论文解读者:北邮 GAMMA Lab 2020届硕士 赵健安
题目: 图神经网络的异质图结构学习
会议: AAAI 2021
论文链接:http://shichuan.org/doc/100.pdf
论文代码:
https://github.com/Andy-Border/HGSL
1 摘要
近年来,异质图神经网络引起了广泛关注并应用在各种下游任务上。现有异质图神经网络模型通常依赖于原始的异质图结构并暗含着原始图结构是可靠的假设。然而,这种假设往往并不现实,异质图结构普遍存在噪声和缺失的问题。因此,如何为异质图神经网络学习一个合适的图结构而不是依赖于原始图结构是一个关键问题。为解决这一问题,本文首次研究了异质图结构学习(Heterogeneous Graph Structure Learning)问题,并提出了HGSL框架来联合学习适合分类的异质图结构和图神经网络参数。HGSL 通过挖掘特征相似性、特征与结构之间的交互以及异质图中的高阶语义结构来生成适合下游任务的异质图结构并联合学习 GNN参数。三个数据集上的实验结果表明,HGSL 的性能优于基线模型。
2 引言
许多真实世界的数据具有图结构,例如社交媒体图、文献引用图。图神经网络(GNN)作为一种处理图数据的强大深度表示学习工具被广泛地应用于节点分类、图分类以及推荐等下游任务中。最近,随着真实世界中异质图应用的激增,学者们提出了异质图神经网络(HGNN),并在一系列应用上取得了优越的效果。
大多数HGNN遵循一种消息传递(message passing)机制,其中节点的表示通过聚合和转换其原始邻居或基于元路径邻居的信息来学习。然而,这些方法依赖于一个基本假设,即原始异质图结构良好且适合下游任务。然而,这种假设因为以下原因经常不成立。首先,由于异质图通常是根据一些预先定义的规则从复杂的交互系统中提取得出,这些交互系统本身不可避免地包含了一些不确定的信息或错误。以推荐中的用户-物品图为例,用户可能会误点一些不需要的物品,给图带来噪声信息。其次,异质图的提取通常要经过数据清洗、特征提取和特征转换等过程,这些过程通常与下游任务无关,导致提取的图结构与下游任务之间存在差距。因此,为GNN学习适合下游任务的异质图结构是一个重要的问题。
本文首次对图神经网络的异质图结构学习进行研究,并提出了一个异质图结构学习框架HGSL。HGSL框架根据下游任务对异质图结构和GNN参数进行联合学习。在图结构学习部分,HGSL分别对每个关系子图进行学习。具体来说,对于每一种关系,通过从异质节点特征和图结构中挖掘复杂关联,生成特征图、和语义图并与原始图结构进一步融合成可学习的异质图结构馈送给GNN。最终,图结构学习参数和GNN参数联合优化以完成节点分类任务。
3 方法
一个异质图
G 的邻接矩阵由多个关系子矩阵构成,即
\mathcal{A}=\left\{\mathbf{A}_{r}, r \in \mathcal{R}\right\}。因此,如上图所示,对于每个关系子矩阵
\mathbf{A}_{r}, HGSL 根据节点属性,原始图结构,以及基于不同元路径的语义表示生成特征图
\mathbf{S}_{r}^{Feat}和语义图
\mathbf{S}_{r}^{S e m},并将其与原始图结构
\mathbf{A}_{r}融合生成新的子图结构
\mathbf{A}_{r}^\prime。随后,将学习到的子图输入到GNN和正则项中,以进行具有正则化的节点分类。通过最小化正则化的分类损失,HGSL联合优化图结构和GNN参数。
3.1 特征图产生器
由于原始图对于下游任务可能不是最佳的,我们可以利用异质节点特征内部的丰富信息来增强原始图的结构。通常,有两个因素会影响基于特征的图结构的形成。一个是节点特征间的相似性,另一个是节点特征与拓扑间的关系。因此,HGSL 充分考虑这两种潜在因素来生成特征图,一方面生成一个特征相似度图,该特征相似度图通过异质特征投影和度量学习捕获由节点特征生成的潜在关系。另一方面,通过特征来生成特征传播图。最后,将生成的特征相似度图和特征传播图通过通道注意力层聚合为最终特征图。
3.2 特征相似图
特征相似图通过特征的相似性来生成图结构,即一对特征相似的节点对存在潜在的边。
给定一个节点
v_i和类型
\phi(v_i) ,我们将它的特征向量
\mathbf{f}_i \in \mathbb{R}^ {1 \times d_{\phi(v_i)}}映射到
d_c维的公共空间,其公共空间的特征向量记为
\mathbf{f}_{i}^\prime \in \mathbb{R}^ {1 \times d_{c}}:
\mathbf{f}_{i}^{\prime}=\sigma\left(\mathbf{f}_{i} \cdot\mathbf{W}_{\phi\left(v_{i}\right)} +\mathbf{b}_{\phi\left(v_{i}\right)}\right),
随后,我们根据度量学习来习得适合任务的一阶特征相似性图
\mathbf{S}^{FS}_{r}:
\mathbf{S}^{FS}_{r}[i,j]=\left\{\begin{array}{ll}
\Gamma^{FS}_r(\mathbf{f}^\prime_i,\mathbf{f}^\prime_j) &\Gamma^{FS}_r(\mathbf{f}^\prime_i,\mathbf{f}^\prime_j)>\epsilon^{FS} \\
0 & \text { otherwise,}
\end{array}\right.
其中,
\epsilon^{FS} 为生成特征相似图的门限,
\Gamma^{FS}_r为一个相似性度量函数,表示为:
\Gamma^{FS}_r(\mathbf{f}^\prime_i,\mathbf{f}^\prime_j)= \frac{1}{K}\sum_k^K \cos \left(\mathbf{w}^{FS}_{k,r} \odot \mathbf{f}^\prime_i, \mathbf{w}^{FS}_{k,r} \odot \mathbf{f}^\prime_j\right),
参数为
\mathbf{W}^{FS}_r= [\mathbf{w}^{FS}_{k,r}],通过为每个关系
r学习一个不同的度量学习函数
\Gamma^{FS}_r,HGSL为每个关系自适应的根据特征相似性生成特征相似图。
3.3 特征传播图
特征相似图通过特征与拓扑之间的交互来生成图结构,我们通过一个例子来更好的理解。例如,考虑生成用户和电影之间的潜在图结构,存在这样一种图结构生成方式:如果用户
U_1看过电影
M_1,且
M_1和
M_2相似,那么用户
U_1可能对
M_2感兴趣即
U_1和
M_2节点存在潜在边。上述潜在的图结构可以分两步构建:得到特征相似的节点对(找到相似的电影
M_1和
M_2),随后用拓扑结构传播(通过
U_1的观影历史得到
U_1可能感兴趣的电影)。HGSL 也通过上述两步过程来得到特征传播图。
具体地,HGSL从首节点和尾节点分别出发,通过度量学习得到特征相似性图
\mathbf{S}_r^{FH} 和
\mathbf{S}_r^{FT},以头特征相似性图
\mathbf{S}_r^{FH}为例:
\mathbf{S}^{FH}_{r}[i,j]=\left\{\begin{array}{ll}
\Gamma^{FH}_r(\mathbf{f}_i,\mathbf{f}_j) &\Gamma^{FH}_r(\mathbf{f}_i,\mathbf{f}_j)>\epsilon^{FP} \\
0 & \text { otherwise,}
\end{array}\right.
得到两个特征相似性图之后,我们使用拓扑信息得到特征传播图:
\mathbf{S}_{r}^{FPH}=\mathbf{S}_r^{FH} \mathbf{A}_r\\
\mathbf{S}_{r}^{FPT}= \mathbf{A}_r \mathbf{S}_r^{FT}.
其中
\mathbf{S}_{r}^{FPH}和
\mathbf{S}_{r}^{FPT}分别表示根据头类型结点和尾类型节点生成的特征相似性图。
3.4 特征生成图
得到特征相似图
\mathbf{S}_{r}^{FS}和特征传播图
\mathbf{S}_{r}^{FPH}, \mathbf{S}_{r}^{FPT}后,HGSL将特征相似图和特征传递图通过图级别的通道注意力层( channel attention layer)融合得到特征生成图
\mathbf{S}^{Feat}_{r}:
\mathbf{S}^{Feat}_{r} =\Psi_r^{Feat}([\mathbf{S}_{r}^{FS},\mathbf{S}_{r}^{FPH}, \mathbf{S}_{r}^{FPT}]),
其中
[\mathbf{S}_{r}^{FS},\mathbf{S}_{r}^{FPH}, \mathbf{S}_{r}^{FPT}]\in \mathbb{R}^{|V_{\phi_{h}(r)}|\times |V_{\phi_{t}(r)}|\times 3} 表示堆叠的备选图张量,
\Psi_r^{Feat} 是一个参数为
\mathbf{W}^{Feat}_{\Psi,r} \in \mathbb{R}^{1\times1\times3} 的通道注意力层,对输入以权重为
\operatorname{softmax}(\mathbf{W}^{Feat}_{\Psi,r})的卷积核进行
1\times1 卷积。
通过为每个关系
r 学习不同的图级别的注意力,HGSL 自适应地学习如何融合不同特征图得到该关系的特征生成图。
3.5 语义图产生器
语义图
\mathbf{S}_{r}^{Sem} 通过高阶拓扑关系来生成图结构。具体地,HGSL首先根据元路径集合
\mathcal{P},使用 MP2Vec 学习得到语义表示矩阵
\mathcal{Z}。随后,对于每种关系
r和每条元路径
P_m 的语义表示矩阵
\mathbf{Z}_{P_{m}},生成对应的语义备选图
\mathbf{S}^{MP}_{r,m}:
\mathbf{S}^{MP}_{r,m}[i,j]=\left\{\begin{array}{ll}
\Gamma^{MP}_{r,m}(\mathbf{z}_{i}^{m},\mathbf{z}_{j}^{m}) &\Gamma^{MP}_{r,m} (\mathbf{z}_{i}^{m},\mathbf{z}_{j}^{m})>\epsilon^{MP} \\
0 & \text { otherwise,}
\end{array}\right.
得到含有不同语义的语义备选图后,根据语义注意力融合得到语义生成图
\mathbf{S}_{r}^{Sem}:
\mathbf{S}_{r}^{Sem}=\Psi_{r}^{MP}([\mathbf{S}^{MP}_{r,1}, \mathbf{S}^{MP}_{r,2}, ... , \mathbf{S}^{MP}_{r,M}])
其中,
\Psi_{r}^{MP} 是参数为
\mathbf{W}^{MP}_{\Psi,r}\in \mathbb{R}^{1 \times 1\times M} 的通道注意力层。
3.6 图结构与 GNN 参数优化
最后,对于每种关系
r,HGSL根据图级别的通道注意力综合考虑特征图、语义图及原始图结构融合得到关系子图
\mathbf{A}_{r}^{\prime} :
\mathbf{A}_{r}^{\prime} = \Psi_r([\mathbf{S}_{r}^{Feat}, \mathbf{S}_{r}^{Sem}, \mathbf{A}_{r}]) ,
至此,我们得到了异质图结构
\mathcal{A}^\prime=\{\mathbf{A}_{r}^{\prime},r\in\mathcal{R}\}。将其对应的邻接矩阵
\mathbf{A^\prime}进行 GNN 分类,并得到图神经网络的分类损失
\mathcal{L}_{GNN}:
\mathcal{L}_{GNN}=\sum_{v_{i} \in V_{L}} \ell\left(f_{\theta}(\mathbf{X}, \mathbf{A^\prime})_{i}, y_{i}\right),
HGSL的损失函数
\mathcal{L}由图神经网络损失
\mathcal{L}_{GNN}和正则化项
\mathcal{L}_{reg}=\alpha \|\mathbf{A}^{\prime}\|_{1}相加得到:
\mathcal{L} = \mathcal{L}_{GNN}+ \mathcal{L}_{reg}.
4 实验
我们在 DBLP、ACM 及 Yelp 数据集上行了丰富的实验来验证HGSL 的有效性。
节点分类实验:
频道注意力可视化实验:
参数实验:
本期责任编辑:杨成
本期编辑:刘佳玮