您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (7): 64-75.doi: 10.6040/j.issn.1671-9352.1.2023.102

• 综述 • 上一篇    下一篇

融合多重特征的噪声网络对齐方法

咸宁1,2(),范意兴1,2,廉涛3,郭嘉丰1,2,*()   

  1. 1. 中国科学院计算技术研究所网络与数据科学与技术重点实验室，北京 100190
    2. 中国科学院大学计算机科学与技术学院，北京 100190
    3. 太原理工大学计算机科学与技术学院(大数据学院)，山西 晋中 030600
  • 收稿日期:2023-11-24 出版日期:2024-07-20 发布日期:2024-07-15
  • 通讯作者: 郭嘉丰 E-mail:xianning21s@ict.ac.cn;guojiafeng@ict.ac.cn
  • 作者简介:咸宁(1999—)，男，硕士研究生，研究方向为网络对齐、大语言模型评估. E-mail：xianning21s@ict.ac.cn
  • 基金资助:
    国家自然科学基金资助项目(62372431);国家重点研发计划项目(2021QY1701);国家重点研发计划项目(2023YFA1011602);中国科学院青年创新促进会会员项目(2021100);中国科学院计算技术研究所创新项目(E261090);国防科技创新项目

Noise network alignment method integrating multiple features

Ning XIAN1,2(),Yixing FAN1,2,Tao LIAN3,Jiafeng GUO1,2,*()   

  1. 1. Key Laboratory of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
    2. School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100190, China
    3. College of Computer Science and Technology (College of Data Science), Taiyuan University of Technology, Jinzhong 030600, Shanxi, China
  • Received:2023-11-24 Online:2024-07-20 Published:2024-07-15
  • Contact: Jiafeng GUO E-mail:xianning21s@ict.ac.cn;guojiafeng@ict.ac.cn

RichHTML

1

PDF (PC)

91

摘要：

针对网络对齐任务中网络结构差异大和锚节点对噪声大的问题，提出一种基于多轮迭代的网络对齐方法。该方法在每轮迭代时使用多种启发式方法计算不同维度的节点特征，利用多重特征的组合来评估锚节点的可靠性，过滤其中潜在的噪声，增强每轮对齐过程的置信度; 使用图神经网络增强无属性节点之间的一致性，减轻网络结构差异带来的影响。实验结果表明, 该方法可以在高噪声的情况下具有高准确率，验证了其有效性。

关键词: 网络对齐, 图同构网络, 噪声过滤, 图元

Abstract:

A multi-round iterative network alignment method is proposed to address the challenges of large structural differences and high noise sensitivity in anchor nodes in network alignment tasks. The method calculates node features of different dimensions using various heuristic approaches at each iteration, utilizing the combination of multiple features to assess the reliability of anchor nodes, filter potential noise, and enhance the confidence of each alignment round. Additionally, a graph neural network is employed to improve the consistency between nodes without attributes, mitigating the impact of structural differences in networks. Experimental results demonstrate that this method achieves high accuracy under high noise conditions, verifying its effectiveness.

Key words: network alignment, graph isomorphism, noise filtering, graphlet

中图分类号: 

  • TP391

图1

图元度向量"

表1

数据集信息"

数据集 网络名 节点数 边数 节点属性数 所有的对齐节点对数
原始Arenas Email网络 Gs 1 135 5 451 0 1 135
合成Arenas Email网络 Gt 1 135 5 437 0
Facebook Gs 1 043 4 734 0 1 043
Twitter Gt 1 043 4 860 0
Douban Offline Gs 1 118 1 511 538 1 118
Douban Online Gt 3 906 8 164 538

表2

对齐结果"

数据集 指标 本文方法/% REGAL/% CENALP/%
Accuracy 94.45 0.09 77.48
Arenas Email Precision@5 98.06 0.44 87.49
Precision@10 98.06 0.88 92.85
Accuracy 96.36 34.13 91.66
Facebook-Twitter Precision@5 97.32 44.87 93.44
Precision@10 98.47 49.09 95.01
Accuracy 46.24 2.77 21.91
Douban Precision@5 63.24 8.50 34.26
Precision@10 72.27 11.09 40.52

图2

正例节点比例对对齐正确率的影响"

图3

迭代轮数对对齐正确率的影响"

图4

各对齐组件对对齐正确率的影响"

1 SHU Kai , WANG Suhang , TANG Jiliang , et al. User identity linkage across online social networks: a review[J]. ACM SIGKDD Explorations Newsletter, 2017, 18 (2): 5- 17.
doi: 10.1145/3068777.3068781
2 ZHONG Erheng, FAN Wei, WANG Junwei, et al. ComSoc: adaptive transfer of user behaviors over composite social network[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing: ACM, 2012: 696-704.
3 PEI Shihao, YU Lu, YU Guoxian, et al. Graph alignment with noisy supervision[C]//Proceedings of the ACM Web Conference 2022. Lyon: ACM, 2022: 1104-1114.
4 GUZZI PH , MILENKOVIĆ T . Survey of local and global biological network alignment: the need to reconcile the two sides of the same coin[J]. Briefings in Bioinformatics, 2018, 19, 472- 481.
5 CHEN Chen, TONG Hanghang, XIE Lei, et al. FASCINATE: Fast cross-layer dependency inference on multi-layered networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco: ACM, 2016: 765-774.
6 MAO Xin, WANG Wenting, WU Yuanbin, et al. From alignment to assignment: frustratingly simple unsupervised entity alignment[C]// Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. Punta Cana: Association for Computational Linguistics, 2021: 2843-2853.
7 TRUNG H T, VAN VINH T, TAM N T, et al. Adaptive network alignment with unsupervised and multi-order convolutional networks[C]//2020 IEEE 36th International Conference on Data Engineering (ICDE). Dallas: IEEE, 2020: 85-96.
8 PEI Shichao, YU Lu, YU Guoxian, et al. REA: robust cross-lingual entity alignment between knowledge graphs[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2020: 2175-2184.
9 EMMERT-STREIB F , DEHMER M , SHI Y . Fifty years of graph matching, network alignment and network comparison[J]. Information Sciences, 2016, 346 (C): 180- 197.
10 BURKARD R E , PITSOULIS L S . The quadratic assignment problem[J]. Parallel Optimization Colloquium, 2012, 25 (4): 143- 174.
11 MILENKOVIĆ T , NG W L , HAYES W , et al. Optimal network alignment with graphlet degree vectors[J]. Cancer Informatics, 2010, 9, 121- 137.
12 BAYATI M , GLEICH D F , SABERI A , et al. Message-passing algorithms for sparse network alignment[J]. ACM Transactions on Knowledge Discovery from Data, 2013, 7 (1): 1- 31.
13 KOUTRA D, TONG H, LUBENSKY D. BIG-ALIGN: fast bipartite graph alignment[C]//2013 IEEE 13th International Conference on Data Mining. Dallas: IEEE, 2013: 389-398.
14 SAAD-ELDIN A, PEDIGO B D, PRIEBE C E, et al. Graph matching via optimal transport[EB/OL]. (2021-11-09)[2023-09-01]. https://arxiv.org/abs/2111.05366.
15 SINGH R , XU J , BERGER B . Global alignment of multiple protein interaction networks with application to functional orthology detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105 (35): 12763- 12768.
16 HEIMANN M, SHEN H, SAFAVI T, et al. REGAL: representation learning-based graph alignment[C]//Proceedings of the 27th ACM International Conference on Information and Knowledge Management. New York: ACM, 2018: 117-126.
17 ZHANG Si, TONG Hanghang. FINAL: fast attributed network alignment[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco: ACM, 2016: 1345-1354.
18 MAN Tong, SHEN Huawei, LIU Shenghua, et al. Predict anchor links across social networks via an embedding approach[C]//Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. New York: AAAI Press, 2016: 1823-1829.
19 NGUYEN T T , PHAM M T , NGUYEN T T , et al. Structural representation learning for network alignment with self-supervised anchor links[J]. Expert Systems with Applications, 2021, 165, 113857.
doi: 10.1016/j.eswa.2020.113857
20 XIN Keyuan, SUN Zequn, HUA Wen, et al. Large-scale entity alignment via knowledge graph merging, partitioning and embedding[C]//Proceedings of the 31st ACM International Conference on Information & Knowledge Management. Atlanta: ACM, 2022: 2240-2249.
21 WANG Zichuan, LYU Qingsong, LAN Xiaohan, et al. Cross-lingual knowledge graph alignment via graph convolutional networks[C]//Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing. Brussels: Association for Computational Linguistics, 2018: 349-357.
22 LI Chengjiang, CAO Yixin, HOU Lei, et al. Semi-supervised entity alignment via joint knowledge embedding model and cross-graph model[C]//Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). Hong Kong: Association for Computational Linguistics, 2019: 2723-2732.
23 PEI Shichao, YU Lu, YU Guoxian, et al. Graph alignment with noisy supervision[C]//Proceedings of the ACM Web Conference 2022. New York: ACM, 2022: 1104-1114.
24 KOUTRA D , SHAH N , VOGELSTEIN J T , et al. Delta Con: principled massive-graph similarity function with attribution[J]. ACM Transactions on Knowledge Discovery from Data, 2016, 10 (3): 1- 43.
25 PRZULJ N . Biological network comparison using graphlet degree distribution[J]. Bioinformatics, 2007, 23 (2): e177- e183.
doi: 10.1093/bioinformatics/btl301
26 TONG H, FALOUTSOS C, PAN J Y. Fast random walk with restart and its applications[C]//Sixth International Conference on Data Mining (ICDM'06). Hong Kong: IEEE, 2006: 613-622.
27 XU K, HU W, LESKOVEC J, et al. How powerful are graph neural networks?[EB/OL]. (2018-10-01)[2023-08-06]. https://arxiv.org/abs/1810.00826.
28 XU Keyulu, LI Chengtao, TIAN Yongle, et al. Representation learning on graphs with jumping knowledge networks[C]// Proceedings of the 35th International Conference on Machine Learning: Volume 80. Stockholmsmässan: PMLR, 2018 : 5453-5462.
29 PARK J D , TRAN C , SHIN W Y , et al. On the power of gradual network alignment using dual-perception similarities[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023, 45 (12): 15292- 15307.
30 YAN Yucheng, ZHANG Si, TONG Hanghang. BRIGHT: a bridging algorithm for network alignment[C]//Proceedings of the Web Conference 2021. Ljubljana: ACM, 2021: 3907-3917.
31 GUIMERÀ R , DANON L , DÍAZ-GUILERA A , et al. Self-similar community structure in a network of human interactions[J]. Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics, 2003, 68, 065103.
32 CAO Xuezhi, YU Yong. BASS: a bootstrapping approach for aligning heterogenous social networks[M]//FRASCONI P, LANDWEHR N, MANCO G, et al. Machine Learning and Knowledge Discovery in Databases: Volume 9851. Cham: Springer, 2016: 459-475.
33 DU Xingbo, YAN Junchi, ZHA Hongyuan. Joint link prediction and network alignment via cross-graph embedding[C]//Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Macao: International Joint Conferences on Artificial Intelligence Organization, 2019: 2251-2257.
34 FEY M, LENSSEN J E. Fast graph representation learning with pytorch geometric[EB/OL]. (2019-05-06)[2023-09-01]. https://arxiv.org/abs/1903.02428v3.
[1] 孙承杰,李宗蔚,单丽莉,林磊. 一种基于核心论元的篇章级事件抽取方法[J]. 《山东大学学报(理学版)》, 2024, 59(7): 53-63.
[2] 刘沛羽,姚博文,高泽峰,赵鑫. 基于矩阵乘积算符表示的序列化推荐模型[J]. 《山东大学学报(理学版)》, 2024, 59(7): 44-52, 104.
[3] 邵伟,朱高宇,于雷,郭嘉丰. 高维数据的降维与检索算法[J]. 《山东大学学报(理学版)》, 2024, 59(7): 27-43.
[4] 杨纪元,马沐阳,任鹏杰,陈竹敏,任昭春,辛鑫,蔡飞,马军. 基于自监督的预训练在推荐系统中的研究[J]. 《山东大学学报(理学版)》, 2024, 59(7): 1-26.
[5] 陈海粟,廖佳纯,姚思诚. 政府开放数据中个人信息披露识别与统计方法[J]. 《山东大学学报(理学版)》, 2024, 59(3): 95-106.
[6] 温欣,李德玉. 基于属性加权的ML-KNN方法[J]. 《山东大学学报(理学版)》, 2024, 59(3): 107-117.
[7] 曾雪强,孙雨,刘烨,万中英,左家莉,王明文. 基于情感分布的emoji嵌入式表示[J]. 《山东大学学报(理学版)》, 2024, 59(3): 81-94.
[8] 牛泽群,李晓戈,强成宇,韩伟,姚怡,刘洋. 基于图注意力神经网络的实体消歧方法[J]. 《山东大学学报(理学版)》, 2024, 59(3): 71-80, 94.
[9] 史春雨,毛煜,刘浩阳,林耀进. 基于样本相关性的层次特征选择算法[J]. 《山东大学学报(理学版)》, 2024, 59(3): 61-70.
[10] 卢婵,郭军军,谭凯文,相艳,余正涛. 基于文本指导的层级自适应融合的多模态情感分析[J]. 《山东大学学报(理学版)》, 2023, 58(12): 31-40, 51.
[11] 王新生,朱小飞,李程鸿. 标签指导的多尺度图神经网络蛋白质作用关系预测方法[J]. 《山东大学学报(理学版)》, 2023, 58(12): 22-30.
[12] 张乃洲,曹薇. 一种基于文本语义扩展的记忆网络查询建议模型[J]. 《山东大学学报(理学版)》, 2023, 58(12): 10-21.
[13] 陈淑珍,史开泉,李守伟. 微信息的嵌入生成及其智能隐藏-还原[J]. 《山东大学学报(理学版)》, 2023, 58(12): 1-9.
[14] 仲诚诚,周恒,张梓童,张春雷. LAC-UNet: 基于胶囊表达局部-整体特征关系的语义分割模型[J]. 《山东大学学报(理学版)》, 2023, 58(11): 116-126.
[15] 吴贤君,唐绍诗,王明秋. 融合基础属性和通信行为的移动用户个性化推荐[J]. 《山东大学学报(理学版)》, 2023, 58(9): 81-93.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 刁科凤,赵　平 . 具有最小连通点对图的C-超图的染色讨论[J]. J4, 2007, 42(2): 56 -58 .
[2] 薛岩波 杨波 陈贞翔. 小波分析在土木工程结构健康监测系统中的应用研究[J]. J4, 2009, 44(9): 28 -31 .
[3] 江雪莲,石洪波*. 产生式与判别式组合分类器学习算法[J]. J4, 2010, 45(7): 7 -12 .
[4] 彭艳芬,李宝宗,刘天宝 . 有机气体麻醉活性的构效关系研究[J]. J4, 2006, 41(5): 148 -150 .
[5] 廖明哲. 哥德巴赫的两个猜想[J]. J4, 2013, 48(2): 1 -14 .
[6] 王开荣,高佩婷. 建立在DY法上的两类混合共轭梯度法[J]. 山东大学学报（理学版）, 2016, 51(6): 16 -23 .
[7] 伍代勇, 张海. 具有Allee效应和时滞的单种群离散模型的稳定性和分支[J]. 山东大学学报（理学版）, 2014, 49(07): 88 -94 .
[8] 周娟,郭卫华,宗美娟,韩雪梅,王仁卿 . 房干村不同植被下可培养细菌多样性研[J]. J4, 2006, 41(6): 161 -167 .
[9] 朱智强,马可欣,孙磊. 一种基于零知识证明的远程桌面认证协议[J]. 山东大学学报（理学版）, 2016, 51(9): 47 -52 .
[10] 王 兵 . 拟无爪图的性质[J]. J4, 2007, 42(10): 111 -113 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发