一、Address Spectral Networks and Deep Locally Connected Networks on Graphs
地址：https://arxiv.org/pdf/1312.6203.pdf
二、Introduction 作者提出了两种结构，一种是基于时域的层次聚类，并使用它们定义“局部”连接和池化
另一种是谱结构，利用了卷积在傅里叶域中的性质，通过找到相应的“傅里叶”基，可以将卷积扩展到一般的图。
作者通过实验证明，对于低维图，我们可以学习到独立于输入大小的卷积层参数，从而得到有效的深层结构。
三、Model 3.1 Spatial Construction 局部性
加权图G=（Ω，W），其中Ω是大小为m的离散集，W是m×m对称非负矩阵。
利用图的权重定义局部性：例如，在W上定义邻域的一种简单方法是设置一个阈值δ>0，然后取邻域
N_{\delta}(j)=\left\{i \in \Omega: W_{i j}>\delta\right\}
深度局部连接网络
\mathcal{N}_{k}=\left\{\mathcal{N}_{k, i} ; i=1 \ldots d_{k-1}\right\}
k代表第k个卷积层，
\Omega k 表示第k层的输入节点数目，
d_{k} 为第k层的聚类类数
，\Omega k=d_{k-1} x_{k+1, j}=L_{k} h\left(\sum_{i=1}^{f_{k-1}} F_{k, i, j} x_{k, i}\right) \quad\left(j=1 \ldots f_{k}\right)
f_{k-1} 代表第k-1层的滤波器数目以及第k层中每个节点的特征维数。
x_k 代表输入数据，
x_k 的shape为（
d_{k-1}，f_{k-1} ）。
F_{k,i j} 表示第k层第j个滤波器的第i个值，h为激活函数，L为pooling操作
对于当前节点，按照如下方法取邻居：
\begin{aligned}
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 \leq K) \\
W_{k} &=\operatorname{rownormalize}\left(A_{k}\right),(k \leq K) \\
\mathcal{N}_{k} &=\operatorname{supp}\left(W_{k}\right) \cdot(k \leq K)
\end{aligned}
这里体现了局部性（只取每个节点前k个邻居）（supp是支撑集，如果x和y节点不是邻域关系，
F_{k,i j}(x,y) 的值为0）
连接体现在层与层之间的神经元数目是通过聚类得到的，上一层的聚类对应为下一层的神经元
第k层需要学习的参数个数为：
O\left(S_{k} \cdot\left|\Omega_{k}\right| \cdot f_{k} \cdot f_{k-1}\right)=O(n)
S_k 为 average support of the neighborhoods
\mathcal{N}_{k} 3.2 Spectral Construction x_{k+1, j}=h\left(V \sum_{i=1}^{f_{k-1}} F_{k, i, j} V^{T} x_{k, i}\right) \quad\left(j=1 \ldots f_{k}\right)
F为权重的对角矩阵，V是拉普拉斯矩阵的特征向量矩阵，h为激活函数。
x_{k,i} 是第K层上所有节点的第i个特征拼接形成的向量,
F_{k,i,j} 是滤波器。
推导过程
离散卷积：
(f * g)=\sum_{\tau=-\infty}^{\infty} f(\tau) g(n-\tau) 离散傅里叶变换：
X(k)=F(x(n))=\sum_{n=0}^{N-1} x(n) e^{-j k \frac{2 \pi}{N} n}, k \in[0, N-1] 离散傅里叶逆变换：
x(n)=F^{-1}(X(k))=\frac{1}{N} \sum_{k=0}^{N-1} X(k) e^{j k \frac{2 \pi}{N} n}, n \in[0, N-1] step 1
\begin{array}{l}
\mathcal{F}((f * g)(t))(k) \\
=\int_{t}[(f * g)(t)] e^{i k t} d t \\
=\int_{t}\left[\int_{u} f(u) g(t-u) d u\right] e^{i k t} d t \\
=\int_{u}\left[\int_{t} g(t-u) e^{i k t} d t\right] f(u) d u \\
=\int_{u} f(u)\left[\int_{\tau} g(\tau) e^{i k(\tau+u)} d \tau\right] d u \\
=\int_{u} f(u)\left[\int_{\tau} g(\tau) e^{i k \tau} d \tau\right] e^{i k u} d u \\
=\int_{u} f(u)[\mathcal{F}(g)] e^{i k u} d u \\
=\int_{u} f(u) e^{i k u} d u \mathcal{F}(g) \\
=\mathcal{F}(f) \mathcal{F}(g)
\end{array}
(上述推导来源于知乎回答：https://www.zhihu.com/question/47883434/answer/286401230)
(此处符号略不同，简单对比一下就可以理解了)
最后可得结论：f和g的卷积（时域）等于 f和g的频域乘积
(f * g)=F^{-1}[F[f] \odot F[g]]
step 2
根据亥姆霍兹方程有
\nabla^{2} f=\frac{\partial^{2} e^{-j k \frac{2 \pi}{N} n}}{\partial n^{2}}=-\left(k \frac{2 \pi}{N}\right)^{2} e^{-j k \frac{2 \pi}{N} n}=-w^{2} f
其中
\nabla^{2} 是拉普拉斯算子
根据拉普拉斯的谱分解可得
-w^2 为拉普拉斯矩阵的特征值
f 代表时域信号,
\hat{f} 代表频域信号，有：
\hat{f}(k)=\sum_{n=0}^{N-1} f(n) e^{-j k \frac{2 \pi}{N} n}=\sum_{n=0}^{N-1} f(n) v_{k}(n)=v_{k}^{T} f
step 3
将step 2代入卷积公式：
(g * f)=V\left[V^{T} g \odot V^{T} f\right]
V^{T} g=\left(v_{1}^{T} g, \ldots, v_{n}^{T} g\right)^{T}
V^{T} g \odot V^{T} f=\operatorname{diag}\left(v_{1}^{T} g, \ldots, v_{n}^{T} g\right) V^{T} f
令
g_{\theta}=\operatorname{diag}\left(v_{1}^{T} g, \ldots, v_{n}^{T} g\right)
得
(g * f)(n)=V g_{\theta} V^{T} f
四、Experiments FCN为全连接层（with N outputs），LRF为局部连接 ， MP 为max-pooling layer， SP为spectral层
五、Conclusion 谱结构是所有顶点都参与运算，没有实现局部卷积和参数共享。 每一次前向传播都要计算， V,diag(g_\theta)，V^T 的矩阵乘积，运算量大
参数量大，卷积核参数量为n个 
