你有没有想过这样一个场景：你要给一个班级的学生发糖果，但糖果数量有限，每天只能发30颗。班里有100个学生，怎么分配才公平又有效？

一种办法是每天固定发给同样30个学生，简单省事,但剩下70个学生永远吃不到糖。另一种办法是每天重新抽签决定给谁，公平是公平了，但抽签这件事本身也要花时间和精力，抽的次数多了,这个"抽签成本"甚至可能比糖果本身更贵。

图神经网络（GNN）的训练，正面临一个几乎一模一样的难题。

**节点和边,谁来传递消息**

图神经网络是什么？简单说，它是一种专门处理"关系数据"的深度学习模型。比如社交网络里谁和谁是好友、论文引用网络里谁引用了谁，这些数据天然长成图的样子，有节点（比如一个人、一篇论文），也有边（连接两个节点的关系）。

GNN工作的核心机制叫消息传递：每个节点会把自己的信息,沿着边,传给邻居节点，邻居收到之后再综合处理，更新自己的表示。这个过程一层层叠加，节点就能"看到"越来越远的邻居的信息。

但这里就有个麻烦事。如果一张图有几百万个节点、几千万条边，每一轮训练都要让所有这些边都参与消息传递，计算量会大到吓人。

一个真实的例子是Reddit数据集，23.3万个节点,1160万条边。有一种叫ASGCN的采样方法，为了决定"这一轮该用哪些边",花了20.7秒,而真正做模型计算（前向加反向传播）只用了3.5秒。

**决定用哪些边,比用这些边本身更费时间**

这句话听起来有点荒谬，但确实是现实。

**稀疏化,是指人为地删掉一部分边，只保留一部分用来训练，这样能减少计算量,但问题是,到底删哪些边、留哪些边,这件事本身也要耗费计算资源,甚至可能比训练本身更贵。**

面对这个矛盾，研究者们大致走了两条路。

第一条路是"一次性稀疏化"：把图稀疏化一次，然后整个训练过程都用这张固定的稀疏图。好处是省事，省时间，但坏处也很明显,模型从头到尾只能看到图的一个固定局部，很多信息永远被排除在外。这就像前面说的糖果问题里,每天固定发给同样30个学生的做法。

第二条路是"每轮重新采样"：比如GraphSAINT每个epoch都重新抽一个子图出来训练，或者SpanGNN逐步增长一个生成树，又或者GERN每次都随机生成一棵全新的生成树。这条路更灵活，模型能见到更多样的图结构，但代价是每一轮都要重新计算一遍"该怎么采样"，这个开销累积起来相当惊人。

这篇论文的作者们意识到，这两条路其实都没有真正解开矛盾的核心,他们都把"决定用哪些边"和"每一轮实际用哪些边"这两件事绑在了一起。

于是他们提出了一个新框架,叫EDiS（Edge-Disjoint Subgraph sparsification framework，边不相交子图稀疏化框架）。

**EDiS**：一种把图分解和训练解耦的稀疏化框架，核心思路是先把原图切成互不重叠的若干个子图并缓存起来，之后每一轮训练只需要从这些缓存里重新组合出一张训练图，而不需要每次都重新计算"该选哪些边"。

回到糖果问题的类比。EDiS的做法相当于：提前把100个学生按某种规则分成若干个小组,一次性分好,然后每天根据哪个小组"分数"更高,优先把糖果分给对应小组的学生，分完一组不够再从下一组补,直到凑够30颗。分组这件事只做一次，但每天具体发给谁可以不一样。这样既不用每天重新分组（省了"抽签"的成本），又不会每天都发给完全相同的人（避免了只喂饱固定30人的问题）。

**图怎么被切成一块一块的**

EDiS的核心操作分成两个阶段：一次性的分解（Decomposition），和每一轮训练时的组合（Composition）。

分解阶段只做一次。它先给图里每一条边打一个分数，默认用的是节点特征之间的余弦相似度。

**余弦相似度**：衡量两个向量方向是否接近的一种指标，取值在0到1之间（这里做了偏移处理），数值越高说明两个节点的特征越相似。

打完分之后，EDiS用一种叫"最大得分覆盖森林"（MaxCF）的方法，从所有边里挑出一批得分总和最高、同时能保持图连通性的边，组成第一个子图。然后把这些边从图里拿掉，剩下的边里再挑一批同样性质的边，组成第二个子图。如此反复，直到达到设定的轮数上限，剩下没被选中的边则归入一个"剩余池"。

**覆盖森林**：一种不含环路、但能连接图中每个连通部分的边集合，类似于给图搭一个"骨架",保证信息能在图的各个角落之间流通，但又不浪费边去形成多余的循环。

这个过程的结果，是把原图切成了K个互不重叠的子图,外加一个剩余边池。每个子图还会被赋予一个权重,等于这个子图里所有边的得分总和。这个分解只做一次,之后不管训练多少轮,不管想用多大的边预算，都不需要重新切。

这里有个细节值得琢磨。为什么要反复提取"最大得分森林"，而不是简单地把边按分数从高到低排序，直接切成K段？

答案在于连通性。如果单纯按分数切割，得分最高的那一批边很可能全部集中在图的某个局部区域（比如一群联系紧密的朋友），而忽略了图的其他部分。覆盖森林的要求保证了每一轮提取出来的子图,都能摸到图的每一个连通组件,不会漏掉任何一块区域。这就像前面分组的类比里，如果你只按"成绩最好"来分组，可能第一组全是尖子生，后面几组质量参差不齐；但如果你要求"每组都要覆盖所有班级",那每组都得兼顾各方面的学生,结构上更均衡。

**每一轮训练,图是怎么拼出来的**

分解好之后，到了真正训练的阶段，每个epoch需要组合出一张边数恰好等于预算B的图。这个过程是这样的：

先按子图的权重做一次加权随机排序，权重越高的子图越容易排在前面（但不是绝对的，仍有随机性）。然后按这个顺序，把子图一个一个加进来，直到边数达到或超过预算。如果超过了，就从权重最低的那个子图开始删，删完整个子图还不够,就从下一个权重稍高的子图里随机削减一部分，直到刚好凑够。如果子图全部加完还不够预算,就从剩余边池里随机补齐。

这个设计有一个很巧妙的地方：权重高的子图几乎总是整个保留的,只有一个子图会被部分裁剪。这意味着,得分最高、结构最重要的那部分骨架,大概率会被完整地保留在每一轮的训练图里，而变化主要发生在"要不要用某个权重较低的子图,以及用多少"这个层面上。

**这不是说每一轮用的图都完全一样。恰恰相反，正是因为排序是随机的、裁剪对象是动态变化的，不同epoch看到的训练图通常是不同的。**

想象一下这个场景：你是一个厨师，每天要给顾客做一份套餐，预算是30元。你手上有几种固定搭配好的"菜品组合包"，每个包的总价不同。你会优先把贵的组合包（代表更重要的食材搭配）放进套餐里，如果超预算了，就先去掉便宜的组合包，实在不够再从一个组合包里单独拿掉几样菜。这样一来，顾客每天吃到的套餐构成会有变化，但核心的"硬菜"几乎总是在的。如果你每天都严格按固定顺序取最贵的几个组合包，不做任何随机打乱，那每天的套餐几乎一模一样，顾客很快就会吃腻,这正是论文里提到的"确定性方案会导致epoch之间的多样性崩塌"的问题所在。

**理论保证：被切掉的边,信息真的会丢失吗**

讲到这里，一个自然的疑问是：既然每一轮用的边不一样，那被排除在外的那些边,它们携带的信息不就彻底损失了吗?

论文在这里给出了两层理论分析，这也是整篇论文比较硬核的部分。

第一层叫"分数阈值割保留定理"。简单说，对于图里任何一个"切割"（也就是把图的节点分成两堆，中间连接两堆的边叫跨越边），只要你保留的子图数量够多，那些得分较高的跨越边，大概率会继续出现在你保留的子图联合体里。

**割（Cut）**：图论中的一个概念，指把图的节点集合分成两部分后，连接这两部分的那些边。割的大小通常反映了这两部分之间信息交流的"带宽"。

这个结论的直观意义是，图里真正重要的连接通道（跨越某个割的高分边）不会因为分解过程而被系统性地抹掉，只要你保留的子图数量足够。

第二层叫"组合后保留概率"，这是一个更贴近实际使用场景的保证，因为前面那个定理针对的是"完整保留前k个子图"的理想情况，但实际训练时每一轮都可能裁剪、丢弃部分子图。论文证明了,哪怕考虑到这种裁剪和随机性，某个重要割上至少保留一条高分边的概率，仍然有一个明确的下界，这个下界只取决于每个子图保留的比例和这个子图里有多少条高分跨越边。

这两个定理共同传达的信息是：EDiS的随机性不是盲目的赌博，而是一种"大概率保证关键信息不丢失"的受控随机。这就好比你把一支球队的核心球员分散安排在不同的轮换阵容里，每场比赛的具体阵容会变,但核心球员上场的概率始终很高，不会因为轮换就彻底消失。

**实验说话：19个数据集,17个对手**

理论说得再漂亮，终究要看实际效果。论文在19个节点分类任务的基准数据集上做了测试，覆盖同质图（节点倾向于和相似节点相连，比如论文引用网络）、异质图（节点倾向于和不同类型节点相连，比如某些社交网络）、以及大规模图（节点边数达到百万甚至千万级别）。

**同质图/异质图**：根据相连节点是否"相似"来区分图的类型。在同质图里,相邻节点往往属于同一类别（比如两篇互相引用的论文大概率研究方向相近）；在异质图里，相邻节点反而经常属于不同类别。这个区分很重要，因为不同类型的图上,图神经网络的行为可能大相径庭。

在保留30%边数的设定下，EDiS的轻量版本（EDiS-Lite，训练和推理都用稀疏图）在17个被排名的方法里，拿到了最高的平均分和最低的平均排名,平均排名2.53，相比表现最好的方法，平均差距只有1.25个百分点。

这个数字意味着什么?17个方法参与排名，EDiS-Lite几乎总是排在前几名，没有在某个数据集上严重拉胯，又在很多数据集上领先。相比之下，有些对手方法比如Unified-LTH的平均排名是11.87，差距达到6.65个百分点，这个差距可不小。

论文还设计了一个EDiS-Full版本，训练阶段仍然用稀疏图，但推理（最终预测）阶段切换成完整的原图。这个版本在很多数据集上能明显弥补精度损失，比如在Cora数据集上，EDiS-Lite准确率是77.16%，切到完整图推理后能提升到84.08%，几乎追平独立调参的完整图GCN基准（84.26%）。但也不是所有数据集都这样，比如Chameleon数据集上，EDiS-Full（43.13%）反而略低于EDiS-Lite（43.75%），说明切换推理图不是万能药，具体效果要看图本身的结构。

**消融实验：拆开来看,到底是谁在起作用**

一个方法有效，不代表每个设计细节都有必要。论文做了一组对照实验，专门检验"结构化分解"和"每轮重采样"这两个核心机制,是不是真的各自都有贡献。

他们设置了三个对照组。第一个叫Frozen,整个训练过程只用一张固定采样出来的图,不做任何轮次间的变化。第二个叫Direct,直接按分数采样边,不经过"切子图"这个结构化步骤。第三个叫Shuffled groups,保留和EDiS一样的子图大小，但把边随机打乱重新分配到各个子图里,专门用来检验"子图内部的结构组织"到底有没有意义。

结果显示，在30%边预算这个设定下，EDiS相比Frozen,在14个数据集中的13个上表现更好；相比Direct，赢了11个；相比Shuffled groups,赢了12个。而且在边预算特别紧张的时候，这种领先优势最明显。

这个结果说明了一件事：光是"多看一些不同的边"（Direct能做到这点）还不够，光是"保持子图大小不变"（Shuffled groups能做到这点）也不够，真正起作用的,是把边按照某种结构性原则（比如覆盖森林）组织成子图，再配合轮次间的变化,这两者缺一不可。

**选择器和打分方式：换个方案会怎样**

EDiS的框架设计里有一个重要特点：决定"怎么切子图"的选择器（selector）和决定"怎么给边打分"的评分函数，是互相独立的模块,可以自由组合。

论文测试了七种不同的选择器（最大森林、最小森林、度数优先、k近邻、图稀疏器、随机、以及混合策略），和五种打分方式（余弦相似度、欧氏距离、点积、均匀打分、以及一个专门训练的小型神经网络打分器）。

结果是，没有哪一种组合在所有数据集上都是最优的,大部分组合之间的差距都在几个百分点以内。默认的"最大森林+余弦相似度"组合整体表现稳健，但不是绝对冠军。

比较有意思的一个发现出现在Minesweeper数据集上。用MLP（小型神经网络）打分器时,得分达到83.70（ROC-AUC指标），而默认的余弦相似度打分只有73.82，差了将近10个百分点，这个差距比其他任何数据集上两种打分方式的差距都大出至少六倍。这提示我们,对于某些特定图,打分方式的选择可能比选择器本身更关键，具体原因论文没有深挖，留给了后续研究。

**计算成本：省下来的时间去哪了**

既然EDiS的核心卖点是"分解只做一次,之后反复复用"，那它到底省了多少时间？

论文在五个大规模图上做了对比。以Reddit为例,在30%边预算下，EDiS一次性的分解构建大约需要313.7秒，但训练阶段（300个epoch）只需要518.7秒,总共832.4秒。相比之下,直接用完整图训练的Full-GCN需要713.4秒。

单看这个数字，EDiS反而更慢，这是因为分解这件事本身要耗时间，而300个epoch还没能把这个成本"摊平"。论文估算，大约480个epoch之后，EDiS的总耗时就会反超Full-GCN，而且如果同一份分解结果被用于多个不同的边预算设定（比如同时跑ρ=0.3和ρ=0.5两个实验），这个分解成本只需要付一次,摊得更快。论文给出的具体数字是，查询5个不同边预算时,相比每次都重新分解,EDiS能把累计构建时间压缩到五分之一。

这就好比你买了一台切菜机,第一次用之前要花时间组装调试,如果只切一顿饭的菜，可能还不如直接手切快。但如果你打算用它准备接下来一整周的饭菜,组装的那点时间很快就被后面省下来的时间覆盖了。

**提取深度的影响：切得越细越好吗**

论文还研究了一个参数,叫Kmax,也就是"最多切几个子图"这个上限。切得越多，意味着原本留在剩余池里的边被纳入了结构化子图,理论上应该让训练图更有章法。

但实验结果有点出乎意料：切得更深,不总是带来更好的效果。在五个大规模图上测试不同的Kmax值后发现，有些数据集受益于更深的切分,有些反而变差，而且用稀疏图推理和用完整图推理时,最优的切分深度还可能不一致。

更关键的是,一旦图的边已经在某个切分深度被耗尽（也就是没有剩余边可切了），再增大Kmax也不会有任何变化,因为提取过程早已经自然停止。论文发现，在实际测试的五个图中，有的在Kmax远未达到设定上限时就已经耗尽（比如ogbn-arxiv在43层就耗尽，而设定上限是320）,有的则一直切到了上限（比如Reddit和ogbn-proteins）。

有意思的是,尽管"最优Kmax"在不同数据集之间差异很大,但如果统一用一个折中值（比如Kmax=20），和各自的最优值相比,差距基本都在1个百分点以内。这说明这个参数虽然看起来重要,但实际调参压力不算大,不需要给每个数据集都精细调优。

Q&A

Q1：EDiS是什么？

A：EDiS是一种图神经网络训练框架，核心思路是把图的结构分解和每轮训练时的图组合这两件事分开处理。它先把原图一次性切成若干个互不重叠的子图并缓存，之后每一轮训练只需要从缓存里重新组合出一张符合预算的训练图，不用每次都重新计算该用哪些边。

Q2：EDiS和传统的图稀疏化方法有什么区别？

A：传统方法通常要么用一张固定的稀疏图训练到底（简单但缺乏多样性），要么每轮都重新采样（灵活但计算开销大）。EDiS把"分解"和"组合"拆成两步，分解只做一次并缓存，组合阶段轮次间可以变化，兼顾了效率和多样性，同时还给出了理论上的信息保留保证。

Q3：EDiS在实际测试中效果如何？

A：在19个节点分类数据集、对比17种基线方法的实验中，保留30%边数时，EDiS的轻量版本拿到了最高的平均分和最低的平均排名，平均排名2.53，与最优方法的平均差距仅1.25个百分点，在边预算紧张的场景下优势最明显。