图结构相似性度量 | 长亭百川云

分享一篇关于图结构相似性度量的文章，来自AAAI 20，题目为"Learning-Based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching"。

这篇阅读笔记只关注应用部分的内容，并不涉及相关数学原理的解读（我系做代码分析的啦，靓仔）。

图相似度计算是许多基于图的应用程序的核心操作之一，如图相似度搜索、图数据库分析、图聚类等。由于计算两个图之间的精确距离/相似度通常是NP困难的，因此提出了一系列在精度和速度之间权衡的近似方法。近年来，人们提出了几种数据驱动的神经网络方法，将图的相似度建模为其图级表示的内积，并提出了不同的技术来生成每个图的嵌入。然而，对每个图使用一个固定维度的嵌入可能无法完全捕获不同大小和链接结构的图——这一限制对于图相似度计算任务（其目标是找到两个图之间的细粒度差异）来说尤其有问题。在本文中，作者从另一个角度解决了图的相似度计算问题，通过直接匹配两组节点嵌入，而不需要使用固定维向量来表示整个图的相似度计算。

Problem Definition

图是一个包含节点集和边集的数据结构，。每一个节点和边都可以有相应的标签，例如分子图中的院子和化学键类型。在本研究中，作者将图限定为无向图和未加权图，但也可以将GRAPHSIM（本文所提模型）扩展到其他类型的图，因为GRAPHSIM是用于图相似性计算的通用框架。

给定两个图和，可以定义不同的距离和相似性指标：

Graph Edit Distance（GED）：两个图和之间的编辑距离是指将转换成的最优比对中的编辑操作的数量，其中对图的编辑操作是指插入/删除一个节点/边或对节点重新打标签。本文使用一对一映射函数将GED转换成范围在0和1之间的相似性度量。
Maximum Common Subgraph（MCS）：最大公共子图是指和之间的公共子图，该子图以外的所有子图都没有包含比它更多的节点。本文中，和的相似性得分被定义为最大公共子图的节点数，即：。
基于学习的图相似性计算：给定一个图相似性定义，目标是学习一个基于神经网络的函数，该函数将两个图作为输入，并通过训练输出所需的相似性得分。

Approach

本文所提方法的框架如图2所示，包括3个阶段：

Multi-Scale Neighbor Aggregation

对两个图中每个节点在不同尺度上生成向量表示。图2中不同类型的节点用不同的颜色表示，用one-hot对节点进行初始化向量表示。对于具有未标记节点的图，使用与初始表示相同的常量向量。直观地说，图卷积运算聚集了节点的一阶邻居的特征。由于在一个节点上应用一次GCN层可以看作是聚合了它的一阶邻居和它自己的表示，顺序堆叠L层将导致一个节点的最终表示包括它的L阶邻居。换句话说，GCN层越多，学习到的嵌入规模就越大。

使用深度GCN架构的潜在问题是：在多次聚合邻居后，嵌入可能会在局部邻居中丢失微妙的模式。当两个图非常相似时，这个问题尤其严重，而差异主要在于小的局部子结构。

人类比较两个图之间差异的一种自然方法是通过自上而下的方法递归地将整个图分解为其组成子图。每个子图进一步分解为额外的子图级别，直到整个规范减少到节点级别，产生子图(分解)组合的层次结构。因此，本文提出了一个多尺度框架来提取用于构建相似矩阵的许多GCN层中的每个层的输出。

Similiarity Matrix Generation

计算两个图中每对节点的嵌入之间的内积，得到多个相似矩阵，捕获不同尺度的节点-节点交互得分。在一些经典的图相似度建模方法中使用了节点-节点相似度评分，例如用于图分类的Optimal Assignment Kernels和用于GED近似的Bipartite Graph Matching。

对于Optimal Assignment Kernels，直观地，两个图中的每一个都表示为一组节点嵌入，kernel找到将一组节点嵌入转换为另一组节点嵌入的最佳方法，其中转换一对节点的代价是它们的欧几里得距离。

对于Bipartite Graph Matching，尽管目标不同，但核方法和GED近似算法都直接处理节点级信息，而不需要全图表示。具体来说，两者都需要两个图之间的成对节点-节点距离得分，节点-节点距离的定义不同。由于GRAPHSIM是端到端训练用于图的相似度计算，可以计算两个图中所有对节点嵌入在多个尺度上的内积，从而得到多个相似矩阵。将每个矩阵视为一幅图像，将图相似度度量任务视为一个图像处理问题，其目标是利用CNN发现图像中编码的最优节点匹配模式。将此过程视为将两组节点嵌入转换为分数的相似性操作符，则GRAPHSIM可视为:

其中表示相似度矩阵生成和它的后续层。训练过程以正确的相似性得分为指导，更新与生成节点嵌入X和Y以及后续CNN的邻居聚合层相关的权重。

对于BFS Order，与图像的像素或句子的单词不同，图的节点通常缺乏排序。不同的节点排序将导致不同的相似性矩阵。为了完全解决图节点排列问题，需要为图集合中的每个图找到一个规范排序，这是NP困难的。此外，CNN需要空间局部性保留。为了缓解这两个问题，本文利用GraphRNN中提出的广度优先搜索（BFS）节点排序方案对节点嵌入进行排序和重新排序。由于BFS是在图上执行的，附近的节点被排序为彼此靠近。值得注意的是，BFS排序方案在排序的效率和唯一性之间实现了合理的权衡，因为它在最坏的情况下（即完全图）需要二次运算。

除了与节点排列和空间局域性相关的问题外，还必须解决图大小差异带来的挑战以及CNN架构需要固定长度输入的事实。为了在确定相似矩阵大小的同时保留图大小方差信息，本文提出如下解决方案：

Max Padding：可以通过将fake节点添加到预定义的数量来固定每个图中的节点数量，从而导致固定大小的相似矩阵。然而，这样的矩阵将完全忽略图大小信息，这在GED和MCS的定义中都是至关重要的。例如，两个小但同构的图之间的相似性矩阵可能被填充了很多零，这可能会误导CNN预测它们是不相似的。为了反映相似矩阵中图大小的差异，本文设计了最大填充。假设和分别包含和个节点，在两个图中较小的图的节点嵌入矩阵中填充行零，使两个图都包含最大个节点。
Matrix Resizing：为了将CNN应用于相似矩阵，本文通过图像重采样来调整相似矩阵的大小。本文选择双线性插值，并将探索更先进的技术留给未来的工作。得到的相似矩阵具有固定形状，其中是控制重采样导致的信息损失程度的超参数。相似性矩阵的生成过程如下（翻译不动了，自己看吧）：

CNN Based Similarity Score Computation

将相似度计算问题转化为模式识别问题，为全连接网络提供多尺度特征，得到最终预测的图-图相似度得分。作者将这些矩阵通过多个CNN并行输入。如图2所示，使用了三个CNN通道，每个通道都有自己的CNN滤波器。最后，将结果连接并馈送到多个完全连接的层中，从而为图对和生成最终的相似度分数。损失函数为均方误差：

其中D是训练图对的集合，是来自任何图相似度度量的真实相似度得分。对于GED，采用一对一映射函数将真距离得分转化为真相似得分；对于MCS，将归一化的MCS大小作为真实相似度得分。