《Spectral Networks and Deep Locally Connected Networks on Graphs》论文理解

在欧式空间中使用的CNN卷积具有平移不变性，权值共享，局部连接，分层次表达的特点；但是图网络是一种非欧式结构的数据，网络是不规整的关系型数据，所以其不存在平移不变形（每个节点的周围邻居数不固定），导致图网络无法使用传统的CNN。不使用卷积核卷积的话，只能按照全连接网络的方式进行线性映射，这样又将失去权值共享，局部连接，分层次表达这些优势，需要大量的参数。在《Spectral Networks and Deep Locally Connected Networks on Graphs》 中，作者想办法把传统欧式空间的卷积迁移到图网络中去，作者提出了两个结构，把欧式空间的卷积迁移到了图网络的空间域和频域。

无向图：G=(Ω,W)G=(\Omega,W)G=(Ω,W)，其中Ω\OmegaΩ表示图中所有节点的集合，size = m；WWW表示图的邻接矩阵，shape = （m,m）,由于是无向图，WWW是一个对称矩阵。WWW中的值Wi,jW_{i,j}Wi,j​表示节点i，j之间的边的权重，为非负值，当这两个节点之间没有边的时候，认为权重值为0。

在传统的欧式空间中（以图像为例），在卷积时需要设置一定大小的卷积核，如 kernel = (3,3)，就是相当于中心像素点的邻域为周围的8个像素点。
在图中，利用WWW来确定每个节点的邻域。论文中给出公式：
Nδ(j)={i∈Ω:Wi,j>δ}(1)N_\delta(j)=\{i\in\Omega:W_{i,j}>\delta\}\tag{1}Nδ​(j)={i∈Ω:Wi,j​>δ}(1)

Nδ(j)N_\delta(j)Nδ​(j)表示jjj的邻域，是一个集合；以δ\deltaδ为阈值划分节点jjj的邻域，权值大于δ\deltaδ才属于jjj的邻域。

2.2节中作者在介绍一个传统卷积的分层次表达的特点，这里就不再解释，直接进入2.3节。
在传统的欧式空间中（以图像为例），在卷积时需要设置一定大小的步长，如stride = (3,3)，假设input_image.shape = (18,18),kernel = (3,3)，out_image.shape = (6,6),这个操作相当于在18×18个像素点中找到了6×6个聚类中心，将其进行聚类操作，每个类中的元素为中心点的邻域元素。将每个类与卷积核对应项相乘求和，得到输出的一个像素点。
在图中，作者给出了以下（2）（3）两个公式：
Nk={Nk,i;i=1...dk−1}(2)N_{k}=\{N_{k,i};i=1...d_{k-1}\}\tag{2}Nk​={Nk,i​;i=1...dk−1​}(2)

在公式（2）中，k表示第k个尺度，类比传统卷积，意思就是第k层卷积层，Ωk\Omega_{k}Ωk​表示第k层输入的节点数目，dk−1d_{k-1}dk−1​第k-1层中聚类的类数，即Ωk=dk−1\Omega_{k} = d_{k-1}Ωk​=dk−1​，Ωk+1=dk\Omega_{k+1}=d_{k}Ωk+1​=dk​表示输出的节点数目，Nk,iN_{k,i}Nk,i​表示第i个节点的类，在这个公式中，作者是以每个输入节点为类中心，以节点邻域为类元素，得到了Ωk=dk−1\Omega_{k} = d_{k-1}Ωk​=dk−1​个类。
具体如何得到NkN_{k}Nk​如上图所示：（这些公式就没怎么看懂了）

xk+1,j=Lkh(∑i=1fk−1Fk,i,jxk,j)（j=1...fk）(3)x_{k+1,j}=L_{k}h(\sum_{i=1}^{f_{k-1}}{F_{k,i,j}x_{k,j}})（j=1...f_{k}）\tag{3}xk+1,j​=Lk​h(i=1∑fk−1​​Fk,i,j​xk,j​)（j=1...fk​）(3)

在公式（3）中，fk−1f_{k-1}fk−1​表示k-1层的滤波器个数，也是k层中每个节点的特征维数。xk=(xk,i;i=1...fk−1)x_{k}=(x_{k,i};i=1...f_{k-1})xk​=(xk,i​;i=1...fk−1​),xkx_{k}xk​.shape = (dk−1,fk−1d_{k-1},f_{k-1}dk−1​,fk−1​),表示输入数据；xk,ix_{k,i}xk,i​.shape = (dk−1d_{k-1}dk−1​,1),表示dk−1d_{k-1}dk−1​个节点的第i个特征拼接形成的向量。Fk,i,jF_{k,i,j}Fk,i,j​.shape = (dk−1,dk−1d_{k-1},d_{k-1}dk−1​,dk−1​)，表示第k层第j个滤波器的i个值，Fk,i,jF_{k,i,j}Fk,i,j​的值与NkN_{k}Nk​有关，表示第k层第j个滤波器的i个特征的映射关系，x节点和y节点不是邻域关系则对应的Fk,i,j(x,y)F_{k,i,j}(x,y)Fk,i,j​(x,y)的值将为0，和WWW类似。
∑i=1fk−1Fk,i,jxk,j\sum_{i=1}^{f_{k-1}}{F_{k,i,j}x_{k,j}}∑i=1fk−1​​Fk,i,j​xk,j​部分完成了卷积的工作(类比传统的卷积的话，可以认为卷积的模式选择了same，stride = 1)，卷积后输出和输入节点数一样，输出(dk−1,1)(d_{k-1},1)(dk−1​,1)的向量，h(∗)h(*)h(∗)为非线性激励函数，Lk(∗)L_{k}(*)Lk​(∗)为池化操作，将(dk−1,1)(d_{k-1},1)(dk−1​,1)的向量池化为(dk,1)(d_{k},1)(dk​,1)的向量，即xk+1,j.shape=(dk,1)x_{k+1,j}.shape = (d_{k},1)xk+1,j​.shape=(dk​,1)，然后，如果第k层有fkf_{k}fk​个滤波器的话，那么第k层的输出为xk+1=(xk+1,i;i=1...fk)x_{k+1}=(x_{k+1,i};i=1...f_{k})xk+1​=(xk+1,i​;i=1...fk​)。

图上的空间域卷积如下图所示：

k =1时：
num(Ω0)=12,x1.shape=(12,f0),f1=4,F1,i,j.shape=(12,12),1≤i≤f0,1≤j≤f1,d1=6num(\Omega_{0})=12,x_{1}.shape=(12,f_{0}),f_{1}=4,F_{1,i,j}.shape=(12,12),1 \leq i \leq f_{0},1 \leq j \leq f_{1},d_{1}=6num(Ω0​)=12,x1​.shape=(12,f0​),f1​=4,F1,i,j​.shape=(12,12),1≤i≤f0​,1≤j≤f1​,d1​=6
k =2时：
num(Ω1)=d1=6,x2.shape=(6,f1),f2=6,F2,i,j.shape=(6,6),1≤i≤f1=4,1≤j≤f2,d2=3num(\Omega_{1})=d_{1}=6,x_{2}.shape=(6,f_{1}),f_{2}=6,F_{2,i,j}.shape=(6,6),1 \leq i \leq f_{1}=4,1 \leq j \leq f_{2},d_{2}=3num(Ω1​)=d1​=6,x2​.shape=(6,f1​),f2​=6,F2,i,j​.shape=(6,6),1≤i≤f1​=4,1≤j≤f2​,d2​=3
网络输出：
x3.shape=(d2,f2)=(3,6)x_{3}.shape=(d_{2},f_{2})=(3,6)x3​.shape=(d2​,f2​)=(3,6)

离散域的卷积公式：(f∗g)=∑τ=−∞∞f(τ)g(n−τ)(f*g)=\sum_{\tau=-\infty}^{\infty}{f(\tau)g(n-\tau)}(f∗g)=∑τ=−∞∞​f(τ)g(n−τ)
离散傅里叶变换公式（DFT）：X(k)=F(x(n))=∑n=0N−1x(n)e−jk2πNnX(k)=F(x(n))=\sum_{n=0}^{N-1}{x(n)e^{-jk\frac{2\pi}{N}n}}X(k)=F(x(n))=∑n=0N−1​x(n)e−jkN2π​n , k∈[0,N−1]k\in[0,N-1]k∈[0,N−1]，表示的是x(n)x(n)x(n)与{e−jk2πNn}\{e^{-jk\frac{2\pi}{N}n}\}{e−jkN2π​n}的内积，也可以认为是将x(n)x(n)x(n)映射为{e−jk2πNn}\{e^{-jk\frac{2\pi}{N}n}\}{e−jkN2π​n}基向量空间的X(k)X(k)X(k)。
离散傅里叶逆变换公式（IDFT）：x(n)=F−1(X(k))=1N∑k=0N−1X(k)ejk2πNnx(n) = F^{-1}(X(k))=\frac{1}{N}\sum_{k=0}^{N-1}{X( k)e^{jk\frac{2\pi}{N}n}}x(n)=F−1(X(k))=N1​∑k=0N−1​X(k)ejkN2π​n , n∈[0,N−1]n\in[0,N-1]n∈[0,N−1]。
由于时域卷积等于频域相乘，所以卷积公式的频域表达：
(f∗g)=F−1[F[f]⨀F[g]](4)(f*g)=F^{-1}[F[f]\bigodot F[g]]\tag{4}(f∗g)=F−1[F[f]⨀F[g]](4)

⨀\bigodot⨀表示哈达玛乘积，指的是两个矩阵(或向量)的逐点乘积。
在图网络中，定义了度矩阵DDD，DDD为对角矩阵，对角线上的值为各个节点连接的边的数目，WWW为图的邻接矩阵，图中的拉普拉斯矩阵定义为L=D−WL=D-WL=D−W，对LLL进行矩阵的特征分解，得到：L=VΛVTL=V\Lambda V^{T}L=VΛVT,V=(v1,...,vi,...vn),viV=(v_{1},...,v_{i},...v_{n}),v_{i}V=(v1​,...,vi​,...vn​),vi​是LLL的特征向量，Λ=diag(λ1...λi...λn)\Lambda=diag(\lambda_{1}...\lambda_{i}...\lambda_{n})Λ=diag(λ1​...λi​...λn​),λi\lambda_{i}λi​是LLL的特征值。所以:
Lvi=λivi(5)Lv_{i}=\lambda_{i}v_{i}\tag{5}Lvi​=λi​vi​(5)

而所有的基向量{e−jk2πNn}\{e^{-jk\frac{2\pi}{N}n}\}{e−jkN2π​n}都满足亥姆霍兹方程（Helmholtz Equation）：
∇2f=∂2e−jk2πNn∂n2=−(k2πN)2e−jk2πNn=−w2f(6)\nabla^{2}f=\frac{\partial^{2} e^{-jk\frac{2\pi}{N}n}}{\partial n^{2}}=-(k\frac{2\pi}{N})^{2}e^{-jk\frac{2\pi}{N}n}=-w^{2}f\tag{6}∇2f=∂n2∂2e−jkN2π​n​=−(kN2π​)2e−jkN2π​n=−w2f(6)

∇2\nabla^{2}∇2是拉普拉斯算子，e−jk2πNne^{-jk\frac{2\pi}{N}n}e−jkN2π​n是拉普拉斯算子∇2\nabla^{2}∇2的特征函数,−w2-w^{2}−w2是特征函数的特征值。
将式(5)和式(6)对比，可知：e−jk2πNne^{-jk\frac{2\pi}{N}n}e−jkN2π​n~viv_{i}vi​,−w2-w^{2}−w2 ~ λi\lambda_{i}λi​。
用fff表示时域信号，f^\hat{f}f^​表示相应的频域信号，将这两个类比带入离散傅里叶变换的公式，得到：
f^(k)=∑n=0N−1f(n)e−jk2πNn=∑n=0N−1f(n)vk(n)=vkTf(7)\hat{f}(k) =\sum_{n=0}^{N-1}{f(n)e^{-jk\frac{2\pi}{N}n}}=\sum_{n=0}^{N-1}{f(n)v_{k}(n)}= v_{k}^{T}f\tag{7}f^​(k)=n=0∑N−1​f(n)e−jkN2π​n=n=0∑N−1​f(n)vk​(n)=vkT​f(7)

由式(7)可知：
f^=VTf(8)\hat{f}=V^{T}f\tag{8}f^​=VTf(8)

将式(8)带入卷积公式得：
(g∗f)=V[VTg⨀VTf](9)(g*f)=V[V^{T}g\bigodot V^{T}f ]\tag{9}(g∗f)=V[VTg⨀VTf](9)

由于VTg=(v1Tg,...,vnTg)TV^{T}g=(v_{1}^{T}g,...,v_{n}^{T}g)^{T}VTg=(v1T​g,...,vnT​g)T,所以VTg⨀VTf=diag(v1Tg,...,vnTg)VTfV^{T}g\bigodot V^{T}f=diag(v_{1}^{T}g,...,v_{n}^{T}g)V^{T}fVTg⨀VTf=diag(v1T​g,...,vnT​g)VTf,令gθ=diag(v1Tg,...,vnTg)g_{\theta}=diag(v_{1}^{T}g,...,v_{n}^{T}g)gθ​=diag(v1T​g,...,vnT​g),所以(g∗f)(n)=VgθVTf(10)(g*f)(n)=Vg_{\theta}V^{T}f\tag{10}(g∗f)(n)=Vgθ​VTf(10)

论文中所给的频域公式为：
xk+1,j=h(V∑i=1fk−1Fk,i,jVTxk,i)(11)x_{k+1,j}=h(V\sum_{i=1}^{f_{k-1}}{F_{k,i,j}V^{T}x_{k,i}})\tag{11}xk+1,j​=h(Vi=1∑fk−1​​Fk,i,j​VTxk,i​)(11)

在式(11)中Fk,i,jF_{k,i,j}Fk,i,j​就是gθg_{\theta}gθ​，xk,i就是fx_{k,i}就是fxk,i​就是f，fff相当于输入信号xxx的一个通道的信号。所以在每个通道求完卷积后，将结果累加，得到输出结果的一个通道的值。xk,ix_{k,i}xk,i​表示第k层所有节点的第i个特征拼接形成的向量。Fk,i,jF_{k,i,j}Fk,i,j​表示第k层第j个滤波器的i个值的频域表示(类比于传统卷积的第jjj个卷积核的第iii个通道),h(∗)h(*)h(∗)依然是非线性激活函数。

论文其他内容:
(1)经常情况下，V只有前d个特征向量起作用，因此取前d个特征向量，以减少参数。
(2)通过样条差值的方法，近似的求出这个操作的解，而使权值参数减少到O(1)。
(3)实验部分。

AND deep