When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors¶

会议: NeurIPS 2026
arXiv: 2610.13765
论文: https://arxiv.org/abs/2610.13765
领域: 图学习
关键词: 图生成模型, 离散图扩散, 潜在社交度先验, 边独立性失效, 交换性随机图

一句话总结¶

针对无节点特征的离散图扩散模型因边独立性与置换交换性强制退化为 Erdős–Rényi 不动点病态的问题，本文提出潜在社交度先验（LSP）与节点-边联合扩散框架，在免训练编码器的闭式初始化下保留节点异质性并显著提升高阶拓扑生成质量。

研究背景与动机¶

离散图扩散模型（如 DiGress）直接在离散图结构上通过马尔可夫噪声过程对边执行独立的翻转与破坏，相较于将整图投影至欧氏空间的连续隐空间模型，在保持真实图稀疏度与离散拓扑特性方面展现出显著优势。然而，在无语义节点特征（即 \(\mathbf{X} = \mathbf{1}\)）的无条件图生成任务中，这类模型生成的大规模图普遍呈现出高度均质化、缺乏高阶基元（如三角形与高阶环）的严重缺陷。学术界此前普遍将该现象归咎于图神经网络（GNN）去噪器的表达能力不足，并倾向于在每一步去噪采样中后验计算昂贵的辅助特征（如度数、多尺度环计数或拉普拉斯谱特征）加以修补。

然而，这种修补策略掩盖了问题的真正根源。在图生成必须满足置换交换性（Exchangeability）的前提下，前向破坏过程中的逐边独立假设在数学上强制终末先验分布只能是 Erdős–Rényi（E-R）随机图。由此引发了一个根本性的病态不动点定理：在图节点数扩大的极限条件下，任何排列等变的 GNN 去噪器在以 E-R 随机图为输入且缺乏差异化节点输入时，其输出的边预测概率渐进地退化为常数矩阵，其去噪产物在统计上依然逼近 E-R 随机图。这使得去噪网络在扩散最开端的关键阶段根本无法打破均质对称性，即使注入手工设计的局部结构特征，在稀疏或密集 E-R 图上这些特征的节点间方差同样依概率渐进归零。

因此，解决该困境的关键不在于继续堆叠复杂的后验结构特征，而在于从根源上打破终末先验的边独立性，同时维持全局交换性。本文从非均匀随机图理论中汲取灵感，赋予每个节点隐式的潜在社交度（Latent Sociability），通过节点连续隐变量与离散边状态的协同演化，彻底消除终末先验中的条件独立限制。核心 idea：构建一种免编码器的潜在社交度先验（LSP），将无约束的高斯连续扩散与边空间离散马尔可夫扩散协同耦合，在保证全局交换性的同时全轨迹维持节点异质性，打破 E-R 不动点退化。

方法详解¶

整体框架¶

JointLSP 框架的核心由两部分构成：定义在连续空间中的节点潜在社交度向量 \(\mathbf{u} \in \mathbb{R}^n\)，以及定义在离散空间中的图邻接边张量 \(\mathbf{E} \in \{0,1\}^{n \times n \times 2}\)。在前向加噪阶段，模型首先利用干净训练图的度序列，以无须训练编码器的闭式解析方式初始化节点社交度 \(\mathbf{u}^0\)；随后，连续变量 \(\mathbf{u}^t\) 按照校准后的平移缩放 DDPM 过程向高斯分布扩散，而边张量 \(\mathbf{E}^t\) 的转移概率矩阵则由干净潜在变量 \(\mathbf{u}^0\) 逐节点对个性化参数化，最终平滑过渡到显式保留节点连接倾向方差的非均匀随机图先验。在反向去噪阶段，图 Transformer 去噪网络同时预测干净潜在变量 \(\hat{\mathbf{u}}^{0,t}\) 与干净边概率 \(\hat{\mathbf{p}}^{E,t}\)，两路状态同步更新迭代直至生成目标图结构。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入干净图 G0 = (1, E0)"] --> B["解析式节点社交度初始化<br/>基于度分布闭式计算 u0"]
    B --> C["双路协同前向扩散<br/>平移缩放高斯扩散 + u0 条件化边转移"]
    C --> D["终末先验状态<br/>高斯变量 uT 与 LSP 异质随机图 ET"]
    D --> E["双任务图 Transformer 去噪器<br/>同时回归潜在社交度与分类边状态"]
    E --> F["双路协同反向采样<br/>个性化转移核引导离散边与连续变量更新"]
    F --> G["生成图样本 G0"]

关键设计¶

1. 潜在社交度先验（LSP）与闭式初始化：根治边独立性的非均匀图机制

为了打破传统离散扩散中边独立性导致的唯一 E-R 极限先验，本文引入了基于泊松化随机图扩展的潜在社交度先验。每个节点 \(i\) 被赋予正社交度权重 \(w_i = \exp(u_i)\)，在给定权重集合条件下，任意两节点连边的条件概率被定义为 \(p_{ij} = 1 - \exp(-w_i w_j) = 1 - \exp(-\exp(u_i + u_j))\)。这种构造型先验使得边与边在给定隐变量时条件独立，但在边边缘分布上呈现出强依赖性，且天然满足置换交换性。更关键的是，不同于传统隐式图扩散必须训练昂贵的自编码器，在稀疏图渐进区，节点期望度与潜在社交度满足指数线性关联 \(\mathbb{E}(d_i \mid \mathbf{u}) \approx C e^{u_i}\)。基于此，干净潜在变量 \(\mathbf{u}^0\) 可以通过节点平滑度数及全图对数度中心化直接闭式生成：

\[u_i^0 = \mu_{\text{LSP}} + \log(d_i + \delta) - \frac{1}{|V|} \sum_{k \in V} \log(d_k + \delta)\]

其中 \(\mu_{\text{LSP}}\) 与 \(\sigma_{\text{LSP}}\) 作为全局先验参数，仅需在训练前通过 Gauss-Hermite 高斯正交数值积分匹配训练集的全局平均边密度与经验度方差进行单次校准，在整个训练过程中固定不变。

2. 干净变量参数化的双路协同前向过程：保持边缘闭式分解的马尔可夫扩散

直接在连续隐空间对未有界的 \(w_i\) 进行加噪会导致边界溢出，因此本文对实数对数变量 \(u_i\) 采用具有针对性的平移缩放 DDPM 加噪过程：

\[\mathbf{u}^t = \mu_{\text{LSP}} + \sqrt{\bar{\alpha}_t}(\mathbf{u}^0 - \mu_{\text{LSP}}) + \sigma_{\text{LSP}}\sqrt{1 - \bar{\alpha}_t}\,\boldsymbol{\epsilon}, \quad \boldsymbol{\epsilon} \sim \mathcal{N}(0, \mathbf{I})\]

确保 \(t \to T\) 时变量精确收敛于 \(\mathcal{N}(\mu_{\text{LSP}}, \sigma_{\text{LSP}}^2 \mathbf{I})\)。对于离散图结构，传统离散扩散将所有节点对的转移核稳态强行收敛于全局经验边均值 \(\mathbf{m}_E\)；本文创新性地用节点对特异性的稳态概率 \(\mathbf{p}_{ij}^0 = [1 - p_{ij}^0, p_{ij}^0]\) 予以替换，其中 \(p_{ij}^0 = 1 - \exp(-\exp(u_i^0 + u_j^0))\)。累计转移矩阵形式为：

\[\bar{\mathbf{Q}}_E^{t,ij} = \bar{\alpha}_t \mathbf{I} + (1 - \bar{\alpha}_t) \mathbf{1}_b (\mathbf{p}_{ij}^0)^\top\]

这种设计的极为巧妙之处在于：转移矩阵严格由确定性的干净潜在变量 \(\mathbf{u}^0\)（而非随机的带噪变量 \(\mathbf{u}^t\)）进行参数化。若转移依赖于带噪变量 \(\mathbf{u}^t\)，转移矩阵本身将变为随机算子，导致边破坏过程丧失马尔可夫边缘独立分解能力；而固定于 \(\mathbf{u}^0\) 则使得离散边缘后验概率分布依然保持可解析计算的封闭形式。

3. 联合反向采样与协同多任务损失：全轨迹引导打破去噪不动点

在反向逆演阶段，针对时间步 \(t\) 的带噪状态 \((\mathbf{u}^t, \mathbf{E}^t)\)，图去噪骨干网络 \(\phi_\theta\) 联合输出对干净隐变量的估计 \(\hat{\mathbf{u}}^{0,t}\) 以及对边分类的预测分布 \(\hat{\mathbf{p}}^{E,t}\)。在反向转移中，连续隐变量沿标准后验分布采样生成 \(\mathbf{u}^{t-1}\)，而离散边的后验抽样则由预测的潜在社交度构造出逐对反向转移核 \(\hat{\mathbf{Q}}_E^{t,ij}\)：

\[p_\theta(e_{ij}^{t-1} \mid e_{ij}^t, \hat{\mathbf{u}}^{0,t}) = \sum_{r \in \{0,1\}} q(e_{ij}^{t-1} \mid e_{ij}^t, e_{ij}^0 = r; \hat{\mathbf{u}}^{0,t}) \hat{\mathbf{p}}_{ij}^{E,t}(r)\]

整个架构的训练目标结合了图结构上的交叉熵分类损失与节点隐变量维度的均方误差回归项：

\[\mathcal{L} = \sum_{1 \le i, j \le n} \text{CE}(e_{ij}^0, \hat{\mathbf{p}}_{ij}^{E,t}) + \frac{\lambda_u}{n} \sum_{i=1}^n \|\hat{u}_i^{0,t} - u_i^0\|_2^2\]

由于高噪声端（\(t \approx T\)）先验已蕴含真实的节点连接倾向方差，去噪网络从逆扩散初始点便具备显著的节点区分度，彻底瓦解了标准去噪器在 E-R 图上的对称常数预测病态。

损失函数 / 训练策略¶

训练采用时间步均匀采样 \(t \sim \mathcal{U}(\{1, \dots, T\})\)，扩散总步数设为 \(T = 500\)。优化目标由边分类交叉熵与隐变量 MSE 联合构成，超参数 \(\lambda_u\) 设为平衡权重。去噪主干采用图 Transformer 架构（配以自注意力与配对调制），骨干网络深度为 4–6 层，采用 AdamW 优化器，学习率设定为 \(1 \times 10^{-4}\)。先验校准步骤（确定 \(\mu_{\text{LSP}}, \sigma_{\text{LSP}}\)）作为预处理在数据加载前完成，仅需几十毫秒且整个训练生命周期内不产生动态开销。

实验关键数据¶

主实验¶

实验在合成的现实结构子图数据集 CoraChameleon（跨 \(n \in \{10, 20, 50, 100\}\) 四种规模）上全面评估无节点特征场景下的图生成分布保真度，评价指标采用测试集与生成集之间的最大均值差异比值 \(r = \text{MMD}^2(\text{gen}, \text{test}) / \text{MMD}^2(\text{train}, \text{test})\)（越低越优，基线理想值为 1.0）。

数据集规模	模型配置	度分布 (Degree) ↓	聚类系数 (Clustering) ↓	三角形数 (Triangles) ↓	度同配性 (Assortativity) ↓	幂律指数 (PLE) ↓	特征路径长 (CPL) ↓
Node 10	DiGress (无特征)	6.30 ± 1.57	2.46 ± 0.34	15.28 ± 7.27	12.41 ± 1.55	35.40 ± 6.41	12.97 ± 4.19
	JointLSP+DiGress (本文)	5.19 ± 1.61	1.79 ± 0.06	13.45 ± 4.25	1.25 ± 0.25	23.58 ± 4.95	12.93 ± 3.90
Node 20	DiGress (无特征)	22.47 ± 1.63	1.44 ± 0.00	58.45 ± 9.88	49.80 ± 3.08	15.84 ± 2.39	11.46 ± 2.22
	JointLSP+DiGress (本文)	11.13 ± 1.29	1.40 ± 0.00	8.38 ± 0.92	14.04 ± 3.72	34.19 ± 3.47	7.82 ± 1.24
Node 50	DiGress (无特征)	21.09 ± 0.91	1.51 ± 0.01	16.90 ± 0.23	70.67 ± 1.95	18.57 ± 1.07	55.49 ± 3.01
	JointLSP+DiGress (本文)	8.01 ± 0.42	1.40 ± 0.00	4.87 ± 0.80	33.18 ± 1.16	10.77 ± 0.69	30.65 ± 1.71
Node 100	DiGress (无特征)	4.53 ± 0.11	11.33 ± 0.27	14.82 ± 0.12	101.95 ± 2.13	4.64 ± 0.17	39.68 ± 1.14
	JointLSP+DiGress (本文)	10.50 ± 0.16	2.07 ± 0.10	2.33 ± 0.15	59.72 ± 0.75	10.79 ± 0.19	44.99 ± 0.29

消融实验¶

在 CoraChameleon-Node100 上分析后验辅助特征数量与先验设计的对比，验证后验注入结构特征在极限尺度下的疲软，以及 LSP 机制在零特征条件下的高阶拓扑优越性。

方法与特征配置	聚类系数 ↓	三角形计数 ↓	度同配性 ↓	幂律指数 ↓	运行复杂度特征
DiGress + 结构特征 (\(k=2\))	5.08 ± 2.95	11.75 ± 4.50	118.18 ± 2.68	7.43 ± 2.65	低开销局部环特征
DiGress + 结构特征 (\(k=4\))	9.73 ± 7.67	11.46 ± 4.55	107.68 ± 12.37	10.07 ± 5.75	环基元扩展
DiGress + 结构特征 (\(k=8\))	5.89 ± 4.60	7.45 ± 5.08	79.81 ± 52.72	7.04 ± 5.38	中等结构基元集
DiGress + 结构特征 (\(k=10\))	10.72 ± 6.46	10.06 ± 6.11	70.54 ± 40.85	6.99 ± 3.69	饱和结构基元集
DiGress + 纯度数特征 (\(k=1\))	2.04 ± 0.02	2.41 ± 0.14	57.66 ± 0.76	10.81 ± 0.17	仅后验度特征
JointLSP+DiGress (零特征, \(k=0\))	2.07 ± 0.10	2.33 ± 0.15	59.72 ± 0.75	10.79 ± 0.19	无任何后验结构特征
DiGress + 结构与谱特征 (\(k=17\))	1.95 ± 0.00	1.68 ± 0.00	3.55 ± 0.00	1.53 ± 0.00	包含高成本拉普拉斯特征向量

关键发现¶

高阶拓扑的巨大跃升：在完全不依赖任何人工设计节点特征的情况下，JointLSP 在代表图高阶团簇特性的关键指标上实现了数量级改善。在 Node 100 规模下，三角形数 MMD 误差从 DiGress 的 14.82 骤降至 2.33，聚类系数从 11.33 降低到 2.07，同配性误差从 101.95 降至 59.72。
验证理论引理（Lemma 4.3）：当单纯为 DiGress 堆叠 2 至 10 种局部子图结构特征时，三角形与同配性性能始终处于停滞与高方差状态（如 \(k=10\) 时同配性仍高达 70.54 ± 40.85）。这证明了理论预测——在接近 E-R 的带噪图上计算的任何局部子图计数，其离散方差均按 \(O(\sqrt{\log n / n})\) 消失，根本无法提供有效的去噪梯度。
高噪声端节点区分度保持：节点连接倾向方差 \(V^t = \text{Var}_i(\mathcal{S}_i^t)\) 的轨迹分析显示，DiGress 在 \(t=500\) 处方差完全坍缩为 0，而 JointLSP 从终末状态到反向去噪全程维持健康的方差平台，避免了逆向初期的随机对称性死锁。

亮点与洞察¶

指出并证明离散扩散的核心病理：本文首次从理论上揭示了无特征离散图扩散模型的阿喀琉斯之踵——边独立性结合图置换交换性不可避免地导致 E-R 终末先验，而 GNN 在大图极限下处理 E-R 图退化为常数预测不动点。
以生成机制替代繁复编码器：不同于以往将整图压缩至高维向量的图潜在扩散架构，本文的潜在社交度机制并不试图通过隐空间重建整图，而是仅作为引导离散边更新的“连续催化剂”，借由度分布闭式解直接构造先验，兼具轻量性与可解释性。
向稀疏大规模图的高效迁移：将 JointLSP 挂载到面向大图采样的稀疏扩散模型 SparseDiff 上（在 CoraChameleon-Node500 上测试），三角形 MMD 误差从 113.81 降至 35.41，证明该连续-离散协同范式具有通用拓展价值。

局限与展望¶

分子等富特征图领域的适用边界：作者在正文中明确指出，本文框架聚焦于无节点语义特征或拓扑主导的图生成；对于小分子图生成，由于节点携带丰富的原子物理类型及化学键语义，E-R 不动点退化并不显著，LSP 的增益相对有限。
度分布轻微过度校正倾向：在部分大规模节点（如 Node 100）实验中，JointLSP 的纯度分布 MMD 略高于 baseline，推测是强化的节点异质性在部分图实例上对全局度分布造成了轻微的过度校正。
社区感知先验的扩展空间：当前 LSP 主要编码一阶度异质性，尚未显式包含社团划分（Community Structure）的先验信息。未来可探索将标量社交度扩展为多维混合社团变量，在无须每步计算稠密谱特征的前提下赋予先验感知全局图聚类的能力。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从理论上指认无特征离散图扩散的 E-R 不动点病态，并给出免编码器的闭式协同扩散解法。
实验充分度: ⭐⭐⭐⭐☆ 理论推导完备，涵盖极限方差证明、合成现实图基准、多尺度消融与轨迹方差追踪，补充了 SparseDiff 大图实验。
写作质量: ⭐⭐⭐⭐⭐ 数学脉络极度清晰，由浅入深，从引理递进至定理，问题定义与工程落地严丝合缝。
价值: ⭐⭐⭐⭐☆ 针对无属性图扩散生成的基础理论瓶颈提供了优雅且通用的解决范式，对复杂网络与拓扑生成领域极具启发性。