【宾夕法尼亚博士论文】大规模图机器学习，179页pdf

2022 年 11 月 20 日 专知

图神经网络(GNNs)成功地从大多数类型的网络数据学习表示，但在大型图的情况下受到限制。挑战出现在学习架构的设计本身，因为大多数GNN是由图的一些矩阵表示(例如，邻接矩阵)参数化的，当网络很大时，这可能很难获得。此外，在许多GNN架构中，图操作是通过谱域中的卷积操作来定义的。在这种情况下，另一个障碍是图谱的获得，这需要代价高昂的矩阵特征分解。

然而，从共享结构属性的意义上来说，大型图通常可以被识别为彼此相似。因此，我们可以预期，处理这些图上支持的数据应该会产生类似的结果，这将减轻大尺寸的挑战，因为我们可以为小图设计GNN，并将它们转移到更大的图上。在这篇论文中，我将这种直觉形式化，并表明当这些图属于同一个“族”时，这种图的可移植性是可能的，其中每个族由不同的图元标识。

graphon是一个函数W(x,y)，它描述了一类具有相似形状的随机图。我们可以将参数(x,y)看作是一对节点的标签，以及图元值W(x,y)作为x和y之间一条边的概率的标签。这产生了一个从图元采样的图的概念，或者，等价地，一个随着采样图中节点数量增长的极限的概念。从一个graphon上采样的图形几乎肯定在极限上具有相同的属性，例如同态密度，这在实践中意味着，graphon识别的网络家族在某种意义上是相似的，某些“motifs”的密度是保持不变的。这激发了对图上的信息处理的研究，作为在大型图上进行信息处理的一种方法。

信号处理理论的核心部分是一个移位的概念，它引入了一类具有傅立叶变换(FT)特征的光谱表示的线性滤波器。本文表明，graphon诱导了一个线性算子，可用于定义移位，从而定义graphon滤波器和graphon FT。基于图序列和相关图信号的收敛性质，可以证明对于这些序列，图FT收敛到graphon FT，图滤波器的输出收敛到具有相同系数的graphon滤波器的输出。这些定理表明，对于属于某些族的图，图傅里叶分析和图滤波器设计具有明确的限制。反过来，这些事实使具有大量节点的图上的图信息处理成为可能，因为为极限图设计的信息处理管道可以应用于有限图。

我们通过组合具有点非线性的graphon滤波器组来进一步定义graphon神经网络(WNNs)。WNNs是理想的极限，在实际中并不存在，但它们是理解GNNs基本性质的有用工具。特别是，graphon滤波器的采样和收敛结果可以很容易地扩展到WNNs，从而表明当图收敛到graphon时，GNN收敛到WNNs。如果两个GNN可以任意接近同一个WNN，那么通过一个简单的三角形不等式参数，它们也可以任意接近彼此。这个结果证实了我们的直觉，即GNN可以在相似的图之间转移。一个GNN可以在中等规模的图上训练，并在一个可转移性误差主要为最小图的大小的倒数的大尺度图上执行。有趣的是，这种误差随着卷积滤波器光谱响应的可变性而增加，揭示了从图滤波器继承来的可转移性和光谱鉴别性之间的权衡。在实践中，由于非线性，这种权衡在GNN中很少出现，它能够将数据的光谱成分分散到特征值谱的不同部分，在那里它们可以被区分。这解释了为什么GNN比图过滤器更可转移。