ABSTRACT
Networks evolve continuously over time with the addition, deletion, and changing of links and nodes. Although many networks contain this type of temporal information, the majority of research in network representation learning has focused on static snapshots of the graph and has largely ignored the temporal dynamics of the network. In this work, we describe a general framework for incorporating temporal information into network embedding methods. The framework gives rise to methods for learning time-respecting embeddings from continuous-time dynamic networks. Overall, the experiments demonstrate the effectiveness of the proposed framework and dynamic network embedding approach as it achieves an average gain of 11.9% across all methods and graphs. The results indicate that modeling temporal dependencies in graphs is important for learning appropriate and meaningful network representations.
- Charu Aggarwal and Karthik Subbian. 2014. Evolutionary network analysis: A survey. CSUR Vol. 47, 1 (2014), 10. Google ScholarDigital Library
- Charu C Aggarwal, Yao Li, Philip S Yu, and Ruoming Jin. 2010. On dense pattern mining in graph streams. VLDB Vol. 3, 1--2 (2010), 975--984. Google ScholarDigital Library
- Charu C Aggarwal, Yuchen Zhao, and S Yu Philip. 2011. Outlier detection in graph streams. In ICDE. IEEE, 399--409. Google ScholarDigital Library
- Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander S. Smola. 2013. Distributed large-scale natural graph factorization WWW. 37--48. Google ScholarDigital Library
- Nesreen K. Ahmed, Nick Duffield, Theodore L. Willke, and Ryan A. Rossi. 2017 a. On Sampling from Massive Graph Streams. In VLDB. 1430--1441. Google ScholarDigital Library
- Nesreen Kamel Ahmed and Ryan Anthony Rossi. 2015. Interactive Visual Graph Analytics on the Web. In ICWSM. 566--569.Google Scholar
- Nesreen K. Ahmed, Ryan A. Rossi, Rong Zhou, John Boaz Lee, Xiangnan Kong, Theodore L. Willke, and Hoda Eldardiry. 2017 b. Inductive Representation Learning in Large Attributed Graphs WiML NIPS.Google Scholar
- R. Albert, H. Jeong, and A.L. Barabási. 1999. Internet: Diameter of the world-wide web. Nature Vol. 401, 6749 (1999), 130--131.Google Scholar
- Mikhail Belkin and Partha Niyogi. 2002. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation Vol. 15 (2002), 1373--1396. Google ScholarDigital Library
- Toine Bogers. 2010. Movie recommendation using random walks over the contextual graph Context-Aware Recommender Systems.Google Scholar
- A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. 2000. Graph structure in the web. Computer Networks Vol. 33, 1--6 (2000), 309--320. Google ScholarDigital Library
- Zhuhua Cai, Dionysios Logothetis, and Georgos Siganos. 2012. Facilitating real-time graph mining. In Proceedings of the Fourth International Workshop on Cloud Data Management. 8. Google ScholarDigital Library
- J. Camacho, R. Guimerà, and L.A. Nunes Amaral. 2002. Robust patterns in food web structure. Physical Review Letters Vol. 88, 22 (2002), 228102: 1--4.Google ScholarCross Ref
- Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2015. GraRep: Learning graph representations with global structural information CIKM. ACM, 891--900. Google ScholarDigital Library
- Sandro Cavallari, Vincent W Zheng, Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cambria. 2017. Learning community embedding with community detection and node embedding on graphs CIKM. 377--386. Google ScholarDigital Library
- Rémy Cazabet and Frédéric Amblard. 2014. Dynamic community detection. In ESNAM. Springer, 404--414.Google Scholar
- Fan Chung. 2007. Random walks and local cuts in graphs. Linear Algebra and its applications Vol. 423, 1 (2007), 22--32.Google Scholar
- Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. 2017. metapath2vec: Scalable Representation Learning for Heterogeneous Networks SIGKDD. 135--144. Google ScholarDigital Library
- Daniel M Dunlavy, Tamara G Kolda, and Evrim Acar. 2011. Temporal link prediction using matrix and tensor factorizations. TKDD Vol. 5, 2 (2011), 10. Google ScholarDigital Library
- J.A. Dunne, R.J. Williams, and N.D. Martinez. 2002. Food-web structure and network theory: The role of connectance and size. Proceedings of the National Academy of Sciences of the United States of America Vol. 99, 20 (2002), 12917.Google ScholarCross Ref
- M. Faloutsos, P. Faloutsos, and C. Faloutsos. 1999. On power-law relationships of the internet topology Proceedings of the ACM SIGCOMM International Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. 251--262. Google ScholarDigital Library
- Wenjie Fu, Le Song, and Eric P Xing. 2009. Dynamic mixed membership blockmodel for evolving networks Proceedings of the 26th Annual International Conference on Machine Learning. 329--336. Google ScholarDigital Library
- David F. Gleich and Ryan A. Rossi. 2014. A Dynamical System for PageRank with Time-Dependent Teleportation. Internet Mathematics (2014), 188--217.Google Scholar
- A. Goyal, F. Bonchi, and L.V.S. Lakshmanan. 2010. Learning influence probabilities in social networks WSDM. ACM, 241--250. Google ScholarDigital Library
- Leo Grady. 2006. Random walks for image segmentation. TPAMI Vol. 28, 11 (2006), 1768--1783. Google ScholarDigital Library
- Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In SIGKDD. 855--864. Google ScholarDigital Library
- Sudipto Guha and Andrew McGregor. 2012. Graph synopses, sketches, and streams: A survey. VLDB Vol. 5, 12 (2012), 2030--2031. Google ScholarDigital Library
- Ryohei Hisano. 2016. Semi-supervised Graph Embedding Approach to Dynamic Link Prediction. arXiv preprint arXiv:1610.04351 (2016).Google Scholar
- P. Holme and J. Saram"aki. 2012. Temporal networks. Physics Reports (2012).Google Scholar
- Akshay Java, Pranam Kolari, Tim Finin, and Tim Oates. 2006. Modeling the spread of influence on the blogosphere WWW. 22--26.Google Scholar
- H. Jeong, S.P. Mason, A.L. Barabasi, and Z.N. Oltvai. 2001. Lethality and centrality in protein networks. arXiv preprint cond-mat/0105306 (2001).Google Scholar
- H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, and A.L. Barabási. 2000. The large-scale organization of metabolic networks. Nature Vol. 407, 6804 (2000), 651--654.Google ScholarCross Ref
- Nitin Kamra, Umang Gupta, and Yan Liu. 2017. Deep Generative Dual Memory Network for Continual Learning. arXiv preprint, arXiv:1710.10368 (2017).Google Scholar
- A. Kleczkowski and B.T. Grenfell. 1999. Mean-field-type equations for spread of epidemics: The small world model. Physica A: Statistical Mechanics and its Applications Vol. 274, 1--2 (1999), 355--360.Google Scholar
- V.E. Krebs. 2002. Mapping networks of terrorist cells. Connections Vol. 24, 3 (2002), 43--52.Google Scholar
- Jean-Louis Lassez, Ryan Rossi, and Kumar Jeev. 2008. Ranking Links on the Web: Search and Surf Engines. In IEA/AIE. 199--208. Google ScholarDigital Library
- John Boaz Lee, Ryan Rossi, and Xiangnan Kong. 2017. Deep Graph Attention Model. In arXiv:1709.06075.Google Scholar
- Lizi Liao, Xiangnan He, Hanwang Zhang, and Tat-Seng Chua. 2017. Attributed Social Network Embedding. arXiv preprint arXiv:1705.04969 (2017).Google Scholar
- W. Liu and L. Lü. 2010. Link prediction based on local random walk. Europhysics Letters Vol. 89 (2010), 58007.Google ScholarCross Ref
- László Lovász. 1993. Random walks on graphs. Combinatorics Vol. 2 (1993), 1--46.Google Scholar
- S. Maslov and K. Sneppen. 2002. Specificity and stability in topology of protein networks. Science Vol. 296, 5569 (2002), 910--913.Google Scholar
- R.M. May and A.L. Lloyd. 2001. Infection dynamics on scale-free networks. Physical Review E Vol. 64, 6 (2001), 66112.Google ScholarCross Ref
- A. McGovern, L. Friedland, M. Hay, B. Gallagher, A. Fast, J. Neville, and D. Jensen. 2003. Exploiting Relational Structure to Understand Publication Patterns in High-Energy Physics. SIGKDD Explorations Vol. 5, 2 (2003), 165--172. Google ScholarDigital Library
- Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient estimation of word representations in vector space ICLR Workshop. 10.Google Scholar
- C. Moore and M.E.J. Newman. 2000. Epidemics and percolation in small-world networks. Physical Review E Vol. 61, 5 (2000), 5678--5682.Google ScholarCross Ref
- J. Neville, O. Simsek, D. Jensen, J. Komoroske, K. Palmer, and H. Goldberg. 2005. Using relational knowledge discovery to prevent securities fraud Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. 449--458. Google ScholarDigital Library
- M.E.J. Newman. 2001. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences Vol. 98, 2 (2001), 404--409.Google ScholarCross Ref
- Andrew Y Ng, Michael I Jordan, and Yair Weiss. 2002. On spectral clustering: Analysis and an algorithm. In NIPS. 849--856. Google ScholarDigital Library
- J. O'Madadhain, J. Hutchins, and P. Smyth. 2005. Prediction and ranking algorithms for event-based network data. SIGKDD Explorations Vol. 7, 2 (2005), 30. Google ScholarDigital Library
- L. Page, S. Brin, R. Motwani, and T. Winograd. 1998. PageRank citation ranking: Bringing order to the web. Stanford Tech. Report (1998).Google Scholar
- R. Pastor-Satorras and A. Vespignani. 2001. Epidemic spreading in scale-free networks. Physical Review Letters Vol. 86, 14 (2001), 3200--3203.Google ScholarCross Ref
- Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations SIGKDD. 701--710. Google ScholarDigital Library
- Robert Pienta, James Abello, Minsuk Kahng, and Duen Horng Chau. 2015. Scalable graph exploration and visualization: Sensemaking challenges and opportunities. In BigComp. 271--278.Google Scholar
- Pascal Pons and Matthieu Latapy. 2006. Computing communities in large networks using random walks. J. Graph Alg. Appl. Vol. 10, 2 (2006), 191--218.Google ScholarCross Ref
- Stephen Ranshous, Shitian Shen, Danai Koutra, Steve Harenberg, Christos Faloutsos, and Nagiza F Samatova. 2015. Anomaly detection in dynamic networks: a survey. Wiley Interdisc. Rev.: Comp. Stat. Vol. 7, 3 (2015), 223--247. Google ScholarDigital Library
- Leonardo F.R. Ribeiro, Pedro H.P. Saverese, and Daniel R. Figueiredo. 2017. Struc2Vec: Learning Node Representations from Structural Identity SIGKDD. 385--394. Google ScholarDigital Library
- Ryan Rossi and Jennifer Neville. 2012. Time-evolving Relational Classification and Ensemble Methods PAKDD. 13.Google Scholar
- Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization AAAI. 4292--4293. deftempurl%http://networkrepository.com tempurl Google ScholarDigital Library
- Ryan A. Rossi, Brian Gallagher, Jennifer Neville, and Keith Henderson. 2013. Modeling Dynamic Behavior in Large Evolving Graphs WSDM. ACM, 667--676. Google ScholarDigital Library
- Ryan A. Rossi and Jennifer Neville. 2010. Modeling the Evolution of Discussion Topics and Communication to Improve Relational Classification. In SIGKDD SOMA. 89--97. Google ScholarDigital Library
- Ryan A. Rossi, Rong Zhou, and Nesreen K. Ahmed. 2017. Deep Feature Learning for Graphs. In arXiv:1704.08829.Google Scholar
- Sergio D Servetto and Guillermo Barrenechea. 2002. Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks. In Wireless Sensor Networks & App. 12--21. Google ScholarDigital Library
- Sucheta Soundarajan, Acar Tamersoy, Elias B Khalil, Tina Eliassi-Rad, Duen Horng Chau, Brian Gallagher, and Kevin Roundy. 2016. Generating graph snapshots from streaming edge data Proceedings of the 25th International Conference Companion on World Wide Web. 109--110. Google ScholarDigital Library
- Jimeng Sun, Christos Faloutsos, Spiros Papadimitriou, and Philip S Yu. 2007. GraphScope: parameter-free mining of large time-evolving graphs SIGKDD. 687--696. Google ScholarDigital Library
- Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. LINE: Large-scale Information Network Embedding. In WWW. 1067--1077. Google ScholarDigital Library
- A. Wagner and D.A. Fell. 2001. The small world inside large metabolic networks. Proceedings of the Royal Society of London. Series B: Biological Sciences Vol. 268, 1478 (2001), 1803--1810.Google Scholar
- D.J. Watts and S.H. Strogatz. 1998. Collective dynamics of small-world networks. Nature Vol. 393, 6684 (1998), 440--442.Google Scholar
Index Terms
- Continuous-Time Dynamic Network Embeddings
Recommendations
Continuous-Time Link Prediction via Temporal Dependent Graph Neural Network
WWW '20: Proceedings of The Web Conference 2020Recently, graph neural networks (GNNs) have been shown to be an effective tool for learning the node representations of the networks and have achieved good performance on the semi-supervised node classification task. However, most existing GNNs methods ...
Higher-order Network Representation Learning
WWW '18: Companion Proceedings of the The Web Conference 2018This paper describes a general framework for learning Higher-Order Network Embeddings (HONE) from graph data based on network motifs. The HONE framework is highly expressive and flexible with many interchangeable components. The experimental results ...
Continuous temporal network embedding by modeling neighborhood propagation process
AbstractNetwork embedding has become the focal point of increasing research interests in academic and industrial domains. Temporal networks are evolved by adding nodes and edges sequentially, which should be regarded as neighborhood propagation processes ...
Comments