第一章：世界的另一种语言——走进图的世界

想象这样一个场景：清晨，你被手机闹钟唤醒。睁开眼的第一件事，是查看社交媒体上的消息提醒——那些小红点背后，是一张由点赞、评论和转发织成的无形网络。出门前，你习惯性地查看天气预报，天气预报背后的气象站网络正在实时交换数据。乘坐地铁上班时，你的手机信号在不同基站间切换，而这些基站通过复杂的通信网络相互连接。午餐时间，你用外卖软件点了一份沙拉，推荐算法从你过去的点餐记录中推断出你今天的偏好——这套算法背后，是一张庞大的用户-商品关系图。

到了办公室，你打开电脑，开始处理堆积的邮件。每封邮件都涉及多个收件人，而这些人的组织关系又构成了一张层级森严的企业架构图。下午三点，你参加了一场关于项目风险的会议，项目经理用甘特图展示各项任务的依赖关系。晚上回到家，你躺在床上，准备刷一会儿视频入睡——屏幕上的推荐列表越来越懂你，因为算法已经学习了你与平台上数亿条内容之间形成的复杂交互图谱。

这一天，你从一个图的世界醒来，在图的包围中工作和生活，最终在一个由图构建的推荐系统中沉沉睡去。

This is not a scene from a science fiction novel. This is the reality we live in every day. We exist in a world where relationships matter as much as entities themselves. And in the language of computer science, the mathematical abstraction we use to capture these relationships is called the Graph—or in Chinese, we call it 图（tú）.

The Language of Connections: What Exactly Is a Graph?

The word "graph" carries different meanings in different contexts. In mathematics, a graph is a structure composed of a set of objects where some pairs of objects are connected by links. In data structures, a graph is a non-linear data type consisting of nodes (also called vertices) and edges (also called arcs or links) that connect pairs of nodes. In everyday language, when we say someone "graphed" something, we might mean they created a chart or diagram.

In this book, when we speak of graphs, we refer to the mathematical structure: a way of representing entities and the relationships between them. But we don't mean simple charts like bar graphs or pie charts. We mean relational structures—the kind that can capture the complexity of social networks, the intricacy of molecular bonds, or the vastness of the internet itself.

Let us begin with a formal definition, though we shall soon breathe life into it with examples.

> Definition (Graph): A graph $G$ is an ordered pair $G = (V, E)$ comprising a set $V$ of vertices (or nodes) together with a set $E$ of edges (or arcs), where each edge is a 2-element subset of $V$. In other words, an edge connects two vertices.

This definition, elegant in its brevity, captures the essence of what graphs represent. The set $V$ contains the actors in our relational world—who or what we are modeling. The set $E$ contains the actions—the connections, relationships, or interactions between these actors.

当我们第一次接触图的概念时，很容易将它与我们日常生活中常见的图表（如柱状图、折线图）混淆。这些图表确实在视觉上呈现为"图"的形式，但它们本质上是数据的可视化展示，而非图论意义上的图结构。真正图论意义上的图，关注的核心是关系本身——节点之间如何连接，以及这些连接意味着什么。

To understand this distinction more clearly, consider the difference between a organizational chart that shows who reports to whom, versus a line chart that shows a company's stock price over time. The organizational chart is a graph in the mathematical sense—it represents relationships between people. The line chart, while visually "graphical," is not a graph in the data structure sense—it merely visualizes a sequence of values.

The Anatomy of a Graph: Nodes and Edges

Every graph, regardless of its complexity, consists of two fundamental components. Let us examine each in turn.

节点（Node）, also called 顶点（Vertex）, are the individual units in a graph. They represent the entities in our system—the people in a social network, the cities in a transportation map, the proteins in a biological pathway, or the web pages on the internet. Each node typically has a unique identifier and may carry additional attributes that describe its properties.

In mathematical notation, if we have a graph $G = (V, E)$, then $V = \{v_1, v_2, v_3, ..., v_n\}$ represents the set of all nodes. The number of nodes, $|V|$, is called the order of the graph.

边（Edge） are the connections between nodes. They represent the relationships or interactions between entities. An edge connects two nodes (which may be the same node, in the case of self-loops, though these are less common in many applications). In a social network, an edge might represent a friendship; in a road network, an edge represents a road connecting two intersections.

Edges can also carry information. When an edge has an associated numerical value, we call it a weighted edge, and the value is the weight. In a transportation network, the weight might represent distance or travel time. In a social network, the weight might represent the strength of a relationship or the frequency of interaction.

The set of edges $E$ can be defined in different ways depending on whether multiple edges between the same pair of nodes are allowed:

• In a **simple graph**, at most one edge exists between each pair of vertices, and no self-loops exist.
• In a **multigraph**, multiple edges between the same pair of vertices are permitted.
• In a **pseudograph**, self-loops are allowed in addition to multiple edges.

For most applications in graph neural networks, we work with simple graphs or slight variations thereof, so we shall focus primarily on these cases.

The Nature of Connections: Directed vs. Undirected

One of the most fundamental distinctions in graph theory is whether the edges have a direction or not. This single property dramatically changes how we interpret and analyze the graph.

无向图（Undirected Graph） is a graph where edges have no orientation. If an edge connects node $A$ and node $B$, the relationship is symmetric—it doesn't matter which direction we consider. The edge $\{A, B\}$ is identical to the edge $\{B, A\}$.

现实世界中有许多关系本质上是无向的：友谊就是最典型的例子。如果Alice是Bob的朋友，那么Bob也必然是Alice的朋友。这种关系天然是对称的。地理位置的相邻关系也是无向的——如果城市A与城市B相邻，那么城市B也与城市A相邻。同事关系同样如此——如果Alice和Bob是同事，这种关系是相互的。

In a directed graph (or digraph), edges have a direction. We distinguish between an edge from $A$ to $B$ and an edge from $B$ to $A$. Directed edges are often represented as ordered pairs $(A, B)$ rather than unordered sets $\{A, B\}$.

有向图能够表达更为复杂的关系结构。Twitter上的关注关系就是典型——如果Alice关注了Bob，Bob可能并不回关Alice。网页之间的链接也是单向的——网页A链接到网页B并不意味着网页B也链接回网页A。在金融交易网络中，资金从A流向B是明确的单向流动。在城市交通系统中，单行道只能用有向来表示。

When edges have directions, we often use different terminology: the edge $(A, B)$ goes out of node $A$ and into node $B$. Node $A$ is the source or tail, and node $B$ is the target or head. In-degree of a node is the number of edges pointing to it; out-degree is the number of edges pointing from it.

It is worth noting that directed graphs can be converted to undirected graphs (and vice versa) through various transformations, depending on the application. For instance, if we want to represent mutual relationships, we might convert a directed graph to an undirected one by adding edges in both directions. Or we might analyze a directed graph while ignoring directions to study its "underlying undirected structure."

The Family of Graphs: Beyond Basic Types

Beyond the directed/undirected distinction, graphs come in many varieties, each suited to different kinds of problems.

有权图（Weighted Graph） assigns a numerical weight to each edge. These weights can represent costs, distances, capacities, or any quantity relevant to the application. A transportation network where edge weights represent travel times between cities is a weighted graph. A neural network where edge weights represent connection strengths is also a weighted graph (though with a different interpretation).

连通图（Connected Graph） is an undirected graph where there is a path between every pair of vertices. If we can reach any node from any other node by following edges, the graph is connected. In a disconnected graph, some nodes or groups of nodes are isolated from others. In graph theory, the connected components of a graph are maximal connected subgraphs—they cannot be further split while maintaining connectivity.

有环图与无环图（Cyclic vs. Acyclic Graph） distinguishes graphs that contain cycles from those that do not. A cycle exists when, starting from a node and following edges, we can return to the starting node without repeating any edges. Trees are a special case of acyclic graphs—connected graphs without cycles. Many algor