AAAI21 | 基于块(Block)建模理论图神经网络

2021 年 12 月 28 日 图与推荐

题目： Block Modeling-Guided Graph Convolutional Neural Networks

作者：何东晓（天津大学），梁春栋（天津大学），刘蕙心（天津大学），文明祥（天津大学），焦鹏飞（杭州电子科技大学），冯志勇（天津大学）

会议：The 36th AAAI Conference on Artificial Intelligence (AAAI-2022)
文章链接：https://github.com/hedongxiao-tju/BM-GCN/blob/main/paper.pdf
代码链接：https://github.com/hedongxiao-tju/BM-GCN

1. 内容简介

网络表征（Network Embedding）旨在学习网络中节点的低维表示，可以用于许多下游网络分析任务。图卷积网络（Graph Convolutional Networks, GCN）已经成为学习网络表征的一种经典范式。然而，GCN的方法是建立在同质性假设（homophily assumption）基础上的，即相似的节点往往更倾向于在网络中建立连接。因此GCN聚合机制不能适应于现实生活中普遍存在的异质性（heterophily）网络。为了使GCN的传播和聚合机制能够高效处理不同程度的同质性和异质性(甚至二者混合)的网络，本文将块建模理论引入到GCN框架中，使图卷积操作能够实现“分类聚合”，自动学习不同类邻居间对应的聚合规则。本文将所提算法与当前针对网络异质性问题的先进方法进行了比较，实验结果表明，本方法在同质性和异质性的网络上均优于现有的方法，且对模型关键组件的可视化进一步对本方法作了解释。

2. 方法

本文模型主要由两部分构成，分别为块相似度矩阵的计算模块和块相似度矩阵引导下的图卷积模块（如下图所示）。

在块相似度矩阵的计算模块部分，本文利用MLP预学习节点的软标签矩阵B，并用学习到的软标签矩阵来近似计算块矩阵H。块矩阵H描述了不同类节点间存在边的概率，在异质性强网络中不足以指导图卷积操作实现分类聚合。基于块矩阵H，本文进一步引入块相似度矩阵Q来刻画类间相似度，以实现块相似度矩阵Q引导的分类聚合，即同类或相似类间存在更多的消息聚合。

在块相似度矩阵引导下的图卷积模块部分，本文依据软标签矩阵B中各节点的标签概率分布，以及块相似度矩阵Q中的类间相似度，来计算任意两节点在聚合过程中的消息传递规则。依据学习到的聚合规则，本文对网络的原始拓扑结构进行修正，使得图卷积过程能够自适应地处理同质性和异质性的网络。

2.1 基于MLP的预训练

计算块矩阵H需要预先知道每个节点的真实标签，然而在本文的半监督场景中，只有训练集的真实标签是已知的。因此，本文设计基于MLP的预训练方式来通过节点属性X对节点的标签进行预测。预测节点软标签B的预训练过程为

其中T_v是训练集， Y是真实标签， f代表多分类交叉熵损失函数。

2.2 块相似度矩阵的计算

块建模理论揭示了网络拓扑结构的规律，块矩阵的概念可以表示网络中类与类之间节点的连接模式。在已知部分真实标签和学习到节点的软标签后，本文块矩阵的计算过程如下

其中 Y_s是真实标签与软标签的组合，A 是邻接矩阵，E 是全1矩阵， %代表矩阵对应元素做除法运算。块矩阵H 中每一元素刻画了对应两类节点间存在边的概率，描述了网络拓扑的固有规律。然而，在异质性强的网络中，块矩阵H 所描绘的网络异质性规律并不能用作GCN的指导，因为GCN取得高性能的前提是网络满足同质性假设。

同质性假设下的GCN模型之所以性能优异，是因为同类或相似类间节点存在更多的消息聚合，使得相似节点间的表征更平滑，最终保证模型对相似节点的预测结果更相近。为了使GCN在各种情况下保持这种能力，本文基于块矩阵设计了块相似度矩阵，用来衡量类与类之间的相似性，其计算过程如下

Q 中坐标(i，j) 对应的元素值代表第i 类和第j 类的相似度。考虑到同类节点间应该传递更多的信息，本文引入增强因子alpha ，对Q 中的主对角线元素进行增强。

2.3 块相似度矩阵指导的图卷积

基于计算得到的块相似度矩阵Q ，本文为不同节点对分配不同的消息传递策略。考虑节点v_i 和节点v_j 及其对应的软标签向量和，其中c代表类别数，软标签向量的第t 个分量代表了该节点属于第t 类的概率，因此节点对(v_i,v_j) 有 c^2种类型候选组合，计算不同类型组合概率的形式化表达如下

其中是将节点类别映射函数。由于Q 刻画了类与类之间的相似性，因此可以将其建模为不同类间传递信息的概率，即越相似的两类间传递消息的概率越大。因此，节点v_i 和节点v_j 间的消息传递概率期望的形式化公式如下

根据上述公式可以看出，两个节点间传递消息的概率由节点的软标签向量及块相似度矩阵Q 共同决定。对于网络中的所有节点，上述过程的矩阵运算表示为

受益于块相似度矩阵的性质，提供了一个在同质性和异质性网络上均适用的消息传递策略，可以真正地帮助GCN实现分类聚合的目的，即同类或相似类间节点存在更多的消息聚合。本文用对原始网络拓扑进行修正，新型的图卷积过程如下

在模型优化阶段，本文采用交叉熵损失对模型进行半监督训练优化，同时为了保证MLP所学软标签的可靠性，对预训练的MLP模块进行了微调，整体的目标函数如下

3. 实验

本文在六个真实网络数据集上进行了实验，数据集的统计信息如下

节点分类实验本文在六个数据集上进行了节点分类实验，结果如下
节点可视化实验本文在chameleon数据集上进行了节点可视化实验，结果如下
块矩阵的可视化本文分别在Cora（同质）和Chameleon（异质）上可视化了用真实标签计算的块矩阵 H^bar（图a），基于软标签的块矩阵H（图b）及块相似度矩阵 Q（图c），结果如下图，其中左列为Cora网络，右列为Chameleon网络。可以看出，在同质Cora网络上，块矩阵已经足以实现“分类聚合”的指导，且本文方法的块相似度矩阵与块矩阵有相同的作用；在异质Chameleon网络，块矩阵中没有展示适于“分类聚合”的类间连接模式，而本文方法的块相似度矩阵中同类(主对角线)间连接概率更大，更有助于图卷积模式实现“分类聚合”。