精华内容
下载资源
问答
  • 图3 CompGCN框架 从图3中可以看到,CompGCN的框架相对而言是比较简单的,可以认为是一种二阶段式的学习模型。它基于一个给定的多关系图的节点嵌入和边嵌入(可以过其他嵌入方法获得一个多关系的初始表示),提出了...

    1 前言

    本文发表于ICLR 2020, 作者单位是印度科技学院,作者之一 Partha Talukdar 是我很早就开始关注的以为知识图谱方向的作者,在GNN趋势的引导下,作者也开始将研究中心转为知识图谱与GNN的结合。他的个人主页为 http://www.talukdar.net/下面给出了该作者在2019年发表的一些成果。本博客主要用于学术交流,属于原创,如有引用请注明。另:文中内容如有侵犯各方利益,请告知删除

    图1 Partha Talukdar 的发表论文(2019,部分)

         

    2 符号定义

     对论文中涉及的一些具体符号以及其表征的意义进行了一个统计,并展示在表1中,其他具体到公式的符号,在阐述公式的时候会进行介绍。

     

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

         Symbol

                              Definition

         Symbol

                                   Definition

     𝒢

    Multi-relational graph

    Basis vectors of relation

    𝒱

    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  𝒳 𝜖 \mathbb{R}^{\vartheta \times d_{0}}𝑊𝑑𝑖𝑟(𝑟)𝑊𝑑𝑖𝑟(𝑟) = {𝑊𝑂, 𝑊𝐼, 𝑊𝑆}

     𝒵

    Initial relation features 𝒵 𝜖 \mathbb{R}^{\Re \times d_{0}}𝑊𝑟𝑒𝑙𝑊𝑟𝑒𝑙 𝜖 \mathbb{R}^{d_{1} \times d_{0} },关系向量的参数矩阵
    (𝑢,𝑣,𝑟)

    (𝑢,𝑣,𝑟) 𝜖 ,  𝑢,𝑣 𝜖 𝒱𝑟 𝜖

    X

    Score function

    Self-loop edges

    M

    The specific method to obtain embeddings

    𝐾

    Hidden layers of GCN

    Y

    Composition operations

     

    3 动机

    随着图神经网络在图结构数据上的应用,GNN对建模无向、单关系的图或者网络是特别有效的。使用GCN编码一个无向图的过程基本可概括为:图输入,𝐻=𝑓(𝐴𝒳𝑊)进行编码,节点向量输出。但是:

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

    基于主要动机1,Schlichtkrull等人对参数过载的问题进行了改进。他们使用矩阵𝑊𝑟的对角块分解和基变换的方式适当的减少了模型的参数,但是他们对于主要动机2还是没有提出改进的办法。本文则基于上述两个主要动机,设计了CompGCN模型,来同时学习多关系图的节点表示和关系表示,并在增加一种表示的基础上,对模型的参数过载问题提出了解决办法。CompGCN的主要贡献如图2所示。

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

     

    4 背景

    1、图卷积网络(GCN)

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

    GCN遵循的是一种层与层对应(layer-wise)的传播规则,即:

    \bg_green H^{l+1}=\sigma \left ( \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{l}W^{l} \right ) , 其中\tilde{A}=A+I_{N}表示使图的邻接矩阵的对角线元素为1,即对每个节点增加自环。\tilde{D}_{ii}=\sum_{j} \tilde{A}_{ij}表示每个节点的出度矩阵,\sigma \left ( \cdot \right )是一种激活函数。

    之前对于理解GCN的公式推导都是比较盲目的。因为仅限于上述这篇论文的理论基础,认为GNN仅是一种源自于谱方法的图信号处理。但在3月29日参与了SMP联合智源教育平台推出的图神经网络在线研讨会https://www.bilibili.com/video/BV1zp4y117bB?from=search&seid=8519676631676283249,听过沈华伟老师对GNN的一些理论知识的讲解,才发现GNN也存在一种空间方法的理论推导,并且沈老师也很详实的证明了基于谱方法的GNN实际上是一种特殊的空间GNN的方法,而本节开始列出的文献提出的GCN更是一种无卷积的特征平滑方法。有兴趣的同学可以参考上方链接,观看回放视频。下面仅是从个人角度,结合节首文献开展基于谱方法的GCN的简单推导。


    定义:在谱域中,图的谱域信号卷积通常被定义为一个信号x\epsilon \mathbb{R}^{N}(是一个标量)和一个滤波器g_{\theta }=diag\left ( \theta \right )\theta \epsilon \mathbb{R}^{N})在傅里叶域的乘积。


    用公式化语言表述为:𝑔_𝜃⋆𝑥=𝑈𝑔_𝜃 𝑈^𝑇 𝑥g_{\theta }\star x=Ug_{\theta }U^{\top }x, 其中L=I_{N}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=U\Lambda U^{\top },而U^{\top }x就是信号x\epsilon \mathbb{R}^{N}在傅里叶域的转换。滤波器g_{\theta }可以看作是\Lambda的一个函数 ,即g_{\theta }\left ( \Lambda \right )。所以信号x\epsilon \mathbb{R}^{N}在傅里叶域的转换公式可以改为g_{\theta }\star x=Ug_{\theta }\left ( \Lambda \right )U^{\top }x

    这样,貌似看来图信号的转变就可以在傅里叶域实现了。但是上式存在一个尤其致命的问题,就是使用这样的一个公式对图或者网络进行编码时,时间复杂度太高,为𝒪\left ( N^{2} \right )O\left ( N^{2} \right ) (因为涉及到了矩阵的乘法)。同时,我们可以看到,想要计算图信号的变换,就需要先计算拉普拉斯方程L来得到特征矩阵U,这对于计算大规模图而言也是极不友好的。所以,为了解决这样的问题,GCN引入了切比雪夫多项式,近似估计g_{\theta }\star x.


    定义:切比雪夫多项式是一种递归式的定义,即T_{k}\left ( x \right )=2xT_{k-1}\left ( x \right )-T_{k-2}\left ( x \right ), 先验条件是T_{0}\left ( x \right )=1T_{1}\left ( x \right )=x


    所以,g_{\theta }\star x = Ug_{\theta }\left ( \Lambda \right )U^{T}x中的g_{\theta }\left ( \Lambda \right )可以使用切比雪夫多项式来近似,即g_{\theta ^{'}}\left ( \Lambda \right )\approx \sum_{k=0}^{K}\theta _{k}^{'}T_{k}\left ( \tilde{\Lambda } \right )。在这个近似表达中,K表示切比雪夫多项式的第K项,\tilde{\Lambda }=\frac{2}{\lambda _{max}}\Lambda -I𝜆𝑚𝑎𝑥是拉普拉斯方程特征值的最大值。这样,经过切比雪夫多项式的近似表达,并限制K=1, 𝜆𝑚𝑎𝑥=2, 图信号的transform公式可以变成:

    由此,GCN的核心公式部分基本介绍完成,更多的细节以及推导还请参考论文。

    2、图卷积的变体

    正如上文提到的,图卷积已经被广泛的用于无向图的嵌入和多关系图的嵌入,但是都存在一些弊端。如下所示。

     

    5 CompGCN框架

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

    1. 联合学习一个多关系图中的节点嵌入和关系表示
    2. 解决之前多关系图表示工作(图神经网络方面)中存在的参数过载问题

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

    图3 CompGCN框架

     

    从图3中可以看到,CompGCN的框架相对而言是比较简单的,可以认为是一种二阶段式的学习模型。它基于一个给定的多关系图的节点嵌入和边嵌入(可以过其他嵌入方法获得一个多关系的初始表示),提出了一种更新策略。同时,作者引入边的三种方向(出,入和自环),并使用对应的三种学习矩阵来完成中心节点(Christopher Nolan)的向量更新。

    本文中,作者定义多关系图 𝒢=(𝒱,,,𝒳), 并且引入边的方向属性,也就是在CompGCN中,边的定义是\varepsilon ^{'}=\varepsilon \cup \left \{ \left ( v,u,r^{-1} \right ) | \left ( v,u,r \right )\epsilon \varepsilon \right \}\cup \left \{ \left ( v,u,\top |u\epsilon \nu \right ) \right \},  即在原多关系图中增加了反向和自环两种形式的边。同样的,对于关系ℛ 而言,也在原基础上增加了反向关系(_inv)类型和自循环(self-loop)类型。

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

    在GCN的图编码函数𝐻=𝑓(𝐴𝒳𝑊)中,接受特征空间的输入𝒳是节点的特征表示也是唯一的特征输入。这样的话就会导致联合学习节点嵌入和关系表示的问题看起来无法实现。但是作者在CompGCN中提出了使用节点-关系的组合(composition)方式 \Phi 将节点的初始表示和关系的初始表示融合在一个统一的特征空间中,作为GCN的特征输入(这点是借鉴了知识图谱嵌入表示的常用方式)。公式化表示为: e_{o}=\Phi \left ( e_{s} , e_{r}\right )。将e_{o}作为图编码函数的特征输入,其中e_{o}表示目标节点, e_{s} 表示源节点,e_{r}表示两节点之间的关系。在组合方式 \Phi 的选择上,论文给出了三种表达,分别是(1)向量减(e_{s}-e_{r})(2)向量乘(e_{s}\ast e_{r})和(3)向量的循环相关(e_{s}\bigstar e_{r})。循环相关的相关内容可转到博客https://www.cnblogs.com/zhxuxu/p/10097620.html了解,这里不再赘述。

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

    h_{v}=f\left ( \sum_{\left (u,r \right )\epsilon N\left ( v \right )}W_{\lambda \left ( r \right )} \Phi \left ( x_{u}, z_{r} \right )\right )                     (1),

    其中N_{v}表示与节点v直接相连的出度边和目标节点的集合。x_{u}z_{r}分别是节点u和关系r的初始向量。W_{\lambda \left ( r \right )}是与关系的方向相一致的具体参数表示。也就是当参与更新的关系是原始关系时,W_{\lambda \left ( r \right )}=W_{o}; 当参与更新的关系是原关系的反向关系时,W_{\lambda \left ( r \right )}=W_{I}; 当参与更新的关系是循环关系时,W_{\lambda \left ( r \right )}=W_{\top }

    通过改写后的编码函数进行图节点的向量更新时,关系 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到多关系图中进行编码时,𝐻=𝑓(𝐴𝒳𝑊𝑟)的改动所引入的𝑊𝑟会随着关系的种类数而产生多个,从而引入了太多的学习参数。

    所以针对这个问题,把关系(不管这关系是什么类型,或者有多少种)统一用向量来表示的另一个优点(除了可以同时学习节点嵌入和关系表示之外的另一个优点)就是可以将参数从矩阵的量级先降到向量的量级。更近一步,作者在CompGCN中,对Schlichtkrull等人提出的节点训练过程做了改进,不再是在每一层神经网络上都定义独立的关系嵌入,而是只给第一层的神经网络定义一个关系向量,其他层使用的都是第一层的线性组合(这也是引入组合机制的一个关键目的)。

    为了再进一步的去减少模型的参数量,作者又对 z_{r} 进行了改动。从图3的框架中可以看出,每一种关系都会对应到一个 z_{r} ,所以z_{r} 的数量和维度也会影响模型的参数量。因此,作者为了使用统一的关系向量来表征不同的关系类型和数量,提出了基向量的方法。也就是

     其中,B表示基底的数量,\alpha _{br}表示从基向量b_{r}到关系向量z_{r}的权重。这样,CompGCN的参数量就可以降低到 \left | R \right |B 的水平,从而缓解了参数过载的问题。

    6 实验结果

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

    1、任务

    表2 CompGCN任务描述
    任务数据集评价指标
    链路预测FB15K-237 和 WN18RRMRR, MR 和 Hit@N
    节点分类MUTAG 和 AMACC
    图分类MUTAG (图) 和 PTCACC

    2、数据集

    表3 数据集描述
    名称描述
    FB15k-237是FreeBase 15k的一个删减版,其中的反向关系被删掉了,以此防止实体的直接推理
    WN18RR是WordNet18 的一个子集
    MUTAG(节点)包含复杂分子之间的关系,任务是确定一个分子是否具有致癌性
    AM包含阿姆斯特丹博物馆中不同文物之间的关系的数据集。其目的是根据连接和其他属性预测文物的类别
    MUTAG(图)包含188种诱变的芳香族硝基化合物的生物信息徐数据集,根据诱变作用将图分为两类(二分类)
    PTC由344种化合物组成的数据集,这些化合物指示雄性和雌性大鼠的致癌性。任务是根据它们对啮齿类动物的致癌性进行分类(二分类)

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

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

    3、链路预测的实验结果

     

    从上图可以看出,CompGCN在链路预测任务中的多数指标下取得了最好的结果。在众多的对比方法中,RotaE的性能是最好的,这主要是因为RotaE对节点向量在复杂域中使用了旋转操作,所以作者也指出,如果能够对节点和关系的初始向量进行合理的复杂化组合操作可能会提高CompGCN的表现性能。

    同时,作者采用了X+M(Y)的方法验证了不同的GCN Encoder 在链路预测上的表现效果。如下图所示。

    从上图中看出,使用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

     

     

    展开全文
  • CompGCN论文汇报ppt可通过关注公众号【AI机器学习与知识图谱】,回复关键词:CompGCN 来获得,供学习者使用!可添加微信号【17865190919】进学习交流群,加好友时备注来自CSDN。原创不易,转载请告知并注明出处! ...

    作者:CHEONG

    公众号:AI机器学习与知识图谱

    研究方向:自然语言处理与知识图谱

    CompGCN (ICLR 2020)

    Composition-based Multi-Relational Graph Convolutional Networks

    CompGCN论文汇报ppt可通过关注公众号【AI机器学习与知识图谱】,回复关键词:CompGCN 来获得,供学习者使用!可添加微信号【17865190919】进学习交流群,加好友时备注来自CSDN。原创不易,转载请告知并注明出处!


    一、基本概念:

    图神经网络: 图神经网络是一种专门用于处理图结构数据的神经网络模型。基于图神经网络的知识图谱学习方法:知识图谱表示学习,信息抽取,实体对齐,链接预测,知识推理。

    知识图谱: 知识图谱是以图的形式表现客观世界中的实体及之间关系的知识库,实体可以是真实世界中的物体或抽象的概念,关系则表示了实体间的联系。知识图谱拥有复杂的schema,实体类型和关系种类丰富,同质图模型远不能满足知识图谱的需求。

    在现实中的知识图谱会存在复杂的实体和关系类型,传统的GCN算法广泛应用于同质图,而同质图算法远不能满足知识图谱需求,CompGCN便是针对于Multi-relational Graphs提出的异质图表征算法,CompGCN能够同时对node和relation进行表征学习,在节点分类,链接预测和图分类任务上都取得Sota效果。


    二、Motivation

    在这里插入图片描述

    解释一: GNN, GCN等对于建模无向、单关系的图或网络是有效的,如上公式1;

    解释二: 现实生活中的知识图谱大多是多关系图,需要对关系进行编码,如上公式2;

    解释三: RGCN,如上公式2存在的缺陷,会随着关系的增大,引入过多关系矩阵Wr,参数爆炸模型无法训练。

    结合上述描述,CompGCN的研究动机便是为了解决以下两大问题:

    1、联合学习一个多关系图中的节点嵌入和关系表示;

    2、解决之前多关系图表示工作RGCN等存在的参数过载问题。



    三、Method

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-u6IDPr3Y-1615955780946)(file:///C:/Users/zl_sd/AppData/Local/Temp/msohtmlclip1/01/clip_image004.png)]
    如上左图是CompGCN为了将图的关系(Relation)加入到表示学习中,将Relation当成Embedding(向量)和Node Embedding联合学习,并且CompGCN丰富了边的类型,即反向关系类型和自循环关系类型,这样可以对多关系图谱进行表征学习并且不会引入过多参数;

    如上右图展示了CompGCN在进行表示学习时Aggregation的过程,对应如下公式:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W2mFfZee-1615955780953)(file:///C:/Users/zl_sd/AppData/Local/Temp/msohtmlclip1/01/clip_image006.png)]

    为了充分理解CompGCN Update图和上面Aggregation公式,需要弄清以下三个问题


    1、Node Embedding和Relation Embedding表征如何组合?

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l45x9PnM-1615955780961)(file:///C:/Users/zl_sd/AppData/Local/Temp/msohtmlclip1/01/clip_image008.png)]

    论文中给出了三种节点和关系表征的组合方式, 分别是Sub,Mult和Corr,也分别对应了TransE,DistMult和ConvE三种方式,在实验效果上看TransE训练速度最快但效果差,ConvE训练速度最慢但效果最佳。


    2、三种类型关系如何组合?

    CompGCN中做了关系增强,在正向关系类型基础上,增加了反向关系和自循环关系类型

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-h5KrTtIK-1615955780978)(file:///C:/Users/zl_sd/AppData/Local/Temp/msohtmlclip1/01/clip_image010.png)]
    因此就如公式所示,对这三种关系类型分别做Aggregation后需要将三种关系进行西格玛求和,可以看一下论文源码便十分清晰了

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JuLWKdqv-1615955780984)(file:///C:/Users/zl_sd/AppData/Local/Temp/msohtmlclip1/01/clip_image011.png)]

    3、关系表征如何更新?

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5JC1TEZT-1615955780990)(file:///C:/Users/zl_sd/AppData/Local/Temp/msohtmlclip1/01/clip_image013.png)]
    在每一层GCN迭代中,除了对Node Embedding进行Aggregation更新,还需要对Relation Embedding进行更新,如上公示引入Wrel参数进行更新,较为简单。

    至此我们对CompGCN提出的Node和Relation联合学习就较为清晰,为了更加深刻理解CompGCN模型的整体框架,让我们看下图:
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A51WjCvE-1615955780995)(file:///C:/Users/zl_sd/AppData/Local/Temp/msohtmlclip1/01/clip_image015.png)]

    CompGCN模型实现框架采用了R-GCN提出的Encoder-Decoder框架,在Encoder阶段将Entity Embedding和Realtion Embedding进行组合Aggregation,然后在Decoder阶段再采用类似TransE,TransH或者ConvE等方式对(h,r,t)三元组进行解码。因为CompGCN在Encoder阶段就引入了Realtion Embedding,因此从上图可以看出CompGCN的另一大优势便是可以在Encoder和Decoder编码的是同一套Realtion Embedding,使得表征学习更加精准。



    四、Conclusion


    1、实验数据介绍

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WlwazmGq-1615955780998)(file:///C:/Users/zl_sd/AppData/Local/Temp/msohtmlclip1/01/clip_image017.png)]
    FB15k-237: Freebase中的一部分数据,包含14541个节点、237类边;

    WN18RR: WordNet Graph的一部分,包含40943个节点,11类边;FB15k-237\WN18RR相对于FB15k\WN18是将测试集存在训练集的相反关系的一部分数据给去除了,官文有详细说明:

    WN18 and FB15k suffer from test leakage through inverse relations: a large number of test triples can be obtained simply by inverting triples in the training set. For example, the test set frequently contains triples such as (s, hyponym, o) while the training set contains its inverse (o, hypernym, s). To create a dataset without this property, FB15k-237 was introduced – a subset of FB15k where inverse relations are removed. And similarly, WN18 was corrected by WN18RR.


    2、实验结果

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MESzdnnk-1615955781004)(file:///C:/Users/zl_sd/AppData/Local/Temp/msohtmlclip1/01/clip_image019.png)]
    在这里插入图片描述

    结论: CompGCN在Encoder和Decoder阶段使用同一个编码方式效果会更好,从上表可以看出在Encoder和Decoder阶段同时使用ConvE时,在FB15k-237数据 Link Predictioon任务上取得了最好的效果。

    展开全文
  • ICLR20| 融合多关系图卷积网络COMPGCN 我们现实世界的复杂关系一般是异质图,但是现在GCN一般是应用在同质图上,这就为我们真实建模应用上带来了很大的限制。相比GCN的同质图,知识图谱从拓扑结构上来看,其实也是...

    前言

    今天是21年研究生考试的第一天,回想去年这个时候,自己也是百万大军中的一员,日复一日地在图书馆复习,然后订着酒店,赶着公交,奔赴考场,考完政治和英语伤心自己没有发挥好,这些场景恍如昨日。这一年过的有点光阴似箭,突如其来的疫情打乱了我们每个人的计划,我们被迫取消一些出行、一些活动,甚至一些企业也因为这次疫情而被迫关闭,但是我们依旧如那窗外的春燕,在凌厉的寒冬过后,几度徘徊后,待春暖花开后归来。
    尽管20年还有计划未完成,会有一些遗憾,一些心愿,但是我们向前看,向往新的一年,希望自己能够科研上有所成果,技术上也变的更强,为人处世方面也有所加强,也希望大家能够长风破浪会有时,直挂云帆济沧海。
    下面继续分享每周一篇论文阅读。

    ICLR20| 融合多关系图卷积网络COMPGCN

    论文链接: https://dl.acm.org/doi/10.1145/3394486.3403209
    代码链接:https://github.com/malllabiisc/CompGCN

    在这里插入图片描述

    我们现实世界的复杂关系一般是异质图,但是现在GCN一般是应用在同质图上,这就为我们真实建模应用上带来了很大的限制。相比GCN的同质图,知识图谱从拓扑结构上来看,其实也是一个异质图,不同的是,知识图谱增加了规则限制,因此适合逻辑推理,但是节点数和边关系数量很大,导致一般的GNN算法无法直接应用到知识图谱上。目前知识图谱嵌入的方法主流还是基于三元组的方法。但是我们可以利用知识图谱的优势来应用到异质图上,从节点和边的关系表示来增强学习。

    Abstract

    作者将多重关系融入到同质图中,每个边都有与之关联的标签和方向。 处理此类图的大多数现有方法都存在过拟合问题,并且仅限于学习节点表示。 在本文中,我们提出COMPGCN,这是一种新颖的图卷积框架,它将节点和关系共同嵌入到关系图中。 COMPGCN利用了来自知识图嵌入技术的各种实体关系组合操作,并根据关系的数量进行缩放。 我们在节点分类,链接预测和图分类等多项任务上评估了我们提出的方法,并取得了明显的优异结果。

    1 Instruction

    嵌入知识图(KG)方面已进行了广泛的研究(Nickel等,2016; Wang等,2017),其中共同学习了节点和关系的表示。 这些方法仅限于使用链接预测目标学习嵌入。由于GCN应用很大程度上只限于同质图,因此需要一种可以利用KG嵌入技术来学习特定于任务的节点和关系嵌入的框架。 在本文中,我们提出了COMPGCN,这是一种用于多关系图的新颖GCN框架,该框架系统地利用了来自知识图嵌入技术的实体-关系组合操作。 COMPGCN通过共同学习图中的节点和关系的矢量表示,解决了先前提出的GCN模型的缺点。 图1给出了COMPGCN的概述。

    在这里插入图片描述

    我们的工作可以总结如下:

    1. 我们提出了COMPGCN,这是一种在图卷积网络中整合多关系信息的新颖框架,该框架利用了各种知识图谱嵌入技术将节点和关系共同嵌入图中。
    2. 我们证明,COMPGCN框架概括了几种现有的多关系GCN方法(命题4.1),并且随着图中关系数量的增加而扩展(第6.3节)。
    3. 通过对节点分类,链接预测和图分类等任务的广泛实验,我们证明了所提方法的有效性。

    2 Background

    这节我们为GCNs应用无向图和它拓展到有向关系图做一个总结。

    GCN在无向图应用:给定一个图 G = ( V , E , X ) G =(V,E,X) G=VEX,其中V表示一组节点,E表示一组边,而 X ∈ R ∣ V ∣ × d 0 X∈R ^{| V |×d_0} XRV×d0表示每个节点的d0维输入特征。

    从单个GCN层获得的节点表示定义为: H = f ( A ^ X W ) H = f(\hat{A}XW) H=fA^XW。 在此,将 A ^ = D − 1 2 ( A + I ) D − 1 2 \hat{A} =D^{-\frac{1}{2}}(A + I)D^{-\frac{1}{2}} A^D21A+ID21定义是添加了自连接的归一化邻接矩阵,和D定义为 D i i ( A + I ) i j D_{ii}(A + I)_{ij} DiiA+Iij。 模型参数由 W ∈ R d 0 × d 1 W∈R^{d_0×d1} WRd0×d1表示,f是一些激活函数。 GCN表示形式H对图形中每个节点的直接邻域进行编码。 为了捕获图形中的多跳相关性,可以堆叠几个GCN层,一层如下: H k + 1 = f ( A ^ H k W k ) H^{k + 1} = f(\hat{A}H^kW^k) Hk+1=fA^HkWk,其中k表示层数, W k ∈ R d k × d k + 1 W^k∈R^{d_k×d_k + 1} WkRdk×dk+1 是特定于图层的参数,并且 H 0 = X H^0 =X H0=X

    GCN在多关系图上: 对于一个多关系图 G = ( V , R , E , X ) G=(V,R,E,X) G=V,R,E,X ,这里R表示关系集,每个边(u,v,r)表示从节点u到v存在关系r∈R , GCN公式基于以下假设: 有向边沿两个方向流动。 因此,对于每个边(u,v,r)∈E,逆边(v,u, r − 1 r^{-1} r1)包括在G中。在k层有向GCN层之后获得的表示形式为
    H k + 1 = f ( A ^ H k W r k ) H^{k + 1}=f( \hat{A}H^kW^k_ r ) Hk+1=f(A^HkWrk)
    这里, W r k W^k _r Wrk表示模型的关系特定参数。 但是,上述公式导致关系数量过多的过度参数化,因此Marcheggiani&Titov(2017)使用了特定于方向的权重矩阵。 Schlichtkrull等。 (2017)通过提出 W r k W^k_ r Wrk的块对角分解来解决过度参数化问题。

    3 Method

    在本节中,我们将对提出的方法COMPGCN进行详细说明。 总体架构如图1所示。我们用第2节中定义的 G = ( V , R , E , X , Z ) G =(V,R,E,X,Z) G=VREXZ表示多关系图,其中 Z ∈ R ∣ R ∣ × d 0 Z∈R ^{| R |\times d0} ZRR×d0表示初始关系特征。 我们的模型是受使用Chebyshev多项式的GCN的一阶逼近(Kipf&Welling,2016)启发的。 继Marcheggiani&Titov(2017)之后,我们还允许有向边的信息沿两个方向流动。 因此,我们用相应的反边和关系扩展E和R,即
    E ′ = E ∪ ( v , u , r − 1 ) ∣ ( u , v , r ) ∈ E ∪ ( u , u , T ) ∣ u ∈ V ) , E'= E ∪ {(v, u, r^{−1}) | (u, v, r) ∈ E} ∪ {(u, u,T) | u ∈ V)}, E=E(v,u,r1)(u,v,r)E(u,u,T)uV),
    R ′ = R ∪ R i n v ∪ T R' = R∪R_{inv}∪{T} R=RRinvT,其中 R i n v = { r − 1 ∣ r ∈ R } R_{inv} = \{r^{-1} | r∈R\} Rinv={r1rR}表示反向关系,T 表示自循环。

    在这里插入图片描述

    3.1 融合关系

    与大多数现有的仅在图中嵌入节点的方法不同,COMPGCN学习d维表示 h r ∈ R d h_r∈R^d hrRd,∀r∈R以及节点嵌入hv∈Rd,∀v∈V。将关系表示为矢量可以缓解以下问题: 在关系图上应用GCN时过度参数化。 此外,它允许COMPGCN利用任何可用的关系特征(Z)作为初始表示。 为了将关系嵌入合并到GCN公式中,我们利用知识图嵌入方法(Bordes等,2013; Nickel等,2016)中使用的实体-关系组合操作,其形式为
    e o = φ ( e s , e r ) . eo=φ(es, er). eo=φ(es,er).
    在此,φ:Rd×Rd→Rd是一个融合算子,s,r和o表示知识图中的主体,关系和客体,而e(·)∈Rd表示其对应的嵌入。 在本文中,我们将自己局限于非参数化运算,例如减法(Bordes等,2013),乘法(Yang等,2014)和循环相关(Nickel等,2016)。 但是,COMPGCN可以扩展到参数化操作,例如神经张量网络(NTN)(Socher等人,2013)和ConvE(Dettmers等人,2018)。 我们将他们的分析作为以后的工作。
    正如我们在第6节中所示,合成操作的选择对于确定学习的嵌入的质量很重要。 因此,可以采用未来开发的知识图的出色合成操作来进一步提高COMPGCN的性能。

    3.2 更新参数

    第二节定义的GCN更新方程式可以重写为
    h v = f ( ∑ ( u , r ) ∈ N ( v ) W r h u ) h_v = f( \sum_{(u,r)∈N(v) } W_rh_u) hv=f((u,r)N(v)Wrhu)
    其中N(v)是v的输出边缘的v的直接邻居的集合。 由于该公式存在过度参数化的问题,因此在COMPGCN中,我们按照上述关系r执行邻节点u的合成(φ)。 这使我们的模型在特征维数上呈线性(O(| R | d))的同时也可以感知关系。 此外,为了区别对待原始边缘,反边缘和自身边缘,我们为每个边缘定义了单独的过滤器。 COMPGCN的更新公式为:
    h v = f ( ∑ ( u , r ) ∈ N ( v ) W λ ( r ) φ ( x u , z r ) ) h_v = f (\sum_{(u,r)∈N(v)} W_{λ(r)}φ(x_u, z_r) ) hv=f((u,r)N(v)Wλ(r)φ(xu,zr))
    其中 x u , z r x_u,z_r xuzr分别表示节点u和关系r的初始特征, h v h_v hv表示节点v的更新表示,并且 W λ ( r ) ∈ R d 1 × d 0 W_{λ(r)}∈R^{d1×d0} WλrRd1×d0是关系类型特定的参数。 在COMPGCN中,我们使用特定于方向的权重,即λ(r)= dir(r),表示为:

    在这里插入图片描述

    在这里插入图片描述

    此外,在COMPGCN中,在等式中定义的节点嵌入更新之后。

    关系嵌入也如下转换:

    在这里插入图片描述

    其中 W r e l ∈ R d 1 × d 0 W_{rel}∈R^{d1×d0} WrelRd1×d0 是一个可学习的变换矩阵,它将所有关系投影到与节点相同的嵌入空间中,并允许它们在下一个COMPGCN层中使用。 在表1中,我们在COMPGCN和其他现有方法之间就功能和参数复杂性进行了对比。
    随着关系数量的增加而缩放为了确保COMPGCN随着关系数量的增加而缩放,我们使用Schlichtkrull等人提出的基础公式的一种变体。 (2017)。 它们不是为每个关系独立定义嵌入,而是将其表示为一组基本向量的线性组合。 正式地,让{v1,v2,…,vB}为一组可学习的基础向量。 然后,初始关系表示为:

    在这里插入图片描述

    在此, α b r α_{br} αbr∈R是关系和基础特定的可学习标量权重。

    关于与Relational-GCN的比较注意,这与Schlichtkrull等人的基础公式不同。 (2017),其中为每个GCN层定义了一组单独的基础矩阵。 相反,COMPGCN使用嵌入矢量而不是矩阵,并且仅为第一层定义基本矢量。 后面的层根据等式4通过转换共享关系。这使我们的模型比Relational-GCN更有效的参数。
    我们可以将等式2的公式扩展到具有k个堆叠的COMPGCN层的情况。 令hk + 1 v表示在k层之后获得的节点v的表示,定义为

    在这里插入图片描述

    类似地,令 h r k + 1 h^{k + 1}_ r hrk+1表示在k层之后关系r的表示。 然后,

    在这里插入图片描述

    在此, h v 0 h^0_ v hv0 h r 0 h^0_ r hr0分别是初始节点( x v x_v xv)和关系( z r z_r zr)特征。

    4. 实验

    作者分别从以下几个方面评估COMPGCN。

    • 链接预测是根据知识图中的已知事实推断缺失事实的任务。 在我们的实验中,我们利用FB15k-237(Toutanova&Chen,2015)和WN18RR(Dettmers et al。,2018)数据集进行评估。 继Bordes等。 (2013),我们使用过滤后的设置进行评估,并报告平均倒数排名(MRR),平均排名(MR)和Hits @ N。
    • 节点分类是根据节点特征及其连接来预测图中节点的标签的任务。 与Schlichtkrull等类似。 (2017),我们在MUTAG(Node)和AM(Ristoski&Paulheim,2016)数据集上评估了COMPGCN
    • 图分类,在给定一组图及其对应标签的情况下,目标是学习每个图的表示形式,然后将其表示给分类器进行预测。 我们评估了2个生物信息学数据集:MUTAG(图)和PTC(Yanardag&Vishwanathan,2015)。

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在节点分类上,与性能最佳的基线相比,我们在两个数据集上均获得了3%的平均改善,而在图形分类上,我们在PTC数据集上获得了3%的改善。

    5.总结

    在本文中,我们提出了COMPGCN,这是一种新颖的基于图卷积的多关系图框架,该框架利用了各种组合运算符,包括知识图嵌入技术,将节点和关系共同嵌入图中。 我们的方法概括了几种现有的多关系GCN方法。 此外,我们的方法通过跨层共享关系嵌入并使用基分解来缓解过参数化的问题。 通过对知识图链接预测,节点分类和图分类任务的广泛实验,我们证明了COMPGCN相对于现有基于GCN的方法的有效性,并证明了随着关系数量的增加,它的可扩展有效性。

    展开全文
  • 通过联合学习图中节点和关系的向量表示,COMPGCN解决了以前提出的GCN模型的缺点。图1给出了COMPGCN的概述。我们工作的贡献可总结如下:7 结论 摘要 图卷积网络(GCNs)最近被证明在建模图结构数据方面非常成功。然而,...

    文章目录


    参考阅读: https://blog.csdn.net/sinat_28978363/article/details/105298286

    摘要

    图卷积网络(GCNs)最近被证明在建模图结构数据方面非常成功。然而,主要的焦点是处理简单的无向图。多关系图是一种更一般和普遍的图形式,其中每条边都有一个标签和与之相关的方向。大多数现有的处理此类图的方法都存在过度参数化的问题,并且仅限于学习节点表示。在本文中,我们提出了一种新的图卷积框架CompGCN,它将节点和关系共同嵌入到关系图中。CompGCN利用了来自知识图谱嵌入技术的各种实体-关系组合操作,并根据关系的数量进行缩放。它还扩展了现有的几种多关系GCN方法。我们在节点分类、链接预测和图分类等多个任务上评估了我们提出的方法,并取得了明显的优越结果。我们提供COMPGCN的源代码,以促进可重复的研究。

    1 引言

    因此,需要一个能够利用KG嵌入技术来学习特定于任务的节点和关系嵌入的框架。在本文中,我们提出了一个新的多关系图GCN框架,该框架系统地利用了知识图嵌入技术中的实体-关系组合操作。通过联合学习图中节点和关系的向量表示,COMPGCN解决了以前提出的GCN模型的缺点。图1给出了COMPGCN的概述。我们工作的贡献可总结如下:

    • 我们提出了一种将多关系信息整合到图卷积网络中的新框架COMPGCN,该框架利用知识图嵌入技术的各种合成操作,将节点和关系共同嵌入到图中。
    • 我们证明了COMPGCN框架概括了几种现有的多关系GCN方法(命题4.1),并随着图中关系数量的增加而扩展(章节6.3)。
    • 通过在节点分类、链接预测和图分类等任务上的大量实验,我们证明了所提方法的有效性。

    7 结论

    在本文中,我们提出了一种新的基于图卷积的多关系图框架COMPGCN,该框架利用知识图嵌入技术中的各种合成算子来联合嵌入图中的节点和关系。我们的方法推广了现有的多关系GCN方法。此外,我们的方法通过跨层共享关系嵌入和使用基分解来缓解过度参数化的问题。通过对知识图链接预测、节点分类和图分类任务的大量实验,我们证明了COMPGCN优于现有的基于GCN的方法,并证明了其随着关系数量的增加而具有可扩展性。


    总结

    展开全文
  • 本文作者从实际的图数据特点出发,设计了一种针对多关系有向图的图神经网络 CompGCN 来同时学习节点和关系的表示。 同时,为了降低大量不同类型关系带来的参数,这里作者设计了一种分解操作 composition operation,...
  • 代码链接:https://github.com/malllabiisc/CompGCN 1、引言 图神经网络已经成为图数据分析领域的经典算法了,各大顶会上相关的论文也层出不穷.但是,这些工作主要关注点都在如何在简单无向图上设计一个更新颖更复杂的...
  • 代码地址:...本篇解析代码为[2s-AGCN/model/aagcn.py] import math import numpy as np import torch import torch.nn as nn from torch.autograd import Variable def import_class(name):...
  • 报错案例复现: def test(): return 1 a,b = test() print(a) 报错信息 Traceback (most recent call last): File "D:/pytest/thread_test/subprocess_pipe.py", line 5, in <...TypeError: cannot unpack non-...
  • CompGCN中,作者用关系的方向的来进行区分:   此外,为了统一边与结点之间的运算,作者用一个投影矩阵将边空间投影到节点空间:   为了避免随着关系数量的增加所带来的参数复杂性,CompGCN使用了一组基来作为...
  • 7.DropEdge: Towards Deep Graph Convolutional Networks on Node Classification 8.Composition-based Multi-Relational Graph Convolutional Networks 8.1 相关工作回顾 8.2 模型COMPGCN 8.3 实验 8.4 结论 9....
  • CompGCN的缩放能力 我们分析了具有不同数量的关系和基向量的COMPGCN的scalability。 变化关系基向量的影响 模型性能随着基础数量的增加而提高。作者注意到注意到在B = 100的情况下,模型的性能变得与所有关系都有其...
  • 100 7.4.2 带权重的图卷积编码器 101 7.4.3 知识图谱与图注意力模型 102 7.4.4 图神经网络与传统知识图谱嵌入的结合:CompGCN 103 7.5 小结 103 第 8 章 图神经网络模型的应用 105 8.1 图数据上的一般任务 ...
  • 1. 前言 论文链接:https://arxiv.org/abs/1911.03082?context=stat.ML github:https://github.com/malllabiisc/CompGCN
  • 关系图卷积网络 带权重的图卷积编码器 知识图谱与图注意力模型 图神经网络与传统知识图谱嵌入的结合:CompGCN 总结 知识图谱作为一种重要而特殊的图结构,在各个领域有着广泛的应用,知识图谱的表示学习为传统人工...
  • 将边的类型分成一对一、一对多、多对一以及多对多分析,GCN-based 模型(WGCN 与 COMPGCN)由于融合了图结构信息,其在复杂类型边上效果显著,而 RotatE 可以有效建模识别出关系模式中对称/反对称、反转和合成等四...
  • CompGCN采用编码-解码方法,其中图编码器构建节点和边的表示形式,然后解码器生成某些下游任务(如链接预测或节点分类)的分数。 CompGCN intuition. Source: Vashishth et al 节点表示是通过聚集来自相邻节点的...
  • 自适应深度和广度图神经网络模型 【知识图谱系列】知识图谱多跳推理之强化学习 【知识图谱系列】知识图谱的神经符号逻辑推理 【知识图谱系列】动态时序知识图谱EvolveGCN 【知识图谱系列】多关系神经网络CompGCN ...
  • CompGCN采用编码-解码方法,其中图编码器构建节点和边的表示形式,然后解码器生成某些下游任务(如链接预测或节点分类)的分数。 CompGCN intuition. Source: Vashishth et al 节点表示是通过聚集来自相邻节点的...
  • 【知识图谱系列】知识图谱多跳推理之强化学习 【知识图谱系列】知识图谱的神经符号逻辑推理 【知识图谱系列】动态时序知识图谱EvolveGCN 【知识图谱系列】多关系神经网络CompGCN 【机器学习系列】机器学习中的两大...
  • ICLR 2020 图神经学习论文汇总

    千次阅读 2020-09-08 15:20:02
    作者还将提议的CompGCN与其他现有的GCN变体进行了比较,并总结了CompGCN与其他模型之间的关系。 2 Graph Neural Networks Exponentially Lose Expressive Power for Node Classification   节点分类。随着层数达到...
  • 多关系神经网络CompGCN 【机器学习系列】机器学习中的两大学派 干货 | Attention注意力机制超全综述 干货 | NLP中的十个预训练模型 FastText原理和文本分类实战,看这一篇就够了 机器学习算法篇:最大似然估计证明...
  • 【知识图谱系列】动态时序知识图谱EvolveGCN 【知识图谱系列】多关系神经网络CompGCN 【知识图谱系列】探索DeepGNN中Over-Smoothing问题 【知识图谱系列】知识图谱表示学习综述 | 近30篇优秀论文串讲 【知识图谱系列...
  • 知识图谱综述:表示、获取及应用 这是研究生第一篇综述文章,第一次读也是花了好几天的时间。 摘要:人类的知识提供了对世界的一种形式的理解。表征实体之间结构关系的知识图已成为认知和人的智能研究的热门方向。...
  • CompGCN中,作者用关系的方向的来进行区分: 此外,为了统一边与结点之间的运算,作者用一个投影矩阵将边空间投影到节点空间: 为了避免随着关系数量的增加所带来的参数复杂性,CompGCN使用了一组基来作为可学习的...
  • 编辑: ShuYini 校稿: ShuYini 时间: 2020-02-21     2020年的ICLR会议将于今年的4月26日-4月30日在Millennium Hall, Addis Ababa ETHIOPIA(埃塞俄比亚首都亚的斯亚贝巴 千禧大厅)举行。 ...
  • ​ 5、Pytorch实现把一个Tensor中大于0的数字都置为0 ​ 6、实现编辑距离,O(n)空间复杂度 快手二面 ​ 1、介绍项目,结合项目聊了相关算法 ​ 2、在实际图业务数据中CompGCN算法的相关问题 ​ 3、编程题: 求树中两...
  • 提出 CompGCN,使用基向量分解。 hγk=f(∑(u,r)∈N(γ)Wλ(γ)kϕ(huk−1,hγk−1)){\mathbf h}^{k}_\gamma = f(\sum_{(u, r) \in N(\gamma)}W^{k}_{\lambda(\gamma)} \phi({\mathbf h^{k-1}_u}, h^{k-1}_\gamma))h...
  • 这时候,为什么不直接采用像R-GCN或CompGCN之类的多关系GNN编码器呢?在WebNLG上探测时,MGCN的收益约为46.5个BLEU点,而前面提到的KGPT收益在65+以上。 但是,MGCN仍然为ENT-DESC展示了强有力的基线,因此,鼓励...

空空如也

空空如也

1 2 3 4
收藏数 76
精华内容 30
关键字:

COMPGCN