Advertisement

CompGCN: Composition-based multi-relational graph convolutional network

阅读量：

1 前言

本文发表于ICLR 2020年会上，并由印度科技学院等单位资助支持。其中一位研究者 Partha Talukdar 是我一直追踪的知识图谱领域的重要学者，在 GNN 研究的发展趋势指引下逐渐转向了知识图谱与生成式神经网络（GNN）的融合研究工作。他的个人主页位于 http://www.talukdar.net ，具体成果则包含多篇具有影响力的文章。本公众号旨在提供学术交流平台，并声明所有内容均为原创性质的作品；如需引用，请注明出处。另：若文中内容涉及侵犯任何第三方权益，请告知删除

图1 Partha Talukdar 的发表论文（2019，部分）

2 符号定义

对论文中的具体符号及其意义进行了统计分析，并在表格1中进行了详细展示；同时，在介绍相关公式时也会涉及这些具体的数学符号。

表1 项目符号及其具体描述 | Symbol | Definition | Symbol | Definition |

--- --- --- ---
𝒱 Set of vertices 𝑊𝑂 Learned matrix of outgoing edges
ℛ Set of relations 𝑊𝐼 Learned matrix of incoming edges
ℰ Set of edges 𝑊𝑆 Learned matrix of self-loop edges
𝒳 Input features of each node 𝒳 𝜖
athbb{R}^{artheta imes d_{0}}

|𝑊𝑑𝑖𝑟(𝑟)|𝑊𝑑𝑖𝑟(𝑟) = {𝑊𝑂, 𝑊𝐼, 𝑊𝑆}|
|𝒵|Initial relation features 𝒵 𝜖

athbb{R}^{e imes d_{0}}

|𝑊𝑟𝑒𝑙|𝑊𝑟𝑒𝑙 𝜖

athbb{R}^{d_{1} imes d_{0} }

，关系向量的参数矩阵|
|(𝑢,𝑣,𝑟)|(𝑢,𝑣,𝑟) 𝜖 ℰ, 𝑢,𝑣 𝜖 𝒱, 𝑟 𝜖 ℛ|X|Score function|
|⊺|Self-loop edges|M|The specific method to obtain embeddings|
|𝐾|Hidden layers of GCN|Y|Composition operations|

3 动机

基于图神经网络在处理具有结构特性的数据时的能力，在建模无向、单关系的图或者网络方面尤其表现出色。构建一个无向图的节点表示过程基本上涉及将输入节点特征与邻接矩阵结合进行计算，并通过数学表达式𝐻=𝑓(𝐴𝒳𝑊)来进行编码操作后得到各节点的表示向量。

  1. 类似于知识图谱这样的多关系图（或网络）才是现实世界中最普遍的图数据类型，而多数GCN的编码函数对于处理这样的多关系图是不适合的。而为了使用GCN去建模多关系图，需要对GCN的编码函数做适当的调整，即𝐻=𝑓(𝐴𝒳𝑊𝑟) 。显而易见的是，这样的改进虽然可以对多关系图进行建模，但是随之而来的问题也是致命的。当多关系图中的关系类型过多的时候，这样的编码函数会引进多个关系矩阵𝑊𝑟，这样的参数过载对于模型的训练是极其不利的，甚至导致模型不可训练。
  2. 另一方面，GCN的通用任务是学习图的节点表示，从而服务于节点的分类任务。也就是说，通过GCN获得的只是图的节点嵌入 。而在多关系图中，关系向量的表达也是特别重要的。

针对主要动机1, Schlichkrull等人对参数过载的问题有所改进. 他们采用了矩阵𝑊𝑟的对角块分解和基变换的方式有效地降低了模型的参数, 但针对主要动机2仍然没有提出相应的改进方案. 本文则基于上述两个主要动机, 提出了 CompGCN 模型, 该模型能够同时学习多关系图中的节点表示及其对应的关系表示, 并在此基础上提出了针对参数过载问题的有效解决方案. CompGCN 的主要贡献如图2所示.

图2 CompGCN 与其他方法的贡献对比和参数对比

4 背景

1、图卷积网络（GCN）

本小节内容主要参考论文 “SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS”进行的总结。

本小节内容基于文章 "SEMI-SUPERVILLED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS" 进行了综述

GCN遵循的是一种层与层对应（layer-wise ）的传播规则，即：

g_green H^{l+1}=igma eft

\(\)\(\), 其中

ilde{A}=A+I_{N}

表示使图的邻接矩阵的对角线元素为1，即对每个节点增加自环。

ilde{D}{ii}=um{j} ilde{A}_{ij}

表示每个节点的出度矩阵，

igma eft

是一种激活函数。

之前在掌握GCN（图卷积网络）公式推导方面一直采取较为被动的态度。受限于仅能基于该篇论文所建立的理论框架，在过去的时间里我认为GNN（图神经网络）更倾向于一种传统的谱方法图信号处理方式。然而今年3月29日参加了一个由SMP联合智源教育平台主办的图神经网络专题线上研讨会https://www.bilibili.com/video/BV1zp4y117bB?from=search&seid=8519676631676283249，观看了沈华伟老师关于GNN理论知识的详细讲解后才意识到原来GNN不仅有基于谱方法的传统路径，在空间方法上也有深入研究，并且沈老师通过详尽的例子展示了基于谱方法构建的GNN模型本质上属于一种特殊的基于空间视角的方法。有兴趣的同学可以参考上方链接观看回放视频。以下将从个人角度出发，在节首文献的基础上展开对基于谱方法实现GCN（无卷积特征平滑模型）的相关推导工作

定义 ：在谱域中，图的谱域信号卷积通常被定义为一个信号

xpsilon athbb{R}^{N}

（是一个标量）和一个滤波器

g_{heta }=diageft

（

heta psilon athbb{R}^{N}

）在傅里叶域的乘积。

用公式化语言表述为：

𝑔_𝜃⋆𝑥=𝑈𝑔_𝜃 𝑈^𝑇 𝑥
g_{heta }tar x=Ug_{heta }U^{op }x

, 其中

L=I_{N}-D{-\frac{1}{2}}AD{-rac{1}{2}}=Uambda U^{op }

,而

U^{op }x

就是信号

xpsilon athbb{R}^{N}

在傅里叶域的转换。滤波器

g_{heta }

可以看作是

ambda

的一个函数 ，即

g_{heta }eft

。所以信号

xpsilon athbb{R}^{N}

在傅里叶域的转换公式可以改为

g_{heta }tar x=Ug_{heta }eft U^{op }x

。

从这个角度来看，在频域中实现图信号的转换是完全可行的。然而，在该公式中用于编码图或网络时会遇到一个主要难题：计算效率较低。

𝒪eft
Oeft

因为涉及到矩阵乘法的情况

L

来得到特征矩阵

U

在处理大规模图时显得非常不方便。为了应对这一挑战，在处理大规模图时显得非常不方便。

g_{heta }tar x

.

定义 ：切比雪夫多项式是一种递归式的定义，即

T_{k}eft =2xT_{k-1}eft -T_{k-2}eft

, 先验条件是

T_{0}eft =1

和

T_{1}eft =x

。

所以，

g_{heta }tar x = Ug_{heta }eft U^{T}x

中的

g_{heta }eft

可以使用切比雪夫多项式来近似，即

g_{heta ^{'}}eft pprox um_{k=0}^{K}heta {k}^{'}T{k}eft

。在这个近似表达中，K表示切比雪夫多项式的第K项，

ilde{ambda }=rac{2}{ambda _{max}}ambda -I

,𝜆𝑚𝑎𝑥代表拉普拉斯方程特征值中的最大值。基于切比雪夫多项式进行近似表达时，并将K限定为1且𝜆𝑚𝑎𝑥设定为2时，则图信号经此变换后的公式则可简化为

由此可见，GCN的核心公式部分大体上完成。关于进一步的内容和推导过程，请参考相关论文。

2、图卷积的变体

如前所述，在现有的研究中已有多种基于图卷积的方法被提出并已被广泛应用于无向图及其上的嵌入表示技术以及多关系图模型中。然而这些方法均存在一些不足之处例如计算效率较低泛化能力有待提高等局限性

5 CompGCN框架

介绍该框架之前，再明确一下作者的研究动机：

  1. 通过综合学习复杂网络模型中node embeddings与relation representations的交互机制
  2. 针对现有multi-relational graph representation tasks在graph neural networks中的parameter explosion issue提出了创新性的解决方案

基于这两个研究动机，作者提出了如图3所示的框架图。

图3 CompGCN框架

如图3所示，CompGCN框架相较于其他复杂架构而言相对较为简单，并主要采用两阶段学习策略。该方法基于给定的多关系图节点与边表示（其中可以通过其他方法获取初始表示），并设计了一种更新机制以优化网络性能。研究者将边的方向分为出边、入边以及自环边，并分别对应着三种学习矩阵来更新中心节点（Christopher Nolan）的相关向量表示。

本文中，
作者提出了多关系图 𝒢=(𝒱, _ℛ, _ℰ, _𝒳) 的符号化表示。
并且特别指出，在CompGCN框架下对边的方向性特征进行了明确定义。

arepsilon ^{'}=arepsilon up eft eft | eft psilon arepsilon ight up eft eft ight

基于原始多关系图，在其基础上引入了逆向边与自连接边以扩展其连接性；同时为该特定的关系模式ℓ，在原有基础之上新增设置了逆向关联类型以及自我循环属性以进一步丰富其关联维度。

动机1：联合学习多关系图的节点嵌入和关系表示

在GCN中的图编码函数通过数学表达式𝐻=𝑓(𝐴𝒳𝑊) 来表示。其中接收作为输入的是特征空间中的数据。这种设计会导致当尝试同时学习节点嵌入与边上的关系时遇到困难。为了应对这一挑战，在CompGCN中提出了一种新的方法——通过将节点与边的关系进行组合来解决这个问题。

hi

通过整合节点与关系的初始表示到一个统一的特征空间中，并将其作为GCN模型的输入特征（这一做法借鉴了知识图谱嵌入方法的传统做法）

e_{o}=hi eft

_ 。将

e_{o}

作为图编码函数的特征输入，其中

e_{o}

表示目标节点，

e_{s}

表示源节点，

e_{r}

表示两节点之间的关系。在组合方式

hi

的选择上，论文给出了三种表达，分别是（1）向量减（

e_{s}-e_{r}

）（2）向量乘（

e_{s}st e_{r}

）和（3）向量的循环相关（

e_{s}igstar e_{r}

）。循环相关的内容建议您参考博客https://www.cnblogs.com/zhxuxu/p/10097620.html进行详细学习。无需进一步讨论。

在引入组合机制和边的方向属性之后，GCN的编码函数可以进行改写，即：

h_{v}=feft psilon Neft }W_{ambda eft } hi eft ight

（1），

其中

N_{v}

表示与节点

v

直接相连的出度边和目标节点的集合。

x_{u}

和

z_{r}

分别是节点

u

和关系

r

的初始向量。

W_{ambda eft }

遵循方向一致的具体参数设置。也就是说，在涉及更新的关系为原始关系的情况下

W_{ambda eft }=W_{o}

; 当参与更新的关系是原关系的反向关系时，

W_{ambda eft }=W_{I}

; 当参与更新的关系是循环关系时，

W_{ambda eft }=W_{op }

。

通过改写后的编码函数进行图节点的向量更新时，关系

r

的向量也隐含的参与到了运算中。也就是说，经过公式（1）后，关系向量

z_{r}

也被更新到了和节点向量

x_{u}

的同表示空间中。将关系的隐含表达使用可使用公式化的描述，

h_{r}=W_{rel}z_{r}

。

CompGCN中的第k层传递机制与传统的GCN一致，在上一层网络获得的中间状态基础上进行传递。

至此时刻, CompGCN 已经实现了对节点嵌入与边嵌入的联合学习这一目标。同时, 通过将关系转化为向量并输入模型的思想不仅能够扩展 CompGCN 的应用范围, 并且还可以将其推广至其他类型的图或知识图谱嵌入方法中。此外, 在深入分析这种基于向量组合的方法后发现 CompGCN 实际上是先前一些 GNN 方法中的一个特例（如图 4 所示）。

图4展示了CompGCN与其他方法在细节上的对比结果。结果显示CompGCN仅使用了不同类型的向量组合方式以及学习矩阵。

动机2：参数过载问题

回顾参数过载问题的成因，在将GCN应用于处理多关系图数据时,𝐻=𝑓(𝐴𝒳****𝑊ᵝ)**这一改进操作会导致生成多个权重矩阵,𝑊ᵝ,这些矩阵的数量会随着关系类型数量的变化而变化,从而给模型带来过多的学习挑战。

针对这一问题

为了再进一步的去减少模型的参数量，作者又对

z_{r}

进行了改动。从图3的框架中可以看出，每一种关系都会对应到一个

z_{r}

，所以

z_{r}

的数量和维度也会直接影响模型的参数规模。因此，在需要统一表示不同复杂关系及其数量的情况下,作者提出了一种基于基础向量的方法,即通过构建基础向量集合来反映不同关系类型及其存在的数量特征

的数量和维度也会影响模型的参数量.因此,为了能够使用统一的关系向量来表征不同的关系类型和数量,作者提出了基向量的方法.即通过构建基向量集合来反映不同关系类型及其存在的数量特征

其中，

B

表示基底的数量，

lpha _{br}

表示从基向量

b_{r}

到关系向量

z_{r}

的权重。这样，CompGCN的参数量就可以降低到

eft | R ight |B

的水平，从而缓解了参数过载的问题。

6 实验结果

此部分内容仅作简单展示，更详细的实验设置和结果请参看原论文。

1、任务

表2 CompGCN任务描述 | 任务| 数据集| 评价指标 |

--- --- ---
节点分类 MUTAG 和 AM ACC
图分类 MUTAG （图） 和 PTC ACC

2、数据集

表3 数据集描述 | 名称| 描述 |

--- ---
WN18RR 是WordNet18 的一个子集
MUTAG（节点） 包含复杂分子之间的关系，任务是确定一个分子是否具有致癌性
AM 包含阿姆斯特丹博物馆中不同文物之间的关系的数据集。其目的是根据连接和其他属性预测文物的类别
MUTAG（图） 包含188种诱变的芳香族硝基化合物的生物信息徐数据集，根据诱变作用将图分为两类（二分类）
PTC 由344种化合物组成的数据集，这些化合物指示雄性和雌性大鼠的致癌性。任务是根据它们对啮齿类动物的致癌性进行分类（二分类）

数据集的拓扑统计如图5所示。

图5 实验数据集的拓扑统计

3、链路预测的实验结果

通过观察图表可知，在链路预测任务中大多数指标上 CompGCn 的表现最优。相比之下，在现有对比方法中 RotaE 的性能最为突出。得益于 RotaE 在复杂域内采用了独特的旋转操作处理节点向量。此外 研究者进一步指出 如果能合理地对节点和关系的初始向量进行复杂的组合操作 将可能显著提升 CompGCn 的表现性能。

通过X+M(Y)的方法，作者评估了不同GCN Encoder在link prediction task上的性能指标，并将其结果以可视化结果图的形式展示。

从图表数据可以看出，在采用基于ConvE的得分为基础并结合一种循环依赖关系的组合机制的情况下，CompGCN展现出最佳的效果。进一步展示了当关系向量发生变化时，在不同复杂度场景下模型性能的变化趋势

z_{r}

使用基向量（

B=50

）来表示时的性能，基本可以与最好的CompGCN结果相比。

4、节点分类和图分类

7 参考文献

  1. Vashishth S , Sanyal S , Nitin V , et al. Composition-based Multi-Relational Graph Convolutional Networks[J]. 2019.
  2. Kipf, Thomas N, Welling, Max. Semi-Supervised Classification with Graph Convolutional Networks[J].
  3. Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. arXiv preprint arXiv:1703.06103, 2017
  4. David K. Hammond, Pierre Vandergheynst, and R´emi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129–150, 2011

全部评论 (0)

还没有任何评论哟~

相关文章推荐

CompGCN: Composition-based multi-relational graph convolutional network

1前言 本文发表于ICLR2020,作者单位是印度科技学院，作者之一ParthaTalukdar是我很早就开始关注的以为知识图谱方向的作者，在GNN趋势的引导下，作者也开始将研究中心转为知识图谱与GN...

【论文翻译|ICLR2020】CompGCN - COMPOSITION-BASED MULTI-RELATIONAL GRAPH CONVOLUTIONAL NETWORKS

文章目录 摘要 1引言 3回顾 4CompGCN细节 7结论 参考阅读：< 摘要 图卷积网络GCNs最近被证明在建模图结构数据方面非常成功。然而，主要的焦点是处理简单的无向图。

Knowledge Embedding Based Graph Convolutional Network

研究问题 提出了一种可以充分结合异构的节点信息和边信息，同时学习这两者的嵌入的图卷积网络KEGCN，并将之前的几种知识图谱CNN纳入一个统一的框架下 背景动机 传统的图卷积模型一般不关注学习边的嵌入，...

Relational Graph Attention Network for Aspect-based Sentiment Analysis

1.Introducton 本篇文章是2020年发表于ACL的一篇文章，不同于其他人直接编码现成的依赖树，这篇文章中作者通过重塑与修剪普通的依赖树从而将方面词作为依赖树的根节点。此外作者还提出一个Re...

Attributed Multi-order Graph Convolutional Network for Heterogeneous Graphs

这篇论文是我这周读的最顺畅的一篇，不是因为他的idea特别突出，而是文章的思路很清楚，讲的很详细，所以让我感觉到很顺畅，我觉得有必要多写一点论文解读来记录一下。

Multi-Range Attentive Bicomponent Graph Convolutional Network for Traffic Forecasting

研究问题 交通预测，即根据历史交通数据预测路网未来的交通状况 背景动机 道路网络和交通条件带来复杂的时空依赖性和本质上的不确定性 早期交通预测方法主要对单个观察节点或几个节点采用浅层机器学习，难以捕捉...

shift-GCN：Skeleton-Based Action Recognition with Shift Graph Convolutional Network

SkeletonBasedActionRecognitionwithShiftGraphConvolutionalNetwork CVPR2020 shiftGCN 主要特点：大幅度减少计算成本 背景...

Image Segmentation-based Multi-focus Image Fusion through Multi-scale Convolutional Neural Network

《ImageSegmentationbasedMultifocusImageFusionthroughMultiscaleConvolutionalNeuralNetwork》 一、概述 文章通过基于...

论文4：ACL2020-Relational Graph Attention Network for Aspect-based Sentiment Analysis

论文4：ACL2020RelationalGraphAttentionNetworkforAspectbasedSentimentAnalysis 一.论文思想 1.前三篇论文的局限 （1）首先，忽略...

Cascading Residual Graph Convolutional Network for Multi-Behavior Recommendation (TOIS 2024)

论文链接 Motivation： 在真实场景中，用户通常会采取一系列动作与物品进行交互，以获得有关该物品的更多信息，从而准确评估物品是否符合他们的个人偏好。这些交互行为往往遵循一定的顺序，更重要的是，...