论文《Graph Neural Networks with convolutional ARMA filters》笔记
ARMA 2021 PAMI
ARMA 2021 PAMI
该研究发表于《PAMI》期刊于2021年。主要作者来自乌普萨拉大学 northern Lights 大学分校。
PAMI期刊介绍：其正式名称为IEEE Transactions on Pattern Analysis and Machine Intelligence（IEEE模式识别与机器智能汇刊）。该期刊具有较高的学术影响力，在计算机视觉领域处于顶级位置，并被CCF评为A类。
查询会议：
CCF deadline：https://ccfddl.github.io/
原文和开源代码链接：
0、核心内容
本文提出了一种新型的方法，在图卷积层中采用了**自回归滑动平均模型（Auto-Regression Moving Average, ARMA）**滤波器。
研究背景与动机
- 现有图神经网络通过执行卷积操作于图结构上，并多用于基于多项式的频域滤波过程。
- 研究表明该类滤波器存在局限性：对噪声具有敏感度较高的特点；难以有效反映整体图拓扑特征等。
ARMA滤波器的卷积层
-
开发出一种创新性设计的新型图卷积层，并基于ARMA滤波器进行优化，在性能上超越了传统多项式型滤波方法；该方法在频域响应上更具灵活性，在抗噪声能力方面表现更为突出，在捕捉整体拓扑特征方面也展现出更大的优势。
-
本研究系统性地阐述了基于ARMA滤波器的图神经网络架构，并详细说明了其计算方式；该方法不仅涵盖了递归和分布式表达形式，还显著提升了训练效率；节点的空间表示更加集中化；同时该模型在测试阶段适应不同结构的新图数据的能力也得到了明显提升。
理论分析
- 基于谱分析评估所设计的ARMA层的滤波性能。
- 论文进一步分析了ARMA滤波器与多项式滤波器之间的理论特性及其性能特征比较。
实验验证
- 开展了系统性实证研究，在四个关键研究领域：半监督节点分类问题、图信号分类任务、图结构化学习与关联预测相关的关键任务以及图回归问题上均进行了深入探讨。
- 实验结果表明，在各相关任务中对比于基于多项式滤波器的设计方案，ARMA层型的图神经网络展现出显著的优势。
方法细节
- 论文对ARMA滤波器的理论基础进行了深入阐述，并对其在图信号处理方面的应用进行了详细探讨。
- 该研究深入分析了ARMA滤波器的非线性特性和可训练性特征，并详细阐述了通过优化与任务相关的损失函数来实现参数学习的方法。
实验设置与结果
- 论文详细描述了实验的具体配置,涉及数据集的选择、模型架构的设计以及超参数的优化过程。
- 对实验结果进行了全面而详细的分析,并验证了ARMA层在多个应用场景中的有效性。
结论
论文归纳了ARMA层的关键成果，并详细阐述其在图机器学习领域中的卓越表现。
1、先验知识
① 什么是加权移动平均（weighted moving average）？
在图信号处理领域和GNN背景中，加权滑动平均是一种有效的平滑方法。
移动平均（Moving Average，MA）
- 滑动平均是一种广泛应用于信号处理领域的技术手段，在实际应用中能够有效降低数据的变化幅度并提取变化规律。
- 在图信号处理框架下进行研究时发现：通过计算每个节点及其邻居节点特征值的整体均值来实现对原始数据序列的有效降噪与去噪。
- 在最基本的情形下：每个节点的新特征向量由自身及其直接相连邻居节点的空间加权均值所构成。
加权移动平均（Weighted Moving Average，WMA）
- 加权移动平均是对传统移动平均的一种延伸，在这一方法中每个邻居节点的重要性均通过特定权重系数进行调整。这些权重则主要体现为节点间连接的重要程度或各节点特征间的相关性。
- 在图信号处理领域中其结果即为各节点自身及其邻接点特征值经过加权后的总和 该加权过程通常取决于图的拓扑结构（如边的强度或结点间的相似度）以及其他由学习算法得出的关键参数
2、从谱滤波器到多项式滤波器发展脉络
① 谱滤波器 ：在谱域内与非线性可训练滤波器实现卷积的GNN。
参考资料：
- Their work introduced Spectral Networks and Locally Connected Networks on Graphs, authored by Brunna in 2013.
- This paper introduced Deep Convolutional Networks on Graph-Structured Data, authored by Henaff in 2015.
根据需求对图信号的傅里叶系数进行压缩或扩展处理（其中每个节点特征的一个实例），随后将这些节点特征映射到一个新的空间中去
谱滤波器存在的问题：在实现时需要进行特征分解，计算代价很大。
② 多项式滤波器 ：图神经网络通过避免传统频谱分解和投影方法在频域计算高成本的开销，在节点域直接学习低阶多项式滤波器。
参考资料：
- Graph convolutional neural networks equipped with fast localized spectral filtering capabilities Deferrard et al., 2016
- Graph convolutional networks (GCN) Kipf et al., 2016
- Variational Graph Auto-Encoders Kipf et al., 2016
该多项式滤波器其脉冲响应具有有限性并能执行加权滑动平均滤波图信号于局部节点社区内使其能够在分布式架构中快速实现基于切比雪夫多项式以及Lanczos迭代算法的数据处理
多项式滤波器的频率响应（frequency response）：
多项式滤波器实现：
切比雪夫多项式滤波器实现：
GCN滤波器实现：
多项式滤波器具有局限性之一在于建模能力有限。受平滑特性的影响，在某些情况下无法捕捉到频率响应中的突变或剧烈变化。要实现对高阶邻域的有效处理，则必须依赖于更高阶次的多项式模型；然而这会显著增加计算复杂度，并可能导致模型在面对图信号或底层网络结构的变化时表现出不稳定性。（进一步说明：低阶多项式会导致过于光滑的结果从而忽视了重要的高频信息；而高阶多项式虽然能够捕捉复杂的邻域关系但其计算开销较大且容易过度拟合训练数据）
③ ARMA（自回归滑动平均滤波器） ：相较于具有相同参数数量的多项式滤波器，在频段分布上ARMA滤波器能提供更为丰富的频率响应特性，并在覆盖更高阶的空间领域方面展现出显著的优势。
参考资料：
- 《Development of graph filters and filterbanks》Tremblay 2018
- 《Signal processing methods for interpolation in graph structured data》Narang 2013
ARMA滤波器的频率响应：
ARMA滤波器的实现：
为了避免求逆，ARMA滤波器的近似实现（迭代方法）：
1阶ARMA滤波器的近似实现：
1阶ARMA滤波器的频率响应：
k阶ARMA滤波器的近似实现：
3、ARMA层及滤波器实现
1阶ARMA滤波器的实现 （本文最核心的公式，而且比较好理解）：
定理1证明了公式14可收敛的条件（可以先忽略proof部分）：
在实际实现ARMA算法过程中存在一些问题和挑战：
- 每个GCS堆栈k可能需要多样化的迭代次数T_k来收敛。这使得基于神经网络的实现变得更加复杂，并且其计算图是一个动态结构，在每一次权重矩阵更新时都会发生变化。
- 在反向传播训练过程中, 如果某个GCS堆栈k对应的迭代次数T_k很大, 则神经网络需重新构建计算图, 从而导致较高的计算代价以及可能出现的梯度消失问题。
解决方法：
- 参数W_k和V_k随机权重初始化。
- 固定收敛次数为常数T。
k阶ARMA滤波器的实现：
ARMA卷积层算法实现：
4、实验部分
节点分类任务的数据集和超参数：
节点分类任务实验结果：
5、核心卷积层源码
ARMA4NC类：
class ARMA4NC(nn.Module):
def __init__(self,
in_dim,
hid_dim,
out_dim,
num_stacks,
num_layers,
activation=None,
dropout=0.0):
super(ARMA4NC, self).__init__()
self.conv1 = ARMAConv(in_dim=in_dim,
out_dim=hid_dim,
num_stacks=num_stacks,
num_layers=num_layers,
activation=activation,
dropout=dropout)
self.conv2 = ARMAConv(in_dim=hid_dim,
out_dim=out_dim,
num_stacks=num_stacks,
num_layers=num_layers,
activation=activation,
dropout=dropout)
self.dropout = nn.Dropout(p=dropout)
def forward(self, g, feats):
feats = F.relu(self.conv1(g, feats))
feats = self.dropout(feats)
feats = self.conv2(g, feats)
return feats
Python
ARMA卷积层：
class ARMAConv(nn.Module):
def __init__(self,
in_dim,
out_dim,
num_stacks,
num_layers,
activation=None,
dropout=0.0,
bias=True):
super(ARMAConv, self).__init__()
self.in_dim = in_dim
self.out_dim = out_dim
self.K = num_stacks
self.T = num_layers
self.activation = activation
self.dropout = nn.Dropout(p=dropout)
# init weight
self.w_0 = nn.ModuleDict({
str(k): nn.Linear(in_dim, out_dim, bias=False) for k in range(self.K)
})
# deeper weight
self.w = nn.ModuleDict({
str(k): nn.Linear(out_dim, out_dim, bias=False) for k in range(self.K)
})
# v
self.v = nn.ModuleDict({
str(k): nn.Linear(in_dim, out_dim, bias=False) for k in range(self.K)
})
# bias
if bias:
self.bias = nn.Parameter(torch.Tensor(self.K, self.T, 1, self.out_dim))
else:
self.register_parameter('bias', None)
self.reset_parameters()
def reset_parameters(self):
for k in range(self.K):
glorot(self.w_0[str(k)].weight)
glorot(self.w[str(k)].weight)
glorot(self.v[str(k)].weight)
zeros(self.bias)
def forward(self, g, feats):
with g.local_scope():
init_feats = feats
# assume that the graphs are undirected and graph.in_degrees() is the same as graph.out_degrees()
degs = g.in_degrees().float().clamp(min=1)
norm = torch.pow(degs, -0.5).to(feats.device).unsqueeze(1)
output = None
for k in range(self.K):
feats = init_feats
for t in range(self.T):
feats = feats * norm
g.ndata['h'] = feats
g.update_all(fn.copy_u('h', 'm'), fn.sum('m', 'h'))
feats = g.ndata.pop('h')
feats = feats * norm
if t == 0:
feats = self.w_0[str(k)](feats)
else:
feats = self.w[str(k)](feats)
feats += self.dropout(self.v[str(k)](init_feats))
feats += self.v[str(k)](self.dropout(init_feats))
if self.bias is not None:
feats += self.bias[k][t]
if self.activation is not None:
feats = self.activation(feats)
if output is None:
output = feats
else:
output += feats
return output / self.K
Python
6、心得&代码复现
通过阅读本文可以获得许多宝贵的经验与见解；其中介绍的方法也非常有趣，并且建议读者花时间深入学习。然而，在理论内容上可能会感到有些晦涩难懂，并特别强调了算法实现部分的挑战性。
实验部分我自己复现的结果：
| Cora | Citeseer | Pubmed | Film | Squirrel | Chameleon | Texas | Cornell | Wisconsin | |
|---|---|---|---|---|---|---|---|---|---|
| GCN | 81.90% | 71.80% | 79.10% | 23.36% | 34.49% | 51.97% | 54.05% | 54.05% | 64.71% |
| H2GCN | 74.20% | 59.80% | 76.60% | 25.72% | 38.04% | 52.63% | 72.97% | 48.65% | 74.51% |
| ARMA（dgl版） | 80.80% | 71.20% | 78.50% | 33.30% | 31.50% | 53.40% | 70.27% | 59.46% | 79.80% |
在原先的研究中，并未涉及异构图的实验测试，在本次研究中则增加了6组异构图的数据测试。ARMA算法通过在异构图上的应用取得了显著的效果提升。