图机器学习简介

图机器学习（GraphML）使得对以关系链接的项目结构化的数据进行分析成为可能，能够在图、节点、边和子图层面进行预测。该领域对从药物发现和分子毒性预测到社交网络社区检测以及行程系统中的交通估计等各种应用至关重要。

基本图概念

图由节点（或顶点）和边（或链接）组成。根据数据的性质，图可按以下几个特征进行分类：

  • 同质 vs. 异质：同质图仅包含单一类型的节点和边。异质图具有类型化的节点或边（例如，包含作者和论文的引用网络），需要除拓扑之外的额外信息来表示。
  • 有向 vs. 无向：有向图（例如，关注者网络）中的边具有特定方向，而无向图（例如，分子）则具有双向关系。
  • 表示方式：图通常以边集合或邻接矩阵的形式表示，邻接矩阵是一个方阵，其中值为 1 表示两个节点之间存在连接。

关键在于，图不同于序列（文本/音频）或网格（图像），因为它们不是有序的对象。对边列表或邻接矩阵的列进行洗牌并不会改变底层图结构，这一特性称为置换不变性。

图学习任务

图上的机器学习应用于四个主要的粒度层级：

  • 图层级：包括图生成（例如用于药物发现）、图演化预测（例如在物理学中）以及图层级预测（例如预测分子毒性）。
  • 节点层级：关注节点属性预测，例如 AlphaFold 利用节点属性预测分子中原子的三维坐标。
  • 边层级：涉及边属性预测（例如药物副作用预测）或缺失边预测（例如推荐系统）。
  • 子图层级：关注社交网络中的社区检测或子图属性预测，例如在 Google Maps 等系统中估计到达时间。

这些任务可以在传导式（在单个图上进行训练和测试）或归纳式（使用不同的图进行训练、验证和测试）设置下完成。

图表示的演进

神经网络前的方法

在神经网络出现之前，图表示依赖于人工特征：

  • 节点级特征：中心性（重要性）、度（邻居数量）和聚类系数（邻居连通性）。
  • 边级特征：节点之间的最短距离、共同邻居以及 Katz 指数（在一定长度内的步数）。
  • 图级特征：整体图子结构计数以及通过“节点袋”方法衡量相似性的核方法。

基于游走的方法，如 Node2Vec，使用随机游走来定义相似度度量，并通过 skip-gram 模型计算嵌入。然而，这些方法无法为新节点生成嵌入，且未能捕捉细粒度的结构相似性或利用额外的节点特征。

图神经网络（GNN）

为了对未见数据进行泛化，GNN 被设计为置换不变（无论节点顺序如何，输出相同）和置换等变（节点置换会导致其表示相应置换）。

GNN 层通过信息传递和聚合来工作：节点的表示通过聚合其邻居以及自身在前一层的表示来更新。

值得注意的 GNN 架构包括：

  • 图卷积网络（GCNs）：对邻居的归一化表示取平均。
  • 图注意力网络（GATs）：使用注意力机制根据重要性加权邻居。
  • GraphSAGE：在不同跳数采样邻居，并使用最大池化聚合信息。
  • 图同构网络（GINs）：对邻居表示的求和应用 MLP。

过平滑问题

随着 GNN 层数的增加，每个节点的表示会聚合更大范围的信息。如果层数超过图的直径，节点表示可能会收敛到相同的值，这种现象称为过平滑。可以通过限制层深度、增加层的复杂度、添加非信息传递层（如 MLP）或实现跳连来缓解。

图 Transformer

由于 Transformer 天然具备置换不变性且可有效扩展，它们正被用于图上，以克服 GNN 的过平滑等限制并适应稠密图。关键进展包括：

  • Graphormer：在注意力机制中使用节点特征作为查询/键/值，并结合中心性、空间和边编码。
  • TokenGT：将图表示为带有标识符的节点和边嵌入序列，省去位置嵌入的需求。
  • GraphGPS：一个将信息传递网络与线性长程 Transformer 结合的框架，以构建混合网络。
  • 谱注意力网络（SANs）：将节点特征与基于拉普拉斯特征向量/特征值学习的位置信息相结合。

其他值得注意的方法包括用于图到序列学习的 Graph Encoder 以及 GRPE（图相对位置编码）Transformer。

Sources