基于拓扑结构表示学习的大规模无监督图对齐方法研究  

Large-Scale Graph Alignment Based on Topological Structure Representation Learning

作　　者：王晨旭 周俊铭[1] 姜佩京 WANG Chen-Xu;ZHOU Jun-Ming;JIANG Pei-Jing(School of Software Engineering,Xi’an Jiaotong University,Xi’an 710049;Ministry of Education Key Lab of Intelligent Network and Network Security,Xi’an Jiaotong University,Xi’an 710049)

机构地区：[1]西安交通大学软件学院,西安710049 [2]西安交通大学智能网络与网络安全教育部重点实验室,西安710049

出　　处：《计算机学报》2023年第7期1350-1365,共16页Chinese Journal of Computers

基　　金：国家自然科学基金(62272379);陕西省自然科学基金(2021JM-018);国家重点研发计划(2021YFB1715600);中央高校基本科研业务费专项资金(1191320006)资助。

摘　　要：图数据因其较强的复杂关系表征能力受到广泛关注,在社交网络、学术合作、道路交通、生物信息等多个领域具有重要应用.图对齐技术旨在找出不同图中属于同一实体的节点对,在多个领域具有重要的应用价值,例如,对不同社交网络中属于同一个用户的账号进行关联可以为推荐系统提供更丰富的用户行为画像,对不同生物组织的蛋白质网络进行对齐能够辅助研究人员分析蛋白质的特性和机能.然而,在缺乏人工标注信息的情况下仅使用图的拓扑结构信息实现无监督图对齐一直是图数据挖掘面临的重要难题之一,特别是在大规模图对齐任务中,存在初始种子节点发现难和计算效率低下的问题.针对以上问题,本文提出了一种基于拓扑结构表示学习的大规模无监督图对齐框架.首先,从待匹配图中选取典型子图作为种子节点候选集,利用局部拓扑结构信息计算得到高可靠的种子节点匹配对;然后利用所得种子节点将待匹配图进行融合,并提出一种高效的无监督表示学习算法将融合图映射到统一的向量空间中;最后利用学习得到的节点向量实现大规模图对齐.与已有方法相比,本文所提方法在大规模图对齐任务中用时最短,对齐结果准确率最高,且算法性能受图结构的差异性影响最小.Graph data has attracted lots of attention due to its strong ability of representing complex relationships.It has been widely used in many fields,such as social networks,academic cooperation,road traffic,and biological information.Graph alignment aims to find node pairs belonging to the same entity in different graphs,which have valuable applications in many fields.For example,associating accounts belonging to the same user in different social networks can provide richer user behavior profiles for recommender systems,and aligning protein networks of different biological tissues can assist researchers in analyzing the characteristics and functions of proteins.However,unsupervised graph alignment using the topological information of graphs has always been one of the important problems faced by graph data mining in the absence of manual annotation information.There are difficulties in finding initial seed nodes and low computational efficiency,especially for large-scale graph alignment tasks.To solve these problems,this paper proposes a large-scale unsupervised graph alignment framework based on topological structure representation learning.Firstly,a typical subgraph is selected from each of the graphs as a candidate set of seed nodes.The local topological information is used to retrieve a set of highly reliable seed node pairs.Then,we use the seed nodes to fuse the matching graphs,and propose an efficient unsupervised representation learning algorithm to map the fused graph into a unified vector space.Finally,large-scale graph alignment is realized based on the learned node vectors.Compared with existing methods,the proposed approach uses the least time in large-scale graph alignment tasks and achieves the best performance of alignment accuracy.Moreover,the structural differences of graphs have limited impacts on the performance of the proposed method.

关 键 词：图对齐 大规模图 无监督表示学习 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]