Graph Convolutional Network

Graph Convolutional Network

Introduction

Why Graph

图是科学研究中一种常用的数据结构，可用于描述物体（结点）与它们之间的关系（边），例如社交网络、知识图谱等。
然而，区别于图像这类Euclidean Structure（像素点是排列整齐的矩阵），图是一种Non-Euclidean Structure。

Why Convolution

传统卷积，本质上是一种加权求和。CNN中，卷积核的参数通过优化求出，能够提取多尺度的局部空间特征（multi-scale localized spatial features），主要应用于欧式结构的数据上（可保证卷积的平移不变性）。
比起FNN，CNN的优点主要有以下三点：

• 局部连接（local connection）=> 图本身具有局部连接性
• 共享权重（shared weights）=> 共享参数能够减少传统谱图方法的计算复杂性
• 多层（multi-layer）=> 适合提取多层次的特征

然而图是非欧式结构的，无法保证拓扑图中每个顶点的相邻顶点数目相同，便无法使用相同尺寸的传统卷积核进行卷积运算，GCN的理论主要是为了引入可以优化的卷积参数。（相对传统GNN的好处呢）

Comparison with Graph Embedding

Graph Embedding旨在将图上的每个结点映射为低维向量，例如DeepWalk，node2vec等方法，然而它存在以下问题：

• 每个结点都要映射成一个向量，向量之间没有共享参数，计算复杂度大
  • 难以处理动态图，新增一个结点就要重新训练整个图（但是GCN也需要重新训练，GraphSAGE不一定需要）
  • ？无监督和半监督，传统的Graph Embedding只关注图的局部空间结构，并不关注具体结点的特征（不针对具体的task）；而GCN更多是关注于一个具体的task，训练时可引入部分结点的label信息，包括结点本身的特性。

Generalize Convolution

如何在图上推广卷积，总体来说可以分为两类：

• Spatial Domain（Non-Spectral Domain）

  • 找出neighbor（如何定义每个顶点的neighbor，如何处理不同数目的neighbor）
  • 聚合neighbor（如何聚合）

• Spectral Domain

  • 利用图谱理论（Spectral Graph Theory），借助图的拉普拉斯矩阵的特征值和特征向量推广图上的傅里叶变换，从而定义图上的卷积（联系卷积定理）

几乎所有的Spectral Domain方法都需要使用拉普拉斯矩阵，这就使得它必须针对一个具体的图训练（transductive learning），改变图就需要重新训练，而Spatial Domain方法不一定需要（inductive learning，在图改变不大时）。
Spatial Domain方法更为直观，直接定义图中空间相邻的顶点，但是主要需要考虑如何对不同数目的邻居进行聚合操作，以及怎么保持CNN的局部不变性。

GCN

傅里叶级数(Fourier Series)

光的色散现象：光是一种波，光的颜色由振幅和频率所决定。经过一个三棱镜的折射后，白色的光波被分解为七色光波（实际是无数种颜色的光波）。
任何周期函数，都可以使用傅里叶笔级数展开法，将它们分解为有限或无限个不同频率不同振幅的正弦函数（余弦函数）的叠加。

三角函数系

三角函数系${1, \sin{x}, \cos{x}, \sin{2x}, \cos{2x}, …, \sin{nx}, \cos{nx}, …}$在$[-\pi, \pi]$上正交，即其中任意两个不同的函数之积在$[-\pi, \pi]$上的积分等于0. 但在三角函数系中两个相同的函数的乘积在$[-\pi, \pi]$上的积分不等于0.
函数$f(x)$和$g(x)$在[a, b]区间正交：
$$\int_a^b{f(x)\cdot{g(x)}\mathrm{d}x \ = \ 0}$$
可以将函数看作是一个无穷维的向量，例如$[\sin{1}, \sin{2}, \sin{3}, …]$和$[\cos{1}, \cos{2}, \cos{3}, …]$，那么两个函数正交，即需要满足$\sin{1}\cdot\cos{1}+\sin{2}\cdot\cos{2}+\sin{3}\cdot\cos{3}+…=0$，两个向量对应维度乘积再求和，对应为两个函数乘积再积分。

证明：
显然
$$
\begin{aligned}
1) \ \int{-\pi}^{\pi}1\cdot \cos{nx}\, \mathrm{d}x \ = \ \int{
-\pi}^{\pi}1\cdot \sin{nx}\, \mathrm{d}x \ = \ 0 \qquad (n=1, 2, …) \
\end{aligned}
$$
由积化和差可得
$$
\begin{aligned}
2) \ &\int{-\pi}^{\pi}\cos{nx}\cdot \cos{mx}\, \mathrm{d}x \ = \ \int{-\pi}^{\pi}\frac{\cos{(n+m)x}+\cos{(n-m)x}}{2}\, \mathrm{d} x \
= \ &\frac{1}{2}\, [\frac{\sin{(n+m)x}}{n+m}+\frac{\sin{(n-m)x}}{n-m}]{-\pi}^{\pi} \ = \ 0 \qquad (n\in{N^}, m\in{N^}, n\neq{m}) \
\end{aligned}
$$
同理可证
$$
\begin{aligned}
3) \ &\int{-\pi}^{\pi}\sin{nx}\cdot \sin{mx}\, \mathrm{d}x \ = \ 0 \qquad (n\in{N^}, m\in{N^}, n\neq{m}) \
4) \ &\int{-\pi}^{\pi}\cos{nx}\cdot \sin{mx}\, \mathrm{d}x \ = \ 0 \qquad (n\in{N^}, m\in{N^}) \
\end{aligned}
$$
又
$$
\begin{aligned}
5) \ &\int{-\pi}^{\pi}1\cdot 1 \, \mathrm{d}x \ = \ 2\pi \
6) \ &\int{-\pi}^{\pi}\cos^2{nx} \, \mathrm{d}x \ = \ \pi \qquad (n\in{N^*}) \
7) \ &\int{-\pi}^{\pi}\sin^2{nx} \, \mathrm{d}x \ = \ \pi \qquad (n\in{N^*}) \
\end{aligned}
$$
得证

$T=2\pi$的函数展开为傅里叶级数(Fourier Series)

$$
f(x) \ = \ \frac{a0}{2} +\sum^{\infty}{n=1}{a_n\cos{nx}+b_n\sin{nx}} \qquad
\left{
\begin{aligned}
&a0=\frac{1}{\pi}\int{-\pi}^{\pi}f(x)\mathrm{d}x \
&an=\frac{1}{\pi}\int{-\pi}^{\pi}f(x)\cos{nx}\mathrm{d}x \
&bn=\frac{1}{\pi}\int{-\pi}^{\pi}f(x)\sin{nx}\mathrm{d}x
\end{aligned}
\right.
$$

• 确定$a_0$：对$f(x)$两边求积分

  $$
  \begin{aligned}
  \int{-\pi}^{\pi}f(x)\mathrm{d}x \ &= \int{-\pi}^{\pi}\frac{a0}{2}\mathrm{d}x+\int{-\pi}^{\pi}\sum_{n=1}^{\infty}an\cos{nx}\mathrm{d}x+\int{-\pi}^{\pi}\sum_{n=1}^{\infty}b_n\sin{nx}\mathrm{d}x \
  &= \frac{a0}{2}\int{-\pi}^{\pi}\mathrm{d}x+\sum_{n=1}^{\infty}an\int{-\pi}^{\pi}1\cdot\cos{nx}\mathrm{d}x+\sum_{n=1}^{\infty}bn\int{-\pi}^{\pi}1\cdot\sin{nx}\mathrm{d}x \qquad &{\text{（对x积分与$a_n$无关）}} \
  &= \frac{a0}{2}\cdot{2\pi}+\sum{n=1}^{\infty}an\cdot{0}+\sum{n=1}^{\infty}b_n\cdot{0} \qquad &{\text{（三角函数的正交性）}} \
  &= \pi\cdot{a_0} \
  \Rightarrow a0 \ &= \ \frac{1}{\pi}\int{-\pi}^{\pi}f(x)\mathrm{d}x \
  \end{aligned}
  $$

• 确定$a_n$：两边同乘$\cos{mx}$后积分

  $$
  \begin{aligned}
  \int{-\pi}^{\pi}f(x)\cos{mx}\mathrm{d}x \ &= \int{-\pi}^{\pi}\frac{a0}{2}\cos{mx}\mathrm{d}x+\int{-\pi}^{\pi}\sum_{n=1}^{\infty}an\cos{nx}\cos{mx}\mathrm{d}x+\int{-\pi}^{\pi}\sum_{n=1}^{\infty}b_n\sin{nx}\cos{mx}\mathrm{d}x \
  &= \frac{a0}{2}\int{-\pi}^{\pi}\cos{mx}\cdot{1}\mathrm{d}x+\int{-\pi}^{\pi}\sum{n=1}^{\infty}an\cos{nx}\cos{mx}\mathrm{d}x+\sum{n=1}^{\infty}bn\int{-\pi}^{\pi}\sin{nx}\cos{mx}\mathrm{d}x \qquad \
  &= \int{-\pi}^{\pi}\sum{n=1}^{\infty}an\cos{nx}\cos{mx}\mathrm{d}x \qquad &{\text{（三角函数的正交性）}} \
  &= \int{-\pi}^{\pi}a_n\cos{nx}\cos{nx}\mathrm{d}x \qquad &{\text{（$n=m$时才保留）}} \
  &= \pi\cdot{a_n} \
  \Rightarrow an \ &= \ \frac{1}{\pi}\int{-\pi}^{\pi}f(x)\cos{nx}\mathrm{d}x \
  \end{aligned}
  $$

• 确定$b_n$：如上两边同乘$\sin{mx}$后积分

$T=2L$的函数展开为傅里叶级数(Fourier Series)

$$
f(t) \ = \ \frac{a0}{2} +\sum^{\infty}{n=1}{a_n\cos{n{\omega}t}+b_n\sin{n{\omega}t}} \qquad
\left{
\begin{aligned}
&a0=\frac{2}{T}\int{0}^{T}f(t)\mathrm{d}t \
&an=\frac{2}{T}\int{0}^{T}f(t)\cos{n{\omega}t}\mathrm{d}t \
&bn=\frac{2}{T}\int{0}^{T}f(t)\sin{n{\omega}t}\mathrm{d}t
\end{aligned}
\right.
\qquad
\ ( \omega \ = \ \frac{\pi}{L} \ = \ \frac{2\pi}{T})
$$

证明：
换元，令$x=\frac{\pi}{L}t$，则$t=\frac{L}{\pi}x$
因为f(t)是以$2L$为周期的周期函数，令$f(t)=f(\frac{L}{\pi}x)=g(x)$
则$g(x+2\pi)=f(\frac{L}{\pi}x+\frac{L}{\pi}\cdot2\pi)=f(\frac{L}{\pi}x+2L)=f(\frac{L}{\pi}x)=g(x)$是以$2\pi$为周期的周期函数
所以
$$
g(x) \ = \ \frac{a0}{2} +\sum^{\infty}{n=1}{a_n\cos{nx}+b_n\sin{nx}} \qquad
\left{
\begin{aligned}
&a0=\frac{1}{\pi}\int{-\pi}^{\pi}g(x)\mathrm{d}x \
&an=\frac{1}{\pi}\int{-\pi}^{\pi}g(x)\cos{nx}\mathrm{d}x \
&bn=\frac{1}{\pi}\int{-\pi}^{\pi}g(x)\sin{nx}\mathrm{d}x
\end{aligned}
\right.
$$
代入$x=\frac{\pi}{L}t$，所以
$$
f(t) \ = \ \frac{a0}{2} +\sum^{\infty}{n=1}{a_n\cos{\frac{n\pi}{L}t}+b_n\sin{\frac{n\pi}{L}t}} \qquad
\left{
\begin{aligned}
&a0=\frac{1}{\pi}\int{-L}^{L}f(t)\mathrm{d}t \
&an=\frac{1}{\pi}\int{-L}^{L}f(t)\cos{\frac{n\pi}{L}t}\mathrm{d}t \
&bn=\frac{1}{\pi}\int{-L}^{L}f(t)\sin{\frac{n\pi}{L}t}\mathrm{d}t
\end{aligned}
\right.
$$
工程中，由于t为正数，使用$\omega=\frac{\pi}{L}=\frac{2\pi}{T}$；由于是周期函数，可将积分区间从$[-L, L]$变为$[0, 2L]$即$[0, T]$，证毕。

欧拉公式

傅里叶级数的复数形式

$$f(t) \ = \ \sum_{n=-\infty}^{\infty}{c_n}{e^{in{\omega}t}} \qquad c_n \ = \frac{1}{T}\int_0^T{f(t)e^{-in{\omega}t}\mathrm{d}t} \qquad \omega \ = \ \frac{2\pi}{T}$$

证明：
由欧拉公式
$$e^{i\theta}=cos{\theta}+isin{\theta}$$
则
$$
\left{
\begin{aligned}
&\cos{\theta} \ = \ \frac{1}{2}(e^{i\theta}+e^{-i\theta}) \
&\sin{\theta} \ = \ -\frac{1}{2}i(e^{i\theta}-e^{-i\theta})
\end{aligned}
\right.
$$
代入
$$
f(t) \ = \ \frac{a0}{2} +\sum^{\infty}{n=1}{a_n\cos{n{\omega}t}+b_n\sin{n{\omega}t}} \qquad
\left{
\begin{aligned}
&a0=\frac{2}{T}\int{0}^{T}f(t)\mathrm{d}t \
&an=\frac{2}{T}\int{0}^{T}f(t)\cos{n{\omega}t}\mathrm{d}t \
&bn=\frac{2}{T}\int{0}^{T}f(t)\sin{n{\omega}t}\mathrm{d}t
\end{aligned}
\right.
$$
$$f(t)\ = \ \frac{a0}{2} + \sum{n=1}^{\infty}{[\frac{1}{2}{a_n}(e^{in{\omega}t}+e^{-in{\omega}t})-\frac{1}{2}i{b_n}(e^{in{\omega}t}-e^{-in{\omega}t})]}$$

理解Fourier Series

$$
f(t) \ = \ \frac{a0}{2} +\sum^{\infty}{n=1}{a_n\cos{n{\omega}t}+b_n\sin{n{\omega}t}} \qquad
\left{
\begin{aligned}
&a0=\frac{2}{T}\int{0}^{T}f(t)\mathrm{d}t \
&an=\frac{2}{T}\int{0}^{T}f(t)\cos{n{\omega}t}\mathrm{d}t \
&bn=\frac{2}{T}\int{0}^{T}f(t)\sin{n{\omega}t}\mathrm{d}t
\end{aligned}
\right.
\qquad
\ ( \omega \ = \ \frac{\pi}{L} \ = \ \frac{2\pi}{T})
$$

其中$n\omega=\frac{2{\pi}n}{T}$是频率。

• 理解一：将一个周期函数从时域（时间与振幅的关系）转化为频域（频率与振幅的关系）
  经过分解后的函数可以用另一幅图来表示，横坐标为各个分量的频率（不断递增的整数），纵坐标为对应振幅。即图中，侧面观看到的$S(f)$。也就是说，频域图中每个点(频率，振幅) 对应的就是一个正弦函数中的频率和振幅参数。所有正弦函数的频率和振幅参数点组成整幅频域图。

• 理解二：将周期函数转化为一组正交基下的坐标表示
  描述向量的时候，都有对应的基，即在某组基下的坐标表示构成了向量。默认是单位基时，则不显式提到。
  某个周期函数是在正弦函数系作为正交基下的傅里叶级数向量。给定周期函数T，频率图中的横坐标频率值所代表的三角函数就是傅里叶级数的正交基，即$(1, \cos{\frac{(2{\pi}n)}{T}}, \sin{\frac{(2{\pi}{n})}{T}} )$，而其系数$(\frac{a_0}{2}, a_n, b_n)$构成的向量就是傅里叶级数。

傅里叶变换(Fourier Transformation)

理解傅里叶变换

傅里叶变换可以从多种角度进行表述。
从数学角度，傅立叶变换就是将周期函数转化为一组正交基下的坐标表示，这个坐标表示就是傅立叶变换的结果。换句话说，周期函数是这些正交基的线性组合（向量的叠加），线性组合系数构成的向量就是傅立叶变换的结果。
从信号处理领域角度，傅里叶变换将一个周期函数从时域（时间与振幅的关系）转化为频域（频率与振幅的关系）。做个类比，正交基选择的是正弦函数，每个正弦函数有个频率参数值，而每个正弦函数的振幅参数就是该基下对应的坐标值。所有正弦函数的振幅构成的向量就是傅立叶变换的结果。

函数理解为向量（无穷维的）
如果一个空间有一组基两两正交，那么它就叫做一组正交基。
傅里叶级数是用三角函数作为基函数的。

傅里叶级数实际上就是把这个空间中的一个向量（函数）通过基的线性组合的方式写出来。
（唯一性=>正交性，线性无关（不平行）=>正交（垂直），基=>正交基）
正交 和别人是0 要求的系数只需要$f(t)$和自己做内积（复数的话是共轭做内积）

正交空间（酉空间）的坐标变换

傅里叶变换只是推广成了积分
$$f(t)\ =\ \frac{1}{2\pi}\int{-\infty}^{\infty}{\int^{\infty}{\infty}f(t)e^{-i{\omega}t}\mathrm{d}te^{i{\omega}t}\mathrm{d}{\omega}}$$

$$F(\omega) \ = \ \int^{\infty}_{\infty}f(t)e^{-i{\omega}t}\mathrm{d}t$$
$\omega$取遍整个频域的横坐标，但仍然是基，在这个基上的取值是$F(\omega)$

e^(jwt) 在复平面中，可以作为一个“基”，因为它已经包含了实轴（实数单位“1”）上和虚轴（虚数单位“j”）上两个正交的“基”。

我们说正弦波是正交的，意思是e^(jwt) e^(-jw’t)积分后是delta函数，w’=w时为无穷大，否则为0。

https://www.zhihu.com/question/19714540

三角函数的定义就是通过指数函数的
https://www.zhihu.com/question/26135850/answer/32260694

Laplacian Matrix

拉普拉斯算子(Laplacian Operator)

拉普拉斯矩阵(Laplacian Matrix)

拉普拉斯矩阵的特征分解

拉普拉斯矩阵是半正定对称矩阵，因此其特征值均非负，且特征向量互相正交，构成正交矩阵U

e^-iwt是拉普拉斯算子的特征函数，频率\omega和特征值有关 ？因还是果 是因为傅里叶变换eiwt所以图上推广拉普拉斯算子 拉普拉斯矩阵的特征向量 还是因为拉普拉斯算子所以eiwt，【看看？拉普拉斯变换】

拉普拉斯矩阵的特征向量

现在有一个f，f与图的顶点一一对应，

Graph Fourier Transformation

Graph Convolution

GCN

GraphSAGE

References

• 如何理解 Graph Convolutional Network（GCN）？ - superbrother的回答 - 知乎
• 如何理解 Graph Convolutional Network（GCN）？ - Johnny Richards的回答 - 知乎
• Graph Convolutional Networks @xuetf
• Graph Neural Network: A Review of Methods and Application
• 【谜之舒适】12分钟的傅立叶级数动画 UP主：3Blue1Brown