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 学习相结合，通过特征转换、基于嵌入的启发式方法和优化权重匹配的约束，逐步优化节点对齐，实验证明在对齐准确性上较现有方法显著改进。

基于优化传输和嵌入方法的无监督图对齐中提供更多表达性

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

Finding node correspondence across networks, namely multi-network alignment,
is an essential prerequisite for joint learning on multiple networks. Despite
great success in aligning networks in pairs, the literature on multi-network
alignment is sparse due to the exponentially growing solution space and lack of
high-order discrepancy measures. To fill this gap, we propose a hierarchical
multi-marginal optimal transport framework named HOT for multi-network
alignment. To handle the large solution space, multiple networks are decomposed
into smaller aligned clusters via the fused Gromov-Wasserstein (FGW)
barycenter. To depict high-order relationships across multiple networks, the
FGW distance is generalized to the multi-marginal setting, based on which
networks can be aligned jointly. A fast proximal point method is further
developed with guaranteed convergence to a local optimum. Extensive experiments
and analysis show that our proposed HOT achieves significant improvements over
the state-of-the-art in both effectiveness and scalability.

多网络对齐的多层次多边界优化传输框架（HOT）通过分解网络，使用融合的 Gromov-Wasserstein（FGW）质心来处理大规模的解空间，并基于多边界设置将 FGW 距离推广到多网络对齐中，进而开发了一种快速的邻近点方法以获得局部最优解，通过广泛的实验证明了 HOT 在效果和可扩展性方面都明显优于现有技术的成果。

网络对齐的分层多边际最优输运

Hierarchical Multi-Marginal Optimal Transport for Network Alignment

Subgraph isomorphism or subgraph matching is generally considered as an
NP-complete problem, made more complex in practical applications where the edge
weights take real values and are subject to measurement noise and possible
anomalies. To the best of our knowledge, almost all subgraph matching methods
utilize node labels to perform node-node matching. In the absence of such
labels (in applications such as image matching and map matching among others),
these subgraph matching methods do not work. We propose a method for
identifying the node correspondence between a subgraph and a full graph in the
inexact case without node labels in two steps - (a) extract the minimal unique
topology preserving subset from the subgraph and find its feasible matching in
the full graph, and (b) implement a consensus-based algorithm to expand the
matched node set by pairing unique paths based on boundary commutativity. Going
beyond the existing subgraph matching approaches, the proposed method is shown
to have realistically sub-linear computational efficiency, robustness to random
measurement noise, and good statistical properties. Our method is also readily
applicable to the exact matching case without loss of generality. To
demonstrate the effectiveness of the proposed method, a simulation and a case
study is performed on the Erdos-Renyi random graphs and the image-based affine
covariant features dataset respectively.

在没有节点标签的情况下，我们提出了一种在不精确匹配的情况下识别子图与完整图之间节点对应关系的方法，该方法包括两个步骤：提取子图的最小唯一拓扑保持子集及在全图中查找可行匹配，实现基于边界可交换性的独特路径配对扩展匹配集，并通过共识算法。