research-article

Public Access

Streaming Graph Neural Networks

Authors:

Dawei YinAuthors Info & Claims

SIGIR '20: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval

Pages 719 - 728

https://doi.org/10.1145/3397271.3401092

Published: 25 July 2020 Publication History

Abstract

Graphs are used to model pairwise relations between entities in many real-world scenarios such as social networks. Graph Neural Networks(GNNs) have shown their superior ability in learning representations for graph structured data, which leads to performance improvements in many graph related tasks such as link prediction, node classification and graph classification. Most of the existing graph neural networks models are designed for static graphs while many real-world graphs are inherently dynamic with new nodes and edges constantly emerging. Existing graph neural network models cannot utilize the dynamic information, which has been shown to enhance the performance of many graph analytic tasks such as community detection. Hence, in this paper, we propose DyGNN, a Dynamic Graph Neural Network model, which can model the dynamic information as the graph evolving. In particular, the proposed framework keeps updating node information by capturing the sequential information of edges (interactions), the time intervals between edges and information propagation coherently. Experimental results on various dynamic graphs demonstrate the effectiveness of the proposed framework.

References

[1]

Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. 2016. Interaction networks for learning about objects, relations and physics. In NIPS. 4502--4510.

Digital Library

[2]

Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. 2018. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261 (2018).

[3]

Inci M Baytas, Cao Xiao, Xi Zhang, Fei Wang, Anil K Jain, and Jiayu Zhou. 2017. Patient subtyping via time-aware LSTM networks. In KDD. ACM, 65--74.

[4]

Rianne van den Berg, Thomas N Kipf, and Max Welling. 2017. Graph convolutional matrix completion. arXiv preprint arXiv:1706.02263 (2017).

[5]

Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2013. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203 (2013).

[6]

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. 2012. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems 27, 5 (2012), 387--408.

Digital Library

[7]

Michael B Chang, Tomer Ullman, Antonio Torralba, and Joshua B Tenenbaum. 2016. A compositional object-based approach to learning physical dynamics. arXiv preprint arXiv:1612.00341 (2016).

[8]

Shiyu Chang, Yang Zhang, Jiliang Tang, Dawei Yin, Yi Chang, Mark A HasegawaJohnson, and Thomas S Huang. 2017. Streaming recommender systems. In WWW. WWW, 381--389.

[9]

Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS. 3844--3852.

[10]

Tyler Derr, Yao Ma, and Jiliang Tang. 2018. Signed graph convolutional networks. In 2018 IEEE International Conference on Data Mining (ICDM). IEEE, 929--934.

[11]

Daniel M Dunlavy, Tamara G Kolda, and Evrim Acar. 2011. Temporal link prediction using matrix and tensor factorizations. TKDD 5, 2 (2011), 10.

Digital Library

[12]

Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. 2019. Graph neural networks for social recommendation. In The World Wide Web Conference. 417--426.

Digital Library

[13]

Hongyang Gao and Shuiwang Ji. 2019. Graph u-nets. arXiv preprint arXiv:1905.05178 (2019).

[14]

Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural message passing for quantum chemistry. arXiv preprint arXiv:1704.01212 (2017).

[15]

Marco Gori, Gabriele Monfardini, and Franco Scarselli. [n. d.]. A new model for learning in graph domains. In Neural Networks, 2005. IJCNN'05. Proceedings. 2005 IEEE International Joint Conference on, Vol. 2. IEEE, 729--734.

[16]

Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. 2018. DynGEM: Deep Embedding Method for Dynamic Graphs. arXiv preprint arXiv:1805.11273 (2018).

[17]

Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In KDD. ACM, 855--864.

[18]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NIPS. 1024--1034.

[19]

Frank Harary and Gopal Gupta. 1997. Dynamic graph models. Mathematical and Computer Modelling 25, 7 (1997), 79--87.

Digital Library

[20]

Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation 9, 8 (1997), 1735--1780.

Digital Library

[21]

Petter Holme and Jari Saramäki. 2012. Temporal networks. Physics reports 519, 3 (2012), 97--125.

[22]

Ling Jian, Jundong Li, and Huan Liu. 2018. Toward online node classification on streaming networks. Data Mining and Knowledge Discovery 32, 1 (2018), 231--257.

Digital Library

[23]

Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).

[24]

Jérôme Kunegis. 2013. Konect: the koblenz network collection. In WWW. ACM, 1343--1350.

[25]

Jundong Li, Kewei Cheng, Liang Wu, and Huan Liu. 2018. Streaming link prediction on dynamic attributed networks. In WSDM. ACM, 369--377.

[26]

Jundong Li, Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang, and Huan Liu. 2017. Attributed network embedding for learning in a dynamic environment. In CIKM. ACM, 387--396.

[27]

Yu-Ru Lin, Yun Chi, Shenghuo Zhu, Hari Sundaram, and Belle L Tseng. 2008. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. In WWW. ACM, 685--694.

[28]

Jianxin Ma, Peng Cui, and Wenwu Zhu. 2018. DepthLGP: Learning Embeddings of Out-of-Sample Nodes in Dynamic Networks. AAAI.

[29]

Yao Ma, Suhang Wang, Charu C Aggarwal, and Jiliang Tang. 2019. Graph convolutional networks with eigen pooling. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 723--731.

Digital Library

[30]

Yao Ma, Suhang Wang, Chara C Aggarwal, Dawei Yin, and Jiliang Tang. 2019. Multi-dimensional graph convolutional networks. In Proceedings of the 2019 SIAM International Conference on Data Mining. SIAM, 657--665.

[31]

Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001. Birds of a feather: Homophily in social networks. Annual review of sociology 27, 1 (2001), 415--444.

[32]

Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, and Charles E Leisersen. 2019. Evolvegcn: Evolving graph convolutional networks for dynamic graphs. arXiv preprint arXiv:1902.10191 (2019).

[33]

Alvaro Sanchez-Gonzalez, Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia. 2018. Graph networks as learnable physics engines for inference and control. arXiv preprint arXiv:1806.01242 (2018).

[34]

Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. 2018. Dynamic graph representation learning via self-attention networks. arXiv preprint arXiv:1812.09430 (2018).

[35]

Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2009. The graph neural network model. IEEE Transactions on Neural Networks 20, 1 (2009), 61--80.

Digital Library

[36]

J. Tang, H. Gao, and H. Liu. 2012. mTrust: Discerning multi-faceted trust in a connected world. In WSDM. ACM, 93--102.

[37]

Rakshit Trivedi, Hanjun Dai, Yichen Wang, and Le Song. 2017. Know-evolve: Deep temporal reasoning for dynamic knowledge graphs. arXiv preprint arXiv:1705.05742 (2017).

[38]

Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2017. Graph Attention Networks. arXiv preprint arXiv:1710.10903 (2017).

[39]

Ellen M Voorhees et al. 1999. The TREC-8 Question Answering Track Report. In Trec, Vol. 99. 77--82.

[40]

Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019. Neural graph collaborative filtering. In Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval. 165--174.

Digital Library

[41]

Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. 2019. Heterogeneous graph attention network. In The World Wide Web Conference. 2022--2032.

Digital Library

[42]

Xiaoyang Wang, Yao Ma, Yiqi Wang, Wei Jin, Xin Wang, Jiliang Tang, Caiyan Jia, and Jian Yu. 2020. Traffic Flow Prediction via Spatial Temporal Graph Neural Network. In Proceedings of The Web Conference 2020. 1082--1092.

Digital Library

[43]

Rongjing Xiang, Jennifer Neville, and Monica Rogati. 2010. Modeling relationship strength in online social networks. In WWW. ACM, 981--990.

[44]

Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. 2019. HyperGCN: A New Method For Training Graph Convolutional Networks on Hypergraphs. In Advances in Neural Information Processing Systems. 1509--1520.

[45]

Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. 2018. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. arXiv preprint arXiv:1806.01973 (2018).

[46]

Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. 2018. Hierarchical graph representation learning with differentiable pooling. In Advances in neural information processing systems. 4800--4810.

[47]

Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2017. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint arXiv:1709.04875 (2017).

[48]

Le-kui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang. 2018. Dynamic Network Embedding by Modeling Triadic Closure Process.

[49]

Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. 2003. Semi-supervised learning using gaussian fields and harmonic functions. In ICML. 912--919.

Cited By

Feng BCheng FLiu YChang XWang XJin D(2024)Community Detection on Social Networks With Sentimental InteractionInternational Journal on Semantic Web & Information Systems10.4018/IJSWIS.34123220:1(1-23)Online publication date: 9-Apr-2024
https://dl.acm.org/doi/10.4018/IJSWIS.341232
Guliyev RHaldar AFerhatosmanoglu H(2024)D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural NetworksProceedings of the VLDB Endowment10.14778/3681954.368196117:11(2764-2777)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681961
Chen CGao DZhang YWang QFu ZZhang XZhu JGu YYu G(2024)NeutronStream: A Dynamic GNN Training Framework with Sliding Window for Graph StreamsProceedings of the VLDB Endowment10.14778/3632093.363210817:3(455-468)Online publication date: 20-Jan-2024
https://doi.org/10.14778/3632093.3632108
Show More Cited By

Index Terms

Streaming Graph Neural Networks
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
        Dimensionality reduction and manifold learning
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Social networks

Recommendations

Instant Graph Neural Networks for Dynamic Graphs
KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Graph Neural Networks (GNNs) have been widely used for modeling graph-structured data. Recent breakthroughs have been made in improving the scalability of GNNs to work on graphs with millions of nodes. However, how to instantly represent continuous ...
ROLAND: Graph Learning Framework for Dynamic Graphs
KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Graph Neural Networks (GNNs) have been successfully applied to many real-world static graphs. However, the success of static graphs has not fully translated to dynamic graphs due to the limitations in model design, evaluation settings, and training ...
Graph Sequential Neural ODE Process for Link Prediction on Dynamic and Sparse Graphs
WSDM '23: Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining

Link prediction on dynamic graphs is an important task in graph mining. Existing approaches based on dynamic graph neural networks (DGNNs) typically require a significant amount of historical data (interactions over time), which is not always available ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGIR '20: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval

July 2020

2548 pages

ISBN:9781450380164

DOI:10.1145/3397271

General Chairs:
Jimmy Huang
York University, Canada
,
Yi Chang
Jilin University, China
,
Xueqi Cheng
Chinese Academy of Sciences, China
,
Program Chairs:
Jaap Kamps
University of Amsterdam, Netherlands
,
Vanessa Murdock
Amazon, U.S.A.
,
Ji-Rong Wen
Renmin University of China, China
,
Yiqun Liu
Tsinghua University, China

Copyright © 2020 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

SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SIGIR '20

Sponsor:

SIGIR

SIGIR '20: The 43rd International ACM SIGIR conference on research and development in Information Retrieval

July 25 - 30, 2020

Virtual Event, China

Acceptance Rates

Overall Acceptance Rate 792 of 3,983 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

133
Total Citations
View Citations
4,944
Total Downloads

Downloads (Last 12 months)930
Downloads (Last 6 weeks)93

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feng BCheng FLiu YChang XWang XJin D(2024)Community Detection on Social Networks With Sentimental InteractionInternational Journal on Semantic Web & Information Systems10.4018/IJSWIS.34123220:1(1-23)Online publication date: 9-Apr-2024
https://dl.acm.org/doi/10.4018/IJSWIS.341232
Guliyev RHaldar AFerhatosmanoglu H(2024)D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural NetworksProceedings of the VLDB Endowment10.14778/3681954.368196117:11(2764-2777)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681961
Chen CGao DZhang YWang QFu ZZhang XZhu JGu YYu G(2024)NeutronStream: A Dynamic GNN Training Framework with Sliding Window for Graph StreamsProceedings of the VLDB Endowment10.14778/3632093.363210817:3(455-468)Online publication date: 20-Jan-2024
https://doi.org/10.14778/3632093.3632108
Ji SLiu MSun LLiu CZhu TBaeza-Yates RBonchi F(2024)MemMap: An Adaptive and Latent Memory Structure for Dynamic Graph LearningProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672060(1257-1268)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3672060
Zhong YVu HYang TAdhikari BBaeza-Yates RBonchi F(2024)Efficient and Effective Implicit Dynamic Graph Neural NetworkProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672026(4595-4606)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3672026
Du HShi LChen XZhao YZhang HYang CZhuang FKou GBaeza-Yates RBonchi F(2024)Representation Learning of Temporal Graphs with Structural RolesProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671854(654-665)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671854
Zhang XSong DChen YTao DBaeza-Yates RBonchi F(2024)Topology-aware Embedding Memory for Continual Learning on Expanding NetworksProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671732(4326-4337)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671732
Zhang PYan YZhang XKang LLi CHuang FWang SKim SHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)GPT4Rec: Graph Prompt Tuning for Streaming RecommendationProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657720(1774-1784)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657720
Xia JLi DGu HLu TZhang PShang LGu NAngélica LLattanzi SMuñoz Medina AAkoglu LGionis AVassilvitskii S(2024)Neural Kalman Filtering for Robust Temporal RecommendationProceedings of the 17th ACM International Conference on Web Search and Data Mining10.1145/3616855.3635837(836-845)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1145/3616855.3635837
Xiao CJi WZhang YLv S(2024)PIDKG: Propagating Interaction Influence on the Dynamic Knowledge Graph for RecommendationACM Transactions on the Web10.1145/359331418:2(1-26)Online publication date: 8-Jan-2024
https://dl.acm.org/doi/10.1145/3593314
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Publication

Media

Figures

Other

Tables

View Table of Contents