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

无监督图对齐通过仅利用图结构和节点特征确定带属性图的一对一节点对应关系。我们提出一种名为 CombAlign 的模型框架，将计算节点表示并匹配近似嵌入的方法与确定最优传输的 Gromov-Wasserstein 学习相结合，通过特征转换、基于嵌入的启发式方法和优化权重匹配的约束，逐步优化节点对齐，实验证明在对齐准确性上较现有方法显著改进。