我们将要探索的

• 节点嵌入方法: DeepWalk, Node2Vec
• 图神经网络: GCN, GraphSAGE, GAT…
• 图变换器
• 知识图谱与推理: TransE, BetaE
• 图生成模型: GraphRNN
• 三维图: 分子结构
• 大规模图处理
• 在生物医药、科学、技术领域的应用

我们经常遇到的

一个典型例子就是异构图。
异构图定义为:
G = (V, E, R, T)

其中:

• 节点及节点类型 vi ∈ V
• 带关系类型的边 (vi, r, vj) ∈ E
• 节点类型映射函数 T(vi)
• 关系类型 r ∈ R
• 节点和边都可以具有属性/特征

简单的说，异构图是节点类型不同或关系类型不同的图。而这种结构在现实世界中非常常见,例如:

• 社交网络中的用户、帖子、评论等不同类型的节点
• 知识图谱中的实体和关系
• 推荐系统中的用户、物品、类别等多种节点类型
  

选择合适的图表示方法

选择一个合适的图表示方法决定着我们是否能够顺利使用网络，如果不能很好的表示出其原本具有的信息，那对其相关的训练也会产生误差。

无向图 vs 有向图

顾名思义，无向图的边没有方向，而有向图的边有方向。

二分图

二分图是一种特殊的图结构，其节点可以被分为两个不相交的集合U和V，使得每条边都连接U中的一个节点到V中的一个节点。也就是说，U和V是独立的集合。

举个例子有:

• 作者-论文关系(作者撰写的论文)
• 演员-电影关系(演员出演的电影)
• 用户-电影关系(用户评分的电影)
• 食谱-配料关系(食谱包含的配料)
• “折叠”网络:
  • 作者合作网络
  • 电影共同评分网络

Graph ML(图机器学习)的应用

我们有三种不同种类的任务，包括节点级别的分类、边级别的分类、图级别的分类。

节点预测

如果给你如左图所示的图，你应该如何知道灰色节点的颜色？

这正是我们节点预测要做的。具体方法我们在后文会进行分析。
期不期待！

节点级网络结构

在开始进行节点分类等任务之前,我们得先搞清楚节点在网络中的”身份特征”。就像认识一个人要从多个角度了解一样,我们也需要从三个维度来认识节点:

1. 节点度(Node degree)

   • 简单来说就是看这个节点有多少”朋友”
   • 这是最基础但也是最重要的特征哦

2. 节点重要性与位置(Node importance & position)

   • 通过数最短路径来看节点的”地位”
   • 看看它离其他节点有多远
   • 这就像在社交网络中,有些人总是消息灵通,因为他们处在”中心位置”

3. 节点周围的子结构(Substructures)

   • 观察节点周围的”朋友圈”是什么样的
   • 这能告诉我们很多关于节点角色的信息

Graphlets(图形子结构)

说完了基本的节点特征,我们来看一个更有趣的概念 - Graphlets! 它可以帮我们更细致地描述节点周围的”朋友圈”结构。

那么什么是Graphlets呢？简单来说,它就是统计以某个节点为”根”的各种子图数量。这些子图的形状是固定的,我们把每种形状的出现次数都数出来,最后得到一个计数向量。
听起来有点抽象?别急,看例子就明白了!

让我们一起看这个例子:

1. 首先,右边展示了所有可能的3节点以内的graphlet类型(a,b,c)
2. 左边是一个具体的图G,我们要分析红色节点u
3. 下面就是我们找到的所有以u为根的graphlet实例

最后我们得到一个向量[2,1,0,2],这个向量就描述了节点u周围的”朋友圈”结构特征。是不是感觉Graphlets其实就像是在数”朋友圈”里有多少种不同的小团体呢？

向量[2,1,0,2]如何得到？:

• 2个a节点类似
• 1个b节点类似
• 0个c节点类似
• 2个d节点类似

当然会有人好奇为什么c不是，不是也有三角形吗？但是我们的要求是很严格的，c要求G邻居两个节点不能相连，显然不符合要求。

几个例子

蛋白质折叠预测

在生物学研究中,预测蛋白质的3D结构是一个重要且具有挑战性的问题。我们可以把蛋白质看作一个图结构:

1. 节点表示氨基酸

   • 每个氨基酸都有其特定的性质
   • 它们的空间位置决定了蛋白质的功能

2. 边表示氨基酸之间的相互作用

   • 可以是化学键
   • 也可以是空间上的近邻关系

通过图机器学习方法,我们可以:

• 预测每个节点(氨基酸)的3D坐标
• 考虑节点之间的关系和整体结构
• 最终得到蛋白质的完整3D构型

就像上图展示的那样,通过这种方法,我们可以仅仅基于氨基酸序列就可以预测出蛋白质的3D结构。

药物研发

在药物研发领域,图机器学习也发挥着重要作用。我们可以将分子结构表示为图:

1. 节点表示原子

   • 不同类型的原子有不同的化学性质
   • 原子的排列方式决定了分子的功能

2. 边表示化学键

   • 单键、双键或三键
   • 决定了分子的稳定性和反应性

通过图机器学习,我们可以:

• 预测新分子的生物活性
• 设计具有特定性质的新药物
• 优化现有药物的结构

边预测

边预测任务是什么？
是要去判断两个节点之间是否存在边。
在测试时，我们会生成k个最有可能连接的边，根据概率排序。然后通过计算预测边和真实边之间差异来反向传播以训练模型。

当然还有一种方法时直接假装已有边不知道是不是有，然后让模型去预测。这就是自监督学习方法了。（比如假装不知道BD之间有没有边，然后让模型去预测。然后如果预测出来有那就对了。）

两种边预测形式:

1. 随机缺失的边预测

   • 从图中随机移除一些边
   • 让模型预测这些被移除的边
   • 这种方法适合静态图的链接预测

2. 时序边预测

   • 给定t0时刻之前的图结构
   • 预测t1时刻可能出现的新边
   • 输出一个排序后的边列表
   • 通过与实际出现的边对比来评估

   评估方法:

   • 计算在时间区间[t1,t1’]内出现的新边数量n
   • 取预测边列表中的前n个
   • 计算正确预测的边的数量
   • 评估模型的预测准确率

这种预测任务的实际应用场景:

• 社交网络中的好友推荐
• 知识图谱中的关系预测
• 蛋白质相互作用网络中的新连接发现

几个例子

推荐系统中的边预测

推荐系统是边预测的一个典型应用。在这种场景下:

• 节点包括:

  • 用户节点(Users)
  • 物品节点(Items,如电影、商品、音乐等)

• 边表示:

  • 用户与物品之间的交互(如观看、购买、收听等)
  • 这些交互形成了用户-物品二分图

• 预测任务:

  • 根据已有的用户-物品交互记录
  • 预测用户可能感兴趣的新物品
  • 生成”猜你喜欢”的推荐列表

这种预测的特点是:

• 利用图的结构特征捕捉用户兴趣

• 可以发现相似用户的共同偏好

• 帮助解决冷启动问题

  冷启动问题指的是系统对新用户或新物品缺乏历史交互数据,难以做出准确推荐。通过图结构,可以利用相似用户或物品的关系来缓解这个问题。

比如在上图所示的例子中:

• 如果多个用户都购买了某些相似的商品
• 系统就可以推断出这些用户可能有相似的兴趣
• 进而推荐他们可能喜欢但尚未购买的其他商品

PinSage推荐系统

以Pinterest的PinSage系统为例:

• 预测任务:

  • 向用户推荐相关的图片内容(Pin)
  • 学习节点的嵌入表示
  • 预测两个节点是否相关

• 系统特点:

  • 将每个Pin建模为图中的一个节点
  • 通过图神经网络学习节点的向量表示
  • 利用节点之间的距离度量相似度
  • 推荐距离较近的相关内容

• 具体实现:

  • 如果用户对蛋糕图片感兴趣
  • 系统会分析该图片的嵌入向量
  • 找到向量空间中距离较近的其他内容
  • 可能推荐相似的甜点图片
  • 但不会推荐风格迥异的商品(如运动服)

这种基于图神经网络的推荐方法:

• 能够自动学习内容之间的关联
• 捕捉用户兴趣的细微差异
• 生成更精准的个性化推荐

生物医学图链接预测

在生物医学领域:

• 预测任务:

  • 预测药物与蛋白质的相互作用
  • 发现潜在的药物副作用
  • 分析多种药物联合使用的影响

• 图的构建:

  • 节点包括药物和蛋白质
  • 边表示它们之间的相互作用
  • 不同类型的边代表不同作用关系
    • 药物-蛋白质相互作用
    • 蛋白质-蛋白质相互作用
    • 药物的副作用

• 具体应用:

  • 预测新药与已知蛋白质的作用
  • 分析药物组合可能产生的副作用
  • 发现新的治疗用途
  • 优化药物开发流程

图级别任务

我们想要根据一个整图或子图结果进行预测。

例如交通网络预测。

在交通网络预测中:

• 预测任务:
  • 预测车辆到达时间
  • 分析交通流量变化
  • 优化路线规划

• 图的构建:

  • 节点表示路口和地点
  • 边表示道路连接
  • 边的属性包含:
    • 道路长度
    • 实时车流量
    • 历史通行时间

• 具体应用:

  • Google Maps导航
    • 收集匿名出行数据
    • 通过图神经网络训练
    • 预测最优路线和到达时间
    • 为用户提供实时导航建议
  • 交通管理
    • 预测拥堵路段
    • 优化信号灯配时
    • 分散交通流量

这种基于图神经网络的交通预测方法:

• 能够处理复杂的路网结构
• 考虑多个影响因素
• 提供准确的实时预测

分子图预测

在药物发现和分子设计中,分子可以表示为图结构:

• 节点表示原子
• 边表示化学键
• 节点和边的属性包含:
  • 原子类型
  • 化学键类型
  • 电荷分布
  • 空间构型

例如抗生素分子的图表示:

• 每个原子(C、H、O、N等)是一个节点
• 化学键(单键、双键等)是边
• 通过图神经网络可以:
  • 预测分子性质
  • 分析药物活性
  • 设计新型分子

具体应用包括:

• 药物筛选
  • 预测候选分子的活性
  • 评估毒性和副作用
  • 优化分子结构
• 材料设计
  • 预测材料性质
  • 设计新型材料
  • 优化合成路线

这种基于图的分子表示方法能够:

• 保留分子的结构信息
• 捕捉原子间的相互作用
• 支持端到端的分子设计

总结

本文我们主要介绍了图机器学习在节点预测、边预测、图级别任务和分子图预测中的应用。

接下来我们将对具体实现进行讨论。