Diversity Curves for Graph Representation Learning¶

会议: NeurIPS 2026
arXiv: 2605.06466
代码: https://github.com/aidos-lab/diversity_curves/
领域: 自监督学习
关键词: 图表示学习, 结构多样性, 图粗化, 尺度感知表示, 边收缩池化

一句话总结¶

提出多样性曲线（Diversity Curves）框架，通过边收缩粗化多尺度跟踪图的测度空间散度（spread），构建兼具尺度鲁棒性、可解释性与高表达力的无监督图级几何表示。

研究背景与动机¶

理解图与图之间的结构差异是探索和区分复杂网络系统与图分布的核心基础。在生物信息学（如单细胞轨迹分析、酶结构比对）及几何网格处理中，同分布下采样的图往往具有相似的内在拓扑与局部规律，但节点规模（cardinality）却因实验采样或分辨率差异而剧烈波动。现有无监督图表示学习方案在此类场景下普遍面临严重的尺度敏感性瓶颈：传统的随机游走或路径核方法容易被大图庞大的词表与路径数主导；基于归一化拉普拉斯谱的谱嵌入（如 NetLSD、SpectralZoo）在跨密度与跨节点数时表征聚类能力急剧衰减；而对比学习范式的图神经网络（GNN）在无监督图级任务上高度依赖人工负采样与图数据增强，且对小样本或无标注几何结构缺乏严格的数学表达力保证。

这种失效的核心矛盾在于：既有几何测度与图拓扑不变量（如单尺度测度空间散度 spread 或持续同调 persistent homology）本身具备出色的等距同构不变性与几何可解释性，但其数值天然与输入点数强耦合，无法直接横向比较大小不同的图；若强行归一化节点数，又会抹杀图在不同缩放尺度下的多层次层次化聚类特征。同时，传统的节点聚合操作容易破坏连续流形几何，难以在降采样过程中系统保留结构多样性。

本文的切入角度是：不再试图在固定的原始尺度上强求尺寸无关的静态标量，而是将图粗化视为一种受控的多尺度探测器，系统性追踪图结构多样性随节点数递减时的动态演化轨迹。核心 idea：将多尺度边收缩粗化与度量空间散度（spread）结合构建多样性曲线（Diversity Curves），通过追踪图在不同粗化分辨率下的有效节点数演化，理论上证明边收缩提升图不变量的表达力，实现跨规模图结构的可解释无监督几何对比。

方法详解¶

整体框架¶

多样性曲线通过将任意输入图映射为一个固定维度的向量函数，刻画其在不同分辨率下的内在几何多样性。给定图 $G=(X,E)$ 与节点间测度 $d$（默认采用最短路径距离），方法首先确定一组全局对齐的评估基数集合 $\mathcal{I}=\{1, \dots, n_{\max}\}$。对于每个图，通过迭代边收缩粗化（下采样）或邻域克隆（上采样）将图变形到基数序列 $\{G_i\}_{i \in \mathcal{I}}$，在每个尺度计算其结构散度 $\text{Div}(G_i)$。为平滑单次随机收缩的偶然性，算法执行 $R$ 次重复并求均值，最终输出该图的多样性曲线向量 $\mathbf{v} \in \mathbb{R}^{|\mathcal{I}|}$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入图 G=(X,E)<br/>及指定测度 d"] --> B["多尺度粗化与采样<br/>迭代边收缩 / 节点上采样至基数 i"]
    B --> C["测度空间结构散度计算<br/>有效节点数 Div(G_i) 评估"]
    C --> D["连通分支坍缩校准<br/>基数低于连通数时线性插值"]
    D --> E["重复粗化均值汇聚<br/>R 次采样消除序列方差"]
    E --> F["输出多样性曲线向量<br/>DivCurve(G) 用于聚类与分类"]

关键设计¶

1. 多尺度边收缩粗化：精确控制基数并保全连通拓扑 为了克服现有池化操作不可逆或破坏全局连通性的缺陷，本文采用基于边收缩（edge contraction）的层级下采样机制。对于图 $G=(X,E)$ 与目标边 $e=(u,v) \in E$，收缩操作 $G/e$ 将节点 $v$ 合并入 $u$，删除自环与重边，并对合并节点的属性取均值。与节点聚类池化（如 DiffPool）相比，边收缩天然保全图的连通分支数量与粗粒度骨架，并支持逐节点精确递减图规模 $|G_i| = i$。对于基数低于目标维度的图，采用对称的节点邻域克隆上采样；而在实际工程实现中，边选择策略采用均匀随机排列边并迭代收缩无冲突独立边集，既消除了对计算开销巨大的边重要性贪心重算依赖，又通过多次重复平均保留了图结构的固有拓扑特征。

2. 测度空间散度计算：衡量几何有效节点数的等距不变量 为了在每个粗化尺度 $i$ 精确量化图的内在几何与拓扑多样性，本文引入测度空间散度（spread）作为核心不变量。给定度量空间 $(X,d)$，结构多样性定义为： $$ \text{Div}(G) := \sum_{x \in X} \frac{1}{\sum_{y \in X} \exp(-d(x,y))} $$ 该指标数值严格落入区间 $[1, |X|]$，直观表示图在测度 $d$ 下的“有效独立节点数”。若图为全连通且节点间距离极小，分母迅速累加导致 $\text{Div}(G) \to 1$；若图由完全孤立或远距离的簇组成，交叉指数项衰减至 0，$\text{Div}(G) \to |X|$。相比于同源的测度空间大小指标 magnitude（计算需矩阵求逆，复杂度 $\mathcal{O}(|X|^3)$），散度具有解析闭式、计算复杂度仅为 $\mathcal{O}(|X|^2)$、且天然具备节点置换与等距同构不变性（isometry invariance）。默认采用全源最短路径距离（shortest-path distance），兼顾全局测地线结构捕获与计算效率。

3. 连通分支坍缩理论与跨尺度对齐插值 多样性曲线的极限制约行为由连通分支数严格决定。理论上，包含 $c$ 个连通分支的任意图在经过充分边收缩后必然退化为 $c$ 个孤立节点的无边图 $K_c$，其散度精确等于分支数 $\text{Div}(K_c)=c$。特别地，对于任意连通图，当粗化至单节点时必然收敛至 $\text{Div}(K_1)=1$。针对含有多个连通分支（$c > 1$）而无法物理收缩至小于 $c$ 个节点的图，方法引入尺度校准：强制锚定 $\text{DivCurve}(G)_1 = 1$，并在基数 $i \in \{1, \dots, c-1\}$ 区间内进行确定性线性插值： $$ \text{DivCurve}(G)_i = i, \quad \forall i \in {1, \dots, c} $$ 这使得所有图在低基数端展现出严密的代数一致性，同时曲线在跨越 $c$ 时的转折斜率直接编码了图的全局连通性先验。

4. 边池化表达力增强理论：突破 1-WL 与单点散度局限 论文从理论上严格证明了结合边收缩粗化的动态多样性曲线严格比静态单尺度散度更具表达力。定义全部有效边收缩序列诱导的多重集，论文构造了多对反例：例如具有相同散度数值（$\approx 2.39$）的五节点图与 House 图，在收缩一条边后，前者仅能生成菱形图（散度 $\approx 2.02$），而后者能生成四环 $C_4$（散度 $\approx 2.14$），从而通过多样性曲线在尺度 $n-1$ 上的差值成功区分。进一步，散度与经典 1-WL 表达力不可比（散度能区分 1-WL 无法区分的 $C_3 \sqcup C_3$ 与 $C_6$）；而在结合边收缩后，多样性曲线甚至能够严格区分 1-WL 与单尺度散度均无法区分的同构难题图对（如带弦 6 环同构对），为无监督图表征提供了坚实的理论表达力保障。

损失函数 / 训练策略¶

多样性曲线是纯无监督、免训练的确定性/蒙特卡洛统计特征提取方法，无参数反向传播过程。算法核心超参数为重复粗化次数 $R$（默认设为 $R=3$）与评估尺度集合 $\mathcal{I}=\{1, \dots, n_{\max}\}$。单次随机粗化与全尺度评估的时间复杂度为 $\mathcal{O}(|E|(r + |X|) + |\mathcal{I}| \cdot n_{\max}^3)$，其中 $r$ 为独立集收缩轮数。在下游任务中，提取得到的曲线向量 $\mathbf{v} \in \mathbb{R}^{|\mathcal{I}|}$ 可直接送入 $k$NN、SVM（配合 RBF 核）进行分类，或通过 $L^2$ 距离计算轮廓系数（Silhouette Score）与 PCA 低维投影可视化。

实验关键数据¶

主实验¶

在随机图分布辨识主实验中，作者评估了模型区分 4 类不同随机图生成模型（Erdős-Rényi / ER, Random Partition / RP, Stochastic Block Model / SBM, Random Geometric / RG）的能力。每种分布在节点数 $n \in [10, 29]$ 内各生成 3 个样本，采用 10 折分层分组交叉验证（相同节点数归入同折，彻底排除尺寸泄露），采用 $k$NN 分类准确率和聚类轮廓系数（Silhouette Score）作为核心评估指标。

数据集 / 任务	评估指标	Diversity Curves (本文)	Kernel WL Opt. Assig.	Kernel Shortest Path	NetLSD	TopER
4类图分布辨识	Accuracy (↑)	0.90 ± 0.06	0.90 ± 0.05	0.77 ± 0.07	0.90 ± 0.03	0.70 ± 0.10
(ER, RP, RG, SBM)	Silhouette Score (↑)	0.42 ± 0.03	0.02 ± 0.00	0.28 ± 0.04	0.06 ± 0.04	-0.06 ± 0.02
ER 参数辨识	Accuracy (↑)	1.00 ± 0.00	0.98 ± 0.04	1.00 ± 0.00	0.97 ± 0.05	0.89 ± 0.08
RP 参数辨识	Accuracy (↑)	0.98 ± 0.04	0.89 ± 0.08	0.97 ± 0.04	0.97 ± 0.04	0.87 ± 0.09
RG 参数辨识	Accuracy (↑)	0.97 ± 0.04	0.93 ± 0.06	0.89 ± 0.13	0.92 ± 0.07	0.80 ± 0.10
SBM 参数辨识	Accuracy (↑)	0.86 ± 0.08	0.80 ± 0.08	0.64 ± 0.08	0.83 ± 0.08	0.60 ± 0.07

在生物单细胞 RNA 测序图几何分类任务中，模型需区分图拓扑是属于“连续发育轨迹（trajectory-like）”还是“离散细胞聚类（cluster-like）”，包含 87 个生物金标准图（Gold）与全量 169 个单细胞图集（All）：

数据集	评估指标	Diversity Curves (本文)	NetLSD	Lim & Qiu 几何特征集 [50]	Best Kernel	TopER
Gold (87 细胞图)	Test Accuracy (↑)	0.860 ± 0.077	0.823 ± 0.047	0.804 ± 0.053	0.785 ± 0.079	0.672 ± 0.086
All (169 细胞图)	Test Accuracy (↑)	0.759 ± 0.077	0.731 ± 0.047	0.716 ± 0.053	0.685 ± 0.092	0.624 ± 0.086

消融实验¶

在 BREC 表达力基准测试（400 对 1-WL 等价图对）中，作者对不同图测度及是否结合粗化边池化进行了系统消融。实验统计了在误差容限 $10^{-5}$ 下能够成功区分的图对数量与占比：

配置 / 测度类型	粗化阶段	Basic (60)	Regular (140)	Extension (100)	CFI (100)	全量 Total (400)	占比说明
Shortest Path	单尺度散度 Div(G)	16	13	41	6	76	19.0%
Shortest Path	边收缩 DivCurve($\mathcal{G}_{\{n-1,n\}}$)	60	48	87	8	203	50.8% (+31.8%)
Diffusion Dist.	单尺度散度 Div(G)	60	49	84	3	196	49.0%
Diffusion Dist.	边收缩 DivCurve($\mathcal{G}_{\{n-1,n\}}$)	60	58	94	3	215	53.8% (+4.8%)
Heat Kernel Dist.	单尺度散度 Div(G)	60	50	92	3	205	51.3%
Heat Kernel Dist.	边收缩 DivCurve($\mathcal{G}_{\{n-1,n\}}$)	60	65	96	3	224	56.0% (+4.7%)

同时，在随机图参数辨识消融中，对比了不同边重要性打分算法（精确散度打分 vs 局部近似打分 vs 纯随机边打分）：以 ER 图为例，三者分类准确率均为 1.000，轮廓系数分别为 $0.704 \pm 0.019$、$0.704 \pm 0.020$ 与 $0.679 \pm 0.021$。随机边打分在保持极高分类性能的同时消除了边打分重新排序的计算瓶颈。

关键发现¶

边粗化池化显著激活结构表达力：单尺度最短路径散度在 BREC 上仅能区分 19.0% 的 1-WL 等价图；仅引入一步边收缩 $n-1$，可区分图对数量跃升至 50.8%（增幅高达 +31.8%），充分印证了定理 3 中粗化过程对几何表达力的放大效应。
轮廓系数断层式领先：在图分布辨识中，虽然最强核方法（Kernel WL OA）与谱方法（NetLSD）能取得相当的分类准确率（0.90），但它们的轮廓系数仅为 0.02 和 0.06；而 Diversity Curves 达到 0.42，展现出极为紧凑且类间分离度极高的无监督聚类潜空间。
跨分辨率几何外推鲁棒：在 MANTRA 2-流形三角剖分识别任务中，模型在原始网格上训练并在重心细分（barycentric subdivision）的大图上测试（$\mathcal{T}_{\text{up}}$ 设定），Diversity Curves 取得了 83% 的准确率与 0.96 的 AUROC，显著击败最强专用网格深度学习基线 Cellular Transformer（74% 准确率与 0.83 AUROC）。

亮点与洞察¶

粗化轨迹代替静态标量：巧妙地将图粗化视为一种跨尺度的“几何断层扫描”，使原本受制于节点数的静态测度空间散度转变为富含多层次拓扑信息的函数式向量，从机理上瓦解了尺寸偏差。
轻量级闭式测度赋能大图计算：舍弃了传统高开销的 persistent homology 过滤网格与图核矩阵求解，采用解析闭式的 spread 结合随机边收缩，在获得可解释物理意义（有效节点数）的同时维持了极高的时间可伸缩性。
非参数统计检验迁移能力：在 ENZYMES 与 PROTEINS 分子数据集上，多样性曲线可直接结合双样本置换检验（permutation test），精确证明了跨数据集下同功能酶的宏观几何一致性，为跨数据集图迁移表征提供了定量工具。

局限与展望¶

作者承认的局限：方法目前侧重于无属性图的纯结构与拓扑比对，尚未深度整合高维连续节点特征与边属性的复杂交互；部分严格表达力证明假定了全可能边收缩序列的多重集，而在工程实践中采用随机采样近似。
未言明与观察局限：当图规模达到数万节点时，全源最短路径计算（$\mathcal{O}(|X|^3)$）仍会成为预处理瓶颈，需依赖 2-近似最短路径或 mini-batch 采样散度技术。
未来改进方向：探索与消息传递神经网络（MPNN）端到端联合训练机制，将多样性曲线作为归纳偏置注入图 Transformer 的结构编码中。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [首次将图粗化演化与度量空间散度结合构建尺寸自适应的多样性曲线]
实验充分度: ⭐⭐⭐⭐⭐ [涵盖随机图模型、单细胞几何、分子统计检验、流形网格与 BREC 表达力全面评测]
写作质量: ⭐⭐⭐⭐⭐ [数学推导严谨自洽，概念直观，定理与实验论证环环相扣]
价值: ⭐⭐⭐⭐⭐ [为跨尺寸无监督图学习提供了具备理论保证、可解释且易部署的全新基线范式]