From CNN to GCNN
CNN无法处理非欧式数据，又希望在拓扑图上有效地提取空间特征来进行机器学习。因此GCNN成为了研究重点。
CNN的性质
CNN具有局部平稳(i.e.与位置无关，满足平移不变形) 以及多尺度的特点。
在图像领域，数据以格子的形式分布，非常规律，对其进行处理时需要处理的是每个格子上的信号而非结构。
然而，CNN仅在欧式数据上能够发挥作用，对于图、流形等非欧式数据而言，需要进行一定的变换。
欧式数据的特点： 1. 非负 2. 对称 3. 满足三角不等式
傅里叶变换
在连续的空间上：
\[h(t) = (f * g)(t) \overset{def}\Longrightarrow \int f(t)g(t - \tau) d \tau\]
在离散的空间上：
\[h(x,y) = (f * g)(x,y) \overset{def}\Longrightarrow \sum_{m,n} f(x-m,y-n)g(m,n)\]
不同域的CNN:
- 对于频域而言，卷积核若定义在频域，则它不是local的，对一个地方的修改会影响到全局。
- 对于空间域而言，在节点上定义卷积，对节点周围的邻居节点做平滑。但对于大多数节点而言，度很小，而小部分节点的度很大。
谱域的CNN方法
一个图可以被定义为\(G = (V,E,W)\),其中\(n = |V|\)为节点的个数，\(W \in R^{n \times n}\)为权重邻接矩阵。
每个节点有\(d\)个feature，\(X \in R^{n \times d}\) 为节点的特征矩阵。
对于在非欧式距空间中对数据进行处理，我们可以考虑两种方法： 1. 将图嵌入到欧式空间，再使用CNN对其进行处理，即embedding的方法 2. 对CNN进行修改，使其能够用于图结构，即GCNN的方法
note：embedding嵌入什么空间取决于loss的设置。此外，若是需要在图中找pattern，则embedding的方式不适用，因为其找不到结构pattern。
图上的傅里叶basis
图上的拉普拉斯L：对信号求导，越大越不平滑，是刻画图上平滑程度的算子。
\[L=D-W\] D为对角阵，\(D_{ii} = \sum_j W_{ij}\)
L为非负的，对应信号的平滑程度，当值等于0时信号平滑。
Normalized graph Laplacien:
\[L = I - D^{- \frac{1}{2}} W D^{- \frac{1}{2}}\] \(I\):Identity matrix
在傅里叶变换中，利用基组使空间域映射到频域，即利用正弦波对信号进行分解。
图拉普拉斯可以被对角化为：
\[L = U \Lambda U^T\]
\(\{u_l\}^{n-1}_{l=0}\) : 正交特征向量的完全集 \(\{\lambda_l\}^{n-1}_{l=0}\) : 相应的非负特征值
需要注意的是，都是正交才能进行点积。
其中\(U=[u_0,...,u_{n-1}],\Lambda = diag([\lambda_0,...,\lambda_{n-1}])\)
图傅里叶变换
对于一个信号\(x \in R^n\),傅里叶变换定义为：
\[\hat{x} = U^T x\]
傅里叶逆变换：
\[ x = U \hat{x} \]
傅里叶变换中的定理:卷积在进行傅里叶变换之后会变为点积
因此，x与y的卷积可以表示为：
\[x \ast_G y = U (( U^T x) \odot ( U^T y)) \]
卷积的过程可以被拆解成三步：
- 对x做傅里叶变换: \(U^T x\)
- 乘以卷积核:\(g_{\theta} U^T x\)
- 做傅里叶逆变换: \(U g_{\theta} U^T x\)
因此卷积可以被写为：
\[x \*_G y = U g_{\theta} U^T x \]
\[x_{k+1,j} = h(\sum^{f_k}_{i=1} U F_{k,i,j} U^T x_{k,i})\] \(x_{k,i}\):k+h 信号
缺点： 1. 要进行特征分解 2. 需要大量计算。U的复杂度为\(O(N^2)\) 3. 不是localized
ChebyNet
思想：参数化滤波器 \[ g_{\theta} = diag([\theta_0,...,\theta_{n-1}]) \Rightarrow g_\beta(\Lambda) = \sum^{K-1}_{k = 0} \beta_k \Lambda^k \]
参数由n个减少为k个(\(\beta_k\))
ChebyNet: \[ x *\ast_G y = U g_\beta (\Lambda) U^T x = \sum_{k=0}^{K-1} \beta_k L^k x \]
U被约了，只留下了L，而L是稀疏的。 通过约束空间，来使使其变成local。
优点： 1. 无需特征分解 2. 卷积核是local的 3. 计算复杂度：\(O(n^2) \rightarrow O(|E|)\)
Graph wavelet neural network(GWNN)
ChebyNet通过特征值矩阵\(\Lambda\)的多项式方程来限制图滤波器的空间来达到localized卷积：
\[ g_\theta(\Lambda) = \sum^{K-1}_{k=0} \theta_k \Lambda^k \]
GWNN通过使用小波基对基进行替换来达到localized图卷积的效果。
傅里叶basis \(U\)： - 稠密 - 非局部 - 高计算成本
小波basis \(\psi_s = U e^{\lambda_s} U^T\)： - 稀疏 - 局部 - 低计算成本
主要思想：从特征变换中剥离图卷积
\[x_{k+1,j} = h(\sum^p_{i=1} \psi_s F_{k,i,j} \psi^{-1}_s x_{k,i}), \quad j = 1,...,q \]
特征变换部分：
\[y_{k,j} = \sum^{p}_{i=1} T_{ji} x_{k,i}\]
图卷积部分：
\[x_{k+1,j} = h(\psi_s F_k \psi^{-1}_s y_{k,j})\]
空间域CNN方法
类比方法
将卷积过程拆分成三步： 1. 确定邻居 2. 确定邻居的顺序 3. 参数共享（卷积核里，在定序的基础上）
问题：邻居的数量不同（有的多有的少），然而卷积核的大小是固定的。
解决方式：给定中心节点，确定其到其他节点的距离函数，选前TOP
K个邻居。
GraphSAGE
分为两步： 1. 以某个节点为中心对其邻居节点进行采样 2. 做aggregate（带权平均）
\[a_v^{(k)} = AGGREGATE^{(k)}(\{h_u^{(k-1)} : U \in N(v) \}) \] \[h_v^(k) = COMBINE^{(k)} (h_v^{(k-1)}, a_v^{(k)})\]
GCN
\[Z = f(X,A) = softmax(\hat{A} ReLU(\hat{A}XW^{(0)})) W^{(1)})\]
\(\hat{A}\) :
邻接矩阵的变形，给定，与结构有关
\(W^{(0)}, W^{(1)}\):
特征变换参数
\(X\) : feature
对\(\hat{A}\)进行参数化 \(\rightarrow\) 加attention机制：
\[\alpha_{ij} = \frac{exp(Leaky \quad ReLU(\overset{\sim}a [W \vec{h}_i ||W \vec{h}_j]))}{\sum_{k \in N_i} exp(Leaky \quad ReLU(\overset{\sim}a [W \vec{h}_i ||W \vec{h}_j]))}\]
本质上是求节点i和j的相似度。
MoNet
是所有空间方法的通用形式。
\[(f*g)(x) = \sum_{j=1}^J g_j D_j (x)f\]
\(D_j (x)\) : kernel
function,在频域中为基
\(g_j\):kernel,可以定义为相似度函数。整个公式看做是相似度函数的加权
谱域：显式定义变换 空间域：不显式定义变换
Graph pooling
- 节点粗化
- 节点选择