JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (7): 64-75.doi: 10.6040/j.issn.1671-9352.1.2023.102

• Review • Previous Articles     Next Articles

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)

82

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

CLC Number: 

  • TP391

Fig.1

Graphlet degree vector"

Table 1

Information of dataset"

数据集 网络名 节点数 边数 节点属性数 所有的对齐节点对数
原始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

Table 2

Alignment results"

数据集 指标 本文方法/% 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

Fig.2

Influence of positive anchor nodes ratio on alignment accuracy"

Fig.3

Influence of iterations on alignment accuracy"

Fig.4

Influence of alignment components on alignment accuracy"

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] Chengjie SUN,Zongwei LI,Lili SHAN,Lei LIN. A document-level event extraction method based on core arguments [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(7): 53-63.
[2] Peiyu LIU,Bowen YAO,Zefeng GAO,Wayne Xin ZHAO. Matrix product operator based sequential recommendation model [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(7): 44-52, 104.
[3] Wei SHAO,Gaoyu ZHU,Lei YU,Jiafeng GUO. Dimensionality reduction and retrieval algorithms for high dimensional data [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(7): 27-43.
[4] Jiyuan YANG,Muyang MA,Pengjie REN,Zhumin CHEN,Zhaochun REN,Xin XIN,Fei CAI,Jun MA. Research on self-supervised pre-training for recommender systems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(7): 1-26.
[5] Haisu CHEN,Jiachun LIAO,Sicheng YAO. Identification and statistical analysis methods of personal information disclosure in open government data [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(3): 95-106.
[6] Xin WEN,Deyu LI. The ML-KNN method based on attribute weighting [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(3): 107-117.
[7] Xueqiang ZENG,Yu SUN,Ye LIU,Zhongying WAN,Jiali ZUO,Mingwen WANG. Emoji embedded representation based on emotion distribution [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(3): 81-94.
[8] Zequn NIU,Xiaoge LI,Chengyu QIANG,Wei HAN,Yi YAO,Yang LIU. Entity disambiguation method based on graph attention networks [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(3): 71-80, 94.
[9] Chunyu SHI,Yu MAO,Haoyang LIU,Yaojin LIN. Hierarchical feature selection algorithm based on instance correlations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(3): 61-70.
[10] Chan LU,Junjun GUO,Kaiwen TAN,Yan XIANG,Zhengtao YU. Multimodal sentiment analysis based on text-guided hierarchical adaptive fusion [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 31-40, 51.
[11] Xinsheng WANG,Xiaofei ZHU,Chenghong LI. Label guided multi-scale graph neural network for protein-protein interactions prediction [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 22-30.
[12] Naizhou ZHANG,Wei CAO. A memory network model based on semantic expansion of text for query suggestion [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 10-21.
[13] Shuzhen CHEN,Kaiquan SHI,Shouwei LI. Embedded generation of micro-information and its intelligent hiding-restoration [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 1-9.
[14] Chengcheng ZHONG,Heng ZHOU,Zitong ZHANG,Chunlei ZHANG. LAC-UNet: semantic segmentation model based on capsules for representing part-whole hierarchical features [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 116-126.
[15] Xianjun WU,Shaoshi TANG,Mingqiu WANG. Personalized recommendation of mobile users by integrating basic information and communication behavior [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(9): 81-93.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] DIAO Ke-feng and ZHAO Ping . On the coloring of C-hypergraphs with minimum connected pair graphs[J]. J4, 2007, 42(2): 56 -58 .
[2] XUE Yan-Bei, YANG Bei, CHEN Zhen-Xiang. Structural health monitoring of civil engineering based on wavelet analysis[J]. J4, 2009, 44(9): 28 -31 .
[3] JIANG Xue-lian, SHI Hong-bo*. The learning algorithm of a generative and discriminative combination classifier[J]. J4, 2010, 45(7): 7 -12 .
[4] PENG Yan-fen,LI Bao-zong,LIU Tian-bao . Relationships between the structures and the anesthetic[J]. J4, 2006, 41(5): 148 -150 .
[5] Ming-Chit Liu. THE TWO GOLDBACH CONJECTURES[J]. J4, 2013, 48(2): 1 -14 .
[6] WANG Kai-rong, GAO Pei-ting. Two mixed conjugate gradient methods based on DY[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(6): 16 -23 .
[7] WU Dai-yong, ZHANG Hai. Stability and bifurcation analysis for a single population discrete model with Allee effect and delay[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(07): 88 -94 .
[8] ZHOU Juan,GUO Wei-hua,ZONG Mei-juan,HAN Xue-mei,WANG REN-qing . Analysis of the soil cultivable bacterial diversities underdifferent vegetations of Fanggan village[J]. J4, 2006, 41(6): 161 -167 .
[9] ZHU Zhi-qiang, MA Ke-xin, SUN Lei. A zero-knowledge proof based remote desktop authentication protocol[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(9): 47 -52 .
[10] WANG Bing . Properties of a quasi-claw-free graph[J]. J4, 2007, 42(10): 111 -113 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd