面向有向图的特征提取与表征学习研究

doi:10.3778/j.issn.1002-8331.2310-0080

摘要/Abstract

摘要： 图数据是一种用于描述不同实体之间关联关系的重要数据形式。有向图作为一种特殊形式，不仅能描述实体关联，还能明确关系的方向，提供了更精细和详实的描述。因此，有向图的特征提取和表征学习对于深入理解复杂系统具有至关重要的意义。然而，现有方法在有效提取有向图的方向信息方面仍然存在挑战，主要依赖于节点的局部信息进行特征提取，难以充分利用有向边蕴含的方向信息。为解决这一问题，提出了一种名为变分有向图自编码器（variational directed graph autoencoder，VDGAE）的无监督表示学习方法。VDGAE通过关联矩阵来建模节点与边之间的关联关系，通过计算节点与边之间的亲和力，来重构输入有向图，从而实现无监督表征学习。基于此，VDGAE能够同时为输入有向图学习节点与边的表征，充分捕获有向图的结构信息和方向信息并嵌入至节点与边的表征向量中，使得有向图能够被更准确地表征。实验结果表明，相较于11个基准方法，VDGAE在5个数据集上节点分类任务均优于基准方法，提升了11.96%的预测精度，充分验证了其有效性。

关键词: 有向图, 表征学习, 关联矩阵, 图神经网络, 变分自编码器

Abstract: Directed graphs, as a specific form of graph, not only describe entity relationships but also explicitly indicate the direction of these relationships, providing a more detailed and comprehensive description. Therefore, feature extraction and representation learning for directed graphs are crucial for understanding complex networks and have significant implications for practical applications. Despite the excellent performance of graph neural network (GNN) in extracting structural information from graphs, there are still challenges in effectively capturing directional information in directed graphs due to the limitations of their feature extraction patterns. This paper proposes an unsupervised representation learning method named variational directed graph autoencoder (VDGAE), based on the incidence matrix, which can simultaneously learn representations for nodes and edges to represent directed graphs effectively. Experimental results on five datasets demonstrate that VDGAE outperforms eleven baseline methods, achieving a 11.96% improvement in node classification, validating its effectiveness.

Key words: directed graph, representation learning, incidence matrix, graph neural network (GNN), variational autoencoders (VAE)

谭郁松, 张钰森, 蹇松雷. 面向有向图的特征提取与表征学习研究[J]. 计算机工程与应用, 2025, 61(3): 234-241.

TAN Yusong, ZHANG Yusen, JIAN Songlei. Research on Feature Extraction and Representation Learning for Directed Graphs[J]. Computer Engineering and Applications, 2025, 61(3): 234-241.

参考文献

[1] JU W, FANG Z, GU Y, et al. A comprehensive survey on deep graph representation learning[EB/OL]. (2023-04-19) [2023-08-26]. https://arxiv.org/abs/2304.05055.
[2] 崔文岳, 谷远利, 赵胜利, 等. 基于有向图卷积与门控循环单元的短时交通流预测方法[J]. 交通信息与安全, 2023, 41(2): 121-128.
CUI W Y, GU Y L, ZHAO S L, et al. A method of predicting short-term traffic flows based on a DGC-GRU model[J]. Journal of Transport Information and Safety, 2023, 41(2): 121-128.
[3] GEISLER S, LI Y, MANKOWITZ D, et al. Transformers meet directed graphs[C]//Proceedings of the International Conference on Machine Learning, 2023.
[4] 高春晓, 卢士帅, 刘琼昕, 等. 一种融合关系抽取的推荐系统[J]. 北京理工大学学报, 2022, 42(11): 1191-1199.
GAO C X, LU S S, LIU Q X, et al. A recommendation system with fusion relation extraction[J]. Transactions of Beijing Institute of Technology, 2022, 42(11): 1191-1199.
[5] 檀彦超, 郑小林, 魏翔宇, 等. 基于度量学习的多空间推荐系统[J]. 计算机学报, 2022, 45(1): 1-16.
TAN Y C, ZHENG X L, WEI X Y, et al. Multi-space recommender systems via metric learning[J]. Chinese Journal of Computers, 2022, 45(1): 1-16.
[6] 向露, 朱军楠, 周玉, 等. 基于多粒度对抗训练的鲁棒跨语言对话系统[J]. 自动化学报, 2021, 47(8): 1855-1866.
XIANG L, ZHU J N, ZHOU Y, et al. Robust cross-lingual dialogue system based on multi-granularity adversarial training[J]. ACTA Automatic Sinica, 2021, 47(8): 1855-1866.
[7] 冯雅茹, 黄贤英, 李伟. 增强深层话题语义的对话引导模型[J]. 计算机工程与应用, 2023, 59(7): 171-179.
FENG Y R, HUANG X Y, LI W. Target-guided conversation model combining enhanced deep topic semantics[J]. Computer Engineering and Applications, 2023, 59(7): 171-179.
[8] 雷景生, 李冉, 杨胜英, 等. 融合社交信息的多图神经网络会话推荐方法[J]. 计算机工程与应用, 2023, 59(15): 264-273.
LEI J S, LI R, YANG S Y, et al. Session-based recommendation based on multi-graph neural network incorporating social information[J]. Computer Engineering and Applications, 2023, 59(15): 264-273.
[9] 吴博, 梁循, 张树森, 等. 图神经网络前沿进展与应用[J]. 计算机学报, 2022, 45(1): 35-68.
WU B, LIANG X, ZHANG S S, et al. Advances and applications in graph neural network[J]. Chinese Journal of Computers, 2022, 45(1): 35-68.
[10] NING X, ZHENG Y, ZHOU Z, et al. A generic graph-based neural architecture encoding scheme with multifaceted information[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 45(7): 7955-7969.
[11] 张涛, 程毅飞, 孙欣煦. 基于因果推断的图注意力网络[J]. 计算机科学, 2023, 50(S1): 157-165.
ZHANG T, CHENG Y, SUN X. Graph attention networks based on causal inference[J]. Computer Science, 2023, 50(S1): 157-165.
[12] 朱志国, 李伟玥, 姜盼, 等. 图神经网络会话推荐系统综述[J]. 计算机工程与应用, 2023, 59(5): 55-69.
ZHU Z G, LI W Y, JIANG P, et al. Survey of graph neural networks in session recommender systems[J]. Computer Engineering and Applications, 2023, 59(5): 55-69.
[13] 高阳, 张宏莉. 基于随机游走的社区发现方法综述[J]. 通信学报, 2023, 44(6): 198-210.
GAO Y, ZHANG H L. Survey on community detection method based on random walk[J]. Journal on Communications, 2023, 44(6): 198-210.
[14] KOLLIAS G, KALANTZIS V, IDE T, et al. Directed graph autoencoders[C]//Proceedings of the AAAI Conference on Artificial Intelligence, California, USA, 2022: 7211-7219.
[15] KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[C]//Proceedings of the International Conference on Learning Representations, Toulon, France, 2017.
[16] DEFFERRARD M, BRESSON X, VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Proceeding of the Neural Information Processing Systems, Barcelona, Spain, 2016: 3837-3845.
[17] TONG Z, LIANG Y, SUN C, et al. Directed graph convolutional network[EB/OL]. (2020-04-29) [2023-08-26]. https://arxiv.org/abs/2004.13970.
[18] TONG Z, LIANG Y, SUN C, et al. Digraph inception convolutional networks[C]//Proceedings of the Neural Information Processing Systems, 2020.
[19] ZHANG X, HE Y, BRUGNONE N, et al. MagNet: a neural network for directed graphs[C]//Proceedings of the Neural Information Processing Systems, 2021: 27003-27015.
[20] ZHANG M, JIANG S, CUI Z, et al. D-VAE: a variational autoencoder for directed acyclic graphs[C]//Proceedings of the Neural Information Processing Systems, Vancouver, Canada, 2019: 1586-1598.
[21] THOST V, CHEN J. Directed acyclic graph neural networks[C]//Proceedings of the International Conference on Learning Representations, 2021.
[22] KINGMA D P, WELLING M. Auto-encoding variational bayes[C]//Proceedings of the International Conference on Learning Representations, Banff, Canada, 2014.
[23] XU K, HU W, LESKOVEC J, et al. How powerful are graph neural networks?[C]//Proceedings of the International Conference on Learning Representations, New Orleans, USA, 2019.
[24] VELICKOVIC P, CUCURULL G, CASANOVA A, et al. Graph attention networks[C]//Proceedings of the International Conference on Learning Representations, Vancouver, Canada, 2018.
[25] HAMILTON W L, YING Z, LESKOVEC J. Inductive representation learning on large graphs[C]//Proceedings of the Neural Information Processing Systems, Long Beach, CA, USA, 2017: 1024-1034.
[26] KLICPERA J, BOJCHEVSKI A, GUNNEMANN S. Predict then propagate: graph neural networks meet personalized pagerank[C]//Proceedings of the International Conference on Learning Representations, New Orleans, USA, 2019.
[27] LIN L, GAO J. A magnetic framelet-based convolutional neural network for directed graphs[C]//Proceedings of the 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Rhodes Island, Greece, 2023.