Welcome to the World of Graph Neural Networks / 欢迎来到图神经网络的世界

你有没有过这种经历：早上刷朋友圈，看到你那个大学时期就天天泡奶茶店的同学，点赞了一家新开在写字楼楼下的珍珠奶茶店，下午打开外卖APP，首页推荐位就出现了这家店的「珍珠双拼加芋圆」，旁边还标着「你的好友也喜欢」？你第一反应可能是「这APP是不是偷听我说话了？」，但其实没那么玄乎——这是推荐系统「看」到了你和那位同学之间的社交连接关系，而这种能对「连接关系」进行推理的核心技术之一，就是我们今天要聊的图神经网络（Graph Neural Network，简称GNN）。

再比如你赶早高峰坐地铁，APP给你规划的换乘路线避开了人最多的1号线换乘站，为什么？因为它不仅知道哪条线挤，还知道各个换乘站之间的连接关系，知道哪个站的人会流向下一个站，这种对「连接关系」的推理，也是GNN的拿手好戏。甚至你问智能音箱「周杰伦的歌有哪些？」，它能回答出《晴天》是2007年专辑《我很忙》里的歌，还能关联出同专辑的《青花瓷》，这背后知识图谱的推理，也离不开GNN的支持。

可以说，我们每天都生活在「图」的世界里，只是之前没意识到而已。

1.1 无处不在的「图」：从社交网络到分子结构，万物皆可表示为图

提到「图」，你可能首先想到的是数学课上的函数图像、几何里的点线图，但在计算机领域，「图（Graph）」是一种非常通用的数据结构，专门用来表示实体之间的连接关系。它的结构特别简单，只有两种核心元素：

• **节点（Node / Vertex）**：也就是图里的「实体」，比如社交网络里的用户、地铁线路里的站点、分子结构里的原子、知识图谱里的「周杰伦」「晴天」这些概念；
• **边（Edge）**：也就是连接两个实体的「关系」，比如用户之间的好友关系、站点之间的线路连接、原子之间的化学键、实体之间的「演唱」「所属专辑」这类关系。

你可以把图理解成一个超级简单的「关系网」：每个节点是一个点，边是连接这些点的线，点和线都可以有自己的属性。比如社交网络里的节点（用户）有年龄、性别、消费偏好这些属性，边（好友关系）有认识时间、互动频率这些属性。

为了让你更直观地理解，我们来看一个最简单的社交网络例子：假设有5个用户Alice、Bob、Charlie、David、Eva，他们的好友关系是这样的：Alice和Bob、Charlie是好友，Bob和David是好友，Charlie和Eva是好友，David和Eva是好友。这个关系网用图表示就是下面这个样子：

```mermaid graph TD A[Alice] --- B[Bob] A --- C[Charlie] B --- D[David] C --- E[Eva] D --- E style A fill:#skyblue,stroke:#333,stroke-width:2px style B fill:#skyblue,stroke:#333,stroke-width:2px style C fill:#skyblue,stroke:#333,stroke-width:2px style D fill:#skyblue,stroke:#333,stroke-width:2px style E fill:#skyblue,stroke:#333,stroke-width:2px ```

这种结构是不是特别像你微信里的好友关系网？甚至比好友网更复杂：你还可以给节点加属性，比如Alice是25岁的互联网从业者，喜欢喝奶茶；给边加属性，比如Alice和Bob是认识3年的大学同学，每周互动5次。这就是图的通用性：任何能表示为「实体+关系」的场景，都能用图来建模。

除了社交网络，你能想到的所有有连接关系的场景，几乎都能用图表示：

• 地铁线路：站点是节点，线路连接是边，换乘站就是连接多条边的节点；
• 美食推荐系统：用户是节点，美食是节点，用户吃过某家店就是用户节点和美食节点之间的一条边；
• 分子结构：原子是节点，化学键是边，药物的分子结构就是一张天然的图；
• 知识图谱：实体（人、地点、事件）是节点，实体之间的关系是边，比如「马云-创始人-阿里巴巴」就是一条从「马云」到「阿里巴巴」的边，标签是「创始人」；
• 甚至代码的调用关系、论文的引用关系、交通路网的路线，都能用图来表示。

> 💡 小贴士：你可以现在就拿出手机，打开你的微信好友列表，试着把你和你好友的关系画成一张图，你会发现哪怕只有10个好友，画出来的图就已经有很复杂的连接关系了——这就是图的魅力，简单到只有点和线，却能表示无比复杂的现实世界。

在计算机里，我们通常用两种方式存储图： 1. 边列表（Edge List）：就像上面的好友关系，直接存所有的边，比如`[("Alice", "Bob"), ("Alice", "Charlie"), ...]`，适合存储稀疏的图（边比较少的图）； 2. 邻接矩阵（Adjacency Matrix）：用一个$N \times N$的矩阵（$N$是节点数量）表示所有节点之间的连接关系，矩阵里的$A_{ij}=1$表示节点$i$和节点$j$之间有边，否则为0。比如上面的5个节点的社交网络，邻接矩阵就是： $$ A = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 &

$$ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

这个$5 \times 5$的矩阵就是我们之前社交网络的邻接矩阵（Adjacency Matrix），矩阵的行和列都对应5个用户，$A_{ij}=1$表示第$i$个用户和第$j$个用户是好友，否则为0。你可以看到，邻接矩阵是一个对称矩阵——因为好友关系是双向的，Alice是Bob的好友，Bob也是Alice的好友，所以$A_{12}=A_{21}=1$。如果我们的图是有向图（比如微博的关注关系，你关注了某个博主，博主不一定关注你），邻接矩阵就不对称了。

如果好友关系有强度呢？比如Alice和Bob是每周互动10次的大学同学，Alice和Charlie是每年才见一次的远房亲戚，互动频率只有每周1次，我们可以把邻接矩阵里的0/1换成互动的权重，得到带权邻接矩阵（Weighted Adjacency Matrix），这样图不仅能表示「有没有连接」，还能表示「连接的强弱」。

邻接矩阵的好处是计算非常方便：比如要算每个用户的好友数量（也就是图的「度（Degree）」），只需要对邻接矩阵的每一行求和就行——Alice的度是2，Bob的度是2，所有节点的度都是2，这张图是一张规则的环形图。但如果是真实的社交网络，大V的好友数量可能是百万级，普通用户的好友数量可能只有几十，邻接矩阵就会变得非常稀疏（大部分元素是0），这时候用边列表（Edge List）存储更省空间：我们只需要存所有存在的边，比如`[("Alice", "Bob", 10), ("Alice", "Charlie", 1), ...]`，第三个元素是边的权重，不需要存不存在的边，100万用户如果有1000万条好友关系，边列表只需要存1000万条数据，而邻接矩阵需要存100万*100万=1万亿个元素，差了4个数量级。

> 💡 小知识：为什么图数据被称为「非欧几里得数据（Non-Euclidean Data）」？ > 我们平时接触的图片、文本都属于「欧几里得数据」：图片是规则的二维网格，每个像素都有固定的(x,y)坐标；文本是一维的序列，每个词都有固定的位置索引，都可以用笛卡尔坐标系表示。但图没有这种规则的结构：节点没有固定的位置，没有固定的顺序，邻居数量也不固定，所以被称为「非欧几里得数据」，这也是传统神经网络无法直接处理图数据的核心原因。

---

1.2 传统神经网络的「阿喀琉斯之踵」：为什么CNN、RNN搞不定图数据？

你现在应该能感受到图的通用性了：任何有连接关系的数据都能用图表示。但问题来了——我们已经有这么强大的CNN（卷积神经网络）、RNN（循环神经网络）、Transformer了，为什么还要专门搞一个图神经网络（GNN）来处理图数据？

要回答这个问题，我们得先搞清楚CNN和RNN到底为什么能work，以及它们的核心假设是什么。

1.2.1 CNN：为网格数据而生的特征提取器

CNN最早是用来处理图片的，它的核心操作是卷积（Convolution）：用一个固定大小的卷积核（比如3x3的矩阵）在图片上滑动，每个位置和卷积核做矩阵乘法，提取局部特征。比如第一层卷积核可能提取边缘、角点这些低级特征，第二层卷积核提取纹理、形状这些中级特征，第三层提取猫脸、车轮这些高级特征。

CNN能work的核心前提是：输入数据是规则的网格结构。图片是二维网格，每个像素都有固定的上下左右4个（或8个）邻居，卷积核扫过每个位置的时候，感受野是固定的，提取的特征也是对齐的。哪怕你把输入图片里的像素顺序打乱，CNN提取的特征就会完全错乱，因为它默认了像素的网格位置是有意义的。

如果我们把图数据硬塞给CNN会怎么样？比如我们把社交网络里的用户按注册时间排序，排成一个一维序列，输入到CNN里。首先，用户的邻居数量差异极大：Alice有2个好友，微博大V可能有1000万个粉丝，你要把所有用户的邻居列表padding到同样的长度，要么浪费99%的计算资源在无效的0上，要么截断掉大部分邻居信息，丢失关键的连接关系；其次，用户的排序是任意的——你把用户按注册时间、按姓名拼音、按好友数量排序，得到的序列完全不同，CNN输出的结果也会天差地别，但图的连接关系完全没有变，这显然是无法接受的。

1.2.2 RNN/Transformer：为序列数据而生的时序建模器

RNN和Transformer是用来处理文本、语音这类序列数据的，它们的核心假设是：输入数据有固定的顺序，每个元素只和它前面的（或前后）元素有关系。比如文本里的词，顺序变了意思就完全变了：「我喜欢吃苹果」和「苹果喜欢吃我」是完全不同的句子。

如果我们把图数据当成序列输入给RNN会怎么样？比如我们把社交网络里的用户按好友数量排序，输入RNN。首先，图没有天然的顺序——你按好友数量排、按年龄排、按注册时间排，得到的序列都不一样，模型输出的结果也会不一样，但图的连接关系完全没变；其次，RNN只能捕捉相邻元素的关系，比如文本里相邻的词有关系，但图里距离很远的节点可能也有很强的关联，比如你和某个明星可能隔了10层好友关系，但RNN很难捕捉到这么远的依赖。

> 📖 纸书侧边栏：传统机器学习处理图数据的局限 > 在GNN出现之前，处理图数据主要靠传统机器学习方法：比如人工提取节点的特征（用户的年龄、好友数量、发言频率），然后用随机森林、SVM分类；或者用图论里的手工特征，比如节点的度、聚类系数、最短路径长度。但这种方法需要大量的人工特征工程，而且很难捕捉深层的连接关系，比如「诈骗分子的朋友的朋友是诈骗分子」这种多层的关系，传统方法几乎无法有效捕捉，效果非常有限。

1.2.3 图数据的特殊性：传统方法无法解决的三大痛点

总结下来，图数据有三大特性，是传统神经网络完全无法处理的： 1. 邻居数量不固定：节点的邻居数量从几个到几百万不等，没有固定的输入长度； 2. 结构无序性：图没有固定的节点顺序，节点的排列不会改变图的连接关系； 3. 连接关系复杂：节点之间的连接可以是多层的、动态的，深层的连接关系蕴含了大量的信息，传统方法无法有效捕捉。

而GNN，就是为了解决这三个痛点而生的。

---

1.3 GNN的核心思想：让节点「和邻居聊天」，自动学习特征

GNN的核心思想特别简单，用一句话就能说清楚：每个节点不仅看自己的特征，还会和所有邻居交换信息，聚合邻居的特征，更新自己的特征，重复这个过程多次，每个节点就能得到包含自身和所有深层邻居信息的特征。

我们再用之前的小区治安的例子来解释：你要判断一个小区的治安好不好，不会只看自己家的防盗门是不是牢固，还会问左邻右舍，左邻右舍再问他们的邻居，几轮问下来，你就能知道整个小区的治安情况，甚至能知道哪栋楼、哪个单元更安全。GNN就是这样的「问邻居」的过程，在学术上这个过程叫做消息传递（Message Passing），也叫邻居聚合（Neighborhood Aggregation）。

1.3.1 消息传递的三步走

我们用一个具体的例子来理解消息传递的过程：假设我们要判断社交网络里的用户是不是羊毛党（专门薅商家优惠券的用户），每个用户的初始特征有3个：注册时长（天）、历史消费金额（元）、发言频率（次/天）。 1. 消息发送：每个节点把自己的初始特征作为「消息」，发送给所有直接相连的邻居。比如Alice给Bob和Charlie发自己的特征，Bob给Alice和David发自己的特征。 2. 消息聚合：每个节点收到所有邻居发过来的消息，做一个聚合操作，把邻居的特征合并成一个向量。最常见的聚合操作有三种：

• **求和（Sum）**：把所有邻居的特征加起来，适合捕捉邻居的总特征，比如一个用户的所有好友的总消费金额；
• **平均（Average）**：把所有邻居的特征求平均，适合捕捉邻居的平均特征，比如一个用户的好友的平均消费金额；
• **最大值（Max）**：取所有邻居特征里的最大值，适合捕捉邻居里最显著的特征，比如一个用户的好友里消费最高的那个人的消费金额。

3. 特征更新：把聚合后的邻居特征和节点自身的初始特征合并，经过一个线性变换（就是矩阵乘法，后面第3章会详细讲），得到节点更新后的特征。

这个「发送-聚合-更新」的过程就是一轮消息传递，我们可以重复这个过程多次：比如做3轮消息传递，每个节点的特征就会包含它自己和3层以内的所有邻居的信息——比如Alice的特征会包含Alice自己、她的好友Bob和Charlie、Bob的好友David、Charlie的好友Eva的信息，相当于Alice已经「问过」了所有距离她3步以内的用户的情况。

1.3.2 消息传递的直观演示

我们用下面的图来演示一轮消息传递的过程：

```mermaid graph LR A[Alice<br>特征：[30, 500, 5]] -->|发送消息| B[Bob<br>初始特征：[25, 1200, 2]] C[Charlie<br>特征：[28, 300, 8]] -->|发送消息| B D[David<br>特征：[32, 800, 3]] -->|发送消息| B B -->|聚合邻居消息+自身特征<br>聚合方式：平均| E[Bob更新后特征<br>[31.67, 666.67, 4.33]] style A fill:#f9f,stroke:#333,stroke-width:2px style C fill:#f9f,stroke:#333,stroke-width:2px style D fill:#f9f,stroke:#333,stroke-width:2px style B fill:#9f9,stroke:#333,stroke-width:2px style E fill:#99f,stroke:#333,stroke-width:2px ```

Bob的初始特征是`[25, 1200, 2]`，也就是25岁，消费1200元，发言频率2次/天。他收到了Alice、Charlie、David三个邻居的消息，三个邻居的特征分别是`[30, 500, 5]`、`[28, 300, 8]`、`[32, 800, 3]`，用平均的方式聚合之后得到`[30, 500, 5]`，加上Bob自己的特征，再做一次线性变换，就得到了更新后的特征`[31.67, 666.67, 4.33]`，这个特征就包含了Bob自己和所有邻居的信息。

如果我们再做一轮消息传递，Bob会把更新后的特征发给Alice和David，Alice和David也会把自己的更新后的特征发给Bob，这样Bob的特征就会包含更远的邻居的信息，比如Charlie的好友Eva、David的好友Eva的信息，特征会越来越全面。

1.3.3 从消息传递到下游任务

当所有节点都经过多层消息传递之后，每个节点都会得到一个包含深层邻居信息的「节点嵌入（Node Embedding）」——也就是把节点的高维特征压缩成一个低维的向量，这个向量能充分代表节点的语义信息。有了这个节点嵌入，我们就可以做各种下游任务了：

• **节点分类**：比如判断用户是不是羊毛党、判断分子是不是有毒性；
• **链接预测**：比如预测社交网络里两个用户会不会成为好友、预测知识图谱里两个实体之间有没有关系；
• **图分类**：比如判断一个分子是不是能治疗癌症、判断一个代码片段是不是有漏洞；
• **聚类**：比如发现社交网络里的社群、发现分子里的功能基团。

补完之前未写完的邻接矩阵相关内容后，我们继续深入：如果你仔细观察那个5节点的社交网络邻接矩阵，会发现它是一个对称矩阵——因为微信好友关系是双向的，Alice是Bob的好友，Bob自然也是Alice的好友，所以矩阵中第1行第2列的元素和第2行第1列的元素都是1。如果是微博的关注关系这种有向图，邻接矩阵就会不对称：你关注了某个博主，博主不一定关注你，这时候$A_{ij}=1$只表示你关注了博主，$A_{ji}$可能是0。

除了邻接矩阵，图还有两个在GNN中频繁使用的矩阵，我们先简单做个了解，后面第3章讲数学基础时会详细展开： 1. 度矩阵（Degree Matrix, $D$）：一个对角矩阵，对角线上的元素$D_{ii}$是第$i$个节点的邻居数量，也就是「度」。比如Alice有2个好友，度就是2，Bob有2个好友，度也是2，刚才那个5节点社交网络的度矩阵就是： $$ D = \begin{bmatrix} 2 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 2 \end{bmatrix} $$ 2. 拉普拉斯矩阵（Laplacian Matrix, $L$）：定义为度矩阵减去邻接矩阵，即$L = D - A$，它是图卷积运算的核心矩阵，后面讲GCN的时候会反复用到。

如果边有权重呢？比如Alice和Bob是每周互动10次的大学同学，Alice和Charlie是每年才见一次的远房亲戚，互动频率只有每周1次，我们可以把邻接矩阵里的0/1换成互动的权重，得到带权邻接矩阵，这时候度矩阵的元素就是对应节点所有边的权重之和，拉普拉斯矩阵的定义也依然成立。这就是图的灵活性：不仅能表示「有没有连接」，还能表示「连接的强弱」。

> 📖 纸书侧