Scalable dynamic graph representation learning with neighborhood memory

doi:10.11772/j.issn.1001-9081.2025070907

Abstract

Abstract:

Dynamic graph learning addresses graph data in which nodes and edges evolve over time. Traditional Graph Neural Networks （GNNs） typically rely on information from nodes and their neighbors， but in dynamic graph scenarios， models must capture real-time dynamic evolution information of nodes and edges while balancing global temporal dependencies and local structural details when facing large-scale data. To address these challenges， MTGN （Memory-based Temporal Graph Network）， a scalable dynamic graph representation learning model with neighborhood memory was proposed to realize efficient modeling via subgraph sampling and neighborhood memory mechanism. First， a parallel temporal sampler was used for efficient subgraph sampling. Second， a cache-based node neighborhood memory mechanism was introduced to maintain node historical status dynamically. Third， temporal relationships among dynamic neighbors were modeled through an attention mechanism adaptively， thereby generating more stable and robust dynamic graph representations. Finally， experiments were conducted on four real-world datasets. The results demonstrate that MTGN has excellent prediction accuracy in the link prediction tasks with the prediction accuracies of 99.38% and 74.46% on the MOOC and LASTFM datasets， respectively. In the dynamic node classification tasks， MTGN achieves prediction accuracies of 90.50% and 79.08% on the Wikipedia and Reddit datasets， respectively， showing significant performance improvements compared to the baseline methods. Additionally， MTGN has outstanding training efficiency， reducing training time by at least 86.9% and 93.6% on the Wikipedia and Reddit datasets， respectively， compared to the baseline methods， validating its scalability for large-scale dynamic graph tasks.

Key words: Graph Neural Network (GNN), dynamic representation, neighborhood aggregation, node classification, link prediction

摘要：

动态图学习旨在处理节点和边在时间维度上变化的图数据。传统的图神经网络（GNN）通常依赖节点及其邻居的信息进行学习，而在动态图场景下的模型不仅需要实时捕获节点和边的动态演化特征，还需在面对大规模数据时，兼顾全局时序依赖与局部结构细节。为了解决上述问题，提出基于邻域记忆的可扩展动态图表示学习模型MTGN （Memory-based Temporal Graph Network），以通过子图采样与邻域记忆机制实现高效建模。首先，采用并行时间采样器进行高效的子图采样；其次，引入基于缓存的节点邻域记忆机制，以动态维护节点的历史状态；然后，在信息聚合阶段，通过注意力机制自适应地建模动态邻居之间的时序关系，从而生成更稳定且鲁棒的动态图表示；最后，在4个真实数据集上进行实验。结果表明：在链接预测任务中， MTGN在4个数据集上均表现出优秀的预测精度，在MOOC和LASTFM数据集上的预测精度分别为99.38%和74.46%；而在动态节点分类任务中， MTGN在Wikipedia和Reddit数据集上的预测精度分别为90.50%和79.08%，相较于基线方法具有显著的性能提升。此外， MTGN在训练效率上表现优异，在Wikipedia和Reddit数据集上的训练时间相较于基线方法分别至少减少86.9%和93.6%，验证了MTGN在大规模动态图任务中的可扩展性。

关键词: 图神经网络, 动态表征, 邻域聚合, 节点分类, 链接预测

CLC Number:

TP391

Yue ZHANG, Ying WANG. Scalable dynamic graph representation learning with neighborhood memory[J]. Journal of Computer Applications, 2026, 46(7): 2104-2110.

张玥, 王英. 基于邻域记忆的可扩展动态图表示学习[J]. 《计算机应用》唯一官方网站, 2026, 46(7): 2104-2110.

Figures/Tables 6

References 38

[1]	Wang J， Huang P， Zhao H， et al. Billion-scale commodity embedding for e-commerce recommendation in Alibaba ［C］// KDD 2018. New York： ACM， 2018： 839-848.
[2]	Liben-Nowell D， Kleinberg J. The link prediction problem for social networks ［C］// CIKM 2003. New York： ACM， 2003： 556-559.
[3]	Li H， Yang S， Song Y， et al. Spatial dynamic graph convolutional network for traffic flow forecasting ［J］. Applied Intelligence， 2023， 53（12）： 14986-14998.
[4]	Wu Z， Pan S， Chen F， et al. A comprehensive survey on graph neural networks ［J］. IEEE Transactions on Neural Networks and Learning Systems， 2021， 32（1）： 4-24.
[5]	Barros C D T， Mendonça M R F， Vieira A B， et al. A survey on embedding dynamic graphs ［J］. ACM Computing Surveys， 2023， 55（1）： No.10.
[6]	Abadal S， Jain A， Guirado R， et al. Computing graph neural networks： a survey from algorithms to accelerators ［J］. ACM Computing Surveys， 2022， 54（9）： No.191.
[7]	Jiang W， Luo J. Graph neural network for traffic forecasting： a survey ［J］. Expert Systems with Applications， 2022， 207： No.117921.
[8]	Batarfi O， El Shawi R， Fayoumi A G， et al. Large scale graph processing systems： survey and an experimental evaluation ［J］. Cluster Computing， 2015， 18： 1189-1213.
[9]	Trivedi R， Farajtabar M， Biswal P， et al. DyRep： learning representations over dynamic graphs ［EB/OL］. （2024-04-03）［2025-05-20］. .
[10]	Kumar S， Zhang X， Leskovec J. Predicting dynamic embedding trajectory in temporal interaction networks ［C］// KDD 2019. New York： ACM， 2019： 1269-1278.
[11]	Rossi E， Chamberlain B， Frasca F， et al. Temporal graph networks for deep learning on dynamic graphs ［PP/OL］. V3. arXiv （2020-10-09）［2025-02-10］. .
[12]	Sankar A， Wu Y， Gou L， et al. DySAT： deep neural representation learning on dynamic graphs via self-attention networks ［C］// WSDM 2020. New York： ACM， 2020： 519-527.
[13]	Xu D， Ruan C， Korpeoglu E， et al. Inductive representation learning on temporal graphs ［PP/OL］. arXiv （2020-02-19）［2025-04-05］. .
[14]	Wang X， Lyu D， Li M， et al. APAN： asynchronous propagation attention network for real-time temporal graph embedding ［C］// SIGMOD 2021. New York： ACM， 2021： 2628-2638.
[15]	Zheng Y， Wei Z， Liu J. Decoupled graph neural networks for large dynamic graphs ［J］. Proceedings of the VLDB Endowment， 2023， 16（9）： 2239-2247.
[16]	Liu B， Huang X. Link-aware link prediction over temporal graph by pattern recognition ［C］// IEA/AIE 2023. Cham： Springer， 2023： 325-337.
[17]	Huang S， Poursafaei F， Rabbany R， et al. UTG： towards a unified view of snapshot and event based models for temporal graphs ［C］// LoG 2025. New York： JMLR.org， 2025： No.28.
[18]	Wu F， Zhang T， de Souza A H， et al. Simplifying graph convolutional networks ［C］// ICML 2019. New York： JMLR.org， 2019： 6861-6871.
[19]	Frasca F， Rossi E， Eynard D， et al. SIGN： scalable inception graph neural networks ［PP/OL］. V3. arXiv （2020-11-03）［2025-04-20］. .
[20]	Zheng D， Ma C， Wang M， et al. DistDGL： distributed graph neural network training for billion-scale graphs ［C］// IA3 2020. Piscataway： IEEE， 2020： 36-44.
[21]	Wang M， Zheng D， Ye Z， et al. Deep graph library： a graph-centric， highly-performant package for graph neural networks ［PP/OL］. V2. arXiv （2020-08-25）［2025-03-02］. .
[22]	Yan M， Deng L， Hu X， et al. HyGCN： a GCN accelerator with hybrid architecture ［C］// HPCA 2020. Piscataway： IEEE， 2020： 15-29.
[23]	Zhou J， Cui G， Hu S， et al. Graph neural networks： a review of methods and applications ［J］. AI Open， 2020， 1： 57-81.
[24]	Hamilton W L， Ying R， Leskovec J. Inductive representation learning on large graphs ［C］// NeurIPS 2017. Red Hook： Curran Associates Inc.， 2017： 1025-1035.
[25]	Chiang W L， Liu X， Si S， et al. Cluster-GCN： an efficient algorithm for training deep and large graph convolutional networks ［C］// KDD 2019. New York： ACM， 2019： 257-266.
[26]	Zeng H， Zhou H， Srivastava A， et al. GraphSAINT： graph sampling based inductive learning method ［PP/OL］. V4. arXiv （2020-02-16）［2025-05-20］. .
[27]	Li M， Chen S， Chen X， et al. Actional-structural graph convolutional networks for skeleton-based action recognition ［C］// CVPR 2019. Piscataway： IEEE， 2019： 3590-3598.
[28]	Wei Z， He X， Xiao X， et al. TopPPR： top-k personalized PageRank queries with precision guarantees on large graphs ［C］// SIGMOD 2018. New York： ACM， 2018： 441-456.
[29]	Chen J， Ma T， Xiao C. FastGCN： fast learning with graph convolutional networks via importance sampling ［PP/OL］. arXiv （2018-01-30）［2025-02-25］. .
[30]	Zeng H， Zhang M， Xia Y， et al. Decoupling the depth and scope of graph neural networks ［C］// NeurIPS 2021. Red Hook： Curran Associates Inc.， 2021： 19665-19679.
[31]	Pareja A， Domeniconi G， Chen J， et al. EvolveGCN： evolving graph convolutional networks for dynamic graphs ［C］// AAAI 2020. Palo Alto： AAAI Press， 2020： 5363-5370.
[32]	Nguyen G H， Lee J B， Rossi R A， et al. Continuous-time dynamic network embeddings ［C］// TheWebConf 2018. Republic and Canton of Geneva： International World Wide Web Conferences Steering Committee， 2018： 969-976.
[33]	Wang Y， Chang Y Y， Liu Y， et al. Inductive representation learning in temporal networks via causal anonymous walks ［PP/OL］. V5. arXiv （2022-10-31）［2025-02-12］. .
[34]	Gilmer J， Schoenholz S S， Riley P F， et al. Neural message passing for quantum chemistry ［C］// ICML 2017. New York： JMLR.org， 2017： 1263-1272.
[35]	Zhang J， Xue R， Fan W， et al. Linear-time graph neural networks for scalable recommendations ［C］// TheWebConf 2024. New York： ACM， 2024： 3533-3544.
[36]	Luo Y， Li P. Neighborhood-aware scalable temporal network representation learning ［C］// LoG 2022. New York： JMLR.org， 2022： No.1.
[37]	Guan M， Iyer A P， Kim T. DynaGraph： dynamic graph neural networks at scale ［C］// GRADES-NDA 2022. New York： ACM， 2022： No.6.
[38]	Wang Y， Mendis C. TGLite： a lightweight programming framework for continuous-time temporal graph neural networks ［C］// ASPLOS 2024. New York： ACM， 2024： 1183-1199.

数据集	节点数/10³	边数/10³	标签数	类别数	边特征维度	时间跨度
Wikipedia	9	157	217	2	172	30 d
Reddit	11	672	366	2	172	30 d
MOOC	7	412	—	—	128^*	30 d
LastFM	2	1 300	—	—	128^*	4 a

数据集	节点数/10³	边数/10³	标签数	类别数	边特征维度	时间跨度
Wikipedia	9	157	217	2	172	30 d
Reddit	11	672	366	2	172	30 d
MOOC	7	412	—	—	128^*	30 d
LastFM	2	1 300	—	—	128^*	4 a

方法	Wikipedia	Reddit
TGAT	95.09	97.82
JODIE	94.35	96.56
APAN	98.12	99.22
TGN	98.34	98.47
D-DGNN	98.54	98.81
MTGN-TGAT	98.16	99.54
MTGN- DySAT	96.77	98.53
MTGN-JODIE	98.91	99.49
MTGN-APAN	98.78	99.68
MTGN-TGN	99.14	99.79

方法	Wikipedia	Reddit
TGAT	95.09	97.82
JODIE	94.35	96.56
APAN	98.12	99.22
TGN	98.34	98.47
D-DGNN	98.54	98.81
MTGN-TGAT	98.16	99.54
MTGN- DySAT	96.77	98.53
MTGN-JODIE	98.91	99.49
MTGN-APAN	98.78	99.68
MTGN-TGN	99.14	99.79

方法	LASTFM	MOOC
MTGN-TGAT	73.74	98.63
MTGN-JODIE	74.46	99.20
MTGN-APAN	68.29	99.35
MTGN-TGN	62.56	99.38