论文导读 | 图对齐

半监督图对齐

图对齐问题是将两个图的节点进行匹配的问题。而半监督图对齐指的是已知小部分节点之间的对应关系，通过学习获得其他节点的匹配关系。

问题定义如下：给定属性图、和锚节点对，输出相似矩阵，表示中结点和中结点的相似性。

解决这个问题常见方法有以下3种：consistency-based、embedding-based和optimal transport。

consistency-based method

consistency-based method基于拓扑结构的一致性假设，即如果在图中和是相邻节点，在图中和也是相邻节点，并且如果对齐到，那么很可能应该对齐到。目标函数如下：

其中为结点的度数；是先验对齐矩阵，有锚链接的条目为1，否则为0。

目标函数的显式解为

其中，并且。所以表示锚点对经过步移动到。是锚点对在product graph随机游走，以概率消减赋值，得到的和。

consistency-based方法有以下两个局限性：

一、由于网络的异质性，这种一致性假设很可能会被违反。例如，用户可能在一个社交网络中表现活跃，而在另一个社交网络中表现安静。上述公式要求，只有当锚链的两个锚节点以完全相同的步长到达给定节点对时，才能给结点对赋值。所以即使是很小的扰动也可能对结果产生巨大的影响。

二、上述公式可能产生过平滑的问题。

embedding-based

BRIGHT[1]模型在consistency-based方法的基础上获得结点embedding。BRIGHT使用RWR算法求得embedding矩阵，公式为。这样避免了步长相同的限制，给随机行走过程带来了更大的灵活性，更具鲁棒性。然后经过线性层获得拓扑结构相关的node embedding，这是为了让两个图嵌入到同一个空间。

BRIGHT使用marginal ranking loss，。其中是节点的负对抽样集。为了提高负采样的质量和对齐性能，我们采样中与锚节点在中的嵌入最接近的节点作为下一个epoch的负样例。

NextAlign[2]在建模结点embedding和采样两个方面对BRIGHT做出改进。

NextAlign在RWR和线性层中间增加了RelGCN-U和注意力机制。RelGCN-U是合并两个图并在大图上进行消息传递，这是为了更好地建模两个图之间的交互关系。注意力机制是为了解决区域之间对齐分数一致的过平滑问题（例如图中的点和点）。

损失函数如下：

在抽样负样本的时候，一些方法主张抽样embedding相近的结点，然而这违反对齐一致性假设；另一些方法主张抽样embedding相差较大的结点或者随机采样，这可能对学习有意义的嵌入贡献不大。

NextAlign为了解决这个问题，就将embedding分为两块，一块表示在本图的信息，一块表示在另一张图中的信息。在采样的时候使用不同部分的信息。公式如下：

optimal transport

optimal transport把相似矩阵的计算建模为最优传输问题。其中是代价矩阵，是相似矩阵。

PARROT[3]除此之外，还设计了3个正则化项。

一、edge consistency regularization：两个对齐结点之间的连边embedding通常比较相似

是边embedding矩阵，

二、neighborhood consistency：相同邻域的相似度相近

其中表示的是局部相似度信息

三、S和先验分布相近

其中是先验相似矩阵，，当且仅当 。

最终的优化公式为。可以将其转化为凸优化问题并通过近似点算法进行求值。

Reference

[1] Yan, Y., Zhang, S., & Tong, H. (2021). BRIGHT: A Bridging Algorithm for Network Alignment. Proceedings of the Web Conference 2021.

[2] Zhang, S., Tong, H., Jin, L., Xia, Y., & Guo, Y. (2021). Balancing Consistency and Disparity in Network Alignment. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining.

[3] Zeng, Z., Zhang, S., Xia, Y., & Tong, H. (2023). PARROT: Position-Aware Regularized Optimal Transport for Network Alignment. Proceedings of the ACM Web Conference 2023.