Permutation-Invariant Spectral Learning via Dyson Diffusion¶

会议: NeurIPS 2026
arXiv: 2510.08535
领域: 图像生成
关键词: 图扩散模型, 戴森布朗运动, 谱生成, Weisfeiler-Leman等价, 李代数评分匹配

一句话总结¶

针对现有图扩散模型将置换等变归纳偏置强加于神经网络架构而导致WL等价图谱盲区的问题，本文提出基于戴森布朗运动的戴森扩散模型（DyDM），通过随机矩阵理论将谱动力学与特征向量解耦，在李群及李代数流形上实现完全置换不变的高保真图谱与图生成。

研究背景与动机¶

扩散模型通过随机微分方程（SDE）加噪数据并学习时间反向轨迹，已成为连续与离散生成建模的核心范式。然而，在图生成领域，将扩散过程扩展到邻接矩阵时面临着根本性的组合爆炸障碍：具有 $n$ 个节点的无向图最多存在 $n!$ 种不同的邻接矩阵排列。若在全矩阵空间中直接拟合 score matching 目标，缺乏排列先验的扩散模型会因样本空间膨胀至 $\Omega \times S_n$ 而遭受阶数为 $\Theta(n!/N)$ 的均方误差发散。以往的主流方法（如基于消息传递神经网络的 EDP-GNN、GDSS，或基于图 Transformer 的 ConGress）选择将排列等变（permutation equivariance）的归纳偏置完全压入神经网络骨架中。

这种将对称性归纳偏置完全寄托于网络架构的做法带来了沉重的理论代价。受限于计算复杂度理论中图同构问题（Graph Isomorphism, GI）的多项式时间不可知性，任何多项式复杂度的消息传递或自注意力机制在表达能力上都必然受制于 Weisfeiler-Leman（WL）测试的理论上限。例如，所有度数为 $k$ 的 $k$-正则图在 1-WL 视角下皆等价，GNN 架构无法区分不同拓扑但同谱同度的结构。当在包含 WL 等价图的数据集上进行条件概率拟合时，现有模型不仅难以捕获真实的模态比例，还会频繁生成结构失真甚至幻觉出的其他 WL 等价图；即使如 DiGress 引入人工构造的拉普拉斯谱特征作为数据增强，也只是经验性的修补而非动力学层面的根治。

本文的切入角度是打破将归纳偏置局限在网络架构中的传统思维，转而从随机矩阵理论（Random Matrix Theory, RMT）的动力学本质中寻求突破。对于作用于对称邻接矩阵的 Ornstein-Uhlenbeck（OU）扩散过程，其谱动力学天然遵从一维库仑气体斥力演化，且完全独立于特征向量的旋转。核心 idea：利用随机矩阵理论将图邻接矩阵的扩散过程解析解耦为置换不变的谱演化（戴森布朗运动）与条件李群正交特征向量扩散，将置换归纳偏置从网络架构转移至动力学本身，使谱学习免于 GNN 表达力瓶颈并在李代数切空间实现严格置换不变的特征向量生成。

方法详解¶

整体框架¶

戴森扩散模型（DyDM）将无向图的对称邻接矩阵 $M(t) \in \text{Sym}(\mathbb{R}^{n \times n})$ 的 OU 扩散拆解为两个严格解耦且几何意义明确的动力学分量：第一分量是定义在 Weyl 室（Weyl Chamber）$C_n := \{\lambda \in \mathbb{R}^n : \lambda_1 > \dots > \lambda_n\}$ 内的特征值谱向量 $\lambda(t)$ 的戴森布朗运动（Dyson-BM）；第二分量是在给定特征值演化轨迹条件下，由正交特征基矩阵 $X_t = (v_1(t), \dots, v_n(t)) \in \mathrm{O}(n)$ 在正交群流形上诱导的随机旋转。

在逆向生成阶段，DyDM 首先利用任意无置换约束的通用神经网络（如带有傅里叶时间编码与 FiLM 调制的 MLP）在 Weyl 室内学习时间反转谱 score 并逆向采样特征值；随后，以生成的谱轨迹为条件，在李代数 $\mathfrak{o}(n)$ 空间中利用行置换不变的 Set Transformer 逆向积分生成满足严格正交性的特征向量矩阵，最终重构出图的邻接矩阵或物理图观测算子。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["图邻接矩阵数据 M(0)"] --> B["谱与特征向量解析解耦<br/>M(t) = X_t diag(lambda_t) X_t^T"]
    B --> C["戴森布朗运动动力学<br/>库仑斥力粒子系统 (Dyson-BM)"]
    B --> D["李群正交特征基演化<br/>正交群 O(n) 流形扩散"]
    C --> E["自适应时间步长正向积分<br/>限制在 Weyl 室边界内"]
    D --> F["李代数切空间投影<br/>o(n) 反对称坐标参数化"]
    E --> G["可计算增量 Score 匹配<br/>Euler-Maruyama 局部高斯损失"]
    F --> H["行置换不变 Set Transformer<br/>结合符号对称性规范规约"]
    G --> I["反向 SDE 谱采样<br/>平衡态排斥边界防护"]
    H --> I
    I --> J["重构生成图结构与完整图谱"]

关键设计¶

1. 谱动力学戴森布朗运动解耦：将全局矩阵扩散解析拆分为非相交粒子系统

传统图扩散直接在 $n \times n$ 邻接矩阵上施加逐项 OU 扩散： $$ \mathrm{d}M_{ij}(t) = -\beta M_{ij}(t)\mathrm{d}t + \sqrt{(1+\delta_{ij})\alpha}\,\mathrm{d}B_{ij}(t),\quad 1 \leq i \leq j \leq n $$ 本文利用对称矩阵谱理论与 Itô 引理证明，当初始矩阵具有简单谱（无重根）时，其降序排列的特征值向量 $\lambda(t) = (\lambda_1(t), \dots, \lambda_n(t))$ 严格满足封闭的自主随机微分方程： $$ \mathrm{d}\lambda_k(t) = \left(\alpha \sum_{\ell \neq k}\frac{1}{\lambda_k(t) - \lambda_\ell(t)} - \beta \lambda_k(t)\right)\mathrm{d}t + \sqrt{2\alpha}\,\mathrm{d}W_k(t) $$ 式中前项为带电粒子间的逆距离静电库仑斥力，第二项为谐振子约束势漂移，第三项为独立布朗运动驱动。这一公式最核心的解析优势在于：谱的演化完全独立于特征向量，且对顶点的所有置换操作具备绝对的数学不变性。这意味着学习谱分布无需采用任何置换等变神经网络，彻底规避了 GNN 在 WL 等价图上的表达瓶颈。

2. Weyl 室奇异性控制与可计算增量评分匹配：规避非高斯转移密度的解析求解

戴森 SDE 的漂移项在粒子碰撞边界 $\lambda_k = \lambda_\ell$ 处具有奇异性，且其有限时间条件转移密度 $p_{t|0}(\lambda(t)|\lambda(0))$ 并不具备封闭的高斯解析形式，导致标准的去噪评分匹配（DSM）无法直接计算目标梯度。DyDM 采用局部增量过渡近似：基于 Euler-Maruyama 离散化构建短步长 $h \to 0$ 局部高斯核 $p_{t+h|t}(\lambda_{t+h}|\lambda_t)$，将整体评分目标转化为在离散时间网格上的可解析加权方差极小化。

针对正向积分易越过 Weyl 室边界产生虚假数值相交的问题，设计了自适应步长控制器，保证在单位概率事件下轨道不发生交叉碰撞；同时在逆向动力学生成阶段引入平衡态发射机制（Equilibrium Shooting Mechanism），在轨道逼近边界时施加基于不变测度势函数 $U(\lambda) = \frac{\beta}{2\alpha}\sum_k \lambda_k^2 - \sum_{k<\ell}\ln|\lambda_k - \lambda_\ell|$ 的排斥修正，杜绝采样数值漂移。

3. 条件李群扩散与李代数置换不变评分：将特征向量学习自由度压缩至极小空间

若仅生成特征值而舍弃特征向量，将丢失无向图完整的 $\Theta(n^2)$ 结构信息。本文基于条件矩阵摄动理论推导出正交特征矩阵 $X_t \in \mathrm{O}(n)$ 的流形演化方程，证明其无穷小步长更新满足矩阵指数映射 $X_{t+\mathrm{d}t} = X_t \exp(\mathrm{d}Z_t(\lambda))$，其中反对称增量 $\mathrm{d}Z_t(\lambda) \in \mathfrak{o}(n)$ 具有形式： $$ \mathrm{d}Z_t(\lambda) = \sqrt{\alpha}\sum_{\ell < k} \frac{E_{\ell,k}\,\mathrm{d}W_{\ell,k}}{\lambda_k(t) - \lambda_\ell(t)} $$ 将评分函数直接定义在李代数 $\mathfrak{o}(n)$ 坐标上带来了三个突破性性质：首先，生成过程在几何上内蕴保证了特征向量的严格正交归一性，无需任何投影或拒绝采样；其次，反对称约束使建模自由度从 $n^2$ 压缩至 $n(n-1)/2$；最关键的是，虽然全矩阵 $M$ 在顶点置换下表现为等变变换 $PMP^T$，但由于特征列向量已按唯一降序特征值绑定，顶点置换仅表现为特征向量矩阵行维度的置换 $X \mapsto PX$。作者在理论上证明了李代数坐标评分满足严格置换不变性 $\nabla \ln p_t(\bar{\lambda}, P\bar{X}_t) = \nabla \ln p_t(\bar{\lambda}, \bar{X}_t)$，从而首次打破了传统图扩散模型必须采用等变结构的定式，允许直接使用针对无序行集合的 Set Transformer 架构。

4. 特征向量符号规范规约：利用对角规范实现状态空间 $2^n$ 倍指数缩聚

特征向量的方向定义在符号变换 $v_k \mapsto \pm v_k$ 下具有物理对称性，这种规范不确定性在全群建模中会导致严重的模式冗余。本文证明了反向李代数评分在任意对角符号矩阵 $F = \mathrm{diag}(\pm 1, \dots, \pm 1)$ 作用下严格满足规范共轭关系： $$ \nabla \ln p_t(\bar{\lambda}, \bar{X}_t F) = F \nabla \ln p_t(\bar{\lambda}, \bar{X}_t) F $$ 算法在输入评分网络前，首先将特征基矩阵投影至确定的标准规范（Canonical Gauge），在规范坐标下计算成对 Lie 坐标标量输出，最后反变换恢复原始符号流向。此项设计在数学上消除了 $2^n$ 种等价符号排列的重复拟合，使网络只需在单一座舱内学习几何流形曲率。

损失函数 / 训练策略¶

谱扩散模型采用离散化路径上的加权增量评分匹配损失： $$ \tilde{L}{\text{spec}}(\theta) = \frac{1}{N}\sum \right|_2^2 $$ 其中 }^N \sum_{i=1}^{k^{(r)}} \frac{t_i^{(r)} - t_{i-1}^{(r)}}{T}\eta(t_i^{(r)}) \left| s_\theta(\lambda_i^{(r)}, t_i^{(r)}) - \frac{a(t_{i-1}^{(r)}, \lambda_{i-1}^{(r)})\Delta t_i^{(r)} - (\lambda_i^{(r)} - \lambda_{i-1}^{(r)})}{b^2(t_{i-1}^{(r)}, \lambda_{i-1}^{(r)})\Delta t_i^{(r)}$a(t, \lambda)$ 与 $b(t, \lambda)$ 分别对应戴森布朗运动的漂移项与扩散系数矩阵。时间权重 $\eta(t)$ 结合戴森混合猜想选用指数时间调度（在局部微观混合的快速时间尺度 $t \sim \Theta(1/n)$ 处赋予精细步长）。

条件特征向量评分模型则在由样本路径决定的时间网格上，以均方误差最小化拟合李代数坐标梯度： $$ \tilde{L}{\text{vec}}(\phi) = \frac{1}{N}\sum^2 $$ 训练全程采用 AdamW 优化器配合余弦退火学习率和全局梯度范数裁剪（阈值 0.5），所有模型评估均结合权重指数移动平均（EMA，衰减率 0.95）。}^N \sum_{i=1}^{k^{(r)}-1} \frac{\Delta t_i^{(r)}}{T} \left| s_\phi(X_{t_{i+1}}^{(r)}, \lambda_{t_{i+1}}^{(r)}, t_{i+1}^{(r)}) - \frac{\Sigma(t_{i+1}^{(r)}, t_i^{(r)}) Z_{t_i}^{(r)}}{\Delta t_i^{(r)}} \right|_{\mathfrak{o}(n)

实验关键数据¶

主实验¶

在涵盖理论盲区基准（WL-Bimodal：80% Graph A 与 20% Graph B 的 3-正则图混合集）、标准图基准（Community Small）以及包含 15,000 个脑连接组局部子图的大规模高保真基准（Brain）上，对比 DyDM 与代表性 GNN/Transformer 图扩散模型在谱分布上的拟合误差。评估指标包括谱均值向量距离 $\mu(\nu_{\text{samp}}, \nu_{\text{test}})$ 以及维度平均边际 Wasserstein 距离 $\mathcal{W}_{\text{marg}}$。

数据集	指标	DyDM (本文)	EDP-GNN	GDSS	ConGress	DiGress (无特征增强)	DiGress (带谱特征技巧)
WL-Bimodal	$\mu$	0.02	0.13	0.24	0.38	1.06	0.03
	$\mathcal{W}_{\text{marg}}$	0.01*	0.08	0.13	0.16	0.29	0.01*
Community Small	$\mu$	0.07	0.42	0.38	0.27	2.51	0.09
	$\mathcal{W}_{\text{marg}}$	0.02	0.14	0.14	0.11	0.45	0.03
Brain (15k 图)	$\mu$	0.05	0.07	0.33	0.13	0.57	0.12
	$\mathcal{W}_{\text{marg}}$	0.03†	0.03†	0.12	0.03†	0.17	0.03†

注：标号（*）表示两数值在前四位小数内一致，标号（†）表示数值在前三位小数内一致。

特征向量重构与高阶拓扑保真度（WL-Bimodal 图生成实验）¶

在 WL-Bimodal 数据集上，将学习到的谱与李群条件特征向量扩散联合，生成完整图样本并计算最大均值差异（MMD）。该任务精确检验模型是否能够区分 WL 等价的非同构拓扑，而非仅仅拟合同构不变量。

模型	度分布 MMD (Degree)	聚类系数 MMD (Clustering)	谱距离 MMD (Spectral)	轨道数 MMD (Orbit)
DyDM + 李群特征向量 (本文)	0.00013	0.00041	0.00011	0.00001
EDP-GNN	0.00000	0.16590	0.05011	0.00189
GDSS	0.00000	0.33342	0.12303	0.00025
ConGress	0.07759	0.45267	0.15022	0.01024
DiGress (无特征增强)	0.37712	0.70940	0.23426	0.04024
DiGress (带谱特征技巧)	0.00000	0.00189	0.00050	0.00004

关键发现¶

在 WL-Bimodal 实验中，基线 GNN 模型（EDP-GNN、GDSS）虽然在度分布上取得了完美的 0.00000（因为同类正则图度数完全一致），但聚类系数和轨道分布 MMD 极大（分别高达 0.16590 和 0.33342），且大量生成其他非同构的 WL 等价图；DyDM 在聚类系数和谱 MMD 上相比未增强模型实现两个数量级以上的误差下降。
DiGress 之所以能在部分指标上接近 DyDM，完全归功于其硬性拼接了前 6 个拉普拉斯特征值和前 2 个特征向量作为节点特征；一旦去除这一经验技巧（DiGress no trick），其在所有数据集上的谱误差与拓扑指标均发生严重崩塌（Community 谱均值距离从 0.09 恶化至 2.51）。DyDM 完全无需任何特设数据增强即可达到甚至超越其上限。
计算开销方面，在单张 A100 GPU 上，DyDM 结合李群扩散生成 1,000 张图的整体采样时间仅需 17 秒，特征向量评分模型训练仅需 20 分钟，具有极高的实际推断效率。

亮点与洞察¶

将几何归纳偏置由网络结构转移到动力学本身：传统几何深度学习过度依赖等变/不变网络设计，导致受限于 WL 分类瓶颈；本文通过随机矩阵理论将物理约束置入 SDE 演化算子，为几何表征学习开辟了全新视角。
李代数上的置换不变性证明：发现了正交特征基在按特征值定序后，左乘置换矩阵在切空间 $\mathfrak{o}(n)$ 中退化为严格不变性这一反直觉的代数性质，使得无需等变结构的 Set Transformer 能够合法应用于稠密矩阵分解生成。
谱生成工具的跨领域泛化潜力：戴森布朗运动仅依赖实对称矩阵假设，这意味着 DyDM 的数学范式能够无缝推广到协方差矩阵分析、主成分动态演化、大分子高斯网络模型（GNM）及量子系统哈密顿量生成中。

局限与展望¶

目前实现依赖特征值非相交假设：理论推导基于初始矩阵具有简单谱（simple spectrum）的前提，对于具有大量多重重根特征值的图（如高度对称的格点图），需要引入细微扰动破坏对称性，可能对极限特征间距引入轻微数值噪声。
二阶段联合采样的累积误差：虽然特征值谱独立解耦，但特征向量扩散强条件依赖于谱轨迹；若逆向谱采样发生局部微小漂移，可能在李群逆向步长中放大旋转梯度的方差。
复数域与超图扩展：目前框架局限于实对称矩阵与无向图，进一步推广到厄米特矩阵（Hermitian matrices）可用于有向图与复权重网络，具有广阔的数学拓展空间。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙利用随机矩阵理论与戴森布朗运动，颠覆了传统图扩散依赖等变网络的范式。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖理论反例检验、真实图谱拟合、大规模图数据集及完整拓扑重构实验。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严密优雅，几何图景清晰，附录推导完备。
价值: ⭐⭐⭐⭐⭐ 为图生成、非欧流形扩散以及随机矩阵谱学习提供了极具开创性的理论和工程基础。

数据集	指标	DyDM (本文)	EDP-GNN	GDSS	ConGress	DiGress (无特征增强)	DiGress (带谱特征技巧)
WL-Bimodal	\(\mu\)	0.02	0.13	0.24	0.38	1.06	0.03
	\(\mathcal{W}_{\text{marg}}\)	0.01*	0.08	0.13	0.16	0.29	0.01*
Community Small	\(\mu\)	0.07	0.42	0.38	0.27	2.51	0.09
	\(\mathcal{W}_{\text{marg}}\)	0.02	0.14	0.14	0.11	0.45	0.03
Brain (15k 图)	\(\mu\)	0.05	0.07	0.33	0.13	0.57	0.12
	\(\mathcal{W}_{\text{marg}}\)	0.03†	0.03†	0.12	0.03†	0.17	0.03†