图采样方法有哪些？｜阿里巴巴算法面经解析

60 秒回答模板

可以从三个层次回答。第一，图采样的目的，是在大图上降低计算、存储和消息传递开销，同时尽量保持节点分布、边分布、局部邻域、连通性和任务相关信号。第二，按采样对象分类：节点采样直接抽节点，边采样抽边，随机游走抽路径，邻居采样限制每个节点的邻居数，层采样按 GNN 层级抽样，子图或簇采样抽一块连通结构，重要性采样按贡献大小调整概率，负采样构造不存在或未观察到的边作为训练对照。第三，比较取舍：节点和边采样简单但容易破坏连通性；随机游走保留局部结构但偏向高阶节点；邻居采样适合 mini-batch GNN 但方差会累积；层采样能控制每层规模但可能引入估计偏差；簇采样更好保留社区结构但依赖划分质量；重要性采样可降方差但需要合理估计权重；负采样影响链路预测和表示学习的判别边界。

考点 为什么需要图采样

主线 节点采样

易错点 只说随机采样，没有区分节点、边、路径、邻居、层和子图这…

深入解析

为什么需要图采样

真实图常常具有节点多、边多、度分布长尾、邻域爆炸等特点。以 GNN 为例，一个中心节点聚合一阶邻居，二层模型还要聚合邻居的邻居，层数增加后计算量会快速膨胀。图采样的目标不是随便丢数据，而是在预算受限时获得对原图统计特性或训练目标的近似。好的采样需要兼顾效率、代表性、连通性和任务相关性。

节点采样

节点采样是从原始图结构里选择一部分节点，再保留这些节点之间的诱导边。最简单的是均匀节点采样，每个节点被选中的概率相同；也可以按度、PageRank、类别、活跃度或任务权重进行非均匀采样。优点是实现简单、适合估计节点属性分布；缺点是容易打断边结构，尤其在稀疏图结构里，采到的节点之间可能没有足够边，导致连通性差。

边采样

边采样是直接从边集合中抽取部分边，保留边两端的节点。它适合关注关系、链路、交互记录的任务，也常用于减少图卷积中的消息传递边数。均匀边采样简单，但对高度节点更友好，因为高度节点连接的边更多，被保留下来的概率自然更大。边采样通常比节点采样更能保留局部连接，但可能产生很多零散节点或破坏高阶结构。

随机游走采样

随机游走从某个起点出发，按边转移到邻居，连续得到路径或路径诱导子图。DeepWalk、node2vec、PinSAGE 等思想都与随机游走相关。它的优势是能保留局部邻近性、路径上下文和社区结构，适合表示学习、相似节点发现和大图局部采样。主要问题是存在度偏差：高度节点更容易被访问；游走太短会局限在局部，游走太长可能混入噪声或趋向平稳分布。

邻居采样

邻居采样是 GNN 中非常常见的方法。对一个 mini-batch 的目标节点，每一层只采固定数量的邻居，例如每个节点采 10 个一阶邻居、再为这些邻居各采 5 个二阶邻居。GraphSAGE 是典型代表。优点是直接控制计算图规模，让大图训练可扩展；缺点是采样带来方差，层数越多，采样噪声可能越明显。

层采样

层采样不是以每个节点为中心独立扩展邻居，而是在 GNN 的每一层采一批节点或邻接关系，用这些采样结果近似整层的聚合。FastGCN 将图卷积看作积分估计，按节点重要性采样；LADIES 进一步让下一层采样依赖上一层，减少无关节点。层采样能缓解邻居采样的指数膨胀，但估计设计更复杂。

子图与簇采样

子图采样一次抽取一块节点和边组成的小图，再在小图上训练或挖掘。簇采样先把大图划分为多个簇或社区，每次采一个或多个簇，例如 Cluster-GCN。GraphSAINT 则可以通过节点、边、随机游走等方式采样子图，并用归一化权重修正偏差。子图采样的优点是保留局部连通性和社区结构，训练时可以复用子图内边。

重要性采样

重要性采样不是一种固定对象，而是一类思想：让贡献更大的节点、边或邻居以更高概率被采到，并在估计时用权重修正。重要性可以来自度、归一化邻接权重、注意力分数、历史梯度、PageRank、任务损失或业务先验。它的价值是降低方差、提高有效样本比例；风险是如果重要性估计不准，会引入新的偏差。

负采样

负采样常用于链路预测、知识图谱补全、推荐图和图对比学习。它通常不是为了缩小原图结构，而是为了构造训练目标：给定正边，再采一些不存在或未观察到的边作为负例。常见做法包括均匀负采样、按节点度采样、困难负样本采样、类型约束负采样等。负采样质量会直接影响模型学到的决策边界。

易错点

只说随机采样，没有区分节点、边、路径、邻居、层和子图这些不同粒度。
忽略采样带来的偏差和方差，以为样本越多一定越好。
没有说明随机游走和边采样天然更偏向高度节点。
把负采样和普通子图采样混为一谈，忽略它主要用于构造训练目标。
只关注计算加速，不讨论连通性、社区结构和任务相关信号是否被保留。
认为某一种方法通用最优，而没有结合节点分类、链路预测、推荐或表示学习等任务场景分析。

面试官追问

随机游走采样为什么会偏向高度节点？

因为高度节点连接的边更多，从邻居转移时更容易被走到。对于无权无向连通图，简单随机游走的平稳访问概率与节点度成正比，所以高度节点出现频率更高。这种偏差有时有利于捕捉核心结构，但会削弱低度节点表示。

邻居采样和层采样有什么区别？

邻居采样通常以目标节点为中心逐层向外采固定数量邻居，控制每个节点的 fanout；层采样则从整层角度采一批节点或边来近似该层聚合。邻居采样直观、实现常见，但多层时采样规模和噪声会累积；层采样更关注全层估计效率，但需要更精细的概率设计。

Cluster-GCN 类方法为什么有效？

它利用图的社区性，把大图划分成若干簇，每次在一个或几个簇上训练。这样 mini-batch 内部保留了较多真实边，消息传递更完整，计算也更集中。它的问题是跨簇边可能被弱化，如果图没有明显社区结构或划分质量差，效果会下降。

负采样是不是图采样的一种？

广义上可以算与图学习相关的采样，但它的目的不同。节点、边、邻居、子图采样主要是为了近似原图计算或保留结构；负采样主要是为了构造训练对照样本，常用于链路预测、推荐和对比学习。它影响的是监督信号和判别难度，而不只是计算规模。

如何判断采样方法是否合适？

可以从四个方面判断：训练是否能在预算内完成，采样后节点和边分布是否严重偏移，关键结构是否被保留，最终任务指标是否稳定。还要观察不同随机种子下的波动。如果模型性能高度依赖某次采样，说明方差可能过大。