skip to main content
10.1145/3184558.3191526acmotherconferencesArticle/Chapter ViewAbstractPublication PageswwwConference Proceedingsconference-collections
research-article
Free Access

Continuous-Time Dynamic Network Embeddings

Published:23 April 2018Publication History

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.

References

  1. Charu Aggarwal and Karthik Subbian. 2014. Evolutionary network analysis: A survey. CSUR Vol. 47, 1 (2014), 10. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  3. Charu C Aggarwal, Yuchen Zhao, and S Yu Philip. 2011. Outlier detection in graph streams. In ICDE. IEEE, 399--409. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander S. Smola. 2013. Distributed large-scale natural graph factorization WWW. 37--48. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  6. Nesreen Kamel Ahmed and Ryan Anthony Rossi. 2015. Interactive Visual Graph Analytics on the Web. In ICWSM. 566--569.Google ScholarGoogle Scholar
  7. 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 ScholarGoogle Scholar
  8. 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 ScholarGoogle Scholar
  9. Mikhail Belkin and Partha Niyogi. 2002. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation Vol. 15 (2002), 1373--1396. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Toine Bogers. 2010. Movie recommendation using random walks over the contextual graph Context-Aware Recommender Systems.Google ScholarGoogle Scholar
  11. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  12. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  13. 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 ScholarGoogle ScholarCross RefCross Ref
  14. Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2015. GraRep: Learning graph representations with global structural information CIKM. ACM, 891--900. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. Rémy Cazabet and Frédéric Amblard. 2014. Dynamic community detection. In ESNAM. Springer, 404--414.Google ScholarGoogle Scholar
  17. Fan Chung. 2007. Random walks and local cuts in graphs. Linear Algebra and its applications Vol. 423, 1 (2007), 22--32.Google ScholarGoogle Scholar
  18. Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. 2017. metapath2vec: Scalable Representation Learning for Heterogeneous Networks SIGKDD. 135--144. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  20. 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 ScholarGoogle ScholarCross RefCross Ref
  21. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  22. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  23. David F. Gleich and Ryan A. Rossi. 2014. A Dynamical System for PageRank with Time-Dependent Teleportation. Internet Mathematics (2014), 188--217.Google ScholarGoogle Scholar
  24. A. Goyal, F. Bonchi, and L.V.S. Lakshmanan. 2010. Learning influence probabilities in social networks WSDM. ACM, 241--250. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. Leo Grady. 2006. Random walks for image segmentation. TPAMI Vol. 28, 11 (2006), 1768--1783. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In SIGKDD. 855--864. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. Sudipto Guha and Andrew McGregor. 2012. Graph synopses, sketches, and streams: A survey. VLDB Vol. 5, 12 (2012), 2030--2031. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. Ryohei Hisano. 2016. Semi-supervised Graph Embedding Approach to Dynamic Link Prediction. arXiv preprint arXiv:1610.04351 (2016).Google ScholarGoogle Scholar
  29. P. Holme and J. Saram"aki. 2012. Temporal networks. Physics Reports (2012).Google ScholarGoogle Scholar
  30. Akshay Java, Pranam Kolari, Tim Finin, and Tim Oates. 2006. Modeling the spread of influence on the blogosphere WWW. 22--26.Google ScholarGoogle Scholar
  31. 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 ScholarGoogle Scholar
  32. 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 ScholarGoogle ScholarCross RefCross Ref
  33. Nitin Kamra, Umang Gupta, and Yan Liu. 2017. Deep Generative Dual Memory Network for Continual Learning. arXiv preprint, arXiv:1710.10368 (2017).Google ScholarGoogle Scholar
  34. 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 ScholarGoogle Scholar
  35. V.E. Krebs. 2002. Mapping networks of terrorist cells. Connections Vol. 24, 3 (2002), 43--52.Google ScholarGoogle Scholar
  36. Jean-Louis Lassez, Ryan Rossi, and Kumar Jeev. 2008. Ranking Links on the Web: Search and Surf Engines. In IEA/AIE. 199--208. Google ScholarGoogle ScholarDigital LibraryDigital Library
  37. John Boaz Lee, Ryan Rossi, and Xiangnan Kong. 2017. Deep Graph Attention Model. In arXiv:1709.06075.Google ScholarGoogle Scholar
  38. Lizi Liao, Xiangnan He, Hanwang Zhang, and Tat-Seng Chua. 2017. Attributed Social Network Embedding. arXiv preprint arXiv:1705.04969 (2017).Google ScholarGoogle Scholar
  39. W. Liu and L. Lü. 2010. Link prediction based on local random walk. Europhysics Letters Vol. 89 (2010), 58007.Google ScholarGoogle ScholarCross RefCross Ref
  40. László Lovász. 1993. Random walks on graphs. Combinatorics Vol. 2 (1993), 1--46.Google ScholarGoogle Scholar
  41. S. Maslov and K. Sneppen. 2002. Specificity and stability in topology of protein networks. Science Vol. 296, 5569 (2002), 910--913.Google ScholarGoogle Scholar
  42. R.M. May and A.L. Lloyd. 2001. Infection dynamics on scale-free networks. Physical Review E Vol. 64, 6 (2001), 66112.Google ScholarGoogle ScholarCross RefCross Ref
  43. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  44. Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient estimation of word representations in vector space ICLR Workshop. 10.Google ScholarGoogle Scholar
  45. 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 ScholarGoogle ScholarCross RefCross Ref
  46. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  47. 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 ScholarGoogle ScholarCross RefCross Ref
  48. Andrew Y Ng, Michael I Jordan, and Yair Weiss. 2002. On spectral clustering: Analysis and an algorithm. In NIPS. 849--856. Google ScholarGoogle ScholarDigital LibraryDigital Library
  49. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  50. L. Page, S. Brin, R. Motwani, and T. Winograd. 1998. PageRank citation ranking: Bringing order to the web. Stanford Tech. Report (1998).Google ScholarGoogle Scholar
  51. R. Pastor-Satorras and A. Vespignani. 2001. Epidemic spreading in scale-free networks. Physical Review Letters Vol. 86, 14 (2001), 3200--3203.Google ScholarGoogle ScholarCross RefCross Ref
  52. Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations SIGKDD. 701--710. Google ScholarGoogle ScholarDigital LibraryDigital Library
  53. 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 ScholarGoogle Scholar
  54. 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 ScholarGoogle ScholarCross RefCross Ref
  55. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  56. Leonardo F.R. Ribeiro, Pedro H.P. Saverese, and Daniel R. Figueiredo. 2017. Struc2Vec: Learning Node Representations from Structural Identity SIGKDD. 385--394. Google ScholarGoogle ScholarDigital LibraryDigital Library
  57. Ryan Rossi and Jennifer Neville. 2012. Time-evolving Relational Classification and Ensemble Methods PAKDD. 13.Google ScholarGoogle Scholar
  58. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  59. Ryan A. Rossi, Brian Gallagher, Jennifer Neville, and Keith Henderson. 2013. Modeling Dynamic Behavior in Large Evolving Graphs WSDM. ACM, 667--676. Google ScholarGoogle ScholarDigital LibraryDigital Library
  60. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  61. Ryan A. Rossi, Rong Zhou, and Nesreen K. Ahmed. 2017. Deep Feature Learning for Graphs. In arXiv:1704.08829.Google ScholarGoogle Scholar
  62. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  63. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  64. Jimeng Sun, Christos Faloutsos, Spiros Papadimitriou, and Philip S Yu. 2007. GraphScope: parameter-free mining of large time-evolving graphs SIGKDD. 687--696. Google ScholarGoogle ScholarDigital LibraryDigital Library
  65. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  66. 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 ScholarGoogle Scholar
  67. D.J. Watts and S.H. Strogatz. 1998. Collective dynamics of small-world networks. Nature Vol. 393, 6684 (1998), 440--442.Google ScholarGoogle Scholar

Index Terms

  1. Continuous-Time Dynamic Network Embeddings

            Recommendations

            Comments

            Login options

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

            Sign in

            PDF Format

            View or Download as a PDF file.

            PDF

            eReader

            View online with eReader.

            eReader

            HTML Format

            View this article in HTML Format .

            View HTML Format