1. 简介
- 表示学习 / Graph Embedding / 特征学习：把图、节点或边映射（投影）到k维隐空间，用该向量来表示原物。
节点域/空间域
表示向量
表示学习的目标：相似节点的表示向量相似
衡量节点的相似：连通性（离得近）、结构相似性
2.Why networks?→因为关系是有用的
3.graph上有监督机器学习的流程图
4.机器学习在graph上的经典任务：
- node classification节点分类 eg：识别电信诈骗用户
- link prediction eg：打电话预测关系；电商异构网络（购买行为）
- community detection社区发现
以上三种的标签/label在节点和边上
4.graph classification eg：预测化学分子毒性
GNN主要要解决node classification和graph classification
node classification和link prediction的模型结构会和graph classification有差异
5.graph在深度学习上会遇到问题的原因（相比可以用CNN的image等欧式数据）
- Arbitrary neighbor size
- Complex topological structure
- No fixed node ordering
2. 数学与数据结构基础
本课程仅涉及无向图，且边的权非负
2.1 线性代数部分
- 当B = M − 1 AM时，我们说matrix B is similar to matrix A，且此时A和B有相同的特征值
2.2 graph基础部分
- 图G，节点集合V，节点数|V|，边集合E
- 节点上面存在信号，用以表示节点信息（可以是标量或向量。特征、表示向量可以当作信号）
- 整个图的信号构成feature matrix
- 邻接矩阵Adjency matrix（01矩阵，或者可以带权）：对称的
- 度矩阵Degree Matrix：对角矩阵，Djj是j位置节点的度数（边权和）
- 拉普拉斯矩阵Laplacian Matrix：L = D − A
- Normalized graph Laplacian L = I − D − 1/2 A D − 1/2
（对为什么要用正则化的拉普拉斯矩阵的诠释见后文GCN部分，大致来说就是加了个权）
- L是描述图中节点信号的差分运算difference operator→对整个图进行一阶导数
- 拉普拉斯矩阵的特性
- 对称的
2.半正定的
3.特征值非负
证明半正定矩阵特征值非负：
以下完整的证明链：
证明n阶矩阵一定有n个特征值：d e t ( A − λ 1 I ) = 0 左边是个n次多项式，必有n个解证明实对称矩阵的特征值都是实数（似乎是同济的证法）：（共轭是虚数取反）
证明实对称矩阵可对角化（没完全看懂，但是我寻思应该差不多就是这么回事儿）
另有一个很全面的也是按照这个顺序来的博文实对称矩阵一定可以对角化，另证明了实对称矩阵属于不同特征值的特征向量正交。这篇博文最后证明也用的是数学归纳法，还是有点没看懂。
（以下这些未标明来源的图片都截图自该博文）
证明实对称矩阵属于不同特征值的特征向量正交：
证明实对称矩阵一定可以对角化：
总之可以用数学归纳法证明，具体怎么搞等我学好矩阵论再回来研究吧。
参考证明半正定矩阵特征值非负这一百度知道回答：
- 紫色部分为参考拉普拉斯矩阵的性质一文做的补充（本文还有一个L的零特征值的重数等于图连通子图的个数这一特性，此外对归一化拉普拉斯矩阵用途也做了似乎更多的数学证明。未作了解）：
①L的行和为0
②L的一个特征值为0
- 有N个正交特征向量，构成N维空间
- 可以特征分解
3. Graph Filtering卷积
1.卷积是一个定义在两个函数（如f和g）上的运算
n是常量，τ是自变量，f 和g 的变量和是常量
例子1：（翻转相乘）
例子2：同时丢2个骰子，求和为4的概率（关于n=4的卷积）
例子3：image上的卷积——卷积后每个位置的结果是九宫格的加权平均
卷积核g
原始信号f
卷积在数学上是一个信号处理过程（滤波器、对信号进行平滑的过程）
5.CNN
(1)学到局部patterns（通过局部的卷积操作localized convolution filter进行学习，将卷积结果进行层级堆叠，把学到的信息变成一个层次化的多尺度的信息multi-scale hierarchical patterns）
(2)共享参数
欧式数据和非欧数据对比：
欧式数据：平移不变性
非欧数据无法直接用CNN的原因：
(1) 没有平移不变性（图上节点没有固定的顺序，更改顺序后邻接矩阵也会剧变）
(2) 邻居数不一样导致需要不同的卷积核，不能共享参数，因此没法用CNN
6.谱方法Spectral Methods：图映射到谱域卷积，再映射回来
空间方法Spatial Methods：在原空间域上定义卷积操作
7.历史发展：谱方法→空间方法
GNN的本质是对图信号进行处理，尝试作卷积
8.卷积/滤波：学出节点的表示
9.General GNN Framework
1.For node-level tasks
2.For graph-level tasks
3.1 Spectral-based Graph Neural Networks (GNN)
1.信号处理领域：将时域信号投影到频域上，方式是傅里叶变换（后续内容仅借鉴其物理意义，所以我还没搞懂这是个什么玩意）
泰勒展开：用多个简单函数的和来近似复杂函数
将一个时空域的信号拆分成若干个正弦函数的线性组合
频域空间是由这些正弦函数构成的基向量，信号投影后的坐标就由这些基向量表示（可参考我之前写的线性代数的本质笔记中 第11章：抽象向量空间 部分理解）
傅里叶变换的示意图：（大概就是把一个波拆成很多个正弦/余弦波）
2.时域：自变量是时间
频域：自变量是波动的频率
空间域：自变量是位置、坐标……
节点域：描述图像时，自变量是节点
3.低频信号、高频信号（image上变化大或小的部分）
4.Discrete Time Fourier Basis
5.泰勒展开
6.在图上定义傅里叶变换Graph Fourier Transform
以拉普拉斯矩阵的n个正交特征向量所张成的空间作为投影到的新空间（Spectral Space）。将这些向量组合，按其对应特征值大小排序，得到矩阵U 。
（此图中间的U T 应当为U ）
3.拉普拉斯矩阵特征值代表了图信号的变化频率。特征值越小，表示信号变化越平缓（频率低）
拉普拉斯矩阵特征向量（基向量）表征了图信号的变化过程
7.卷积定理：2个信号的卷积等于这2个信号傅里叶变换后的点积
逻辑就是先投影到谱域，点积，再投影回来
8.g ：空间域上的卷积核 → 反正卷积也是在谱域上做的，不如直接把( U T g ) 整体视作卷积核（谱域上的卷积核）
在图上做卷积：
Drawbacks of SCNN
- Requiring eigen-decomposition of Laplacian matrix
Eigenvectors are explictly used in convolution
2.High computational cost
Multiplication with graph Fourier basis U is O ( n 2 ) （这个U 大概率不稀疏）
3.Not localized in vertex domain：因为G θ 是free的
3.2 Spatial-based GNN
1.General Idea: Aggregating neighbor information
这样聚合后，点本身会失去自己的信息（除非有自环）；度数高的节点会获得过高的信号绝对值（会造成梯度爆炸或梯度消失）；同时这也没有卷积了
3.GCN: Graph Convolution Network（ChebyNet的简化：约束K（0或1））
renormalization trick: 加自环（否则会节点迷失自我）
用归一化后的拉普拉斯矩阵原因：用拉普拉斯矩阵会变成邻居信号和，用归一化后的拉普拉斯矩阵会变成加权平均
4.GCN已经没有卷积了
这里面没有卷积核了，W WW是对节点特征用linear function做一个变化（feature transformation），W WW是linear function的一个参数
5.GCN的目标函数是cross entropy
6.在实验上，GCN比ChebyNet表现更好（尤其在节点分类问题上），原因：
7.GCN缺点
- GCN只能做transdutive learning（训练时需要看到包括测试集的全部数据）
Inductive learning
- GCN不支持mini-batch
- GCN没有卷积了
8.将CNN普适到图上：
（第一步受无平移不变性的影响）
确定一个数，找图上点最像的这么多个点作为邻居（sample一个子图来），这样邻居数量就能确定了。
9.GraphSAGE
约束这个邻域一定是一度邻居或二度邻居，走random walk采样获得节点作为邻域
10.GAT Graph Attention Network：主要改进GCN没有卷积的问题（GCN这样的缺点是没权了）
用attention机制来量化点的相似性（用这个来加权）
attention matrix就是卷积核
3.3 Spectral Methods vs. Spatial Methods
- 频域方法是空间域方法的一个子集
- 如果显式定义卷积核，就是频域方法（知道投影到了一个什么空间）
4. Graph Pooling池化
- 学出图的表示
2.Graph Coarsening图粗化
- 节点聚类，聚成一个supernode→卷积→Pooling→直到只剩下1个节点⇒ \Rightarrow⇒这就是整个图的表示
- 聚类可以GNN前做，也可以边GNN边做
- DiffPool
3.Node Selection节点选择
选出一部分有代表性的节点
5. 除本课程外上文未提及的参考资料来源
- 建议学习：线性代数，图谱论，信号处理。课程中提及的模型的原论文
- 矩阵的特征分解
