【WWW2022】互信息压缩的紧凑图结构学习

题目：Compact Graph Structure Learning via Mutual Information Compression

作者：Nian Liu, Xiao Wang, Lingfei Wu, Yu Chen, Xiaojie Guo, Chuan Shi

https://arxiv.org/abs/2201.05540

简介：图结构学习（GSL）的目的是同时学习最优图结构以及图神经网络（GNNs）参数，可大致分为基于单视图和基于多视图两类。其中，基于多视图的GSL能从原始结构中抽取出多个基础视图，利用多方面的知识，从而来综合评估最优的最终视图。那么，如何有原则地从多个视图中评估出最优结构，如何定义“最优”的概念，尚未有理论的指导。我们认为，本质上，最优图结构应该仅包含关于下游任务中最精简的信息，不多不少，从而能对于标签做出最精确的预测。如果学到的结构吸收了很多和标签无关的信息，那它会易受到对抗攻击的影响；反之，如果它仅包含关于标签有限的信息，模型就无法支撑下游任务。总之，最优结构应该包含最小但却充分的关于标签的信息，我们称其为最小充分结构，它是有效性和鲁棒性的平衡。

然而，获得这样一个最小充分结构需要解决两个挑战：（1）如何确保最终视图的最小以及充分？为了达到充分，最终视图应该充分由标签指导，从而尽可能多地包含和标签有关的信息；为了达到最小，我们需要限制信息从基础视图向最终视图的流动。因此，为了达到最小与充分，我们需要思考基础视图、最终视图以及标签三者间的关系；（2）如何确保基础视图的有效性？作为最终视图的信息源，基础视图需要保证较高质量。一方面，基础视图同样需要包含标签的信息，从而保证最终视图的表现效果；另一方面，不同视图间应相互独立，这样能消除彼此间的冗余，为最终视图提供多方面的关于标签的知识。

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