SGA: Self-boosting Attributed Graph Alignment via Neighborhood Consistency-based Edge Enhancement

Graph alignment, the task of identifying corresponding nodes across different graphs, is crucial for applications ranging from social network analysis to bioinformatics. Although most existing methods leverage graph neural networks (GNNs) to learn node embeddings for attributed graphs and match them based on node similarity, they often rely on objectives designed for node classification or link prediction. These approaches preserve node proximity within individual graphs but fail to capture cross-graph correspondence knowledge, leading to suboptimal alignment performance. This paper presents SGA (Self-boosting Graph Alignment), a novel framework that introduces a self-supervised objective and an iterative refinement scheme for robustly aligning attributed graphs. SGA begins with an unsupervised Graph Convolutional Network (GCN) to learn initial node representations. Then, a contrastive loss is designed to train the GCN using stably aligned node pairs derived from these initial embeddings. This constraint distinguishes closely connected nodes within individual graphs by leveraging cross-graph correspondence knowledge, thereby promoting accurate alignment across graphs. To handle graphs with incomplete topology, SGA incorporates an iterative refinement process enhanced by a neighborhood consistency metric. This metric evaluates the reliability of complementary edges, ensuring that only reliable connections are used to refine the graph structures. The refined graphs are then fed back into the GCN for the subsequent iterations, with the process terminating when no additional pseudo-aligned node pairs are identified or a maximum iteration count is reached. Extensive experiments on four real-world and two synthetic datasets demonstrate that SGA outperforms state-of-the-art graph alignment methods by an average of 5.8% in alignment accuracy. Our code is publicly available at https://github.com/XNetLab/SGA.