  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.
