本篇为最近看的两篇1,2 GNN Introduction 的笔记。

Challenges

  1. 机器学习的输入通常为网格状数组，即矩阵。而图（Graph not Image）的信息比较复杂，结点、边、全局信息、连通性这些难以表达。
  2. 排列不变性（Node-Order Equivariance）。通过置换同一个图的的结点顺序会得到不同的邻接矩阵，这显然是不符合排列不变性的要求的。
  3. 扩展性（Scalability）。不同图的量级相差极大，简单如无机分子图，只有几个原子结点；复杂的如社交网络图，可能拥有超过十亿的用户结点。

What

步骤

  1. 聚合邻居特征
  2. 与自身特征结合

本质上，消息传递和卷积都是通过聚合和处理元素邻居的信息来更新元素值的操作。说人话就是图中结点是根据与它有边相连的结点的信息来更新的。根据结点、边之间的交互总共有四种消息传递方式，主要是结点-结点的方式。消息传递方式有个缺陷：距离远的结点之间无法交流信息，解决方案

  1. 全部结点间可以交流信息（注意力机制），但是计算量大。
  2. 使用全图表示，添加一个连接所有结点的虚拟结点。

Performance

如何获得更好的性能

  1. 参数量，一般来说正相关
  2. embedding dim，维度越高，平均性能越高，偏差越小
  3. layers，深度越深，平均越好，但也可能会有所下降
  4. 聚合函数，影响不大？
  5. 消息传递方式，边、结点、全局信息

Where

背景及起源

ChebNet

Improve

改进方向

  1. 更复杂的图算法，之前的都是基于邻域的pooling操作，很多图的概念无法表达，比如路径。
  2. 图本身，更好的去表示图，利用更多的结构和关系。

sample

图采样，图中不同结点的边数量会变，整张图做一个batch可能会导致内存不足，如何得到图的batch是一个难点。

一个解决方案：subgraph，随机选一个结点，扩展到它的k阶邻居，选取一个固定大小的node set。

Others

一些其他概念

Inductive bias

先验知识，对特定的图，可以利用一些辅助信息提高性能

Aggregation

  1. mean：邻居偏差大或者需要标准化特征
  2. max：需要显著特征
  3. sum：前两者一个平衡

经过K层后，一个结点的表示可以看作一个k阶邻居构成的子图表示，但是直接列举这些子图代价昂贵。

图上的卷积操作可以用邻接矩阵和特征矩阵的相乘实现

Graph Dual

图上的边看成结点，结点看成边，则可以把一个边预测问题转变为结点预测问题。

Generative model

生成新图，比如制药中找新的药物分子图。图变分自编码器。

Spectral

谱表示可以保存大部分特征，即可以用较少的参数量得到相当的性能。

  • 较小特征值对应的特征向量对应于低频分量，偏向全局表征，越smooth
  • 较大特征值对应的特征向量对应与高频分量，偏向局部表征

图（graph）上的谱域卷积可以看作image上频域卷积的泛化

缺点：

  • 需要计算特征向量U，时间复杂度较高
  • 有重复的U和U’相乘计算
  • 只针对某个图，换个图拉普拉斯矩阵不一样

参考