KDD'21 | 时间复杂度接近最优的通用图传播算法

Houye

发布于 2021-08-26 15:38:42

1.1K0

发布于 2021-08-26 15:38:42

文章被收录于专栏：图与推荐

本期论文解读邀请了中国人民大学博士生王涵之分享其发表在KDD 2021 的论文 《Approximate Graph Propagation》，第二作者为中国人民大学博士生何明国，通讯作者为中国人民大学魏哲巍教授。这篇论文将目前绝大多数的图节点邻近度指标和图神经网络特征传播形式都归纳为一个概括性的图传播范式，针对该图传播范式，这篇论文提出了一个时间复杂度近似最优的通用算法AGP。

论文链接：https://arxiv.org/pdf/2106.03058.pdf

前言： 节点邻近度的高效计算在众多图挖掘和表示学习问题中都有着广泛的应用，例如：社区发现、图神经网络应用中的节点分类问题等。但是，现有工作普遍只着眼于某一特定的邻近度指标，而缺乏一种通用的算法以同时支持绝大多数节点邻近度指标的高效计算。本篇论文将多种节点邻近度指标归纳为一种通用的计算范式，针对该通用范式提出了一种可以高效计算绝大多数节点邻近度指标的算法AGP。通过严格的理论分析，我们证明了AGP算法可以在近似最优的时间复杂度下完成所有符合该通用范式的邻近度指标的计算，例如Personalized PageRank、Heat Kernel PageRank、transition probability、Katz、图神经网络中的特征传播过程等。我们以社区发现和图神经网络应用中的节点分类场景为例，借助大量的实验证明了AGP算法的有效性。特别地，在以GNN为基础的节点分类问题中，AGP成功将多种GNN模型的支持数据大小扩展到了目前最大的公开数据集 Papers100M ，AGP可以在半小时内单机单卡完成Papers100M上的训练过程。

一、研究背景

1. 图传播简介：

图是一类重要的数据结构，因为其强大的关系表达能力而被广泛用于刻画真实的网络结构，例如社交网络、论文引用网络、道路交通网络等。在抽象表达中，图

G=(V,E)

由节点集

和边集

组成，在图学习的场景中，图节点或边上还会包含特征信息。如何准确理解图结构，如何高效捕获图结构和附加特征的信息，如何进一步深入挖掘图结构、图特征和特定任务间的关系，是图分析与学习领域的重点研究问题之一。

在目前的研究中，大多数工作尝试借助图传播来捕获图结构信息（在图学习任务中也同时聚合了特征信息），最终借助图传播的结果进行下游任务的分析和预测。例如，在社区发现中，现有工作大多按照某种图节点邻近度（node proximity，从给定源节点出发在图结构上进行概率传播，并依据计算得到的图上各节点关于源节点的邻近度概率值，借助sweep算法[Spielman & Teng, STOC'04]寻找源节点所在的社区。在图神经网络（GNN）中，可扩展的GNN普遍会先将给定的初始特征带入图结构中，基于图结构进行特征传播，再将特征传播的结果视为图上各节点的表示向量，并使用该表示向量完成下游任务的训练。因此，图传播过程的时间效率和质量对整个图分析与学习任务至关重要。

在以往的工作中，图传播框架普遍由某种图节点邻近度指标的计算形式给出，常用的图节点邻近度指标包括：PageRank、Personalized PageRank、Heat Kernel PageRank、转移概率（transition probability）、Katz等，下表列出了这些图节点邻近度指标的计算式：

在上表中，

\boldsymbol{\pi}

表示图传播向量，

\mathbf{A}

为给定图结构的邻接矩阵，

\mathbf{D}

为给定图结构的度数矩阵，

\alpha

、

\beta

、

均为给定参数。目前在大多数的可扩展图神经网络（GNN）（即图传播与训练过程解耦的GNN）中，特征传播的方式也遵从某一指定的节点邻近度，下表列出了三种代表性的GNN模型所采用的图传播框架。我们发现，这三种GNN模型的特征传播方式基本完全遵从节点邻近度的计算式，区别在于传统的（逆）概率转移矩阵

\mathbf{AD^{-1}} (\mathbf{D}^{-1}\mathbf{A})

被替换为了标准化概率转移矩阵

\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}

、图特征传播的最大层数限制为

、起始状态下的one-hot向量被替换为特征向量。

2. 现存问题：

如前所述，图传播过程的计算效率至关重要。但是，现有算法普遍只着眼于某一种图节点邻近度指标，设计针对性的优化算法。因此，这些优化算法普遍不具有通用性，仅能改进某一种特定的节点邻近度。然而，现有的图节点邻近度指标各有侧重，在不同的应用问题中，研究者会根据各种邻近度指标的特性，选出最适合的邻近度指标进行图传播。例如，社区发现领域普遍采用Heat Kernel PageRank (HKPR) 结果寻找包含源节点的社区，在图神经网络模型中，SGC、APPNP、GDC三种GNN方法分别采用转移概率、PPR和HKPR进行特征传播。因此，我们归纳出如下两个重要问题：

是否可以将现有的图节点邻近度指标 / GNN特征传播框架归纳为一个通用的图传播方式？
是否可以面向这一通用图传播方式，设计一种时间复杂度近似最优的算法，以同时提高所有图传播方式的效率？

3. 核心贡献：

在本篇论文中，我们提出了一种通用的图传播范式，其可以概括目前绝大多数的图节点邻近度指标（如PageRank、Personalized PageRank (PPR)、Heat Kernel PageRank (HKPR)、转移概率（transition probability）、Katz等）和相对应的GNN特征传播模型。该通用范式如下所示

其中，

\boldsymbol{\pi}

为图传播向量，

w_i

为各传播层的权重参数，

\mathbf{D}^{-a}\mathbf{A}\mathbf{D}^{-b}

为通用概率转移矩阵，

、

是两个可调节参数（当

a=0

、

b=1

时即为传统的概率转移矩阵

\mathbf{A}\mathbf{D}^{-1}

，当

a=b=\frac{1}{2}

时即为GNN中常用的标准化概率转移矩阵

\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}

，向量

\mathbf{x}

表示初始图信号（在图节点邻近度计算中常设为one-hot向量，在图神经网络（GNN）中常设为给定的特征向量）。由上图可以看到，通过调节参数

w_i

、

\mathbf{x}

的设置，该通用范式可以转化为各种节点邻近度计算式 / GNN特征传播框架。

针对上述图传播范式，在本篇论文中，我们提出了通用图传播算法AGP，首次在近似最优的时间复杂度内，得到通用图传播向量

\boldsymbol{\pi}

在误差要求范围内的估计结果。

(\varepsilon_r, \delta)

相对误差】定义： 对于由通用范式计算得到的图传播向量

\boldsymbol{\pi}

，给定相对误差阈值

\delta

，我们要求AGP得到的图传播向量

\boldsymbol{\pi}

的估计结果

\hat{\boldsymbol{\pi}}

满足，对于图上任意节点

v\in V

，如果

|\boldsymbol{\pi}(v)|>\delta

, 则

|\boldsymbol{\pi}(v)-\hat{\boldsymbol{\pi}}(v)| \leq \varepsilon_{r} \cdot \boldsymbol{\pi}(v)

以高概率成立（如成功概率为99%）。在本篇论文中，我们将

\varepsilon_r

看作常数，以常数相对误差、

\delta

误差阈值来约束近似图传播结果的准确率。

二、通用图传播算法AGP：

1. 现有算法回顾：

在现有研究中，已有一些算法可以被扩展至通用图传播框架下，如Monte-Carlo随机游走和确定性传播 (Deterministic propagation) [Andersen et al., FOCS'06]等。但是这些方法普遍存在不够通用、时间复杂度较高等问题，接下来我们将具体分析Monte-Carlo随机游走和确定性传播两种算法的局限。

Monte-Carlo随机游走 [Fogaras et al., Internet Mathematics 2005]：

如果图传播框架为：

\boldsymbol{\pi}=\sum_{i=0}^\infty w_i \left(\mathbf{A}\mathbf{D}^{-1}\right)^i \cdot \mathbf{x}

，则我们可以借助Monte-Carlo随机游走得到

\boldsymbol{\pi}

的估计。具体方法为：将向量

\mathbf{x}

看作随机游走起始节点的概率分布（如果

||\mathbf{x}||_1\neq 1

，则可以先对

\mathbf{x}

做column normalization，即按照

\frac{\mathbf{x}}{|| \mathbf{x} ||_1}

所指示的概率分布选择起始节点，在传播过程结束后，对传播结果乘

||\mathbf{x}||_1

以保证结果无偏），从所选起始节点出发产生足够多条随机游走，第

步游走以

\frac{w_i}{Y_i}

的概率停止在当前节点，以

\left(1-\frac{w_i}{Y_i}\right)=\frac{Y_{i+1}}{Y_i}

的概率随机走向当前节点的任一邻居。最后，我们用所有随机游走中，停止在节点

的游走数占总随机游走数的比例作为对节点

图传播结果

\boldsymbol{\pi}(u)

的估计。

在通用图传播范式

\boldsymbol{\pi}=\sum_{i=0}^\infty w_i \left(\mathbf{D}^{-a}\mathbf{A}\mathbf{D}^{-b}\right)^i \mathbf{x}

中，如果

a+b=1

，则该范式可以被等价写为：

\boldsymbol{\pi}=\mathbf{D}^{-a}\cdot \sum_{i=0}^\infty w_i \left(\mathbf{A}\mathbf{D}^{-1}\right)^i \cdot \left(\mathbf{D}^a\mathbf{x} \right)

。我们可以将

\left(\mathbf{D}^a\mathbf{x} \right)

整体看作一个概率分布，用于选择随机游走的起始节点。按照上述游走方式进行图传播，并对返回的随机游走结果乘

\mathbf{D}^{-a}

作为图传播向量

\boldsymbol{\pi}

的估计。

Monte-Carlo随机游走的优势在于直观、灵活，但是其只能处理

a+b=1

的情形，而不支持类似Katz

\left(\boldsymbol{\pi}=\sum_{i=0}^\infty \beta^i \mathbf{A}^i \mathbf{e}_s \right)

的邻近度指标。其次，Monte-Carlo随机游走的估计结果方差较大，为了达到估计结果的误差要求，需要产生大量的随机游走，时间消耗较大。

确定性传播 (Deterministic propagation) [Andersen et al., FOCS 2006]：

确定性传播算法的原型来源于Andersen等人在FOCS'06论文《Local Graph Partitioning using PageRank Vectors》里提出的Forward Search方法，虽然原论文提出Forward Search的目标是估计单源Personalized PageRank（即

\boldsymbol{\pi}=\sum_{i=0}^\infty \alpha (1-\alpha)^i \left(\mathbf{A}\mathbf{D}^{-1}\right)^i \mathbf{e}_s

），但是该方法可以被很容易地拓展用于通用图传播范式的估计问题中。

在确定性传播算法中，其将图传播向量

\boldsymbol{\pi}

的计算问题拆分为对各层传播结果的估计问题，即

\boldsymbol{\pi}=\sum_{i=0}^\infty \boldsymbol{\pi}^{(i)}

，其中

\boldsymbol{\pi}^{(i)}=\alpha (1-\alpha)^i \left(\mathbf{D}^{-a}\mathbf{A}\mathbf{D}^{-b}\right)^i \mathbf{e}_s

表示传播

步时的图传播向量。我们发现，对于现实生活中使用的绝大多数节点邻近度指标，超过

L=\log{\frac{1}{\delta}}

层的图传播结果均小于相对误差阈值

\delta

，即我们可以仅用前

层图传播估计结果的加和

\hat{\boldsymbol{\pi}}=\sum_{i=0}^L \hat{\boldsymbol{\pi}}^{(i)}

，作为图传播向量

\boldsymbol{\pi}

的估计值，这里

\hat{\boldsymbol{\pi}}^{(i)}

表示第

层传播结果

\boldsymbol{\pi}^{(i)}

的估计值。

具体而言，在计算第

层图传播向量的估计结果

\hat{\boldsymbol{\pi}}^{(i)}

时，我们对图上各节点

都维护两个变量：residue

\mathbf{r}^{(i)}(u)

和 reserve

\hat{\boldsymbol{\pi}}^{(i)}(u)

。其中， residue

\mathbf{r}^{(i)}(u)

记录图传播在第

步走到节点

的概率，reserve

\hat{\boldsymbol{\pi}}^{(i)}(u)

对应图传播在第

步走到节点

并停止在节点

的概率。在从第

层到第

(i+1)

层的图传播中，所有在第

层的residue

\mathbf{r}^{(i)}(u)>0

的节点

，都将其所拥有的一部分residue：

(1-\alpha)\mathbf{r}^{(i)}(u)

传播到其邻居节点

\forall v\in N_u

在第

(i+1)

层的residue

\mathbf{r}^{(i+1)}(v)

上。此外，节点

在第

层剩下的residue：

\alpha\mathbf{r}^{(i)}(u)

被转移到其在第

层的reserve

\boldsymbol{\hat{\pi}}^{(i)}(u)

上。上述过程的示意图如下所示：

回顾上述过程，确定性传播借助确定性的概率更新，有效避免了Monte-Carlo随机游走方法存在的估计结果方差大的问题，同时也可以支持转移概率矩阵

\mathbf{D}^{-a}\mathbf{A}\mathbf{D}^{-b}

中

a+b\neq 1

的情况。

但是，确定性传播的问题在于不够灵活，例如在下面这种bad case中，如果我们想要估计节点

到节点

的传播概率，根据确定性传播算法，从

出发经过一步传播就需要更新图上绝大多数节点

(v_1,v_2,...,v_n)

的residue值，从而造成了较大的时间代价。其实在下述情景中，我们只需从节点

出发产生一条随机游走，就可以准确估计出从

传播到节点

的概率（任意一条随机游走，如果不在中途停止，都可以准确地从节点

走到

，且没有估计方差)。

2. AGP算法：

受上述Monte-Carlo随机游走和确定性传播方法的启发，在本篇论文中，我们提出了通用算法AGP。AGP算法将Monte-Carlo随机游走和确定性传播两种方法的优势巧妙结合，从而在近似最优的时间复杂度下，完成了图传播向量

\boldsymbol{\pi}

在

(\varepsilon_r, \delta)

相对误差下的估计，其中相对误差

\varepsilon_r

为常数。

具体而言，对于图传播范式

\boldsymbol{\pi}=\sum_{i=0}^L w_i \left(\mathbf{D}^{-a}\mathbf{A}\mathbf{D}^{-b}\right)\mathbf{x}

（如前所述，我们只关注前

L=\log{\frac{1}{\delta}}

层的图传播结果估计，为了表达简便，这里我们省去了

\boldsymbol{\pi}

中

层后的加和），当第

层的节点

向其在第

(i+1)

层的邻居节点

进行传播时，节点

residue

\mathbf{r}^{(i+1)}(v)

的增加值为

\mathbf{r}^{(i+1)}(v)=\mathbf{r}^{(i+1)}(v)+\frac{Y_{i+1}}{Y_i}\cdot \frac{\mathbf{r}^{(i)}(u)}{d_v^a \cdot d_u^b }

，这里

Y_i=w_i+w_{i+1}+...

。

我们注意到，对于节点

的所有邻居节点

，其residue

\mathbf{r}^{(i+1)}(v)

的增长量与节点

的度数成反比。因此，我们可以提前将图上各节点邻接表中的节点按照度数增序排列，在需要更新节点

邻居节点的residue时，我们只需按顺序扫描节点

的邻接表，判断当前邻居节点

对应的residue 增量

\frac{Y_{i+1}}{Y_i}\cdot \frac{\mathbf{r}^{(i)}(u)}{d_v^a \cdot d_u^b }

是否超过阈值（分析得到该阈值和相对误差阈值

\delta

处于同一级别）。我们仅确定性地更新residue增量超过阈值的节点（如下图所示的节点

v_1

、

v_2

），同时仅从剩余节点中采样部分节点进行residue的更新（即采样部分节点进行图传播，如下图中的节点

v_4

）。值得注意的是，这里我们之所以不直接忽略那些residue增量小于阈值的节点，而需要补充一个采样操作，是为了保证估计结果的无偏性。

以上图为例，节点

v_1, v_2, ..., v_n

的度数都相同，因此节点

向节点

v_1, v_2, ..., v_n

进行图传播时，节点

v_1, v_2, ..., v_n

的residue增量

\frac{Y_{1}}{Y_0}\cdot \frac{\mathbf{r}^{(0)}(s)}{d_v^a \cdot d_s^b }

也都相同。当这一增量小于阈值时，如果我们只是简单地忽略所有residue增量小于阈值的节点，则会导致从

到

的传播结果为0，从而超出误差要求。因此，即使residue增量小于阈值，我们仍需要额外进行采样操作，以避免类似情况出现。

针对residue增量

\frac{Y_{i+1}}{Y_i}\cdot \frac{\mathbf{r}^{(i)}(u)}{d_v^a \cdot d_u^b }<\delta

的节点，我们以

\frac{1}{\delta}\cdot \left(\frac{Y_{i+1}}{Y_i}\cdot \frac{\mathbf{r}^{(i)}(u)}{d_v^a \cdot d_u^b }\right)

的概率采样节点

,对于被采样到的节点

，更新其residue：

\mathbf{r}^{(i+1)}(v)=\mathbf{r}^{(i+1)}(v)+\delta

。因此，节点

的residue的期望增量仍然是

\delta\cdot \frac{1}{\delta}\cdot \left(\frac{Y_{i+1}}{Y_i}\cdot \frac{\mathbf{r}^{(i)}(u)}{d_v^a \cdot d_u^b }\right)=\frac{Y_{i+1}}{Y_i}\cdot \frac{\mathbf{r}^{(i)}(u)}{d_v^a \cdot d_u^b }

，采样结果是无偏的。

值得注意的是，在上述对采样过程的描述中，我们其实遗漏了一个关键问题：如何能在不需要逐一查看各节点的前提下，选出采样到的节点，同时保证采样过程是独立的呢？ 之所以存在这一问题，原因在于：如果我们逐个判断各节点是否被采样到，则花费的时间代价和依次更新所有邻居节点

的residue的代价一样，无法达到节省时间的目标。因此，我们希望采样过程的时间消耗仅与最后采样到的节点个数相关。为了解决这一问题，我们采用了一种巧妙的采样技术Subset Sampling [Bringmann et al. ICALP 2012]，其对应的采样代价与输出大小基本相同（仅多一个log的系数)。至此，通过结合确定性传播和基于Subset Sampling的独立采样，AGP算法最终可以在

O\left(\frac{L^2}{\delta}\cdot \sum_{i=1}^L \left\|Y_i \cdot \left(\mathbf{D}^{-a}\mathbf{A}\mathbf{D}^{-b}\right)^i \cdot \mathbf{x}\right\|_1\right)

的时间复杂度下，得到图传播向量

\boldsymbol{\pi}

在

(\varepsilon_r, \delta)

相对误差下的估计结果。在绝大多数情况下（本篇论文中提到的所有节点邻近度指标和图神经网络模型均满足），这一时间复杂度与输出大小处于同一级别（忽略log项)，因此我们认为AGP拥有近似最优的时间复杂度。

Subset Sampling [Bringmann et al. ICALP 2012]: 我们可以将Subset Sampling技术针对的问题抽象为：对于节点

v_1, v_2, ..., v_n

，每个节点

v_i

都对应一个采样概率

p_i=c\cdot \frac{1}{d_{v_i}^a}

，

是所有节点共有的因子，不同节点的采样概率间相互独立。如何能面向这

个节点完成独立采样，使得采样过程的时间消耗与输出大小处于同一级别，即采样复杂度

T(n)=\tilde{O}\left(\sum_{i=1}^n p_i\right)

，这里

\tilde{O}

表示忽略log因子。在subset sampling中，其将所有待采样节点按照度数大小分为

\log{n}

组，度数处于区间

[2^k, 2^{k+1})

的节点在第

组。我们注意到，在同一组内，最大的采样概率不超过最小采样概率的

2^a<2

倍。对于同一组（e.g. 第

组）内的节点，我们使用该组最大的采样概率

p^{*}_k

对该组所有节点进行采样。这里我们可以借助二项分布采样的方法，先产生一个服从二项分布

B(n_k, p^{*}_k)

的随机数

\ell_k

（这里

n_k

表示第

组的节点数），再独立产生

\ell_k

个均匀随机数，取出节点ID与这

\ell_k

个随机数对应的节点作为这一组的 预采样结果 。最后，为了保证采样结果的正确性，我们还需对所有预采样节点进行一次修正检查，对于第

组的预采样节点

v_j

，我们以

\left(1-\frac{p_{v_j}}{p^{*}_k}\right)

的概率拒绝节点

v_j

。通过这一修正检查的节点成为最终的采样节点。上述过程的时间复杂度为

O\left(\sum_{i=1}^n p_{v_i}+\log{n}\right)

，在忽略log因子时，与输出大小处于同一级别。上述过程的示意如下图所示。

三、实验结果：

为了验证AGP算法的有效性，我们分别在社区发现和基于图神经网络模型的节点分类两种应用场景下进行了实验。

社区发现： 目前大多数的社区发现研究都遵从相同的范式：（1）给定社区发现的种子节点

；（2）计算图上各节点关于源节点

的Heat Kernel PageRank (HKPR) 这一节点邻近度指标的分数值；（3）依据各节点的HKPR值，借助sweep操作，找到节点

所在的导度最小的社区。导度是一种衡量社区发现质量的指标，越小的导度值说明社区发现的质量越高。在实验环节，我们首先比较了AGP算法计算HKPR指标的query time-MaxError 的trade-off图线是否优于其他baseline方法，同时，我们还绘制了query time-导度的trade-off图线用于衡量各种方法社区发现的质量。

基于图神经网络(GNN)的节点分类： 我们借助AGP算法提升了现有GNN模型的可扩展性，具体包括SGC、APPNP、GDC。这里APPNP和GDC指将图特征传播和预测解耦后，在图传播过程分别借助PPR、HKPR进行特征传播的方法，与原始论文所述方法不尽相同。从下图实验结果中可以看到，借助AGP算法加速后的GNN模型，可以在更短的时间内与达到相同的accuracy。