FODGE - Fast Online Dynamic Graph Embedding
Pages 258 - 262
Abstract
Graph embedding algorithms (GEA) project each vertex in a graph to a real-valued vector. Dynamic GEA (DGEA) are used to project dynamic graphs, where vertices and edges can appear and disappear. Such graphs are mostly divided into snapshots. Current DGEAs are often offline, and computationally expensive, and most do not ensure a slow change in vertices projection.
We propose here FODGE, a novel DGEA algorithm to gradually shift the projection of vertices whose first and second neighbors changed. FODGE optimizes CPU and memory efficacy by initially projecting the graph's densest K-core using any existing global optimization and then projecting the periphery of the graph using a local approximation. FODGE then smoothly updates the projection of all vertices, through an iterative local update rule. As such it can be applied to extremely large dynamic graphs over long periods.
We show that FODGE is faster than current algorithms, more accurate in an auxiliary task of link prediction. and it ensures a limited difference in vertex positions between consecutive time points. FODGE is highly modular and can be combined with any static projection, including graph convolutional networks, and has a few hyperparameters to tune. The code is available at https://github.com/unknownuser13570/FODGE in GIT.
References
[1]
H. Cai, V. W. Zheng, and K. C.-C. Chang, "A comprehensive survey of graph embedding: Problems, techniques, and applications," IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 9, pp. 1616--1637, 2018.
[2]
P. Goyal and E. Ferrara, "Graph embedding techniques, applications, and performance: A survey," Knowledge-Based Systems, pp. 78--94, 2018.
[3]
P. Cui, X. Wang, J. Pei, and W. Zhu, "A survey on network embedding," IEEE Transactions on Knowledge and Data Engineering, vol. 31, no. 5, pp. 833--852, 2018.
[4]
Y. Zuo, G. Liu, H. Lin, J. Guo, X. Hu, and J. Wu, "Embedding temporal network via neighborhood formation," The 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 19--23, 2018, London, United Kingdom, 2018.
[5]
A. Pareja, G. Domeniconi, J. Chen, T. Ma, T. Suzumura, H. Kanezashi, T. Kaler, T. B. Schardl, and C. E. Leiserson, "Evolvegcn: Evolving graph convolutional networks for dynamic graphs," 2019.
[6]
J. Liu, C. Xu, C. Yin, W. Wu, and Y. Song, "K-core based temporal graph convolutional network for dynamic graphs," IEEE Transactions on Knowledge and Data Engineering, p. 1--1, 2020.
[7]
D. Xu, C. Ruan, E. Korpeoglu, S. Kumar, and K. Achan, "Inductive representation learning on temporal graphs," ICLR 2020, 2020.
[8]
L. Munasinghe and R. Ichise, "Activeem: A node embedding method for dynamic social networks," 10 2020.
[9]
E. Rossi, B. Chamberlain, F. Frasca, D. Eynard, F. Monti, and M. Bronstein, "Temporal graph networks for deep learning on dynamic graphs," 2020.
[10]
Z. Zhang, J. Bu, M. Ester, J. Zhang, C. Yao, Z. Li, and C. Wang, "Learning temporal interaction graph embedding via coupled memory networks," 2020.
[11]
M. Ou, P. Cui, J. Pei, Z. Zhang, and W. Zhu, "Asymmetric transitivity preserving graph embedding," Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, vol. ACM, p. 1105--1114, 2016.
[12]
S. T. Roweis and L. K. Saul, "Nonlinear dimensionality reduction by locally linear embedding," Science, pp. 2323--2326, 2000.
[13]
A. Grover and J. Leskovec, "node2vec: Scalable feature learning for networks," 2016.
[14]
U. Singer, I. Guy, and K. Radinsky, "Node embedding over temporal graphs," Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), 2019.
[15]
M. Haddad, C. Bothorel, P. Lenca, and D. Bedart, "Temporalnode2vec: Temporal node embedding in temporal networks," 2019.
[16]
D. M. Dunlavy, T. G. Kolda, and E. Acar, "Temporal link prediction using matrix and tensor factorizations," ACM Transactions on Knowledge Discovery from Data, vol. 5, p. 1--27, Feb 2011.
[17]
P. Goyal, N. Mehrabi, and E. Ferrara, "Dynamicgem: A library for dynamic graph embedding methods," Journal of Machine Learning Research, vol. 1, pp. 1--48, 2018.
[18]
Y. Lu, X. Wang, C. Shi, P. S. Yu, and Y. Ye, "Temporal network embedding with micro- and macro-dynamics," 2019.
[19]
M. Liu, Z. Quan, and Y. Liu, "Network representation learning algorithm based on neighborhood influence sequence," 2020.
[20]
A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A. J. Smola, "Distributed large-scale natural graph factorization," Proceedings of the 22nd International Conference on World Wide Web, ACM, pp. 37--48, 2013.
[21]
T. N. Kipf and M. Welling, "Variational graph auto-encoders," NIPS Workshop on Bayesian Deep Learning, 2016.
[22]
L. Hamers et al., "Similarity measures in scientometric research: The jaccard index versus salton's cosine formula.," Information Processing and Management, vol. 25, no. 3, pp. 315--18, 1989.
[23]
P. H. Schönemann, "A generalized solution of the orthogonal procrustes problem," Psychometrika, vol. 31, no. 1, pp. 1--10, 1966.
Index Terms
- FODGE - Fast Online Dynamic Graph Embedding
Index terms have been assigned to the content through auto-classification.
Recommendations
Dynamic Coloring on Restricted Graph Classes
Algorithms and ComplexityAbstractA proper k-coloring of a graph is an assignment of colors from the set to the vertices of the graph such that no two adjacent vertices receive the same color. Given a graph , the Dynamic Coloring problem asks to find a proper k-coloring of G such ...
Graph structural properties of non-Yutsis graphs allowing fast recognition
Yutsis graphs are connected simple graphs which can be partitioned into two vertex-induced trees. Cubic Yutsis graphs were introduced by Jaeger as cubic dual Hamiltonian graphs, and these are our main focus. Cubic Yutsis graphs also appear in the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 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].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 15 March 2024
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
ASONAM '23
Sponsor:
ASONAM '23: International Conference on Advances in Social Networks Analysis and Mining
November 6 - 9, 2023
Kusadasi, Turkiye
Acceptance Rates
ASONAM '23 Paper Acceptance Rate 53 of 145 submissions, 37%;
Overall Acceptance Rate 116 of 549 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 98Total Downloads
- Downloads (Last 12 months)98
- Downloads (Last 6 weeks)24
Reflects downloads up to 13 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in