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

1. 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)，如下：

• 图 (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∈N​GNN的信息传播流图以及等效的网络结构如下图所示

根据上图所示，顶端的图是原始的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∑p​j=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的稳定状态。

算法流程如下

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,u​xu​+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,u​bw​​=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​=jmax​i∑​∣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∑p​j=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的所有节点都有标签，然后对部分节点进行训练，在验证阶段使用另外一部分节点进行验证。输入的数据图如下图：

其中，该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))
  

• 模型的训练和评估结果如下图:
  
  第一条曲线为训练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》

图卷积的演变

按照图傅里叶变换的性质，可以得到如下图卷积的定义
( 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} Φ。