七、PATCHY-SAN

1. 很多重要问题都可以视为图数据得学习问题。考虑以下两个问题：

   • 给定一组图作为训练数据，学习一个用于对未见过的图（即测试图）进行分类或者回归的函数。其中训练集中任意两个图的结构不一定是相同的。例如：给定一组化合物以及它们对于癌细胞活性抑制效果，用于预测新的化合物对于癌细胞活性抑制的结果。
   • 给定一张大图，学习该图的representation 从而可以推断未见过的图属性，如顶点类型（即顶点分类）、缺失边（即链接预测）。

2. 卷积神经网络CNN 在图像领域中大获成功。图像image 也是一种图graph ，但是它是一种特殊的正方形的网格图，其中顶点表示像素。如下图所示，黑色/白色顶点表示像素的不同取值（黑色取值为1、白色取值为0 ），红色顶点表示当前卷积核的中心位置。(a) 图给出了一个 3x3 卷积核在一个 4x4 图像上的卷积过程，其中步幅为1、采用非零填充。

   我们可以将 CNN 视为遍历一个顶点序列（即图(a) 中的红色顶点 1,2,3,4 ）、然后为该序列中的每个顶点生成固定大小的邻域子图（即图(b) 中的 3x3 网格） 的过程。其中邻域子图作为感受野receptive field，用于特征抽取（抽取感受野中顶点的特征）。

   

   由于像素点的隐式空间顺序，从左到右以及从上到下唯一确定了这个顶点序列。在NLP 问题中，句子也隐式的从左到右确定了单词的顺序。但是对于图graph 问题，难以针对不同的问题给予一个合适的顶点顺序。同时数据集中不同图的结构不同，不同图的顶点之间都无法对应。

   因此如果希望将卷积神经网络应用到图结构上，必须解决两个问题：

   • 为图确定一个顶点序列，其中我们为序列中的每个顶点创建邻域子图。
   • 邻域图的归一化，即将邻域子图映射到向量空间，从而方便后续的卷积运算（因为卷积核无法作用于子图上）。

   论文《Learning Convolutional Neural Networks for Graphs》 提出了一种学习任意图的卷积神经网络框架 PATCHY-SAN ，该框架解决了这两个问题。PATCHY-SAN 适用于无向图/有向图，可以处理连续/离散的顶点和边的属性，也支持多种类型的边。

   对于每个输入的graph，PATCHY-SAN 方法首先确定了一个顶点序列；然后，对序列中每个顶点提取一个正好由 个顶点组成的邻域并归一化邻域，归一化的邻域将作为当前顶点的感受野；最后，就像 CNN 的感受野一样，可以将一些特征学习组件（如卷积层、dense 层）作用到归一化邻域上。其整体架构如下图所示，其中红色顶点表示顶点序列中的顶点， 。

   

3. PATCHY-SAN 方法具有以下优势：

   • 计算高效，原生支持并行计算，并且可用于大型图。
   • 支持特征可视化，可以深入了解图的结构属性。
   • 相比较与 graph kernel 方法，PATCHY-SAN 无需依赖任何特征工程就可以学到具体任务的特征。

7.1 模型

7.1.1 Graph Kernel

1. 目前现有的大多数 Graph Kernel 算法都是基于 R-Convolution 理论构建而来，其理论思想是：设计一种图的分解算法，两个图的核函数和图分解后的子结构相似程度有关。

   给定两个图 以及一种图的分解方式 ，则分解后的子结构为：

   

   基于该子结构，则 和 的核函数可以表示为：

   

   其中：

   

   因此，任意一种图的分解方式 以及任意一种子结构同构判断方式 的组合都可以定义一种新的 Graph Kernel ，常见的主要分为三类：

   • 基于游走的Graph Kernel，如 Random Walk Kernel。
   • 基于路径的 Graph Kernel，如 Shortest-Path Kernel 。
   • 基于子树subtree 或者子图 subgraph 的 Graph Kernel ，如 Weisfeiler-Lehman Subtree Kernel。

   另外，除了 R-Convolution 系列之外，还有其它的 Graph Kernel 。

2. Random Walk Kernel：随机游走Kernel 的基本思想是：统计两个输入图中相同的随机游走序列的数量。

   给定输入图 ，设顶点 的label 为 。定义direct product graph 为： ，其中：

   

   其中 表示顶点 的label， 表示边 的 label 。

   定义图 的邻接矩阵为 ，则随机游走 kernel 定义为：

   

   其中 必须仔细挑选从而保证 的收敛性。

   • 给出了 中两个顶点label 相同的顶点pair 对

   • 给出了 中两条边label 相同、边的对应顶点分别相同的边 pair 对。

     G1:        v1(label=A) -------- v2(label=B), label(v1,v2) = s
     G2:        w1(label=A) -------- w2(label=B), label(w1,w2) = s

   • ：给出了图 和 中，长度为 的路径的数量，该路径满足以下条件：路径的顶点label 序列完全相同、顶点的边label 序列完全相同。

     G1: (label = A1) ---s1--- (label = A2) ---s2--- (label = A3)
     G2: (label = A1) ---s1--- (label = A2) ---s2--- (label = A3)

3. Shortest-Path Kernel：随机游走Kernel 的基本思想是：统计两个输入图中相同标签之间的最短路径。

   给定输入图 ：

   • 首先通过Floyd 成对最短路径生成算法，构建每个图的顶点之间的最短路径，得到新的图 ，其中 给出了 的两两顶点之间最短路径、 给出了 的两两顶点之间最短路径。

   • 计算：

     

     其中 为一个定义在长度为1 的 edge walk 上的正定核（？需要参考代码）。

4. Weisfeiler-Lehman Subtree Kernel ：它基于 Weisfeiler-Lehman 算法。

   • 顶点 label 更新：对于图 的顶点 ，获取顶点 的邻居顶点 ，通过一个 hash 函数得到顶点 的新label：

     

     更新后的新label 包含了其直接邻域的顶点信息。因此如果两个顶点更新后的 label 相同，我们可以认为其邻域结构是同构的。

   • 更新图的所有顶点 、重复更新最多 轮直到收敛，最终得到图 。

     每一轮更新后，顶点 的 label 就包含了更大规模的邻域的顶点信息，最终每个顶点的 label 编码了图的全局结构信息。

   • 对于输入图 我们分别对其执行 Weisfeiler-Lehman 算法，最终根据 的 顶点label 集合的相似性（如 Jaccard 相似性）来得到核函数：

     

     其中 为顶点的label 集合。

5. 一旦定义了 Graph Kernel，则我们可以使用基于核计巧的方法，如 SVM 来直接应用在图上。

7.1.2 PATCHY-SAN

1. 给定图 ，假设顶点数量为 ，边的数量 。

   • 定义图的邻接矩阵 为：

     

   • 每个顶点以及每条边可以包含一组属性，这些属性可以为离散的，也可以为连续的。

   • 定义一个游走序列 walk 是由连续的边组成的一个顶点序列；定义一条路径 path 是由不重复顶点构成的walk 。

   • 定义 为顶点 和 之间的距离，它是 和 之间的最短路径距离。

   • 定义 为顶点 的一阶邻居顶点集合，它由与 直连的所有顶点构成。

2. PATCHY-SAN 利用了graph labeling 对顶点进行排序。

   • 如果图的顶点自带label， 则我们可以直接用该label ；如果顶点没有label ，则我们可以通过一个graph labeling 函数 为图注入label ，其中 为一个有序集（如，实数集 或整数集 ）。

     • graph labeling 的例子包括：通过顶点的度degree 计算label、通过顶点的中介中心性between centrality 计算 label 。

       一个顶点 的中介中心性为：网络中经过顶点 的最短路径占所有最短路径的比例。

     • graph labeling 引入顶点集合 的一个划分： ，其中 为label 的取值类别数。顶点 当且仅当 。

   • 一个排序 ranking 是一个函数 。每个graph labeling 引入一个排序函数，使得当且仅当 时有 ，即：label 越大则排序越靠前。

   • 给定一个 graph labeling，则它决定了图 中顶点的顺序，根据该顺序我们定义一个邻接矩阵 ，它定义为：

     

     其中顶点 在 中的位置由它的排名 决定。

3. 如前所述，如果希望将卷积神经网络应用到图结构上，必须解决两个问题：

   • 为图确定一个顶点序列，其中我们为序列中的每个顶点创建邻域子图
   • 邻域图的归一化，即将邻域子图映射到向量空间，使得相似的邻域子图具有相似的vector 。

   PATCHY-SAN 通过graph labeling 过程来解决这些问题。给定一组图，PATCHY-SAN 对每个图执行以下操作：

   • 采用 Node Sequence Selection 算法从图中选择一个固定长度的顶点序列。
   • 采用 Neighborhood Assembly 算法为顶点序列中的每个顶点拼装一个固定大小的邻域。
   • 通过 Graph Normalization 对每个邻域子图进行归一化处理，从而将无序的图转换为有序的、长度固定的顶点序列。
   • 利用卷积神经网络学习邻域的 representation。

a. Node Sequence Selection

1. 顶点序列选择是为每个输入的图鉴别需要创建感受野的顶点的过程。

   顶点序列选择过程首先将输入图的顶点根据给定的 graph labeling 进行排序；然后，使用给定的步幅 遍历所有的顶点，并对每个访问到的顶点采用创建感受野的算法来构造一个感受野，直到恰好创建了 个感受野为止。

   • 步幅 决定了顶点序列中，需要创建感受野的两个顶点之间的距离。

   • 决定了卷积运算输出 feature map 的尺寸，它对应于CNN 中的图像宽度。

     如果顶点数量小于 ，则算法创建全零的感受野，用于填充。

   • 也可以采用其它顶点序列选择方法，如根据 graph labeling 进行深度优先遍历。

2. Select Node Sequence 算法：

   • 算法输入：

     • graph labeling 函数
     • 输入图
     • 步幅 、宽度 、感受野尺寸

   • 算法输出：被选择的顶点序列，以及对应的感受野

   • 算法步骤：

     • 根据 选择顶点集合 中的 top 个顶点，记作 。

     • 初始化：

     • 迭代，直到 停止迭代。迭代步骤为：

       • 如果 ，则对排序后的顶点 创建感受野 ；否则创建全零感受野 。

       • 将 应用到每个输入通道。

         因为顶点的特征可能是一个向量，表示多维度属性。

       • 更新： 。

     • 返回访问到的顶点序列，以及创建的感受野序列。

b. Neighborhood Assembly

1. 对于被选择的顶点序列，必须为其中的每个顶点构建一个感受野。创建感受野的算法首先调用邻域拼接算法来构建一个局部邻域，邻域内的顶点是感受野的候选顶点。

   给定顶点 和感受野的尺寸 ，邻域拼接算法首先执行广度优先搜索 BFS 来探索与顶点 距离依次增加的顶点，并将这些被探索到的顶点添加到集合 。如果收集到的顶点数量小于 ，则使用最近添加到 顶点的一阶邻居（即 BFS 过程），直到 中至少有 个顶点；或者没有更多的邻居顶点添加为止。注意，最终 的大小可能超过 。

2. Neighborhood Assembly 算法：

   • 算法输入：

     • 当前顶点
     • 感受野尺寸

   • 算法输出：顶点 的局部邻域

   • 算法步骤：

     • 初始化： ，其中 存放BFS 遍历到的顶点。

     • 迭代，直到 或者 停止迭代。迭代步骤：

       • 获取当前BFS 遍历顶点的一阶邻居：，其中 表示顶点 的一阶邻居集合。
       • 合并BFS 遍历到的顶点： 。
     • 返回 。

c. Graph Normalization

1. 子图归一化是对邻域子图的顶点施加一个顺序，使得顶点从无序的图空间映射到有序的、长度固定的顶点序列，从而为下一步的感受野创建做准备。

   子图归一化的基本思想是利用 graph labeling，对于不同子图中的顶点，当且仅当顶点在各自子图中的结构角色相似时，才给它们分配相似的位置。

   为了形式化该思想，我们定义了一个 Optimal Graph Normalization 问题，该问题的目标是找到给定的一组图的最佳 labeling 。

2. Optimal Graph Normalization 问题：令 为一组图，每个图包含 个顶点。令 为一个 graph labeling 过程。令 为 顶点图之间的距离函数，令 为 矩阵之间的距离函数。则我们的目标是寻找 ，使得：

   

   即：从 中随机均匀采样的两个子图，子图在排序空间的距离与图空间的距离的差距最小。这使得不同子图中结构相似的顶点映射到各子图中相近的顶点排名，从而实现不同子图的顶点对齐。

   图的最优归一化问题是经典的图规范化问题graph canonicalization problem 的推广。但是经典的labeling 算法仅针对同构图isomorphic graph 最佳，对于相似但是不同构的图可能效果不佳。这里相似度由 来衡量。

   • 图的同构问题是 NP 难的。在某些限制下，该问题是 P 的，如：图的degree 是有界的。图的规范化是对于图 ，用固定的顶点顺序来代表 的整个同构类。

   • 关于图的最优归一化问题，论文给出了两个定理：

     • 定理一：图的最优归一化问题是 NP 难的，证明见论文。

       因此PATCHY-SAN 无法完全解决图的最优归一化问题，它只是比较了不同的 graph labeling 方法，然后选择其中表现最好的那个。

     • 定理二：设 为一组图，令 是从 中独立随机均匀采样的一对图的序列。令：

       

       如果 ，则当且仅当 时有 。其中 表示采用不同的 graph labeling 。证明见论文。

       该定理使得我们通过比较估计量 来以无监督的方式比较不同的 graph labeling 。我们可以简单的选择使得 最小的graph labeling 。

       当我们在图上选择编辑距离edit distance、在矩阵 上选择汉明距离时，假设条件 成立。

       另外，上述结论不仅对无向图成立，对于有向图也成立。

3. 图的归一化问题，以及针对该问题的合适的graph labeling 方法是PATCHY-SAN 算法的核心。我们对顶点 的邻域子图进行归一化，并约束顶点的 label：任意两个其它顶点 ，如果 则 ，即距离 越近，排名越靠前。该约束保证了顶点 的排名总是1（即排名最靠前）。

   众所周知，对于有界degree 的图的同构问题可以在多项式时间求解，由于邻域子图的规模为 是一个常数，因此图的归一化算法可以在多项式时间内求解。我们的实验证明：图的邻域计算graph labeling 的过程仅产生一个微不足道的开销。

4. Graph Normalization 算法：

   • 算法输入：

     • 从原始图 得到的顶点子集 ，即邻域子集

     • 顶点

     • graph labeling 过程

     • 感受野尺寸

     • 输出：归一化的子图

     • 算法步骤：

       • 对 中的每个顶点，使用 计算这些顶点对 的排名，使得：

         

       • 如果 ，则根据 ranking 取 中的 top k 个顶点，对所选择的顶点再执行一次labeling 以及 ranking 的过程。

         这里必须使用 在筛选出的较小的顶点集合上重新计算，因为新的结构导致了新的 labeling 分布。

       • 如果 ，则：添加 个断开的虚拟顶点。

       • 根据这 个顶点的排名来归一化这些顶点，并返回归一化的结果。

5. 下图为对红色根节点 的邻域进行归一化过程，颜色表示到根节点的距离，感受野尺寸为 。首先利用graph labeling 对顶点进行排序，然后创建归一化的邻域。

   • 归一化还包括裁剪多余的顶点和填充虚拟顶点。
   • 顶点的不同属性对应于不同的输入通道。
   • 不仅可以针对顶点创建感受野，还可以针对边创建感受野，边的感受野尺寸为 ，边的不同属性对应不同的输入通道。

   

6. 创建感受野的 Create Receptive Field 算法：

   • 算法输入：

     • 顶点
     • 
     • 感受野大小

   • 算法输出：顶点 的感受野

   • 算法步骤：

     • 计算顶点 的邻域：
     • 归一化邻域子图：
     • 返回

d. CNN 等价性

1. 定理：在图像中得到的一个像素序列上应用 PATCHY-SAN ，其中感受野尺寸为 、步幅为 、非零填充以及采用 1-WL 归一化，则这等效于 CNN 的一个感受野大小为 、步幅为 、非零填充的卷积层。

   证明：如果输入图为一个正方形网格，则为顶点构造的 1-WL 归一化的感受野始终是具有唯一顶点顺序的正方形网格。

e. PATCHY-SAN 架构

1. PATCHY-SAN 既能处理顶点，也能处理边；它既能处理离散属性，也能处理连续属性。

2. PATCHY-SAN 对每个输入图 产生 个尺寸为 的归一化的感受野。假设 为顶点属性的数量、 为边属性的数量，则这将产生一个 的张量（顶点的感受野）以及一个 的张量（边的感受野）。这里 和 都是输入通道的数量。

   • 我们可以将这两个张量reshape 为一个 的张量和一个 的张量，然后对每个输入通道采用一个一维卷积层进行卷积。顶点产生的张量采用步幅 尺寸为 的卷积核，边产生的张量采用步幅 尺寸为 的卷积核 。
   • 剩下的结构可以任意结合 CNN 的组件。另外我们可以利用融合层来融合来自顶点的卷积输出feature map 核来自边的卷积输出 feature map 。

f. 算法复杂度

1. PATCHY-SAN 的创建感受野算法非常高效。另外，由于这些感受野的生成是相互独立的，因此感受野生成过程原生支持并行化。

2. 定理：令 为数据集中图的数量， 为感受野尺寸， 为宽度（每个图包含的感受野数量）。假设 为包含 个顶点、 条边的图的 graph labeling 过程的计算复杂度。则PATCHY-SAN 最坏情况下的计算复杂度为 。

   证明见论文。

   当采用Weisfeiler-Lehman 算法作为graph labeling 算法时，它的算法复杂度为 。考虑到 ，则PATCHY-SAN 的复杂度为 的线性、 的准线性、 的准线性。

7.2 实验

7.2.1 运行时分析

1. 论文通过将PATCHY-SAN 应用于实际的graph 来评估其计算效率，评估指标为感受野的生成速度。另外论文还给出了目前 CNN 模型

2. 数据集：所有输入图都来自 Python 模块 GRAPHTOOL 。

   • torus 图：具有10k 个顶点的周期性晶格。
   • random 图：具有10 个顶点的随机无向图，顶点的度的分布满足： ，以及 。
   • power 图：美国电网拓扑网络。
   • polbooks：2004年美国总统大选期间出版的有关美国政治书籍的 co-purchasing 网络。
   • preferential：一个 preferential attachment network，其中最新添加的顶点的degree 为 3 。
   • astro-ph：天体物理学 arxiv 上作者之间的 co-authorship 网络。
   • email-enron：一个由大约 50万 封已发送 email 生成的通信网络。

3. 我们的PATCHY-SAN 采用一维 Weisfeiler-Lehman:1-WL 算法来归一化邻域子图。下图给出了每个输入图每秒产生感受野的速度。所有实验都是在单台 2.8 GHZ GPU、64G 内存的机器上执行。

   • 对于感受野尺寸 ，除了在 email-eron 上的速度为 600/s 和 320/s 之外，在其它所有图上PATCHY-SAN 创建感受野的速度超过 1000/s 。
   • 对于最大的感受野尺寸 ，PATCHY-SAN 创建感受野的速度至少为 100/s 。

   对于一个经典的带两层卷积层、两层 dense 层的 CNN 网络，我们在相同机器上训练速度大概是 200-400 个样本/秒，因此PATCHY-SAN 感受野的生成速度使得下游 CNN 组件饱和。

   

7.2.2 可视化

1. 我们将 PATCHY-SAN 学到的尺寸为9 的归一化感受野使用 restricted boltzman machine:RBM 进行无监督学习，RNM 所学到的特征对应于重复出现的感受野模式。其中：

   • PATCHY-SAN 采用 1-WL 算法进行邻域子图归一化。
   • 采用单层RBM ，隐层包含 100 个隐单元。
   • RBM 采用对比散度算法contrastive divergence:CD 训练 30 个 epoch，学习率设为 0.01 。

   下图给出了从四张图中得到的样本和特征。我们将RBM 学到的特征权重可视化（像素颜色越深，则对应权重重大）。另外我们还采样了每种模式对应的三个顶点的归一化邻域子图，黄色顶点表示当且顶点（排序为1）。

   左上角为 torus 周期性晶格图，左下角为 preferential attachment 图、右上角为 co-purchasing 图、右下角为 随机图。

   

7.2.3 图分类

1. 图分类任务是将每个图划分到若干类别之一。我们采用6 个标准 benchmark 数据集来比较不同图分类模型的分类准确性和运行时间。

   • MUTAG 数据集：由188 种硝基化合物组成的数据集，其类别表明该化合物是否对细菌具有诱变 mutagenic 作用。
   • PTC 数据集：由 344 种化合物组成的数据集，其类别表明是否对老鼠具有致癌性。
   • NCI1 和 NCI109 数据集：筛选出的抑制 non-small 肺癌细胞和卵巢癌细胞活性的化合物。
   • PROTEIN：一个图的数据集，其中图的顶点表示二级结构元素 secondary structure element， 边表示氨基酸序列中的相邻关系，或者三维空间中的氨基酸相邻关系。其类别表示酶或者非酶。
   • D&D：由 1178 种蛋白质组成的数据集，其类别表明是酶还是非酶。

2. 我们将PATCHY-SAN 和一组核方法比较，包括shortest-path kernel:SP 、random walk kernel:RW、graphlet count kernel:GK，以及 Weisfeiler-Lehman sbutree kernel:WL 。

   • 对于核方法，我们使用 LIB-SVM 模型来训练和评估核方法的效果。我们使用10 折交叉验证，其中9-fold 用于训练，1-fold 用于测试。我们重复10 次并报告平均准确率和标准差。

     类似之前的工作，我们设置核方法的超参数为：

     • WL 的高度参数设置为2 。
     • GK 的尺寸参数设置为 7 。
     • RW 的衰减因子从 中进行挑选。

   • 对于 PATCHY-SAN:PSCN 方法，我们设置 为平均顶点数量、感受野尺寸分别为 和 。

     • 实验中我们仅使用顶点的属性，但是在 时我们实验了融合顶点的感受野和边的感受野，记作 。

     • 所有 PSCN 都使用了具有两个卷积层、一个dense 层、一个 softmax 层的网络结构。其中第一个卷积层有 16 个输出通道；第二个卷积层有 8 个输出通道，步长为1，核大小为 10；dense 层有 128 个隐单元，采用dropout = 0.5 的 dropout。我们采用一个较小的隐单元数量以及 dropout 从而避免模型在小数据集上过拟合。

       所有卷积层和 dense 层的激活函数都是 reLU 。 模型的优化算法为 RMSPROP 优化算法，并基于Keras 封装的 Theno 实现。

     • 所有 PSCN 需要优化的超参数为 epoch 数量以及 batch-size 。

     • 当 时，我们也对 PATCHY-SAN 抽取的感受野应用一个逻辑回归分类器 PSLR 。

   这些模型在 benchmark 数据集上的结果如下表所示。其中前三行给出了各数据集的属性，包括图的最大顶点数Max、图的平均顶点数Avg、图的数量Graphs 。我们忽略了 NCI109 的结果，因为它几乎和 NCI1 相同。

   • 尽管使用了非常普通的CNN 架构，PSCN 的准确率相比现有的graph kernel 方法具有很强的竞争力。在大多数情况下，采用 的 PSCN 具有最佳的分类准确性。
   • PSCN 这里的预测方差较大，这是因为：benchmark 数据集较小，另外 CNN 的一些超参数（epoch 和 batch-size 除外）没有针对具体的数据集进行优化。
   • PATCHY-SAN 的运行效率是graph kernel 中最高效的 WL 方法的2到8倍。
   • PATCHY-SAN + 逻辑回归的效果较差，这表明 PATCHY-SAN 更适合搭配 CNN 。CNN 学到了归一化感受野的非线性特征组合，并在不同感受野之间共享权重。
   • 采用中介中心性归一化 betweeness centrality normalization 结果也类似（未在表中体现），除了它的运行时间大约增加了 10% 。

   

3. 我们在较大的社交网络图数据集上使用相同的配置进行实验，其中每个数据集最多包含 12k 张图，每张图平均 400 个顶点。我们将 PATCHY-SAN 和之前报告的 graphlet count:GL、deep graplet count kernel:DGK 结果相比。

   我们使用归一化的顶点degree 作为顶点的属性，这突出了PATCHY-SAN 的优势之一：很容易的包含连续特征。

   可以看到 PSCN 在六个数据集的四个中明显优于其它两个核方法，并且在剩下两个数据集也取得了很好的性能。