GNN图神经网络详述-02

小咪咪 2023-02-13 03:29 48阅读 0赞

本文作为第2部分，主要根据原始论文介绍几篇基础的工作，主要包括GNN，GCN及变体，DCNN，Tree-LSTM,包括模型的详解和模型训练，以及模型评价。

# 1. The Graph Neural Network Model #

*  论文：[2009 -《The Graph Neural Network Model 》][2009 -_The Graph Neural Network Model]

这篇论文是第一个提出Graph Neural Network模型的论文，它将神经网络使用在图结构数据上，并细述了神经网络模型了结构组成、计算方法、优化算法、流程实现等等。论文后面还对模型的复杂度进行了评估，以及在现实任务上进行了实验和比较(比较算法为NL、L、FNN)。该报告暂时**主要关注模型设计部分和实验结果部分，忽略复杂性评估部分**。

## 图领域应用 ##

对于图领域问题，假设函数 τ \\tau τ是将一个图 G G G和图中的一个节点 n n n转化为一个实值向量的函数  
 τ ( G , n ) ∈ R m \\tau(G,n)\\in\{R^m\} τ(G,n)∈Rm那么监督学习的任务就在于从已知样本中学习得到这样的函数。

图领域的应用主要可以分为两种类型：**专注于图的应用(graph-focused)和专注于节点的应用(node-focused)**。对于graph-focused的应用，函数 τ \\tau τ和具体的节点无关，(即 τ ( G ) \\tau(G) τ(G))，训练时，在一个图的数据集中进行分类或回归。对于node-focused的应用， τ \\tau τ函数依赖于具体的节点 n n n，即 τ ( G , n ) \\tau(G,n) τ(G,n)，如下：  
![在这里插入图片描述][20200527053252466.jpeg_pic_center]

*  图 **(a)** 是一个化学分子结构，能够使用图  **G G G** 进行表示，函数 τ ( G ) \\tau(G) τ(G)可能用于估计这种化学分子对人体有害的概率，因此，我们并不关注分子中具体的原子(相当于节点)，所以属于graph-focused应用。
 *  图 **(b)** 是一张城堡的图片，图片中的每一种结构都由节点表示，函数 τ ( G , n ) \\tau(G,n) τ(G,n)可能用于预测每一个节点是否属于城堡(图中的黑点)。这种类型属于node-focused应用。

### GNN模型详述 ###

GNN模型**基于信息传播机制，每一个节点通过相互交换信息来更新自己的节点状态，直到达到某一个稳定值**，GNN的输出就是在每个节点处，根据当前节点状态分别计算输出。

有如下定义：

*  一个图 G G G表示为一对 ( N , E ) (\\boldsymbol\{N\}, \\boldsymbol\{E\}) (N,E)，其中， N \\boldsymbol\{N\} N表示节点集合， E \\boldsymbol\{E\} E表示边集。
 *   n e \[ n \] ne\[n\] ne\[n\]表示节点 n n n的邻居节点集合
 *   c o \[ n \] co\[n\] co\[n\]表示以 n n n节点为顶点的所有边集合
 *   l n ∈ R l N \\boldsymbol\{l\}\_\{n\} \\in \\mathbb\{R\}^\{l\_\{N\}\} ln∈RlN表示节点 n n n的特征向量
 *   l ( n 1 , n 2 ) ∈ R l E \\boldsymbol\{l\}\_\{\\left(n\_\{1\}, n\_\{2\}\\right)\} \\in \\mathbb\{R\}^\{l\_\{E\}\} l(n1,n2)∈RlE表示边 ( n 1 , n 2 ) (n\_1,n\_2) (n1,n2)的特征向量
 *   l \\boldsymbol\{l\} l表示所有特征向量叠在一起的向量

> **注**：原论文里面 l \\boldsymbol\{l\} l表示label，但论文中的label指的是`features of objects related to nodes and features of the relationships between the objects`，也就是相关特征，所以这里一律使用特征向量翻译。

论文将图分为positional graph和nonpositional graph，对于positional graph，对于每一个节点 n n n，都会给该节点的邻居节点 u u u赋予一个position值 ν n ( u ) \\nu\_\{n\}(u) νn(u)，该函数称为injective function， ν n : n e \[ n \] → \{ 1 , … ∣ N ∣ \} \\nu\_\{n\} : \\mathrm\{ne\}\[n\] \\rightarrow\\\{1, \\ldots|\\mathbf\{N\}|\\\} νn:ne\[n\]→\{ 1,…∣N∣\}。

假设存在一个图-节点对的集合 D = G × N \\mathcal\{D\}=\\mathcal\{G\} \\times \\mathcal\{N\} D=G×N， G \\mathcal\{G\} G表示图的集合， N \\mathcal\{N\} N表示节点集合，**图领域问题可以表示成一个有如下数据集的监督学习框架**  
 L = \{ ( G i , n i , j , t i , j ) ∣ G i = ( N i , E i ) ∈ G ; n i , j ∈ N i ; t i , j ∈ R m , 1 ≤ i ≤ p , 1 ≤ j ≤ q i \} \\mathcal\{L\}=\\left\\\{\\left(\\boldsymbol\{G\}\_\{i\}, n\_\{i, j\}, \\boldsymbol\{t\}\_\{i, j\}\\right)| \\boldsymbol\{G\}\_\{i\}=\\left(\\boldsymbol\{N\}\_\{i\}, \\boldsymbol\{E\}\_\{i\}\\right) \\in \\mathcal\{G\}\\right.;n\_\{i, j\} \\in \\boldsymbol\{N\}\_\{i\} ; \\boldsymbol\{t\}\_\{i, j\} \\in \\mathbb\{R\}^\{m\}, 1 \\leq i \\leq p, 1 \\leq j \\leq q\_\{i\} \\\} L=\{ (Gi,ni,j,ti,j)∣Gi=(Ni,Ei)∈G;ni,j∈Ni;ti,j∈Rm,1≤i≤p,1≤j≤qi\} 其中， n i , j ∈ N i n\_\{i, j\} \\in \\boldsymbol\{N\}\_\{i\} ni,j∈Ni表示集合 N i ∈ N \\boldsymbol\{N\}\_\{i\} \\in \\mathcal\{N\} Ni∈N中的第 j j j个节点， t i , j \\boldsymbol\{t\}\_\{i, j\} ti,j表示节点 n i j n\_\{ij\} nij的期望目标(即标签)。

节点 n n n的状态用 x n ∈ R s \\boldsymbol\{x\}\_\{n\} \\in \\mathbb\{R\}^\{s\} xn∈Rs表示，该节点的输出用 o n \\boldsymbol\{o\}\_\{\\boldsymbol\{n\}\} on表示， f w f\_\{\\boldsymbol\{w\}\} fw为*local transition function*， g w g\_\{\\boldsymbol\{w\}\} gw为*local output function*，那么 x n \\boldsymbol\{x\}\_\{n\} xn和 o n \\boldsymbol\{o\}\_\{\\boldsymbol\{n\}\} on的更新方式如下  
 x n = f w ( l n , l c o \[ n \] , x n e \[ n \] , l n e \[ n \] ) o n = g w ( x n , l n ) \\begin\{array\}\{l\}\{\\boldsymbol\{x\}\_\{n\}=f\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{l\}\_\{n\}, \\boldsymbol\{l\}\_\{\\mathrm\{co\}\[n\]\}, \\boldsymbol\{x\}\_\{\\mathrm\{ne\}\[n\]\}, \\boldsymbol\{l\}\_\{\\mathrm\{ne\}\\left\[n\\right\]\}\\right)\} \\\\ \{\\boldsymbol\{o\}\_\{n\}=g\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{x\}\_\{n\}, \\boldsymbol\{l\}\_\{n\}\\right)\}\\end\{array\} xn=fw(ln,lco\[n\],xne\[n\],lne\[n\])on=gw(xn,ln)其中， l n , l co ⁡ \[ n \] , x n e \[ n \] , l n e \[ n \] \\boldsymbol\{l\}\_\{n\}, \\boldsymbol\{l\}\_\{\\operatorname\{co\}\[n\]\}, \\boldsymbol\{x\}\_\{\\mathrm\{ne\}\[n\]\}, \\boldsymbol\{l\}\_\{\\mathrm\{ne\}\[n\]\} ln,lco\[n\],xne\[n\],lne\[n\]分别表示节点 n n n的特征向量、与节点 n n n相连的边的特征向量、节点 n n n邻居节点的状态向量、节点 n n n邻居节点的特征向量。

假设 x , o , l , l N \\boldsymbol\{x\}, \\boldsymbol\{o\}, \\boldsymbol\{l\}, \\boldsymbol\{l\}\_\{N\} x,o,l,lN分别为所有的状态、所有的输出、所有的特征向量、所有节点的特征向量的叠加起来的向量，那么上面函数可以写成如下形式  
 x = F w ( x , l ) o = G w ( x , l N ) \\begin\{array\}\{l\}\{\\boldsymbol\{x\}=F\_\{\\boldsymbol\{w\}\}(\\boldsymbol\{x\}, \\boldsymbol\{l\})\} \\\\ \{\\boldsymbol\{o\}=\\boldsymbol\{G\}\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{x\}, \\boldsymbol\{l\}\_\{\\boldsymbol\{N\}\}\\right)\}\\end\{array\} x=Fw(x,l)o=Gw(x,lN)其中， F w F\_\{\\boldsymbol\{w\}\} Fw为*global transition function*， G w G\_\{\\boldsymbol\{w\}\} Gw为*global output function*，分别是 f w f\_\{\\boldsymbol\{w\}\} fw和 g w g\_\{\\boldsymbol\{w\}\} gw的叠加形式。

根据Banach的不动点理论，假设 F w F\_\{\\boldsymbol\{w\}\} Fw是一个压缩映射函数，那么式子有唯一不动点解，而且可以通过迭代方式逼近该不动点  
 x ( t + 1 ) = F w ( x ( t ) , l ) \\boldsymbol\{x\}(t+1)=F\_\{\\boldsymbol\{w\}\}(\\boldsymbol\{x\}(t), \\boldsymbol\{l\}) x(t\+1)=Fw(x(t),l)其中， x ( t ) \\boldsymbol\{x\}(t) x(t)表示 x \\boldsymbol\{x\} x在第 t t t个迭代时刻的值，对于任意初值，迭代的误差是以指数速度减小的，使用迭代的形式写出状态和输出的更新表达式为  
 x n ( t + 1 ) = f w ( l n , l c o \[ n \] , x n e \[ n \] ( t ) , l n e \[ n \] ) o n ( t ) = g w ( x n ( t ) , l n ) , n ∈ N \\begin\{aligned\} \\boldsymbol\{x\}\_\{n\}(t+1) &=f\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{l\}\_\{n\}, \\boldsymbol\{l\}\_\{\\mathrm\{co\}\[n\]\}, \\boldsymbol\{x\}\_\{\\mathrm\{ne\}\[n\]\}(t), \\boldsymbol\{l\}\_\{\\mathrm\{ne\}\[n\]\}\\right) \\\\ \\boldsymbol\{o\}\_\{n\}(t) &=g\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{x\}\_\{n\}(t), \\boldsymbol\{l\}\_\{n\}\\right), \\quad n \\in \\boldsymbol\{N\} \\end\{aligned\} xn(t\+1)on(t)=fw(ln,lco\[n\],xne\[n\](t),lne\[n\])=gw(xn(t),ln),n∈NGNN的信息传播流图以及等效的网络结构如下图所示

![在这里插入图片描述][20200527054859607.jpeg_pic_center]根据上图所示，顶端的图是原始的Graph，中间的图表示状态向量和输出向量的计算流图，最下面的图表示将更新流程迭代 T T T次，并展开之后得到等效网络图。

### 网络的学习算法设计 ###

GNN的学习就是估计参数 w \\boldsymbol\{w\} w，使得函数 φ w \\varphi\_\{\\boldsymbol\{w\}\} φw能够近似估计训练集  
 L = \{ ( G i , n i , j , t i , j ) ∣ G i = ( N i , E i ) ∈ G ; n i , j ∈ N i ; t i , j ∈ R m , 1 ≤ i ≤ p , 1 ≤ j ≤ q i \} \\mathcal\{L\}=\\left\\\{\\left(\\boldsymbol\{G\}\_\{i\}, n\_\{i, j\}, \\boldsymbol\{t\}\_\{i, j\}\\right)| \\boldsymbol\{G\}\_\{i\}=\\left(\\boldsymbol\{N\}\_\{i\}, \\boldsymbol\{E\}\_\{i\}\\right) \\in \\mathcal\{G\}\\right.;n\_\{i, j\} \\in \\boldsymbol\{N\}\_\{i\} ; \\boldsymbol\{t\}\_\{i, j\} \\in \\mathbb\{R\}^\{m\}, 1 \\leq i \\leq p, 1 \\leq j \\leq q\_\{i\} \\\} L=\{ (Gi,ni,j,ti,j)∣Gi=(Ni,Ei)∈G;ni,j∈Ni;ti,j∈Rm,1≤i≤p,1≤j≤qi\}其中， q i q\_i qi表示在图 G i G\_\{i\} Gi中监督学习的节点个数，对于graph-focused的任务，需要增加一个特殊的节点，该节点用来作为目标节点，这样，graph-focused任务和node-focused任务都能统一到节点预测任务上，学习目标可以是最小化如下二次损失函数  
 e w = ∑ i = 1 p ∑ j = 1 q i ( t i , j − φ w ( G i , n i , j ) ) 2 e\_\{\\boldsymbol\{w\}\}=\\sum\_\{i=1\}^\{p\} \\sum\_\{j=1\}^\{q\_\{i\}\}\\left(\\boldsymbol\{t\}\_\{i, j\}-\\varphi\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{G\}\_\{i\}, n\_\{i, j\}\\right)\\right)^\{2\} ew=i=1∑pj=1∑qi(ti,j−φw(Gi,ni,j))2优化算法基于随机梯度下降的策略，优化步骤按照如下几步进行

*  按照迭代方程迭代 T T T次得到 x n ( t ) x\_\{n\}(t) xn(t)，此时接近不动点解： x ( T ) ≈ x \\boldsymbol\{x\}(T) \\approx \\boldsymbol\{x\} x(T)≈x
 *  计算参数权重的梯度 ∂ e w ( T ) / ∂ w \\partial e\_\{\\boldsymbol\{w\}\}(T) / \\partial \\boldsymbol\{w\} ∂ew(T)/∂w
 *  使用该梯度来更新权重 w \\boldsymbol\{w\} w

> 这里假设函数 F w F\_\{\\boldsymbol\{w\}\} Fw是压缩映射函数，保证最终能够收敛到不动点。另外，这里的梯度的计算使用*backpropagation-through-time algorithm*。

为了表明前面的方法是可行的，论文接着证明了两个结论

--------------------

> 理论1(可微性)：令 F w F\_\{\\boldsymbol\{w\}\} Fw和 G w G\_\{\\boldsymbol\{w\}\} Gw分别是global transition function和global output function，如果 F w ( x , l ) F\_\{\\boldsymbol\{w\}\}(\\boldsymbol\{x\}, \\boldsymbol\{l\}) Fw(x,l)和 G w ( x , l N ) G\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{x\}, \\boldsymbol\{l\}\_\{\\boldsymbol\{N\}\}\\right) Gw(x,lN)对于 x \\boldsymbol\{x\} x和 w \\boldsymbol\{w\} w是连续可微的，那么 φ w \\varphi\_\{\\boldsymbol\{w\}\} φw对 w \\boldsymbol\{w\} w也是连续可微的。

> 理论2(反向传播)：令 F w F\_\{\\boldsymbol\{w\}\} Fw和 G w G\_\{\\boldsymbol\{w\}\} Gw分别是global transition function和global output function，如果 F w ( x , l ) F\_\{\\boldsymbol\{w\}\}(\\boldsymbol\{x\}, \\boldsymbol\{l\}) Fw(x,l)和 G w ( x , l N ) G\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{x\}, \\boldsymbol\{l\}\_\{\\boldsymbol\{N\}\}\\right) Gw(x,lN)对于 x \\boldsymbol\{x\} x和 w \\boldsymbol\{w\} w是连续可微的。令 z ( t ) \\boldsymbol\{z\}(t) z(t)定义为  
>  z ( t ) = z ( t + 1 ) ⋅ ∂ F w ∂ x ( x , l ) + ∂ e w ∂ o ⋅ ∂ G w ∂ x ( x , l N ) z(t)=z(t+1) \\cdot \\frac\{\\partial F\_\{w\}\}\{\\partial x\}(x, l)+\\frac\{\\partial e\_\{w\}\}\{\\partial o\} \\cdot \\frac\{\\partial G\_\{w\}\}\{\\partial x\}\\left(x, l\_\{N\}\\right) z(t)=z(t\+1)⋅∂x∂Fw(x,l)\+∂o∂ew⋅∂x∂Gw(x,lN)  
> 那么，序列 z ( T ) , z ( T − 1 ) , … \\boldsymbol\{z\}(T), \\boldsymbol\{z\}(T-1), \\ldots z(T),z(T−1),…收敛到一个向量， z = lim ⁡ t → − ∞ z ( t ) z=\\lim \_\{t \\rightarrow-\\infty\} z(t) z=limt→−∞z(t)，并且收敛速度为指数级收敛以及与初值 z ( T ) \\boldsymbol\{z\}(T) z(T)无关，另外，还存在  
>  ∂ e w ∂ w = ∂ e w ∂ o ⋅ ∂ G w ∂ w ( x , l N ) + z ⋅ ∂ F w ∂ w ( x , l ) \\frac\{\\partial e\_\{w\}\}\{\\partial \\boldsymbol\{w\}\}=\\frac\{\\partial e\_\{\\boldsymbol\{w\}\}\}\{\\partial \\boldsymbol\{o\}\} \\cdot \\frac\{\\partial G\_\{\\boldsymbol\{w\}\}\}\{\\partial \\boldsymbol\{w\}\}\\left(\\boldsymbol\{x\}, \\boldsymbol\{l\}\_\{N\}\\right)+\\boldsymbol\{z\} \\cdot \\frac\{\\partial F\_\{\\boldsymbol\{w\}\}\}\{\\partial \\boldsymbol\{w\}\}(\\boldsymbol\{x\}, \\boldsymbol\{l\}) ∂w∂ew=∂o∂ew⋅∂w∂Gw(x,lN)\+z⋅∂w∂Fw(x,l)  
> 其中， x \\boldsymbol\{x\} x是GNN的稳定状态。

算法流程如下  
![在这里插入图片描述][20200527055030162.png_pic_center]  
**FORWARD**用于迭代计算出收敛点，**BACKWARD**用于计算梯度。

### Transition和Output函数实现 ###

在GNN中，函数 g w g\_\{\\boldsymbol\{w\}\} gw不需要满足特定的约束，直接使用多层前馈神经网络，对于函数 f w f\_\{\\boldsymbol\{w\}\} fw，则需要着重考虑，因为 f w f\_\{\\boldsymbol\{w\}\} fw需要满足压缩映射的条件，而且与不动点计算相关。下面提出两种神经网络和不同的策略来满足这些需求

1.  **Linear(nonpositional) GNN**：
    
    对于节点 n n n状态的计算，将 f w f\_\{\\boldsymbol\{w\}\} fw改成如下形式  
     x n = ∑ u ∈ ne ∣ n \] h w ( l n , l ( n , u ) , x u , l u ) , n ∈ N \\boldsymbol\{x\}\_\{n\}=\\sum\_\{u \\in \\text \{ ne \} | n \]\} h\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{l\}\_\{n\}, \\boldsymbol\{l\}\_\{(n, u)\}, \\boldsymbol\{x\}\_\{u\}, \\boldsymbol\{l\}\_\{u\}\\right), \\quad n \\in \\boldsymbol\{N\} xn=u∈ ne ∣n\]∑hw(ln,l(n,u),xu,lu),n∈N 相当于是对节点 n n n的每一个邻居节点使用 h w h\_\{\\boldsymbol\{w\}\} hw，并将得到的值求和来作为节点 n n n的状态。
    
    由此，对上式中的函数 h w h\_\{\\boldsymbol\{w\}\} hw按照如下方式实现  
     h w ( l n , l ( n , a ) , x u , l u ) = A n , u x u + b n h\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{l\}\_\{n\}, \\boldsymbol\{l\}\_\{(n, \\mathfrak\{a\})\}, \\boldsymbol\{x\}\_\{u\}, \\boldsymbol\{l\}\_\{u\}\\right) = \\boldsymbol\{A\}\_\{n, u\} \\boldsymbol\{x\}\_\{u\}+\\boldsymbol\{b\}\_\{n\} hw(ln,l(n,a),xu,lu)=An,uxu\+bn 其中，向量 b n ∈ R s \\boldsymbol\{b\}\_\{n\} \\in \\mathbb\{R\}^\{s\} bn∈Rs，矩阵 A n , u ∈ R s × s \\boldsymbol\{A\}\_\{n, u\} \\in \\mathbb\{R\}^\{s \\times s\} An,u∈Rs×s定义为两个前向神经网络的输出。更确切地说，令产生矩阵 A n , u \\boldsymbol\{A\}\_\{n, u\} An,u的网络为*transition network*，产生向量 b n \\boldsymbol\{b\}\_\{n\} bn的网络为*forcing network*
    
    transition network表示为 ϕ w \\phi\_\{\\boldsymbol\{w\}\} ϕw  
     ϕ w : R 2 l N + l E → R s 2 \\phi\_\{\\boldsymbol\{w\}\} : \\mathbb\{R\}^\{2 l\_\{N\}+l\_\{E\}\} \\rightarrow \\mathbb\{R\}^\{s^\{2\}\} ϕw:R2lN\+lE→Rs2  
    forcing network表示为 ρ w \\rho\_\{\\boldsymbol\{w\}\} ρw  
     ρ w : R l N → R s \\rho\_\{\\boldsymbol\{w\}\} : \\mathbb\{R\}^\{l\_\{N\}\} \\rightarrow \\mathbb\{R\}^\{s\} ρw:RlN→Rs 由此，可以定义 A n , u \\boldsymbol\{A\}\_\{n, u\} An,u和 b n \\boldsymbol\{b\}\_\{n\} bn  
     A n , u = μ s ∣ ne ⁡ \[ u \] ∣ ⋅ Ξ b w = ρ w ( l n ) \\begin\{aligned\} \\boldsymbol\{A\}\_\{\\boldsymbol\{n\}, \\boldsymbol\{u\}\} &=\\frac\{\\mu\}\{s|\\operatorname\{ne\}\[u\]|\} \\cdot \\boldsymbol\{\\Xi\} \\\\ \\boldsymbol\{b\}\_\{\\boldsymbol\{w\}\} &=\\rho\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{l\}\_\{n\}\\right) \\end\{aligned\} An,ubw=s∣ne\[u\]∣μ⋅Ξ=ρw(ln) 其中， μ ∈ ( 0 , 1 ) \\mu \\in(0,1) μ∈(0,1)， Ξ = resize ⁡ ( ϕ w ( l n , l ( n , u ) , l u ) ) \\Xi=\\operatorname\{resize\}\\left(\\phi\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{l\}\_\{n\}, \\boldsymbol\{l\}\_\{(n, u)\}, \\boldsymbol\{l\}\_\{u\}\\right)\\right) Ξ=resize(ϕw(ln,l(n,u),lu))， resize ( ⋅ ) \\text\{resize\}(\\cdot) resize(⋅)表示将 s 2 s^2 s2维的向量整理(reshape)成 s × s s\\times\{s\} s×s的矩阵，也就是说，将transition network的输出整理成方形矩阵，然后乘以一个系数就得到 A n , u \\boldsymbol\{A\}\_\{n, u\} An,u。 b n \\boldsymbol\{b\}\_\{n\} bn就是forcing network的输出。
    
    在这里，假定 ∥ ϕ w ( l n , l ( n , u ) , l u ) ∥ 1 ≤ s \\left\\|\\phi\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{l\}\_\{n\}, \\boldsymbol\{l\}\_\{(\\boldsymbol\{n\}, \\boldsymbol\{u\})\}, \\boldsymbol\{l\}\_\{u\}\\right)\\right\\|\_\{1\} \\leq \\boldsymbol\{s\} ∥∥ϕw(ln,l(n,u),lu)∥∥1≤s，这个可以通过设定transition function的激活函数来满足，比如设定激活函数为 t a n h ( ) tanh() tanh()。在这种情况下， F w ( x , l ) = A x + b F\_\{\\boldsymbol\{w\}\}(\\boldsymbol\{x\}, \\boldsymbol\{l\})=\\boldsymbol\{A\} \\boldsymbol\{x\}+\\boldsymbol\{b\} Fw(x,l)=Ax\+b， A \\boldsymbol\{A\} A和 b \\boldsymbol\{b\} b分别是 A n , u \\boldsymbol\{A\}\_\{n, u\} An,u的块矩阵形式和 b n \\boldsymbol\{b\}\_\{n\} bn的堆叠形式，通过简单的代数运算可得  
     ∥ ∂ F w ∂ x ∥ 1 = ∥ A ∥ 1 ≤ max ⁡ u ∈ N ( ∑ n ∈ ne ⁡ \[ u \] ∥ A n , u ∥ 1 ) ≤ max ⁡ u ∈ N ( μ s ∣ ne ⁡ \[ u \] ∣ ⋅ ∑ n ∈ n e \[ u \] ∥ Ξ ∥ 1 ) ≤ μ \\begin\{aligned\}\\left\\|\\frac\{\\partial F\_\{\\boldsymbol\{w\}\}\}\{\\partial \\boldsymbol\{x\}\}\\right\\|\_\{1\} &=\\|\\boldsymbol\{A\}\\|\_\{1\} \\leq \\max \_\{u \\in \\boldsymbol\{N\}\}\\left(\\sum\_\{n \\in \\operatorname\{ne\}\[u\]\}\\left\\|\\boldsymbol\{A\}\_\{n, u\}\\right\\|\_\{1\}\\right) \\\\ & \\leq \\max \_\{u \\in N\}\\left(\\frac\{\\mu\}\{s|\\operatorname\{ne\}\[u\]|\} \\cdot \\sum\_\{n \\in \\mathrm\{ne\}\[u\]\}\\|\\mathbf\{\\Xi\}\\|\_\{1\}\\right) \\leq \\mu \\end\{aligned\} ∥∥∥∥∂x∂Fw∥∥∥∥1=∥A∥1≤u∈Nmax⎝⎛n∈ne\[u\]∑∥An,u∥1⎠⎞≤u∈Nmax⎝⎛s∣ne\[u\]∣μ⋅n∈ne\[u\]∑∥Ξ∥1⎠⎞≤μ  
    该式表示 F w F\_\{\\boldsymbol\{w\}\} Fw对于任意的参数 w \\boldsymbol\{w\} w是一个压缩映射。
    
    > 矩阵 M M M的1-norm定义为  
    >  ∥ M ∥ 1 = max ⁡ j ∑ i ∣ m i , j ∣ \\|M\\|\_\{1\}=\\max \_\{j\} \\sum\_\{i\}\\left|m\_\{i, j\}\\right| ∥M∥1=jmaxi∑∣mi,j∣
2.  **Nonelinear(nonpositional) GNN**：在这个结构中， h w h\_\{\\boldsymbol\{w\}\} hw通过多层前馈网络实现，但是，并不是所有的参数 w \\boldsymbol\{w\} w都会被使用，因为同样需要保证 F w F\_\{\\boldsymbol\{w\}\} Fw是一个压缩映射函数，这个可以通过惩罚项来实现  
     e w = ∑ i = 1 p ∑ j = 1 q i ( t i , j − φ w ( G i , n i , j ) ) 2 + β L ( ∥ ∂ F w ∂ x ∥ ) e\_\{\\boldsymbol\{w\}\}=\\sum\_\{i=1\}^\{p\} \\sum\_\{j=1\}^\{q\_\{i\}\}\\left(\\boldsymbol\{t\}\_\{i, j\}-\\varphi\_\{\\boldsymbol\{w\}\}\\left(\\boldsymbol\{G\}\_\{i\}, n\_\{i, j\}\\right)\\right)^\{2\}+\\beta L\\left(\\left\\|\\frac\{\\partial F\_\{\\boldsymbol\{w\}\}\}\{\\partial \\boldsymbol\{x\}\}\\right\\|\\right) ew=i=1∑pj=1∑qi(ti,j−φw(Gi,ni,j))2\+βL(∥∥∥∥∂x∂Fw∥∥∥∥) 其中，惩罚项 L ( y ) L(y) L(y)在 y > μ y>\\mu y>μ时为 ( y − μ ) 2 (y-\\mu)^2 (y−μ)2，在 y ≤ μ y\\le\{\\mu\} y≤μ时为0，参数 μ ∈ ( 0 , 1 ) \\mu\\in(0,1) μ∈(0,1)定义为希望的 F w F\_\{\\boldsymbol\{w\}\} Fw的压缩系数。

### 实验结果 ###

论文将GNN模型在三个任务上进行了实验：子图匹配(subgraph matching)任务，诱变(mutagenesis)任务和网页排序(web page ranking)任务。在这些任务上使用linear和nonlinear的模型测试，其中nonlinear模型中的激活函数使用sigmoid函数。

子图匹配任务为在一个大图 G G G上找到给定的子图 S S S(标记出属于子图的节点)，也就是说，函数 τ \\tau τ必须学习到，如果 n i , j n\_\{i,j\} ni,j属于子图 G G G，那么 τ ( G i , n i , j ) = 1 \\tau(G\_i,n\_\{i,j\})=1 τ(Gi,ni,j)=1，否则， τ ( G i , n i , j ) = − 1 \\tau(G\_i,n\_\{i,j\})=-1 τ(Gi,ni,j)=−1。实验结果中，nonlinear模型的效果要好于linear模型的效果，两个模型都要比FNN模型效果更好。

诱变问题任务是对化学分子进行分类，识别出诱变化合物，采用二分类方法。实验结果是nonlinear效果较好，但不是最好。

网页排序任务是学会网页排序。实验表明虽然训练集只包含50个网页，但是仍然没有产生过拟合的现象。

### 模型实现 ###

在模拟的节点分类任务上实现该论文的GNN模型。

*  **任务要求**为输入一个graph，该graph的所有节点都有标签，然后对部分节点进行训练，在验证阶段使用另外一部分节点进行验证。输入的数据图如下图：

![在这里插入图片描述][20200527055513863.png_pic_center]  
其中，该graph总共有18个节点，分别是 \{ n 1 , n 2 , . . . , n 18 \} \\\{n1,n2,...,n18\\\} \{ n1,n2,...,n18\}，不同颜色的节点表示不同的节点类别。模拟的问题中节点类别有三类，分别用 \{ 0 , 1 , 2 \} \\\{0,1,2\\\} \{ 0,1,2\}表示，在训练阶段，使用节点 \{ n 1 , n 2 , n 3 , n 7 , n 8 , n 9 , n 13 , n 14 , n 15 \} \\\{n1,n2,n3,n7,n8,n9,n13,n14,n15\\\} \{ n1,n2,n3,n7,n8,n9,n13,n14,n15\}进行训练，相当于每一类取出三个节点训练，其余的节点用于在验证阶段进行验证。

输入的数据为`(node,label)`列表和`(node1, node2)`边列表，表示如下

# (node, label)集
    N = [("n{}".format(i), 0) for i in range(1,7)] + \
        [("n{}".format(i), 1) for i in range(7,13)] + \
        [("n{}".format(i), 2) for i in range(13,19)]
    # 边集
    E = [("n1","n2"), ("n1","n3"), ("n1","n5"),
         ("n2","n4"),
         ("n3","n6"), ("n3","n9"),
         ("n4","n5"), ("n4","n6"), ("n4","n8"),
         ("n5","n14"),
         ("n7","n8"), ("n7","n9"), ("n7","n11"),
         ("n8","n10"), ("n8","n11"), ("n8", "n12"),
         ("n9","n10"), ("n9","n14"),
         ("n10","n12"),
         ("n11","n18"),
         ("n13","n15"), ("n13","n16"), ("n13","n18"),
         ("n14","n16"), ("n14","n18"),
         ("n15","n16"), ("n15","n18"),
         ("n17","n18")]

N N N为节点集合， E E E为边集合。

*  模型部分使用论文的linear函数来设计 f w f\_w fw和 g w g\_w gw，而且，这两个函数在graph所有的节点上进行共享。模型部分实现了 Ξ \\Xi Ξ， ρ \\rho ρ函数，以及完整的forward传播部分，如下简化代码：
    
        # 实现Xi函数，输入一个batch的相邻节点特征向量对ln，返回是s*s的A矩阵
        # ln是特征向量维度，s为状态向量维度
        # Input : (N, 2*ln)
        # Output : (N, S, S)
        class Xi(nn.Module):
            def __init__(self, ln, s):
                ...
            def forward(self, X):
                ...
        
        # 实现Rou函数
        # Input : (N, ln)
        # Output : (N, S)
        class Rou(nn.Module):
            def __init__(self, ln, s):
                ...
            def forward(self, X):
                ...
        
        # 实现Hw函数
        # Input : (N, 2 * ln) 
        #         每一行都是一个节点特征向量和该节点的某一个邻接向量concat
        #         得到的向量
        # Input : (N, s)
        #         对应中心节点的状态向量
        # Input : (N, )
        #         对应中心节点的度的向量
        # Output : (N, s)
        class Hw(nn.Module):
            def __init__(self, ln, s, mu=0.9):
                ...
            def forward(self, X, H, dg_list):
                ...
        
        class AggrSum(nn.Module):
            def __init__(self, node_num):
                ...
            
            def forward(self, H, X_node):
                ...
        
        # 实现GNN模型
        class OriLinearGNN(nn.Module):
            def __init__(self, node_num, feat_dim, stat_dim, T):
                ...
            # Input : 
            #    X_Node : (N, )
            #    X_Neis : (N, )
            #    H      : (N, s)
            #    dg_list: (N, )
            def forward(self, X_Node, X_Neis, dg_list):
                ...
                for t in range(self.T):
                    # (V, s) -> (N, s)
                    H = torch.index_select(self.node_states, 0, X_Node)
                    # (N, s) -> (N, s)
                    H = self.Hw(X, H, dg_list)
                    # (N, s) -> (V, s)
                    self.node_states = self.Aggr(H, X_Node)
        #             print(H[1])
                ...
    
    **可以看出，在模型训练阶段，每次forward，都会直接循环计算T次 f w f\_w fw函数计算不动点，然后再计算output。**
 *  模型训练部分按照常规的分类模型进行训练，采用Adam优化器，学习率保持为0.01，权重衰减为0.01，使用交叉熵作为损失函数，模型训练部分代码如下
    
        # 用于计算accuracy
        def CalAccuracy(output, label):
            ...
        
        # 开始训练模型
        def train(node_list, edge_list, label_list, T, ndict_path="./node_dict.json"):
            # 生成node-index字典
            ...
        
            # 现在需要生成两个向量
            # 第一个向量类似于
            #   [0, 0, 0, 1, 1, ..., 18, 18]
            # 其中的值表示节点的索引，连续相同索引的个数为该节点的度
            # 第二个向量类似于
            #   [1, 2, 4, 1, 4, ..., 11, 13]
            # 与第一个向量一一对应，表示第一个向量节点的邻居节点
        
            # 首先统计得到节点的度
            ...
            
            # 然后生成两个向量
            ...
            # 生成度向量
            ...
            # 准备训练集和测试集
            train_node_list = [0,1,2,6,7,8,12,13,14]
            train_node_label = [0,0,0,1,1,1,2,2,2]
            test_node_list = [3,4,5,9,10,11,15,16,17]
            test_node_label = [0,0,0,1,1,1,2,2,2]
            
            # 开始训练
            model = OriLinearGNN(node_num=len(node_list),
                                 feat_dim=2,
                                 stat_dim=2,
                                 T=T)
            optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=0.01)
            criterion = nn.CrossEntropyLoss(size_average=True)
            
            min_loss = float('inf')
            node_inds_tensor = Variable(torch.Tensor(node_inds).long())
            node_neis_tensor = Variable(torch.Tensor(node_neis).long())
            train_label = Variable(torch.Tensor(train_node_label).long())
            for ep in range(500):
                # 运行模型得到结果
                res = model(node_inds_tensor, node_neis_tensor, dg_list) # (V, 3)
                train_res = torch.index_select(res, 0, torch.Tensor(train_node_list).long())
                test_res = torch.index_select(res, 0, torch.Tensor(test_node_list).long())
                loss = criterion(input=train_res,
                                 target=train_label)
                loss_val = loss.item()
                train_acc = CalAccuracy(train_res.cpu().detach().numpy(), np.array(train_node_label))
                test_acc = CalAccuracy(test_res.cpu().detach().numpy(), np.array(test_node_label))
                # 更新梯度
                optimizer.zero_grad()
                loss.backward(retain_graph=True)
                optimizer.step()
        
                if loss_val < min_loss:
                    min_loss = loss_val
                print("==> [Epoch {}] : loss {:.4f}, min_loss {:.4f}, train_acc {:.3f}, test_acc {:.3f}".format(ep, loss_val, min_loss, train_acc, test_acc))
 *  模型的训练和评估结果如下图:  
    ![在这里插入图片描述][20200527055634657.png_pic_center]  
    第一条曲线为训练loss曲线，第二条曲线为训练的acc曲线，第三条曲线为评估的acc曲线，可以看出，训练的loss很快达到了最低0.56左右，而准确率达到了1.0，基本已经过拟合，而验证集的准确率一直很低，最高在第500个epoch处上升到0.667，约为 2 3 \\frac\{2\}\{3\} 32左右。

# 2. Graph Convolutional Networks #

*  论文：[《Semi-Supervised Classification with Graph Convolutional Networks》][Semi-Supervised Classification with Graph Convolutional Networks]

## 图卷积的演变 ##

按照图傅里叶变换的性质，可以得到如下图卷积的定义  
 ( f ∗ h ) G = Φ diag ⁡ \[ h ^ ( λ 1 ) , … , h ^ ( λ n ) \] Φ T f (\\boldsymbol\{f\} \* \\boldsymbol\{h\})\_\{\\mathcal\{G\}\}=\\boldsymbol\{\\Phi\} \\operatorname\{diag\}\\left\[\\hat\{h\}\\left(\\lambda\_\{1\}\\right), \\ldots, \\hat\{h\}\\left(\\lambda\_\{n\}\\right)\\right\] \\mathbf\{\\Phi\}^\{T\} \\boldsymbol\{f\} (f∗h)G=Φdiag\[h^(λ1),…,h^(λn)\]ΦTf其中

*  对于图$ \\boldsymbol\{f\} 的 傅 里 叶 变 换 为 的傅里叶变换为 的傅里叶变换为\\boldsymbol\{\\hat\{f\}\}=\\mathbf\{\\Phi\}^\{T\} \\boldsymbol\{f\}$
 *  对于卷积核的图傅里叶变换： h ^ = ( h ^ 1 , … , h ^ n ) \\hat\{h\}=\\left(\\hat\{h\}\_\{1\}, \\ldots, \\hat\{h\}\_\{n\}\\right) h^=(h^1,…,h^n)，其中  
     h ^ k = ⟨ h , ϕ k ⟩ , k = 1 , 2 … , n \\hat\{h\}\_\{k\}=\\left\\langle h, \\phi\_\{k\}\\right\\rangle, k=1,2 \\ldots, n h^k=⟨h,ϕk⟩,k=1,2…,n 按照矩阵形式就是 h ^ = Φ T h \\hat\{\\boldsymbol\{h\}\}=\\mathbf\{\\Phi\}^\{T\} \\boldsymbol\{h\} h^=ΦTh
 *  对两者的傅里叶变换向量 f ^ ∈ R N × 1 \\hat\{f\} \\in \\mathbb\{R\}^\{N \\times 1\} f^∈RN×1和 h ^ ∈ R N × 1 \\hat\{h\} \\in \\mathbb\{R\}^\{N \\times 1\} h^∈RN×1求element-wise乘积，**等价于将 h \\boldsymbol\{h\} h组织成对角矩阵**，即 diag ⁡ \[ h ^ ( λ k ) \] ∈ R N × N \\operatorname\{diag\}\\left\[\\hat\{h\}\\left(\\lambda\_\{k\}\\right)\\right\] \\in \\mathbb\{R\}^\{N \\times N\} diag\[h^(λk)\]∈RN×N，然后再求 diag ⁡ \[ h ^ ( λ k ) \] \\operatorname\{diag\}\\left\[\\hat\{h\}\\left(\\lambda\_\{k\}\\right)\\right\] diag\[h^(λk)\]和 f \\boldsymbol\{f\} f矩阵乘法。
 *  求上述结果的傅里叶逆变换，即左乘 Φ \\mathbf\{\\Phi\} Φ。

深度学习中的卷积就是要**设计trainable的卷积核**，从上式可以看出，就是要设计 diag ⁡ \[ h ^ ( λ 1 ) , … , h ^ ( λ n ) \] \\operatorname\{diag\}\\left\[\\hat\{h\}\\left(\\lambda\_\{1\}\\right), \\ldots, \\hat\{h\}\\left(\\lambda\_\{n\}\\right)\\right\] diag\[h^(λ1),…,h^(λn)\]，由此，可以直接将其变为卷积核 diag ⁡ \[ θ 1 , … , θ n \] \\operatorname\{diag\}\\left\[\\theta\_\{1\}, \\ldots, \\theta\_\{n\}\\right\] diag\[θ1,…,θn\]，而**不需要再将卷积核进行傅里叶变换**，由此，相当于直接将变换后的参量进行学习。

### 第一代GCN ###

第一代GCN为  
 y output = σ ( Φ g θ Φ T x ) = σ ( Φ diag ⁡ \[ θ 1 , … , θ n \] Φ T x ) \\boldsymbol\{y\}\_\{\\text \{output\}\}=\\sigma\\left(\\mathbf\{\\Phi\} \\boldsymbol\{g\}\_\{\\theta\} \\mathbf\{\\Phi\}^\{T\} \\boldsymbol\{x\}\\right)=\\sigma\\left(\\boldsymbol\{\\Phi\} \\operatorname\{diag\}\\left\[\\theta\_\{1\}, \\ldots, \\theta\_\{n\}\\right\] \\mathbf\{\\Phi\}^\{T\} \\boldsymbol\{x\}\\right) youtput=σ(ΦgθΦTx)=σ(Φdiag\[θ1,…,θn\]ΦTx)  
其中， x \\boldsymbol\{x\} x就是graph上对应每个节点的feature构成的向量， x = ( x 1 , x 2 , … , x n ) x=\\left(x\_\{1\}, x\_\{2\}, \\ldots, x\_\{n\}\\right) x=(x1,x2,…,xn)，这里暂时对每个节点都使用标量，然后经过激活之后，得到输出 y output \\boldsymbol\{y\}\_\{\\text \{output\}\} youtput，之后传入下一层。

**一些缺点：**

*  需要对拉普拉斯矩阵进行谱分解来求 Φ \\mathbf\{\\Phi\} Φ，在graph很大的时候复杂度很高。另外，还需要计算矩阵乘积，复杂度为 O ( n 2 ) O(n^2) O(n2)。
 *  卷积核参数为 n n n，当graph很大的时候， n n n会很大。
 *  卷积核的spatial localization不好。

### 第二代GCN ###

图傅里叶变换是关于特征值(相当于普通傅里叶变换的频率)的函数，也就是 F ( λ 1 ) , … , F ( λ n ) F\\left(\\lambda\_\{1\}\\right), \\ldots, F\\left(\\lambda\_\{n\}\\right) F(λ1),…,F(λn)，即 F ( Λ ) F(\\mathbf\{\\Lambda\}) F(Λ)，因此，将卷积核 g θ \\boldsymbol\{g\}\_\{\\theta\} gθ写成 g θ ( Λ ) \\boldsymbol\{g\}\_\{\\theta\}(\\Lambda) gθ(Λ)，然后，将 g θ ( Λ ) \\boldsymbol\{g\}\_\{\\theta\}(\\Lambda) gθ(Λ)定义为如下**k阶多项式**  
 g θ ′ ( Λ ) ≈ ∑ k = 0 K θ k ′ Λ k g\_\{\\theta^\{\\prime\}\}(\\mathbf\{\\Lambda\}) \\approx \\sum\_\{k=0\}^\{K\} \\theta\_\{k\}^\{\\prime\} \\mathbf\{\\Lambda\}^\{k\} gθ′(Λ)≈k=0∑Kθk′Λk将卷积公式带入，可以得到  
 g θ ′ ∗ x ≈ Φ ∑ k = 0 K θ k ′ Λ k Φ T x = ∑ k = 0 K θ k ′ ( Φ Λ k Φ T ) x = ∑ k = 0 K θ k ′ ( Φ Λ Φ T ) k x = ∑ k = 0 K θ k ′ L k x \\begin\{aligned\} g\_\{\\theta^\{\\prime\}\} \* x & \\approx \\Phi \\sum\_\{k=0\}^\{K\} \\theta\_\{k\}^\{\\prime\} \\mathbf\{\\Lambda\}^\{k\} \\mathbf\{\\Phi\}^\{T\} \\boldsymbol\{x\} \\\\ &=\\sum\_\{k=0\}^\{K\} \\theta\_\{k\}^\{\\prime\}\\left(\\mathbf\{\\Phi\} \\mathbf\{\\Lambda\}^\{k\} \\mathbf\{\\Phi\}^\{T\}\\right) x \\\\ &=\\sum\_\{k=0\}^\{K\} \\theta\_\{k\}^\{\\prime\}\\left(\\mathbf\{\\Phi\} \\mathbf\{\\Lambda\} \\mathbf\{\\Phi\}^\{T\}\\right)^\{k\} x \\\\ &=\\sum\_\{k=0\}^\{K\} \\theta\_\{k\}^\{\\prime\} \\boldsymbol\{L\}^\{k\} x \\end\{aligned\} gθ′∗x≈Φk=0∑Kθk′ΛkΦTx=k=0∑Kθk′(ΦΛkΦT)x=k=0∑Kθk′(ΦΛΦT)kx=k=0∑Kθk′Lkx  
可以看出，这一代的GCN不需要做特征分解了，可以直接对Laplacian矩阵做变换，通过事先将Laplacian矩阵求出来，以及 L k \\boldsymbol\{L\}^\{k\} Lk求出来，前向传播的时候，就可以直接使用，复杂度为 O ( K n 2 ) O(Kn^2) O(Kn2)。

对于每一次Laplacian矩阵 L \\boldsymbol\{L\} L和 x \\mathbf\{x\} x相乘，对于节点 n n n，相当于从邻居节点 n e \[ n \] ne\[n\] ne\[n\]传递一次信息给节点 n n n，由于连续乘以了 k k k次Laplacian矩阵，那么相当于n节点的k-hop之内的节点能够传递信息给 n n n，**因此，实际上只利用了节点的K-Localized信息**。

另外，可以使用切比雪夫展开式来近似 L k \\boldsymbol\{L\}^\{k\} Lk，**任何k次多项式都可以使用切比雪夫展开式来近似**，由此，引入切比雪夫多项式的 K K K阶截断获得 L k \\boldsymbol\{L\}^\{k\} Lk近似，从而获得对 g θ ( Λ ) g\_\{\\theta\}(\\mathbf\{\\Lambda\}) gθ(Λ)的近似  
 g θ ′ ( Λ ) ≈ ∑ k = 0 K θ k ′ T k ( Λ ~ ) g\_\{\\theta^\{\\prime\}\}(\\mathbf\{\\Lambda\}) \\approx \\sum\_\{k=0\}^\{K\} \\theta\_\{k\}^\{\\prime\} T\_\{k\}(\\tilde\{\\mathbf\{\\Lambda\}\}) gθ′(Λ)≈k=0∑Kθk′Tk(Λ~)  
其中， Λ ~ = 2 λ max ⁡ Λ − I n \\tilde\{\\mathbf\{\\Lambda\}\}=\\frac\{2\}\{\\lambda\_\{\\max \}\} \\mathbf\{\\Lambda\}-\\boldsymbol\{I\}\_\{n\} Λ~=λmax2Λ−In， θ ′ ∈ R K \\boldsymbol\{\\theta\}^\{\\prime\} \\in \\mathbb\{R\}^\{K\} θ′∈RK为切比雪夫向量， θ k ′ \\theta\_\{k\}^\{\\prime\} θk′为第 k k k个分量，切比雪夫多项式 T k ( x ) T\_\{k\}(x) Tk(x)使用递归的方式进行定义： T k ( x ) = 2 x T k − 1 ( x ) − T k − 2 ( x ) T\_\{k\}(x)=2 x T\_\{k-1\}(x)-T\_\{k-2\}(x) Tk(x)=2xTk−1(x)−Tk−2(x)，其中， T 0 ( x ) = 1 , T 1 ( x ) = x T\_\{0\}(x)=1, T\_\{1\}(x)=x T0(x)=1,T1(x)=x。

此时，带入到卷积公式  
 g θ ′ ∗ x ≈ Φ ∑ k = 0 K θ k ′ T k ( Λ ~ ) Φ T x ≈ ∑ k = 0 K θ k ′ ( Φ T k ( Λ ~ ) Φ T ) x = ∑ k = 0 K θ k ′ T k ( L ~ ) x \\begin\{aligned\} \\boldsymbol\{g\}\_\{\\boldsymbol\{\\theta\}^\{\\prime\}\} \* \\boldsymbol\{x\} & \\approx \\mathbf\{\\Phi\} \\sum\_\{k=0\}^\{K\} \\theta\_\{k\}^\{\\prime\} T\_\{k\}(\\tilde\{\\boldsymbol\{\\Lambda\}\}) \\mathbf\{\\Phi\}^\{T\} \\boldsymbol\{x\} \\\\ &\\approx \\sum\_\{k=0\}^\{K\} \\theta\_\{k\}^\{\\prime\}\\left(\\mathbf\{\\Phi\} T\_\{k\}(\\tilde\{\\mathbf\{\\Lambda\}\}) \\mathbf\{\\Phi\}^\{T\}\\right) x \\\\ &=\\sum\_\{k=0\}^\{K\} \\theta\_\{k\}^\{\\prime\} T\_\{k\}(\\tilde\{\\boldsymbol\{L\}\}) \\boldsymbol\{x\} \\end\{aligned\} gθ′∗x≈Φk=0∑Kθk′Tk(Λ~)ΦTx≈k=0∑Kθk′(ΦTk(Λ~)ΦT)x=k=0∑Kθk′Tk(L~)x其中， L ~ = 2 λ max ⁡ L − I n \\tilde\{\\boldsymbol\{L\}\}=\\frac\{2\}\{\\lambda\_\{\\max \}\} \\boldsymbol\{L\}-\\boldsymbol\{I\}\_\{n\} L~=λmax2L−In。

因此，可以得到输出为  
 y output = σ ( ∑ k = 0 K θ k ′ T k ( L ~ ) x ) \\boldsymbol\{y\}\_\{\\text \{output\}\}=\\sigma\\left(\\sum\_\{k=0\}^\{K\} \\theta\_\{k\}^\{\\prime\} T\_\{k\}(\\tilde\{\\boldsymbol\{L\}\}) \\boldsymbol\{x\}\\right) youtput=σ(k=0∑Kθk′Tk(L~)x)

### 第三代GCN ###

这一代GCN**直接取切比雪夫多项式中 K = 1 K=1 K=1，此时模型是1阶近似**

将 K = 1 K=1 K=1， λ max ⁡ = 2 \\lambda\_\{\\max \}=2 λmax=2带入可以得到  
 g θ ′ ∗ x ≈ θ 0 ′ x + θ 1 ′ ( L − I n ) x = θ 0 ′ x + θ 1 ′ ( L − I n ) x = θ 0 ′ x − θ 1 ′ ( D − 1 / 2 W D − 1 / 2 ) x \\begin\{aligned\} \\boldsymbol\{g\}\_\{\\boldsymbol\{\\theta\}^\{\\prime\}\} \* \\boldsymbol\{x\} & \\approx \\boldsymbol\{\\theta\}\_\{0\}^\{\\prime\} \\boldsymbol\{x\}+\\theta\_\{1\}^\{\\prime\}\\left(\\boldsymbol\{L\}-\\boldsymbol\{I\}\_\{n\}\\right) \\boldsymbol\{x\} \\\\ &=\\boldsymbol\{\\theta\}\_\{0\}^\{\\prime\} \\boldsymbol\{x\}+\\theta\_\{1\}^\{\\prime\}\\left(\\boldsymbol\{L\}-\\boldsymbol\{I\}\_\{n\}\\right) \\boldsymbol\{x\} \\\\ &=\\theta\_\{0\}^\{\\prime\} \\boldsymbol\{x\}-\\theta\_\{1\}^\{\\prime\}\\left(\\boldsymbol\{D\}^\{-1 / 2\} \\boldsymbol\{W\} \\boldsymbol\{D\}^\{-1 / 2\}\\right) \\boldsymbol\{x\} \\end\{aligned\} gθ′∗x≈θ0′x\+θ1′(L−In)x=θ0′x\+θ1′(L−In)x=θ0′x−θ1′(D−1/2WD−1/2)x  
其中，归一化拉普拉斯矩阵 L = D − 1 / 2 ( D − W ) D − 1 / 2 = I n − D − 1 / 2 W D − 1 / 2 \\boldsymbol\{L\}=\\boldsymbol\{D\}^\{-1 / 2\}(\\boldsymbol\{D\}-\\boldsymbol\{W\}) \\boldsymbol\{D\}^\{-1 / 2\}=\\boldsymbol\{I\}\_\{n\}-\\boldsymbol\{D\}^\{-1 / 2\} \\boldsymbol\{W\} \\boldsymbol\{D\}^\{-1 / 2\} L=D−1/2(D−W)D−1/2=In−D−1/2WD−1/2。**为了进一步简化，令 θ 0 ′ = − θ 1 ′ \\theta\_\{0\}^\{\\prime\}=-\\theta\_\{1\}^\{\\prime\} θ0′=−θ1′，此时只含有一个参数 θ \\theta θ**  
 g θ ′ ∗ x = θ ( I n + D − 1 / 2 W D − 1 / 2 ) x g\_\{\\theta^\{\\prime\}\} \* x=\\theta\\left(I\_\{n\}+D^\{-1 / 2\} W D^\{-1 / 2\}\\right) x gθ′∗x=θ(In\+D−1/2WD−1/2)x  
由于 I n + D − 1 / 2 W D − 1 / 2 \\boldsymbol\{I\}\_\{n\}+\\boldsymbol\{D\}^\{-1 / 2\} \\boldsymbol\{W\} \\boldsymbol\{D\}^\{-1 / 2\} In\+D−1/2WD−1/2的**谱半径 \[ 0 , 2 \] \[0,2\] \[0,2\]太大，使用归一化的trick**  
 I n + D − 1 / 2 W D − 1 / 2 → D ~ − 1 / 2 W ~ D ~ − 1 / 2 \\boldsymbol\{I\}\_\{n\}+\\boldsymbol\{D\}^\{-1 / 2\} \\boldsymbol\{W\} \\boldsymbol\{D\}^\{-1 / 2\} \\rightarrow \\tilde\{\\boldsymbol\{D\}\}^\{-1 / 2\} \\tilde\{\\boldsymbol\{W\}\} \\tilde\{\\boldsymbol\{D\}\}^\{-1 / 2\} In\+D−1/2WD−1/2→D~−1/2W~D~−1/2  
其中， W ~ = W + I n \\tilde\{\\boldsymbol\{W\}\}=\\boldsymbol\{W\}+\\boldsymbol\{I\}\_\{n\} W~=W\+In， D ~ i j = Σ j W ~ i j \\tilde\{D\}\_\{i j\}=\\Sigma\_\{j\} \\tilde\{W\}\_\{i j\} D~ij=ΣjW~ij。

由此，带入卷积公式  
 g θ ′ ∗ x ⏟ R n × 1 = θ ( D ~ − 1 / 2 W ~ D ~ − 1 / 2 ⏟ R n × n ) x ⏟ R n × 1 \\underbrace\{g\_\{\\theta^\{\\prime\}\} \* x\}\_\{\\mathbb\{R\}^\{n \\times 1\}\}=\\theta\\left(\\underbrace\{\\tilde\{D\}^\{-1 / 2\} \\tilde\{W\} \\tilde\{D\}^\{-1 / 2\}\}\_\{\\mathbb\{R\}^\{n \\times n\}\}\\right) \\underbrace\{x\}\_\{\\mathbb\{R\}^\{n \\times 1\}\} Rn×1gθ′∗x=θ(Rn×nD~−1/2W~D~−1/2)Rn×1x  
如果**推广到多通道**，相当于每一个节点的信息是向量  
 x ∈ R N × 1 → X ∈ R N × C x \\in \\mathbb\{R\}^\{N \\times 1\} \\rightarrow X \\in \\mathbb\{R\}^\{N \\times C\} x∈RN×1→X∈RN×C  
其中， N N N是节点**数量**， C C C是通道数，或者称作表示节点的信息**维度数**。 X \\mathbf\{X\} X是节点的**特征矩阵**。

相应的卷积核参数变化  
 θ ∈ R → Θ ∈ R C × F \\theta \\in \\mathbb\{R\} \\rightarrow \\Theta \\in \\mathbb\{R\}^\{C \\times F\} θ∈R→Θ∈RC×F  
其中， F F F为卷积核数量。

那么卷积结果写成矩阵形式为  
 Z ⏟ R N × F = D ~ − 1 / 2 W ~ D ~ − 1 / 2 ⏟ R N × N X ⏟ R N × C Θ ⏟ R C × F \\underbrace\{Z\}\_\{\\mathbb\{R\}^\{N \\times F\}\}=\\underbrace\{\\tilde\{D\}^\{-1 / 2\} \\tilde\{W\} \\tilde\{D\}^\{-1 / 2\}\}\_\{\\mathbb\{R\}^\{N \\times N\}\} \\underbrace\{X\}\_\{\\mathbb\{R\}^\{N \\times C\}\} \\underbrace\{\\mathbf\{\\Theta\}\}\_\{\\mathbb\{R\}^\{C \\times F\}\} RN×FZ=RN×ND~−1/2W~D~−1/2RN×CXRC×FΘ  
上述操作**可以叠加多层，对上述输出激活一下，就可以作为下一层节点的特征矩阵**。

这一代GCN特点：

*  取 K = 1 K=1 K=1，相当于直接取邻域信息，类似于 3 × 3 3\\times\{3\} 3×3的卷积核。
 *  由于卷积核宽度减小，可以通过增加卷积层数来扩大感受野，从而增强网络的表达能力。
 *  增加了参数约束，比如 λ max ⁡ ≈ 2 \\lambda\_\{\\max \} \\approx 2 λmax≈2，引入归一化操作。

## 论文模型 ##

论文采用两层的GCN，用来在graph上进行半监督的节点分类任务，邻接矩阵为 A A A，首先计算出 A ^ = D ~ − 1 2 A ~ D ~ − 1 2 \\hat\{A\}=\\tilde\{D\}^\{-\\frac\{1\}\{2\}\} \\tilde\{A\} \\tilde\{D\}^\{-\\frac\{1\}\{2\}\} A^=D~−21A~D~−21，由此，前向网络模型形式如下  
 Z = f ( X , A ) = softmax ⁡ ( A ^ ReLU ⁡ ( A ^ X W ( 0 ) ) W ( 1 ) ) Z=f(X, A)=\\operatorname\{softmax\}\\left(\\hat\{A\} \\operatorname\{ReLU\}\\left(\\hat\{A\} X W^\{(0)\}\\right) W^\{(1)\}\\right) Z=f(X,A)=softmax(A^ReLU(A^XW(0))W(1))  
其中， W ( 0 ) ∈ R C × H W^\{(0)\} \\in \\mathbb\{R\}^\{C \\times H\} W(0)∈RC×H为输入层到隐藏层的权重矩阵，隐藏层的特征维度为 H H H， W ( 1 ) ∈ R H × F W^\{(1)\} \\in \\mathbb\{R\}^\{H \\times F\} W(1)∈RH×F为隐藏层到输出层的权重矩阵，softmax激活函数定义为 softmax ⁡ ( x i ) = 1 Z exp ⁡ ( x i ) \\operatorname\{softmax\}\\left(x\_\{i\}\\right)=\\frac\{1\}\{\\mathcal\{Z\}\} \\exp \\left(x\_\{i\}\\right) softmax(xi)=Z1exp(xi)， Z = ∑ i exp ⁡ ( x i ) \\mathcal\{Z\}=\\sum\_\{i\} \\exp \\left(x\_\{i\}\\right) Z=∑iexp(xi)，相当于对每一列做softmax，由此，得到**交叉熵损失函数**为  
 L = − ∑ l ∈ Y L ∑ f = 1 F Y l f ln ⁡ Z l f \\mathcal\{L\}=-\\sum\_\{l \\in \\mathcal\{Y\}\_\{L\}\} \\sum\_\{f=1\}^\{F\} Y\_\{l f\} \\ln Z\_\{l f\} L=−l∈YL∑f=1∑FYlflnZlf  
其中， Y L \\mathcal\{Y\}\_\{L\} YL为带有标签的节点集合。

![在这里插入图片描述][2020052706030549.png_pic_center]  
上图中左图为GCN图示，输入为 C C C个通道，输出为 F F F个通道， Y 1 Y\_1 Y1和 Y 2 Y\_2 Y2为节点标签。右图为在一数据集上进行训练得到的隐藏层激活值经过t-SNE降维可视化后的结果，可以看出聚类效果较好。

## 实验结果 ##

论文在如下几个任务中进行实验

*  在citation network中进行半监督的document classification。
 *  在从knowledge graph中提取的bipartite graph中进行半监督的entity classification

实验数据说明如下  
![在这里插入图片描述][20200527060457909.png_pic_center]  
前三个Dataset是citation network数据集，节点表示文档，边表示引用的连接，label rate表示用来有监督训练的节点数量占总节点数量比例，第四个Dataset是bipartite graph数据集。

结果如下：  
![在这里插入图片描述][20200527060410154.png_pic_center]

可以看出，在比较的几种算法中，论文GCN的在准确率和时间上都最好。

# 3. DCNN #

*  论文：[《Diffusion-Convolutional Neural Networks》][Diffusion-Convolutional Neural Networks]

该模型对每一个节点(或边、或图)采用H个hop的矩阵进行表示，每一个hop都表示该邻近范围的邻近信息，由此，对于局部信息的获取效果比较好，得到的节点的representation的表示能力很强。

## DCNN模型详述 ##

假设有如下定义

*  一个graph数据集 G = \{ G t ∣ t ∈ 1 … T \} \\mathcal\{G\}=\\left\\\{G\_\{t\} | t \\in 1 \\ldots T\\right\\\} G=\{ Gt∣t∈1…T\}
 *  graph定义为 G t = ( V t , E t ) G\_\{t\}=\\left(V\_\{t\}, E\_\{t\}\\right) Gt=(Vt,Et)，其中， V t V\_t Vt为节点集合， E t E\_t Et为边集合
 *  所有节点的特征矩阵定义为 X t X\_t Xt，大小为 N t × F N\_t\\times\{F\} Nt×F，其中， N t N\_t Nt为图 G t G\_t Gt的节点个数， F F F为节点特征维度
 *  边信息 E t E\_t Et定义为 N t × N t N\_t\\times\{\}N\_t Nt×Nt的邻接矩阵 A t A\_t At，由此可以计算出**节点度(degree)归一化**的转移概率矩阵 P t P\_t Pt，表示从 i i i节点转移到 j j j节点的概率。

对于graph来说没有任何限制，graph可以是带权重的或不带权重的，有向的或无向的。

模型的目标为预测 Y Y Y，也就是预测每一个图的节点标签，或者边的标签，或者每一个图的标签，**在每一种情况中，模型输入部分带有标签的数据集合，然后预测剩下的数据的标签**。

DCNN模型输入图 G \\mathcal\{G\} G，返回硬分类预测值 Y Y Y或者条件分布概率 P ( Y ∣ X ) \\mathbb\{P\}(Y|X) P(Y∣X)。该模型将每一个预测的目标对象(节点、边或图)转化为一个diffusion-convolutional representation，大小为 H × F H\\times\{\}F H×F， H H H表示扩散的hops。因此，对于节点分类任务，图 t t t的confusion-convolutional representation为大小为 N t × H × F N\_t\\times\{H\}\\times\{F\} Nt×H×F的张量，表示为 Z t Z\_t Zt，对于图分类任务，张量 Z t Z\_t Zt为大小为 H × F H\\times\{F\} H×F的矩阵，对于边分类任务，张量 Z t Z\_t Zt为大小为 M t × H × F M\_t\\times\{H\}\\times\{F\} Mt×H×F的矩阵。示意图如下

![在这里插入图片描述][20200527060818401.png_pic_center]  
对于**节点分类任务**，假设 P t ∗ P\_t^\* Pt∗为 P t P\_t Pt的power series，大小为 N t × H × N t N\_t\\times\{H\}\\times\{N\_t\} Nt×H×Nt，那么对于图 t t t的节点 i i i，第 j j j个hop，第 k k k维特征值 Z t i j k Z\_\{tijk\} Ztijk计算公式为  
 Z t i j k = f ( W j k c ⋅ ∑ l = 1 N t P t i j l ∗ X t l k ) Z\_\{t i j k\}=f\\left(W\_\{j k\}^\{c\} \\cdot \\sum\_\{l=1\}^\{N\_\{t\}\} P\_\{t i j l\}^\{\*\} X\_\{t l k\}\\right) Ztijk=f(Wjkc⋅l=1∑NtPtijl∗Xtlk)  
使用矩阵表示为  
 Z t = f ( W c ⊙ P t ∗ X t ) Z\_\{t\}=f\\left(W^\{c\} \\odot P\_\{t\}^\{\*\} X\_\{t\}\\right) Zt=f(Wc⊙Pt∗Xt)  
其中 ⊙ \\odot ⊙表示element-wise multiplication，由于模型只考虑 H H H跳的参数，即参数量为 O ( H × F ) O(H\\times\{F\}) O(H×F)，**使得diffusion-convolutional representation不受输入大小的限制**。

在计算出 Z Z Z之后，过一层全连接得到输出 Y Y Y，使用 Y ^ \\hat\{Y\} Y^表示硬分类预测结果，使用 P ( Y ∣ X ) \\mathbb\{P\}(Y|X) P(Y∣X)表示预测概率，计算方式如下  
 Y ^ = arg ⁡ max ⁡ ( f ( W d ⊙ Z ) ) \\hat\{Y\}=\\arg \\max \\left(f\\left(W^\{d\} \\odot Z\\right)\\right) Y^=argmax(f(Wd⊙Z))

P ( Y ∣ X ) = softmax ⁡ ( f ( W d ⊙ Z ) ) \\mathbb\{P\}(Y | X)=\\operatorname\{softmax\}\\left(f\\left(W^\{d\} \\odot Z\\right)\\right) P(Y∣X)=softmax(f(Wd⊙Z))

对于**图分类任务**，直接采用所有节点表示的均值作为graph的representation  
 Z t = f ( W c ⊙ 1 N t T P t ∗ X t / N t ) Z\_\{t\}=f\\left(W^\{c\} \\odot 1\_\{N\_\{t\}\}^\{T\} P\_\{t\}^\{\*\} X\_\{t\} / N\_\{t\}\\right) Zt=f(Wc⊙1NtTPt∗Xt/Nt)  
其中， 1 N t 1\_\{N\_t\} 1Nt是全为1的 N t × 1 N\_t\\times\{1\} Nt×1的向量。

对于**边分类任务**，通过**将每一条边转化为一个节点来进行训练和预测**，这个节点与原来的边对应的首尾节点相连，转化后的图的邻接矩阵 A t ′ A\_t' At′可以直接从原来的邻接矩阵 A t A\_t At增加一个**incidence matrix**得到  
 A t ′ = ( A t B t T B t 0 ) A\_\{t\}^\{\\prime\}=\\left(\\begin\{array\}\{cc\}\{A\_\{t\}\} & \{B\_\{t\}^\{T\}\} \\\\ \{B\_\{t\}\} & \{0\}\\end\{array\}\\right) At′=(AtBtBtT0)  
之后，使用 A t ′ A\_t' At′来计算 P t ′ P\_t' Pt′，并用来替换 P t P\_t Pt来进行分类。

对于**模型训练**，使用梯度下降法，并采用early-stop方式得到最终模型。

## 实验结果 ##

节点分类任务的实验数据集使用Cora和Pubmed数据集，包含scientific papers(相当于node)、citations(相当于edge)和subjects(相当于label)。实验评估标准使用分类准确率以及F1值。

**节点分类的实验结果**如下

![在这里插入图片描述][20200527060921598.png_pic_center]

可以看出使用各种评估标准，DCNN效果都是最好的。

**图分类任务**的实验结果如下

![在这里插入图片描述][20200527060943833.png_pic_center]  
可以看出，在不同数据集上，DCNN在图分类任务上并没有明显表现出很好的效果。

### 优缺点 ###

**优点**：

*  节点分类准确率很高
 *  灵活性
 *  快速

**缺点**：

*  **内存占用大**：DCNN建立在密集的张量计算上，需要存储大量的张量，需要 O ( N t 2 H ) O(N\_t^2H) O(Nt2H)的空间复杂度。
 *  **长距离信息传播不足**：模型对于局部的信息获取较好，但是远距离的信息传播不足。

# 4. Tree-LSTM #

*  论文：[《Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks》][Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks]

将**序列型的LSTM模型扩展到树型的LSTM模型**，简称Tree-LSTM，并根据孩子节点是否有序，论文提出了两个模型变体，**Child-Sum Tree-LSTM模型和N-ary Tree-LSTM模型**。和序列型的LSTM模型的主要不同点在于，序列型的LSTM从前一时刻获取隐藏状态 h t h\_t ht，而树型的LSTM从其所有的孩子节点获取隐藏状态。

## 模型详解 ##

Tree-LSTM模型对于每一个孩子节点都会产生一个“遗忘门” f j k f\_\{jk\} fjk，这个使得模型能够**从所有的孩子节点选择性地获取信息和结合信息**。

### Child-Sum Tree-LSTMs ###

该模型的更新方程如下  
 h ~ j = ∑ k ∈ C ( j ) h k i j = σ ( W ( i ) x j + U ( i ) h ~ j + b ( i ) ) f j k = σ ( W ( f ) x j + U ( f ) h k + b ( f ) ) o j = σ ( W ( o ) x j + U ( o ) h ~ j + b ( o ) ) u j = tanh ⁡ ( W ( u ) x j + U ( u ) h ~ j + b ( u ) ) c j = i j ⊙ u j + ∑ k ∈ C ( j ) f j k ⊙ c k h j = o j ⊙ tanh ⁡ ( c j ) \\begin\{aligned\} \\tilde\{h\}\_\{j\} &=\\sum\_\{k \\in C(j)\} h\_\{k\} \\\\ i\_\{j\} &=\\sigma\\left(W^\{(i)\} x\_\{j\}+U^\{(i)\} \\tilde\{h\}\_\{j\}+b^\{(i)\}\\right) \\\\ f\_\{j k\} &=\\sigma\\left(W^\{(f)\} x\_\{j\}+U^\{(f)\} h\_\{k\}+b^\{(f)\}\\right) \\\\ o\_\{j\} &=\\sigma\\left(W^\{(o)\} x\_\{j\}+U^\{(o)\} \\tilde\{h\}\_\{j\}+b^\{(o)\}\\right) \\\\ u\_\{j\} &=\\tanh \\left(W^\{(u)\} x\_\{j\}+U^\{(u)\} \\tilde\{h\}\_\{j\}+b^\{(u)\}\\right) \\\\ c\_\{j\} &=i\_\{j\} \\odot u\_\{j\}+\\sum\_\{k \\in C(j)\} f\_\{j k\} \\odot c\_\{k\} \\\\ h\_\{j\} &=o\_\{j\} \\odot \\tanh \\left(c\_\{j\}\\right) \\end\{aligned\} h~jijfjkojujcjhj=k∈C(j)∑hk=σ(W(i)xj\+U(i)h~j\+b(i))=σ(W(f)xj\+U(f)hk\+b(f))=σ(W(o)xj\+U(o)h~j\+b(o))=tanh(W(u)xj\+U(u)h~j\+b(u))=ij⊙uj\+k∈C(j)∑fjk⊙ck=oj⊙tanh(cj)其中， C ( j ) C(j) C(j)表示 j j j节点的邻居节点的个数， h k h\_k hk表示节点 k k k的隐藏状态， i j i\_j ij表示节点 j j j的”输入门“， f j k f\_\{jk\} fjk表示节点 j j j的邻居节点 k k k的“遗忘门“， o j o\_j oj表示节点 j j j的”输出门“。

这里的关键点在于第三个公式的 f j k f\_\{jk\} fjk，这个模型对节点 j j j的每个邻居节点 k k k都计算了对应的”遗忘门“向量，然后在第六行中计算 c j c\_j cj时对邻居节点的信息进行”遗忘“和组合。

由于该模型是对所有的孩子节点求和，所以**这个模型对于节点顺序不敏感的**，适合于孩子节点无序的情况。

### N-ary Tree-LSTMs ###

假如一个树的最大分支数为 N N N(即孩子节点最多为 N N N个)，而且孩子节点是有序的，对于节点 j j j，对于该节点的第 k k k个孩子节点的隐藏状态和记忆单元分别用 h j k h\_\{jk\} hjk和 c j k c\_\{jk\} cjk表示。模型的方程如下  
 i j = σ ( W ( i ) x j + ∑ ℓ = 1 N U ℓ ( i ) h j ℓ + b ( i ) ) f j k = σ ( W ( f ) x j + ∑ ℓ = 1 N U k ℓ ( f ) h j ℓ + b ( f ) ) o j = σ ( W ( o ) x j + ∑ ℓ = 1 N U ℓ ( o ) h j ℓ + b ( o ) ) u j = tanh ⁡ ( W ( u ) x j + ∑ ℓ = 1 N U ℓ ( a ) h j ℓ + b ( a ) ) c j = i j ⊙ u j + ∑ ℓ = 1 N f j ℓ ⊙ c j ℓ h j = o j ⊙ tanh ⁡ ( c j ) \\begin\{aligned\} i\_\{j\} &=\\sigma\\left(W^\{(i)\} x\_\{j\}+\\sum\_\{\\ell=1\}^\{N\} U\_\{\\ell\}^\{(i)\} h\_\{j \\ell\}+b^\{(i)\}\\right) \\\\ f\_\{j k\} &=\\sigma\\left(W^\{(f)\} x\_\{j\}+\\sum\_\{\\ell=1\}^\{N\} U\_\{k \\ell\}^\{(f)\} h\_\{j \\ell\}+b^\{(f)\}\\right) \\\\ o\_\{j\} &=\\sigma\\left(W^\{(o)\} x\_\{j\}+\\sum\_\{\\ell=1\}^\{N\} U\_\{\\ell\}^\{(o)\} h\_\{j \\ell\}+b^\{(o)\}\\right) \\\\ u\_\{j\} &=\\tanh \\left(W^\{(u)\} x\_\{j\}+\\sum\_\{\\ell=1\}^\{N\} U\_\{\\ell\}^\{(a)\} h\_\{j \\ell\}+b^\{(a)\}\\right) \\\\ c\_\{j\} &=i\_\{j\} \\odot u\_\{j\}+\\sum\_\{\\ell=1\}^\{N\} f\_\{j \\ell\} \\odot c\_\{j \\ell\} \\\\ h\_\{j\} &=o\_\{j\} \\odot \\tanh \\left(c\_\{j\}\\right) \\end\{aligned\} ijfjkojujcjhj=σ(W(i)xj\+ℓ=1∑NUℓ(i)hjℓ\+b(i))=σ(W(f)xj\+ℓ=1∑NUkℓ(f)hjℓ\+b(f))=σ(W(o)xj\+ℓ=1∑NUℓ(o)hjℓ\+b(o))=tanh(W(u)xj\+ℓ=1∑NUℓ(a)hjℓ\+b(a))=ij⊙uj\+ℓ=1∑Nfjℓ⊙cjℓ=oj⊙tanh(cj)值得注意的是**该模型为每个孩子节点都单独地设置了参数 U l U\_\{l\} Ul**。

## 模型训练 ##

### 分类任务 ###

分类任务定义为在类别集 Y \\mathcal\{Y\} Y中预测出正确的标签 y ^ \\hat\{y\} y^，对于每一个节点 j j j，使用一个softmax分类器来预测节点标签 y ^ j \\hat\{y\}\_j y^j，分类器取每个节点的隐藏状态 h j h\_j hj作为输入  
 p ^ θ ( y ∣ \{ x \} j ) = softmax ⁡ ( W ( s ) h j + b ( s ) ) y ^ j = arg ⁡ max ⁡ y p ^ θ ( y ∣ \{ x \} j ) \\begin\{aligned\} \\hat\{p\}\_\{\\theta\}\\left(y |\\\{x\\\}\_\{j\}\\right) &=\\operatorname\{softmax\}\\left(W^\{(s)\} h\_\{j\}+b^\{(s)\}\\right) \\\\ \\hat\{y\}\_\{j\} &=\\arg \\max \_\{y\} \\hat\{p\}\_\{\\theta\}\\left(y |\\\{x\\\}\_\{j\}\\right) \\end\{aligned\} p^θ(y∣\{ x\}j)y^j=softmax(W(s)hj\+b(s))=argymaxp^θ(y∣\{ x\}j)损失函数使用negative log-likelihood  
 J ( θ ) = − 1 m ∑ k = 1 m log ⁡ p ^ θ ( y ( k ) ∣ \{ x \} ( k ) ) + λ 2 ∥ θ ∥ 2 2 J(\\theta)=-\\frac\{1\}\{m\} \\sum\_\{k=1\}^\{m\} \\log \\hat\{p\}\_\{\\theta\}\\left(y^\{(k)\} |\\\{x\\\}^\{(k)\}\\right)+\\frac\{\\lambda\}\{2\}\\|\\theta\\|\_\{2\}^\{2\} J(θ)=−m1k=1∑mlogp^θ(y(k)∣\{ x\}(k))\+2λ∥θ∥22其中， m m m是带有标签的节点数量， λ \\lambda λ是 L 2 L2 L2是正则化超参。

### 语义相关性任务 ###

该任务给定一个句子对(sentence pair)，模型需要预测出一个范围在 \[ 1 , K \] \[1,K\] \[1,K\]之间的实数值，这个值越高，表示相似度越高。

论文首先对每一个句子产生一个representation，两个句子的表示分别用 h L h\_L hL和 h R h\_R hR表示，得到这两个representation之后，从distance和angle两个方面考虑，使用神经网络来得到 ( h L , h R ) (h\_L,h\_R) (hL,hR)相似度：  
 h × = h L ⊙ h R h + = ∣ h L − h R ∣ h s = σ ( W ( × ) h × + W ( + ) h + + b ( h ) ) p ^ θ = softmax ⁡ ( W ( p ) h s + b ( p ) ) y ^ = r T p ^ θ \\begin\{aligned\} h\_\{ \\times\} &=h\_\{L\} \\odot h\_\{R\} \\\\ h\_\{+\} &=\\left|h\_\{L\}-h\_\{R\}\\right| \\\\ h\_\{s\} &=\\sigma\\left(W^\{( \\times)\} h\_\{ \\times\}+W^\{(+)\} h\_\{+\}+b^\{(h)\}\\right) \\\\ \\hat\{p\}\_\{\\theta\} &=\\operatorname\{softmax\}\\left(W^\{(p)\} h\_\{s\}+b^\{(p)\}\\right) \\\\ \\hat\{y\} &=r^\{T\} \\hat\{p\}\_\{\\theta\} \\end\{aligned\} h×h\+hsp^θy^=hL⊙hR=∣hL−hR∣=σ(W(×)h×\+W(\+)h\+\+b(h))=softmax(W(p)hs\+b(p))=rTp^θ其中， r T = \[ 1 2 … K \] r^\{T\}=\\left\[\\begin\{array\}\{llll\}\{1\} & \{2\} & \{\\ldots\} & \{K\}\\end\{array\}\\right\] rT=\[12…K\]。模型期望根据训练得到的参数 θ \\theta θ得到的结果： y ^ = r T p ^ θ ≈ y \\hat\{y\}=r^\{T\} \\hat\{p\}\_\{\\theta\} \\approx y y^=rTp^θ≈y。由此，定义一个目标分布 p p p  
 p i = \{ y − ⌊ y ⌋ , i = ⌊ y ⌋ + 1 ⌊ y ⌋ − y + 1 , i = ⌊ y ⌋ 0 otherwise p\_\{i\}=\\left\\\{\\begin\{array\}\{ll\}\{y-\\lfloor y\\rfloor,\} & \{ i=\\lfloor y\\rfloor+ 1\} \\\\ \{\\lfloor y\\rfloor- y+1,\} & \{i=\\lfloor y\\rfloor\} \\\\ \{ 0\} & \{\\text \{ otherwise \}\}\\end\{array\}\\right. pi=⎩⎨⎧y−⌊y⌋,⌊y⌋−y\+1,0i=⌊y⌋\+1i=⌊y⌋ otherwise 其中， 1 ≤ i ≤ K 1\\le\{i\}\\le\{K\} 1≤i≤K，损失函数为 p p p和 p ^ θ \\hat\{p\}\_\{\\theta\} p^θ之间的KL散度：  
 J ( θ ) = 1 m ∑ k = 1 m K L ( p ( k ) ∥ p ^ θ ( k ) ) + λ 2 ∥ θ ∥ 2 2 J(\\theta)=\\frac\{1\}\{m\} \\sum\_\{k=1\}^\{m\} \\mathrm\{KL\}\\left(p^\{(k)\} \\| \\hat\{p\}\_\{\\theta\}^\{(k)\}\\right)+\\frac\{\\lambda\}\{2\}\\|\\theta\\|\_\{2\}^\{2\} J(θ)=m1k=1∑mKL(p(k)∥p^θ(k))\+2λ∥θ∥22

## 实验结果 ##

对于分类任务，实验数据使用**Stanford Sentiment Treebank**，分为五类：very negative, negative, neural, positive和very positive。在该数据集上的测试集上的准确度结果如下：

![在这里插入图片描述][20200527061437811.png_pic_center]

对于语义相似度度量，模型的任务是预测出两个句子语义的相似度分数。在SICK的语义相似度子任务上的测试结果如下  
![在这里插入图片描述][20200527061508245.png_pic_center]  
对于模型的实现部分目前可以直接使用DGL或者PyG等库帮助快速实现，接下来会整理如何使用这些库进行简单的图网络的实验。图神经网络在工业界的挑战主要是非结构化的图结构计算需要消耗巨大的计算资源和存储资源。

[2009 -_The Graph Neural Network Model]: https://persagen.com/files/misc/scarselli2009graph.pdf
[20200527053252466.jpeg_pic_center]: https://img-blog.csdnimg.cn/20200527053252466.jpeg#pic_center
[20200527054859607.jpeg_pic_center]: https://img-blog.csdnimg.cn/20200527054859607.jpeg#pic_center
[20200527055030162.png_pic_center]: https://img-blog.csdnimg.cn/20200527055030162.png#pic_center
[20200527055513863.png_pic_center]: https://img-blog.csdnimg.cn/20200527055513863.png#pic_center
[20200527055634657.png_pic_center]: https://img-blog.csdnimg.cn/20200527055634657.png#pic_center
[Semi-Supervised Classification with Graph Convolutional Networks]: https://arxiv.org/abs/1609.02907
[2020052706030549.png_pic_center]: https://img-blog.csdnimg.cn/2020052706030549.png#pic_center
[20200527060457909.png_pic_center]: https://img-blog.csdnimg.cn/20200527060457909.png#pic_center
[20200527060410154.png_pic_center]: https://img-blog.csdnimg.cn/20200527060410154.png#pic_center
[Diffusion-Convolutional Neural Networks]: https://arxiv.org/abs/1511.02136
[20200527060818401.png_pic_center]: https://img-blog.csdnimg.cn/20200527060818401.png#pic_center
[20200527060921598.png_pic_center]: https://img-blog.csdnimg.cn/20200527060921598.png#pic_center
[20200527060943833.png_pic_center]: https://img-blog.csdnimg.cn/20200527060943833.png#pic_center
[Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks]: https://arxiv.org/abs/1503.00075
[20200527061437811.png_pic_center]: https://img-blog.csdnimg.cn/20200527061437811.png#pic_center
[20200527061508245.png_pic_center]: https://img-blog.csdnimg.cn/20200527061508245.png#pic_center