[论文笔记] [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

对于第一个问题，作者是通过对称非负的矩阵 $W$W（其实就是图的邻接矩阵），并通过设定一个阈值 $\delta$δ，来确定中心结点的neighbors：
$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}$dk−1​×fk−1​ 的 $x_k = (x_{k,i};i=1...f_{k-1})$xk​=(xk,i​;i=1...fk−1​) ，它的输出 $x_{k+1}$xk+1​ 定义为：
$x_{k+1,j}=L_{k}h(\sum_{i=1}^{f_{k-1}}{F_{k,i,j}x_{k,i}}) \quad (j=1...f_k)$xk+1,j​=Lk​h(i=1∑fk−1​​Fk,i,j​xk,i​)(j=1...fk​)
其中，$F_{k,i,j}$Fk,i,j​是一个 由$N_k$Nk​ 确定的 $d_{k-1} \times d_{k-1}$dk−1​×dk−1​ 的稀疏矩阵，$L_k$Lk​ 输出每个cluster pooling操作后结果，$f_{k-1}$fk−1​ 是 $x$x 的channel数，$f_{k}$fk​ 则是当前层的卷积核的数量。

可以看出，作者在第二个问题上的处理方式是对中心结点neighbors做了一个加权求和，而这个权重就是通过 $W$W 给定的 $F_{k,i,j}$Fk,i,j​。对于每经过一层映射，图结构都会发生变化（pooling操作后，size变成了cluster的数量），相应的 W 需要更新，更新的策略是：
$W_0 = W \\ A_k(i,j)=\sum_{s \in \Omega_k(i)}{\sum_{t \in \Omega_k(j)}{W_{k-1}(s,t)}} \quad (k \leq K) \\ W_k = rownormalize(A_k) \\ N_k = supp(W_k)$W0​=WAk​(i,j)=s∈Ωk​(i)∑​t∈Ωk​(j)∑​Wk−1​(s,t)(k≤K)Wk​=rownormalize(Ak​)Nk​=supp(Wk​)
对于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^Tx_{k,i}}) \quad (j=1...f_k)$xk+1,j​=h(Vi=1∑fk−1​​Fk,i,j​VTxk,i​)(j=1...fk​)
其中，不难看出，作者是“简单粗暴”地将图卷积中卷积核换成了一个可学习的卷积核，拆开看就是先对图信号 $x_{k,i}$xk,i​ 乘上$V^T$VT 做傅里叶变换，再乘上卷积核，再乘上 $V$V 做傅里叶逆变换，最后经过**函数 $h$h。
作为第一代的图卷积，它存在着一些弊端，主要在于：

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

总结

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

待解决问题：

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

参考文献

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