2.《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》论文理解

论文理解"/>

2.《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》论文理解

在 《Spectral Networks and Deep Locally Connected Networks on Graphs》的基础上，
《Convolutional Neural Networks on Graphs
with Fast Localized Spectral Filtering》作出了改进：
作者提出，泛化卷积网络到图上需要以下3个基本的步骤：
（1）在图上设计出局部的卷积核
（2）将的相似节点聚类的图粗化过程
（3）将空间分辨率转化为更高的滤波器分辨率的图池化操作

1.在图上设计出局部的卷积核
定义无向图 G = ( V , E , W ) G=(V,E,W) G=(V,E,W),其中 V V V是节点的集合， ∣ V ∣ = n |V|=n ∣V∣=n， E E E是边的集合， W W W是由节点之间的连接权重得到的邻接矩阵， D D D是度矩阵，并且 D i i = ∑ j W i j D_{ii}=\sum_{j}{W}_{ij} Dii​=∑j​Wij​， L L L是图的拉普拉斯矩阵， L = D − W L=D-W L=D−W。 U = [ u 0 , . . . , u n − 1 ] ∈ R n × n U=[u_{0},...,u_{n-1}]\in R^{n×n} U=[u0​,...,un−1​]∈Rn×n是 L L L的特征向量矩阵， Λ = d i a g ( [ λ 0 , . . . λ n − 1 ] ) ∈ R n × n \Lambda=diag([\lambda_{0},...\lambda_{n-1}])\in R^{n×n} Λ=diag([λ0​,...λn−1​])∈Rn×n，“ ∗ g *_{g} ∗g​”表示图上的卷积算子，所以
y = x ∗ g g = U ( ( U T x ) ⨀ ( U T g ) ) = U g θ U T x (1) y=x*_{g}g=U((U^{T}x)\bigodot(U^{T}g) )=Ug_{\theta}U_{T}x\tag{1} y=x∗g​g=U((UTx)⨀(UTg))=Ugθ​UT​x(1)

其中， g θ = d i a g [ ( u 0 T g , . . . , u n − 1 T g ) ] g_{\theta}=diag[(u_{0}^{T}g,...,u_{n-1}^{T}g)] gθ​=diag[(u0T​g,...,un−1T​g)],
因为对于 L L L来说，特征值和特征向量一一对应，当 λ i \lambda_{i} λi​确定时， u i T u_{i}^{T} uiT​就确定了，所以可以写成 g ( λ i ) = u i T g g(\lambda_{i})=u_{i}^{T}g g(λi​)=uiT​g，那么
g θ = d i a g [ ( g ( λ 0 ) , . . . , g ( λ n − 1 ) ) ] = g ( d i a g ( [ λ 0 , . . . λ n − 1 ] ) ) = g ( Λ ) = d i a g ( θ ) (2) g_{\theta}=diag[(g(\lambda_{0}),...,g(\lambda_{n-1}))]=g(diag([\lambda_{0},...\lambda_{n-1}]))=g(\Lambda)=diag(\theta)\tag{2} gθ​=diag[(g(λ0​),...,g(λn−1​))]=g(diag([λ0​,...λn−1​]))=g(Λ)=diag(θ)(2)

其中， θ ∈ R n \theta \in R^{n} θ∈Rn，所以 g θ g_{\theta} gθ​是个关于 Λ \Lambda Λ的函数，所以
y = U g θ ( Λ ) U T x (3) y=Ug_{\theta}(\Lambda)U^{T}x\tag{3} y=Ugθ​(Λ)UTx(3)

由于 g θ ( Λ ) g_{\theta}(\Lambda) gθ​(Λ)是一个关于 Λ \Lambda Λ的函数，由 K K K阶矩阵级数展开得到：
g θ ( Λ ) ≈ ∑ k = 0 K − 1 θ k Λ k (4) g_{\theta}(\Lambda)\approx\sum_{k=0}^{K-1}{\theta_{k}\Lambda^{k}}\tag{4} gθ​(Λ)≈k=0∑K−1​θk​Λk(4)

将式(4)带入式(1)，得到：
y ≈ U ∑ k = 0 K − 1 θ k Λ k U T x = ∑ k = 0 K − 1 θ k L k x = g θ ( L ) x (5) y\approx U\sum_{k=0}^{K-1}{\theta_{k}\Lambda^{k}}U^{T}x=\sum_{k=0}^{K-1}{\theta_{k}L^{k}}x=g_{\theta}(L)x\tag{5} y≈Uk=0∑K−1​θk​ΛkUTx=k=0∑K−1​θk​Lkx=gθ​(L)x(5)

其中 ( g θ ( L ) ) i , j (g_{\theta}(L))_{i,j} (gθ​(L))i,j​表示卷积核 g θ g_{\theta} gθ​当中心在节点 i i i上时对节点 j j j的权值， d g ( i , j ) d_{g}(i,j) dg​(i,j)表示节点 i , j i,j i,j之间的最短路径的边的数目，当 d g ( i , j ) > K − 1 d_{g}(i,j)>K-1 dg​(i,j)>K−1时， ( g θ ( L ) ) i , j (g_{\theta}(L))_{i,j} (gθ​(L))i,j​的值为0，这意味这在计算节点 i i i的邻域节点时，只计算 d g ( i , j ) ≤ K − 1 d_{g}(i,j)\leq K-1 dg​(i,j)≤K−1的节点作为邻域进行卷积。
在这里的多项式展开可以利用切比雪夫多项式展开，切比雪夫多项式满足：
T k ( x ) = 2 x T k − 1 ( x ) − T k − 2 ( x ) (6) T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x)\tag{6} Tk​(x)=2xTk−1​(x)−Tk−2​(x)(6)

其中， T 0 = 1 , T 1 = x T_{0}=1,T_{1}=x T0​=1,T1​=x。
而且切比雪夫多项式 { T n ( x ) } \{T_{n}(x)\} {Tn​(x)}在 L 2 ( [ − 1 , 1 ] , d y / 1 − y 2 ) L^{2}([-1,1],dy/\sqrt{1-y^{2}}) L2([−1,1],dy/1−y2 ​)为正交基，即 ∫ − 1 1 T n ( x ) T m ( x ) 1 1 − x 2 d x \int_{-1}^{1}{T_{n}(x)T_{m}(x)\frac{1}{\sqrt{1-x^{2}}}dx} ∫−11​Tn​(x)Tm​(x)1−x2 ​1​dx=0(当n!=m), π \pi π(当n=m=0), π / 2 \pi/2 π/2(当n=m!=0)。所以
g θ ( Λ ) = ∑ k = 0 K − 1 θ k T k ( Λ ~ ) (7) g_{\theta}(\Lambda)=\sum_{k=0}^{K-1}\theta_{k}T_{k}(\tilde{\Lambda})\tag{7} gθ​(Λ)=k=0∑K−1​θk​Tk​(Λ~)(7)

其中， Λ ~ = 2 Λ / λ m a x − I n \tilde{\Lambda}=2\Lambda/\lambda_{max}-I_{n} Λ~=2Λ/λmax​−In​。将 Λ \Lambda Λ这个对角矩阵规范到 [ − 1 , 1 ] [-1,1] [−1,1]之间。所以 L ~ = 2 L / λ m a x − I n \tilde{L}=2L/\lambda_{max}-I_{n} L~=2L/λmax​−In​。
令 x ‾ k = T k ( L ~ ) x \overline x_{k}=T_{k}(\tilde L)x xk​=Tk​(L~)x，由式（6）可知： x ‾ k = 2 L ~ x ‾ k − 1 − x ‾ k − 1 , x ‾ 0 = x , x ‾ 1 = L ~ x (8) \overline x_{k}=2\tilde L\overline x_{k-1}-\overline x_{k-1},\overline x_{0}=x,\overline x_{1}=\tilde Lx\tag{8} xk​=2L~xk−1​−xk−1​,x0​=x,x1​=L~x(8)

将式（8）带入式（7）推出：
y = g θ ( L ) x = [ x ‾ 0 , . . . x ‾ K − 1 ] θ (9) y=g_{\theta}(L)x=[\overline x_{0},...\overline x_{K-1}]\theta \tag{9} y=gθ​(L)x=[x0​,...xK−1​]θ(9)

到此，其实已经构造完了局部卷积核，原来的卷积公式： y = U g θ ( Λ ) U T x y=Ug_{\theta}(\Lambda)U^{T}x y=Ugθ​(Λ)UTx，新的卷积公式 y = [ x ‾ 0 , . . . x ‾ K − 1 ] θ y=[\overline x_{0},...\overline x_{K-1}]\theta y=[x0​,...xK−1​]θ,将求解 g θ ( Λ ) g_{\theta}(\Lambda) gθ​(Λ)部分变为求解 θ \theta θ(即为卷积核的训练参数)，复杂度降低为 O ( K ) O(K) O(K)，并且计算了求解特征矩阵 U U U，变为计算 [ x ‾ 0 , . . . x ‾ K − 1 ] [\overline x_{0},...\overline x_{K-1}] [x0​,...xK−1​],其复杂度为 O ( K ∣ E ∣ ) O(K|E|) O(K∣E∣)， ∣ E ∣ |E| ∣E∣表示图中边的数目。而且这个部分在训练的时候只需要计算一次，只于 x , L x,L x,L有关，也就是只与输入有关，没有训练参数在其中。
当输入为多通道样本的时候：
y s , j = ∑ i = 1 F i n g θ i , j ( L ) x s , i = ∑ i = 1 F i n [ x ‾ s , i , 0 , . . . x ‾ s , i , K − 1 ] θ i , j ∈ R n (10) y_{s,j}=\sum_{i=1}^{F_{in}}{g_{\theta_{i,j}}(L)x_{s,i}}=\sum_{i=1}^{F_{in}}[\overline x_{s,i,0},...\overline x_{s,i,K-1}]\theta_{i,j} \in R^{n}\tag{10} ys,j​=i=1∑Fin​​gθi,j​​(L)xs,i​=i=1∑Fin​​[xs,i,0​,...xs,i,K−1​]θi,j​∈Rn(10)

其中， s s s表示某个样本 s s s， x s , i x_{s,i} xs,i​表示样本的第 i i i个特征， θ i , j ∈ R K \theta_{i,j}\in R^{K} θi,j​∈RK表示第 j j j个滤波器对样本 s s s的第 i i i个特征的切比雪夫系数， θ ∈ R F o u t × F i n × K = R J × I × K \theta\in R^{F_{out}×F_{in}×K}=R^{J×I×K} θ∈RFout​×Fin​×K=RJ×I×K

2.将的相似节点聚类的图粗化过程
在池化操作的时候，需要在图像找到有意义的邻域节点，它们需要有一定的相似性。这里作者使用了 G r a c l u s Graclus Graclus分层聚类算法，首先选择了一个未标记的节点 i i i,然后从其他未标记的节点中找出最大的局部归一化切割 W i , j ( 1 / d i + 1 / d j ) W_{i,j}(1/d_{i}+1/d_{j}) Wi,j​(1/di​+1/dj​)的节点 j j j,将这两个节点进行标记，粗化后的权值等于这两个节点的权值之和，然后重复这个过程直到所有的节点都被标记。这个过程将节点的数量大约减少了一半，并且这个过程中会存在一些孤立节点以及未匹配点。

3.将空间分辨率转化为更高的滤波器分辨率的图池化操作
在池化操作中，需要完成两个步骤：
①：建立一个二叉树
②：重新排列节点变成一维信号
在粗化后，每个节点都将有两个子节点，即前一层粗化中是子节点，求和后得到后一个粗化中的节点。通过粗化创建的二叉树有以下特点：（绿色是常规节点，橙色是孤立节点，蓝色是假节点）
1):常规的节点和孤立节点有两个常规的子节点；图中 g 1 g_{1} g1​的0节点，它是个孤立节点， g 1 g_{1} g1​中没有和它匹配的点，但是它的子节点在 g 0 g_{0} g0​中是一对配对的节点0,1;
2):孤立节点可以通过添加假节点（未连接的节点，其权值为0）进行配对，成为子节点；图中 g 2 g_{2} g2​的节点0，它的子节点是 g 1 g_{1} g1​中的孤立节点0以及假节点1；
3):假节点对应的子节点总都是假节点；
图中 g 1 g_{1} g1​的节点1，它是由于孤立节点0添加的，所以在 g 0 g_{0} g0​中的子节点为假节点2,3；

在图中左边部分是粗化过程，初始的图 g 0 g_{0} g0​有8个节点，并且希望经过第一次粗化得到 g 1 g_{1} g1​有5个点，所以需要在 g 0 g_{0} g0​中找到3对匹配的点，剩下的节点作为孤立节点于假节点匹配，得到 g 1 g_{1} g1​;之后第二次粗化希望 g 2 g_{2} g2​有3个点，那么需要找到2对匹配的点，然后剩下的孤立点与假节点匹配，在 g 1 g_{1} g1​中的假节点对应到 g 0 g_{0} g0​中需要添加两个假节点。到此，完成了粗化的过程。
图的右边是池化的过程，它的过程相当于将 g 0 g_{0} g0​中的12个节点按照粗化过程中的节点关系排列成为一维信号（ 将 g 2 将g_{2} 将g2​节点排成一维信号后，反推出 g 0 g_{0} g0​中节点的顺序，即建立二叉树的过程），按照传统的池化窗口的形式进行池化操作即可