第一章 介绍

复杂数据可以表示为对象之间的关系图。这种图网络是模拟社会、技术和生物等系统的基本工具。

图是描述实体之间复杂交互的自然方式。 我们在笔记中互换使用图/网络。

1.1 充满图的世界

常见的网络包括人类社会、化学相互作用、神经元连接、知识图谱等。您可以将它们粗略地分为（1）自然定义的（2）人造的，但区分通常很困难。

从下图我们可以看到，图可以用于建模：社会网络、经济网络、通信网络、事件网络、知识图、病毒传播路径网络、信息网络：网页和引用、互联网、神经元网络、分子网络、场景网络、细胞网络等等

1.2 图的现实世界应用

一般来说，我们对网络的分析分为以下几类：

• 节点分类：预测给定节点的类型
• 链接预测：预测两个节点之间的交互（或存在）
• 社区检测：识别链接的节点集群
• 网络相似性：测量节点/子图/整个网络之间的相似性

1.2.1 社交网络

我们习惯被告知有 6 度分离。 研究人员在 2012 年发现，根据 Facebook 数据构建的社交图谱，人与人之间的平均距离实际上是3.74，远小于 1967 年发现的 4.4 − 5.7 范围，即著名的“小世界问题”。

通过聚类技术，我们还可以发现社交圈。 下面是从使用网络结构和用户配置文件识别社交圈的方法中提取的示例图像。

我们可以使用类似于社交圈检测的技术将转发网络沿着党派界限分开。

1.2.2 影响力传播

网络分析对于识别基础设施网络的弱点也很有用。 下面显示了 2003 年 8 月 15 日发生的停电（8 月 14 日与 8 月 15 日），影响了东海岸的大部分地区，影响了加拿大和美国的城市。 请注意，多伦多/底特律完全消失，而华盛顿 - 波士顿走廊则明显变暗。 更高分辨率的图像。 通过网络分析工具，我们可以了解哪些节点（城市）将受到影响、影响的严重程度以及传播的速度。

这种故障传播模型也适用于错误信息的传播和病毒的传播。 通过病毒传播模型，您可以对人、社区、城市和国家之间的连通性（疾病传播的概率）进行建模。 识别和切断传播中心可以定位疾病传播的影响。 请参阅 CDC 于 2006 年发布的大流行性流感模型。

1.2.3 知识图谱

知识图是异构图的一个很好的例子，异构图包含具有不同含义的节点。 通常在知识图中，有项目节点和属性/类别节点。

1.2.4 推荐系统

预测用户偏好可以抽象为预测二分图中边的存在。 可以通过SVD（奇异值分解）等概念，但您也可以通过将用户偏好矩阵视为邻接矩阵来解决这个问题。 在课堂上，我们展示了 Pinterest 拥有自己的基于图像嵌入的图搜索算法，可处理 3 亿用户、超过 40 亿个 pin 和超过 20 亿个图板。 请注意，Pinterest 正在构建一个包含用户、图钉和图板的“三方”图。

将推荐系统的二分图与底层知识图结合起来并不罕见。 一个明显的用例是电影推荐，其中电影具有流派、主题、导演、演员等属性。这可以视为多个不相交图的叠加，但完全组合的图具有最佳的预测能力。

1.2.5 生物化学应用

生物途径、源自药物和蛋白质原子结构的“网络”、药物的相互作用/作用/副作用，甚至食物链自然地形成具有潜在异质节点的网络。 近年来，使用图卷积网络来预测化学品的影响已受到关注，可以与基于点云的 3D 体素卷积技术竞争。 例如，可以使用具有代表药物和蛋白质的节点的异质图来对药物组合的效果进行建模。

1.3 图结构数据上的机器学习

• 节点预测：预测节点的类别或某类属性的取值
  • 例子：对是否是潜在客户分类、对游戏玩家的消费能力做预测
• 边预测：预测两个节点间是否存在链接
  • 例子：Knowledge graph completion、好友推荐、商品推荐
• 图的预测：对不同的图进行分类或预测图的属性
  • 例子：分子属性预测
• 节点聚类：检测节点是否形成一个社区
  • 例子：社交圈检测
• 其他任务
  • 图生成：例如药物发现
  • 图演变：例如物理模拟
  • ……

1.4 应用神经网络于图面临的挑战

在学习了简单的图论知识，我们再来回顾应用神经网络于图面临的挑战。

过去的深度学习应用中，我们主要接触的数据形式主要是这四种：矩阵、张量、序列（sequence）和时间序列（time series），它们都是规则的结构化的数据。然而图数据是非规则的非结构化的，它具有以下的特点：

• 任意的大小和复杂的拓扑结构；
• 没有固定的节点排序或参考点；
• 通常是动态的，并具有多模态的特征；
• 图的信息并非只蕴含在节点信息和边的信息中，图的信息还包括了图的拓扑结构。

以往的深度学习技术是为规则且结构化的数据设计的，无法直接用于图数据。应用于图数据的神经网络，要求

• 适用于不同度的节点；
• 节点表征的计算与邻接节点的排序无关；
• 不但能够根据节点信息、邻接节点的信息和边的信息计算节点表征，还能根据图拓扑结构计算节点表征。

1.5 参考资料

图深度学习从理论到实践 包勇军、朱小坤、颜伟鹏、姚普 清华大学出版社

CS224W Lecture Notes https://jingboyang.github.io/stanford-cs224w-graph-ml/stanford_cs224w_graph_ml.pdf#section.1