Combining Optimal Transport and Embedding-Based Approaches for More Expressiveness in Unsupervised Graph Alignment

• DOI: 10.48550/arxiv.2406.13216
• Publication Date: 2024-06-19
• Authors: Songyang Chen; Yu Liu; Lei Zou; Zexuan Wang; Youfang Lin; Yuxing Chen; Anqun Pan
• Keywords: Graph Embedding

Unsupervised graph alignment finds the one-to-one node correspondence between a pair of attributed graphs by only exploiting structure and features. One category existing works first computes representation then matches nodes with close embeddings, which is intuitive but lacks clear objective tailored for in unsupervised setting. The other reduces problem to optimal transport (OT) via Gromov-Wasserstein (GW) learning well-defined leaves large room exploring design cost. We propose principled approach combine their advantages motivated theoretical analysis model expressiveness. By noticing limitation discriminative power separating matched unmatched pairs, we improve cost GW feature transformation, enables interaction across dimensions. Besides, simple yet effective embedding-based heuristic inspired Weisfeiler-Lehman test add its prior knowledge OT more expressiveness when handling non-Euclidean data. Moreover, are guarantee matching constraint reducing maximum weight matching. algorithm effectively combines our predictions stacking, an ensemble strategy. framework named \texttt{CombAlign} integrating all above modules refine progressively. Through extensive experiments, demonstrate significant improvements accuracy compared state-of-the-art approaches validate effectiveness proposed modules.