第1章：图的世界——节点与边的冒险

欢迎来到图神经网络奇境！在这个充满连接与关系的世界里，一切都可以用节点和边来描述。想象一下，你手中的地图不是山川河流，而是一个由点和线编织的冒险网络——这就是图（Graph）的奇妙世界。无论你是想理解家庭成员之间的纽带，还是探索互联网上网页的超级链接，图都是最强大的思维工具。本章将带你从零开始，认识图的基本元素：节点（Node）和边（Edge），并学会如何用两种经典方法——邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）——将它们描绘出来。准备好了吗？让我们踏上这场节点与边的冒险吧！

节点：图的基本粒子

图（Graph）是由节点（Node）和边（Edge）组成的数学结构，用于表示对象之间的关系。节点（Node），也称为顶点（Vertex），是图的基本单元，代表一个独立的实体或对象。节点可以具有标签（Label）和属性（Attribute），用于描述其特性。例如，在家庭关系图中，每个家庭成员（爸爸、妈妈、孩子）是一个节点；在社交网络中，每个用户是一个节点；在交通地图中，每个城市是一个节点。节点本身不包含任何连接信息，它只是等待被边（Edge）链接的“孤岛”。

节点的核心特性：

• **唯一标识**：每个节点有唯一ID，如数字0、1、2或名称“Alice”。
• **可携带信息**：节点可以存储数据，如用户的年龄、城市的人口。
• **无连接时孤立**：节点可以独立存在，不依赖其他节点。

让我们通过具体例子理解节点。假设你有一个小家庭：爸爸（Node A）、妈妈（Node B）和你（Node C）。这里，A、B、C就是三个节点。再扩大范围，你的学校可能是一个节点，你的宠物狗是另一个节点，甚至你最喜欢的玩具也可以是节点！图的神奇之处在于，任何事物都可以成为节点——只要你想研究它们之间的关系。

💡 小提示（电子版侧边栏）：在现实世界中，节点可以是物理实体（如城市、机器）或抽象概念（如想法、事件）。图神经网络（GNN）正是通过学习节点及其邻居的特征来预测节点属性或图整体性质。

节点的数学表示

从数学角度，节点集合通常用 $V$ 表示（来自德语“Vertices”），$|V|$ 表示节点数量。例如，一个包含5个节点的图，$V = \{v_1, v_2, v_3, v_4, v_5\}$。每个节点 $v_i$ 可以有一个特征向量 $\mathbf{x}_i \in \mathbb{R}^d$，其中 $d$ 是特征维度。例如，在用户节点中，$\mathbf{x}_i$ 可能包含年龄、兴趣、活跃度等数值。

```python

示例：节点特征表示（Python字典）

nodes = { "Alice": {"age": 25, "hobby": "reading", "city": "Beijing"}, "Bob": {"age": 30, "hobby": "hiking", "city": "Shanghai"}, "Charlie": {"age": 22, "hobby": "gaming", "city": "Beijing"} } ``` 这段代码定义了三个用户节点，每个节点有年龄、爱好和城市属性。在图神经网络中，这些特征将作为输入，通过消息传递（Message Passing）聚合邻居信息。

节点的可视化：Mermaid示例

用Mermaid绘制一个简单的家庭节点图： ```mermaid graph LR A[爸爸] --- B[妈妈] A --- C[我] B --- C ``` 这里，`graph LR` 表示从左到右布局，`A[爸爸]` 定义节点A标签为“爸爸”，`---` 表示无向边（稍后解释）。三个节点通过边连接，形成一个三角形，代表家庭关系。

历史趣闻：图论的起源可追溯到1736年，瑞士数学家欧拉（Leonhard Euler）解决了柯尼斯堡七桥问题（Seven Bridges of Königsberg）。该问题问：能否一次走遍七座桥且每座桥只走一次？欧拉将问题抽象为图：陆地是节点，桥是边，并证明无解，从而开创了图论。节点和边的思想由此诞生。

边：关系的桥梁

边（Edge）连接两个节点，表示它们之间的关系或互动。边是图的“粘合剂”，没有边，图只是一堆孤立的节点。边的类型决定了图的性质和应用场景。

边的核心类型： 1. 无向边（Undirected Edge）：关系是对称的，没有方向。例如，家庭关系中的“是父母”是相互的（爸爸和孩子互为亲属），友谊通常是双向的（Alice是Bob的朋友，Bob也是Alice的朋友）。无向图（Undirected Graph）中，边用直线 `---` 表示。 2. 有向边（Directed Edge）：关系有方向，从源节点指向目标节点。例如，社交媒体上的“关注”（Following）：Alice关注Bob，但Bob不一定关注Alice。有向图（Directed Graph）中，边用箭头 `-->` 表示。 3. 带权边（Weighted Edge）：边附加数值权重，表示关系的强度、距离或成本。例如，地图中城市间的道路可能有距离权重（公里数），社交网络中的互动频率可作为权重。带权图（Weighted Graph）中，边可以标注权重值。

边的数学表示

边集合用 $E$ 表示，$|E|$ 是边的数量。对于无向图，边是无序对 $(u, v)$，表示节点 $u$ 和 $v$ 相连；对于有向图，边是有序对 $(u, v)$，表示从 $u$ 到 $v$ 的指向。带权边可表示为 $(u, v, w)$，其中 $w$ 是权重。

例如，一个家庭无向图：$V = \{A, B, C\}$，$E = \{(A,B), (B,C), (A,C)\}$。 一个有向图（关注网络）：$V = \{Alice, Bob, Charlie\}$，$E = \{(Alice, Bob), (Bob, Charlie)\}$，表示Alice关注Bob，Bob关注Charlie。

边的可视化与例子

用Mermaid展示有向边（关注网络）： ```mermaid graph LR A[Alice] --> B[Bob] B --> C[Charlie] C -.-> A ``` 这里，`-->` 是有向边，`-.->` 是虚线有向边（表示弱连接或非互惠）。Alice→Bob→Charlie形成链，Charlie→Alice形成循环，表示Charlie也关注Alice。

地图中的边：假设三个城市北京、上海、广州。无向边表示双向道路，有向边可能表示单行道或航班方向（北京→上海有航班，但上海→北京可能不同）。权重可以是距离（北京到上海约1000公里）或时间（飞行2小时）。

社交网络中的边：在微信或微博中，好友关系通常是无向的（双向好友），但关注关系是有向的（单向关注）。边还可以有权重，如互动频率：每天聊天 vs 偶尔点赞。

边的多重性与自环

• **多重边（Multiple Edges）**：两个节点间有多条边，表示不同类型的关系。例如，两个人既是同事又是邻居，可画两条边（但通常用一条带权边或标签边简化）。
• **自环（Self-loop）**：边连接节点到自身，表示节点与自身的关系。例如，在知识图中，一个概念指向自身表示循环定义；在社交网络，用户自己关注自己（罕见但可能）。简单图（Simple Graph）通常不允许自环和多重边，但复杂图可以。

实践案例：绘制你的家庭关系图 1. 列出家庭成员：爸爸、妈妈、你、兄弟姐妹（如有）。 2. 确定关系：父母与子女是无向边（相互），但如果你认为“孩子依赖父母”有方向，可尝试有向边（从孩子指向父母表示依赖）。 3. 用Mermaid代码绘制： ```mermaid graph LR F[爸爸] --- M[妈妈] F --- C[我] M --- C C --> F C --> M ``` 这里，`---` 是无向边（夫妻关系），`-->` 是有向边（孩子指向父母表示依赖）。这展示了混合边类型，但通常家庭关系视为无向图。

有向图 vs 无向图：方向的重要性

方向决定了图的对称性和应用。无向图假设关系双向等价，适合表示对称关系（如道路、 undirected friendship）。有向图允许不对称关系，适合表示流动、影响或单向连接（如网络流量、引用、关注）。

对比分析： | 特性 | 无向图 | 有向图 | |------|--------|--------| | 边表示 | 无序对 $\{u, v\}$ | 有序对 $(u, v)$ | | 对称性 | 边 $(u,v)$ 和 $(v,u)$ 等价 | 边 $(u,v)$ 和 $(v,u)$ 不同 | | 邻接矩阵 | 对称矩阵：$A[i][j] = A[j][i]$ | 一般不对称 | | 度计算 | 度（Degree）：邻接行和 | 出度（Out-degree）：源行和；入度（In-degree）：源列和 | | 典型应用 | 社交好友、物理网络、分子结构 | 互联网链接、引用网络、交通流 | | 遍历难度 | 相对简单，双向可达 | 可能单向，强连通分量重要 |

数学细节：在无向图中，节点 $v$ 的度 $\deg(v) = \sum_{u \in V} A[v][u]$。在有向图中，出度 $\deg^{out}(v) = \sum_{u \in V} A[v][u]$，入度 $\deg^{in}(v) = \sum_{u \in V} A[u][v]$。例如，一个节点有出度3、入度2，表示它指向3个节点，被2个节点指向。

案例：互联网 vs 友谊网络

• 互联网：网页A链接到网页B，但B不一定链接回A，是有向图。Google PageRank算法利用有向图的入度计算重要性。
• 友谊网络（如Facebook好友）：好友关系双向，通常建模为无向图。但注意：现实中“好友”可能不对等（A加B为好友，B未通过），但平台通常强制双向，所以近似无向。

混合图：实际中，图可能同时包含有向和无向边。例如，交通网络：高速公路有向（单行道），普通道路无向。在表示时，可统一用有向图（无向边用双向有向边代替），但会增加复杂度。

图的表示方法：邻接矩阵与邻接表

如何用计算机存储和处理图？两种主流方法：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。它们各有优劣，适用于不同场景。

邻接矩阵（Adjacency Matrix）

邻接矩阵是一个 $n \times n$ 的二维数组（$n = |V|$），其中元素 $A[i][j]$ 表示节点 $i$ 和 $j$ 之间是否存在边。对于无权图，$A[i][j] = 1$ 如果有边，否则 $0$；对于带权图，$A[i][j] = w$ 权重，或 $\infty$ 表示无边。

示例：四个节点的无向图，节点0、1、2、3，边：0-1, 0-2, 1-2, 2-3。 邻接矩阵： $$ A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} $$ 由于无向，矩阵对称（$A[i][j] = A[j][i]$）。

优点：

• **快速边查询**：检查边 $(i,j)$ 是否存在只需 $O(1)$ 时间（直接访问 $A[i][j]$）。
• **简单实现**：易于编码和数学操作（如矩阵乘法用于图卷积）。
• **适合稠密图**：当边数 $m$ 接近 $n^2$ 时，空间开销相对小。

缺点：

• **空间复杂度高**：$O(n^2)$，即使图很稀疏（边很少），也需分配 $n^2$ 空间。例如，社交网络有百万用户，但每人平均好友几百，$n^2$ 会达 $10^{12}$，不可行。
• **遍历邻居低效**：要找到节点 $i$ 的所有邻居，需扫描整行 $A[i]$，时间 $O(n)$，即使邻居很少。

代码示例（Python）： ```python class GraphMatrix: def __init__(self, n): self.n = n self.matrix = [[0] * n for _ in range(n)] # 初始化n x n零矩阵

def add_edge(self, u, v, weight=1): self.matrix[u][v] = weight

无向图需对称赋值

self.matrix[v][u] = weight

def has_edge(self, u, v): return self.matrix[u][v] != 0

def neighbors(self, u):

返回所有邻居节点

return [v for v in range(self.n) if self.matrix[u][v] != 0]

使用示例

g = GraphMatrix(4) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 3) print(g.neighbors(2)) # 输出: [0, 1, 3] ```

邻接表（Adjacency List）

邻接表为每个节点维护一个列表（或集合、字典），存储其相邻节点。通常用数组/字典 of lists 实现。对于带权图，列表元素可为 (邻居, 权重) 对。

示例：同上图，邻接表： ``` 0: [1, 2] 1: [0, 2] 2: [0, 1, 3] 3: [2] ``` 节点0的邻居是1和2，等等。

优点：

• **空间高效**：空间复杂度 $O(n + m)$，仅存储实际边。稀疏图（$m \ll n^2$）下显著节省内存。
• **遍历邻居快速**：获取节点 $u$ 的所有邻居只需访问其列表，时间 $O(\deg(u))$，通常远小于 $O(n)$。
• **灵活扩展**：易于添加边、节点，支持动态图。

缺点：

• **边查询较慢**：检查边 $(u,v)$ 是否存在需遍历 $u$ 的列表，时间 $O(\deg(u))$。最坏情况 $O(n)$，但平均好于矩阵。
• **不直接支持矩阵运算**：某些图算法（如矩阵乘法）需先转换为矩阵。

代码示例（Python）： ```python class GraphList: def __init__(self): self.adj = {} # 字典：节点 -> 邻居列表

def add_node(self, u): if u not in self.adj: self.adj[u] = []

def add_edge(self, u, v, weight=None, directed=False): self.add_node(u) self.add_node(v) if weight is not None: self.adj[u].append((v, weight)) else: self.adj[u].append(v) if not directed:

无向图添加反向边

if weight is not None: self.adj[v].append((u, weight)) else: self.adj[v].append(u)

def neighbors(self, u): return self.adj.get(u, [])

def has_edge(self, u, v): for neighbor in self.adj.get(u, []): if neighbor == v or (isinstance(neighbor, tuple) and neighbor[0] == v): return True return False

使用示例

g = GraphList() g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 3) print(g.neighbors(2)) # 输出: [0, 1, 3] ```

对比总结与选择指南

| 维度 | 邻接矩阵 | 邻接表 | |------|----------|--------| | 空间复杂度 | $O(n^2)$ | $O(n + m)$ | | 边查询时间 | $O(1)$ | $O(\deg(u))$ | | 遍历邻居时间 | $O(n)$ | $O(\deg(u))$ | | 添加/删除边 | $O(1)$ | $O(1)$（若列表无序）或 $O(\deg(u))$（保持有序） | | 适合图类型 | 稠密图（$m \approx n^2$）、小图（$n < 10^3$） | 稀疏图（$m \ll n^2$）、大图（$n$ 大） | | 典型应用 | 社交网络小规模分析、图卷积层（GCN）内部计算 | 大规模社交网络、互联网图、推荐系统 |

实践建议：在真实图神经网络中，输入数据常以邻接表或稀疏矩阵（如SciPy的`csr_matrix`）存储，以节省内存。邻接矩阵仅在图很小或需要密集矩阵运算时使用。

练习：绘制你的社交关系图 1. 列出节点：写下至少5个你的朋友或家人名字，作为节点。 2. 定义边：确定关系类型。如果是好友（双向），用无向边；如果是关注（单向），用有向边。可选：为边添加权重，如互动频率（1-5分）。 3. 选择表示方法：

• 尝试用邻接矩阵：创建一个表格，行和列都是朋友名字，交叉格填1（有连接）或0（无）。
• 尝试用邻接表：为每个朋友写一个列表，列出他们的朋友。

4. 可视化：用Mermaid代