认识图：世界的数据结构

图中有数：图神经网络的入门与实战

第 1 章

认识图：世界的数据结构

1.1 从一张网络说起

想象你正在使用微信和朋友聊天。你点开通讯录，看到了一长串好友列表。这个列表看起来平淡无奇——仅仅是名字的罗列。但如果我告诉你，这个看似简单的通讯录背后，隐藏着一种极其强大且普遍的数据结构，你是否会感到惊讶？

让我们深入思考一下。你和好友之间的关系，并不是孤立存在的。假设你是小明，你的好友小红同时也认识你的另一位好友小刚。这种“认识”的关系，就像一条条无形的丝线，将你和小红、小红和小刚、小刚和你连接在一起。如果你把所有用户看作一个个点（我们称之为节点），把用户之间的好友关系看作连接这些点的线（我们称之为边），那么整个微信的好友网络就会呈现为一幅巨大的、由节点和边编织而成的复杂结构图。这，就是我们今天要认识的图（Graph）。

也许你会说：“这听起来很抽象，和我的日常生活有什么关系呢？”事实上，图是一种无处不在的数据结构，它远比我们想象的要普遍得多。翻开你的手机地图应用，那些错综复杂的道路网络，实际上就是一幅图；浏览学术论文时，文末的参考文献列表，实际上也构成了一张引文网络；甚至你身体里每一个细胞的代谢过程，也可以用图来建模。掌握图的概念，就相当于掌握了一把钥匙，能够打开理解世界复杂关联的大门。

在本书中，我们将一起踏上学习图神经网络的旅程。图神经网络是近年来人工智能领域最激动人心的研究方向之一，它让机器能够“理解”图结构的数据，从而完成节点分类、链路预测、图分类等任务。但正如建造高楼需要稳固的地基一样，要掌握图神经网络，我们首先需要对图这种数据结构有扎实的理解。本章将作为这本书的起点，带领大家从日常生活中的例子出发，系统地认识图的基本概念、类型、表示方法，以及它在现实世界中的应用场景。让我们开始吧！

1.2 图的基本构成要素

1.2.1 节点：图的基石

在图的世界里，节点（Node），也称为顶点（Vertex），是构成图的基本单位。顾名思义，节点就像是一张网中的各个交点，代表了我们要研究或关注的实体对象。

节点的含义可以根据具体应用场景而变化。在社交网络中，节点可以代表用户账户；在城市交通网络中，节点可以代表交叉路口或地铁站；在分子结构图中，节点可以代表化学原子。理解节点代表什么实体，是理解具体图结构的第一步。

在数学上，我们通常用大写字母 $V$ 来表示节点组成的集合，用 $|V|$ 来表示节点的总数（也称为图的阶数）。例如，对于一个有 5 个节点的图，我们可以说 $|V| = 5$。每个节点通常会被赋予一个唯一的标识符，比如 $v_1, v_2, v_3, \ldots$ 或者直接使用我们关心的实体名称。

```mermaid graph TD A[节点 A<br/>社交网络：用户A<br/>交通网络：站点A<br/>分子结构：碳原子C1] B[节点 B] C[节点 C] D[节点 D] E[节点 E] ```

上面这个简单的示意图展示了一个包含 5 个节点的图，每个节点可以代表不同场景下的不同实体。重要的是，节点本身可以携带信息。例如，一个社交网络用户节点可能包含姓名、年龄、兴趣爱好等属性；一个城市地铁站点节点可能包含站点名称、客流量、是否可换乘等信息。在图神经网络中，节点的这些属性信息就是我们进行学习和预测的重要特征来源。

1.2.2 边：关系的纽带

如果说节点是图的基本单元，那么边（Edge）就是连接节点、表达节点之间关系的纽带。边定义了图中不同节点之间的关联方式，是图结构的核心所在。

在数学表示中，我们通常用集合 $E$ 来表示所有边的集合，一条具体的边可以表示为 $(u, v)$，其中 $u$ 和 $v$ 是这条边所连接的两个节点。我们称节点 $u$ 和节点 $v$ 是相邻的（adjacent）或者说是邻居（neighbor），因为它们之间存在直接的连接关系。如果一条边连接了节点 $u$ 和节点 $v$，我们可以说这条边关联于（incident）节点 $u$ 和 $v$。

```mermaid graph LR A((节点 A)) --- B((节点 B)) B --- C((节点 C)) C --- D((节点 D)) A --- D B --- D

style A fill:#e1f5fe style B fill:#e1f5fe style C fill:#e1f5fe style D fill:#e1f5fe ```

考虑一个具体的例子。在微博的关注网络中，如果用户 A 关注了用户 B，那么我们就需要在节点 A 和节点 B 之间创建一条边，表示这种关注关系。这条边承载了重要的语义信息——它告诉我们 A 和 B 之间存在某种社会关系。类似地，在城市的道路网络中，如果要从地点 A 到达地点 B，需要经过一段实际的道路，那么在地点 A 对应的节点和地点 B 对应的节点之间，就应该存在一条边来表示这段道路。

一个节点的度（degree）是指与该节点相连的边的数量。度是图论中一个非常重要的概念，它描述了节点在网络中的重要性和活跃程度。在社交网络中，一个拥有很多好友的用户，其对应节点的度就会很高——这可能意味着这个人是一个社交达人，或者是一个拥有广泛影响力的公众人物。

1.2.3 正式定义：什么是图

现在我们已经了解了图的两个核心要素——节点和边，接下来让我们给出图的形式化定义。

> 图的定义：图（Graph）是由非空的节点集合 $V$ 和连接这些节点的边集合 $E$ 组成的数学结构，记作 $G = (V, E)$。

这个定义看似简单，但它蕴含了图的本质：图是描述事物之间关系结构的抽象工具。无论我们要研究的是社交网络、神经网络还是蛋白质相互作用网络，只要我们能够识别出其中的实体（节点）和实体之间的关系（边），就可以用图这一统一的数学框架来建模。

在实际应用中，我们经常需要对图进行扩展，加入更多的信息来满足具体需求。例如，我们可以为节点和边附加属性信息，得到属性图（Property Graph）；我们也可以为边赋予权重，得到加权图（Weighted Graph）。这些扩展使得图能够更加精确地描述复杂多变的现实世界。

1.3 图的多种类型

现实世界中的关系是复杂多样的，因此图的结构也呈现出丰富的变化。在本节中，我们将介绍几种最常见的图类型分类，理解这些分类将帮助我们更好地根据具体问题选择合适的图模型。

1.3.1 有向图与无向图

这是图的最基本分类之一，取决于图中的边是否具有方向性。

无向图（Undirected Graph）是最直觉的图类型。在无向图中，连接两个节点的边没有方向之分，也就是说，边 $(u, v)$ 和边 $(v, u)$ 是等价的。这就像现实生活中的邻里关系——如果 A 是 B 的邻居，那么 B 也一定是 A 的邻居。城市中的双向道路、微信的好友关系都是无向图的典型例子。

```mermaid graph Undirected A --- B B --- C A --- C B --- D ```

想象一下北京地铁的 1 号线和 2 号线（假设它们构成一个简化的小型网络）。如果你要从东单站前往王府井站，你可以选择步行到达，这段路在地图上就是一条无向边——因为这条道路是双向的，你既可以从东单走到王府井，也可以从王府井走回东单。这就是无向图的特征：关系是双向的、对称的。

有向图（Directed Graph）则不同。在有向图中，每条边都有明确的方向，用箭头表示。边 $(u, v)$ 表示从节点 $u$ 指向节点 $v$ 的有向关系，但并不意味着存在从 $v$ 到 $u$ 的反向关系。微博的关注网络就是一个经典的有向图例子——如果 A 关注了 B，我们可以画一条从 A 指向 B 的边，但 B 是否关注 A 则是另一回事，两者之间没有必然联系。

```mermaid graph Directed A --> B B --> C C --> A A -.-> D D --> A ```

在有向图中，节点的度需要区分为入度（in-degree）和出度（out-degree）。入度是指向该节点的边的数量，出度是从该节点指出的边的数量。在微博的例子中，一个拥有众多粉丝（被很多人关注）的用户，其入度就很高；而一个关注了很多人的用户，其出度就很高。

1.3.2 加权图与非加权图

在许多实际应用中，我们不仅需要知道两个节点之间是否存在关系，还需要知道这种关系的强度或成本。这就引出了加权图的概念。

加权图（Weighted Graph）是指为图中的每条边都赋予一个数值（权重）的图。这个权重可以代表各种有意义的量：距离、时间、成本、流量、概率等等。例如，在导航应用中，从一个路口到另一个路口的道路可以有不同的长度，这些长度就可以作为边的权重；在航空网络中，两个城市之间的航班价格可以作为边的权重；在推荐系统中，用户对商品的评分也可以作为边的权重。

```mermaid graph Weighted A--0.5 km, 步行 8 分钟-->B B--3.2 km, 驾车 10 分钟-->C A--2.8 km, 驾车 12 分钟-->C

style A fill:#c8e6c9 style B fill:#c8e6c9 style C fill:#c8e6c9 ```

相比之下，非加权图（Unweighted Graph）的边不带有权重信息，它只告诉我们两个节点是否相连，而不关心这种连接的具体程度。非加权图可以看作是加权图的特例，即所有边的权重都相等（通常设为 1）。

加权与非加权的区分对于后续选择合适的图算法至关重要。在处理加权图时，很多算法（如最短路径算法）需要考虑边的权重；而在处理非加权图时，我们只需要关心拓扑结构本身。

1.3.3 同构图与异构图

这是图数据处理领域非常重要的一个分类维度。

同构图（Homogeneous Graph）是指所有节点都属于同一种类型、所有边都属于同一种类型的图。也就是说，在同构图中，节点之间的边表示的关系是单一且一致的。例如，一个只包含用户节点的社交网络图就是同构图，其中所有边都表示“好友关系”；一个只包含蛋白质分子的相互作用网络也是同构图。

异构图（Heterogeneous Graph）则允许图中存在多种类型的节点和/或多种类型的边。这是更接近真实世界的建模方式。想象一个学术网络：论文、作者、会议/期刊、甚至关键词都是不同类型的节点；作者写论文、会议发表论文、论文引用论文、论文包含关键词等，都是不同类型的边。这样的图就是一个典型的异构图。

```mermaid graph Heterogeneous P1((论文 P1)) P2((论文 P2)) A1((作者 A1)) A2((作者 A2)) J1((会议 J1)) K1((关键词 K1)) K2((关键词 K2))

A1 -->|撰写| P1 A2 -->|撰写| P1 A2 -->|撰写| P2 P1 -->|发表于| J1 P1 -->|引用| P2 P1 -->|包含| K1 P2 -->|包含| K2 ```

异构图能够表达更加丰富和复杂的关系语义，这使得它在知识图谱、推荐系统等场景中得到了广泛应用。然而，异构图的复杂性也带来了建模和计算上的挑战，这也是图神经网络领域的研究热点之一。

1.3.4 其他常见的图类型

除了上述分类，还有几种值得了解的图类型。

简单图（Simple Graph）是指图中不存在自环（self-loop，即连接节点自身的边）和重边（multi-edge，即两个节点之间存在多条边）的图。相比之下，多重图（Multigraph）允许两个节点之间存在多条边。例如，在航空网络中，如果两个城市之间有多家航空公司的航班，就可以用多重边来表示。

连通图（Connected Graph）是指图中任意两个节点之间都存在一条路径（由多条边依次连接而成的节点序列）相连的图。如果图中存在孤立的节点或节点群与其他部分没有连通，则称为非连通图（Disconnected Graph）。对于有向图，还有强连通图（Strongly Connected Graph）的概念，要求任意两个节点之间都存在双向的路径。

有环图（Cyclic Graph）与无环图（Acyclic Graph）的区分在于图中是否存在环路（closed walk）。特别地，有向无环图（Directed Acyclic Graph，简称 DAG）是计算机科学和机器学习中非常重要的一类图结构，许多概率图模型（如贝叶斯网络）和神经网络架构都基于 DAG。

```mermaid graph DAG DAG[A --> B] DAG[B --> C] DAG[C --> D] DAG[A --> D]

cycle[C --> E] E --> B ```

1.4 生活中的图：从社交网络到分子结构

理论的概念或许略显抽象，但图在我们的日常生活中无处不在。在这一节中，让我们通过几个具体的例子，来感受图这一数据结构是如何描述和帮助我们理解真实世界的。

1.4.1 社交网络：数字时代的人际关系图谱

社交网络是图数据最直观的应用场景之一，也是最容易理解的例子。

以微信为例，当我们讨论好友关系时，微信实际上构建了一个庞大的社交网络图谱。在这个图中，每个用户是一个节点，两个人之间如果是好友关系，就用一条无向边连接。整个微信的十亿多用户和数百亿的好友关系，构成了一个规模巨大的社交网络图。

这个图不仅仅是名字和边的简单集合，它蕴含着丰富的信息。通过分析这个图的结构，我们可以发现社交圈子的划分（社区发现）、识别有影响力的人物（节点重要性分析）、推荐可能认识的新朋友（链接预测）、检测虚假账号或垃圾信息（异常检测）等等。社交网络分析已经成为社会学、市场营销、公共安全等领域的重要工具。

微博、Twitter 等平台关注/粉丝关系则构成了有向图的典型场景。一个人可以关注很多其他人，同时又被很多人关注。入度和出度的分布往往呈现出幂律分布（Power Law）的特征——少数用户拥有海量的粉丝（意见领袖、明星账号），而大多数用户只有少量粉丝。这种分布是社交网络的一个重要统计特性。

LinkedIn 的职业社交网络则引入了更多的关系类型：同事关系、同学关系、合作关系、师徒关系等等。这使得 LinkedIn 的网络成为一个异构图的典型案例，其中不同类型的边编码了不同语义的社会关系。

1.4.2 交通网络：城市运转的血管

城市交通系统是图的另一个经典应用场景，而且我们几乎每天都在与它打交道。

当你打开手机地图导航时，系统内部实际上在操作一个巨大的图结构。图的节点代表各种地点：路口、地铁站、公交站、机场航站楼、目的地等。图的边代表道路或路线：城市道路、高速公路、地铁线路、航线等。这些边通常带有权重，可以表示距离、时间、交通拥堵程度等。

当你查询从 A 地到 B 地的最短路径时，地图应用内部运行的是最短路径算法（如 Dijkstra 算法或 A* 算法），这些算法正是图论中的经典算法。它们遍历图中的节点和边，综合考虑边的权重，最终找到最优的路线。

城市公共交通网络（地铁、公交）可以建模为有向加权图。以地铁网络为例，每个站点是一个节点，相邻站点之间的线路是边。由于地铁是按方向行驶的（在大多数情况下，同一条线路上相对方向的车不在同一轨道），所以边是有向的。边的权重可以是两站之间的运行时间、票价，或者是你愿意花费的综合成本。

值得注意的是，同一个物理交通系统可以用不同的方式建模，取决于你的具体需求。如果你关心的是道路连通性而非具体路线，那么建模为无向图可能是合适的；如果你关心的是单向车道、转向限制等交通规则，那么有向图更能准确描述。

1.4.3 分子结构：微观世界的图景

在化学和生物领域，图结构同样扮演着重要角色。

分子的化学结构式天然就是一个图的表示。原子是节点，化学键是边。有机化学中的碳骨架可以用简单的无向图来表示，其中碳-碳单键、双键、三键可以用不同类型的边或加权边来表示。这种表示方法使得化学家能够用图论工具来研究分子结构、化学反应、化合物分类等问题。

在生物信息学和药物研发领域，分子图（Molecular Graph）是表示分子的标准方式之一。每个原子作为一个节点，包含原子类型、电荷、手性等信息作为节点属性；每个化学键作为一条边，包含键的类型（单键、双键、芳香键等）作为边的属性。这种表示使得图神经网络可以直接应用于分子性质预测、药物虚拟筛选等任务，这也是图神经网络在科学领域最成功的应用方向之一。

蛋白质结构、DNA 结构、细胞内的信号传导网络，同样可以用图来建模。蛋白质相互作用网络（Protein-Protein Interaction Network）将蛋白质作为节点，将蛋白质之间的相互作用作为边，研究这个网络的拓扑结构有助于理解细胞功能、发现疾病机制、识别药物靶点。

1.4.4 知识图谱：知识的关联网络

知识图谱（Knowledge Graph）是人工智能领域近年来兴起的重要技术，它将结构化知识表示为图的形式。

在知识图谱中，节点可以代表实体（如人物、地点、组织、概念等），边可以代表实体之间的关系（如“出生在”、“位于”、“创始人”等）。例如，“北京是中国的首都”这句话可以表示为一个包含三个节点（北京市、中华人民共和国、首都） 和两条边（北京市——首都——中华人民共和国；北京市——位于——中华人民共和国）的子图结构。

Google 知识图谱是目前规模最大的知识图谱之一，它包含数十亿个实体和数千亿条关系。通过知识图谱，搜索引擎能够理解用户的查询意图，提供更加精准的搜索结果和智能问答服务。例如，当你搜索“埃菲尔铁塔的设计师”时，搜索引擎可以从知识图谱中找到相关实体，理解“设计师”这层关系，然后返回正确的答案。

知识图谱的构建和补全是知识图谱领域的核心问题，而图神经网络正是解决这些问题的重要工具。通过学习图中的结构信息和语义关系，图神经网络能够帮助我们发现新的知识、纠正错误信息、完善知识图谱的覆盖范围。

1.4.5 推荐系统：发现你的下一个喜好

当你打开 Netflix 观