【图神经网络论文阅读笔记：GCN-1】Spectral Networks and Locally Connected Networks on Graphs

【阅读笔记】Spectral Networks and Locally Connected Networks on Graphs

Abstract

本文是基于CNN（卷积神经网络，convolutional neural network）所构造的GCN。

本文提出两种构造，一种基于域的层次集群（a hierachical clustering of the domain），另一种是基于图拉普拉斯的谱（the spectrum of the graph Laplacian）。

其中后者（GCN-1）是本文的重点

结果显示，对于低维图，可以通过一些参数来学习卷积层，这些参数与输入大小无关。

Background

CNN在机器学习问题中非常成功，在这些问题中，底层数据表示的坐标具有网格（grid）结构（在1、2和3维），并且在这些坐标中要研究的数据具有相对于该网格的平移等变性/不变性（translational equivariance/invariance）。

同时，CNN相比传统的全连接网络（FC）还极大地减少了参数的使用。

然而，对于不具备较好几何结构的数据，传统的CNN不太适用。而图（graph）天然具备较好的表示能力。为了将卷积推广到图上，本文提出两种结构：spatial construction和spectral construction。

Spacial Construction

CNN 对一般图最直接的泛化是考虑多尺度（multiscale）、层次化（hierarchical）、局部感受野（local receptive field）。

网格（grid）将被带权图$G=(\Omega ,W)$所替代——$\Omega$是大小为$m$的离散集，而$W$是一个$m\times m$的对称矩阵（元素非负）。

将$\Omega$理解为节点集合，$W$理解为边矩阵

Locality

要在图中泛化局部（locality）的概念，可以通过权重$W$来决定。定义“邻居”（neighborhood）的最直接方式是设定一个门限值$\delta$，则节点$j$的邻居（neighbor）为：
N δ ( j ) = { i ∈ Ω : W i j > δ } N_\delta(j)=\{i\in\Omega:W_{ij}>\delta\} Nδ​(j)={i∈Ω:Wij​>δ}

通过此处“邻居”的概念，之后会定义“社区”（neighborhood）

Multiresolution

由于网格具备天然的多尺度集群（multiscale clustering），CNN得以通过池化层和二次采样层（subsampling layer）减少网格的尺度。前人提出了多种在图上形成多尺度集群的方法。

本文使用一种简单的方法。下图说明了具有相应邻域的图的多分辨率集群（multiresolution clustering）：

Deep Locally Connected Networks

spatial construction始于对图的多尺度集群。

考虑尺度为$K$。设${\Omega }_0=\Omega$，对每个$k=\mathrm{1...}K$，定义：

• ${\Omega }_k$为一个分割：将${\Omega }_{k-1}$分为$d_k$个集群
• ${\mathcal{N}}_k$为${\Omega }_{k-1}$中各元素所在的社区： N k = { N k , i ; i = 1... d k − 1 } \mathcal{N}_k=\{\mathcal{N}_{k,i};i=1...d_{k-1}\} Nk​={Nk,i​;i=1...dk−1​}

上图为无向图$G=({\Omega }_0,W)$的两级集群。

容易理解错误的是，这里的$W_{ij}$不是“距离”，而是表征两个节点关系紧密与否的“权重”——关系越紧密，权值越大。

e.g. ${\Omega }_1$是将${\Omega }_0=\Omega$分为$d_1$个集群；${\mathcal{N}}_2$是一个集合（共$d_1$个元素），其中每个元素都是${\Omega }_1$中某个集群的“邻居”，即一个社区

图中：

• 灰色节点表示的是原始图$G$中的各节点${\Omega }_0$
• $k=1$时划分第一级社区${\Omega }_1$：每个彩色的多边形表示一个社区。各社区${\mathcal{N}}_{1j}$可以进一步用一个节点表示（图中彩色的节点）
• $k=2$时划分第二级社区${\Omega }_2$：椭圆圈表示在上一步基础之上划分的各社区${\mathcal{N}}_{2j}$

据此定义网络的第$k$层（k-th layer of the network）：不失一般性地，假设输入信号是在${\Omega }_0$中定义的实信号（real signal），用$f_k$表示在第$k$层中创建的filters的数量。在网络的每一层，会把用${\Omega }_{k-1}$索引（index）的$f_{k-1}$维信号转化为用${\Omega }_k$索引的$f_k$维信号，从而权衡空间分辨率（spatial resolution）与新创建的特征坐标（feature coordinates）。

通俗地说，就是每一层都使得空间分辨率有所降低、“图”更加“抽象”，但图中隐含的信息通过特征的提取变得更加明显。

更正式地，如果第$k$层的输入是$d_{k-1}\times f_{k-1}$的$x_k=(x_{k,i};i=\mathrm{1...}{f}_{k-1})$，则输出$x_{k+1}$为：
$$x_{k+1,j}=L_{k}h(\sum _{i=1}^{f_{k-1}}{F}_{k,i,j}{x}_{k,i})(j=\mathrm{1...}{f}_k)\text{\hspace{1em}(2.1)}$$
其中$F_{k,i,j}$是$d_{k-1}\times d_{k-1}$大小的稀疏矩阵，且在由${\mathcal{N}}_k$所给出的位置上，其元素（entries）是非零的。$L_k$是在${\Omega }_k$中的每个集群上做池化操作的输出结果。如下图所示。

可以理解为：
初始值$d_0=|{\Omega }_0|$即原图$G$中节点的数目，$f_0=1$
$x_{k+1}$是$x_k$经过第$k$层的$f_k$个filter作用后得到的结果
$h$为激活函数

注：“entries”
The individual items in an m×n matrix A, often denoted by ai,j, where i and j usually vary from 1 to m and n, respectively, are called its elements or entries.
矩阵中的元素可以叫elements，items，或者entries。

上图为$K=2$情况下，$(2.1)$式所描述的空间构造，其中池化操作为演示方便而隐含在了过滤阶段（filtering stage）。每一个转化层都会损失空间分辨率，但也会增加filters的数量。

本文使用如下方式构造${\Omega }_k$和${\mathcal{N}}_k$：

小结

空间构造可能看起来很幼稚，但它的优点是它需要对图进行相对较弱的正则性假设。 具有低内在维度的图具有局部邻域，即使不存在良好的全局嵌入也是如此。 然而，在这种结构下，没有简单的方法可以在图形的不同位置之间进行权重共享。 一种可能的选择是考虑将图形全局嵌入到低维空间中，这在高维数据的实践中很少见。

Spectral Construction

图的全局结构可以利用其图拉普拉斯算子（graph-Laplacian）的谱（spectrum）来推广卷积运算符。

Harmonic Analysis on Weighted Graphs

harmonic analysis: analysis of a periodic function into a sum of simple sinusoidal components.
synonymous: Fourier analysis

组合拉普拉斯矩阵（combinatorial Laplacian）$L=D-W$或图拉普拉斯矩阵（graph Laplacian）$\mathcal{L}=I-D^{-1/2}W{D}^{-1/2}$是对网格中的拉普拉斯算子的推广。

$L$：图拉普拉斯矩阵，就是图上的拉普拉斯算子$\Delta$
$D$：度矩阵
$W$：权重矩阵

图拉普拉斯算子$\Delta$作用在由图节点信息构成的向量$\vec{f}$上，得到的结果等于图拉普拉斯矩阵$L$和向量$\vec{f}$的点积：
$$\Delta \vec{f}=L\vec{f},\vec{f}=(f_1,...f_N)$$

设$x$是$m$维的向量，节点$i$的平滑度（smoothness）可定义为：
$$\Vert ▽x{\Vert }_W^2(i)=\sum _j{W}_{ij}[x(i)-x(j){]}^2$$

Extending Convolutions via the Laplacian Spectrum

设$W$是一个带权图，$\Omega$表示索引集。设$V$是拉普拉斯矩阵$L$的各特征向量（eigenvector）组成的列向量矩阵，按特征值（eigenvalue）排序。可以据此在图上做卷积网络的推广。
$$x_{k+1,j}=h(V\sum _{i=1}^{f_{k-1}}{F}_{k,i,j}{V}^T{x}_{k,i})(j=\mathrm{1...}{f}_k)$$

$f_k$为第$k$层中创建的filters的数量
每层$k=\mathrm{1...}K$中，将大小为$|\Omega |\times f_{k-1}$的输入向量$x_k$，转化为大小为$|\Omega |\times f_k$的输出向量$x_{k+1}$
$F_{k,i,j}$是一个对角矩阵（即为要学习的参数——卷积核）
$h$为激活函数

理论上，每层需要$|\Omega |\times f_{k-1}\times f_k$个参数：

通常来说，只有拉普拉斯算子的前$d$个特征向量是有用的，因此可以将特征向量组成的列矩阵$V$变为$V_d$。这样每层需要训练的参数减少到$d\cdot f_{k-1}\cdot f_k=O(|\Omega |)$。

术语

multiscale clustering：多尺度集群

multiresolution clustering：多分辨率集群

spatial resolution：空间分辨率

neighbor：邻居

neighborhood：社区

spectrum：谱

Laplacian：拉普拉斯算子

eigenvector/eigenvalue：特征向量/特征值