自适应通用广义 PageRank 图神经网络

摘要

在许多重要的图数据处理应用中，获取的信息包括节点特征和图拓扑的观察。 图神经网络（GNN）旨在利用这两种证据来源，但它们并没有以最佳方式权衡其效用并以通用的方式整合它们。 这里，普遍性是指对同质或异质图假设的独立性。 我们通过引入一种新的广义 PageRank (GPR) GNN 架构来解决这些问题，该架构自适应地学习 GPR 权重，从而联合优化节点特征和拓扑信息提取，无论节点标签同质或异质的程度如何。 学习到的 GPR 权重会自动调整到节点标签模式，与初始化类型无关，从而保证通常难以处理的标签模式的出色学习性能。 此外，它们还可以避免特征过度平滑，这一过程使特征信息变得无差别，而不需要网络变浅。 由所谓的上下文随机块模型生成的新颖的综合基准数据集促进了我们对 GPR-GNN 方法的伴随理论分析。 我们还使用众所周知的基准同质和异质数据集，将我们的 GNN 架构与几种最先进的 GNN 在节点分类问题上的性能进行了比较。 结果表明，与现有技术相比，GPR-GNN 在合成数据和基准数据上都提供了显着的性能改进。 我们的实现可在线获取。

1简介

近年来，以图为中心的机器学习受到了广泛关注，这是因为图结构数据无处不在，而且它在解决半监督节点分类和图分类等众多实际问题方面具有重要意义（Zhu，2005；Shervashidze 等人，2011；Lü & Zhou，2011）。 通常，手头的数据包含两个信息源：节点特征和图拓扑。 例如，在社交网络中，节点代表具有由其相应特征向量捕获的不同兴趣和属性组合的用户；另一方面，边记录了可观察的友谊和协作关系，这些关系可能取决于也可能不取决于节点特征。 因此，非常需要能够同时自适应地利用节点特征和图拓扑的学习方法，因为它们利用它们的潜在连接，从而改进图的学习。

图神经网络 (GNN) 在解决上述应用领域时利用其表征能力提供最先进的性能。 许多 GNN 使用消息传递（Gilmer 等人，2017；Battaglia 等人，2018） 来操纵节点特征和图拓扑。 它们是通过堆叠（图）神经网络层构建的，这些神经网络层本质上是在给定的图拓扑上传播和转换节点特征。 不同类型的层已经被提出并在实践中使用，包括图卷积层（GCN）（Bruna等人，2014；Kipf＆Welling，2017），图注意力层（GAT）（ Velickovic 等人, 2018) 和许多其他人(Hamilton 等人, 2017; Wijesinghe & Wang, 2019; Zeng 等人, 2020; Abu-El-Haija 等人, 2019)。

然而，大多数现有的 GNN 架构都有两个根本弱点，限制了它们对一般图结构数据的学习能力。 首先，它们中的大多数似乎都是为同质（关联）图而量身定制的。 节点分类上下文中的同质原则（McPherson等人，2001）断言来自同一类的节点倾向于形成边。 同质性也是图聚类中的常见假设（Von Luxburg，2007；Tsourakakis，2015；Dau & Milenkovic，2017）和许多 GNN 设计（Klicpera 等人，2018）。 为同亲图开发的方法是非通用的，因为它们无法正确解决异亲（不协调）图的学习问题 （Pei 等人，2019；Bojchevski 等人，2019；2020）. 在异性图中，具有不同标签的节点更有可能连接在一起（例如，许多人倾向于在约会图中优先与异性连接，不同类别的氨基酸更有可能在许多蛋白质结构中连接（朱等人，2020）等）。 GNN 通过聚合图邻域内的节点特征来建模同质原理。 为此，他们使用不同的机制，例如在每个网络层中进行平均。 邻域聚合是有问题的，并且对于异嗜图来说要困难得多（Jia & Benson，2020）。

其次，大多数现有的 GNN 都不够“深度”。 尽管原则上可以堆叠任意数量的层，但实际模型通常是浅层的（包括 $2$-$4$ 层），因为已知这些架构比深层网络能够实现更好的经验性能。 随着深度的增加，GNN 性能下降，一个广为接受的解释是 特征过度平滑，可以直观地解释如下。 GNN 特征传播的过程代表了“特征图”上的一种随机游走形式，在适当的条件下，这种随机游走以指数速率收敛到其驻点。 这本质上平衡了特征的表达能力并使它们具有非歧视性。 这种直观推理首先在 Li 等人 (2018) 中针对线性设置进行了描述，最近在 Oono & Suzuki (2020) 中针对涉及非线性整流器的设置进行了研究。

我们通过在名为 GPR-GNN 的新模型中将 GNN 与通用 PageRank 技术 (GPR) 相结合来解决这两个弱点。 GPR-GNN 架构旨在首先学习隐藏特征，然后通过 GPR 技术传播它们。 网络的核心组件是 GPR 过程，它将特征传播的每个步骤与 可学习的重量。 权重取决于信息传播过程中不同步骤的贡献，可以是正值，也可以是负值。 这偏离了常见的非负性假设（Klicpera等人，2018）允许权重的符号适应基础图的同质/异质结构。 权重的幅值权衡节点特征的平滑程度和拓扑特征的聚合能力。 这些特征不会随着初始化过程的选择而改变，并阐明了用于组合节点特征和图结构的过程，以实现（接近）最优的预测。 总之，GPR-GNN 方法可以同时学习不同类图的节点标签模式并防止特征过度平滑。

GPR-GNN 的优异性能在现实世界数据集上得到了实证证明，并通过许多理论研究结果得到了进一步支持。 在后一种设置中，我们表明探地雷达过程与一般多项式图滤波相关，它可以自然地处理图信号的高频部分和低频部分。 相比之下，最近使用具有固定权重的个性化PageRank（PPR）的GNN模型（Wu等人，2019；Klicpera等人，2018；2019）不可避免地充当低通滤波器。 因此，他们无法学习异性图的标签。 我们还证明，即使在大步传播之后（即在大量传播步骤之后），GPR-GNN 也可以以自适应方式缓解特征过度平滑问题。 因此，该方法能够利用信息丰富的大步传播。

为了测试 GPR-GNN 在同质和异质节点标签模式上的性能并确定节点和拓扑特征探索之间的权衡，我们首先描述最近提出的上下文随机块模型（cSBM）（Deshpande等人，2018）。 cSBM 允许平滑地控制节点特征和图拓扑之间的“信息比率”，其中图可以从高度同质到高度异质变化。 我们表明，在 cSBM 上从强同质到强异质的半监督节点分类任务中，GPR-GNN 的表现优于所有其他基线方法。 然后，我们继续证明 GPR-GNN 在包含同质图和异质图的节点分类基准真实世界数据集上提供了最先进的性能。 由于篇幅限制，我们将所有证明、形式定理陈述和结论部分放在补充中。

2 预赛

令 $G=(V,E)$ 为具有节点 $V$ 和边 $E$ 的无向图。让 $n$ 表示节点数，假设属于 $C\ge 2$ 类之一。 节点与节点特征矩阵 $𝐗\in {ℝ}^{n\times f},$ 相关联，其中 $f$ 表示每个节点的特征数量。 在整篇论文中，我们使用 ${𝐗}_{}$我: 分别表示矩阵$𝐗$的$i^{\text{th}}$行和${𝐗}_{:j}$表示$j^{\text{th}}$列。 符号 ${\delta }_{ij}$ 是为 Kronecker delta 函数保留的。 图$G$由邻接矩阵$𝐀$描述，而$\widetilde{𝐀}$代表添加了自循环的图的邻接矩阵。 我们令$\widetilde{𝐃}$为$\widetilde{𝐀}$的对角度矩阵，${\widetilde{𝐀}}_{\text{sym}}={\widetilde{𝐃}}^{-1/2}\widetilde{𝐀}{\widetilde{𝐃}}^{-1/2}$表示具有自环的对称归一化邻接矩阵。

(a)我们提出的 GPR-GNN 模型的图示。

(b)科拉，$\mathscr{H}(G)=0.825$

(c) 德克萨斯州，$\mathscr{H}(G)=0.057$

图1： (a) 隐藏状态特征提取由神经网络使用通过 GPR 传播的各个节点特征来执行。 请注意，神经网络的 GPR 权重 ${\gamma }_k$ 和参数集 $\{\theta \}$ 都是以端到端方式同时学习的（如红色所示）。 (b)-(c) GPR-GNN 在现实世界数据集上学习到的 GPR 权重。 Cora 是同质性的，而 Texas 是异质性的（这里，$\mathscr{H}$ 代表下面定义的同质性水平）。 可以观察到一个有趣的趋势：对于异嗜性情况，权重从正到负交替，并具有衰减幅度（更多示例在第 5 节中提供）。 阴影区域对应于$95\%$置信区间。

3 GPR-GNN：动机和贡献

广义 PageRank。 广义 PageRank (GPR) 方法首先在无监督图聚类的背景下使用，与个性化 PageRank 相比，它们表现出显着的性能改进（Kloumann 等人，2017；Li 等人，2019）。 探地雷达的工作原理可以简洁地描述如下。 给定图中某个簇中的种子节点 $s\in V$，根据以下公式初始化一维特征向量 ${𝐇}^{(0)}\in {ℝ}^{n\times 1}$ ${𝐇}_{}^{}$v:(0)=δvs. GPR 得分定义为 ${\sum }_{k=0}^{\mathrm{\infty }}{\gamma }_k{\widetilde{𝐀}}_{\text{sym}}^k{𝐇}^{(0)}={\sum }_{k=0}^{\mathrm{\infty }}{\gamma }_k{𝐇}^{(k)}$，其中参数 ${\gamma }_k\in ℝ,k=0,1,2,\mathrm{\dots }$ 称为 GPR 权重。 通过对 GPR 分数进行阈值化，在本地执行图的聚类。 某些 PangRank 方法，例如个性化 PageRank 或热内核 PageRank （Chung，2007），与 GPR 权重的特定选择相关联（Li 等人，2019）。 有关 PageRank 方法的精彩深入讨论，感兴趣的读者可以参考（Gleich，2015）。 Li 等人 (2019) 的工作最近介绍并理论上分析了一种特殊形式的探地雷达，称为逆 PR (IPR)，并表明长随机游走路径更有利于如果正确选择了 GPR 权重，则可以进行先前假设的聚类（请注意，IPR 是针对同性图开发的，目前尚不清楚异性图的最佳 GPR 权重）。

探地雷达方法和多项式图过滤的等价性。 如果我们将 GPR 定义中的无限和截断为某个自然数 $K$，则 ${\sum }_{k=0}^K{\gamma }_k{\widetilde{𝐀}}_{\text{sym}}^k$ 对应于阶数为 $K$ 的多项式图滤波器。因此，学习最优 GPR 权重相当于学习最优多项式图滤波器。 请注意，我们可以使用多项式图过滤器（Shuman等人，2013）来近似任何图过滤器，因此GPR方法能够处理大量不同的节点标签模式。 此外，增加 $K$ 可以更好地近似底层最佳图形过滤器。 这再次表明大步长传播是有益的。

节点标签模式的普遍性：同质与异质。 Pei 等人 (2019) 在他们最近的工作中提出了一个指标来衡量图中节点的同质性水平$\mathscr{H}(G)=\frac{1}{|V|}{\sum }_{v\in V}\frac{\text{Number of neighbors of}v\in V\text{that have the same label as}v}{\text{Number of neighbors of}v}$。请注意，$\mathscr{H}(G)\to 1$ 对应于强同质性，而 $\mathscr{H}(G)\to 0$ 表示强异质性。 图 1 (b) 和 (c) 绘制了我们的 GPR-GNN 方法在同性 (Cora) 和异性 (Texas) 数据集上学习到的 GPR 权重。 从 Cora 中学习到的 GPR 权重与 IPR (Li 等人, 2019) 的行为相匹配，这验证了大步传播对于同亲图确实非常重要。 从德克萨斯州学到的 GPR 权重的表现与所有已知的 PR 变体显着不同，具有许多负值。 这些权重模式的差异是在随机初始化下观察到的，表明权重实际上是由网络学习的，而不是由特定初始化强制的。 此外，这两个图模型的 GPR 权重的巨大差异说明了 GPR-GNN 的学习能力及其普遍适应性。

过度平滑问题。 大多数 GNN 模型的关键组件之一是图卷积层，描述为

${𝐇}_{\text{GCN}}^{(k)}=\text{ReLU}\left({\widetilde{𝐀}}_{\text{sym}}{𝐇}_{\text{GCN}}^{(k-1)}{𝐖}^{(k)}\right),{\widehat{𝐏}}_{\text{GCN}}=\text{softmax}\left({\widetilde{𝐀}}_{\text{sym}}{𝐇}_{\text{GCN}}^{(K-1)}{𝐖}^{(k)}\right),$

其中 ${𝐇}_{\text{GCN}}^{(0)}=𝐗$ 和 ${𝐖}^{(k)}$ 表示 $k^{\text{th}}$ 层的可训练权重矩阵。 限制多层堆叠的关键问题是过度平滑现象：如果要删除上面表达式中的 ReLU，则 ${lim}_{k\to \mathrm{\infty }}{\widetilde{𝐀}}_{\text{sym}}^k{𝐇}^{(0)}={𝐇}^{(\mathrm{\infty })},$ 其中 ${𝐇}^{(\mathrm{\infty })}$ 的每一行> 仅取决于相应节点的度，前提是该图是不可约且非周期的。 这表明随着层数的增加，模型会丢失节点特征提供的判别信息。

使用 GPR-GNN 模型缓解图异质性和过度平滑问题。 GPR-GNN 首先提取每个节点的隐藏状态特征，然后使用 GPR 传播它们。 GPR-GNN 过程可以在数学上描述为：

$\widehat{𝐏}=\text{softmax}(𝐙),𝐙={\displaystyle \sum _{k=0}^K}{\gamma }_k{𝐇}^{(k)},{𝐇}^{(k)}={\widetilde{𝐀}}_{\text{sym}}{𝐇}^{(k-1)},{𝐇}_{i:}^{(0)}=f_{\theta }({𝐗}_{i:}),$ (1)

其中$f_{\theta }(.)$ 表示具有参数集 $\{\theta \}$ 的神经网络，可生成隐藏状态特征 ${𝐇}^{(0)}$。 GPR 权重 ${\gamma }_k$ 与 $\{\theta \}$ 以端到端方式一起训练。 GPR-GNN 模型很容易解释：正如已经指出的，GPR-GNN 具有自适应控制每个传播步骤的贡献并将其调整为节点标签模式的能力。 检查学习到的 GPR 权重还有助于阐明图的拓扑信息的属性（即确定最佳多项式图滤波器），如图 1 (b) 和 (c) 所示。

将 GPR-GNN 置于相关先前工作的背景下。 在与重复堆叠 GCN 层不同的方法中，APPNP (Klicpera 等人, 2018) 代表了与我们的 GPR-GNN 方法相关的最先进的 GNN 之一。 很容易看出，APPNP 和 SGC (Wu 等人，2019) 是我们模型的特例，因为 APPNP 修复了 ${\gamma }_k=\alpha {(1-\alpha )}^k$、${\gamma }_K={(1-\alpha )}^K,$，而SGC 分别用 ${\gamma }_k={\delta }_{kK}$ 消除所有非线性。 这两个权重选择对应于个性化 PageRank (PPR)(Jeh & Widom, 2003)，众所周知，当应用于同亲节点分类时，与 IPR 框架相比，其不是最优的(Li 等人，2019）。 固定 GPR 权重使得模型无法自适应地学习最优传播规则，这一点至关重要：正如我们将在第 4 节中展示的，固定的 PPR 权重对应于低通图滤波器，这使得它们不足以学习异嗜图。 最近的工作（Klicpera等人，2018）表明固定PPR权重（APPNP）也可以证明解决过度平滑问题。 然而，APPNP防止过度平滑的方式与节点标签信息无关。 相比之下，GPR-GNN 避免过度平滑是由节点标签信息引导的（定理 4.2)。 对这一现象的详细讨论以及说明性例子委托给了补充材料。

在类 GCN 模型中，JK-Net (Xu 等人, 2018) 与 GPR-GNN 表现出一些相似之处。 它还聚合不同 GCN 层的输出以得出最终输出。 另一方面，GCN-Cheby 方法(Defferrard 等人, 2016; Kipf & Welling, 2017) 与多项式图过滤相关，其中每个卷积层传播多个步骤，图过滤器相关为切比雪夫多项式。 在这两种情况下，模型的深度在实践中都受到限制（Klicpera等人，2018）并且它们不容易解释为我们的GPR-GNN方法。 一些先前的工作还强调自适应学习不同步骤的重要性（Abu-El-Haija 等人，2018；Berberidis 等人，2018）。 然而，上述工作均不适用于 GNN 的半监督学习并考虑异嗜图。

4 GPR-GNN 的理论特性

GPR-GNN 的图过滤方面。 正如3节中提到的，网络的GPR组件可以被视为多项式图滤波器。 令${\widetilde{𝐀}}_{\text{sym}}=𝐔𝚲{𝐔}^T$为${\widetilde{𝐀}}_{\text{sym}}$的特征值分解。 然后，相应的多项式图过滤器等于${\sum }_{k=0}^K{\gamma }_k{\widetilde{𝐀}}_{\text{sym}}^k=𝐔g_{\gamma ,K}(𝚲){𝐔}^T$，其中$g_{\gamma ,K}(𝚲)$按元素应用，$g_{\gamma ,K}(\lambda )={\sum }_{k=0}^K{\gamma }_k{\lambda }^k$。 我们得出以下结果。

Theorem 4.1 （非正式）.

假设图$G$是连通的。 如果${\gamma }_k\mathrm{\ge }\mathrm{0}\mathit{}\mathrm{\forall }k\mathrm{\in }\mathrm{\{}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{,}\mathrm{\dots }\mathrm{,}K\mathrm{\}}$、${\mathrm{\sum }}_{k\mathrm{=}\mathrm{0}}^K{\gamma }_k\mathrm{=}\mathrm{1}$和$\mathrm{\exists }{k}^{\mathrm{\prime }}\mathrm{>}\mathrm{0}$使得${\gamma }_{k^{\mathrm{\prime }}}\mathrm{>}\mathrm{0}$，则$g_{\gamma \mathrm{,}K}\mathit{}\mathrm{(}\mathrm{\cdot }\mathrm{)}$是低通图滤波器。 此外，如果 ${\gamma }_k\mathrm{=}{\mathrm{(}\mathrm{-}\alpha \mathrm{)}}^k\mathrm{,}\alpha \mathrm{\in }\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{)}$ 和 $K$ 足够大，则 $g_{\gamma \mathrm{,}K}\mathit{}\mathrm{(}\mathrm{\cdot }\mathrm{)}$ 是高通图滤波器。

根据定理4.1以及我们在3节中的讨论，我们知道APPNP和SGC都会不可避免地抑制高频分量。 因此，它们不足以用于异嗜图。 相反，如果允许 ${\gamma }_k$ 为负并自适应学习，图滤波器将通过相关的高频。 这就是 GPR-GNN 在异性图上表现异常出色的原因（见图 1)。

GPR-GNN 可以避免过度平滑。 正如已经强调的，GPR-GNN 方法的一项关键创新是使 GPR 权重自适应可学习，这使得 GPR-GNN 能够避免过度平滑并交换节点和拓扑特征信息。 直观上，当大步传播没有好处时，它会增加训练损失。 因此，相应的探地雷达权重应该在幅度上衰减。 这一观察结果由以下结果体现，由于篇幅限制，其更正式的陈述和证明委托给补充材料。

Theorem 4.2 （非正式）.

假设图 $G$ 已连接，并且训练集包含每个类的节点。 还假设 $k^{\mathrm{\prime }}$ 足够大，以便 ${𝐇}^{\mathrm{(}k\mathrm{)}}\mathrm{,}\mathrm{\forall }k\mathrm{\ge }{k}^{\mathrm{\prime }}$ 发生过度平滑效应，这主导了对最终输出 $𝐙$ 的贡献。 那么，对于所有$k\mathrm{\ge }{k}^{\mathrm{\prime }}$,${\gamma }_k$ 和${\gamma }_k$ 的梯度符号相同。

定理4.2表明，只要发生过度平滑，当我们使用这样的优化器时，对于所有$k\ge k^{\prime }$,$|{\gamma }_k|$都会接近$0$作为随机梯度下降（SGD），它具有合适的学习率衰减。 这减少了相应步骤${𝐇}^{(k)}$在最终输出$𝐙$中的贡献。 当权重$|{\gamma }_k|$足够小，使得${𝐇}^{(k)}$不再主导最终输出$𝐙$的值时，过度平滑效应就会被消除。

5 新 cSBM 合成数据集和真实数据集的结果

综合数据。 为了测试 GNN 在具有任意同质和异质水平的图上的标签学习能力，我们建议使用 cSBM （Deshpande 等人，2018） 来生成合成图。 我们考虑两个大小相等的类的情况。 在 cSBM 中，节点特征是高斯随机向量，其中高斯的均值取决于社区分配。 均值的差异由参数$\mu$控制，而社区内和社区之间的边缘密度的差异由参数$\lambda$控制。 因此 $\mu$ 和 $\lambda$ 分别捕获节点特征和图拓扑的“相对信息性”。 此外，正${\lambda }^{\prime }$对应同性图，负${\lambda }^{\prime }$对应异性图。 Deshpande 等人 (2018) 描述了 cSBM 重建的信息论限制。 结果表明，渐进地需要${\lambda }^2+{\mu }^2/\xi >1$来保证误分类节点与节点总数的消失率，其中$\xi =n/f$和$f$与之前一样表示节点特征向量的维度。

请注意，给定公差值$ϵ>0$,${\lambda }^2+{\mu }^2/\xi =1+ϵ$是椭圆体的弧，其中$\lambda \ge 0$和$\mu \ge 0$。 为了公平、持续地控制节点特征和图拓扑所承载的信息范围，我们引入了参数$\varphi =\arctan (\frac{\lambda \sqrt{\xi }}{\mu })\times \frac{2}{\pi }$。 设置$\varphi =0$表示仅节点特征提供信息，而$|\varphi |=1$表示仅图拓扑提供信息。 此外，$\varphi =1$对应于强同性图，而$\varphi =-1$对应于强异性图。 请注意，值 $\varphi$ 和 $-\varphi$ 传达有关图拓扑的相同数量的信息。 这是由于${\lambda }^2={(-\lambda )}^2$。 理想情况下，能够在同性图和异性图上进行最佳学习的 GNN 对于 $\varphi$ 和 $-\varphi$ 应该具有相似的性能。 由于篇幅限制，我们建议感兴趣的读者参考（Deshpande等人，2018）来回顾所有正式的理论结果，并仅概述我们分析所需的cSBM属性。 补充材料中还提供了更多信息。

我们的实验设置检查了传导设置中的半监督节点分类任务。 我们考虑两种不同的选择，将随机分割为训练/验证/测试样本，分别称为稀疏分割($2.5\%/2.5\%/95\%$)和密集分割($60\%/20\%/20\%$)。 稀疏 splittnig 更类似于 Kipf & Welling (2017) 中考虑的原始半监督设置，而密集设置则在 Pei 等人 (2019) 中考虑进行研究异嗜图。 我们使用多个随机分割和不同的初始化来运行每个实验 $100$ 次。

用于比较的方法。 我们将 GPR-GNN 与 $6$ 基线模型进行比较：MLP、GCN (Kipf & Welling, 2017)、GAT (Velickovic 等人, 2018)、 JK-Net (Xu 等人, 2018)、GCN-Cheby (Defferrard 等人, 2016)、APPNP (Klicpera 等人, 2018)、SGC (Wu 等人, 2019)、SAGE (Hamilton 等人, 2017) 和 Geom-GCN (Pei 等人, 2019)。 对于所有架构，我们使用相应的 Pytorch Geometric 库实现（Fey & Lenssen，2019）。 对于Geom-GCN，我们直接使用作者提供的代码。 由于预处理子例程未公开，我们无法在 cSBM 和其他最初在论文中测试的数据集上测试 Geom-GCN （Pei 等人，2019）。

GPR-GNN 模型设置和超参数调整。 我们选择带有 $K=10$ 的随机游走路径长度，并使用带有 $64$ 隐藏单元的 $2$ 层（MLP）作为神经网络组件。 对于 GPR 权重，我们使用不同的初始化，包括带有 $\alpha \in \{0.1,0.2,0.5,0.9\}$、${\gamma }_k={\delta }_{0k}$ 或 ${\delta }_{Kk}$ 的 PPR 以及 pytorch 中的默认随机初始化。 类似地，对于 APPNP，我们在 $\{0.1,0.2,0.5,0.9\}$ 内搜索最佳 $\alpha$。 对于其他超参数调整，我们优化了所有模型的学习率 $\{0.002,0.01,0.05\}$ 和权重衰减 $\{0.0,0.0005\}$。 对于 Geom-GCN，我们对每个数据集使用原始论文中的最佳变体。 最后，我们使用 GPR-GNN(rand) 来描述 GPR 权重随机初始化所获得的结果。 补充材料中讨论了进一步的实验设置。

结果。 我们使用 cSBM 生成的数据和 $\varphi \in \{-1,-0.75,-0.5,\mathrm{\dots },1\}$ 检查所有基线方法和 GPR-GNN 的稳健性，其中包括跨异质/同质频谱的图表。 结果总结在图2中。 对于稀疏和密集设置，每当 （异嗜图）时，GPR-GNN 都显着优于所有其他基线模型。 另一方面，当图信息较弱时($\varphi =0,-0.25$)，所有基线 GNN 都可能比简单的 MLP 更差。 这表明现有的 GNN 无法应用于任意图，而 GPR-GNN 显然更加鲁棒。 APPNP 方法在强异嗜图上的性能最差。 这与定理 4.1 的结果一致，该定理断言 APPNP 本质上充当低通滤波器，因此不适用于强异性设置。 JKNet、GCN-Cheby 和 SAGE 是仅有的三个能够在密集分裂下学习强异亲图的基线模型。 这也是意料之中的，因为 JKNet 是唯一一个结合了最后一层不同步骤结果的基线模型，这与 GPR-GNN 中的做法类似。 GCN-Cheby 在每一层中使用多个步骤，这使得它能够部分适应异嗜性设置，因为每一层都与比 GCN 更高阶的多项式图滤波器相关。 SAGE 以不同的方式对待自我嵌入和来自相邻节点的嵌入，而不是简单地对它们进行平均。 这使得 SAGE 能够适应异性情况，因为自我嵌入可以防止节点被邻居的信息淹没。 尽管如此，JKNet、GCN-Cheby 和 SAGE 的实践并不深入。

图2： cSBM 上测试模型的准确性。 误差线表示$95\%$置信区间。

此外，JKNet 在稀疏分裂模型下无法学习，而 GCN-Cheby 和 SAGE 在图信息较强时($|\varphi |\ge 0.5$)也无法在稀疏分裂模型下很好地学习。

此外，我们观察到 GPR 权重的随机初始化只会导致密集分裂下轻微的性能下降。 对于稀疏分割设置，下降更为明显，但对于强异嗜图，我们的方法仍然大大优于基线模型。 这也是意料之中的，因为我们在稀疏分割设置中拥有较少的标签信息，而良好的 GPR 初始化提供的隐式偏差是有帮助的。 由于标签信息足够丰富，隐式偏差与密集分割设置无关。

GPR-GNN 除了强大的性能之外，另一个好处是它的可解释性。 在图 3 中，我们展示了通过随机初始化的 cSBM 上的 GPR-GNN 学习到的 GPR 权重。 当图是弱同性($\varphi =0.25$)时，学习到的 GPR 权重正在减少。 这与 APPNP 中使用的 PPR 权重类似，尽管衰减速度不同。 当图具有强同性($\varphi =0.75$)时，学习到的 GPR 权重会增加，这与 PPR 权重显着不同。 这一结果与 Li 等人 (2019) 中的最新发现相匹配，并且与作者提出的知识产权相似。 另一方面，当图是异性的时，学习到的 GPR 权重具有锯齿形状。 这再次验证了定理 4.1，因为具有交替符号的 GPR 权重对应于高通滤波器。 有趣的是，当 $\varphi =-0.25$ 时，学习到的 GPR 权重的大小正在减小。 这是因为在这种情况下图信息较弱而节点特征信息更重要。 学习到的 GPR 权重集中在前几步是有道理的。 因此，我们验证了 GPR-GNN 的可解释性。 在实践中，人们可以使用学习到的 GPR 权重来更好地理解手头的图结构化数据。 我们在现实世界基准数据集的结果中展示了这一优势。

(a) $\varphi =0.25$、

($\mathscr{H}(G)=0.673$)

(b) $\varphi =0.75$、

($\mathscr{H}(G)=0.928$)

(c) $\varphi =-0.25$、

($\mathscr{H}(G)=0.328$)

(d) $\varphi =-0.75$、

($\mathscr{H}(G)=0.073$)

图3： 图 (a)-(d) 显示了 GPR-GNN 学习到的 GPR 权重，在 cSBM 上随机初始化，密集分割。 阴影区域表示$95\%$置信区间。

真实世界基准数据集。 我们使用 Pytorch Geometric 库中提供的$5$同质基准数据集，包括引用图 Cora、CiteSeer、PubMed （Sen 等人，2008；Yang 等人，2016） 和亚马逊共同购买图表计算机和照片（McAuley 等人，2015；Shchur 等人，2018）。 我们还使用 Pei 等人 (2019) 中测试的 $5$ 异性基准数据集，包括维基百科图 Chameleon 和 Squirrel (Rozemberczki 等人, 2021)，演员共现图，以及来自 WebKB。 我们在表1中总结了数据集统计数据。

表格1： 基准数据集属性和统计数据。

Dataset	Cora	Citeseer	PubMed	Computers	Photo	Chameleon	Squirrel	Actor	Texas	Cornell
Classes	7	6	5	10	8	5	5	5	5	5
Features	1433	3703	500	767	745	2325	2089	932	1703	1703
Nodes	2708	3327	19717	13752	7650	2277	5201	7600	183	183
Edges	5278	4552	44324	245861	119081	31371	198353	26659	279	277
$\mathscr{H}(G)$	0.825	0.718	0.792	0.802	0.849	0.247	0.217	0.215	0.057	0.301

真实世界数据集的结果。

表2： 真实世界基准数据集的结果：平均准确度 ($\%$) $\pm$ $95\%$ 置信区间。 粗体字母用于标记最佳结果，而带下划线的粗体字母表示最佳结果给定置信区间内的结果。

	Cora	Citeseer	PubMed	Computers	Photo	Chameleon	Actor	Squirrel	Texas	Cornell
GPRGNN	79.51$\mathrm{\pm }$0.36	67.63$\pm$0.38	85.07$\mathrm{\pm }$0.09	82.90$\mathrm{\pm }$0.37	91.93$\mathrm{\pm }$0.26	67.48$\mathrm{\pm }$0.40	39.30$\mathrm{\pm }$0.27	49.93$\mathrm{\pm }$0.53	92.92$\mathrm{\pm }$0.61	91.36$\mathrm{\pm }$0.70
APPNP	79.41$\mathrm{\pm }$0.38	68.59$\mathrm{\pm }$0.30	85.02$\mathrm{\pm }$0.09	81.99$\pm$0.26	91.11$\pm$0.26	51.91$\pm$0.56	38.86$\pm$0.24	34.77$\pm$0.34	91.18$\pm$0.70	91.80$\mathrm{\pm }$0.63
MLP	50.34$\pm$0.48	52.88$\pm$0.51	80.57$\pm$0.12	70.48$\pm$0.28	78.69$\pm$0.30	46.72$\pm$0.46	38.58$\pm$0.25	31.28$\pm$0.27	92.26$\pm$0.71	91.36$\mathrm{\pm }$0.70
SGC	70.81$\pm$0.67	58.98$\pm$0.47	82.09$\pm$0.11	76.27$\pm$0.36	83.80$\pm$0.46	63.02$\pm$0.43	29.39$\pm$0.20	43.14$\pm$0.28	55.18$\pm$1.17	47.80$\pm$1.50
GCN	75.21$\pm$0.38	67.30$\pm$0.35	84.27$\pm$0.01	82.52$\pm$0.32	90.54$\pm$0.21	60.96$\pm$0.78	30.59$\pm$0.23	45.66$\pm$0.39	75.16$\pm$0.96	66.72$\pm$1.37
GAT	76.70$\pm$0.42	67.20$\pm$0.46	83.28$\pm$0.12	81.95$\pm$0.38	90.09$\pm$0.27	63.9$\pm$0.46	35.98$\pm$0.23	42.72$\pm$0.33	78.87$\pm$0.86	76.00$\pm$1.01
SAGE	70.89$\pm$0.54	61.52$\pm$0.44	81.30$\pm$0.10	83.11$\mathrm{\pm }$0.23	90.51$\pm$0.25	62.15$\pm$0.42	36.37$\pm$0.21	41.26$\pm$0.26	79.03$\pm$1.20	71.41$\pm$1.24
JKNet	73.22$\pm$0.64	60.85$\pm$0.76	82.91$\pm$0.11	77.80$\pm$0.97	87.70$\pm$0.70	62.92$\pm$0.49	33.41$\pm$0.25	44.72$\pm$0.48	75.53$\pm$1.16	66.73$\pm$1.73
GCN-Cheby	71.39$\pm$0.51	65.67$\pm$0.38	83.83$\pm$0.12	82.41$\pm$0.28	90.09$\pm$0.28	59.96$\pm$0.51	38.02$\pm$0.23	40.67$\pm$0.31	86.08$\pm$0.96	85.33$\pm$1.04
GeomGCN	20.37$\pm$1.13	20.30$\pm$0.90	58.20$\pm$1.23	NA	NA	61.06$\pm$0.49	31.81$\pm$0.24	38.28$\pm$0.27	58.56$\pm$1.77	55.59$\pm$1.59

我们使用准确性（micro-F1 分数）以及 $95\%$ 置信区间作为评估指标。 相关结果总结于表2中。 对于同质数据集，我们提供了稀疏分割的结果，这与 Kipf & Welling (2017) 中使用的原始设置更加一致； Shchur 等人 (2018). 对于异性数据集，我们采用Pei等人(2019)中使用的密集分裂。

表2显示，总的来说，GPR-GNN 优于所有测试方法。 在同质数据集上，GPR-GNN 实现了最先进的性能。 在异质数据集上，GPR-GNN 显着优于所有其他基线模型。 需要指出的是，在异嗜性数据集中观察到两种不同的模式。 在 Chameleon 和 Squirrel 上，MLP 和 APPNP 的表现比其他基线方法（例如 GCN 和 JKNet）更差。 相比之下，MLP 和 APPNP 在 Actor、Texas 和 Cornell 上的表现优于其他基线方法。 我们推测这是由于图拓扑信息分别强和弱造成的。 请注意，这两种模式分别与 $\varphi$ 接近 $-1$ 和 $0$ 的 cSBM 实验结果相匹配（图 2) 。 此外，Pei等人(2019)提出的同质性度量$\mathscr{H}(G)$无法表征异质数据集中的这种差异。 我们将对该主题的更详细讨论以及说明性示例放在补充中。为了公平起见，我们还使用密集分割在同质数据集上重复了涉及 GeomGCN 的实验 - 观察到的性能模式往往是相似的，这可以在补充中找到。

(a) 考研

(b)照片

(c)演员

(d)松鼠

(e) 纪元$=0$

(f) 纪元$=50$

(g) 纪元$=100$

(h) 纪元$=150$

图4： 图 (a)-(d) 显示了我们的 GPR-GNN 方法学习到的 GPR 权重，并在各种数据集上随机初始化，以进行密集分割。 图 (e)-(f) 显示了我们的 GPR-GNN 方法的学习权重，在 cSBM$(\varphi =-1)$ 上初始化 ${\delta }_{kK}$，用于密集分裂。 阴影区域表示$95\%$置信区间。

我们还在图 4 中检查了真实数据集上学习到的 GPR 权重。 由于篇幅限制，对其他数据集进行更全面的 GPR 权重分析将推迟到补编中。 我们可以看到，学习到的 GPR 权重对于同质数据集（PubMed 和 Photo）都是正值。 相反，从异性数据集（Actor 和 Squirrel）学习到的一些 GPR 权重是负的。 这些结果与 cSBM 上观察到的模式一致。 有趣的是，学习到的权重 ${\gamma }_0$ 对于 Actor 数据集具有最大的量级。 这表明大部分信息都包含在节点特征中。 从表2中我们还可以看到MLP确实优于大多数基线GNN（这与cSBM$(\varphi =-0.25)$的情况类似）。 另一方面，从 Squirrel 学到的 GPR 权重具有锯齿形图案。 这意味着与 Actor 相比，Squirrel 的图拓扑信息更丰富。 从表2中我们还看到基线 GNN 在 Squirrel 上也优于 MLP。

摆脱学习 GPR 权重的过度平滑和动态。 为了证明 GPR-GNN 避免过度平滑的能力，我们选择初始 GPR 权重为 ${\gamma }_k={\delta }_{kK}$。 这确保了在学习过程的一开始就很可能出现过度平滑效果。 在具有密集分割的 cSBM$(\varphi =-1)$ 上，我们发现对于 $100$ 次运行中的 $96$ 次运行，GPR-GNN 在 epoch $0$，这意味着过度平滑确实立即发生。 最终预测的准确度是$98.79\%$，远高于$50.07\%$在时期$0$的初始准确度。 对于其他数据集也可以观察到类似的结果，这验证了我们的理论发现。 我们在图4(e)-(h)中绘制了学习到的 GPR 权重的动态，这表明最后一步的峰值确实减少了，而其他步骤的 GPR 权重在幅度上显着增加。 有关学习 GPR 权重的动态的更多结果可以在补充中找到。

表3： 所选真实世界基准数据集的效率：每个周期的平均运行时间（毫秒）/平均总运行时间。 请注意，Geom-GCN 需要预处理过程，因此我们不将其包含在表中。 由于篇幅限制，所有基准数据集的完整效率表位于补充材料中。

	Cora	Pubmed	Computers	Chameleon	Actor	Squirrel	Texas
GPRGNN	17.62ms / 3.74s	20.19ms / 5.53s	39.93ms / 11.40s	16.74ms / 3.40s	19.31ms / 4.49s	25.28ms / 5.12s	17.56ms / 3.55s
APPNP	17.16ms / 4.00s	18.47ms / 6.29s	39.59ms / 20.00s	17.01ms / 3.44s	16.32ms / 4.04s	22.93ms / 4.63s	15.96ms / 3.24s
MLP	4.14ms / 0.92s	5.43ms / 2.86s	5.33ms / 2.77s	3.41ms / 0.69s	4.84ms / 0.98s	5.19ms / 1.05s	3.81ms / 1.04s
SGC	3.31ms / 3.31s	3.81ms / 3.81s	4.36ms / 4.36s	3.13ms / 3.13s	3.98ms / 1.00s	4.79ms / 4.79s	2.86ms / 2.09s
GCN	9.25ms / 1.97s	14.11ms / 4.17s	32.45ms / 16.29s	13.83ms / 2.79s	12.39ms / 2.50s	27.11ms / 5.56s	10.22ms / 2.06s
GAT	14.78ms / 3.42s	21.52ms / 6.70s	61.45ms / 24.28s	16.63ms / 3.63s	18.91ms / 3.86s	47.46ms / 10.05s	15.50ms / 3.13s
SAGE	12.06ms / 2.44s	28.82ms / 6.32s	171.36ms / 71.94s	64.43ms / 13.02s	27.95ms / 5.65s	343.47ms / 69.38s	6.08ms / 1.28s
JKNet	18.97ms / 4.41s	24.48ms / 6.61s	35.02ms / 14.96s	20.03ms / 5.15s	23.52ms / 4.75s	29.89ms / 6.67s	19.67ms / 4.01s
GCN-cheby	22.96ms / 4.75s	45.76ms / 12.02s	218.82ms / 96.58s	89.41ms / 18.06s	43.94ms / 8.88s	440.55ms / 88.99s	12.34ms / 3.08s

效率分析。 我们还检查了 GPR-GNN 与其他基线模型相比的计算复杂性。 我们在表 3 中报告了经验训练时间。 与 APPNP 相比，我们只需要为 GPR-GNN 学习 $K+1$ 个额外的 GPR 权重，通常是 $K\le 20$ （即我们在实验中选择 $K=10$)。 这些额外的计算主要由神经网络模块 $f_{\theta }$ 执行的计算主导。 从表3中我们可以观察到，GPR-GNN 的运行时间确实与 APPNP 相似。 然而值得指出的是，Bojchevski 等人 (2020) 的作者成功地扩展了 APPNP 以在大型图上运行。 是否可以使用相同的技术来扩展 GPR-GNN 是一个有趣的悬而未决的问题。

6 结论

我们解决了现有 GNN 的两个基本弱点：无法泛化到异嗜图并利用大量传播步骤，从而无法充当通用学习者。 我们开发了一种新颖的 GPR-GNN 架构，它将自适应广义 PageRank (GPR) 方案与 GNN 相结合。 我们从理论上证明，我们的方法不仅可以减轻特征过度平滑，而且还适用于高度多样化的节点标签模式。 我们还在同性和异性节点标签模式上测试了 GPR-GNN，并提出了一种由上下文随机块模型生成的新颖的综合基准数据集。 我们对现实世界基准数据集的实验表明，GPR-GNN 相对于最先进的方法有明显的性能提升。 此外，我们表明 GPR-GNN 具有独立兴趣的理想可解释性。

致谢

这项工作得到了 NSF 信息科学新兴前沿拨款 0939370 和 NSF CIF 1618366 拨款的部分支持。 作者感谢 Mohamad Bairakdar 对本文早期版本的有益评论。

附录A附录

A.1关于防止过度平滑的详细讨论。

正如 4 节中提到的，另一种方法 - APPNP - 也可以证明可以防止过度平滑 Klicpera 等人 (2018)。 本研究的作者利用了 PPR 传播将收敛于 ${𝚷}_{\text{ppr}}{𝐇}^{(0)}$ 的事实，其中 ${𝚷}_{\text{ppr}}=\alpha {({𝐈}_n-(1-\alpha ){\widetilde{𝐀}}_{\text{sym}})}^{-1}$ 独立于训练数据中提供的节点标签信息。 ${𝚷}_{\text{ppr}}{𝐇}^{(0)}$ 的每一行仍然依赖于 ${𝐇}^{(0)}$，因此 APPNP 不会受到过度平滑的影响。 但是，由于 ${𝚷}_{\text{ppr}}$ 独立于标签信息，因此它可能会导致我们在下面讨论的不良后果。

(a) 图表$G$。

(b) 标签分配的一个示例。

(c) 标签分配的另一个示例。

图5： 一个简单的例子演示了 GPR-GNN 如何避免过度平滑。

让我们考虑一个如图 5 所示的简单示例，涉及一个连通无向图 $G=(V,E)$（图 5 (a)）。 考虑图 5 (b) 和图 5 (c) 中所示的两种不同的节点标签分配。 显然，图5（b）和（c）中描述的图拓扑是相同的，唯一的区别是类标签分配。 在图5（b）中，图是同质的，因此最佳图滤波器应该强调图信号的低频部分。 相反，在图5（c）中，该图是异性的，因为该图相对于标签是二分的。 因此，最佳的图滤波器应该强调图信号的高频部分。 此示例说明最佳图过滤器应取决于图拓扑和节点标签信息。 回想一下，APPNP 在渐进机制中使用的等效图过滤器是 ${𝚷}_{\text{ppr}}$，它独立于节点标签信息。 此外，定理 4.1 确定 APPNP 本质上利用低通滤波器。 相比之下，GPR-GNN 学习由节点标签信息引导的 GPR 权重，这使得它能够解释所示的两种情况（同性和异性）。

A.2 同质性测度不足的讨论$\mathscr{H}(G)$

(a)情况 1。

(b)情况 2。

图6： 一个简单的例子来解释同质性测度$\mathscr{H}(G)$的不足。

正如5节中提到的，同质性度量$\mathscr{H}(G)$不足以表征异亲图拓扑是否提供信息。 考虑图 6 中描述的两个简单示例，其中节点的颜色表示它们的标签。 在情况 1 中，蓝色和绿色节点链接到所有橙色和紫色节点。 在情况 2 中，蓝色节点仅链接到橙色节点，绿色节点仅链接到紫色节点。 从$\mathscr{H}(G)$的定义可以看出，这两种情况都有$\mathscr{H}(G)=0$，因为在这两种情况下，节点都不会链接到同一标签的其他节点。 然而，很明显，与情况 1 相比，情况 2 中的图拓扑携带了更多的节点标签信息。 事实上，对于情况 1，仅从图拓扑中无法区分蓝色和绿色节点（橙色和紫色节点也是如此）。 同质性度量的一种可能替代方案是经验边缘概率矩阵 $𝐁$ 的 Chernoff-Hellinger 散度 Abbe (2017)；这里 ${𝐁}_{ij}$ 是一条边的经验概率，其中一个末端节点标记为 $i$，另一个末端节点标记为 $j$。 我们的建议背后的直觉在于 Chernoff-Hellinger 散度表征了 SBM 的基本极限。 然而，由于许多实际的图生成过程可能与 SBM 显着不同，因此研究替代同质/异质度量是另一个有趣的开放问题。

A.3 定理证明4.1

我们首先陈述定理4.1的正式版本。

Theorem A.1 （定理 4.1 的正式版本）。

假设图 $G$ 已连接。 令 ${\lambda }_{\mathrm{1}}\mathrm{\ge }{\lambda }_{\mathrm{2}}\mathrm{\ge }\mathrm{\dots }\mathrm{\ge }{\lambda }_n$ 为 ${\stackrel{\mathrm{~}}{𝐀}}_{\text{𝑠𝑦𝑚}}$ 的特征值。 如果${\gamma }_k\mathrm{\ge }\mathrm{0}\mathit{}\mathrm{\forall }k\mathrm{\in }\mathrm{\{}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{,}\mathrm{\dots }\mathrm{,}K\mathrm{\}}$、${\mathrm{\sum }}_{k\mathrm{=}\mathrm{0}}^K{\gamma }_k\mathrm{=}\mathrm{1}$和$\mathrm{\exists }{k}^{\mathrm{\prime }}\mathrm{>}\mathrm{0}$使得${\gamma }_{k^{\mathrm{\prime }}}\mathrm{>}\mathrm{0}$，则。 另外，如果 ${\gamma }_k\mathrm{=}{\mathrm{(}\mathrm{-}\alpha \mathrm{)}}^k\mathrm{,}\alpha \mathrm{\in }\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{)}$ 和 $K\mathrm{\to }\mathrm{\infty }$，则 $\mathrm{|}{\lim }_{K\mathrm{\to }\mathrm{\infty }}{g}_{\gamma \mathrm{,}K}\mathit{}\mathrm{(}{\lambda }_i\mathrm{)}\mathrm{/}{\lim }_{K\mathrm{\to }\mathrm{\infty }}{g}_{\gamma \mathrm{,}K}\mathit{}\mathrm{(}{\lambda }_{\mathrm{1}}\mathrm{)}\mathrm{|}\mathrm{>}\mathrm{1}\mathit{}\mathrm{\forall }i\mathrm{\ge }\mathrm{2}$。

请注意， 意味着在应用图形过滤器$g_{\gamma ,K}$ 后，最低频率分量（对应于${\lambda }_1$)进一步占主导地位。 回想一下，在未过滤的情况下，我们不与 ${\widetilde{𝐀}}_{\text{sym}}$ 相乘。 它也可以被视为乘以单位矩阵$I$，其中特征值比为$\frac{{|{\lambda }_i|}^0}{{|{\lambda }_1|}^0}=1$。 因此，在这种情况下 $g_{\gamma ,K}$ 的作用就像一个低通滤波器。 相反，$|{lim}_{K\to \mathrm{\infty }}{g}_{\gamma ,K}({\lambda }_i)/{lim}_{K\to \mathrm{\infty }}{g}_{\gamma ,K}({\lambda }_1)|>1\forall i\ge 2$ 意味着应用图形过滤器后，最低频率分量（对应于 ${\lambda }_1$)不再占主导地位。 这对应于高通滤波器的情况。

证明。

我们从低通滤波器结果开始。 从基本频谱分析（Von Luxburg，2007）我们知道${\lambda }_1=1$和。 人们还可以在补充中的引理A.2的证明中找到分析。 然后通过假设我们知道

$g_{\gamma ,K}({\lambda }_1)={\displaystyle \sum _{k=0}^K}{\gamma }_k=1.$

因此，证明定理A.1相当于证明

这是显而易见的，因为 $g_{\gamma ,K}(\lambda )={\sum }_{k=0}^K{\gamma }_k{\lambda }^k$ 是具有非负系数的 $K$ 阶多项式。 很容易检查。 结合所有 ${\gamma }_k$ 都是非负的事实，我们有

$|g_{\gamma ,K}({\lambda }_i)|\le {\displaystyle \sum _{k=0}^K}{\gamma }_k|{\lambda }^k|={\displaystyle \sum _{k=0}^K}{\gamma }_k{|\lambda |}^k\stackrel{\text{(a)}}{\le }{\displaystyle \sum _{k=0}^K}{\gamma }_k=1.$

最后，请注意，自 以来，(a) 中的等式成立的唯一可能性是 ${\gamma }_k={\delta }_{0,k}$。 然而，通过假设${\sum }_{k=0}^K{\gamma }_k=1$和$\exists k^{\prime }>0$使得${\gamma }_{k^{\prime }}>0$我们知道这是不可能的。 因此(a)是一个严格的不等式。 我们一起完成低通滤波部分的证明。

对于高通滤波器的结果，不难看出

$\underset{K\to \mathrm{\infty }}{lim}{g}_{\gamma ,K}(\lambda )=\underset{K\to \mathrm{\infty }}{lim}{\displaystyle \sum _{k=0}^K}{\gamma }_k{\lambda }^k=\underset{K\to \mathrm{\infty }}{lim}{\displaystyle \sum _{k=0}^K}{(-\alpha \lambda )}^k={\displaystyle \frac{1}{1+\alpha \lambda }},$

其中最后一步是由于 $\alpha \in (0,1)$ 和 ${lim}_{K\to \mathrm{\infty }}{(-\alpha \lambda )}^K=0,\forall |\lambda |\le 1$ 的事实。 因此我们有

$\left|{\displaystyle \frac{{lim}_{K\to \mathrm{\infty }}{g}_{\gamma ,K}({\lambda }_i)}{{lim}_{K\to \mathrm{\infty }}{g}_{\gamma ,K}({\lambda }_1)}}\right|=\left|{\displaystyle \frac{1+\alpha }{1+\alpha {\lambda }_i}}\right|\stackrel{\text{(b)}}{>}1\forall i\ge 2.$

严格的不等式(b)来自于这一事实。 值得注意的是，${sup}_{\lambda \in [1,-1)}\frac{1}{1+\alpha \lambda }$发生在边界$\lambda =-1$处，它对应于二部图。 它进一步表明，关于选择 ${\gamma }_k={(-\alpha )}^k$ 的图形滤波器强调高频分量，因此它确实充当高通滤波器。 ∎

A.4 定理证明4.2

在我们继续定理 4.2 的正式陈述之前，我们首先介绍一些附加的符号、引理和定义。 标签矩阵用$𝐘\in {ℝ}^{n\times C}$表示，其中每一行都是一个one-hot向量。 我们使用 $\mathrm{𝟏}[𝜷]\in {ℝ}^C$ 来表示向量 $𝜷\in {ℝ}^C$ 的 argmax：当且仅当 ${𝜷}_i=\max (𝜷)$ 时我们才有 $\mathrm{𝟏}{[𝜷]}_i=1$（关系均匀断开） ，否则 $\mathrm{𝟏}{[𝜷]}_i=0$。 让我们用softmax替换softmax$(\cdot )$$$(⋅)η，其中我们让 ${\text{softmax}}_{\eta }{(𝜷)}_i=e^{\eta {𝜷}_i}/({\sum }_j{e}^{\eta {𝜷}_j})$ 代表具有平滑参数 $\eta >0$ 的 softmax。 请注意，对于 $\eta =1$，我们恢复标准 softmax。 稍微滥用了符号，对于向量 $𝜷$，我们编写 $\exp (𝜷)$ 来表示按元素取幂。 我们使用 $⟨\cdot ,\cdot ⟩$ 来表示标准欧几里得内积。 我们还使用 $L$ 来表示交叉熵损失，其中

$L={\displaystyle \sum _{i\in V}}-\log (⟨{\widehat{𝐏}}_{i:},{𝐘}_{i:}⟩).$

Lemma A.2.

假设无向连通图中的节点 $G$ 具有 $C$ 标签之一。 然后，对于足够大的 $k$，我们有

${𝐇}_{:j}^{(k)}={𝜷}_j𝝅+o_k(1)\forall j\in [C],\mathit{\text{where}}{𝝅}_i={\displaystyle \frac{\sqrt{{\widetilde{𝐃}}_{ii}}}{\sqrt{{\sum }_{v\in V}{\widetilde{𝐃}}_{vv}}}}\mathit{\text{and}}{𝜷}^T={𝝅}^T{𝐇}^{(0)}.$ (2)

对于任何${𝐇}^{(0)}$和足够大的$k\le K$，如果标签预测以${𝐇}^{(k)}$为主，所有节点将具有与${\gamma }_k\beta$成比例的表示。 因此，我们将为所有节点得出相同的标签。 这就是我们所说的过度平滑现象。

Definition A.3 （过度平滑现象）.

首先，回想一下$𝐙\mathrm{=}{\mathrm{\sum }}_k{\gamma }_k\mathit{}{𝐇}^{\mathrm{(}k\mathrm{)}}$。 如果在 $K$ 足够大的情况下，GPR-GNN 中出现过度平滑，那么在 ${\gamma }_k\mathrm{>}\mathrm{0}$ 的情况下，对于某个 $c_{\mathrm{0}}\mathrm{>}\mathrm{0}$ 就会出现 ${𝐙}_{\mathrm{:}j}\mathrm{=}{c}_{\mathrm{0}}\mathit{}{𝛃}_j\mathit{}𝛑\mathrm{,}\mathrm{\forall }j\mathrm{\in }\mathrm{[}C\mathrm{]}$，而在 的情况下，对于某个 $c_{\mathrm{0}}\mathrm{>}\mathrm{0}$ 就会出现 ${𝐙}_{\mathrm{:}j}\mathrm{=}\mathrm{-}{c}_{\mathrm{0}}\mathit{}{𝛃}_j\mathit{}𝛑\mathrm{,}\mathrm{\forall }j\mathrm{\in }\mathrm{[}C\mathrm{]}$。

Lemma A.4.

让 $$L=Σiε𝒯L0>i1>=2>Σiε𝒯− log(⟨𝐏^我:,𝐘我:⟩) 为交叉熵损失，令 $𝒯$ 为训练集。 在与引理 A.2 中给出的相同假设下，$k$ 足够大的 ${\gamma }_k$ 的梯度为 $$∂L∂γk=Σiε𝒯η𝛑i⟨𝐏^我:−𝐘我:,𝛃⟩+ok(1).

Lemma A.5.

对于任何足够大的实向量 $𝛃\mathrm{\in }{ℝ}^C$ 和 $\eta \mathrm{>}\mathrm{0}$，我们有 ${\text{𝑠𝑜𝑓𝑡𝑚𝑎𝑥}}_{\eta }\mathit{}\mathrm{(}𝛃\mathrm{)}\mathrm{=}\mathrm{𝟏}\mathit{}\mathrm{[}𝛃\mathrm{]}\mathrm{+}{o}_{\eta }\mathit{}\mathrm{(}\mathrm{1}\mathrm{)}$。

现在我们准备好陈述定理4.2的正式版本。

Theorem A.6 （定理 4.2 的正式版本）。

在与引理A.2中列出的假设相同的情况下，如果集合包含每个类的节点，那么GPR-GNN方法总是可以避免过度平滑。 更具体地说，对于足够大的 $k\mathrm{,}\eta$ 我们有

${\displaystyle \frac{\partial L}{\partial {\gamma }_k}}={\displaystyle \sum _{i\in 𝒯}}\eta {𝝅}_i\left(\underset{j\in [C]}{\max }{𝜷}_j-{𝜷}_{\mathrm{𝟏}[{𝐘}_{i:}]}\right)+o_k(1)+o_{\eta }(1),\mathit{\text{when}}{\gamma }_k>0.$ (3)

(4)

注意，当${\gamma }_k>0$、(3)$\ge 0$时忽略$o(1)$项。 当且仅当 $$maxjε[C]⁡0>𝜷2>j3>1>=4>𝜷𝟏[𝐘我:]. 这意味着过度平滑会导致预测与训练集中的真实标签完全一致。 然而，如果我们的训练集至少包含每个类的一个节点，那么永远无法实现相等。 因此，当${\gamma }_k>0$时，${\gamma }_k$的梯度将始终为正。 类似地，当 、(4) $\le 0$ 时忽略 $o(1)$ 项。 当且仅当 $$分钟jε[C]⁡0>𝜷2>j3>1>=4>𝜷𝟏[𝐘我:]. 出于同样的原因，我们知道在训练集的假设下永远不可能达到平等。 因此，当时，${\gamma }_k$的梯度将始终为负。 最后，不难检查梯度的大小是否有界。 我们一起证明了 ${\gamma }_k$ 和 ${\gamma }_k$ 的梯度具有相同的符号。 这直接意味着当我们使用优化器的递减学习率（即 SGD）时，$|{\gamma }_k|$ 将接近 $0$，直到我们摆脱过度平滑。

证明。

首先，我们假设发生了过度平滑，并且 ${\gamma }_k>0$ 为主导项。 根据定义A.3，我们知道${𝐙}_{:j}=c_0{𝜷}_j𝝅,\forall j\in [C]$对于某些$c_0>0$和$K$足够大。 通过引理 A.4 我们有

${\displaystyle \frac{\partial L}{\partial {\gamma }_k}}={\displaystyle \sum _{i\in 𝒯}}\eta {𝝅}_i⟨{\displaystyle \frac{e^{\eta {𝐙}_{i:}}}{{\sum }_{j\in [C]}{e}^{\eta {𝐙}_{ij}}}}-{𝐘}_{i:},𝜷⟩+o_k(1)$ (5)

$={\displaystyle \sum _{i\in 𝒯}}\eta {𝝅}_i⟨{\displaystyle \frac{e^{\eta c_0{𝝅}_i𝜷}}{{\sum }_{j\in [C]}{e}^{\eta c_0{𝝅}_i{𝜷}_j}}}-{𝐘}_{i:},𝜷⟩+o_k(1),$ (6)

其中最后一步来自定义A.3。 接下来，通过引理 A.5，我们可以根据 $\eta >0$ 足够大的真实 argmax 来近似 softmax${}_{\eta }$

${\displaystyle \sum _{i\in 𝒯}}\eta {𝝅}_i⟨\mathrm{𝟏}[c_0{𝝅}_i𝜷]-{𝐘}_{i:},𝜷⟩+o_k(1)+o_{\eta }(1)$ (7)

$={\displaystyle \sum _{i\in 𝒯}}\eta {𝝅}_i⟨\mathrm{𝟏}[𝜷]-{𝐘}_{i:},𝜷⟩+o_k(1)+o_{\eta }(1)$ (8)

$={\displaystyle \sum _{i\in 𝒯}}\eta {𝝅}_i\left(\underset{j\in [C]}{\max }{𝜷}_j-{𝜷}_{\mathrm{𝟏}[{𝐘}_{i:}]}\right)+o_k(1)+o_{\eta }(1).$ (9)

第一个相等是由于 $c_0>0$ 和 ${𝝅}_i>0$ 的事实。 回想一下引理A.2,${𝝅}_i=\frac{\sqrt{{\widetilde{𝐃}}_{ii}}}{\sqrt{{\sum }_{v\in V}{\widetilde{𝐃}}_{vv}}}$。 由于我们每个节点都有一个自循环，${\widetilde{𝐃}}_{ii}>0$ 以及${𝝅}_i>0$。 对于情况，相同的分析在(7)之前仍然有效。 因此我们有

${\displaystyle \sum _{i\in 𝒯}}\eta {𝝅}_i⟨\mathrm{𝟏}[-c_0{𝝅}_i𝜷]-{𝐘}_{i:},𝜷⟩+o_k(1)+o_{\eta }(1)$ (10)

$={\displaystyle \sum _{i\in 𝒯}}\eta {𝝅}_i⟨\mathrm{𝟏}[-𝜷]-{𝐘}_{i:},𝜷⟩+o_k(1)+o_{\eta }(1)$ (11)

$={\displaystyle \sum _{i\in 𝒯}}\eta {𝝅}_i\left(\underset{j\in [C]}{\min }{𝜷}_j-{𝜷}_{\mathrm{𝟏}[{𝐘}_{i:}]}\right)+o_k(1)+o_{\eta }(1).$ (12)

我们一起完成证明。

∎

A.5 cSBM 详细信息

cSBM 在经典 SBM 之上添加高斯随机向量作为节点特征。 为简单起见，我们假设 $C=2$ 大小相同的社区，在 $\{+1,-1\}$ 中具有节点标签 $v_i$。 每个节点 $i$ 都与一个 $f$ 维高斯向量 $b_i=\sqrt{\frac{\mu }{n}}{v}_{i}u+\frac{Z_i}{\sqrt{f}}$ 关联，其中 $n$ 是节点数，$u\sim N(0,I/f)$和$Z_i\in {𝐑}^f$有独立的标准正常条目。 cSBM 中的（无向）图由邻接矩阵 $𝐀$ 描述，定义为

与经典的 SBM 类似，给定节点标签，边是独立的。 符号$d$代表图的平均度。 另外，请记住 $\mu$ 和 $\lambda$ 分别控制节点特征和图结构携带的信息强度。

使用 cSBM 生成合成数据的原因之一是模型的信息论极限已在 Deshpande 等人 (2018) 中得到表征。 该结果总结如下。

Theorem A.7 (Deshpande 等人 (2018) 中的非正式主要结果）。

假设$n\mathrm{,}f\mathrm{\to }\mathrm{\infty }$、$\frac{n}{f}\mathrm{\to }\xi$和$d\mathrm{\to }\mathrm{\infty }$。 然后存在一个估计器$\widehat{v}$，使得当且仅当${\lambda }^{\mathrm{2}}\mathrm{+}\frac{{\mu }^{\mathrm{2}}}{\xi }\mathrm{>}\mathrm{1}$时$\lim {\inf }_{n\mathrm{\to }\mathrm{\infty }}\frac{\mathrm{|}\mathrm{⟨}\widehat{v}\mathrm{,}v\mathrm{⟩}\mathrm{|}}{n}$远离$\mathrm{0}$。

在我们的实验中，我们设置了 $n=5000,f=2000$，因此有 $\xi =2.5$。 对于某些$ϵ>0$，我们沿着弧线${\lambda }^2+{\mu }^2/\xi =1+ϵ$改变$\mu$和$\lambda$，以确保我们处于可实现的参数范围内。 我们还为所有实验选择 $ϵ=3.25$。

A.6 引理证明A.2

请注意，引理 A.2 的证明简化为图上随机游走的标准分析。 为了完整起见，我们将其包含在内，并请感兴趣的读者参考教程 Von Luxburg (2007)。

我们首先证明对称图拉普拉斯

${\widetilde{𝐋}}_{\text{sym}}=𝐈-{\widetilde{𝐃}}^{-1/2}\widetilde{𝐀}{\widetilde{𝐃}}^{-1/2}=𝐈-{\widetilde{𝐀}}_{\text{sym}}$ (13)

是半正定的。 令 $u$ 为单位范数和 $f={\widetilde{𝐃}}^{-1/2}u$ 的任意实数向量，则我们有

$u^T{\widetilde{𝐋}}_{\text{sym}}u=u^{T}u-u^T{\widetilde{𝐃}}^{-1/2}\widetilde{𝐀}{\widetilde{𝐃}}^{-1/2}u={\displaystyle \sum _{i=1}^n}{u}_i^2-{\displaystyle \sum _{i,j=1}^n}{f}_i{f}_j{\widetilde{𝐀}}_{ij}$ (14)

$={\displaystyle \sum _{i=1}^n}{\widetilde{𝐃}}_{ii}{f}_i^2-{\displaystyle \sum _{i,j=1}^n}{f}_i{f}_j{\widetilde{𝐀}}_{ij}={\displaystyle \frac{1}{2}}({\displaystyle \sum _{i=1}^n}{\widetilde{𝐃}}_{ii}{f}_i^2-2{\displaystyle \sum _{i,j=1}^n}{f}_i{f}_j{\widetilde{𝐀}}_{ij}+{\displaystyle \sum _{j=1}^n}{\widetilde{𝐃}}_{jj}{f}_j^2)$ (15)

$={\displaystyle \frac{1}{2}}{\displaystyle \sum _{i,j=1}^n}{\widetilde{𝐀}}_{ij}{(f_i-f_j)}^2,$ (16)

其中最后一步来自度的定义。

接下来我们证明 $0$ 确实是与单位特征向量 $𝝅$ 相关的 ${\widetilde{𝐋}}_{\text{sym}}$ 特征值，其中 $𝝅=\frac{\sqrt{{\widetilde{𝐃}}_{ii}}}{\sqrt{{\sum }_v{\widetilde{𝐃}}_{vv}}}$。

令 $\mathrm{𝟙}$ 为全一个向量。 那么直接计算可知

${\widetilde{𝐋}}_{\text{sym}}𝝅=𝝅-{\widetilde{𝐃}}^{-1/2}\widetilde{𝐀}{\widetilde{𝐃}}^{-1/2}𝝅=𝝅-{\widetilde{𝐃}}^{-1/2}\widetilde{𝐀}{\widetilde{𝐃}}^{-1/2}{\widetilde{𝐃}}^{1/2}\mathrm{𝟙}\times {\displaystyle \frac{1}{\sqrt{{\sum }_v{\widetilde{𝐃}}_{vv}}}}$ (17)

$=𝝅-{\widetilde{𝐃}}^{-1/2}\widetilde{𝐀}\mathrm{𝟙}\times {\displaystyle \frac{1}{\sqrt{{\sum }_v{\widetilde{𝐃}}_{vv}}}}=𝝅-{\widetilde{𝐃}}^{-1/2}\widetilde{𝐃}\mathrm{𝟙}\times {\displaystyle \frac{1}{\sqrt{{\sum }_v{\widetilde{𝐃}}_{vv}}}}$ (18)

$=𝝅-{\widetilde{𝐃}}^{1/2}\mathrm{𝟙}\times {\displaystyle \frac{1}{\sqrt{{\sum }_v{\widetilde{𝐃}}_{vv}}}}=𝝅-𝝅=0.$ (19)

将此结果与拉普拉斯算子的正半定性质相结合表明 $0$ 确实是与特征向量 $𝝅$ 相关的 ${\widetilde{𝐋}}_{\text{sym}}$ 的最小特征值。 而且，从(16)和图连通的假设，不难看出特征值$0$的重数恰好为1（见命题2和命题4）参见 Von Luxburg (2007) 了解更多详情）。 最后，从(13)可以明显看出${\widetilde{𝐀}}_{\text{sym}}$的最大特征值是$1$，对应特征向量$𝝅$ 。 因此 ${\widetilde{𝐀}}_{\text{sym}}$ $1>{\lambda }_2\ge \mathrm{\dots }\ge {\lambda }_n$ 的所有其他特征值。

接下来我们证明。 这也可以直接从 (16) 显示。 注意

$u^T{\widetilde{𝐋}}_{\text{sym}}u={\displaystyle \frac{1}{2}}{\displaystyle \sum _{i,j=1}^n}{\widetilde{𝐀}}_{ij}{(f_i-f_j)}^2$ (20)

$\le {\displaystyle \sum _{i,j=1}^n}{\widetilde{𝐀}}_{ij}(f_i^2+f_j^2)=2{\displaystyle \sum _{i,j=1}^n}{\widetilde{𝐀}}_{ij}{f}_i^2=2{\displaystyle \sum _{i,j=1}^n}{\widetilde{𝐀}}_{ij}{\displaystyle \frac{u_i^2}{{\widetilde{𝐃}}_{ii}}}$ (21)

$=2{\displaystyle \sum _{i=1}^n}{\displaystyle \frac{u_i^2}{{\widetilde{𝐃}}_{ii}}}{\displaystyle \sum _{j=1}^n}{\widetilde{𝐀}}_{ij}=2{\displaystyle \sum _{i=1}^n}{\displaystyle \frac{u_i^2}{{\widetilde{𝐃}}_{ii}}}{\widetilde{𝐃}}_{ii}=2{\displaystyle \sum _{i=1}^n}{u}_i^2=2.$ (22)

该不等式源自柯西-施瓦茨不等式的应用。 因此，${\widetilde{𝐋}}_{\text{sym}}$ 的最大特征值以 $2$ 为界，这意味着 $|{\lambda }_n|\le 1$。 请注意，当且仅当底层图是二分图时，相等才成立。 然而，这在我们的设置中是不可能的，因为我们已经向每个节点添加了一个自循环。 因此。 这意味着

$\underset{k\to \mathrm{\infty }}{lim}{\widetilde{𝐀}}_{\text{sym}}^k=𝝅{𝝅}^T.$ (23)

因此，对于任何 ${𝐇}^{(0)}$ 我们有

$\underset{k\to \mathrm{\infty }}{lim}{\widetilde{𝐀}}_{\text{sym}}^k{𝐇}^{(0)}=𝝅{𝝅}^T{𝐇}^{(0)}=𝝅{𝜷}^T.$ (24)

请注意，这也可以用 $o_k(1)$ 项写成

${\widetilde{𝐀}}_{\text{sym}}^k{𝐇}^{(0)}=𝝅{𝜷}^T+o_k(1).$ (25)

这样就完成了证明。

A.7 引理证明A.4

回想一下，我们的损失函数等于

$L={\displaystyle \sum _{i\in 𝒯}}{L}_i={\displaystyle \sum _{i\in 𝒯}}-\log ({\displaystyle \frac{e^{\eta ⟨{𝐙}_{i:},{𝐘}_{i:}⟩}}{{\sum }_{m=1}^C{e}^{\eta {𝐙}_{im}}}}).$ (26)

然后通过对损失函数关于 ${\gamma }_{k^{\prime }}$ 求偏导数，我们有

${\displaystyle \frac{\partial L}{\partial {\gamma }_{k^{\prime }}}}={\displaystyle \frac{\partial }{\partial {\gamma }_{k^{\prime }}}}{\displaystyle \sum _{i\in 𝒯}}(\log ({\displaystyle \sum _{m=1}^C}{e}^{\eta {𝐙}_{im}})-⟨\eta {𝐙}_{i:},{𝐘}_{i:}⟩).$ (27)

接下来，回想一下，对于 GPR-GNN，我们还有 $𝐙={\sum }_{k=0}^K{\gamma }_k{𝐇}^{(k)}$。 将此表达式代入前面的公式并应用我们获得的链式法则

${\displaystyle \frac{\partial }{\partial {\gamma }_{k^{\prime }}}}{\displaystyle \sum _{i\in 𝒯}}(\log ({\displaystyle \sum _{m=1}^C}{e}^{\eta {𝐙}_{im}})-⟨\eta {𝐙}_{i:},{𝐘}_{i:}⟩)={\displaystyle \sum _{i\in 𝒯}}({\displaystyle \frac{{\sum }_{m=1}^C{e}^{\eta {𝐙}_{im}}\frac{\partial \eta {𝐙}_{im}}{\partial {\gamma }_{k^{\prime }}}}{{\sum }_{m=1}^C{e}^{{𝐙}_{im}}}}-⟨\eta {𝐇}_{i:}^{(k^{\prime })},{𝐘}_{i:}⟩)$ (28)

$={\displaystyle \sum _{i\in 𝒯}}({\displaystyle \frac{{\sum }_{m=1}^C{e}^{\eta {𝐙}_{im}}\eta {𝐇}_{im}^{(k^{\prime })}}{{\sum }_{m=1}^C{e}^{\eta {𝐙}_{im}}}}-⟨\eta {𝐇}_{i:}^{(k^{\prime })},{𝐘}_{i:}⟩)$ (29)

设置$k^{\prime }=k$为足够大的$k$，从引理A.2得出

${\displaystyle \frac{\partial L}{\partial {\gamma }_k}}={\displaystyle \sum _{i\in 𝒯}}\eta ({\displaystyle \frac{{\sum }_{m=1}^C{e}^{\eta {𝐙}_{im}}{𝐇}_{im}^{(k)}}{{\sum }_{m=1}^C{e}^{\eta {𝐙}_{im}}}}-⟨{𝐇}_{i:}^{(k)},{𝐘}_{i:}⟩)$ (30)

$={\displaystyle \sum _{i\in 𝒯}}\eta ({\displaystyle \frac{{\sum }_{m=1}^C{e}^{\eta {𝐙}_{im}}({𝝅}_i{𝜷}_m+o_k(1))}{{\sum }_{m=1}^C{e}^{\eta {𝐙}_{im}}}}-⟨{𝝅}_i𝜷+o_k(1),{𝐘}_{i:}⟩)$ (31)

$={\displaystyle \sum _{i\in 𝒯}}{𝝅}_i\eta ({\displaystyle \frac{{\sum }_{m=1}^C{e}^{\eta {𝐙}_{im}}{𝜷}_m}{{\sum }_{m=1}^C{e}^{\eta {𝐙}_{im}}}}-⟨𝜷,{𝐘}_{i:}⟩)+o_k(1)$ (32)

$={\displaystyle \sum _{i\in 𝒯}}{𝝅}_i\eta ({\displaystyle \sum _{m=1}^C}{\widehat{𝐏}}_{im}{𝜷}_m-⟨𝜷,{𝐘}_{i:}⟩)+o_k(1)={\displaystyle \sum _{i\in 𝒯}}\eta {𝝅}_i⟨{\widehat{𝐏}}_{i:}-{𝐘}_{i:},𝜷⟩+o_k(1).$ (33)

请注意，在 (32) 和 (33) 中，我们使用了软预测 $\widehat{𝐏}={\text{softmax}}_{\eta }(𝐙)$ 的定义。 这样就完成了证明。

A.8 引理证明A.5

让$\widehat{\beta }=\max (𝜷)$。 然后根据 $\eta >0$ 的 softmax${}_{\eta }$ 的定义，我们有

${\text{softmax}}_{\eta }(𝜷)={\displaystyle \frac{e^{\eta 𝜷}}{{\sum }_{m=1}^C{e}^{\eta {𝜷}_m}}}={\displaystyle \frac{e^{-\eta (\widehat{\beta }-𝜷)}}{{\sum }_{m=1}^C{e}^{-\eta (\widehat{\beta }-{𝜷}_m)}}}.$ (34)

请注意，${𝜷}_m\ne \widehat{\beta }$ 时为 $\widehat{\beta }-{𝜷}_m>0$,${𝜷}_m=\widehat{\beta }$ 时为 $\widehat{\beta }-{𝜷}_m=0$。 不失一般性，我们假设 $𝜷$ 中有 $p$ 最大值，其中 $1\le p\le C,$ 并让 $𝒫$ 表示这些最大值的索引集最大值。 然后，取限制 $\eta \to \mathrm{\infty }$ 我们有

(35)

这意味着对于足够大的 $\eta >0$ 有

${\text{softmax}}_{\eta }(𝜷)=\mathrm{𝟏}[𝜷]+o_{\eta }(1).$ (36)

以上结果完成了证明。

A.9其他实验细节

表 4： cSBM 数据集的同质性度量值。

$\varphi$	$-1$	$-0.75$	$-0.5$	$-0.25$	$0$	$0.25$	$0.5$	$0.75$	$1$
$\mathscr{H}(G)$	0.039	0.073	0.170	0.328	0.500	0.673	0.829	0.928	0.960

所有实验均在具有 $48$ 个内核、$376$GB RAM 以及具有 $12$GB GPU 内存的 NVIDIA Tesla P100 GPU 的 Linux 计算机上执行。 对于训练集，我们确保每个类的节点数量大致相同，并使训练节点总数接近 $2.5\%/60\%$。 对于验证集，我们随机抽取节点 $2.5\%/20\%$ 并将其余节点放入测试集中。

对于所有基线模型，我们直接使用 Pytorch 几何库 Fey & Lenssen (2019) 中提供的实现。我们使用提前停止 $200$ 和最大时期数等于 $1000$ 对于真实基准数据集和我们的 cSBM 合成数据集。 所有模型均使用 Adam 优化器Kingma & Ba (2014)。 请注意，早期停止标准与 Pytorch Geometric 中的完全相同 - 当历元大于最大历元的一半时，我们检查当前验证损失是否低于过去 $200$ 历元的平均值。 如果不低于，我们停止训练过程。

对于 GCN，我们使用带有 $64$ 隐藏单元的 $2$ GCN 层。 对于 GAT，我们使用 $2$ GAT 卷积层，其中第一层有 $8$ 个注意力头，每个头有 $8$ 个隐藏单元；第二层有 $1$ 注意力头和 $64$ 隐藏单元。 对于 GCN-Cheby，我们对具有 $32$ 隐藏单元的每一层使用 $2$ 步骤传播。 请注意，在这种情况下，每层的等效隐藏单元数量为$64$。 对于 JK-Net，我们使用基于 GCN 的模型，每层都有 $2$ 层和 $16$ 隐藏单元。 至于层聚合部分，我们使用具有 $16$ 通道和 $4$ 层的 LSTM。 对于 MLP，我们选择具有 $6$4 个隐藏单元的 $2$ 层全连接网络。 对于 APPNP，我们使用相同的 $2$ 层 MLP 和 $10$ 传播步骤。 除了GPR-GNN之外，我们将NN部分的dropout率固定为$0.5$作为APPNP，并优化$\{0,0.5,0.7\}$中GPR部分的dropout率。 对于 Geom-GCN，我们选择论文中已经测试过的数据集，该数据集首次描述了该方法（Pei 等人，2019）。 对于SGC，我们在$\{2,3\}$之间测试后使用默认的$K=2$层。 对于 SAGE，我们使用 $2$ SAGE 卷积层和 $64$ 隐藏单元。

（裴等人，2019）中使用的异嗜性数据集。 图 Chameleon、Actor、Squirrel、Texas 和 Cornell 的原始形式是有向图（参见 (Pei 等人, 2019) 的 github 存储库）。 由于半监督节点分类的通常设置涉及无向图，因此我们将图转换为无向图，以在所有先前描述的基准方法上对其进行测试。 我们保留针对 Geom-GCN 的输入图，因为该方法使用固定的预处理方案，不幸的是作者没有公开该方案。 表1中的同质性度量值$\mathscr{H}(G)$均基于无向图，因此与（Pei等人，2019）中报告的数字不同>。

A.10附加实验结果

表 5： cSBM 的结果，稀疏分裂。 粗体值表示获得的最佳结果，粗体带下划线的值表示相对于最佳结果在 $95\%$ 置信区间内的结果。

	$\varphi =-1$	$\varphi =-0.75$	$\varphi =-0.5$	$\varphi =-0.25$	$\varphi =0$	$\varphi =0.25$	$\varphi =0.5$	$\varphi =0.75$	$\varphi =1$
GPRGNN	97.19$\mathrm{\pm }$0.16	95.54$\mathrm{\pm }$0.15	81.54$\mathrm{\pm }$0.73	60.65$\pm$0.31	62.16$\mathrm{\pm }$0.23	68.83$\mathrm{\pm }$0.28	89.31$\mathrm{\pm }$0.16	96.98$\mathrm{\pm }$0.08	96.71$\mathrm{\pm }$0.13
GPRGNN(random)	88.39$\pm$3.31	88.54$\pm$3.01	66.91$\pm$2.93	56.35$\pm$0.98	58.09$\pm$0.71	64.01$\pm$1.39	81.93$\pm$1.68	94.59$\pm$0.29	93.69$\pm$1.04
APPNP	49.57$\pm$0.11	52.45$\pm$0.27	56.32$\pm$0.40	59.55$\pm$0.48	61.21$\pm$0.23	68.41$\pm$0.30	85.66$\pm$0.22	94.37$\pm$0.09	90.02$\pm$0.16
MLP	49.88$\pm$0.10	53.40$\pm$0.34	57.14$\pm$0.41	60.55$\pm$0.41	62.15$\mathrm{\pm }$0.33	61.26$\pm$0.21	57.91$\pm$0.35	53.36$\pm$0.32	49.92$\pm$0.11
SGC	54.41$\pm$0.37	59.74$\pm$0.29	55.57$\pm$0.33	51.84$\pm$0.23	53.95$\pm$0.28	65.65$\pm$0.27	85.51$\pm$0.20	93.99$\pm$0.10	88.50$\pm$0.18
GCN	55.24$\pm$0.35	61.04$\pm$0.39	56.40$\pm$0.39	52.23$\pm$0.24	54.43$\pm$0.32	67.23$\pm$0.29	84.56$\pm$0.20	90.19$\pm$0.14	78.67$\pm$0.19
GAT	53.97$\pm$0.32	57.18$\pm$0.45	53.39$\pm$0.34	51.23$\pm$0.19	53.26$\pm$0.27	64.45$\pm$0.36	81.94$\pm$0.34	88.45$\pm$0.26	78.06$\pm$0.30
SAGE	62.30$\pm$0.50	75.10$\pm$0.50	72.84$\pm$0.44	63.88$\mathrm{\pm }$0.37	58.62$\pm$0.30	63.55$\pm$0.47	73.50$\pm$0.50	75.26$\pm$0.52	62.61$\pm$0.44
JKNet	51.70$\pm$0.39	55.83$\pm$0.75	52.67$\pm$0.51	50.27$\pm$0.15	52.02$\pm$0.35	65.67$\pm$0.44	86.35$\pm$0.19	95.13$\pm$0.09	90.32$\pm$0.17
GCN-Cheby	61.44$\pm$0.51	73.91$\pm$0.75	71.96$\pm$0.6	63.96$\mathrm{\pm }$0.43	59.70$\pm$0.34	64.00$\pm$0.38	72.34$\pm$0.63	73.56$\pm$0.65	60.88$\pm$0.58

表 6： cSBM 的结果，密集分裂。 粗体值表示找到的最佳结果，而粗体、下划线值表示相对于最佳结果在 $95\%$ 置信区间内的结果。

	$\varphi =-1$	$\varphi =-0.75$	$\varphi =-0.5$	$\varphi =-0.25$	$\varphi =0$	$\varphi =0.25$	$\varphi =0.5$	$\varphi =0.75$	$\varphi =1$
GPRGNN	98.83$\mathrm{\pm }$0.06	98.19$\mathrm{\pm }$0.08	94.23$\mathrm{\pm }$0.14	86.06$\mathrm{\pm }$0.20	82.22$\mathrm{\pm }$0.20	86.48$\mathrm{\pm }$0.20	94.34$\mathrm{\pm }$0.13	98.46$\mathrm{\pm }$0.08	98.84$\mathrm{\pm }$0.06
GPRGNN(random)	98.75$\pm$0.05	98.08$\pm$0.08	94.22$\pm$0.14	86.06$\pm$0.20	81.57$\mathrm{\pm }$0.23	86.36$\mathrm{\pm }$0.20	94.09$\pm$0.14	98.38$\mathrm{\pm }$0.08	98.77$\pm$0.07
APPNP	48.94$\pm$0.29	63.87$\pm$0.29	73.30$\pm$0.26	79.30$\pm$0.20	82.41$\pm$0.23	86.47$\pm$0.18	94.20$\pm$0.14	97.96$\pm$0.10	98.53$\pm$0.08
MLP	49.79$\pm$0.29	66.69$\pm$0.27	75.36$\pm$0.26	80.30$\pm$0.24	82.19$\pm$0.24	80.88$\pm$0.22	76.07$\pm$0.24	66.61$\pm$0.25	49.65$\pm$0.29
SGC	78.95$\pm$0.23	81.79$\pm$0.24	75.15$\pm$0.25	59.40$\pm$0.28	63.75$\pm$0.26	80.81$\pm$0.22	93.04$\pm$0.15	98.05$\pm$0.08	97.80$\pm$0.09
GCN	78.50$\pm$0.28	83.68$\pm$0.22	75.98$\pm$0.25	59.98$\pm$0.25	64.09$\pm$0.26	81.89$\pm$0.19	93.91$\pm$0.12	97.78$\pm$0.08	96.29$\pm$0.11
GAT	82.39$\pm$0.41	80.37$\pm$0.22	71.01$\pm$0.26	57.68$\pm$0.29	62.95$\pm$0.28	80.61$\pm$0.24	93.26$\pm$0.14	97.99$\pm$0.08	98.40$\pm$0.09
SAGE	91.33$\pm$0.23	95.72$\pm$0.12	93.23$\pm$0.17	84.52$\pm$0.20	78.99$\pm$0.24	84.87$\pm$0.20	92.90$\pm$0.15	95.75$\pm$0.11	91.19$\pm$0.24
JKNet	96.11$\pm$0.37	95.33$\pm$0.25	87.98$\pm$0.56	59.61$\pm$0.49	63.28$\pm$0.10	80.23$\pm$0.36	93.28$\pm$0.15	98.33$\pm$0.07	98.22$\pm$0.07
GCN-Cheby	90.94$\pm$0.16	94.82$\pm$0.13	91.83$\pm$0.17	85.18$\pm$0.21	80.80$\pm$0.25	85.28$\pm$0.21	92.70$\pm$0.16	95.06$\pm$0.13	90.34$\pm$0.18

表 7： (Pei 等人, 2019) 中测试的同质真实世界基准数据集的结果，密集分割：平均准确率 ($\%$) $\pm$ $95\%$ 置信区间。 粗体值表示找到的最佳结果，而粗体、下划线值表示相对于最佳结果的置信区间内的结果。

	Cora	Citeseer	PubMed
GPRGNN	88.65$\mathrm{\pm }$0.28	80.01$\pm$0.28	89.18$\mathrm{\pm }$0.15
APPNP	88.1$\pm$0.23	80.5$\mathrm{\pm }$0.26	89.15$\mathrm{\pm }$0.13
MLP	76.44$\pm$0.30	76.25$\pm$0.28	86.43$\pm$0.13
SGC	86.58$\pm$0.26	76.23$\pm$0.29	83.52$\pm$0.10
GCN	86.87$\pm$0.25	79.28$\pm$0.25	86.97$\pm$0.12
GAT	87.52$\pm$0.24	80.56$\mathrm{\pm }$0.31	86.64$\pm$0.11
SAGE	86.58$\pm$0.26	78.24$\pm$0.30	86.85$\pm$0.11
JKNet	86.97$\pm$0.27	77.69$\pm$0.35	87.38$\pm$0.13
GCN-Cheby	86.46$\pm$0.26	78.66$\pm$0.26	88.2$\pm$0.09
GeomGCN	85.4$\pm$0.26	76.42$\pm$0.37	88.51$\pm$0.08

(a) cSBM、$\varphi =0.0$、

($\mathscr{H}(G)=0.501$)

(b) cSBM、$\varphi =0.25$、

($\mathscr{H}(G)=0.673$)

(c) cSBM、$\varphi =0.5$、

($\mathscr{H}(G)=0.829$)

(d) cSBM、$\varphi =0.75$、

($\mathscr{H}(G)=0.928$)

(e) cSBM、$\varphi =1.0$、

($\mathscr{H}(G)=0.960$)

(f) cSBM、$\varphi =-0.25$、

($\mathscr{H}(G)=0.328$)

(g) cSBM、$\varphi =-0.5$、

($\mathscr{H}(G)=0.170$)

(h) cSBM、$\varphi =-0.75$、

($\mathscr{H}(G)=0.073$)

(i) cSBM、$\varphi =-1.0$、

($\mathscr{H}(G)=0.039$)

图7： 图 (a)-(i) 显示了 GPR-GNN 学习到的 GPR 权重，在 cSBM 上随机初始化，密集分裂。 阴影区域表示$95\%$置信区间。

(a)科拉，

($\mathscr{H}(G)=0.825$)

(b) Citeseer、

($\mathscr{H}(G)=0.718$)

(c) PubMed、

($\mathscr{H}(G)=0.792$)

(d) 计算机，

($\mathscr{H}(G)=0.802$)

(e) 照片，

($\mathscr{H}(G)=0.849$)

(f) 变色龙，

($\mathscr{H}(G)=0.247$)

(g)演员，

($\mathscr{H}(G)=0.215$)

(h)松鼠，

($\mathscr{H}(G)=0.217$)

(i) 德克萨斯州，

($\mathscr{H}(G)=0.057$)

(j) 康奈尔大学，

($\mathscr{H}(G)=0.301$)

图8： 图 (a)-(j) 显示了 GPR-GNN 学习到的 GPR 权重，对各种基准数据集进行随机初始化、密集分割。 阴影区域表示$95\%$置信区间。 请注意，学习到的 GPR 权重对于每个同质数据集都是正的。 每个异嗜数据集至少有一个负学习 GPR 权重。

表8： 其他实验表明 GPR-GNN 避免了过度平滑。 我们按照 5 节中的描述初始化 GPR 权重 ${\gamma }_k={\delta }_{kK}$。 我们报告训练纪元 $0$ 和之后（最终纪元）的平均准确度。 过度平滑比率表示 GPR-GNN 开始的 $100$ 运行中有多少次导致所有节点具有相同的标签。 有关 GPR 权重在不同时期如何变化的说明，请查看图9。

	Accuracy at epoch $0$(%)	Accuracy at the final epoch(%)	Over-smoothing ratio(%)
Cora	12.75	88.25	84
Computers	9.41	85.93	89
Squirrel	19.87	52.06	97
Texas	21.05	90.05	100

(a) 科拉，纪元$0$

(b) 科拉，纪元$50$

(c) 科拉，纪元$100$

(d) 科拉，纪元$150$

(e) 科拉，纪元$200$

(f) 计算机，

纪元$0$

(g) 计算机，

纪元$50$

(h) 计算机，

纪元$100$

(i) 计算机，

纪元$150$

(j) 计算机，

纪元$200$

(k) 松鼠，

纪元$0$

(l) 松鼠，

纪元$50$

(m) 松鼠，

纪元$100$

(n) 松鼠，

纪元$150$

(o) 松鼠，

纪元$200$

(p) 德克萨斯州，纪元$0$

(q) 德克萨斯州，纪元$50$

(r) 德克萨斯州，纪元$100$

(s) 德克萨斯州，纪元$150$

(t) 德克萨斯州，纪元$200$

图9： 通过 GPR-GNN 学习 GPR 权重，并在各种基准数据集上初始化 ${\gamma }_k={\delta }_{kK}$（最后一步），密集分割。 阴影区域表示$95\%$置信区间。 另外，请检查表8。 请注意，GPR 权重 ${\{{\gamma }_k\}}_{k=0}^K$ 在图过滤方面与 ${\{-{\gamma }_k\}}_{k=0}^K$ 相同。

(a) 科拉，纪元$0$

(b) 科拉，纪元$50$

(c) 科拉，纪元$100$

(d) 科拉，纪元$150$

(e) 科拉，纪元$200$

(f) 计算机，

纪元$0$

(g) 计算机，

纪元$50$

(h) 计算机，

纪元$100$

(i) 计算机，

纪元$150$

(j) 计算机，

纪元$200$

(k) 松鼠，

纪元$0$

(l) 松鼠，

纪元$50$

(m) 松鼠，

纪元$100$

(n) 松鼠，

纪元$150$

(o) 松鼠，

纪元$200$

(p) 德克萨斯州，纪元$0$

(q) 德克萨斯州，纪元$50$

(r) 德克萨斯州，纪元$100$

(s) 德克萨斯州，纪元$150$

(t) 德克萨斯州，纪元$200$

图10： 在各种基准数据集上随机初始化学习 GPR 权重的动态，密集分裂。 阴影区域表示$95\%$置信区间。

表 9： 同质现实世界基准数据集的效率：每个周期的平均运行时间（毫秒）/平均总运行时间。

	Cora	Citeseer	Pubmed	Computers	Photo
GPRGNN	17.62ms / 3.74s	19.28ms / 3.89s	20.19ms / 5.53s	39.93ms / 11.40s	21.61ms / 6.18s
APPNP	17.16ms / 4.00s	15.97ms / 3.26s	18.47ms / 6.29s	39.59ms / 20.00s	20.10ms / 10.93s
MLP	4.14ms / 0.92s	5.30ms / 1.13s	5.43ms / 2.86s	5.33ms / 2.77s	4.63ms / 2.72s
SGC	3.31ms / 3.31s	11.45ms / 2.31s	3.81ms / 3.81s	4.36ms / 4.36s	19.12ms / 8.75s
GCN	9.25ms / 1.97s	17.46ms / 3.53s	14.11ms / 4.17s	32.45ms / 16.29s	32.56ms / 11.33s
GAT	14.78ms / 3.42s	19.94ms / 4.47s	21.52ms / 6.70s	61.45ms / 24.28s	24.57ms / 11.61s
SAGE	12.06ms / 2.44s	41.40ms / 8.36s	28.82ms / 6.32s	171.36ms / 71.94s	108.88ms / 42.18s
JKNet	18.97ms / 4.41s	3.99ms / 3.99s	24.48ms / 6.61s	35.02ms / 14.96s	3.66ms / 3.66s
GCN-cheby	22.96ms / 4.75s	23.16ms / 4.68s	45.76ms / 12.02s	218.82ms / 96.58s	82.38ms / 30.48s

表 10： 异质现实世界基准数据集的效率：每个周期的平均运行时间（毫秒）/平均总运行时间（秒）。

	Chameleon	Squirrel	Actor	Texas	Cornell
GPRGNN	16.74ms / 3.40s	25.28ms / 5.12s	19.31ms / 4.49s	17.56ms / 3.55s	18.42ms / 3.72s
APPNP	17.01ms / 3.44s	22.93ms / 4.63s	16.32ms / 4.04s	15.96ms / 3.24s	14.66ms / 3.09s
MLP	3.41ms / 0.69s	5.19ms / 1.05s	4.84ms / 0.98s	3.81ms / 1.04s	3.46ms / 0.89s
SGC	13.83ms / 2.79s	27.11ms / 5.56s	12.39ms / 2.50s	10.22ms / 2.06s	10.38ms / 2.10s
GCN	16.63ms / 3.63s	47.46ms / 10.05s	18.91ms / 3.86s	15.50ms / 3.13s	13.67ms / 2.76s
GAT	20.03ms / 5.15s	29.89ms / 6.67s	23.52ms / 4.75s	19.67ms / 4.01s	19.35ms / 3.91s
SAGE	89.41ms / 18.06s	440.55ms / 88.99s	43.94ms / 8.88s	12.34ms / 3.08s	12.15ms / 2.69s
JKNet	3.13ms / 3.13s	4.79ms / 4.79s	3.98ms / 1.00s	2.86ms / 2.09s	2.81ms / 1.18s
GCN-cheby	64.43ms / 13.02s	343.47ms / 69.38s	27.95ms / 5.65s	6.08ms / 1.28s	6.05ms / 1.44s