S3GA: Towards Scalable Self-Supervised Learning for Large Scale Graph Alignment

Graph Alignment (GA) is an NP-hard combinatorial challenge. The existing methods usually work on small-scale graphs because their computational complexity grows as the square of the number of nodes. Recent techniques relied on alignment labels to divide the large source and target graphs into small ones respectively, which are then aligned separately. However, the alignment labels in expansive real-world graphs are often scarce, which makes GA even more challenging. To address these issues, we propose a novel self-supervised learning framework that is able to work on the graphs of million nodes without any alignment labels, where the existing methods usually fail to output an answer within a reasonable time. Our method also falls in the divide-and-conquer paradigm. We do not cluster the source and target graph separately by the existing graph clustering algorithms, because it is difficult to pair and then align the cluster-induced source and target subgraphs in the absence of alignment labels. We devise an Alignment-Aware Clustering (AAC) method to partition the source and target nodes jointly and keep the ought-to-be-aligned pairs of nodes within the same cluster as much as possible. Furthermore, we develop a Topology-Aware Repartition (TAR) that leverages pseudo-alignment labels as anchors for re-clustering, preserving detailed structural information within clusters. This enables graph neural networks to effectively enhance the graph representation learning for node alignments which are self-supervised by a graph-matching solver. Extensive experiments have demonstrated that our method greatly reduces computational demands and sustains high alignment accuracies in large-scale graph applications.