Adaptive Graph Convolutional Neural Networks
自适应图卷积神经网络（AGCN）通过构建独有图拉普拉斯矩阵和学习距离度量，解决了传统图卷积神经网络（GCN）在处理不同图结构和大小时的局限性。论文提出了一种自适应图拉普拉斯层（SGC-LL），能够学习图的几何性质并更新图拓扑结构，从而适应特定任务的需求。此外，网络还引入了自适应图卷积模块、图最大池化层和图收集层，能够处理不同图结构的数据，并通过双边卷积核和BN层进一步提升性能。该方法在图卷积网络中首次实现了对不同图结构和大小的灵活适应，为图学习任务提供了新的解决方案。
Adaptive Graph Convolutional Neural Networks
-
- Introduction
-
- Method
- 2.1 SGC-LL Layer
-
学习图的Laplacian矩阵
-
训练图更新的度量指标
-
特征转换的重参数化过程
-
残差图的Laplacian矩阵
-
2.2 AGCN网络
-
- Graph Max Pooling层
- Graph Gather层
- 双边卷积核
- 网络配置
- 不同图的batch训练
-
1、Introduction
前人工作的不足之处：
- 早期图CNN的局限性：其处理数据的维度较低，导致卷积核的局部性过强，难以从复杂图结构中提取多层次的表示信息。
- 当前图CNN存在的主要缺陷在于：其无法充分挖掘图数据的几何特性，因为现有设计难以构建适应不同节点邻居数量的参数化空间核。此外，由于图数据的灵活性和参数规模，为每个独特图定制专门的空间核结构是不现实的。
- 共享卷积核的方法：为了确保各层输出的统一维度，必须对输入进行调整。然而，这种对图数据的预处理处理可能会导致信息的丢失。
- 输入数据的处理方式：图CNN接受的数据要么具有固有的图结构，要么需要通过聚类方法构建。在传统图CNN模型中，图结构在整个训练过程中是固定的。然而，评估通过无监督聚类（或领域知识）获得的图结构是否最适合监督学习任务仍然存在挑战。尽管已有研究提出利用全连接网络进行监督图构建，但其密集的训练权重限制了模型只能处理小型图。此外，独立网络学习得到的图结构也不一定是最优的，无法确保最适合图卷积任务。
本文图CNN的创新点：
- 生成独特的图Laplacian矩阵 ：在每个样本中构建并学习其独有的残差Laplacian矩阵，这些矩阵将被加到初始图中（包括聚类结果图或固有图）。
- 优化数据共享的最优距离度量参数 ：通过学习数据共享的最优距离度量参数，随着预测网络的训练，拓扑结构被更新。该过程具有O(d^2)的复杂度且与图尺寸无关。
- 卷积操作中的特征嵌入 ：在卷积操作中，首先处理类内和类间结点特征，完成结点特征的转换。
- 支持多样化的图输入 ：该网络支持多样化的图结构和大小输入，显著提升了图的表示能力。
2、Method
2.1\ SGC-LL\ Layer
为使谱卷积核在不同图拓扑中真正可行，本文对距离度量进行参数化处理，使得图Laplacian函数本身能够实现可训练性。通过训练后的度量参数，动态构建不同形状和大小的输入样本图。在此基础上，设计了一种新型的层，即基于自适应图构建的K-局域卷积核，用于执行卷积操作。同时，对样本的图拓扑结构进行持续更新，以最小化训练损失。通过上述方法，实现了具有图Laplacian学习能力的谱图卷积层，命名为SGC-LL。本节将详细阐述SGC-LL层的核心创新点。
1.学习图Laplacian
谱卷积核的k阶多项式
该限制降低了卷积核的灵活性。
可能有两个主要原因：其一是网络结构的复杂性。其二是特征之间的关系。
- 图是基于特征提取和转换之前的原始特征域构建的。
- 图的拓扑结构是固有的，它仅表示物理连接关系，如分子中的化学键网络。
为了突破现有限制，我们提出一种新的谱核方法，通过参数化Laplacian矩阵L来替代系数。对于原始Laplacian矩阵L，其特征向量X和参数向量\Gamma，函数F(L,X,\Gamma)则输出参数化后的L矩阵的频谱，卷积核表示为：
最后，SGC-LL层表示为：
用切比雪夫展开 来计算k阶多项式T_{k}(\tilde{L})X .
2.训练图更新的度量
在图结构数据中，不适合使用欧式距离。为了适应不同任务需求，这里的距离度量需要根据任务特征和数据属性动态调整。在度量学习领域，算法主要分为有监督学习和无监督学习两种类型。无监督方法所得的最优度量能够有效缩小类内距离，同时最大化不同类别之间的距离。对于有监督学习场景，目标是找到能够最小化损失函数的度量。
在此时，广义的Mahalanobis距离正式提出。其中，x_i和x_j之间的广义Mahalanobis距离度量为：
当M=I时，该方法退化为欧式距离。在本文模型中，M=W_{d}{W^{T}}_{d}表示一个对称且半正定的矩阵，其中，W_d是SGC-LL层中一个可训练的权重参数（SGC-LL层共有三个可训练权重参数：M(W_d)和W_b，它们分别代表SGC-LL层中的两个可训练权重参数，通过计算距离值来生成高斯核。具体而言，M(W_d)和W_b分别对应SGC-LL层中的两个可训练权重参数，其中M(W_d)主要负责将距离转换为可以计算欧式距离的空间，而W_b则用于辅助高斯核的生成。在计算高斯核时，我们通过计算距离值来生成高斯核，从而实现空间变换。
对G进行归一化处理后，\tilde{A}生成了密集型[邻接矩阵]。在模型构建中，通过最优度量\tilde{W}_d，我们能够构建最优的图Laplacian集合\tilde{L}，从而最小化预测损失。
3.特征转换重参数化
在SGC-LL层中，通过转换矩阵和转置向量作用于输出特征，实现了类内与类间结点特征映射的建立。输出特征经过重参数化处理，其表达形式被重新定义为：
总体而言，就每个SGC-LL层而言，参数集{(M_i,W_i,b_i)}所具有的计算复杂度为O(d_id_{i-1})，这一复杂度与图的大小和度数无关。在随后的SGC-LL层中，谱卷积核将通过在另一特征域上建立新的度量来实现信息的传播。
4. 残差图Laplacian
大部分数据不具备天然的图结构特征，在进行网络处理前，需要对每个数据样本构建相应的图结构。通常采用无监督学习方法来构建这些图结构，但这种构建方式无法有效地表达特定任务所需的所有重要拓扑特征。
在缺乏距离度量先验知识的情况下，M的随机初始化可能导致收敛速度较慢。为了加快训练进程并提升所学习图结构的稳定性，本文提出合理假设，认为最优图的Laplacian矩阵\tilde{L}是基于原始矩阵L的一个微小调整。
另一种表述是：图L已经包含了丰富的图结构信息，但未包含由虚拟节点连接形成的子结构，这些虚拟连接无法直接从原图中提取特征。因此，本文专注于研究残差图的Laplacian性质，其中L_res被定义为L(M_i,X)，其中i表示第i个样本。算法1详细描述了完整的操作流程。
2.2 AGCN网络
该网络命名为自适应图卷积网络（AGCN），该命名基于其SGC-LL层的特性，该层能够根据数据和学习任务的上下文有效地学习自适应图拓扑结构。除了该层之外，该网络还包含Graph\ Max\ Pooling层和Graph\ Gather层。
Graph Max Pooling层
对于图神经网络中的池化操作，节点特征x_v经过pooling后，其第j维特征值将被替换成其自身及其邻居节点在该维度上的最大值。其中，N(v)表示节点v的相邻节点，经过池化操作后，节点v的新特征向量为：
Graph Gather层
图形收集层通过逐个元素汇总所有顶点特征向量来表示数据。该层的输出向量可用于graph-level预测任务。即使没有图收集层，仍可训练AGCN模型用于vertex-wise预测任务，该任务基于给定顶点上的标签。逐点预测涵盖了图完成以及社交网络中的多种预测任务。
双边卷积核
主要目的是防止过拟合现象。通过增强L的空间局部性，可以改善SGC-LL的激活特性，同时，通过引入BN层，可以进一步提升训练效率。
网络配置
AGCN由多个连续的组合层构成，其中的核心层是SGC-LL。每个组合层由一个SGC-LL层、一个BN层和一个Graph Max Pooling层组成。残差图Laplacian在每个SGC-LL层中被独立训练，以适应当前图的局部特征。在Max Pooling过程中，通过不断更新残差图，使得每个SGC-LL层能够适应新的图结构特征。经过一个组合层，图的结构被更新，但图的大小保持不变。任何粗燥化或特征平均操作都会破坏图中局部结构的完整性，因此在Max Pooling过程中保留所有节点信息。测试任务为图级别的预测问题。
不同图的batch训练
将卷积应用到图结构数据中将面临一个主要障碍，即如何处理不同局部拓扑结构。