1、概述

近年来,随着互联网、物联网等信息技术的飞速发展,图数据规模呈现爆炸式增长,如微信微博等社交网络图数据,蛋白质分子等生物图数据,以及交通通信等基础设施图数据.由于图数据的强大表达能力和普遍存在性,对图数据的处理分析已成为数据挖掘领域的研究热点.图表示学习(graph representation learning)通过将图数据映射到低维、稠密的向量空间,有效地提升了图挖掘的性能与效率[1].其中,图神经网络(graph neural network,GNN)是图表示学习的主流方法之一,在社会计算、商品推荐、交通流量预测等大量应用场景上取得了显著的效果提升[2∼4].尽管图神经网络展现出了强大的能力,但它们大多假设观察到的结构完美地描述了节点之间的关联关系,并将图数据的原始结构作为信息传递的途径,其计算结构与图结构耦合,对数据的质量极为敏感.然而,现实生活中的图数据大多是直接采集的,这些原始图或是由结构化数据自然形成的(如社交网络),或者由一些预定义的规则从原始特征空间中构建的,而这些规则通常与下游任务无关,这导致了原始图结构与适用于特定任务的最佳图结构之间存在偏差;此外,开放环境下的图数据存在大量随机噪声或人为扰动,例如欺诈者为了逃避检测会伪装与正常用户的关联.上述结构噪声信息会导致图神经网络学习到的表征质量严重下降,鲁棒性差[5,6].随着在工业、金融、风控等关键安全领域的深入应用,图神经网络模型面临开放的数据环境以及复杂的决策任务,对其准确性和安全性提出了更高要求.因此,如何找到与下游任务密切相关的结构,避免噪声数据干扰,提高图表征的表达能力和鲁棒性,是图神经网络进一步发展和应用亟待解决的问题.

为了优化图结构的质量、提高图表征学习的鲁棒性,相关研究提出了一系列图结构学习(graph structure learning)方法[7,8],其中大多数方法是基于对结构的先验假设(如假设图中存在社区结构)或显式的结构约束(如稀疏性[9]、低秩性[10]和特征平滑性[10]),并针对下游任务优化邻接矩阵和模型参数.然而,这些结构性质假设或显式约束并不一定适用于所有的数据集和任务.此外,大部分方法都是针对节点级分类任务设计[11],难以适用于图层级的分类或回归任务.图层级任务主要关注对整个图属性的预测,包括图分类(graph classification)、图回归(graph regression)等,在实际应用中均有丰富的场景.例如:在社交领域中可通过社团网络进行分类以发现目标群体[12],对微博转发网络进行分析以发现谣言信息[13];在生化领域可以通过对分子图进行分类实现对某个分子的性质进行预判[14];在交通领域可以通过对交通路网进行图回归分析以预测其平均到达时间[15].少量图层级的结构学习方法也仅关注于节点间的连接优化,忽略了对于图层级任务十分重要的层次结构信息[16].而层次化特性是对图层级任务非常重要的特性之一.例如:社交网络中存在用户之间的直接连接、共同兴趣的群体、社区结构等不同层次的关系;分子图数据中存在原子、功能基团、分子等不同层次的结构特性;因特网、物流网络、金融网络中的节点也通常具有类似于组织结构的层级隶属关系.因此,目前仍然缺乏能够统一度量图结构的质量、去除图结构噪声信息,并保留图结构层次特性的图层级结构学习框架.

回顾上述存在的问题,结构学习的关键是学习与任务密切相关的底层连接结构.在信息论中,信息瓶颈(information bottleneck,IB)原则[17]为度量数据中与任务有关的信息提供了一个有效的框架.信息瓶颈原则是对数据压缩率失真理论(rate distortion theory)的扩展,通过在有效信息保留(relevant information preservation)和噪声信息压缩(noisy information compression)之间进行权衡,约束输出中与任务无关的信息.具体来说,信息瓶颈原则旨在寻求一种对目标信息量最大(即互信息最大),而对输入数据信息量最小(即互信息最小)的表征.基于信息瓶颈原则,学习到的表征对数据噪声更加鲁棒[18,19].本文将信息瓶颈原则扩展到图数据上,并针对图结构的层次特性,提出了一个非线性信息瓶颈[20]指导的层次图结构学习方法NIB-HGSL (hierarchical graph structure learning with nonlinear information bottleneck).NIB-HGSL针对图结构中的不同层级,在信息瓶颈目标函数的指导下,通过采用无关特征掩码和结构学习方法,生成一个新的最小充分图,为下游任务提炼出更加密切相关的图特征与结构信息,进而获得更鲁棒的图表征.NIB-HGSL方法主要包括以下三个步骤:(1)对于每个结构层次,最小充分图生成器模块通过对不相关的节点特征进行掩码,并基于掩码后的特征来学习最小充分图.(2)图神经网络模块将每个层次的最小充分图作为输入,学习图表征和其分布.(3)对各个层次的图表征进行解码并用于分类,学习其与图标签的联合分布.整个框架可以用图分类交叉熵损失函数和图表征向量分布的KL散度来有效地优化信息瓶颈目标.

本文的主要贡献包括3个方面:(1) NIB-HGSL将信息瓶颈原理引入到层次化的图结构学习中,并结合变分近似获得易于优化的目标函数,从信息论的角度为图结构质量的信息度量提供了一个更加普适和通用的框架.(2) NIB-HGSL通过层次图结构学习,可以保留图数据中不同层级的结构特性并针对性地保留关键信息、去除无关信息.NIB-HGSL是模型无关的即插即用式框架,可以与现有图神经网络结合以提高其性能.(3)在多个图分类和图回归数据集上以及在噪声图以及对抗攻击图上的实验结果表明,与其他的基线方法相比,NIB-HGSL具备更佳的准确性和鲁棒性.

2、相关工作

本节首先介绍图结构学习方法,然后简要介绍信息论视角下的图结构度量方法．

2.1 图结构学习方法

图结构学习[8]的目标是为输入的图数据学习一个更好的图结构,并联合优化后的图结构学习表征,以提高图神经网络模型的表征质量和鲁棒性.部分工作(例如Neural Sparse[11]和PTDNet[21])将图结构学习建模为一个图稀疏化问题,并通过删除与任务无关的边来生成新的结构.这些方法只能生成稀疏图,不考虑恢复原始图数据中缺失的边.其他工作通过学习一个新的图结构作为图神经网络的输入,根据对结构进行建模不同可分为三类方法:度量学习类、概率建模类、直接优化类.其中,度量学习类方法通过对每个节点对特征进行学习获得其边的权重[11,22],例如IDGL[9]将图结构学习转化为相似度度量学习问题,迭代学习图结构和节点表征;概率建模类方法假设图是由一定分布的采样过程生成的,用可学习的参数对采样边的概率进行建模[23],例如LDS[22]通过双层优化技术联合学习边的离散概率分布和图神经网络参数;直接优化类方法将图数据的邻接矩阵作为一个参数,和图神经网络的参数一起进行优化,例如GCN-GT[24]通过类别标签和平滑性正则同时优化邻接矩阵参数和图神经网络参数.

大多数方法对学习到的图的结构进行一定的约束,来控制图结构质量,例如连通性[25]、低秩[10]、稀疏性[9]、特征平滑度[10]和同质性[26].此外,大部分方法针对节点层级的任务设计,仅有两项工作HGP-SL[27]和VIB-GSL[23]专门面向图级别的任务进行结构学习.HGP-SL[27]首先通过节点选择进行池化,再通过结构学习捕捉节点间关联.VIB-GSL[23]和本文工作最为接近,通过变分信息瓶颈来指导图结构的学习,然而,其忽略了对于图层级任务极其重要的子结构,导致大量结构信息丢失.本文所提方法NIB-GSL使用非线性信息瓶颈原则作为指导,避免了先验性结构假设,并通过层次性的结构学习保留关键信息,对不同的图结构和任务具有更强的适应性.

2.2 信息论视角的图结构度量

信息论将信息传递作为一种统计现象来考虑,为复杂系统的描述提供了一套统一的方式,越来越多的研究工作将其引入到表征学习中.信息的度量是信息论研究的基本问题之一,其中,C.E.Shannon于1948年提出信息熵(information entropy)[28],用于度量信息的冗余度(即复杂性).为衡量图结构的复杂性,研究者将熵这一度量信息复杂性的方法扩展到图数据上,其代表性工作包括冯诺依曼图熵[29]和结构熵[30].冯诺依曼图熵[29]将图看作一个量子系统,通过离散的拉普拉斯态和量子态之间的映射,量化图结构的谱复杂性.结构熵[30]将K维结构复杂性定义为确定图结构中可从随机游走中访问的节点的K维编码所需的最小总位数.目前的图熵方法只针对图结构本身的复杂性定义,难以同时考虑图数据中的属性等特征信息以及下游任务.

互信息(mutual information,MI)是在深度学习领域应用较为广泛的一个信息论工具,它衡量了两个变量之间的相关性.若两个变量相关性越大,则其互信息越大,反之如果两个变量相关独立,则其互信息为0.常用互信息估计方法包括MINE (mutual information neural estimation)[31]、变分推断[32].其中,MINE方法通过DV (Donsker-Varadhan)表示来逼近KL散度,并通过神经网络作为统计网络来找到一个互信息的较为紧致的下界.变分推断方法通过变分方法求似然函数的近似分布,从而获得对互信息的近似估计.对于图数据的互信息估计来说,除了上述不同估计方式之外,还可以分为两类:直接估计和分解估计.其中,大部分现有图上互信息估计方法属于直接估计,即将图数据作为整体,将其转化为向量进行互信息行计算.分解估计在领域内研究较少,代表性方法为GIB[33],这类方法将图数据分解为节点特征矩阵和邻接矩阵,并对两部分的互信息分别计算并加和作为整体互信息.

近年来,信息瓶颈原则在深度学习中受到了极大的关注[17,34],部分研究者将其用于解释深度神经网络的训练过程以及指导神经网络学习中.最近一些工作[33,35]将信息瓶颈原则引入到图学习中.GIB[33]将一般的信息瓶颈扩展到具有不规则结构的图数据中,对结构和特征信息进行正则化处理,以获得鲁棒的节点表征.SIB[35]通过“子图-图”与“子图-标签”间互信息的均衡发现对下游任务最具影响力的关键子图.HGIB[36]以无监督的方式实现异构图的共识假设.当前信息论指导的图结构度量方法只针对图数据中观测的结构信息,极少关注结构中缺失的边.VIB-GSL[23]首次将信息瓶颈理论引入图结构学习中,并采取变分近似的方式获取在图数据上易于优化的目标函数.本文提出的层次图结构学习方法NIB-HGSL同样从信息论的视角出发,度量特定下游任务下的图结构质量,旨在去除结构中的噪声连接、恢复观测结构中缺失的隐藏连接,提高图表征的鲁棒性.

3、问题背景与定义

本节首先简要概述图结构学习的相关定义,然后介绍信息瓶颈原则及其在图结构学习中的应用.

图结构学习.图结构学习[8]的目标是同时学习一个优化的图结构和相应的节点/图表征,以提高图神经网络模型的表征质量和鲁棒性.本文工作主要专注于图层级分类和回归任务的图结构学习,可以将其定义为:设G∈G是一个带有标签Y∈Y的图,其节点集为V,节点特征矩阵为X∈R|V|×d,邻接矩阵为A∈R|V|×|V|.本文关注的图结构学习问题可以被表述为:针对下游的图分类或图回归任务,输出一个优化的图G*=(X*,A*)和其相应的图表征Z*,并学习一个分类/预测器f:Z*→Y获得图标签,其中Y对于图分类任务来说为分类类别,对于图回归任务来说为回归值.

常见的信息论定义与计算方法.根据[37],对于变量X∼p(X),其香农熵H(X)=EX∼p(X)[-log p(X)],交叉熵H(p(X),q(X))=EX∼p(X)[-log q(X)],香农互信息I(X;Y)=H(X)-H(X|Y),Kullback-Leibler divergence(KL)散度

信息瓶颈原则.信息瓶颈原则[17]是对数据压缩的率失真问题的拓展,旨在寻求数据拟合和泛化之间的平衡,使用互信息作为损失函数和实现正则化.按照信息瓶颈的标准定义,对于给定的数据X的表征Z和目标标签Y,三元组(X,Y,Z)服从马尔科夫链⟨Y→X→Z⟩.

定义1 (信息瓶颈原则)对于输入数据X和它的标签Y,信息瓶颈原则的目的是学习最小充分表征Z,使得

其中,β是拉格朗日乘子(Lagrangian multiplier),用于权衡表征的充分性和最小信息量.

层次图结构学习的信息瓶颈原则.本文提出的层次图结构学习方法方法旨在学习一个层次最小充分图,其中,从而以最小的有效信息损失保留了图G的性质,其定义如下:

图1 (网络版彩图) NIB-HGSL整体框架

Figure 1 (Color online) Framework of NIB-HGSL

定义2 (IB-Graph)对于一个图G=(X,A)和它的标签Y,通过信息瓶颈找到的最优图GIB:{GIB(1),GIB(2),···,GIB(L)}作为最小充分图IB-Graph:

其中,是优化后的第l层图,XIB(l)是其特征集合,AIB(l)是其邻接矩阵.

直观地说,第一项-I(GIB;Y)是有效信息保留项,该项鼓励GIB中保留与标签Y相关的信息.第二项I(GIB;G)是噪声信息压缩项,该项鼓励学习到的最小充分图中不包含中G与标签无关的信息.而拉格朗日乘子β表示信息压缩的程度,越大的β表示GIB中保留G的信息越少.假设Gn∈G是G中一个任务无关的干扰因素,即影响观测到的图数据G,但与标签Y无关的随机变量,则GIB的学习过程遵循马尔科夫链[18]⟨(Y,Gn)→G→GIB⟩,也就是GIB与Y和Gn之间只通过G进行关联,这使其只保留了原始图中与任务相关的信息,对数据中的干扰具有扰动不变性.

4、非线性信息瓶颈指导的层次图结构学习NIB-HGSL

NIB-HGSL在信息瓶颈原则的指导下,通过学习具有多层次的图结构最小充分图IB-Graph来保留图数据每一层与任务密切相关的关键信息,并将其作为图神经网络消息传递的途径,以此来深入挖掘和发现图结构不同尺度的结构关联,更好地去除图中各层的噪声信息、保留层次化关键信息.其整体结构如图1所示.

本节首先介绍层次化的图结构学习方法,然后介绍信息瓶颈原则在不规则层次图结构上的近似上界推导,最后介绍框架整体优化方法.

4.1 层次图结构学习方法

本节介绍层次图结构学习方法,通过图池化技术递归地聚合节点集以形成超节点,生成不同结构粒度的层次图,再通过结构学习对多层次的图结构进行优化,从而捕捉图中不同粒度的显著信息.

定义S(l)∈RNl×Nl+1表示在第l层的图池化算子,Nl和Nl+1分别代表图在第l和第l+1层时的节点数量.聚类时采用软聚类方式,即节点vi可以同时属于多个类别,Si,j表示节点vi隶属节点簇j的程度,并且.假设A(l)和X(l)分别代表经过l-1层池化后的邻接矩阵和节点特征矩阵,而AIB(l)和XIB(l)分别代表经过结构优化后第l层的邻接矩阵和节点特征矩阵,可以通过以下两个公式生成池化后第l+1层的邻接矩阵A(l+1)和节点特征矩阵X(l+1):

其中XIB(0),AIB(0)为初始化图G的原始节点特征矩阵X和邻接矩阵A.

直观上,具有相似特征的节点被分配到相同聚类的概率较高,因此我们基于注意力机制来获得图池化算子S(l),注意力分数由节点对间的特征相似程度和连接性决定:

其中,xi(l),xj(l)为节点vi,vj的特征向量,其中(AIB(l))c表示节点在l层的c-hop连接性,c为一个超参数,ϕi,j代表节点对(vi,vj)间的注意力分数,衡量了两节点间关联的重要程度.有了注意力分数矩阵ϕ,我们可以得到最终的图池化算子:

其中,GNN(·)为基础图神经网络编码器.此处对于带有边/关系特征的图数据,可以选择考虑边信息或属性的图神经网络作为基础编码器,如RGCN[38]、RGAT[39]等,以保留边上的特征信息,进而将这类特征嵌入到学习的图结构中.

通过图池化技术纯化信息的一个关键问题是,无法正确学习到高层次节点间的结构信息[40].在这项工作中,我们保留通过聚类所得到的原始结构信息A(l+1),同时引入结构学习来捕获高层次中超节点之间所隐含的结构关系.首先使用特征掩码策略,以离散的方式丢弃X(l)中与任务无关特征:

其中,M是一个可学习的二元特征掩码,⊙是元素间的乘积.直观地说,如果一个特定的特征维度与任务不相关,那么M中相应的权重就会接近于零.这里使用重参数化技巧(reparameterization trick)[41]通过d维随机变量进行反向传播,可以将重参数化为:

其中,Xr(l+1)是一个从X(l+1)的经验分布中采样的随机变量.

其次,对最小充分图的结构进行学习.如第2.1节中所介绍,通过概率建模是图结构学习的典型建模方式,具体而言可以选择伯努利分布(Bernoulli distribution)[22,42]、类别分布(categorical distribution)[11,33]、高斯核函数(Gaussian kernel)定义分布[43]等.其中,类别分布和高斯核函数分布更适合于对于图结构分布有先验知识的情况,因此本文选择了更具有普适性的伯努利分布进行结构建模.具体而言,本文将池化子图间所有可能的边建模为一组相互独立的伯努利随机变量,其参数是一个可学习的注意力权重:

对于每一对节点,结合其表征来优化边的采样概率.πi,j描述了边的对于特定任务的质量,数值小的表示边更可能是噪声信息,应该分配更小的权重甚至删除.对于一对节点(vi,vj),结合其节点表征计算其边的采样概率.具体而言,将节点的特征转化为一个特征隐向量:

其中为节点vi的特征,NN(·)表示一个神经网络,本工作中使用两层感知机实现.然后,使用多头余弦相似度机制,结合节点特征隐向量和节点表征向量学习连边采样概率:

其中,m为多头的个数,Wh为第h个头的权重参数.由于Al相对于π的伯努利分布是不可微的,因此此处使用伯努利分布的具体松弛(concrete relaxation)[44]来更新:

其中,ϵ∼Uniform(0,1)和t∈R+是松弛分布的温度系数.在具体松弛之后,ai,jl+1被转化为πil,j+1和ϵ的一个确定性函数.具体松弛后的图结构是一个加权的全连接图,在此之上计算的代价很高.本文通过屏蔽小于非负阈值的矩阵元素来提取一个对称稀疏的邻接矩阵.最后得到高一层次的图:

其中λ是一个预定义的超参数,用于控制优化后的图结构与原始结构的融合程度.

4.2 信息瓶颈目标函数的非线性近似

经过4.1中的步骤,可以得到更新后的层次化图.由于图数据的非欧几里得性质,其互信息难以计算,因此,将信息论应用于图数据的主要挑战之一是对高维联合分布的合理估计[45].公式(2)中的信息瓶颈目标难以直接优化,因此无法直接用于指导层次图结构学习.接下来,本文针对图数据的特性,分别提出了对有效信息保留项和噪声信息压缩项的变分近似上界.

首先,对于信息瓶颈目标函数中的压缩项I(GIB;G),此项旨在使得GIB包含G中尽量少的与任务无关的信息,其上界为[23,35]:

命题1 (I(GIB;G)的上界)对于图G∈G、从中学到的最小充分层次图GIB,有

其中,r(GIB(l))为p(GIB(l))的变分近似.

证明由于层次化图GIB的学习过程中,每个层级的图GIB(l)结构学习都依赖于上一层的图GIB(l-1),因此GIB的学习过程遵循马尔科夫(Markov)链[18]⟨(Y,Gn)→G→GIB⟩,即⟨(Y,Gn)→G→GIB(1)→GIB(2)→···→GIB(L)⟩.根据互信息的链式法则(chain rule for mutual information)[37]和数据处理不等式(data processing inequality),有

对于I(G;GIB(l)),根据互信息的定义,有

由于难以计算,因此我们使用r(GIB(l))作为p(GIB(l))的变分近似.根据KL散度的非负性,有

因此,有

将公式(16)代入公式(14),有

其次,对于信息瓶颈目标函数中的有效信息保留项I(GIB;Y),此项旨在鼓励保留对图标签的有效信息.通过对其进行变分近似,获得-I(GIB;Y)的上界[23,35].

命题2 (-I(GIB;Y)的上界)对于带有标签Y∈Y的图G∈G、从中学到的最小充分层次图GIB,有

其中,qθ(Y|GIB)是真实后验分布p(Y|GIB)的变分近似.

证明

其中,由马尔科夫链⟨(Y,Gn)→G→GIB⟩,p(Y|GIB)可定义为:p(Y|GIB)=∫p(Y|GIB)p(GIB|G)d G.因为p(Y|GIB)难以直接计算,令qθ(Y|GIB)作为真实先验分布p(Y|GIB)的变分近似,其中θ是变分解码映射的参数.根据KL散度的非负性DKL(p(Y|GIB)||qθ(Y|GIB)) 0,即

将公式(20)代入公式(19),有

本文采用充分编码器在表征过程中不存在信息损失的假设[46],这也是信息瓶颈已有相关工作[47]的常用假设.对于每一个层级的图GIB(l),将其输入到图神经网络中进行学习其节点表征,并通过池化层将节点表征转化为图表征ZIB(l).通过这种方法,可以获得图的层次化表征{ZIB(1),ZIB(2),···,ZIB(L)}.进而,可以通过注意力加权的方式将层次化表征转化为一个统一表征向量.因此,对于学习到的层次图结构GIB来说,有

结合式(18),(13)和(22),可以为层次图结构学习的信息瓶颈目标函数提供可处理的上界:

4.3 非线性信息瓶颈的目标函数优化

基于上节中对信息瓶颈原则中有效信息保留项与噪声信息压缩项的互信息上界近似,NIB-HGSL可以使用基于梯度下降的反向传播技术在训练数据样本上有效地计算信息瓶颈目标函数的上界.具体来说,通过对在所有结构层次上优化非线性信息瓶颈目标函数,获得保留最小充分信息的图结构与对应的层次化图表征:

由于有关研究表明,信息瓶颈曲线(IB curve)并不能通过最大化不同β下的拉格朗日项而恢复[48],因此,在实际优化时,本文采用平方拉格朗日项(squared-IB Lagrangian)[48]来进一步探索在不同值下的信息瓶颈曲线,NIB-HGSL优化损失函数为

由于公式(23)中的H(Y)是一个与优化无关的常数,因此在目标函数中舍弃掉了.在实际训练中,公式(25)中的第一项对于图分类任务来说等价于常用的交叉熵(cross entropy,CE)损失函数,对于图回归任务来说等价于常用的均方误差(mean square error,MSE)损失函数.公式(25)中的第二项相当于在优化过程中减少GIB对G的依赖、增大信息压缩度的正则项.拉格朗日乘子β作为压缩系数调节信息压缩程度,在5.5节分析了其参数敏感度.NIB-HGSL方法的算法伪代码如算法1所示.

5、性能评测

本节对NIB-HGSL方法进行性能评测.首先介绍实验数据集、基线方法及实验设置,进一步在图分类任务、图回归任务和图去噪任务上进行验证和分析.

5.1 实验设置

数据集.对于图分类任务来说,本文参考图结构学习基准GSLB[49]的实验设置,在四个广泛使用的社交网络数据集(IMDB-B,IMDB-M,REDDIT-B和COLLAB[50])和两个生物数据集(MUTAG[51]和PROTEINS[52])上进行了验证实验.IMDB-B和IMDB-M数据集中每个图样本代表演员及其在电影中的共现关系关系,图标签代表电影类型.REDDIT-B数据集中每个图样本中节点代表帖子,边代表两个帖子被同一人评论,图标签是帖子对应的社区分类.COLLAB数据集是作者协作网络的一个子集,节点代表作者,边表示作者之间的协作,节点特征是通过平均作者发表的论文的词的表征,边的特征包括年份和该年发表的合著论文数量.MUTAG数据集由分子图组成,根据化合物对细菌是否有诱变作用来对图进行标记.PROTEINS数据集由蛋白质图组成,节点表示蛋白质的二级结构,边表示两个二级结构在氨基酸序列中或者三维结构中是邻居,图标签表示该蛋白质为酶或者非酶.对于图回归任务来说,本文使用了两个聚合物数据集(plym-melting,plym-galss)和三个分子数据集(ogbg-mollipo,ogbg-molesol,ogbg-molfreesolv)[53].其中,plym-melting数据集为每个聚合物样本预测其熔融温度,plym-glass数据集中为每个聚合物样本预测其玻璃转化温度,ogbg-mollipo数据集中为每个分子样本预测其亲脂性,ogbg-molesol数据集中为每个分子样本预测其水溶性(每升摩尔的对数溶解度),ogbg-molfreesolv数据集中为每个分子样本预测其水中分子的水合自由能.

算法1 NIB-HGSL的训练过程

基线方法.本文将提出的NIB-HGSL与两个专门面向图层级的结构学习方法(HGP-SL[27]和VIB-GSL[23])以及其他一些可以扩展到图层级的结构学习基线方法(Neural Sparse[11],SIB[35],IDGL[9])进行比较.(1) Neural Sparse[11]:通过去除图中多余的与任务无关的边,从而更清晰地划分类别边界,提高模型泛化能力.(2) SIB[35]:通过子图信息瓶颈原则识别图数据中具有预测性的关键子图,结合互信息估计器设计了一种双层优化方案.(3) IDGL[9]:将图结构学习看作节点特征的度量学习,通过交替迭代与优化同时学习图结构与节点表征.(4) HGP-SL[27]:首先通过节点选择进行池化,再通过结构学习捕捉节点间关联.(5) VIB-GSL[23]:使用变分信息瓶颈指导,通过节点间的全局相似性学习一个单一尺度图结构.

实验设置.本文将常见的图神经网络作为基础编码器嵌入NIB-GSL框架中(包括经典的图卷积神经网络GCN[54]、图注意力网络GAT[55]、图同构网络GIN[14],以及近年提出的各向同性高效图卷积网络EGC[56]),以观察NIB-HGSL是否能提高这些基础编码器在图分类任务上的性能.为了进行公平的比较,全部方法表征维度为16,使用同样的双层感知机作为分类器.对于层次结构学习中的池化聚类计算,实际训练中由于相近轮次节点嵌入更新差别较小,因此为了提高训练效率间隔固定轮次进行更新.NIB-HGSL设置温度参数t为0.1,c=1,并对α,β,λ进行超参数搜索.所有模型的参数都经过仔细的调整优化,并在单个NVIDIA V100 32GB GPU上进行训练和测试.

5.2 图分类实验结果与分析

首先验证NIB-HGSL改善基础图神经网络图分类的能力,评价指标为图分类的准确率(accuracy),分类准确率越高代表方法效果越好.实验中进行了十折交叉验证,所有方法的平均准确率和标准差如表1,每个方法组的最佳结果用粗体表示,效果次优的用下划线表示.

从图分类的结果可以看出,所提出的NIB-HGSL方法在所有数据集上的图分类准确率都超过了基线方法.NIB-HGSL相对于基础图神经网络的性能优势意味着它能够学习与任务更密切相关的图结构,进而提高图神经网络学到的图表征质量.一般来说,图稀疏化方法(即Neural Sparse[11]和SIB[35])在提升基础图神经网络准确性方面只有很小的改善,甚至对性能有负面影响(例如在COLLAB上),这是因为它们受制于观察到的结构,而没有挖掘节点间潜在的关联关系.相当于全局结构学习的方法(IDGL[9]和VIB-GSL[23]),我们的方法NIB-HGSL由于能够重新学习图的层次结构关系,从而保留不同层级的图性质,因此更适合于图层级的任务.而相对于层次结构池化的方法HGP-SL[27],我们的方法NIB-HGSL由于引入了信息瓶颈理论去指导图结构优化,可以更好地发现在每个层次上关键的结构信息,从而自适应地保留相应的结构性质,因此取得了更好的表现.

5.3 图回归实验结果与分析

其次验证NIB-HGSL在图回归任务上的效果,评价指标为均方绝对误差(mean absolute error,MAE),均方绝对误差越低代表方法效果越好.所有方法的平均MAE和标准差如表2,每个方法组的最佳结果用粗体表示,效果次优的用下划线表示.从图回归的结果可以看出,所提出的NIB-HGSL方法在所有数据集上的回归均方绝对误差都小于基线方法.例如,在plym-melting数据集上,NIB-HGSL相对于次优的基线方法,在不同基础图神经网络编码器的配置下图回归均方绝对误差分别降低了5.25,3.06,2.47,3.77,说明了本文所提方法具有更强的提取图关键信息的能力.

5.4 鲁棒性分析

NIB-HGSL在信息瓶颈原则指导下进行结构优化,旨在压缩噪声信息、保留有效信息.本节分别针对两类典型的噪声场景:随机噪声和对抗攻击噪声,开展对NIB-HGSL鲁棒性的分析验证.

随机噪声鲁棒性分析.为评估NIB-HGSL在噪声图数据上的鲁棒性,本节通过扰动REDDIT-B数据集中图样本的边来生成一个带噪声的合成数据集,并用其进行图去噪任务验证.具体来说,对数据集中的每个样本,随机地翻转25%,50%,75%的边(如果不存在边则增加,如果存在边则删除).重复五次实验,在IMDB-B、REDDIT-B和MUTAG数据集上的结果如图2所示.可以看出,GCN方法的分类准确率随着边翻转比例的增大呈现出剧烈下降,这表明图神经网络对结构噪声较为敏感.图结构学习基线方法HGP-SL和VIB-GSL相对于GCN来说准确率下降趋势较缓,这说明了结构学习对于增强方法鲁棒性的作用.本文方法NIB-HGSL同时受益于信息瓶颈理论的指导和层次化的结构学习,可以去除结构中的噪声信息,因此相对于HGP-SL和VIB-GSL来说具有更好的鲁棒性.

表1 图分类任务上方法准确率和标准差

对抗攻击鲁棒性分析.为评估NIB-HGSL面对图对抗攻击的鲁棒性,本节采用一种典型的图层级攻击方法PRBCD[57]对每个图样本进行逃逸攻击(evasion attack).具体来说,PRBCD方法通过投影随机块下降寻找对性能影响最大的边进行翻转,从而实现攻击,本文采用2.5%,5.0%,7.5%的攻击预算来模仿不同强度的对抗攻击.在不同攻击强度下重复五次实验,在IMDB-B,REDDIT-B和MUTAG三个数据集上的结果如图3所示.从图中可以看出,各方法随着攻击力度的增大准确率都有一定程度的下降,其中HGP-SL的下降程度最为剧烈,对对抗攻击噪声极为敏感.而另一个基于信息瓶颈的结构学习方法VIB-GSL的准确率下降趋势稍缓,表现出更好的鲁棒性,这说明了信息瓶颈原则可以有效提高图神经网络对于对抗攻击的防御能力.而本文方法NIB-HGSL同时受益于信息瓶颈原则对噪声信息的压缩,以及层次结构学习中对于子结构语义的增强,展现出最好的鲁棒性.

表2 图回归任务上方法均方绝对误差和标准差

5.5 NIB-HGSL分析

为验证本文方法NIB-HGSL中信息瓶颈原则与层次结构学习的有效性,本节首先对其进行消融分析实验.此外,本文提出方法NIB-HGSL通过同时对有效信息保留和噪声信息压缩来帮助获得优化的图结构,其中信息压缩程度决定了方法的效果.因此,本节对拉格朗日(Lagrange)乘子β的参数敏感性分析和对压缩过程中的信息平面进行进一步分析.

图2 (网络版彩图) NIB-HGSL在随机噪声图上的鲁棒性分析

图3 (网络版彩图) NIB-HGSL在对抗攻击图上的鲁棒性分析

消融实验.为验证信息瓶颈原则和层次结构学习的有效性,分别构造了两个NIB-HGSL的变种方法NIB-HGSL(w/o IB)和NIB-HGSL(w/o HGSL).其中NIB-HGSL(w/o IB)为去掉信息瓶颈的指导,即去掉优化函数中的信息压缩项,仅通过分类损失函数指导整体框架的优化;NIB-HGSL(w/o HGSL)为去掉层次结构学习,即为每个图样本学习一个全局的图结构.消融实验的结果如图4所示,可以看出在五个数据集上,本文提出的信息瓶颈原则的指导以及层次化的图结构学习方法都能带来一致性的效果提升,其中非线性信息瓶颈原则的引入在大部分数据集上带来的效果提升更为明显.

拉格朗日乘子β参数敏感性.β在公式(2)和(25)中起到对有效信息保留项I(GIB;Y)和噪声信息压缩项I(GIB;G)之间进行权衡的作用.值得注意的是,在信息瓶颈原则中,增加和减少信息瓶颈维度K之间存在着关联关系[18].随着β变化,NIB-HGSL在REDDIT-B数据集上图分类准确性的变化趋势如图5所示.可以观察到,NIB-HGSL的图分类准确率随着β的增加都呈现驼峰型.在其他数据集的β敏感性分析实验中也呈现出同样趋势,在此没有一一展示.分类准确率首先随着β的增大而增加,表明去除与任务不相关的噪声信息确实可以有效增强图表征的质量;然后,准确率逐渐下降并达到较低的值,这表明过度的信息压缩会损失部分有效信息.不同的数据集由不同比例的任务无关信息组成,因此需要不同程度的信息压缩,因此适当的β值可以提高图分类模型的性能.

图4 (网络版彩图)消融实验分析

图5 (网络版彩图) β参数敏感性

可视化分析.我们通过信息平面[34]来分析NIB-HGSL在学习过程中的表现,该方法被广泛应用于分析训练过程中输入、潜在表征和输出之间互信息的变化.NIB-HGSL在REDDIT-B数据集上训练的信息平面如图6所示,图中X轴代表压缩项I(GIB;G),Y轴代表预测项I(GIB;Y),散点代表模型在训练过程中每个轮次所处的信息压缩状态.可以看出,训练过程中互信息变化分为两个阶段.在第一个阶段,I(GIB;G)和I(GIB;Y)都增加,这表明学习到的表征正在提取关于输入数据和标签的互信息,并且坐标向右上角移动.在第二阶段,I(GIB;G)开始下降,而I(GIB;Y)的增长速度放缓,并收敛到左上角,这表明我们的NIB-HGSL开始生效,导致表征向量中开始压缩无关信息,仅保留与下游任务相关的最小充分信息.

模型效率分析.首先,对本文所提出方法NIB-HGSL的复杂度进行分析.NIB-HGSL为一个层次化结构学习方法,过图池化技术递归地聚合节点集以形成超节点,生成不同结构粒度的层次图,再通过结构学习对多层次的图结构进行优化.此处设一共有L层,对于每层分别保留{N0,N1,···,NL-1}个超节点,其中N0=|V|,则对于第l层的结构学习来说,复杂度为O(Nl2).因此,整体方法的复杂度为O(|V|2),和其他结构学习的基线方法(Neural Sparse,SIB,IDGL,HGP-SL,VIB-GSL)相同.其次,图7对NIB-HGSL和其他基线方法的效率进行了对比,其中,横轴为平均每个轮次的训练时间(s),纵轴为图分类任务的准确率(%).从图7可以看出,NIB-HGSL在准确率达到最高的同时,其训练效率优于等IDGL、HSP-SL、SIB最新基线方法.虽然NIB-HGSL的训练效率不如GCN、VIB-GSL、Neural Sparse,但其准确率能够具有较大优势.

6、总结

本文工作针对图数据中存在的结构噪声问题,从信息论的视角出发,提出非线性信息瓶颈指导的图结构学习方法NIB-HGSL.该方法通过变分近似将信息瓶颈原则扩展到图数据的层次结构学习上,通过联合优化层次图结构和图表征来去除结构中的噪声信息,并增强各层结构中的有效信息表达,获得更鲁棒的图表征.在图分类数据集、图回归数据集和结构噪声及对抗攻击数据集上的实验结果表明,NIB-HGSL可以提高图表征学习的准确性和鲁棒性.

图6 (网络版彩图)信息平面

图7 (网络版彩图) NIB-HGSL训练效率分析

参考文献:

2刘知远,张乐,涂存超,等.中文社交媒体谣言统计语义分析.中国科学:信息科学, 2015, 45:1536–1546

3郑志明,吕金虎,韦卫,等.精准智能理论:面向复杂动态对象的人工智能.中国科学:信息科学, 2021, 51:678–690

4闫昭,项欣光,李泽超.基于交互序列商品相关性建模的图卷积会话推荐.中国科学:信息科学, 2022, 52:1069–1082

基金资助:国家自然科学基金(批准号:62225202,62302023)资助项目;

文章来源:孙庆赟,罗家逸,杨贝宁,等.非线性信息瓶颈指导的层次图结构学习方法[J].中国科学:信息科学,2024,54(10):2409-2427.