Graph Alignment Using Seed-Oriented Subgraph Matching
Wei Tang, Xinglin Lyu, Yuang Li, Min Zhang, Hao Yang · 2025
This paper addresses the challenge of unsupervised plain graph alignment, specifically in scenarios where auxiliary information, such as node attributes, is unavailable. Existing alignment algorithms primarily fall into two categories: spectral methods and representation learning-based methods. Spectral methods typically leverage alignment consistency principles, employing heuristic strategies to iteratively infer the alignment matrix. In contrast, representation learning methods focus on encoding the geometric structural features of nodes to generate node representations, thereby transforming the node matching task into a similarity computation based on these representations. While both approaches demonstrate robust performance in the graph alignment domain, their time complexity poses significant concerns. To mitigate this issue, we propose a novel, efficient algorithm grounded in seed-oriented subgraph matching. Our method begins by extracting a limited number of reliable pseudo alignment seeds derived from graph geometric features. Subsequently, we extract the corresponding K-hop seed-oriented subgraphs, allowing us to reformulate the graph alignment problem into a series of subgraph matching tasks. The final alignment matrix is then constructed by aggregating the results of these subgraph matches. Experimental evaluations conducted on public datasets reveal that our method not only improves efficiency but also outperforms current state-of-the-art techniques in terms of accuracy.