近年来,尽管图神经网络(GNN)在挖掘各种图结构数据方面均显示出强大的能力,越来越多的研究发现,GNN中普遍存在着各种各样的偏见亦或是不公平性问题,这些问题往往会诱发一些社会危害或是性能下降,进而严重制约了其在日常生产生活中的实际应用。
具体而言,本文聚焦于传统GNN在预测跨越社区的链路(cross-links)时所面临的偏差问题。事实上,根据图中链路端点所属社区是否相同,可以将图中的所有链路分为cross-links(端点社区不同)和internal-links(端点社区相同)两种类型,而cross-links在保证图连通性以及缓解信息茧房等多个方面均扮演着重要的角色。然而,由于GNN过度依赖基于邻居结构的消息传播机制,GNN在进行链路预测往往会忽略cross-links,进而造成一种性能上的偏差。为消除这种偏差,之前的工作大都基于目标函数的修改,即引入额外的约束条件来消除GNN模型优化过程中的偏差,但这类方法往往会导致模型优化得到一个次优解,最终以牺牲模型链路预测性能的代价来实现消除预测偏差的效果。
不同于之前的研究工作,本文发现现有的GNN模型在训练数据上往往会面临在internal-links和cross-links之间的明显的数据偏差,因此采取了一种数据驱动的方法来重新审视cross-links上的性能偏差问题。具体而言,本文提出来一种简单而高效的孪生结构框架,该框架适用于大多数GNN模型,以减轻这种偏差并提高它们的性能水平。其核心思想在于生成无偏差的节点嵌入向量,然后将这些向量与原始GNN生成的节点嵌入向量融合,以实现性能的提升。此外,一种全新的动态训练策略被设计用来更加高效地将无偏向量与原始向量相结合。经过对三个不同数据集的广泛实验验证,这一框架不仅成功地克服了GNN在处理“internal-links”和“cross-links”时的性能偏差,同时也显著提升了整体预测性能水平。
该成果“Cross-links Matter for Link Prediction: Rethinking the Debiased GNN from a Data Perspective”发表于Thirty-seventh Conference on Neural Information Processing Systems(NeurIPS 2023)。该会议是人工智能的顶级会议之一,是中国计算机学会(CCF)推荐的A类国际学术会议。
论文链接:https://neurips.cc/virtual/2023/poster/70277
背景与动机
什么是Cross-links
事实上,在大型图中,节点会自然形成局部社区子图。例如,在一个学术网络中,在同一研究领域工作的研究人员可以形成一个社区子图;在交通网络中,地理位置相近的目标物可以形成一个社区子图。在这种设定下,我们将端点属于不同社区的链路称为cross-links,而属于相同社区的链路称为internal-links,示意图如图1所示。
图1 internal-links和cross-links示意图。不同色块表示不同的社区
我们通过大量的实验发现,现有的GNN模型由于过度依赖消息传播和邻居聚合,往往在预测internal-links和cross-links展现出非常明显的性能偏差,即模型在internal-links上的性能会远远高于cross-links。从网络的长期发展角度来看,这种性能偏差可能导致cross-links在网络中的数量下降,进而对网络造成危害。具体而言,我们从以下两个方面说明了cross-links的稀缺对网络的影响。
1.1 破坏网络联通性
我们首先在经典的社交网络Karate-club上使用SI模型进行了仿真实验,通过随机去掉图中80%的cross-links或取掉相同数量的随机链路,我们发现在前者的设定下会极大地影响网络的联通性以及消息传播,仿真结果如图2所示。
图2 基于SI模型的消息传播仿真图
1.2 加剧信息茧房
受上面实验结果启发,我们进一步怀疑cross-links在缓解信息茧房中同样起到了非常重要的作用。具体而言,我们使用Calinski-Harabasz 系数(后简称CH系数)作为信息茧房的评价指标,其计算公式如下:
通俗来讲,CH系数衡量了节点表达中簇间距离与簇中距离之比,其值越大,说明当前网络的节点嵌入表达极化程度越高,信息茧房现象越严重。我们在两个真实数据集Epinions和DBLP上通过Friedkin-Johnsen动态模型模拟了节点嵌入表达的更新过程,通过调整cross-links在更新节点嵌入表达时的权重,我们得到如图3所示的实验结果:
图3 基于Friedkin-Johnsen动态模型的CH系数变化图
不难发现,随着cross-links所对应的权重降低,最终节点嵌入表达的CH系数迅速变高并趋于平缓,说明网络中的信息茧房现象发生了迅速的恶化。
通过以上两个分析性实验,我们成功论证了cross-links在网络结构中的重要作用,并进一步启发我们设计一种针对cross-links的GNN去偏方法。
设计与实现
现有的GNN去偏方法普遍通过在目标函数上加入约束条件的方式来达到消除偏差的效果,然而这种修改目标函数的范式往往会影响模型的正常优化,导致最终优化得到的模型出现性能的下降。不同于以往的方法,我们的先验实现发现网络结构中普遍存在着internal-links和cross-links之间的数据偏差,如图4所示,网络中internal-links的数量远远大于cross-links。这种偏差可能诱使GNN模型被更多地训练用于发掘internal-links,进而导致cross-links上的偏差。基于以上发现和推断,我们决定从数据驱动的角度出发重新考量cross-links上的性能偏差问题。
图4 三个真实数据集上cross-links的占比分布
我们的去偏训练框架包含有三个部分,分别是1)针对cross-links的监督信号增强;2)孪生GNN网络和3)嵌入融合动态网络。我们首先基于两种规则,筛选出了大量图中不存在,但具有高置信度的跨社区节点对作为伪监督信号,并对原本的训练集进行扩充。具体而言,我们基于雅各布系数和随机游走设计了两种监督信号增强方式,分别通过筛出雅各布系数最高或随机游走中共现频率最高的Top K个跨社区节点对作为增强的伪监督信号。我们期望通过监督信号增强的方式从源头上缓解cross-links的性能偏差。在这之后,正常的监督信号和扩充之后的监督信号分别被送入两个孪生GNN网络中用于训练。值得一提的是,之所以称之为孪生GNN网络,是因为两个GNN网络享有同样的网络结构,但网络参数在训练中相互独立,我们期望基于正常监督信号训练的GNN网络能够最大程度保留模型的表达能力,而基于扩充之后的监督信号训练的GNN网络能够学习到去偏能力。最后,为了保证最终节点嵌入能够同时拥有较好的表达能力和去偏能力,并且进一步消除监督信号增强环节中可能引入的噪声,我们设计了一个嵌入融合网络,将孪生GNN网络的两种输出嵌入表达进行进一步的加工和融合。考虑到训练开始阶段孪生GNN网络的输出并不稳定,此时不宜对嵌入融合网络进行过多的训练,我们引入了动态的训练策略来控制嵌入融合网络的优化和更新。整体的模型框架如图5所示。
图5 模型框架图
实验结果
我们在Epinions、DBLP和LastFM三个真实数据集上评估了我们的模型在链路预测任务上的性能。作为一种与模型无关的GNN训练框架,我们在实验中分别选择了GraphSAGE、GAT、GIN、LightGCN、PPRGo和UltraGCN作为基础GNN模型。评价指标上,我们采用了Hits@50,并分别统计了模型在internal-links(Internal.),cross-links(Cross.)和整体(Overall)上的性能以及在两种链路上的性能之差(Bias),结果如图6所示:
图6 在三个真实数据集上基于6种GNN的实验结果截图
可以看出,在通过我们的去偏框架方法进行训练之后,所有的GNN模型在没有造成性能下降的前提下显著缓解了cross-links上的性能偏差,这验证了我们方法在性能和去偏上的出色能力。
除此之外,为了验证我们方法在提升GNN模型对cross-links的预测性能之后是否能够有效缓解信息茧房,我们基于UltraGCN模型在三个数据集上进行了基于嵌入表达重构网络的可视化实验,如图7所示:
图7 UltraGCN模型在去偏前(Base)和去偏后(Ours)所得到的网络结构可视化效果图,不同颜色的节点隶属于不同社区
可以看出,除了少数离群点之外,相较于基线模型,通过我们去偏框架训练得到的嵌入表达在重构网络后打破了大部分社区之间的隔阂,下降的模块度(Modularity)也佐证了这一现象。该可视化实验在一定程度上验证了我们的方法能够有效缓解诸如过滤气泡在内的信息茧房现象。
详细内容请参见:
Zihan Luo, Hong Huang, Jianxun Lian, Xiran Song, Xing Xie and Hai Jin. Cross-links Matter for Link Prediction: Rethinking the Debiased GNN from a Data Perspective. In Proceedings of the Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS 2023).
https://neurips.cc/virtual/2023/poster/70277