More Web Proxy on the site http://driver.im/

research-article

Public Access

Atlas: local graph exploration in a global context

Authors:

Duen Horng ChauAuthors Info & Claims

IUI '19: Proceedings of the 24th International Conference on Intelligent User Interfaces

Pages 165 - 176

https://doi.org/10.1145/3301275.3302275

Published: 17 March 2019 Publication History

Abstract

Graphs are everywhere, growing increasingly complex, and still lack scalable, interactive tools to support sensemaking. To address this problem, we present Atlas, an interactive graph exploration system that adapts scalable edge decomposition to enable a new paradigm for large graph exploration, generating explorable multi-layered representations. Atlas simultaneously reveals peculiar subgraph structures, (e.g., quasi-cliques) and possible vertex roles in connecting such subgraph patterns. Atlas decomposes million-edge graphs in seconds, scaling to graphs with up to 117 million edges. We present the results from a think-aloud user study with three graph experts and highlight discoveries made possible by Atlas when applied to graphs from multiple domains, including suspicious yelp reviews, insider trading, and word embeddings. Atlas runs in-browser and is open-sourced.

Supplementary Material

MP4 File (p165-abello.mp4)

Download
493.19 MB

References

[1]

James Abello, Fred Hohman, and Duen Horng Chau. 2015. 3D exploration of graph layers via vertex cloning. In IEEE Conference on Visual Analytics Science and Technology, Poster.

[2]

James Abello and Jeffrey Korn. 2002. MGV: a system for visualizing massive multidigraphs. IEEE Transactions on Visualization and Computer Graphics 8, 1 (2002), 21--38.

Digital Library

[3]

James Abello and François Queyroi. 2014. Network decomposition into fixed points of degree peeling. Social Network Analysis and Mining 4, 1 (2014), 1--14.

[4]

James Abello, Frank Van Ham, and Neeraj Krishnan. 2006. Ask-graphview: a large scale graph visualization system. IEEE Transactions on Visualization and Computer Graphics 12, 5 (2006), 669--676.

Digital Library

[5]

Basak Alper, Benjamin Bach, Nathalie Henry Riche, Tobias Isenberg, and Jean-Daniel Fekete. 2013. Weighted graph comparison techniques for brain connectivity analysis. In ACM Conference on Human Factors in Computing Systems. ACM, 483--492.

Digital Library

[6]

Basak Alper, Tobias Hollerer, JoAnn Kuchera-Morin, and Angus Forbes. 2011. Stereoscopic highlighting: 2d graph visualization on stereo displays. IEEE Transactions on Visualization and Computer Graphics 17, 12 (2011), 2325--2333.

Digital Library

[7]

Basak E Alper, Nathalie Henry Riche, and Tobias Hollerer. 2014. Structuring the space: a study on enriching node-link diagrams with visual references. In ACM Conference on Human Factors in Computing Systems. ACM, 1825--1834.

Digital Library

[8]

J Ignacio Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, and Alessandro Vespignani. 2006. Large scale networks fingerprinting and visualization using the k-core decomposition. In Advances in Neural Information Processing Systems. 41--50.

Digital Library

[9]

Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh. 2015. Vqa: visual question answering. In IEEE International Conference on Computer Vision. 2425--2433.

Digital Library

[10]

Daniel Archambault, Tamara Munzner, and David Auber. 2007. Grouse: feature-based, steerable graph hierarchy exploration. In The EG and VGTC Conference on Visualization, Vol. 2007. 67--74.

Digital Library

[11]

Daniel Archambault, Tamara Munzner, and David Auber. 2007. Topolayout: multilevel graph layout by topological features. IEEE Transactions on Visualization and Computer Graphics 13, 2 (2007).

Digital Library

[12]

David Auber. 2004. Tulip: a huge graph visualization framework. In Graph drawing software. Springer, 105--126.

[13]

Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. Neural machine translation by jointly learning to align and translate. International Conference on Learning Representations.

[14]

Josh Barnes and Piet Hut. 1986. A hierarchical O (N log N) force-calculation algorithm. Nature 324, 6096(1986), 446.

[15]

Mathieu Bastian, Sebastien Heymann, Mathieu Jacomy, et al. 2009. Gephi: an open source software for exploring and manipulating networks. AAAI Conference on Weblogs and Social Media 8 (2009), 361--362.

[16]

Vladimir Batagelj and Matjaz Zaversnik. 2003. An O(m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049 (2003).

[17]

Michael Baur, Ulrik Brandes, Marco Gaertler, and Dorothea Wagner. 2004. Drawing the AS graph in 2.5 dimensions. In International Symposium on Graph Drawing. Springer, 43--48.

Digital Library

[18]

Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Jauvin. 2003. A neural probabilistic language model. Journal of Machine Learning Research 3, Feb (2003), 1137--1155.

[19]

Michael Bostock, Vadim Ogievetsky, and Jeffrey Heer. 2011. D<sup>3</sup> data-driven documents. IEEE Transactions on Visualization and Computer Graphics 17, 12 (2011), 2301--2309.

Digital Library

[20]

Ulrik Brandes and Steven R Corman. 2003. Visual unrolling of network evolution and the analysis of dynamic discourse. Information Visualization 2, 1 (2003), 40--50.

Digital Library

[21]

Govert G Brinkmann, Kristian FD Rietveld, and Frank W Takes. 2017. Exploiting GPUs for fast force-directed visualization of large-scale networks. In International Conference on Parallel Processing. IEEE, 382--391.

[22]

Nan Cao, Jimeng Sun, Yu-Ru Lin, David Gotz, Shixia Liu, and Huamin Qu. 2010. Facetatlas: multifaceted visualization for rich text corpora. IEEE Transactions on Visualization and Computer Graphics 16, 6 (2010), 1172--1181.

Digital Library

[23]

Duen Horng Chau, Aniket Kittur, Jason I Hong, and Christos Faloutsos. 2011. Apolo: making sense of large network data by combining rich user interaction and machine learning. In ACM Conference on Human Factors in Computing Systems. ACM, 167--176.

Digital Library

[24]

Weiwei Cui, Hong Zhou, Huamin Qu, Pak Chung Wong, and Xiaoming Li. 2008. Geometry-based edge clustering for graph visualization. IEEE Transactions on Visualization and Computer Graphics 14, 6 (2008), 1277--1284.

Digital Library

[25]

Tommy Dang, Paul Murray, and Angus Forbes. 2017. BioLinker: bottom-up exploration of protein interaction networks. In IEEE Pacific Visualization Symposium. IEEE, 265--269.

[26]

Naga Shailaja Dasari, Ranjan Desh, and Mohammad Zubair. 2014. ParK: an efficient algorithm for k-core decomposition on multicore processors. In IEEE International Conference on Big Data. IEEE, 9--16.

[27]

Cody Dunne and Ben Shneiderman. 2013. Motif simplification: improving network visualization readability with fan, connector, and clique glyphs. In ACM Conference on Human Factors in Computing Systems. ACM, 3247--3256.

Digital Library

[28]

John Ellson, Emden Gansner, Lefteris Koutsofios, Stephen C North, and Gordon Woodhull. 2001. Graphviz - open source graph drawing tools. In International Symposium on Graph Drawing. Springer, 483--484.

[29]

Ozan Ersoy, Christophe Hurter, Fernando Paulovich, Gabriel Cantareiro, and Alex Telea. 2011. Skeleton-based edge bundling for graph visualization. IEEE Transactions on Visualization and Computer Graphics 17, 12 (2011), 2364--2373.

Digital Library

[30]

Dezhi Fang, Matthew Keezer, Jacob Williams, Kshitij Kulkarni, Robert Pienta, and Duen Horng Chau. 2017. Carina: interactive million-node graph visualization using web browser technologies. In International Conference on World Wide Web Companion. International World Wide Web Conferences Steering Committee, 775--776.

Digital Library

[31]

Emden R Gansner, Yifan Hu, Stephen North, and Carlos Scheidegger. 2011. Multilevel agglomerative edge bundling for visualizing large graphs. In IEEE Pacific Visualization Symposium. IEEE, 187--194.

Digital Library

[32]

Dedre Gentner and Arthur B Markman. 1997. Structure mapping in analogy and similarity. American Psychologist 52, 1 (1997), 45.

[33]

Jeffrey Heer and Stuart K Card. 2004. DOITrees revisited: scalable, space-constrained visualization of hierarchical data. In Proceedings of the Working Conference on Advanced Visual Interfaces. ACM, 421--424.

Digital Library

[34]

Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. 2012. Rolx: structural role extraction & mining in large graphs. In ACM Conference on Knowledge Discovery and Data Mining. ACM, 1231--1239.

Digital Library

[35]

Ivan Herman, Guy Melançon, and M Scott Marshall. 2000. Graph visualization and navigation in information visualization: A survey. IEEE Transactions on Visualization and Computer Graphics 6, 1 (2000), 24-43.

Digital Library

[36]

Danny Holten. 2006. Hierarchical edge bundles: visualization of adjacency relations in hierarchical data. IEEE Transactions on Visualization and Computer Graphics 12, 5 (2006), 741--748.

Digital Library

[37]

Danny Holten and Jarke J Van Wijk. 2009. Force-directed edge bundling for graph visualization. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 983--990.

Digital Library

[38]

Keith J Holyoak and Paul Thagard. 1997. The analogical mind. American Psychologist 52, 1 (1997), 35.

[39]

Paras Jain, Shang-Tse Chen, Mozhgan Azimpourkivi, Duen Horng Chau, and Bogdan Carbunar. 2015. Spotting suspicious reviews via (quasi-) clique extraction. IEEE Symposium on Security and Privacy, Poster (2015).

[40]

Toma Jeowicz, Milo Kudelka, Jan Plato, and Vaclav Snael. 2013. Visualization of large graphs using gpu computing. In International Conference on Intelligent Networking and Collaborative Systems. IEEE, 662--667.

Digital Library

[41]

Humayun Kabir and Kamesh Madduri. 2017. Parallel k-core decomposition on multicore platforms. In IEEE International Parallel and Distributed Processing Symposium Workshops. IEEE, 1482--1491.

[42]

Danai Koutra, U Kang, Jilles Vreeken, and Christos Faloutsos. 2014. VOG: summarizing and understanding large graphs. In SIAM International Conference on Data Mining. SIAM, 91--99.

[43]

Danai Koutra, U Kang, Jilles Vreeken, and Christos Faloutsos. 2015. Summarizing and understanding large graphs. Statistical Analysis and Data Mining: The ASA Data Science Journal 8, 3 (2015), 183--202.

Digital Library

[44]

Yu-Ru Lin, Jimeng Sun, Nan Cao, and Shixia Liu. 2010. Contextour: contextual contour visual analysis on dynamic multi-relational clustering. In SIAM International Conference on Data Mining. SIAM, 418--429.

[45]

Zhiyuan Lin, Nan Cao, Hanghang Tong, Fei Wang, and U Kang. 2013. Interactive multi-resolution exploration of million node graphs. In IEEE Conference on Visual Analytics Science and Technology, Poster.

[46]

Zhiyuan Lin, Minsuk Kahng, Kaeser Md Sabrin, Duen Horng Polo Chau, Ho Lee, and U Kang. 2014. Mmap: fast billion-scale graph computation on a pc via memory mapping. In IEEE International Conference on Big Data. IEEE, 159--164.

[47]

Peng Mi, Maoyuan Sun, Moeti Masiane, Yong Cao, and Chris North. 2016. Interactive graph layout of a million nodes. In Informatics, Vol. 3. Multidisciplinary Digital Publishing Institute, 23.

[48]

Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781.

[49]

Tamara Munzner. 1997. H3: Laying out large directed graphs in 3D hyperbolic space. In IEEE Symposium on Information Visualization. IEEE, 2--10.

Digital Library

[50]

Alexandros Panagiotidis, Guido Reina, Michael Burch, Tilo Pfannkuch, and Thomas Ertl. 2015. Consistently GPU-accelerated graph visualization. In International Symposium on Visual Information Communication and Interaction. ACM, 35--41.

Digital Library

[51]

Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014. Glove: global vectors for word representation. In Conference on Empirical Methods in Natural Language Processing. 1532--1543.

[52]

Robert Pienta, James Abello, Minsuk Kahng, and Duen Horng Chau. 2015. Scalable graph exploration and visualization: sensemaking challenges and opportunities. In International Conference on Big Data and Smart Computing. IEEE, 271--278.

[53]

Robert Pienta, Fred Hohman, Alex Endert, Acar Tamersoy, Kevin Roundy, Chris Gates, Shamkant Navathe, and Duen Horng Chau. 2018. VIGOR: interactive visual exploration of graph query results. IEEE Transactions on Visualization and Computer Graphics 24, 1 (2018), 215--225.

[54]

Robert Pienta, Fred Hohman, Acar Tamersoy, Alex Endert, Shamkant Navathe, Hanghang Tong, and Duen Horng Chau. 2017. Visual graph query construction and refinement. In ACM International Conference on Management of Data. ACM, 1587--1590.

Digital Library

[55]

Robert Pienta, Minsuk Kahng, Zhiyuan Lin, Jilles Vreeken, Partha Talukdar, James Abello, Ganesh Parameswaran, and Duen Horng Chau. 2017. Facets: adaptive local exploration of large graphs. In SIAM International Conference on Data Mining. SIAM, 597--605.

[56]

Robert Pienta, Acar Tamersoy, Alex Endert, Shamkant Navathe, Hanghang Tong, and Duen Horng Chau. 2016. Visage: interactive visual graph querying. In ACM International Working Conference on Advanced Visual Interfaces. ACM, 272--279.

Digital Library

[57]

Siddhartha Sahu, Amine Mhedhbi, Semih Salihoglu, Jimmy Lin, and M Tamer Özsu. 2017. The ubiquity of large graphs and surprising challenges of graph processing. Proceedings of the VLDB Endowment 11, 4 (2017).

Digital Library

[58]

David Selassie, Brandon Heller, and Jeffrey Heer. 2011. Divided edge bundling for directional network data. IEEE Transactions on Visualization and Computer Graphics 17, 12 (2011), 2354--2363.

Digital Library

[59]

Ben Shneiderman. 2003. The eyes have it: A task by data type taxonomy for information visualizations. In The Craft of Information Visualization. Elsevier, 364--371.

[60]

Acar Tamersoy, Elias Khalil, Bo Xie, Stephen L Lenkey, Bryan R Routledge, Duen Horng Chau, and Shamkant B Navathe. 2014. Large-scale insider trading analysis: patterns and discoveries. Social Network Analysis and Mining 4, 1 (2014), 201.

[61]

StefVan den Elzen and Jarke J Van Wijk. 2014. Multivariate network exploration and presentation: From detail to overview via selections and aggregations. IEEE Transactions on Visualization and Computer Graphics 20, 12 (2014), 2310--2319.

[62]

Tatiana Von Landesberger, Arjan Kuijper, Tobias Schreck, Jörn Kohlhammer, Jarke J van Wijk, J-D Fekete, and Dieter W Fellner. 2011. Visual analysis of large graphs: state-of-the-art and future research challenges. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1719--1749.

[63]

Pak Chung Wong, Chaomei Chen, Carsten Gorg, Ben Shneiderman, John Stasko, and Jim Thomas. 2011. Graph analytics-lessons learned and challenges ahead. IEEE Computer Graphics and Applications 31, 5 (2011).

[64]

Pak Chung Wong, Harlan Foote, George Chin, Patrick Mackey, and Ken Perrine. 2006. Graph signatures for visual analytics. IEEE Transactions on Visualization and Computer Graphics 12, 6 (2006), 1399--1413.

Digital Library

[65]

Pak Chung Wong, Harlan Foote, Patrick Mackey, George Chin, Heidi Sofia, and Jim Thomas. 2008. A dynamic multiscale magnifying tool for exploring large sparse graphs. Information Visualization 7, 2 (2008), 105--117.

Digital Library

[66]

Pak Chung Wong, David Haglin, David Gillen, Daniel Chavarria, Vito Castellana, Cliff Joslyn, Alan Chappell, and Song Zhang. 2015. A visual analytics paradigm enabling trillion-edge graph exploration. In IEEE Symposium on Large Data Analysis and Visualization. IEEE, 57--64.

Digital Library

[67]

Pak Chung Wong, Han-Wei Shen, Christopher R Johnson, Chaomei Chen, and Robert B Ross. 2012. The top 10 challenges in extreme-scale visual analytics. IEEE Computer Graphics and Applications 32, 4 (2012), 63--67.

Digital Library

[68]

Vahan Yoghourdjian, Tim Dwyer, Karsten Klein, Kimbal Marriott, and Michael Wybrow. 2018. Graph thumbnails: identifying and comparing multiple graphs at a glance. In IEEE Transactions on Visualization and Computer Graphics.

Cited By

Amin RHammer PButz A(2024)Using Machine Learning to Improve Interactive Visualizations for Large Collected Traffic Detector DataProceedings of the 29th International Conference on Intelligent User Interfaces10.1145/3640543.3645177(803-816)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1145/3640543.3645177
Abello JBroadwell PTangherlini TZhang H(2023)Disentangling the Folklore HairballFabula10.1515/fabula-2023-000464:1-2(64-91)Online publication date: 18-Jul-2023
https://doi.org/10.1515/fabula-2023-0004
Abello JNakhimovich D(2022)Graph WavesBig Data Research10.1016/j.bdr.2022.100327(100327)Online publication date: Jun-2022
https://doi.org/10.1016/j.bdr.2022.100327
Show More Cited By

Index Terms

Atlas: local graph exploration in a global context
1. Human-centered computing
  1. Visualization
    1. Visualization systems and tools
    2. Visualization techniques
      1. Graph drawings
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Decomposition of a Graph into Two Disjoint Odd Subgraphs

An odd (resp. even) subgraph in a multigraph is its subgraph in which every vertex has odd (resp. even) degree. We say that a multigraph can be decomposed into two odd subgraphs if its edge set can be partitioned into two sets so that both form odd ...
New Lower Bounds for Ramsey Numbers of Graphs and Hypergraphs

Let G be an r-uniform hypergraph. The multicolor Ramsey number r"k(G) is the minimum n such that every k-coloring of the edges of the complete r-uniform hypergraph K^(^r^)"n yields a monochromatic copy of G. Improving slightly upon results from M. ...
New Lower Bounds on the Multicolor Ramsey Numbers rk(C4)

The multicolor Ramsey number rk(C4) is the smallest integer n for which any k-coloring of the edges of the complete graph Kn must produce a monochromatic 4-cycle. It was proved earlier that rk(C4) k2 k+2 for k 1 being a prime power. In this note we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IUI '19: Proceedings of the 24th International Conference on Intelligent User Interfaces

March 2019

713 pages

ISBN:9781450362726

DOI:10.1145/3301275

General Chairs:
Wai-Tat Fu,
Shimei Pan,
Program Chairs:
Oliver Brdiczka,
Polo Chau,
Gaelle Calvary

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 March 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Aeronautics and Space Administration
National Science Foundation

Conference

IUI '19

Sponsor:

IUI '19: 24th International Conference on Intelligent User Interfaces

March 17 - 20, 2019

California, Marina del Ray

Acceptance Rates

IUI '19 Paper Acceptance Rate 71 of 282 submissions, 25%;

Overall Acceptance Rate 746 of 2,811 submissions, 27%

Upcoming Conference

IUI '25

Sponsor:
sigai
sigai

30th International Conference on Intelligent User Interfaces

March 24 - 27, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
615
Total Downloads

Downloads (Last 12 months)108
Downloads (Last 6 weeks)13

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Amin RHammer PButz A(2024)Using Machine Learning to Improve Interactive Visualizations for Large Collected Traffic Detector DataProceedings of the 29th International Conference on Intelligent User Interfaces10.1145/3640543.3645177(803-816)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1145/3640543.3645177
Abello JBroadwell PTangherlini TZhang H(2023)Disentangling the Folklore HairballFabula10.1515/fabula-2023-000464:1-2(64-91)Online publication date: 18-Jul-2023
https://doi.org/10.1515/fabula-2023-0004
Abello JNakhimovich D(2022)Graph WavesBig Data Research10.1016/j.bdr.2022.100327(100327)Online publication date: Jun-2022
https://doi.org/10.1016/j.bdr.2022.100327
Abello JMawhirter DSun K(2019)Taming a Graph Hairball: Local Exploration in a Global ContextBusiness and Consumer Analytics: New Ideas10.1007/978-3-030-06222-4_10(467-490)Online publication date: 31-May-2019
https://doi.org/10.1007/978-3-030-06222-4_10

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents