图机器学习（Graph Machine Learning，简称Graph ML）是机器学习领域中一个极具特色的分支——其核心目标在于处理以图形结构呈现的数据。简单来说，数据被组织成一张图：节点（或称顶点）代表实体，边（或称链接）表示实体间的关联。听起来有些抽象？别担心，本文将从头开始讲解：图究竟是什么，我们如何描述它、表示它，以及它具备哪些关键属性。
图论的概念最早可追溯至18世纪，欧拉为解决著名的柯尼斯堡七桥问题而提出：能否只穿过七座桥中的每一座恰好一次？这一经典问题直接催生了现代图论。
什么是图？如何定义它？
图，本质上就是一组相互连接的对象。
一张图由一组节点 N 和一组边 E 组成。n 代表节点数量，m 代表边数量。如果两个节点之间存在边相连，我们称它们为相邻（或称邻接）。当提到网络的“规模 N”时，通常指节点数量（边的数量也常用 L 表示）。
有向与无向
图可划分为无向图和有向图：
- 无向图：边没有方向，关系是对称的。绘制边的顺序无关紧要。
- 有向图：边具有方向（也常称为有向图），节点之间的边可用箭头表示，此时也称为弧线。
图的基本性质
对于任意一个节点，我们可以定义它的“度”（k）——即与它相连的边的数量。对于整个图，无向图的平均度 k 计算方式如下：
在有向网络中，情况稍显复杂：每个节点拥有入度（指向该节点的边数）和出度（从该节点出发的边数），节点的总度等于两者之和。那些没有入度的节点称为“源节点”，没有出度的节点称为“汇节点”。
平均度的计算公式则变为：
其中：
除了用节点和边描述，图还有一种常见的表示形式——邻接矩阵。它是一个 n × n 的方阵（n 为节点数），行和列分别对应图节点，矩阵中的元素 Aij 表示节点 i 与节点 j 之间是否有边相连：有边为 1，否则为 0。对于无向图，该矩阵是对称的。你可能会注意到，矩阵对角线通常为 0，表示没有自环（节点与自身相连）。
对于节点 i，要计算它的度（即它有多少条边），只需将这一行或这一列的所有值相加即可：
无向图中的总边数，等于所有节点的度之和（即邻接矩阵中所有元素之和）再除以 2：
为什么要除以2？因为在无向图里，每条边在对称矩阵中被计算了两次。有向图的情况则不同，我们可以分别用两个邻接矩阵来表示入度和出度：
对于单个节点，它的总边数等于入度加出度：
再具体一点，节点入度、出度以及图的总边数的计算方式如下：
由于线性代数与图论之间存在天然联系，我们可以对邻接矩阵进行多种操作。例如，若对无向图的邻接矩阵做转置，图本身不会发生变化（因为对称），但转置有向图的邻接矩阵后，所有边的方向就会反转。
这些矩阵有一个共同特点——它们极其稀疏。理论上，一个节点可以与图中所有其他节点相连，但在现实世界中几乎不可能发生。如果所有节点都两两相连，我们称之为“完全图”。完全图常被用于理解图论中的某些复杂问题（例如连通性相关的示例）。
图的最大密度就是完全图中可能存在的边的总数。实际密度则用这个最大值来度量非完全图：
举个现实中的例子：理论上在社交网络里，每个人都可以与其他所有人连接，但实际上并不会发生。所以最终你得到的是一个 70 亿行、70 亿列的邻接矩阵，其中绝大多数元素都是 0（因为实在太稀疏了）。为什么提这个？因为并非所有算法都能很好地处理稀疏矩阵。
除了邻接矩阵，我们还可以把图表示成一张“边的列表”：
但这种方法在机器学习分析中会存在问题。因此，一种更常用的表示法诞生了——邻接表。它对于大型稀疏图特别友好，能让你快速检索某个节点的邻居。
加权图
图上的边还可以附加权重。并非所有边都一样——比如在交通图中，为了找出两个节点之间的最佳路径，我们需要考虑代表时间或拥堵程度的权重。
自循环
节点有时也可以与自身相连，这就是自循环。在计算总边数时，必须将这些自环也计入。
另外，还有一种叫做多重图的结构——同一对节点之间可以存在多条边。
多重图
含有平行边的图就叫多重图，也就是说同一对节点之间有多条边。
以上就是一些常见的图类型及其表示方式，来一张汇总图感受一下：
图的另一个重要参数是连通性。每个节点是否能通过某条路径到达其他所有节点？连通图就是指所有顶点都能通过一条路径连接起来。不连通图则包含两个或多个连通分量。
那些最大的、彼此隔离的节点子集，被称为“孤岛”（island）。知道图是连通还是不连通，这一点很重要——有些算法很难处理不连通的图。这种不连通性在邻接矩阵中会表现为：不同组件被写成对角线块（非零元素被限制在少量平方矩阵中）。而连接两个“孤岛”的那条边，我们叫它“桥”（bridge）。
如果图很小，用肉眼观察就能判断连通性。但面对一个大图，检查连通性就变得非常有挑战性。
双部图
前面我们看到的图都叫单部图——只有一种节点和一种关系。双部图则是一种将节点划分为两个不相交集合（通常叫 U 和 V）的图。这两个集合各自内部没有边：U 中的每个节点只与 V 中的节点相连，反之亦然。也就是说，双部图里不存在 U-U 连接或 V-V 连接。现实中有很多这样的例子：作者（U）和他们写的论文（V）、演员（U）和他们参演的电影（V）、用户和产品、食谱和配料等等。另一个经典例子是疾病网络：一组疾病和一组基因，只有那些已知会导致或影响某种疾病的突变基因才与对应的疾病相连。再比如匹配问题——双部图可以用在约会应用里。对于一个有 m 个节点的 U 和 n 个节点的 V 的双部图，可能的边总数是 m × n，节点总数是 m + n。
双部图还可以“折叠”成两个单独的网络：U 的投影和 V 的投影。在 U 的投影中，如果两个 U 节点都连到了同一个 V 节点，那么它们俩之间就有一条边（V 投影同理）。
如果需要，我们还可以构建三部图。更进一步，可以有超过三种类型的节点，这通常被称为 k-部图。
异构图
异构图（也常被称为异质图）是一种具有不同类型节点和边的图。看上去更复杂，但能表达更丰富的现实关系。
平面图
如果一幅图可以被画成没有任何边交叉的形式，我们就称它为平面图（这种画法叫平面表示）。即便最初画的时候边是交叉的，图本身也可能是平面的。看下面这个例子，它完全可以重新画成一个平面表示。
为什么知道图是否是平面的很有用？最经典的例子是电路板设计——要保证不同导线不会相交。
循环图与非循环图
线路（walk）是节点的一个交替序列：从 u 出发到 v 结束，中间经过一串节点。路径（path）则是一种特殊的线路：序列中所有节点都不重复。比如 u-x-v 是一条路径，但 u-x-u-x-v 虽然是一条线路，却不是路径。循环图就是路径的起点和终点为同一个节点的图。很多算法在遇到循环时会出问题（所以有时候需要切断一些连接，把循环图转为非循环图）。前馈神经网络就被定义为有向无环图（DAG），因为 DAG 总是有终点（也叫叶子节点）。
总结
在这篇文章里，我们介绍了什么是图以及它的主要属性。尽管图这个概念看起来很简单，但它能实现的变化几乎无穷无尽。图是节点和边的集合；它没有顺序，也没有起点和终点。通过它，我们可以定义不同类型的概念和数据，还能简洁地描述数据中蕴含的许多属性，帮我们看清不同对象之间的关系。比如，我们可以为节点和边赋予权重和属性。在后续的文章中，我们会进一步讨论如何在这些网络上运用算法（以及它们该如何表示）。