0%

Survey on GNN

Survey on GNN

一、GNN相关研究Survey

0.Preliminary

关于图的一些概念和符号:

图的表示:节点集合$\mathcal{V}$,边集合$\mathcal\epsilon$。

邻接矩阵A,$a_{ij}$表示第i个节点到第j个节点的边的权重。

对角度矩阵(度矩阵)D,$d_{ii}$表示第i个节点的度。

拉普拉斯矩阵L = D - A,D是对角度矩阵。A是邻接矩阵。归一化的拉普拉斯矩阵是图的鲁棒的数学表示。

转移矩阵$P = D^{-1}A$

K近邻:$N_k(i)$,邻居节点$N_1(i) = N(i)$

关于GNN的基础概念和符号:

$F^V, F^E$,节点和边的特征值

$h^t_v$,第t层GNN中节点v的隐藏状态(或称属性)

$e^t_{ij}$,第t层中ij节点连接的边的隐藏状态(或称属性)

1.简介

主要参考:THU的《Deep Learning on Graphs: A Survey》《Graph Neural Networks: A Review of Methods and Applications》和Philip Yu组的《A Comprehensive Survey on Graph Neural Networks》这三篇最近的综述。中间穿插一些其他经典或最新论文的研究内容。

GNN是什么?把基于神经网络的模型使用在图领域(输入是图,在图结构上的推理,生成图结构的数据等)的相关方法。

为什么要用GNN?

  • 常规的图像声音视频等都是将数据转换到欧几里得空间(欧几里得结构数据),而有些数据(社交网络、知识图谱)无法进行欧几里得结构化。
  • 如果输入是图,那么CNN/RNN需要把节点的属性以一定的顺序stack起来处理,但是图的节点本质上是无序的。

  • 其次,边在传统NN的处理中只是被当做节点的属性,而图结构中它其实蕴含更多信息(如依赖信息等)。

  • 最后,高阶AI需要像人类一样从日常经验中利用推理图做决定或者判断(作者认为,无引用),这方面GNN才能做到(从无结构化数据中生成图)。

GNN分类,根据处理的任务类型:

  • Node-focus:节点分类、边预测、节点推荐等,
  • Graph-focus:图的分类(图的同构问题)、预测图的属性、图生成等。

GNN分类,根据

GNN分类:

  • 半监督:GNN,GCN,利用了图中节点的属性和标记来训练网络的参数。
  • 无监督:GAE,自编码器具有图结构
  • 最近的进展,GRNN,GRL(也可以归类为半监督,但是相关的方法还较少)

第二部分主要是一些GNN发展过程中比较重要的论文的阅读笔记。

2.GNN

以最初的GNN为例,来说明图神经网络是如何建模并学习的。

输入与输出:图中的每一个节点具有一个属性值$F^V$以及一个状态值$s_i$,每条边也具有一个属性值$F^E$。节点和边的属性值或者属性向量是输入的特征,我们希望求得每个节点的标签$\hat y_i$,状态值$s_i$是我们求解的中间结果。就像下面的公式所表示的。我们实际上要学习的是映射$\mathcal F和\mathcal O$。对于Graph-focus的任务,增加一个特殊节点表示整个图,一样的可以得到这个节点的标签。

目标函数:所有节点的标签和ground-truth的某种差值之和。

优化过程:首先利用jacobbi方法(把方程重写,并构建一个初始值,一直迭代求新的值直到满足一定条件)迭代求解状态值,直到到达某个不动点;而后利用当前状态值求解损失并反向传播更新参数;重复此步骤。

不足:求解状态值的步骤过于耗时;要求$\mathcal F(\cdot)$是一个压缩映射影响了表达能力;而且求解节点状态值到一个不动点不利用表达节点的信息,因为得到的解会过于smooth(各个节点得到的信息区分度不足,收敛于一个很接近的状态值)。

2.1 GCN

来自文章《Semi-Supervised Classification with Graph Convolutional Networks》(Max Welling组,ICLR’2017)

方法:

从谱图卷积说起,给定输入的x谱图卷积操作是:$g\theta \star x = Ug\theta(\wedge) U^T x$,其中U是拉普拉斯矩阵分解得到的特征向量矩阵$\wedge$是特征值矩阵,这个操作需要分解整张图的L矩阵,效率太低,因此经过了各种近似,最终这篇论文使用了如下的方式计算(下面的H就是X也就是输入向量):

1566630959989

1566630988382

这个公式做了这样一个操作:每个节点拿到邻居节点信息然后聚合到自身embedding上。在上面的公式中D−12~AD−12D−12A~D−12可以看成是归一化后的邻接矩阵,$H^{(l)}W^{(l)}$相当于给l层所有节点的embedding做了一次线性变换,左乘邻接矩阵表示对于每个节点来说,该节点的特征变为邻居节点特征相加后的结果。

最终,在N层网络之后,每个节点表示向量进行仿射变换之后softmax,就可以进行节点分类任务,并通过误差反向传播更新参数矩阵。

实验:在Citeseer和另外两个文献引用数据集,以及NELL这个小型知识图谱上面进行了节点分类任务。(大约3K-65K个节点,4K-266K条边的规模)

2.2 GraphSAGE

来自文章《Inductive Representation Learning on Large Graphs》(Leskovec组,Stanford,NIPS’2017)

1566632463526

已有方法的问题:1.慢;2.只涉及到了直推式学习(transductive learning)的setting,因为图数据中的每一个节点可以通过边的关系利用其他节点的信息,这样就产生了一个问题,如果训练集上的节点通过边关联到了预测集或者验证集的节点,那么在训练的时候能否用它们的信息呢? 如果训练时用到了测试集或验证集样本的信息(或者说,测试集和验证集在训练的时候是可见的), 我们把这种学习方式叫做transductive learning, 反之,称为inductive learning. 显然,我们所处理的大多数机器学习问题都是inductive learning, 因为我们刻意的将样本集分为训练/验证/测试,并且训练的时候只用训练样本。然而,在GCN中,训练节点收集邻居信息的时候,用到了测试或者验证样本,所以它是transductive的。

方法:SAGE的意思就是采样并聚合(sample and aggregate),说明了这个方法主要侧重于控制更新节点表示时涉及的邻域数量。首先对邻居采样(有放回的重采样方法直到采样数量足够),而后进行K次聚合,由K-hop的邻居开始到1-hop的邻居依次根据K个聚合网络和聚合参数更新自己的参数,最终目标样本再更新。实验中效果最好的平均聚合器(mean aggregator),平均聚合器的思路很简单,每个维度取对邻居embedding相应维度的均值。

参数学习:监督学习直接用节点样本进行交叉熵反向传播即可。非监督学习时,论文设计了一个优化目标函数,就是最小化广义邻居节点(定长随机游走能够到达的节点)的embedding,并通过负采样保证非邻居节点的embedding相似度较小。

实验:在一个论文引用数据集上进行论文分类实验,在Reddit数据集上进行帖子主题分类实验(都没有使用内容数据),此外还划分了训练测试集来测试inductive setting下的效果。

主要创新点:利用采样机制克服GCN的缺点,能够大规模应用。inductive框架,训练时只保留训练样本之间的边。

2.3 GAT

来自文章《GRAPH ATTENTION NETWORKS》(Bengio组,ICLR’2018)

已有方法的不足:

图结构数据常常含有噪声,意味着节点与节点之间的边有时不是那么可靠,邻居的相对重要性也有差异,解决这个问题的方式是在图算法中引入“注意力”机制(attention mechanism), 通过计算当前节点与邻居的“注意力系数”(attention coefficient), 在聚合邻居embedding的时候进行加权,使得图神经网络能够更加关注重要的节点,以减少边噪声带来的影响。

提出的方法:

图注意力机制就给定节点$V_i$,以及它的邻居节点集合$\mathcal N(i)$,将节点集合中的每个节点映射到[0, 1]值域的一个函数,该函数表示邻居节点的相对重要程度。

如下公式所示,节点0和邻居j的注意力权重是由一个参数化函数计算得到的,其中a和W是参数向量/矩阵。

1566659721923

此外,本工作还讨论了多头注意力机制(multi-head attention),该机制与Transformer中类似,不再赘述。

实验:

在Cora,Citeseer,Pubmed这三个Transductive的论文引用数据集(即不区分训练和验证集,节点数量2K-19K,边5K-44K),以及PPI这个包含24张图的Inductive数据集(蛋白质相互作用的数据集)上进行实验。并与GCN,GraphSAGE等SOTA的方法进行了详细对比,实验很充分。

创新点:针对图中包含噪音以及不同邻居节点重要程度不同这一事实,把注意力机制引入到GNN中。

相似工作:Kumparampil等人2018年提出直接利用余弦函数计算节点注意力权重。Lee等人2018年提出一种注意力引导的游走法,每个时间步游走到一个新的邻居节点,通过RNN来编码,并由当前步的隐状态确定下一步游走到哪个节点(和本工作的抽样法相比有所不同)。

2.4 其他一些有意思的工作(略读)

《Compositional Fairness Constraints for Graph Embeddings》(William Hamilton组,ICML’19)

面向推荐系统这个任务,为了实现公平约束(Fairness Constraints,即推荐系统学习到的表示不应该与某些属性相关,年龄或者性别),在GNN的基础上引入了一个对抗框架。

《Position-aware Graph Neural Networks》(Leskovec组,Stanford,ICML’19)

GraphSAGE的组的工作,希望改进现有GNN无法获取给定节点在整个图中的相对位置这一不足。首先确定图中一系列的锚节点集,然后对锚节点集进行采样,计算给定目标节点到每个锚集的距离,然后学习锚集上的非线性距离加权聚集方案。

《Estimating Node Importance in Knowledge Graphs Using Graph Neural Networks》(Faloutsos组,KDD’19)

聚焦估计知识图谱(KG)中节点的重要性这个任务,该任务对商品推荐和资源分配等多种下游应用十分重要。已有的方法没有充分利用KG中可用的信息,或者缺乏建模实体与其重要性之间复杂关系所需的灵活性。本文提出了一种有监督学习的GNN-based框架,通过predicate-aware注意力机制和灵活的中心性调整来执行重要性分数的聚合,而不是简单的聚合节点表示。

《Graph Contextualized Self-Attention Network for Session-based Recommendation》(xiaofang zhou组,昆士兰,IJCAL’19)

任务:基于会话的推荐系统。方法:利用GNN和子注意力机制结合。该方法动态地为会话序列构造一个图结构,并通过图神经网络(GNN)捕获丰富的局部依赖关系。然后,每个会话通过应用自注意力机制学习长期依赖关系。最后,每个会话都表示为全局首选项和当前会话兴趣的线性组合。

之后这三篇综述朝着不同的方向走了,Wenwu Zhu组的文章主要阐述了不同类别的神经网络方法如何被应用改造到图结构上面。

3.其他一些NN改造为GNN的变种

(1) GCN卷积图神经网络

a.卷积操作:产生节点的表示

  1. 谱方法,没大看懂,缺点就是计算量大、且不同图之间无法共享参数;
  2. 从效率方面的改进:ChebNet
  3. 从可扩展性(多图)方面的改进:Neural FPs, DCNN
  4. 框架性的,试图提出一种通用的图网络标准化操作:如MPNN

b.Readout操作:产生图的表示

这个操作必须具有顺序不变性。即如果图不变,那么节点的顺序(序号)不应该影响最终的值。

  1. 统计方法,sum,average和max-pool都行但是不够好,也可以加一个全连接层,但是代价就是无法保证顺序不变性。
  2. 层次聚类,比如DiffPool
  3. 其他方法,比如接受所有其他节点和边的信息并经过NN处理得到全图的表示(MPNN)

c.一些重要的模块与改进

  1. 注意力机制,注意力权重可以为卷积操作中邻居的权重进行学习(而不是预定义为完全一致)
  2. 残差连接,在计算节点表示的时候也一样可以用,在神经网络也可以帮助深层网络收敛。
  3. 边的特征,一种选择是根据边的类型训练不同的参数,并把结果汇集起来,但这种方式只能处理离散的边特征。DCNN把边转换为头尾节点上连接的两个特殊节点;另一类方法同时学习边和节点的表示,并通过若干函数进行交互。

d.通过采样进行加速

因为图的节点的度通常服从幂律分布(长尾分布)

  1. 总是采集固定数量的邻居节点用来更新当前节点的表达;或者使用随机游走来选择邻居(PinSage);
  2. 在卷积过程中根据节点的度(正则化之后)作为概率采样节点【FastGCN】;

e.归纳学习的setting

即在图的一部分节点/边上进行训练,并在另一部分节点/边上测试。

f.随机权重

没看懂,留着之后有需要再看吧。

(2) GAE图自编码器

a.自编码器

GAE源于稀疏自编码器,将邻接矩阵$P(i, :)$或其变种作为节点$i$的raw feature,以每个节点的L2重建误差作为损失,得到节点的低维表示向量后使用K-Means可以完成节点聚类任务。

SDNE进一步完整了SAE的理论,指出L2实际上对应着二阶逼近,因此在目标函数中增加一项代表一阶逼近的$\sum_{i,j=1}^N A(i,j)||h_i - h_j||_2$,这一项和拉普拉斯特征映射的目标函数很像。

DRNE利用LSTM来聚合邻居信息。

Graph2Gauss把每个节点映射为一个高斯分布来捕捉节点的随机性(通过学习节点属性到均值/方差的映射函数。优化的目标是KL散度,也就是如果i和j直接距离更近,那么i和j之间的KL散度也应该更小(分布更接近)。

b.变分自编码器

c.其他的一些研究

(3) 最近的研究

a.GRNN

这里的GRNN指的是在图级别使用RNN,而不是在GNN的节点级别使用RNN。

You等人使用两个RNN来生成节点以及边。

b.GRL

而Maosong Sun组的这篇文章主要侧重于讲原始GNN在各方面的改进,以及应用场景:

4. GNN的变种及应用场景

(1) 有向图

原始GNN应用在具有节点信息的无向图上,而有向边有时蕴含着更多的信息(比如信息的流动方向),ADGPM面向知识图谱,对有向边的头结点和尾节点分别使用不同的权重矩阵$W_c, W_p$来学习更好的结构化信息。

(2)异构图

具有不同节点类型的图被称为异构图,可以简单的把节点类型作为feature加入输入信息中,GraphInception提出了一种metapath的思路来处理异构图。

(3)具有边信息的图

比如知识图谱中的边,表征不同的关系。

1.可以通过把图转化为二分图,边变成一个特殊节点,和原本连接的头节点/尾节点之间各有一条边来处理,并通过不同的参数矩阵来区分边的类型。

(4) Propagation Type

分析各种Aggregator和Updater的变种,Aggregator决定从当前节点的哪些相关节点如何使用哪些信息,Updator决定这些信息如何被应用于更新当前节点的hidden state。典型的这两个操作函数公式如下所示(来自GraphSAGE),其中第一个函数可以是对固定数量节点的Mean,Pooling或者LSTM操作:

卷积:一系列的谱方法与非谱方法,谱方法基于图的谱表示而非谱方法直接在图上定义卷积操作。

门限:LSTM和GRU的使用。比如在gather了邻居节点的信息后,使用GRU作为节点状态更新的单元。

Attention:GraphAttentionNetwork使用类似self-attention的机制,在propagation中attend over 邻居的信息,并借鉴了multi-head-attention。比如下面的计算方式,其中$\alpha$是正则化后的注意力权重:(这个式子就是GAT的aggregator,它的update函数不改变节点表示)

Skip-Connection:为了能够使多层GCN容易收敛的trick。

(5)训练方式的改进

用原始的GCN举例,它在训练上有这样一些不足:1.需要整个图的拉普拉斯矩阵;2.第N层的节点i的表示是由第N-1层其所有的邻居节点的表示更新得到的,因为每一层邻居可能有很多,所以存在感受野爆炸问题,梯度反向传播会很慢;3.在一个固定的图上训练,泛化性能不足。

对训练方式的改进主要有:

以可学习的聚合函数代替原本整个图的拉普拉斯矩阵;

使用各种采样的方式减少聚合时涉及到的邻居节点数量,从而减少感受野爆炸的问题

(6)框架性的模型尝试

一些研究者试图提出一种更加General的框架,把多种GNN的模型操作包含在内。有以下这样一些工作:

MPNN(Message Passing NN,2017):尝试包含GCN等在内的监督学习的GNN模型,包含message passing过程和read out 过程(对应综述中的两个过程)。此外利用最后一层所有节点的表示,来计算整个图的表示。M、U和R可以有不同设置,其中M可以是邻接矩阵和w节点表示的乘积,U可以是GRU,R可以是多层DNN。

NLNN(Non-local NN,2017):该框架能够在图结构上应用多种self-attention操作,f可以是点积、高斯、concat等操作,g可以是简单的仿射变换:

GN(Graph Network,2018):尝试提出一种包含MPNN和NLNN等方法的通用框架,利用(u,H,E)三元组定义图分别表示全局属性、点集合和边集合。每一个GN Block包含三个更新和三个聚合函数(左边和右边)其中右边的函数接受不定量参数并且参数顺序不影响结果;按顺序进行如下操作:更新边的表示、根据边的表示更新计算与节点i相关的聚合表示$\bar {e’_i}$、更新节点的表示、根据边的表示更新计算全局聚合表示$\bar {e’}$,根据节点的表示更新计算全局聚合表示$\bar {h’}$,更新全局属性$u’$。

1566612142166

(7)应用场景

交通信息、社交网络、推荐系统以及物理化学领域。下面稍微展开几个领域应用:

知识图谱:利用GNN解决知识图谱补全中的未见实体问题(Out of KB Entity Problem),利用GCN解决多语言知识图谱对齐问题。

NLP中的分类问题:一般是将一句话或者一个段落看做是一张图(节点是一个word),然后用GNN来得到更好的总体编码。

序列标注:引入GNN的方式和分类问题类似,但是得到的顶层node表示可以用来预测标注信息。

文本生成:引入语义或者语法结构,比如在翻译任务中。

(8) 关于GNN未来的改进

现有的GNN无法应用深层神经网络,否则节点的表示会over-smoothing,即收敛到高度相似的值。

GNN如何应用在动态的图结构中而建模效果不会下降太多。

如何应用到大规模数据上。

(9)数据

实验:在主要研究GNN本身的工作中,基本上CiteSeer、Cora这几个学术论文引用的数据集,以及PPI、QM7b这种生物领域的数据集(分子或者蛋白质)已经成为事实上GNN效果判断的Benchmark。

二、GNN在NLP领域近期研究

0.GNN in NLP, Recent Studies

论文来自于ACL’19,论文列表中与GNN相关的有20多篇,选择其中几篇调研。

0.1 《Attention Guided Graph Convolutional Networks for Relation Extraction》

来自Wei Lu组,新加坡科技大学。

主要思路:Dependency trees传递丰富的结构信息,这些信息对于提取文本中实体之间的关系非常有用。然而,如何有效利用相关信息而忽略Dependency trees中的无关信息仍然是一个具有挑战性的研究问题。现有的方法大多使用基于规则的hard-pruning策略来选择相关的部分依赖结构,这个工作提出了一种直接以依赖树为输入的Attention Guided图卷积网络(AGGCNs)模型,期望该模型自动学习如何有选择地关注对关系提取任务有用的相关子结构。

模型框架:输入是依赖树(作为图处理),根据原有的邻接矩阵A,由多头注意力计算出N个代表不同权重的图,而后进入N个全连接层产生N个表示(可以认为代表依赖树的不同特征的N个图),最后由线性组合层产生最终的1个隐藏表示。

1566697021918

实验:在多句和单句关系抽取这两个任务上测试模型效果(TACRED & SemEval),和包括GCN、GraphLSTM在内的方法进行了比较。

0.2 《Cognitive Graph for Multi-Hop Reading Comprehension at Scale》

Jie Tang组,清华&阿里巴巴的工作。

思路:从认知科学中的对偶过程理论得到启发,通过一个隐式的抽取模块和一个显式的推理模块逐步迭代构建认知图。

首先解释一下对偶过程理论,就是说认知神经学的研究认为,人的大脑首先通过注意力寻找相关的信息(这是一个无意识、自发的、直观的过程)System1,而后通过一个可控制的、显示的、有意识的推理过程来找到答案(System2)。System1很快而System2工作时间更慢,需要在working memory中对信息进行顺序的解读和思考。

任务:Multi-Hop QA,其过程如下所示:其中涉及到的具有多种含义的实体,可能在相关的上下文文档中包含所需要的信息(supporting fact)。

1566702171998

方法:System 1负责产生问题+clues的表示,其中clues[x, G]就是认知图中x的前序节点的段落中的某些句子(推理所需要的句子)。同时系统1抽取上下文段落中与问题相关的实体和答案候选,实体以及相应的语义信息被用来组织为认知图(模拟working memory),System2用来对working memory进行推理,实现中就是GNN的节点表示的更新。持续推理过程直到某个答案候选概率超过阈值或认知图超过一定规模。

1566701958352

优势:可解释,答案的推理路径可知。

实验:在HotpotQA数据集上进行了实验,效果比现有方法好非常多。

0.3 《Coherent Comment Generation for Chinese Articles with a Graph-to-Sequence Model》

北大和腾讯的工作。

任务:自动文章评论,给定一个文章,自动生成一些与文章主题相关的评论内容。

以往方法的不足:对于现有的基于encoder-decoder的模型来说,新闻文档通常太长,这往往会导致一般性和不相关的评论。希望能够生成足够相关并且足够diverse的评论。

思路:总体上是一个Graph-to-Sequence框架,在encoder端首先构建一个文章图,首先进行命名实体识别和关键词提取并把提取后的词作为图的节点,而后判断文章每句话中是否包含关键词,如果包含就把这句话加入到这个词所在的节点,如果不同节点之间包含的句子有相同的,那么就增加一条无向边,边的权重由两个节点内容的相似度得到。而后通过GCN来编码节点表示并得到整个图的表示。

1566712761979

实验:在一个中文数据集腾讯快报上面进行了评论生成实验,并通过人工评价流畅度信息丰富程度来和其他方法比较。

创新点:以一种比较新颖的方式构建了图。

0.4 《Multi-hop Reading Comprehension across Multiple Documents by Reasoning over Heterogeneous Graphs》

Xiaodong He&Bowen Zhou组,京东的工作。

针对的任务也是需要multi-hop的RC。该任务给定1个问题,多个相关文档以及多个候选答案,需要从多个文档中进行多次推理才能找到正确答案。

首先,{C}、Q、{S}作为输入,经过GRU对三者分别编码,并抽取文档中的命名实体。而后构建HDE图,图的节点包括所有文档、候选以及命名实体;边的集合由人工定义的7种规则来构建;节点表示由基于co-attention 和 self-attention的上下文编码器初始化。

1566713648318

创新点:建立的图是异构的,由不同粒度的节点组成,包括候选答案、文档以及实体,同时也包含不同类型的边;这样能够充分利用不同粒度的信息进行推理。