Hypergraph Generation via Structured Stochastic Diffusion¶

会议: NeurIPS 2026
arXiv: 2605.05024
论文: arXiv
领域: 图学习
关键词: 超图生成, 随机扩散过程, 关联矩阵, 两侧热流算子, 置换等变性

一句话总结¶

提出了直接作用于连续松弛超图关联矩阵上的结构化扩散生成模型 Hedge，通过融合两侧超图热核与 Ornstein-Uhlenbeck 漂移实现结构感知加噪与解析高斯基分布，并证明了状态逆向漂移回归的最优性与有限时界稳定性。

研究背景与动机¶

超图通过允许多个节点同时参与单个超边，能够高保真地建模科研合作网络、多体社交群组、商品共购以及生物分子交互等系统中的高阶多体关联。然而，逼真地生成真实超图极其困难：现有图生成模型通常仅处理两两成对的邻接矩阵，若通过派系扩展（clique expansion）或二部图展开等启发式方法将超图降维为普通图，往往会严重失真或抹杀节点参与度异质性、超边尺寸分布以及多超边交叠（overlap）等核心高阶拓扑特征。

这一难题的核心矛盾在于：超图的自然代数表示是矩形的节点-超边关联矩阵 $H \in \{0,1\}^{n \times m}$，但直接在离散或连续关联空间建立生成式扩散模型缺乏物理驱动的结构先验。单纯基于无结构高斯扰动（如标准各向同性扩散）会打破高阶邻域拓扑，而纯粹依赖超图拉普拉斯算子的热流过程虽然能保留低频结构，却会收缩至依赖于具体超图的低秩退化子空间，无法提供通用且可解析采样的无偏基分布。

本文的切入角度是：利用关联矩阵天然具备的“节点-超边”双域对称性，构建一个由数据驱动的双侧热流平滑算子与通用 Ornstein–Uhlenbeck（OU）均值回复过程耦合的连续扩散机制。核心 idea：直接在松弛连续关联矩阵空间建立结构化随机扩散模型 Hedge，前期由两侧超图热流算子自适应消除高频拓扑噪声，后期平滑过渡至 OU 机制以收敛到显式高斯极限分布，并通过回归条件逆向漂移解析目标学习 $S_n \times S_m$ 置换等变漂移场。

方法详解¶

整体框架¶

Hedge 直接在连续松弛关联矩阵 $X \in \mathbb{R}^{n \times m}$ 上定义正向加噪与逆向生成。输入为观测超图关联矩阵 $H \in \{0,1\}^{n \times m}$，正向扩散过程结合超图拓扑自适应的双侧热流算子与均值回复 OU 漂移；在训练阶段，利用前向过程关于给定超图的条件线性高斯性质，解析计算条件均值、协方差与无偏分数，作为目标逆向漂移；逆向生成阶段则从标准各向同性高斯先验采样，通过神经网络参数化的 $S_n \times S_m$ 置换等变逆向 SDE 逐步积分，最后经阈值投影还原为离散超图关联矩阵。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["离散超图关联矩阵 H"] --> B["双侧热流与OU复合前向SDE<br/>结构感知平滑 + OU渐进退化"]
    B --> C["条件高斯解析解求解<br/>解耦 Kronecker 谱分解快速计算"]
    C --> D["条件逆向漂移解析目标构造<br/>封闭形式反向分数与确定性漂移"]
    D --> E["置换等变逆向漂移场回归<br/>Sn x Sm 等变架构学习后验平均"]
    E --> F["先验高斯初始化采样与逆向积分<br/>Euler-Maruyama 离散化求解 SDE"]
    F --> G["阈值二值化投影<br/>输出生成超图关联矩阵"]

关键设计¶

1. 双侧热流与OU复合前向扩散：兼顾拓扑结构衰减与解析高斯极限

针对普通高斯加噪破坏超图高阶拓扑、而纯热流又会坍缩到局部退化态的问题，本文设计了联合节点侧归一化拉普拉斯算子 $L_V(H) \in \mathbb{R}^{n \times n}$ 与超边重叠归一化拉普拉斯算子 $L_E(H) \in \mathbb{R}^{m \times m}$ 的双侧热算子 $\mathcal{A}_H(X) := L_V(H)X + XL_E(H)$。其中 $L_E(H) = I_m - D_{\text{ov}}^{-1/2} A_E(H) D_{\text{ov}}^{-1/2}$ 基于消除尺寸偏差的超边交叠矩阵 $A_E(H) = \text{offdiag}(D_E^{-1/2} H^\top H D_E^{-1/2})$ 构造，并被严格证明为对称半正定算子。正向连续 SDE 采用连续退火权重 $\alpha(s)$ 与 $\beta(s)$（满足 $\alpha(s)+\beta(s)=1, \alpha(0)=1, \beta(0)=0$）： $$ \mathrm{d}X_s = -\alpha(s)\mathcal{A}_H(X_s)\,\mathrm{d}s - \beta(s)\gamma(X_s - M_0)\,\mathrm{d}s + \sqrt{2\tau\beta(s)}\,\mathrm{d}W_s, \quad X_0 = H $$ 在扩散初期（$s \to 0$），由两侧热流算子主导，优先滤除高频关联扰动并保留核心高阶交叠结构；随着时间推进（$s \to S$），OU 过程逐步占优，迫使系统平滑收敛到全局已知且与测试样本无关的非退化高斯基分布 $\mathcal{N}(M_0, \frac{\tau}{\gamma} I_{nm})$。

2. 基于Kronecker谱解耦的条件高斯解析推断：规避高维矩阵逆求解

针对将关联矩阵展开为 $nm$ 维超长向量后计算协方差逆导致的 $\mathcal{O}(n^3 m^3)$ 爆炸问题，本文利用了双侧线性算子的代数结构。向量化状态 $x_s = \text{vec}(X_s)$ 服从线性非时齐高斯 SDE： $$ \mathrm{d}x_s = -B_s(H) x_s \,\mathrm{d}s + \beta(s)\gamma \,\text{vec}(M_0)\,\mathrm{d}s + \sqrt{2\tau\beta(s)}\,\mathrm{d}w_s $$ 其中系统矩阵 $B_s(H) = \alpha(s)(I_m \otimes L_V(H) + L_E(H) \otimes I_n) + \beta(s)\gamma I_{nm}$ 具有 Kronecker 和结构。通过对 $L_V$ 和 $L_E$ 进行单次 $\mathcal{O}(n^3 + m^3)$ 谱分解 $L_V = U \Lambda U^\top$ 与 $L_E = V M V^\top$，即可在张量基 $U \otimes V$ 下将 $nm \times nm$ 的李雅普诺夫微分方程完全解耦为 $nm$ 个相互独立的一维标量常微分方程，从而以每时间步仅 $\mathcal{O}(nm)$ 的开销解析求解条件均值 $m_s(H)$ 与正定协方差矩阵 $C_s(H)$。

3. 严格无偏的条件逆向漂移回归与置换等变建模：消除边际评分近似误差

在生成阶段真实超图 $H$ 未知，常规分数扩散模型需近似边际分数 $\nabla_X \log \hat{p}_s(X)$，在离散结构边际混合分布上极易累积误差。本文证明了对条件逆向漂移目标进行 $L^2$ 回归的等价性： $$ u^{\star}_{s \mid H}(X) = \alpha(s)\mathcal{A}_H(X) + \beta(s)\gamma(X - M_0) - 2\tau\beta(s)\,\text{mat}\big(C_s(H)^{-1}(\text{vec}(X) - m_s(H))\big) $$ 状态神经漂移场 $u_s^\theta(X)$ 最小化目标 $\mathbb{E}_{H, s, X_s}[\|u_s^\theta(X_s) - u^{\star}_{s \mid H}(X_s)\|_F^2]$ 的总体极小点严格等于后验期望漂移 $\mathbb{E}[u^{\star}_{s \mid H}(X) \mid X_s = X]$，且与前向边际过程的时间反转完全重合。同时，利用超图节点重编号与超边排布无序的物理对称性，理论证明了最优逆向漂移场天然满足 $S_n \times S_m$ 置换等变性 $u_s^{L^2}(PXQ^\top) = P u_s^{L^2}(X) Q^\top$，指导模型采用行列双向排列等变网络参数化，保证了对称空间泛化性。

损失函数 / 训练策略¶

训练阶段算法流程（算法1）极简高效：每次迭代从经验超图分布中随机采样一个子超图 $H \sim p_{\text{data}}$ 及扩散时刻 $s \sim \rho$，经谱解耦求解出解析均值 $m_s(H)$ 与协方差平方根 $C_s(H)^{1/2}$；直接重参数化前向采样高斯状态 $X_s = \text{mat}(m_s(H) + C_s(H)^{1/2} \xi)$，随后评估无噪声的确定性真实逆向漂移标靶 $u^{\star} = u^{\star}_{s \mid H}(X_s)$，以 Frobenius 范数平方差作为回归损失更新网络参数： $$ \mathcal{L}(\theta) = |u_s^\theta(X_s) - u^{\star}_{s \mid H}(X_s)|_F^2 $$ 该训练过程不依赖任何 Monte Carlo 轨迹积分或 MCMC 采样，所有回归标签均基于闭式解析式计算。

实验关键数据¶

主实验¶

在涵盖稀疏引文共引（Cora、CiteSeer）、作者合作（DBLP）、国会委员会交叠（House-Committees）以及异构实体交互（Actor、Twitch）的 6 个真实超图基准上，将 Hedge 与经典配置模型超图 MCMC 基线（HCM-MCMC）、随机超图（ER-HG）以及基于二部图扩散的生成方法（HYGENE）进行了定长子超图生成对比。下表汇总了衡量真实高阶关联结构匹配度的关键指标（数值均为 10 次随机种子的均值 $\pm$ 标准差，越低越好）：

数据集	指标	Hedge (本文)	HCM-MCMC (强基线)	ER-HG	HYGENE (扩散SOTA)
Cora	Overlap Tail Gap Intersection WD Feature MMD	0.005 ± 0.001 0.017 ± 0.004 0.123 ± 0.050	0.006 ± 0.001 0.026 ± 0.006 0.110 ± 0.032	0.006 ± 0.004 0.167 ± 0.003 1.059 ± 0.091	0.618 ± 0.301 4.390 ± 2.197 0.524 ± 0.080
CiteSeer	Overlap Tail Gap Intersection WD Feature MMD	0.012 ± 0.005 0.050 ± 0.018 0.053 ± 0.026	0.012 ± 0.008 0.081 ± 0.014 0.194 ± 0.181	0.005 ± 0.003 0.187 ± 0.007 1.082 ± 0.079	0.738 ± 0.171 21.65 ± 15.05 0.802 ± 0.125
Actor	Overlap Tail Gap Intersection WD Feature MMD	0.004 ± 0.002 0.041 ± 0.020 0.136 ± 0.079	0.008 ± 0.003 0.058 ± 0.014 0.277 ± 0.145	0.032 ± 0.018 0.319 ± 0.043 0.928 ± 0.151	0.992 ± 0.003 61.56 ± 0.60 1.008 ± 0.288
H.-Comm.	Overlap Tail Gap Intersection WD Feature MMD	0.034 ± 0.016 0.223 ± 0.062 0.072 ± 0.073	0.035 ± 0.011 0.320 ± 0.032 0.163 ± 0.128	0.130 ± 0.029 0.612 ± 0.083 0.699 ± 0.231	0.419 ± 0.133 3.249 ± 2.716 0.422 ± 0.215
DBLP	Overlap Tail Gap Intersection WD Feature MMD	0.011 ± 0.011 0.080 ± 0.022 0.083 ± 0.089	0.016 ± 0.006 0.081 ± 0.021 0.102 ± 0.007	0.012 ± 0.014 0.295 ± 0.040 0.951 ± 0.017	0.977 ± 0.006 40.13 ± 26.09 0.999 ± 0.280
Twitch	Overlap Tail Gap Intersection WD Feature MMD	0.008 ± 0.001 0.075 ± 0.010 0.101 ± 0.085	0.018 ± 0.003 0.113 ± 0.026 0.159 ± 0.019	0.023 ± 0.004 0.334 ± 0.027 0.932 ± 0.116	0.980 ± 0.003 62.61 ± 0.25 0.890 ± 0.066

消融实验¶

在合成数据集上系统测试前向加噪机制（Full heat OU vs Pure OU）与几何算子完整性（两侧热流 Two-sided vs 单侧热流 Node only / Edge only），所有合成体制均值汇总如下：

配置	Intersect. WD	Tail gap	Node spec. WD	Edge spec. WD	Feature MMD
Full Hedge (完整模型)	0.105 ± 0.076	0.012 ± 0.004	0.034 ± 0.020	0.036 ± 0.027	0.331 ± 0.258
w/o Heat (仅 OU 机制)	0.132 ± 0.080	0.012 ± 0.006	0.044 ± 0.020	0.039 ± 0.030	0.391 ± 0.296
w/o Edge算子 (仅 Node 侧)	0.137 ± 0.086	0.019 ± 0.006	0.036 ± 0.021	0.036 ± 0.030	0.353 ± 0.311
w/o Node算子 (仅 Edge 侧)	0.126 ± 0.079	0.014 ± 0.004	0.034 ± 0.022	0.037 ± 0.030	0.373 ± 0.279

关键发现¶

高阶交叠几何的精准复现：在衡量超边两两交集完整分布的 Intersection WD 指标上，Hedge 在全部 6 个真实基准上均稳居第一，在复杂多重交叠数据集（如 House-Committees）上相较于强基线 HCM-MCMC 取得了将近 30% 的显著改善（0.223 vs 0.320）。
两侧热流算子的协同互补性：消融实验清晰证明，单纯依赖 OU 噪声虽然能依靠局部容量匹配局部的 Tail gap，但在表征高阶算子谱结构（Node/Edge spectral WD）及全局结构特征 MMD 上全面落后；单侧算子虽然在部分边际统计上有一定竞争力，但唯有双侧热流才能在各类复杂拓扑体制下取得全局平衡。
二部图扩散基线的严重退化：HYGENE 采用二部图映射扩散，在离散结构逆向恢复时产生严重分布崩塌，无论在交叠测度还是特征 MMD 上误差均超出其他基线数个数量级。

亮点与洞察¶

创新性地在矩形松弛关联矩阵空间建立了两侧超图热核与 OU 过程的融合扩散，巧妙平衡了基于数据内生拓扑的平滑去噪与无偏各向同性高斯基分布的构建。
将传统打分匹配中难以估计的边际分数，通过前向条件的线性高斯性转换为完全闭式的条件逆向漂移监督信号，并给出了严格的 $L^2$ 一致性与 Wasserstein 有限时界收敛保证。
理论建立的 $S_n \times S_m$ 置换等变性分析直接打通了经典双谱理论与现代几何深度学习网络设计的连结，具有直接迁移至加权图、双向图或张量高阶关系生成任务的广泛潜力。

局限与展望¶

固定尺度约束：当前评估框架依托固定维度的子超图采样，对于具有动态、开放可变节点与超边数量的生成任务尚未给出自适应尺度处理方案。
硬约束后验投影缺失：最终生成的二值关联矩阵由简单的标量阈值截断（0.5）产生，虽实测 99.34% 的松弛数值自然聚集在 0 或 1 附近，但缺乏防止孤立节点、空超边产生或严格度序列保留的显式组合约束。
计算复杂度瓶颈：尽管引入了 Kronecker 谱解耦将状态更新降至 $\mathcal{O}(nm)$，但前期单次精确谱分解仍具有 $\mathcal{O}(n^3 + m^3)$ 复杂度，限制了超大规模超图的全量端到端联合建模，未来亟需探索局部算子近似或随机截断 Lanczos 加速。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出在连续关联矩阵空间融合双侧超图谱算子与 OU 扩散，理论推导严谨闭环。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖 6 个真实基准与多套合成体制，实验设计严谨，包含完整的统计检验。
写作质量: ⭐⭐⭐⭐⭐ 数学证明详实严整，动机清晰，方法脉络层层递进。
价值: ⭐⭐⭐⭐⭐ 为超图生成提供了颠覆传统二部图或成对降维的全新范式，对高阶复杂网络研究极具启发意义。