图与图数据基础 / Fundamentals of Graphs and Graph Data

在我们日常接触的数字世界中，绝大多数数据都不是孤立存在的：微信好友关系里每个人和其他人存在关联，导航软件规划的路线由路口和路段构成，化学家研究的分子结构由原子和化学键组成，搜索引擎背后支撑的知识图谱则将实体和关系编织成庞大的语义网络。这些看似迥异的数据背后，共享着一种统一的结构化表示形式——<dfn>图（Graph，也常简写为G）</dfn>。作为<dfn>图神经网络（Graph Neural Network, GNN）</dfn>的核心载体，图数据是对现实世界中关联关系的抽象建模，也是本书所有内容的基石。本章将从图的核心组成元素、基本属性出发，结合大众熟悉的场景建立对图数据的直观认知，同时提供中英对照的核心术语表，为后续的GNN原理学习打下坚实基础。

1.1 图的核心组成元素 / 1.1 Core Components of a Graph

从数学定义来看，一个正式图可以表示为$G = (V, E)$，其中$V$是节点的集合，$E$是边的集合。除了这两个核心元素外，多数实际场景中的图还会包含权重、方向等扩展属性，下面我们逐一介绍。

1.1.1 节点（Node / Vertex）

<dfn>节点（Node，也常称为Vertex，二者在图论中通常可互换使用，后续我们会根据场景交替使用这两个表述）</dfn>是图的核心组成单元，对应现实世界中的实体对象。在社交网络中，节点可以是用户、群聊等实体；在交通路网中，节点可以是路口、交通枢纽、公交站点；在分子结构中，节点对应原子；在知识图谱中，节点对应人物、地点、事件、物品等实体。每个节点可以拥有自身的属性特征：比如社交网络用户的年龄、性别、地域，交通路网路口的人流量、红绿灯时长，分子的原子序数、电负性，知识图谱实体的描述文本、属性标签等。

1.1.2 边（Edge）

<dfn>边（Edge）</dfn>是连接两个节点的关系载体，对应现实世界中节点之间的关联。按照关系的对称性，边可以分为两类：如果关系是双向的（比如微信好友关系、化学共价键），则对应的边是无向边，此时图被称为<dfn>无向图（Undirected Graph）</dfn>；如果关系是单向的（比如微博关注关系、道路的单行道、化学中的离子键），则对应的边是有向边，此时图被称为<dfn>有向图（Directed Graph）</dfn>。此外，连接同一个节点的边被称为<dfn>自环（Self-loop）</dfn>，对应现实中的“自己关注自己”“分子内的原子自相互作用”等场景；连接同一对节点的多条边被称为<dfn>多重边（Multi-edge）</dfn>，对应“两个用户之间有多个共同群聊”“两个路口之间有多个并行道路”等场景。

1.1.3 权重（Weight）

<dfn>权重（Weight）</dfn>是边的可选属性，用于量化节点之间关系的强度、成本或相似性。比如社交网络中，两个用户之间的互动频率、亲密度可以作为边的权重；交通路网中，路段的长度、通行时间、拥堵指数可以作为边的权重；分子结构中，化学键的键长、键能可以作为边的权重；知识图谱中，实体之间关系的可信度、关联强度可以作为边的权重。带有权重的图被称为<dfn>带权图（Weighted Graph）</dfn>，不携带权重的图则被称为<dfn>无权图（Unweighted Graph）</dfn>，无权图的边权重通常默认为1。

1.1.4 方向（Direction）

边的方向是区分有向图和无向图的核心属性：无向图的边没有方向，意味着节点之间的关系是对称的（A和B是好友，等价于B和A是好友）；有向图的边有方向，通常用箭头表示，意味着节点之间的关系是非对称的（A关注B，不等价于B关注A）。方向属性直接影响图的基本属性计算：比如有向图中节点的度需要分为<dfn>入度（In-degree）</dfn>（指向该节点的边的数量）和<dfn>出度（Out-degree）</dfn>（该节点指向的其他节点的边的数量），而无向图中节点的度就是与该节点相连的边的总数量。

为了更直观地理解这些核心元素，我们来看一个简单的社交网络示例：假设有4个用户，分别是张三、李四、王五、赵六，其中张三关注了李四，李四关注了王五，王五关注了赵六，张三和赵六是互相关注的好友，张三和李四的互动权重为3，李四和王五的互动权重为2，王五和赵六的互动权重为1，张三和赵六的互动权重为5。这个场景可以用下图表示： ```mermaid graph LR A[节点A: 张三] -->|权重: 3| B[节点B: 李四] B -->|权重: 2| C[节点C: 王五] C -->|权重: 1| D[节点D: 赵六] A ---|权重: 5| D ``` 在这个示例中，4个用户对应4个节点，关注/好友关系对应边，互动频率对应边的权重，关注关系的单向性对应边的方向，互相关注对应无向边。

1.2 图的基本属性 / 1.2 Basic Properties of Graphs

图的基本属性是描述图结构特征、支持后续图算法计算的核心指标，包括度、路径、连通性、邻接矩阵、拉普拉斯矩阵等，下面我们逐一介绍。

1.2.1 度（Degree）

<dfn>度（Degree）</dfn>是描述节点连接数量的核心指标：对于无向图$G=(V,E)$，节点$v$的度$deg(v)$定义为与$v$相连的边的数量，公式表示为： $$deg(v) = |\{e \in E | e \text{ 与 } v \text{ 关联}\}|$$ 对于有向图，节点的度分为入度和出度：<dfn>入度（In-degree）</dfn>$deg_{in}(v)$是指向节点$v$的边的数量，<dfn>出度（Out-degree）</dfn>$deg_{out}(v)$是节点$v$指向其他节点的边的数量，节点的总度为二者之和： $$deg(v) = deg_{in}(v) + deg_{out}(v)$$ 回到1.1节的社交网络示例：张三的出度为2（关注李四、指向赵六），入度为1（赵六关注张三，因为互相关注对应无向边，等价于双向有向边），因此总度为3；李四的出度为1（关注王五），入度为1（张三关注李四），总度为2；王五的出度为1（关注赵六），入度为1（李四关注王五），总度为2；赵六的出度为1（关注张三），入度为1（王五关注赵六），总度为2。

> 💡 侧边栏（电子版专属）：在社交网络分析中，节点的度可以用来衡量用户的影响力：度越高的用户，连接的关系越多，通常影响力越大。比如微博上的明星账号，关注数和粉丝数通常远高于普通用户，对应节点的度也更高。

1.2.2 路径（Path）与最短路径

<dfn>路径（Path）</dfn）是指图中节点的一个有序序列，其中相邻节点之间由边连接。路径的长度通常定义为路径上所有边的权重之和（无权图中每条边的权重为1，因此路径长度等于边的数量）。如果路径的起点和终点相同，则被称为<dfn>环（Cycle）</dfn>；如果路径中不重复经过任何节点，则被称为<dfn>简单路径（Simple Path）</dfn>。

<dfn>最短路径（Shortest Path）</dfn>是指两个节点之间长度最小的路径，是图算法中最经典的问题之一，广泛应用于路径规划、网络路由等场景。比如导航软件规划从家到公司的最快路线，本质上就是在交通路网图中找到起点和终点之间的最短路径，其中边的权重为实时通行时间。

1.2.3 连通性（Connectivity）

<dfn>连通性（Connectivity）</dfn>是描述图整体结构的属性：如果图中任意两个节点之间都存在至少一条路径，则称该图为<dfn>连通图（Connected Graph）</dfn>；否则，图中会存在多个独立的子图，每个子图内部是连通的，子图之间没有路径连接，这些子图被称为<dfn>连通分量（Connected Component）</dfn>。

比如在社交网络中，如果你的微信好友分为“大学同学”“工作同事”“家人”三个群体，且三个群体之间没有任何共同好友，那么你的好友关系图就会包含3个连通分量，每个分量对应一个好友群体。

1.2.4

1.2.4 邻接矩阵（Adjacency Matrix）

<dfn>邻接矩阵（Adjacency Matrix）</dfn>是图的最常用矩阵表示形式，能够将图的结构信息编码为二维矩阵，方便计算机存储和算法计算。对于具有$n$个节点的图$G=(V,E)$，其邻接矩阵$A$是一个$n \times n$的方阵，其中元素$A_{ij}$表示节点$i$和节点$j$之间的边的关系：

• 对于无权无向图：如果节点$i$和$j$之间有边，$A_{ij}=A_{ji}=1$，否则为0；
• 对于无权有向图：如果存在从$i$指向$j$的边，$A_{ij}=1$，否则为0，此时矩阵不一定对称；
• 对于带权图：$A_{ij}$等于$i$到$j$的边的权重，无边的位置为0。

我们继续用1.1节的4节点社交网络示例，节点顺序为张三（1）、李四（2）、王五（3）、赵六（4），其中张三关注李四（权重3）、李四关注王五（权重2）、王五关注赵六（权重1）、张三和赵六互相关注（权重5），其邻接矩阵可以表示为： $$ A = \begin{bmatrix} 0 & 3 & 0 & 5 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 1 \\ 5 & 0 & 0 & 0 \end{bmatrix} $$ 从矩阵中可以看出：无向边（张三和赵六的好友关系）对应的矩阵元素是对称的（$A_{14}=A_{41}=5$），而有向边（关注关系）对应的矩阵元素不对称（$A_{12}=3$但$A_{21}=0$，因为李四没有关注张三）。如果存在自环（比如张三自己关注自己），则矩阵的对角线元素$A_{11}$会等于自环的权重。

邻接矩阵有一个非常重要的特性：稀疏性。现实世界中的图绝大多数都是稀疏图：比如微信拥有超过10亿用户，平均每个用户的好友数仅为200左右，对应的邻接矩阵大小为$10^9 \times 10^9$，但非零元素仅约$200 \times 10^9$，占比不到0.0002%，也就是说99.9998%的元素都是0。如果直接用二维数组存储会浪费极大的空间，因此实际应用中通常使用CSR（压缩稀疏行）、CSC（压缩稀疏列）等稀疏矩阵格式存储，这也是后续GNN能够处理大规模图数据的基础。

> 💡 侧边栏（电子版专属）：邻接矩阵是社交网络推荐算法的