Tailin Wu 等作者魔王编辑

什么是优秀的图表示?斯坦福提出首个信息论原则——图信息瓶颈

对于图结构数据而言,什么是「优秀」的表示?斯坦福研究者对此进行了重新思考,并提出学习稳健图表示的信息论原则——图信息瓶颈 (GIB)。研究者基于该原则构建了两个 GNN 模型:GIB-Cat 和 GIB-Bern,二者在抵御对抗攻击时取得了优异的性能。

图表示学习旨在基于图结构数据学习表示,并用于节点分类、链路预测等下游任务。由于节点特征和图结构包含重要信息,因此图表示学习任务具备一定的挑战性。图神经网络(GNN)融合了来自节点特征和图结构的信息,因而具备优秀的性能。

近期,很多研究开始关注如何开发更强大的 GNN,使之拟合更复杂的图结构数据。然而,目前 GNN 仍然面临一些问题。例如,邻近节点的特征包括一些无用信息,可能对当前节点的预测产生负面影响。此外,GNN 依赖于通过图的边进行消息传递,这使它容易遭受针对图结构的噪声和对抗攻击。

近日,来自斯坦福大学的研究者希望解决以上问题,并重新思考:对于图结构数据而言,什么是「优秀」的表示?具体而言,信息瓶颈 (IB) 为表示学习提供了核心原则:最优表示应包含适合下游预测任务的最少充足信息。IB 鼓励表示最大程度地包含与目标相关的信息,以使预测结果尽可能准确(充足)。另一方面,IB 遏制表示从数据中获取与预测目标无关的额外信息(最少)。基于这一学习范式学得的模型自然而然可以避免过拟合,并对对抗攻击具备稳健性。


  • 论文地址:https://arxiv.org/pdf/2010.12811.pdf

  • 项目地址:http://snap.stanford.edu/gib/

  • GitHub 地址:https://github.com/snap-stanford/gib


然而,将 IB 原则扩展到图表示学习的过程面临着以下两个独特的挑战:

  • 首先,之前利用 IB 的模型假设数据集中的训练样本是独立同分布的 (i.i.d.)。对于图结构数据而言,该假设不成立,因此按照 IB 原则训练模型较为困难;

  • 此外,结构信息对于表示图结构数据是必不可少的,但此类信息比较分散,因而很难进行优化。如何恰当地建模和从图结构中提取最少充足信息带来了另一项挑战。


解决办法:图信息瓶颈 (GIB)

该研究基于 IB 提出了一种信息论原则——图信息瓶颈 (Graph Information Bottleneck, GIB),专门为图结构数据的表示学习打造。GIB 从图结构和节点特征中提取信息,并鼓励学得表示中的信息满足最少和充分两个原则(参见下图 1)。

为了克服非独立同分布数据带来的挑战,研究者利用图结构数据的局部依赖假设来定义最优 P(Z|D) 的搜索空间 Ω,其遵循马尔可夫链层级化地从特征和图结构中提取信息。研究者表示,这项研究为基于图结构数据的监督式表示学习提供了首个信息论原则。


图 2:GIB 原则利用局部依赖假设。


并得到:

研究者还为 GIB 扩展了变分上下界,使其更适合 GNN 的设计与优化。具体而言,该研究提出变分上界,用于约束从节点特征和图结构提取的信息;并用变分下界来最大化表示中的信息,以预测目标。

研究者将 GIB 原则应用于图注意力网络 (GAT),利用 GAT 的注意力权重采样图结构,从而缓解优化和建模离散图结构的难度。研究者还分别基于类别分布和伯努利分布设计了两个采样算法,提出两个模型 GIB-Cat 和 GIB-Bern。GIB-Cat 和 GIB-Bern 算法参见 Algorithm 2 和 Algorithm 3,Algorithm 1 则展示了这两种算法的基础框架。

GIB-Cat 和 GIB-Bern 算法。

GIB-Cat 和 GIB-Bern 算法的基础框架。


实验表明,这两个模型可以提升标准基线模型的稳健性,性能超过其他 SOTA 防御模型。GIB-Cat 和 GIB-Bern 将对抗扰动情况下的分类准确率分别提升了 31.3% 和 34.0%。


实验

对抗攻击

研究者对比了不同模型对对抗攻击的稳健性,实验结果参见下表 1。

从中可以看出,GIB-Cat 在 Cora 和 Pubmed 上的分类准确率相比 GAT 分别平均提高了 8.9% 和 14.4%,GIB-Bern 提高了 8.4% 和 14.6%,这表明 GIB 原则可以有效提升 GNN 的稳健性。值得注意的是,当扰动数值为 1 时,GIB-Cat 和 GIB-Bern 在 Pubmed 上的分类准确率相比 GAT 分别提升了 31.3% 和 34.0%。



特征攻击

为了进一步确认 IB 对节点特征的有效性,研究者向节点特征引入随机扰动。实验结果参见下表 3:



从中可以看到,在不同特征噪声比率情况下,GIB-Cat 和 GIB-Bern 持续优于不使用 IB 的其他模型,尤其是当特征噪声比率较大 (λ = 1.5) 时,仅具备结构 IB 的 AIB 模型性能稍逊于或等同于 GIB 模型。这表明,当特征攻击成为扰动主要来源时,GIB 可使模型具备更强的稳健性。

理论图表示学习斯坦福大学
相关数据
重采样技术

重采样是指根据一类象元的信息内插出另一类象元信息的过程。在遥感中,重采样是从高分辨率遥感影像中提取出低分辨率影像的过程。常用的重采样方法有最邻近内插法(nearest neighbor interpolation)、双线性内插法(bilinear interpolation)和三次卷积法内插(cubic convolution interpolation)。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

过拟合技术

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

独立同分布技术

在概率论与统计学中,独立同分布(缩写为IID)是指一组随机变量中每个变量的概率分布都相同,且这些随机变量互相独立。一组随机变量独立同分布并不意味着它们的样本空间中每个事件发生概率都相同。例如,投掷非均匀骰子得到的结果序列是独立同分布的,但掷出每个面朝上的概率并不相同。

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

信息论技术

信息论是在信息可以量度的基础上,研究有效地和可靠地传递信息的科学,它涉及信息量度、信息特性、信息传输速率、信道容量、干扰对信息传输的影响等方面的知识。通常把上述范围的信息论称为狭义的信息论,又因为它的创始人是香农,故又称为香农信息论。

马尔可夫链技术

马尔可夫链,又称离散时间马尔可夫链,因俄国数学家安德烈·马尔可夫得名,为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质:下一状态的概率分布只能由当前状态决定,在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。

节点分类技术

节点分类任务是算法必须通过查看其邻居的标签来确定样本的标记(表示为节点)的任务。

推荐文章
暂无评论
暂无评论~