Convolutional Kernel Networks for Graph-Structured Data笔记
这篇论文提出了一种结合图核和核方法的图神经网络（GCKN），用于解决图结构数据的分类问题。GCKN通过提取图中路径属性并将其映射到Hilbert空间，再利用Nyström方法进行端到端学习，能够在大规模数据上高效处理。实验结果表明，GCKN在多个数据集上表现优异，特别是在训练样本较少时，比现有的核方法和图神经网络结合的方法表现更好。该方法容易正则化，计算效率高，适合小样本数据的分类任务。
keywords: CKN, Nyström方法, RKHS, graph, kernel
作者: Dexiong Chen, Julien Mairal, Laurent Jacob
发表时间: 2020
方法: 与传统的CKN方法不同，该方法专为图结构数据设计，通过构建图核来建立核映射。与传统的CKN不同，该方法不仅关注核映射的构建，还特别针对图结构数据的特性进行了优化。与传统的CKN不同，该方法不仅关注核映射的构建，还特别针对图结构数据的特性进行了优化。与传统的CKN不同，该方法不仅关注核映射的构建，还特别针对图结构数据的特性进行了优化。
源代码: https://github.com/claying/GCKN
精读: 是的
结论: GCKN具有良好的正则化特性，能够很好地适配任务，且在分类数据集上的表现尤为出色，但相较于GNN，其计算复杂度更高。
实验: 图像分类
问题: 如何将图神经网络与核方法相结合，以解决图像分类这一具体任务
Summary
这篇论文专门针对图结构数据，提出了创新性的方法，该方法将GNN与核方法巧妙融合，命名为GCKN——Graph Convolutional Kernel Networks。论文还详细阐述了多层图核的概念，包括walks核、path核和WL子树核，基于这些核构建了GCKN模型。一方面，GCKN中的核函数提供了一种无监督、具有强表现力且易于规范化的数据表示方式，在训练样本数量有限的情况下表现出色；另一方面，该方法在大规模数据环境下实现了端到端的学习过程，从而开发出一种新型的图卷积神经网络。
Introduction & Related work
背景介绍：图核能够产出高质量的经验结果，然而数据表示与模型学习过程之间存在脱节现象。为了使图核生成适用于特定任务的数据表示，图神经网络应运而生。其架构基于图结构，相较于核方法，图神经网络的正则化难度显著增加。
GNN与核方法各自具有独特的特性，在图像建模领域，它们可以相互结合以解决相关问题，存在两种相对的结合方式。
有一类图神经网络(GNN)的输出结果位于Weisfeiler-Lehman核再生核希尔伯特空间(RKHS)中。这种基于核的GNN构建方法，其训练过程可被视为典型的神经网络训练。基于GNN架构设计一种新的核，等价于采用随机权重和预训练初始化策略的无限宽GNN结构。
还有其他方法：
- 通过图核所导出的度量来初始化GNN。
- 通过图核生成映射到神经网络的连续嵌入。
本研究阐述了一种显示多层核表示的方法，该方法可应用于传统的核方法。当数据量大时，可将其训练为GNN结构进行端到端学习。
Walks and Path kernels
当且仅当p和p’的属性相等时，σ的值为1；否则为0。k_base(u,u’)的作用是衡量两个不同图中属性相等的path数量。
延伸：两个图中长度到k的所有path的属性相等的数量
Walks kernel：把P替换成W
Weisfeiler-Lehman subtree kernels
WL子树核主要关注子树模式而非子树，这种核捕获子树模式，通过迭代聚合和散列每个节点邻居的属性来增加节点属性。
其中
属性a_i(u)捕获以节点u为根的深度为i的子树模式 。
Graph Convolutional Kernel Networks
图特征映射φ
φ将节点空间V映射至空间H，即为将V中的一个节点与H中的一个点相关联，其中H中的点代表局部图结构的信息。
特点：依赖于图G，可以看作是描述G中节点的空间H的|V|个元素的集合
核 与图G、G‘的映射φ、φ’联系起来的定义式：
其中
特征映射的单层网络构建
path kernel的连续性松弛
采用该核\boldsymbol{\kappa_1}来替代Dirac函数，基于连续性属性，从而实现路径间的不精确比较。
从图特征映射φ0到图特征映射φ1
φ0是从节点（边）映射到 在欧氏空间表示属性的H0。
相反地，\phi_1^{path}是基于高斯核\boldsymbol{\kappa_1}的核映射，通过核映射将边p映射到以φ0为中心的高斯函数。
主要步骤是从节点u中提取长度为k的路径，其中路径的颜色由红、蓝、绿三种颜色表示。在右侧面板上，通过高斯核映射将它们映射到RKHS\mathcal{H_{j+1}}。在节点u处，通过对其\mathcal{H_{j+1}}表示的局部路径进行聚合（池化）操作，可以得到新的映射\varphi_{j+1}。
在实际应用中，这种模型是通过使用有限维嵌入来逼近特征映射 实现的。
具体实现和GCKN
Nyström方法和单层模型
该方法是CKN模型的核心，它通过有限维的核近似嵌入实现对H空间的映射。其主要功能是将H空间映射到其有限维子空间中，从而实现对核近似嵌入的计算。这种映射关系赋予了该方法良好的可扩展性，使其能够处理不同维度的数据。
有限维映射\psi_1:V\to R^{q_1}；\psi'_1:V'\to R^{q_1}
\Phi_1的有限维近似 \Psi_1如下
- 使用核K1的有监督学习问题 可以通过最小化正则后的经验风险解决：
L被定义为凸损失函数；
通过Nyström方法对近似核函数\boldsymbol{\kappa_1}进行近似，能够生成一种新的图神经网络，由\Psi_1(G)表示。这种图神经网络的滤波器可以通过两种途径获得。
1. 通过无监督方式；
2. 在任务适配的情况下使用反向传播。Nyström方法通过将样本点嵌入到一个低维子空间中，并在该子空间上进行后续计算，从而实现了对原始数据的高效处理。子空间\mathcal{E}由\phi_1^{path}(z_1),…,\phi_1^{path}(z_{q_1})的线性组合构成。
解释为GNN
输入属性\psi_0(u)具有单元范数时，例如，在处理离散属性时，采用one-hot编码方法能够确保输入属性具有单位范数特性，而高斯核\boldsymbol{\kappa_1}的表达式则可以表示为
这是非线性函数σ1的点积核。
从映射\psi_0中构造\psi_1有以下4步：
矩阵Z是filter，大小为q0(k+1)×q1。
- 沿着路径进行特征的聚合。
- 对路径实施线性运算后，再进行点态到非线性编码。
- 乘以q×q的矩阵\sigma_1(Z^TZ)^{-1/2}，这种操作可以视为一种滤波操作。相较于传统GNN的主要区别在于，这里的滤波器本质上是基于矩阵在正交子空间上的映射实现的。
- 通过线性池化操作将路径信息进行整合。
基于Dirac函数构建的核，如path kernel和walks kernel，均为不可微的；相比之下，通过指数函数σ1构建的函数则是可微的。这种设计能够有效优化使用反向传播的filter Z。
无监督学习
- 使用Nyström方法，我们实现了对路径属性的提取和处理，通过从训练数据中获取路径属性并执行k-means算法，实现了对H空间的建模。
- 将H中的数据映射至有限维子空间，即通过k-means算法对路径属性进行聚合。
- 我们探索了一个与标签无关的良好核近似。
带反向传播的端到端学习
参数Z可以通过对Z和w的共同最小化（公式11）来实现端到端的学习过程。其主要特点在于，相比无监督学习策略，监督学习方法能够生成具有更少滤波器q₁的良好模型。
多层拓展
多层图像，最后的图表示
\Psi_J(G)的计算过程
附加层的两个可能的用途：
* 用于比路径更复杂的结构。
* 扩展表示的接受域，而不求助于长路径的列举。一个解释子树subtree的两层模型
path kernel无法有效表示复杂的结构。要表示更复杂的结构，必须突破公式(7)和公式(10)所限定的线性框架。相反，可以采用神经网络中的点对点的非线性连接方式。
通过第二层路径长度为k_2=0的设置，可以实现上述非线性结构。该层的特征映射\varphi_2由路径函数\phi_2^{path}(\varphi_1(u))生成，其中路径函数\phi_2^{path}是一个从空间\mathcal{H_1}到空间\mathcal{H_2}的非线性核映射。
将walk和WL子树 核通过论文的架构联系起来：
实际应用中的变体
不同k和不同尺寸的核求和
- 连接不同路径长度k的特征向量集合\Psi(G)。
- 在多层模型中，也可以将每一层j得到的特征表示进行融合，从而构建了图的多尺度特征表示，体现了图的表达能力。
齐次点积核的使用
把（9）的高斯核替换成齐次点积核
σ₁在公式（12）中被定义为某种特定的函数形式。当z和z’具有单位范数时，我们采用式（9）来计算高斯核。在论文中，我们采用齐次点积核来提升网络性能。此外，该核函数也可应用于不具备单位范数的连续属性。
其他池化操作
替换（13）和（14）中的求和池化为平均池化或最大池化。论文使用泛化的最大池化。
使用walk而不是path核
虽然失去一些表达能力，但是降低时间复杂度。
模型解释
寻找输入图G的子图，使其带有预测标签的互信息最大化。
解释GCKN-path和GCKN-subtree
GCKN-path：我们的模型单层\Psi_1。
GCKN-subtree：我们的模型两层\Psi_2且k_2=0。
在输入图G中，我们对一小部分路径进行分析，并保留预测信息。随后，我们通过整合筛选出的路径 来构建一个新的子图 。
- \hat{y}是G的预测label
- \mu是正则化参数，控制选择路径的数量
实验
- 模型：GCKN-walk、GCKN-path、两层模型GCKN-subtree、三层模型GCKN-3layers（k2=2,k3=0)
学习无监督模型
用 K-means 算法在每层的每次训练中提取 300,000 路径信息，生成的图表示基于均值进行标准化处理，并在配置为平方 hinge 损失的线性 SVM 分类器（11）中使用。采用 10 折交叉验证技术进行模型评估。超参数设置包括：高斯核的带宽参数、池化操作类型（13、14）、第一层路径大小 k1、滤波器数量以及（11）中的正则化参数 λ。
学习有监督模型
采用Adam优化器进行模型训练，设定初始学习率为0.01，每训练50个epoch后自动减半学习率，同时固定设置为32的小批量大小。基于无监督模型进行初始化，选择性能最优的模型结构，并将epoch数量作为重要的超参数参与优化过程。在超参数配置上，本方案未采用Dropout和批标准化技术。
有监督模型的filter比无监督模型少很多。32vs512
结果
带有分类节点标签的图像
数据集集合：包含四个生化数据集，具体为MUTAG、PROTEINS、PTC以及NCI1；同时包含三个社会网络数据集，分别为IMDB-B、IMDB-MULTI和COLLAB。
生化数据集：节点的度为标签。
GCKN-walk与图核、GNN之间存在微小的关联——两者都内在地依赖于walk这一概念——这可能源于高斯核所允许的软性结构差异。
GCKN-path通常会带来一些进一步的改进，这可以通过增加表达性来解释。
具有连续节点属性的图像
数据集：4个具有连续节点属性的现实世界图分类数据集，包括ENZYMES、PROTEINS full、BZR和COX2。以相同的超参数设置，进行了10次独立的10折交叉验证，这些设置参数达到了最佳的平均验证精度。