ICML'20 通过图稀疏化来提升GNN的鲁棒性

Houye

发布于 2021-07-08 15:48:00

8560

fig0

论文标题：Robust Graph Representation Learning via Neural Sparsification
作者：Cheng Zheng; Bo Zong; Wei Cheng; Dongjin Song; Jingchao Ni; Wenchao Yu; Haifeng Chen; Wei Wang
论文地址：https://songdj.github.io/publication/icml-20/icml-20.pdf
欢迎关注小编知乎：戴鸽

在真实场景下，图经常含有复杂的邻居信息，特征和邻居个数都很多。尽管图网络通过邻居聚合来高效的捕获图结构，但仍然一些任务无关的节点被加入，使得模型处于次优状态。因此，作者提出了NeuralSparse的方法。这是一种有监督的图稀疏技术，通过去除图中多余与任务无关边，提高模型泛化能力。

1. Introduction

两个节点的连接信息可能与目标下游任务无关(比如偶发的噪音连接，用户偶尔点击一个其并不喜欢的商品)。因此，直接聚合图上原始邻居可能引入了任务无关的信息，进而影响图模型本身的性能（ps：感觉这个可能映照了GCN-LPA，单纯的标签扩散可能都可以带来比较好的结果）。

如下图所示，假设有红蓝两类标签，按照特征来看可以用高斯分布变成两块独立分布。图(a)中展示了直接特征基本找不到明显分界，图(b)中的节点两两相连，随机采周围10个点当做邻居。此时，这种随机采的边信息就和标签信息没有什么太大关系。这时训练一个2层GCN后，可以观察到节点的分布差异更不明显了。而作者的希望的是得到比图(c) DropEdge更好的结果，使得相同标签的节点能够被边链接在一起，进而使得分类边界更明显。

fig1

在以往工作中，有一部分采用无监督方式来进行稀疏图学习，但是其可能无法在下游任务达到最优。另外一部分工作预定义下采样分布，这种方法可能无法适应后续任务，也就是还是和任务本身衔接不够紧密。另外仍然有监督学习的方法，但这些方法运算相对困难。

因此，作者提出的NeuralSparse模型是一种能够从下游任务获得反馈，进而抽取与任务强相关边的方法。NeuralSparse主要由2部分组成：稀疏网络和GNN。其中，稀疏网络采用了参数化的稀疏过程。在固定当前边的情况下去找下一个边。在训练过程中，网络由下游任务决定稀疏化策略。在测试过程中，数据通过稀疏化网络后再进行预测。对于GCN模块，输入是稀疏化后的图，并且切合其下游任务给出特征。在NeuralSparse这样的框架下，作者可以同时优化图结构并且获得稀疏解。最后希望如图(d)一样，其稀疏化过程比随机的边去除更加有效。

2. Method

2.1. 方法总概

从整体上来看，这套框架的loss服务于两个网络，一个对应于找子网络的Sparsification Network，一个对应于通过稀疏化以后，与下游任务紧密相连的GNN分类网络。

fig2

一个带节点特征的图定义为

G=(V,E,A)

，Y表示下游任务预测，用

表示待学习的稀疏图。

P(Y \mid G) \approx \sum_{g \in \mathbb{S}_{G}} P(Y \mid g) P(g \mid G)

由于最终的稀疏图是需要也能够达到一定预测准确率的(对Y的预测)，所以作者将原来的概率分解为所有稀疏图

在原始图中的概率：

P(Y \mid G) \approx \sum_{g \in \mathbb{S}_{G}} P(Y \mid g) P(g \mid G)

由于图的链接比较复杂，所以更近一步，作者采用了估计函数

来近似分布，

\theta

与

\phi

表示两套参数系统，

\sum_{g \in \mathbb{S}_{G}} P(Y \mid g) P(g \mid G) \approx \sum_{g \in \mathbb{S}_{G}} Q_{\theta}(Y \mid g) Q_{\phi}(g \mid G)

最后结果可以视作多个子图综合的结果，因此，需要找到最适合的两种分布函数Q。

（PS：虽然这里都是约等于，但是在之后的工作可以发现有些约等于是可以变成等于的。比如PGExplainer中有谈到第一个约等于可以用互信息来求得。）

2.2. 模型结构

经过以上粗略的分析以后，就应当具体到如何搭建一个稀疏网络的模型了。与之前的模型框架图对应，模型主要分为两个部分：

稀疏网络：一个多层MLP用来得到子图g，对应

Q_{\phi}

GNN：任意一个GNN，用来对接具体任务，对应

Q_{\theta}

首先，作者使用k-neighbor subgraph 构建子图信息。这样做的原因有两点：

的引入可以直观说明参数量少时可能引起下游任务准确率下降，而过多则可能引入更多无关信息。其次是引入

近邻更容易加速模型运算速度，可以将图分解进行并行计算。

之后，在采样的基础上构建子图，在子图上进行边过滤。由一组一阶邻居节点出发，扩散至

个邻居。

最后，针对过滤操作，作者采用

MLP

来学习边是否需要被过滤。这里

表示被选中的点，

为一阶邻居点。所以

就表示了邻接矩阵

\mathbf{A}

边上的信息。

z_{u, v}=\operatorname{MLP}_{\phi}(V(u), V(v), \mathbf{A}(u, v))

之后，作者采用softmax来计算被选中的边的概率。

\pi_{u, v}=\frac{\exp \left(z_{u, v}\right)}{\sum_{w \in \mathbb{N}_{u}} \exp \left(z_{u, w}\right)}

最后，使用Gumbel-Softmax 表示边是否被包含。其中，

\tau

表示一个温度数值，用来控制离散分布和连续分类密度之间的变化，是一个可调超参。在这里，作者采用退火的方式控制

\tau

的值。

x_{u, v}=\frac{\exp \left(\left(\log \left(\pi_{u, v}\right)+\epsilon_{v}\right) / \tau\right)}{\sum_{w \in \mathbb{N}_{u}} \exp \left(\left(\log \left(\pi_{u, w}\right)+\epsilon_{w}\right) / \tau\right)}

Sparse算法的复杂度仅与原始图的边和顶点个数有关，为

O(km)

，

为边与顶点个数之和。

3. 实验

实验模型分为两部分，一部分是Method部分的基础模型，包括GCN，GraphSage，GIN，GAT，另一部分是稀疏方法，包括不做稀疏，spectral sparsifier and Rank Degree (SS/RD)，DropEdge，LDS，NeuralSparse。

fig3

从表可以发现作者提出的方法可以通过修改数据大幅提高模型性能，并且能够用在很多模型上。

在不同

值上，NeuralSparse也能表现出稳定的效果。

fig4

从transaction数据的可视化结果来看，NeuralSparse可以达到预期的效果，使得图上的无关边尽可能减少。

fig5

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-06-22，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

本文分享自图神经网络与推荐系统微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数据结构

登录后参与评论

0 条评论

热度