Towards Effective and Efficient Graph Alignment without Supervision

arXiv:2603.08526v1 Announce Type: cross
Abstract: Unsupervised graph alignment aims to find the node correspondence across different graphs without any anchor node pairs. Despite the recent efforts utilizing deep learning-based techniques, such as the embedding and optimal transport (OT)-based approaches, we observe their limitations in terms of model accuracy-efficiency tradeoff. By focusing on the exploitation of local and global graph information, we formalize them as the “local representation, global alignment” paradigm, and present a new “global representation and alignment” paradigm to resolve the mismatch between the two phases in the alignment process. We then propose underlineGlobal representation and underlineoptimal transport-underlinebased underlineAlignment (textttGlobAlign), and its variant, textttGlobAlign-E, for better underlineEfficiency. Our methods are equipped with the global attention mechanism and a hierarchical cross-graph transport cost, able to capture long-range and implicit node dependencies beyond the local graph structure. Furthermore, textttGlobAlign-E successfully closes the time complexity gap between representative embedding and OT-based methods, reducing OT’s cubic complexity to quadratic terms. Through extensive experiments, our methods demonstrate superior performance, with up to a 20% accuracy improvement over the best competitor. Meanwhile, textttGlobAlign-E achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods.