Search papers, labs, and topics across Lattice.
This paper introduces GlobAlign and GlobAlign-E, novel unsupervised graph alignment methods that shift from a "local representation, global alignment" paradigm to a "global representation and alignment" paradigm. GlobAlign leverages a global attention mechanism and hierarchical cross-graph transport cost to capture long-range node dependencies. GlobAlign-E further improves efficiency by reducing the optimal transport's cubic complexity to quadratic, achieving significant speedups while maintaining accuracy.
Unsupervised graph alignment gets a speed boost: GlobAlign-E slashes computation time by an order of magnitude while simultaneously boosting accuracy by up to 20%.
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 \underline{Gl}obal representation and \underline{o}ptimal transport-\underline{b}ased \underline{Align}ment (\texttt{GlobAlign}), and its variant, \texttt{GlobAlign-E}, for better \underline{E}fficiency. 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, \texttt{GlobAlign-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, \texttt{GlobAlign-E} achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods.
