Something About Graph

符号

**

• 表示一个图， 分别表示相应的节点集与边集， 表示图中的节点， 表示图中的边。
• 表示图的邻接矩阵（adjacency matrix）。
• 表示图的度矩阵（degree matrix）。
• 表示图的拉普拉斯矩阵（Laplacian matrix）， 表示图的归一化拉普拉斯矩阵。

定义

**

邻接矩阵

**
图的邻接矩阵指用于表示图中节点的连接情况的矩阵。该矩阵可以是二值的，也可以是带权的。对于有N个节点的无向图来说，邻接矩阵是一个 的实对称矩阵。

度矩阵

**
节点的度表示与该节点相连的边的数量。图的度矩阵即用于描述图中每个节点的度的矩阵，一般使用 表示。其中， 表示节点 的度。度矩阵是一个对角矩阵，对于无向图来说，一般只使用入度矩阵或出度矩阵。

拉普拉斯矩阵

**
定义矩阵 ，其元素为：

其中， 表示节点 的度，则该矩阵称之为图 的拉普拉斯矩阵（ ）。相应的归一化拉普拉斯矩阵为：

因此，图的归一化拉普拉斯矩阵可以通过下式计算：

图的拉普拉斯矩阵也可以称为导纳矩阵（admittance matrix）或基尔霍夫矩阵（Kirchohoff matrix）。

GCN

现实世界许多数据都是以graph的形式存储的，比如social networks(社交网络),knowledge graphs(知识图谱),最近有一些研究者把目光投向建立一种通用的神经网络模型处理graph数据。

图上的卷积网络从卷积方式上可以分为两种：

1. 谱（spectral）卷积，谱卷积将卷积网络的滤波器与图信号同时搬移到傅里叶域以后进行处理。
2. 空间域卷积, 空间域的卷积，让图中的节点在空间域中相连、达成层级结构，进而进行卷积。

由于大家的思想普遍是如何将CNN等神经网络的思想迁移到graph上，所以往往设计出来的结构都有一定的共性，使用类似convolution权重共享的思想，我们可以把这类网络暂且称为Graph Convolutional Networks(GCNs)。这类网络从数学上来看，是想学习G=(V,E)上的一个函数，该函数的输入是：

• 每一个节点的特征表示,如果节点数为N，特征维度为D维，则所有节点的特征组成一个的矩阵
  
• 图结构的表达，往往使用图的邻接矩阵A表示

该函数产生一个node-level的输出Z（是一个的矩阵，N代表点数量，每一行代表一个节点，F代表节点特征向量的维度）。如果想要得到graph-level的特征表达，只需要将每一个node的表达综合起来再经过一个映射操作即可。

GCN模型同样具备深度学习的三种性质：

1. 层级结构（特征一层一层抽取，一层比一层更抽象，更高级）
2. 非线性变换（增加模型的表达能力）

3. 端对端训练（不需要再去定义任何规则，只需给图的节点一个标记，让模型自己学习，融合特征信息和结构信息）

   
   GCN四个特征：

4. GCN是对卷积神经网络在graph domain上的自然推广。
   

5. 它能同时对节点特征信息与结构信息进行端对端学习，是目前对图数据学习任务的最佳选择。
   
6. 图卷积适用性极广，适用于任何拓扑结构的节点与图。
   
7. 在节点分类与边预测等任务上，在公开数据集上效果远远优于其他方法。
   

参考链接

• 《Semi-Supervised Classification with Graph Convolutional Networks》阅读笔记 - 孙建东的文章 - 知乎 https://zhuanlan.zhihu.com/p/31067515