会员服务 ·

WWW2022｜去芜存菁：基于互信息压缩的紧致图结构学习

2022 年 1 月 21 日 专知

作者：北邮GAMMA Lab硕士生刘念

题目：Compact Graph Structure Learning via Mutual Information Compression

会议：TheWebConf 2022

论文链接： https://arxiv.org/abs/2201.05540

图神经网络依赖于良好的图结构已经是共识，在图结构被广泛关注的今天，我们言必称图结构有用。但实际中会发现其又并不全是有用信息，毕竟图数据的结构复杂多样，信息繁多。那么一个本质问题出现了：能否原则性地指出何为最优的图结构？怎样可以定义最优？

1 介绍

图结构学习（GSL）的目的是同时学习最优图结构以及图神经网络（GNNs）参数，可大致分为基于单视图和基于多视图两类。其中，基于多视图的GSL能从原始结构中抽取出多个 基础视图，利用多方面的知识，从而来综合评估最优的 最终视图，例如GEN[1]。那么， 如何有原则地从多个视图中评估出最优结构，如何定义“最优” 的概念，尚未有理论的指导。我们认为，直观上，最优图结构应该满足如下要求： 仅包含关于下游任务中最精简的信息，不多不少包含下游任务中的相关信息，可以保证对下游任务的预测准确性；而这种信息又需要不多不少，则可以避免除了与下游任务相关信息之外的冗余信息或者噪音信息，保证鲁棒性。总结来，即：少一点信息，不够准确；多一点信息，不够鲁棒。满足这些要求，我们称其为最优结构，命名为 最小充分结构，即包含最小但却充分的关于标签的信息，它是有效性和鲁棒性的平衡。

然而，获得这样一个最小充分结构需要解决两个挑战：

（1）如何确保最终视图的最小以及充分 首先是如何将这一准则形式化。为了达到充分，最终视图应充分由标签指导，从而尽可能包含和标签有关的信息；为了达到最小，需要限制信息从基础视图向最终视图的流动。

（2）如何确保基础视图的有效性 作为最终视图的信息源，基础视图需要保证较高质量。一方面，基础视图需要包含标签的信息；另一方面，不同视图间应相互独立，消除彼此间的冗余。

为了解决上述挑战，在本文中我们通过互信息压缩来学习紧致的图结构，提出CoGSL模型。CoGSL利用两个基础视图作为输入，设计视图评估器加以调整，再将两个调整后的视图自适应聚合成最终视图。之后，我们提出 “最小充分结构” 的正式定义，并从理论上证明， 在保障基础视图和最终视图效果的同时，需要最小化两两视图间的互信息。为了有效地评估不同视图间的互信息，我们基于InfoNCE损失设计相应的互信息估计器。最后，我们采用三折优化去训练上述框架。

2 模型介绍

模型整体流程如上图所示。本节将概述CoGSL框架及相应理论，具体细节请参见论文。

2.1 基础视图选取

给定图，CoGSL首先从原始结构中抽取两种基础视图和，作为模型的输入。抽取的范围是：（1）Adjacency matrix（2）Diffusion matrix（3）Subgraph（4）KNN graph，这四种结构分别从不同角度考察了拓扑空间和特征空间中图的性质。

2.2 视图评估器

视图评估器的作用是调整和，使它们能更灵活地生成最终视图，如上图（b）所示。以视图为例，首先用GCN[2]层来得到节点表示：

其中是节点特征。以节点和为例，利用来评估两点间的连边权重：

为了节省时间和空间开销，仅评估有限的范围，例如是Adjacency matrix，则选定为k-hop内的邻居，k是超参数。进而归一化节点与内其他节点间的权重，得到相应的概率：

由此构建矩阵，其中每个元素均由上式计算得到。结合** **得到评估后的视图：

其中是组合系数，的第行表示为。的评估与之类似，最后得到评估后的视图。

2.3 视图融合

此节的目的是为每个节点自适应地融合和，得到最终视图。我们利用节点的预测概率作为视图融合的证据，并将大的权重赋予给更置信的视图，如上图（c）所示。首先，利用两层GCN得到节点在每个视图下的预测结果：

节点在和下的预测分别表示为和，并据此计算出两视图对于节点的重要性。以计算的重要性为例：

其中，和分别表示的最大值和次大值，和是超参数。上述公式表明，预测结果的最大值越大，最大值和次大值间的差值越大，则该视图的重要性越大。同理，可得的重要性。归一化和，得到相应的权重和，并加权融合和：

将其他的节点同样地经过上述视图融合过程，并将这些融合结果合成最终视图。

2.4 最小充分结构V*

首先我们给出最小充分结构的定义，如下：

之后，我们提出了如下的命题：

命题1要求、和都包含标签的信息，命题2要求最小化两两视图间的互信息。我们证明，在命题1成立的前提下，命题2可推导出如下的结果：

其中，大于号右侧的第二、三项会随着优化的进行而趋于0。也就是说，最小化两两视图间的互信息可达到如下目的：（1）给定标签，不再包含其他信息，从而成为最小成分结构；（2）和只共享的信息，也就是标签的信息，去除了视图间的冗余。

在评估视图间的互信息时，我们采用InfoNCE[3]损失。首先利用一层GCN得到、和的节点表示{ }，再利用两层MLP将它们投影到互信息评估空间中，得到{ }。借鉴GCA[4]，以 , 为例，给出如下InfoNCE损失：

其过程如下所示：

我们最终迭代优化如下的三个损失：

优化分类器

优化互信息评估器

优化视图估计器

3 实验

3.1 节点分类

可以看出，与其他的GS方法相比，我们的模型都有一定程度的效果提升，这表明了准则的有效性，即可使学得的最小充分结构能包含更准确的信息去预测节点标签。

3.2 鲁棒性实验

拓扑攻击下的表现

特征攻击下的表现

无论是在拓扑攻击或是特征攻击层面，相较于其他baseline，我们提出的CoGSL都表现出了很强的鲁棒性，而这鲁棒性的获得，正是源于我们对最小充分结构的刻画，使得最终视图尽可能只保留和label有关的信息。

3.3 互信息分析

上图中，横坐标越大表示限制视图间互信息的力度越大，纵坐标是模型表现。可以看出，最优点时处于中间值，表明在强调分类准确的同时，要尽可能得压缩视图间的互信息，从而滤除噪声的干扰；但压缩也不能过猛，否则会过滤掉有用的信息，导致效果下降。

4 参考文献

[1] Ruijia Wang, Shuai Mou, Xiao Wang, Wanpeng Xiao, Qi Ju, Chuan Shi, and Xing Xie. 2021. Graph Structure Estimation Neural Networks. In WWW. 342–353.

[2] Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR.

[3] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. 2018. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748 (2018).

[4] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2021. Graph contrastive learning with adaptive augmentation. In WWW. 2069–2080.

本期责任编辑：杨成

本期编辑：刘佳玮

专知便捷查看