[论文笔记] [2014] Spectral Networks and Deep Locally Connected Networks on Graphs

这篇论文首次提出了基于空域（Spectral-domain）和基于频域（Spatial-domain）的图上卷积神经网络。
从题目可以看出，这篇论文分为两部分，一部分是Deep Locally Connected Networks，一部分是Spectral Networks。前者是基于空域角度去设计图卷积的，而后者是基于频域角度设计图卷积。

Spatial Construction

空域上的工作，作者的意图是设计一种network适用于拓扑结构，且具备卷积的性质（局部连接和层次化表达，在图卷积中没有local translational invariance这个特性），用来提取拓扑结构上的特征。本质上就是找出每个顶点的neighbors，并对其特征进行提取。而这里需要思考的两个问题是：

• 按照什么条件去找中心的neighbors，也就是确定receptive field？
• 确定receptive field，按照什么方式处理包含不同数目neighbors的特征？

Locality via $W$

对于第一个问题，作者是通过对称非负的矩阵 $W$（其实就是图的邻接矩阵），并通过设定一个阈值 $\delta$，来确定中心结点的neighbors：
Nδ(j)={i∈Ω:Wij>δ}N_{\delta}(j)=\{i \in \Omega: W_{ij} > \delta\} Nδ?(j)={ i∈Ω:Wij?>δ}
这种方式即实现了locality，能得到一个局部连接的网络，减少了网络的参数。但这种方式确定neighbors，存在一个问题，就是对于每个结点都需要单独计算neighbors。

Multiresolution Analysis on Graphs

在CNN中，通过pooling和subsampling layer减小grid的大小，其过程就是将输入特征map到一个cluster中，输出一个对应这个cluster的单一feature。而在图上，关于multiscale clustering，有较多这方面的文献。

上图是图上的两层clustering，第一层有12个结点，有6个clustering，通过图上的pooling操作，映射到下一层就为6个结点，图的规模减小了，此时对其进行聚类，就是3个clustering。

Deep Locally Connected Networks

在第k层，输入维度为$d_{k?1}\times f_{k?1}$ 的 $x_k=(x_{k,i};i=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=1...f_k)$$
其中，$F_{k,i,j}$是一个 由$N_k$ 确定的 $d_{k?1}\times d_{k?1}$ 的稀疏矩阵，$L_k$ 输出每个cluster pooling操作后结果，$f_{k?1}$ 是 $x$ 的channel数，$f_k$ 则是当前层的卷积核的数量。

可以看出，作者在第二个问题上的处理方式是对中心结点neighbors做了一个加权求和，而这个权重就是通过 $W$ 给定的 $F_{k,i,j}$。对于每经过一层映射，图结构都会发生变化（pooling操作后，size变成了cluster的数量），相应的 W 需要更新，更新的策略是：
$$\begin{gathered} W_0=W \\ {A}_k(i,j)=\sum _{s\in {\Omega }_k(i)}\sum _{t\in {\Omega }_k(j)}{W}_{k?1}(s,t)(k\le K) \\ {W}_k=rownormalize(A_k) \\ {N}_k=supp(W_k) \end{gathered}$$
对于pooling产生的新结点之间的权重，就是对其原本属于的cluster与其他新结点所在的cluster内的结点权重进行求和，并做normalize。

Spectral Construction

在频域上的工作，是借助 spectral graph theory 来实现的。从整个研究的时间进程来看[1]：首先研究GSP (graph signal processing) 的学者定义了 Fourier Transformation，进而定义了 graph上的convolution，最后与深度学习结合提出 graph convolutional network。
作者定义图卷积如下：
$$x_{k+1,j}=h(V\sum _{i=1}^{f_{k?1}}{F}_{k,i,j}{V}^T{x}_{k,i})(j=1...f_k)$$
其中，不难看出，作者是“简单粗暴”地将图卷积中卷积核换成了一个可学习的卷积核，拆开看就是先对图信号 $x_{k,i}$ 乘上$V^T$ 做傅里叶变换，再乘上卷积核，再乘上 $V$ 做傅里叶逆变换，最后经过激活函数 $h$。
作为第一代的图卷积，它存在着一些弊端，主要在于：

1. 每一层图卷积，都要计算 $V$ 和 $V^T$ ，以及矩阵乘法，其计算量颇大；
2. 卷积核不具备spatial localization （具体讨论见参考文献[1]）
3. 卷积核需要 n 个参数

总结

这篇论文是GCN的一篇很经典的论文，其中提出的GCN应该算是第一代的GCN，虽然在现在看来存在很多弊端，也有很多论文工作对其进行改进，但还是很有去读的必要。

待解决问题：

1. 文中对于算法复杂度的讨论没有细究，后面有时间补上

参考文献

[1] 如何理解 Graph Convolutional Network（GCN）？, https://www.zhihu.com/question/54504471/answer/332657604