Survey

Preliminary

Graph 的一些基础知识

Graph=G{V,E}
Indirected Graph
Degree(度) - 与某个Node相连的所有E的数目
- 对于有向图，还有入度(In-Degree)和出度
Adjacency Matrix 邻接矩阵
- 对于无向图来说，是个对称阵
Edge Attribute (边的信息)
- Weight – 表示连接的强弱(Frequency of Communication)
- Ranking – (1st Best Friend, 2nd Best…)
- Type
- Sign (Friend/Non-Friend)

Graph Representative Learning

图表示学习，完成的步骤是将一个离散的图做一个Encode，映射到一个连续的空间
- 离散 - 连续；高维 - 低维
主要Flow
- 定义Encoder
- 完成一个相似性度量的函数(Metric)
- Optimize the Encoder
Naive Encoder - Shallow
- 直接对输入Feature乘上一个EmeddingMat
Naive Similarity Function Example
1. 将Loss定为Embedding的乘积-AdjMat
  - 本质上就是将Embedding做一个AdjMat的软化近似
  - （问题在于只用到了直接相连的信息）
2. RandomWalk
  - Similarity Function是一个概率，节点u在节点v的随机游走中出现的概率
  - 本质上是一个Monte Carlo
  - Loss的目的是让Embedding的概率与实际随机游走采样得到的概率相接近
  - 随机游走的策略：两个极端是BFS和DFS，在其中取一个出入参数:以q概率转移到下一级节点

GNN

直接的Shallow Encoder存在很多问题
1. GCN
  - Neighbourhood Aggregation
1. GraphSage
  - 全称是Graph Sampling and Aggregation，是一个系统级
  - 对于Aggregator给出了多种方案
    - Mean
    - Pool
    - LSTM：各个邻居在不同TimeStep以LSTM输入的形式输入(由于LSTM是输入敏感的，所以需要对输入做一个Permute)
1. Graph Attention Network
  - 应对传统GCN中每个Node公用一组Weight
  - 针对不同的Node采用不同的Attention系数
1. Gated Graph Network
  - 对一般GCN，跨层的每个W的地方用一个LSTM代替

Thinking

私以为,在目前这个阶段,对于一个领域的了解,可以先多看一些理解性的东西而不是数学推导~~其实就是怕数学推导~~,先有一个概念性的认知比较重要这一段话等待后期去打脸… （2019-09-07）要理解这些方法在做什么和算法原理，至少得看懂公式在描述什么样的计算 (2020-04-14)

传统NN经典结构的成功点就在于去适应某种数据结构
- CNN - 图像(2D) - 卷积核Kernel,小窗口的结构,实现参数共享
- RNN - 时间序列(1D) - 通过各种门的结构,让序列的前后互相影响以提取时间序列的信息
  
  以上两种结构本质上还是属于欧式空间,有”维度”的概念,但是图却没有,可以认为是无限维的,没有平移不变性
图是一种很灵活多变的结构
- 如果没有边，就会退化为集合
- 如果只有垂直的边，就会变成树
与NN的联系：
- 大部分的数据可以被看做“图”
  
  对于二维图像，不从像素入手，而是将图看做一种“超像素”
- 还可以反映一些一些先验知识：
  - 比如：人的姿态估计，面部识别
- NN本身也可以看做是一张图（计算图）
- 很多Task先天的类似图：
  - 知识图谱；动态对象的交互，问答，3D Mesh分类（图可以描述一个球面上的形状）

CONV IN GNN

WHY CONV?

也就是conv相对于fc的优点，会带来一些自然的优势
1. 平移不变性
2. 局部性
3. 层次结构（浅层低级纹理特征，深度高级特征）
  
  这些属性对于设计GNN有启发意义
  
  An Exmaple To Analog NN to GNN
图像描述
- 对于mnist的图像，用24*24=784个像素来描述，对应地采用784个节点(Node)来描述
- 对于位置比较近的像素，边(Edge)有一个相对比较大的值
计算描述
- 将卷积抽象为了一种“滤波器”，也就是“聚合算子”
- CNN和GNN的区别主要在卷积是对顺序敏感的，而图是无序的
- 对于GNN我们也需要定义“聚合算子”得到一个好的聚合器
  - 平均值
  - 求和（都是以某个节点为中心，对相连的节点相加之后乘上W（W-是一个可训练的Tensor））
  - 人们管这种方式叫做GNN中的“卷积”，但是严格来说并不是卷积，因为他没有方向性，主要利用了卷积中局部性的特点
    A CASE：
GNN的核心思想是聚合“邻值”（而一般什么样的值为邻近值由您定义）
- 个人理解：可以抽象为是很多的，布朗运动的混乱的粒子，邻近的粒子相聚合，聚合成一个图像的形状，GNN就是建模这样一个过程
借助邻接矩阵 -（NN（784784）的邻接矩阵，描述每个节点对之间的距离）
- 是一种距离建模体现了“相近的像素比较容易组成图案，而比较远的不大可能”这样的先验知识
- 这样的抽象过于Naive，而且图像本也不是图网络最好的用武之地，单纯利用这样的方式并不太能获得有效的分类
由于图具有无序性，所以我们给这784如何排序其实是不对的，不可能找到一个正确的排序
- 需要假定像素被随机调整位置
- 新的问题❓: 如何知道在哪一行放置对应节点的特征？
  - 如果忽略的话，训练出来的结果相当于随机打乱
  - Solution： X_l+1 = A * X_l * W只要保证A中第一行对应着X中第一行的特征就可以

Reading List

Refer To This Log
1. Naive GNN(Ancent time)
😟 只是单纯的把Graph通过一个Embedding映射到一个Vector Representation而已
- Graph层的传递，X' = A*X*W 比传统NN多一个adjacent matrix
  2. Spectral Graph Convolution
Core Math
V 是由图的拉普拉斯矩阵L经过SVD得到的特征值矩阵
- L = D(Degree Matrix) - A(Adjacent Matrix)
- 做了Laplace Matrix对称而且归一化的假设，因而可以直接从Adjacent Matrix得到
W是Filter
- W的维度依赖于：前一步Embedding Node的个数
- 需要避免太大: This Paper
  - 提出了采用平滑滤波器，来获得Local的表示 “Smooth Version Of Spectral Conv” （不是去学W中的N个参数，而是学k个参数(k « N),而fk是几个固定函数）
    3. Chebyshev Graph Conv
上面方法的缺陷在于，一个N*N的奇异值分解，需要很大的计算，存储Laplace矩阵也需要很大的RAM；而且过分依赖于奇异值，缺乏一些泛化

4. GCN

\[H^{l+1}=\sigma(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^lW^l)\] \[(\hat{A} = A+I )\] \[(\hat{D} - A's\ Degree\ Matrix\quad \hat{D}_{ii} = \sum{j\hat{A}_{ij}})\] \[(H - Output\ Of\ Each\ Layer)\] \[(\sigma - The\ Non-Linear\ Activation\ Function)\]

* N - Node
* D - Num Of Features Of Every Node
* X = D*N 每个节点和他的特征
* A = N*N 图的邻接矩阵(Adjaceny Matrix) * 各层之间的Node的链接关系 (A) 是共享的 * 每一层的输入都是邻接矩阵Ａ(经过了Ｄ做了处理的 why this? - 🤔可能和图的一些性质有关，这样好像是一种比较好的对图的特征提取方式，就类似用卷积核卷图像一样) * 为什么要给Ａ加一个Ｉ   * 因为邻接矩阵本身在对角线上都是０,直接乘会损失与自己本身有关的信息   * 由于Ａ是一个没有归一化的矩阵，与特征矩阵Ｈ（也就是每一层的输出）相乘会改变分布，所以两个$$D^{-\frac{1}{2}}$$本质上做的是标准化   * $$D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$$与归一化的Laplace Matrix十分类似,而谱卷积(Spectral Conv)的核心就是L-Matrix,因而得名GCN * 即使用完全随机化的参数W,提取出来的特征就已经非常有效了   * why? 🤔我寻思是因为图这种数据结构本来就比时间序列和图片要Elegant
* 有研究认为*拓扑关联*是一种更加广义的联系

Thoughts 🤔🤔🤔

Graph的本质，可以被认为是: 每一个节点无时无刻不因为其邻居和更远的点而改变自己的状态直到平衡
- 可以类比为一个电荷系或者是质点系，各个点有着自己的属性（q或者m），之间又互相作用（库仑力，万有引力）保持一个平衡，但是互相作用和本身的属性都要复杂许多。各种算法的本质就是对这一类问题进行建模（就好比发掘出库仑力公式一样）
Example 传热
- 一个1-D的例子：热传播：一个连续的铁棒传热（T温度对t和x是一个微分方程的关系）
  - 离散化之后，变为一个铁链,传热方程为：差分的差分，就是二阶导数（Laplace算子）
\[\frac{d\phi}{dt} = K(\phi_{i+1}-\phi_i) - k(\phi_i-\phi_{i-1}) -> \frac{\partial\phi}{\partial t} - k\Delta\phi=0\]
- 以上是在欧式空间，考虑在Graph上，也就是在拓扑空间上。只有直接连接的节点有直接的传热,可以推导得到和上面类似的微分方程（两者形式一样）
- 都描述了单位时间状态的变化等于将Laplace算子作用在状态上是同一种变换在不同空间中的体现
  - Laplace变换矩阵 = D(度矩阵Degree Matrix) - A(邻接矩阵 Adjacent Matrix)
- 实际我们GCN中，不是热量流动，而是特征和状态在不同的Node之间流动
- 我们的算法需要完成的其实就是一个传热过程的建模，不过实际问题当中不是服从简单的导数，而是更加非线性且高维的分布

CS224W

做Node(Graph) Embedding: 输入一张图，输出是一个2D embedding，让更接近的Node更加接近 - 需要学习这样的一个embedding
- 那么就需要定义一个相似性函数（定义节点之间的相似性），以及一个encoder（把高维度图映射到k维的）
- 一般的similarity function就是embedding的dot product
- （这样就相当于是个shallow的embedding）
  - node之间没有share parameter
  - 每个embedding有独立的
  - 不能把node的feature(property) incorporate进来
- 将一个单层的encoder换成一个多层非线性Transform
Image看作一个lattice形式的数据
- 卷积操作的核心是transform领域之间的信息并且将其组合
最Naive的操作方法，把邻接矩阵和feature，expand起来
- 问题在于对node order敏感，以及对不同size的图
V是vertex set，A是adjacent matrix，X(m*V) node feature
GCN的idea，node neighbour define compute graph，需要propogate information through graph
- 这样第k层就是k度链接
- 是在做一个neighbor aggregation的过程
- W(所有neighbor的上一层embedding平均)+b(当前vertex的上层embedding)
GCN的Loss Function设计
- Unsupervised形式 - （这样只利用了graph的结构）
  - RandomWalk Loss(Node2Vec, DeepWalk,Struc2Vec)
- Supervised形式 - 直接面向一个具体task

图神经网络

Elegant Structure

Survey

Preliminary

Graph Representative Learning

GNN

Thinking

CONV IN GNN

WHY CONV?

An Exmaple To Analog NN to GNN

A CASE：

Reading List

1. Naive GNN(Ancent time)

2. Spectral Graph Convolution

3. Chebyshev Graph Conv

4. GCN

Thoughts 🤔🤔🤔

CS224W

Ref

CATALOG

FEATURED TAGS

FRIENDS