research-article

A Layout-Based Classification Method for Visualizing Time-Varying Graphs

Authors:

Chenhui LiAuthors Info & Claims

ACM Transactions on Knowledge Discovery from Data (TKDD), Volume 15, Issue 4

Article No.: 54, Pages 1 - 24

https://doi.org/10.1145/3441301

Published: 26 March 2021 Publication History

Abstract

Connectivity analysis between the components of large evolving systems can reveal significant patterns of interaction. The systems can be simulated by topological graph structures. However, such analysis becomes challenging on large and complex graphs. Tasks such as comparing, searching, and summarizing structures, are difficult due to the enormous number of calculations required. For time-varying graphs, the temporal dimension even intensifies the difficulty. In this article, we propose to reduce the complexity of analysis by focusing on subgraphs that are induced by closely related entities. To summarize the diverse structures of subgraphs, we build a supervised layout-based classification model. The main premise is that the graph structures can induce a unique appearance of the layout. In contrast to traditional graph theory-based and contemporary neural network-based methods of graph classification, our approach generates low costs and there is no need to learn informative graph representations. Combined with temporally stable visualizations, we can also facilitate the understanding of sub-structures and the tracking of graph evolution. The method is evaluated on two real-world datasets. The results show that our system is highly effective in carrying out visual-based analytics of large graphs.

References

[1]

Gaurav Agarwal and David Kempe. 2008. Modularity-maximizing graph communities via mathematical programming. The European Physical Journal B 66, 3 (2008), 409--418.

[2]

Benjamin Bach, Emmanuel Pietriga, and Jean-Daniel Fekete. 2014. GraphDiaries: Animated transitions and temporal navigation for dynamic networks. IEEE Transactions on Visualization and Computer Graphics 20, 5 (2014), 740--754.

Digital Library

[3]

Shweta Bansal, Sanjukta Bhowmick, and Prashant Paymal. 2011. Fast community detection for dynamic complex networks. Communications in Computer and Information Science 116 (2011), 196--207.

[4]

Mathieu Bastian, Sebastien Heymann, and Mathieu Jacomy. 2009. Gephi: An open source software for exploring and manipulating networks. In Proceedings of the 3rd International AAAI Conference on Weblogs and Social Media.

[5]

Fabian Beck, Michael Burch, Stephan Diehl, and Daniel Weiskopf. 2017. A taxonomy and survey of dynamic graph visualization. Computer Graphics Forum 36, 1 (2017), 133--159.

Digital Library

[6]

Mikhail Belkin and Partha Niyogi. 2001. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Proceedings of the Advances in Neural Information Processing Systems. 585--591.

[7]

Michele Berlingerio, Danai Koutra, Tina Eliassirad, and Christos Faloutsos. 2012. NetSimile: A scalable approach to size-independent network similarity. Computer Science 12, 1 (2012), 28(1--28).

[8]

Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008, 10 (2008), P10008.

[9]

Béla Bollobás. 2013. Modern Graph Theory. Vol. 184. Springer Science & Business Media.

[10]

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

Digital Library

[11]

Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. 2007. On modularity clustering. IEEE Transactions on Knowledge and Data Engineering 20, 2 (2007), 172--188.

Digital Library

[12]

Matthew Brehmer, Bongshin Lee, Benjamin Bach, Nathalie Henry Riche, and Tamara Munzner. 2016. Timelines revisited: A design space and considerations for expressive storytelling. IEEE Transactions on Visualization and Computer Graphics 22, 1 (2016), 449--458.

Digital Library

[13]

Chen Cai and Yusu Wang. 2019. A simple yet effective baseline for non-attribute graph classification. In 7th International Conference on Learning Representations Workshop on Representation Learning on Graphs and Manifolds.

[14]

Inderjit Dhillon, Yuqiang Guan, and Brian Kulis. 2005. A fast kernel-based multilevel algorithm for graph clustering. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. 629--634.

Digital Library

[15]

Inderjit Dhillon, Yuqiang Guan, and Brian Kulis. 2007. Weighted graph cuts without eigenvectors a multilevel approach. IEEE Transactions on Pattern Analysis and Machine Intelligence 29, 11 (2007), 1944--1957.

Digital Library

[16]

Stephan Diehl, Carsten Görg, and Andreas Kerren. 2001. Preserving the mental map using foresighted layout. In Proceedings of the Data Visualization 2001. Springer, 175--184.

[17]

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

Digital Library

[18]

Tim Dwyer. 2009. Scalable, versatile and simple constrained graph layout. Computer Graphics Forum 28, 3 (2009), 991--998.

[19]

Paolo Federico, Jurgen Pfeffer, Wolfgang Aigner, Silvia Miksch, and Lukas Zenk. 2012. Visual analysis of dynamic networks using change centrality. In Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining (ASONAM’12). IEEE Computer Society, 179--183.

Digital Library

[20]

Kun-Chuan Feng, Chaoli Wang, Han-Wei Shen, and Tong-Yee Lee. 2012. Coherent time-varying graph drawing with multifocus+ context interaction. IEEE Transactions on Visualization and Computer Graphics 18, 8 (2012), 1330--1342.

Digital Library

[21]

Francesco Folino and Clara Pizzuti. 2014. An evolutionary multiobjective approach for community discovery in dynamic networks. IEEE Transactions on Knowledge and Data Engineering 26, 8 (2014), 1838--1852.

[22]

Yaniv Frishman and Ayellet Tal. 2004. Dynamic drawing of clustered graphs. In Proceedings of the IEEE Symposium on Information Visualization. IEEE, 191--198.

Digital Library

[23]

Laetitia Gauvin, André Panisson, and Ciro Cattuto. 2014. Detecting the community structure and activity patterns of temporal networks: A non-negative tensor factorization approach. PloS One 9, 1 (2014), e86028.

[24]

Aristides Gionis, Heikki Mannila, and Panayiotis Tsaparas. 2007. Clustering aggregation. ACM Transactions on Knowledge Discovery from Data 1, 1 (2007), 4.

[25]

Michelle Girvan and Mark E. J. Newman. 2002. Community structure in social and biological networks. In Proceedings of the National Academy of Sciences. Vol. 99. National Academy of Sciences, 7821--7826.

[26]

William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Representation learning on graphs: Methods and applications. In Proceedings of the Advances in Neural Information Processing Systems. 1024--1034.

[27]

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR’16). 770--778.

[28]

Bruce Hendrickson and Robert Leland. 1995. A multi-level algorithm for partitioning graphs. In Proceedings of the 1995 ACM/IEEE Conference on Supercomputing. Vol. 95. 1--14.

[29]

Yifan Hu. 2005. Efficient, high-quality force-directed graph drawing. Mathematica Journal 10, 1 (2005), 37--71.

[30]

George Karypis and Vipin Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20, 1 (1998), 359--392.

Digital Library

[31]

Daniel A. Keim. 2002. Information visualization and visual data mining. IEEE Transactions on Visualization and Computer Graphics 8, 1 (2002), 1--8.

Digital Library

[32]

Stephen G. Kobourov. 2012. Spring embedders and force directed graph drawing algorithms. arXiv preprint arXiv:1201.3011 (2012).

[33]

Gueorgi Kossinets. 2012. Processed Wikipedia edit history. Retrieved from http://snap.stanford.edu/data/bigdata/wikipedia08/enwiki-20080103.

[34]

Oh-Hyun Kwon, Tarik Crnovrsanin, and Kwan-Liu Ma. 2018. What would a graph look like in this layout? A machine learning approach to large graph visualization. IEEE Transactions on Visualization and Computer Graphics 24, 1 (2018), 478--488.

[35]

John Boaz Lee, Ryan Rossi, and Xiangnan Kong. 2018. Graph classification using structural attention. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1666--1674.

Digital Library

[36]

Robert Leland and Bruce Hendrickson. 1994. An empirical study of static load balancing algorithms. In Proceedings of the IEEE Scalable High Performance Computing Conference. 682--685.

[37]

Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Governance in social media: A case study of the wikipedia promotion process. In Proceedings of the 4th International AAAI Conference on Weblogs and Social Media.

[38]

Chenhui Li, George Baciu, and Yunzhe Wang. 2015. ModulGraph: Modularity-based visualization of massive graphs. In Proceedings of the SIGGRAPH Asia 2015 Visualization in High Performance Computing. ACM, 11.

Digital Library

[39]

Qingsong Liu, Yifan Hu, Lei Shi, Xinzhu Mu, Yutao Zhang, and Jie Tang. 2015. EgoNetCloud: Event-based egocentric dynamic network visualization. In Proceedings of the IEEE Conference on Visual Analytics Science and Technology (VAST’15). IEEE, 65--72.

[40]

Dijun Luo, Chris Ding, Heng Huang, and Feiping Nie. 2011. Consensus spectral clustering in near-linear time. In Proceedings of the 2011 IEEE 27th International Conference on Data Engineering. 1079--1090.

Digital Library

[41]

Gary L. Miller, Shang Hua Teng, William Thurston, and Stephen A. Vavasis. 1998. Geometric separators for finite-element meshes. SIAM Journal on Scientific Computing 19, 2 (1998), 364--386.

Digital Library

[42]

Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. 2019. Relational pooling for graph representations. In International Conference on Machine Learning. 4663--4673.

[43]

Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang P. Liu, and Shantanu Jaiswal. 2017. Graph2Vec: Learning distributed representations of graphs. ArXiv abs/1707.05005 (2017).

[44]

Andrew Ng, Michael I. Jordan, and Yair Weiss. 2001. On spectral clustering: Analysis and an algorithm. In Proceedings of the Advances in Neural Information Processing Systems. 849--856.

[45]

Dang Khoa Nguyen, Wei Luo, Tu Dinh Nguyen, Svetha Venkatesh, and Dinh Phung. 2018. Learning graph representation via frequent subgraphs. In Proceedings of the 2018 SIAM International Conference on Data Mining. 306--314.

[46]

Quan Hoang Nguyen, Seok-Hee Hong, Peter Eades, and Amyra Meidiana. 2017. Proxy graph: Visual quality metrics of big graph sampling. IEEE Transactions on Visualization and Computer Graphics 23, 6 (2017), 1600--1611.

Digital Library

[47]

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. Pytorch: An imperative style, high-performance deep learning library. In Proceedings of the Advances in Neural Information Processing Systems. 8026--8037.

[48]

Helen C. Purchase, Eve E. Hoggan, and Carsten Görg. 2006. How important is the ”mental map”? - An empirical investigation of a dynamic graph layout algorithm. In Proceedings of the International Symposium on Graph Drawing.

[49]

Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Physical Review 76, 3 Pt 2 (2007), 036106.

[50]

Giulio Rossetti and Rémy Cazabet. 2018. Community discovery in dynamic networks: A survey. Computing Surveys 51, 2 (2018), 1--37.

Digital Library

[51]

Giulio Rossetti, Luca Pappalardo, Dino Pedreschi, and Fosca Giannotti. 2016. Tiles: An online algorithm for community discovery in dynamic social networks. Machine Learning 106, 8 (2016), 1213--1241.

Digital Library

[52]

Martin Rosvall and Carl T. Bergstrom. 2008. Maps of random walks on complex networks reveal community structure. In Proceedings of the National Academy of Sciences of the United States of America. Vol. 105. 1118--1123.

[53]

Jiaxing Shang, Lianchen Liu, Feng Xie, Zhen Chen, Jiajia Miao, Xuelin Fang, and Cheng Wu. 2012. A real-time detecting algorithm for tracking community structure of dynamic networks. In 6th International Workshop on Social Network Mining and Analysis.

[54]

Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. 2011. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 12, 9 (2011), 2539--2561.

Digital Library

[55]

Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. 2009. Efficient graphlet kernels for large graph comparison. In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. 488--495.

[56]

Zhiqiang Tao, Hongfu Liu, Sheng Li, Zhengming Ding, and Yun Fu. 2019. Robust spectral ensemble clustering via rank minimization. ACM Transactions on Knowledge Discovery from Data 13, 1 (2019), 4.1--4.25.

[57]

Corinna Vehlow, Fabian Beck, Patrick Auwärter, and Daniel Weiskopf. 2015. Visualizing the evolution of communities in dynamic graphs. Computer Graphics Forum 34, 1 (2015), 277--288.

Digital Library

[58]

Corinna Vehlow, Fabian Beck, and Daniel Weiskopf. 2017. Visualizing group structures in graphs: A survey. Computer Graphics Forum 36, 6 (2017), 201--225.

Digital Library

[59]

Scott White and Padhraic Smyth. 2005. A spectral clustering approach to finding communities in graph. In Proceedings of the 2005 SIAM International Conference on Data Mining. SIAM. 274--285.

[60]

Jia Wu, Shirui Pan, Xingquan Zhu, Chengqi Zhang, and Philip S. Yu. 2018. Multiple structure-view learning for graph classification. IEEE Transactions on Neural Networks and Learning Systems 29, 7 (2018), 3236--3251.

[61]

Yanhong Wu, Naveen Pitipornvivat, Jian Zhao, Sixiao Yang, Guowei Huang, and Huamin Qu. 2016. EgoSlider: Visual analysis of egocentric network evolution. IEEE Transactions on Visualization and Computer Graphics 22, 1 (2016), 260--269.

Digital Library

[62]

Pinar Yanardag and S. V. N Vishwanathan. 2015. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1365--1374.

Digital Library

[63]

Jaewon Yang and Jure Leskovec. 2015. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42, 1 (2015), 181--213.

Digital Library

[64]

Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. 2019. GNNExplainer: Generating explanations for graph neural networks. In Proceedings of the Advances in Neural Information Processing Systems. Vol. 32. 9244--9255.

[65]

Anita Zakrzewska and David A. Bader. 2015. A dynamic algorithm for local community detection in graphs. In Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’15). 559--564.

[66]

Xinyi Zhang and Lihui Chen. 2019. Capsule graph neural network. In Proceedings of the International Conference on Learning Representations.

[67]

Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. 2009. Graph clustering based on structural/attribute similarities. In Proceedings of the VLDB Endowment. Vol. 2. 718--729.

Digital Library

Cited By

Yang YSun YJu FWang SGao JYin B(2023)Multi-graph Fusion Graph Convolutional Networks with pseudo-label supervisionNeural Networks10.1016/j.neunet.2022.11.027158:C(305-317)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.neunet.2022.11.027
Ma PWu YLi YGuo LJiang HZhu XWu X(2022)HW-Forest: Deep Forest with Hashing Screening and Window ScreeningACM Transactions on Knowledge Discovery from Data10.1145/353219316:6(1-24)Online publication date: 30-Jul-2022
https://dl.acm.org/doi/10.1145/3532193
Linhares CPonciano JPedro DRocha LTraina APoco J(2022)LargeNetVis: Visual Exploration of Large Temporal Networks Based On Community TaxonomiesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.3209477(1-11)Online publication date: 2022
https://doi.org/10.1109/TVCG.2022.3209477
Show More Cited By

Index Terms

A Layout-Based Classification Method for Visualizing Time-Varying Graphs
1. Computing methodologies
  1. Machine learning
2. Human-centered computing
  1. Visualization
    1. Visualization design and evaluation methods

Recommendations

Layout of Graphs with Bounded Tree-Width

A queue layout of a graph consists of a total order of the vertices, and a partition of the edges into queues , such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph is its queue-number . A ...
Discovering patterns in time-varying graphs: a triclustering approach

This paper introduces a novel technique to track structures in time varying graphs. The method uses a maximum a posteriori approach for adjusting a three-dimensional co-clustering of the source vertices, the destination vertices and the time, to the ...
Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G@?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Knowledge Discovery from Data

ACM Transactions on Knowledge Discovery from Data Volume 15, Issue 4

August 2021

486 pages

ISSN:1556-4681

EISSN:1556-472X

DOI:10.1145/3458847

Editor:
Charu Aggarwal
IBM T. J. Watson Research, USA

Issue’s Table of Contents

Copyright © 2021 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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 March 2021

Accepted: 01 December 2020

Revised: 01 August 2020

Received: 01 February 2020

Published in TKDD Volume 15, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Natural Science Foundation of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
257
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)3

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang YSun YJu FWang SGao JYin B(2023)Multi-graph Fusion Graph Convolutional Networks with pseudo-label supervisionNeural Networks10.1016/j.neunet.2022.11.027158:C(305-317)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.neunet.2022.11.027
Ma PWu YLi YGuo LJiang HZhu XWu X(2022)HW-Forest: Deep Forest with Hashing Screening and Window ScreeningACM Transactions on Knowledge Discovery from Data10.1145/353219316:6(1-24)Online publication date: 30-Jul-2022
https://dl.acm.org/doi/10.1145/3532193
Linhares CPonciano JPedro DRocha LTraina APoco J(2022)LargeNetVis: Visual Exploration of Large Temporal Networks Based On Community TaxonomiesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.3209477(1-11)Online publication date: 2022
https://doi.org/10.1109/TVCG.2022.3209477
Burch Mten Brinke KCastella APeters GShteriyanov VVlasvinkel R(2021)Dynamic graph exploration by interactively linked node-link diagrams and matrix visualizationsVisual Computing for Industry, Biomedicine, and Art10.1186/s42492-021-00088-84:1Online publication date: 7-Sep-2021
https://doi.org/10.1186/s42492-021-00088-8
Wang HLi YLin JCao HJin D(2021)Context-Aware Semantic Annotation of Mobility RecordsACM Transactions on Knowledge Discovery from Data10.1145/347704816:3(1-20)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.1145/3477048
Jiang MD’Souza JAuer SDownie J(2021)Evaluating BERT-based scientific relation classifiers for scholarly knowledge graph construction on digital library collectionsInternational Journal on Digital Libraries10.1007/s00799-021-00313-y23:2(197-215)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1007/s00799-021-00313-y
Wang HLiu GHu P(undefined)TDAN: Transferable Domain Adversarial Network for Link Prediction in Heterogeneous Social NetworksACM Transactions on Knowledge Discovery from Data10.1145/3610229
https://dl.acm.org/doi/10.1145/3610229

View Options

Get Access

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents