Hypergraph Representation Learning with Hyperlink Random Effects¶

会议: NeurIPS 2026
arXiv: 2610.04640
代码: https://anonymous.4open.science/r/Hypergraph-Representation-Learning-7463
领域: 图学习
关键词: 超图表示学习、随机效应模型、低秩结构、变分EM算法、潜在异质性

一句话总结¶

针对非均匀超图中超边生成机制异质且缺乏紧凑低秩结构的难题，本文提出超边随机效应（HRL）统计表示学习框架，通过节点嵌入与超边随机效应的内积核刻画多体交互，提供严谨参数可识别性与统计恢复理论，并针对分类、高斯混合与基于分数的扩散先验推导了高效变分EM求解算法。

研究背景与动机¶

超图作为刻画实体间非对称、多元交互（multi-way interactions）的自然工具，在医学诊断事件、食谱成分配伍、推荐协同过滤等领域被广泛应用。然而，从复杂的组合超图结构中提取紧凑、可解释的实体低秩表示一直面临若干核心挑战。现有基于深度神经网络的超图学习方法（如 HyperGCN、AllSet 等）主要侧重于预测驱动的邻域聚合，并未显式约束或利用交互底层的低秩结构，不仅计算负担繁重，而且学到的嵌入难以获得统计一致性保证；另一方面，经典的张量分解与图投影方法要么要求超边具有严格统一的阶数，在面对非均匀（non-uniform）超边时需要人为填充虚拟节点，要么在投影为两两二元图时丢失了高阶多元依赖。

更关键的根本矛盾在于超边形成机制的潜在异质性（latent heterogeneity）。在真实场景中，相同的实体组合可能由完全不同的底层机理驱动产生。例如在临床电子病历中，相似的一组症状可能由完全不同的急重症或慢性合并症引发；传统的超图表示模型显式或隐式假设超边在给定节点状态下服从齐次分布，将所有超边置于全局均一的生成分布中，抹杀了超边层级的生成异质性。而若简单为每个超边赋予独立的固定效应参数，参数量又会随超边数量线性激增，导致新超边冷启动预测困难且无法共享群体层级的先验统计信息。

本文的切入角度是引入统计学中的随机效应机制：让每个节点拥有反映全局交互特征的潜在嵌入和度参数，同时将每个超边视为来自特定潜在分布的超边随机效应抽样，既统一建模了非均匀超边的多体交互，又自然解耦了节点共性规律与超边局部机理。核心 idea：将超边视为潜在随机效应的独立实现，提出一套融合低秩交互核的超边随机效应表示学习框架（HRL），在确立严格参数可识别性与表示恢复一致性理论的基础上，实例化分类（HRL-Cat）、高斯混合（HRL-GM）与基于分数扩散过程（HRL-Score）三类随机效应先验，并推导出了闭式变分 EM 与去噪分数匹配算法。

方法详解¶

整体框架¶

给定包含 $n$ 个节点和 $m$ 条超边的超图 $\mathcal{H}([n], \mathcal{E}_m)$，其中每条超边 $e_j \subseteq [n]$ 可以包含任意数量的节点。模型为每个节点 $i \in [n]$ 分配一个 $d$ 维低秩潜在嵌入 $\mathbf{z}_i \in \mathbb{R}^d$ 以及刻画节点固有流行度的度参数 $\alpha_i \in \mathbb{R}$；同时为每条超边 $j \in [m]$ 引入一个潜在随机效应向量 $\mathbf{f}_j \in \mathbb{R}^d$，其独立同分布地抽取自超边先验分布 $\mathbb{P}_{\mathbf{F}}$。

在给定超边随机效应 $\mathbf{f}_j$ 与节点参数 $(\mathbf{z}_i, \alpha_i)$ 的条件下，节点 $i$ 是否属于超边 $e_j$ 的二值指示变量 $\mathbf{1}_{\{i \in e_j\}}$ 服从独立的伯努利分布，其对数几率（logit）由内积相容性核决定： $$\mathbb{P}(i \in e_j \mid \mathbf{f}_j, \mathbf{z}_i, \alpha_i) = \sigma(\mathbf{f}_j^\top \mathbf{z}_i + \alpha_i), \quad \sigma(x) = \frac{e^x}{1+e^x}$$ 边际似然函数通过对潜在分布 $\mathbb{P}_{\mathbf{F}}$ 积分消除随机效应 $\mathbf{f}$。针对不同应用对随机效应复杂度的需求，本文构建了三类具体的随机效应规范：离散类别的 HRL-Cat、连续混合群体的 HRL-GM 以及基于随机微分方程先验的连续非高斯 HRL-Score。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["非均匀超图多重集<br/>节点集合与超边关联矩阵"] --> B["超边随机效应建模<br/>解耦节点共享属性与超边异质机理"]
    B --> C["可识别性正规化约束<br/>均值中心化、协方差白化与特征正交对齐"]
    C --> D["三类先验与对应推断引擎<br/>类别EM、混合高斯变分EM、分数扩散匹配"]
    D --> E["参数估计与表征投影<br/>恢复节点嵌入、度参数与超边生成分布"]

关键设计¶

1. 超边随机效应建模：解耦节点共享嵌入与超边形成异质性 传统超图表征要么只关注节点表征忽略超边异质性，要么为每个超边赋予独立自由参数导致超参数爆炸。该设计将超边形成机制视为潜在变量 $\mathbf{f}_j \sim \mathbb{P}_{\mathbf{F}}$，节点 $i$ 包含于超边 $j$ 的概率满足 $\text{logit}(\mathbb{P}(i \in e_j \mid \mathbf{f}_j)) = \mathbf{f}_j^\top \mathbf{z}_i + \alpha_i$。此设计具有三重理论与实用优势：第一，任意大小的超边均由相同的低秩向量维度 $d$ 参数化，自然规避了张量方法阶数固定的硬性约束；第二，$\mathbb{P}_{\mathbf{F}}$ 使得超边之间得以共享群体层级的生成规律，面对仅部分观测的新超边具备严谨的经验贝叶斯后验推断能力；第三，在理论证明中，即便超边内部的节点指示变量存在未建模的局部条件依赖，该边际似然作为工作似然（working law）依然能够渐进一致地恢复真实节点共享表示。

2. 可识别性正规化：消除旋转、平移与尺度不确定性 在内积核形式下，对于任意平移向量 $\boldsymbol{\mu} \in \mathbb{R}^d$ 与非奇异变换矩阵 $\mathbf{A} \in \mathbb{R}^{d \times d}$，做变换 $\mathbf{f}' = \mathbf{A}^\top(\mathbf{f} - \boldsymbol{\mu})$、$\mathbf{z}_i' = \mathbf{A}^{-1}\mathbf{z}_i$ 及 $\alpha_i' = \alpha_i + \boldsymbol{\mu}^\top \mathbf{z}_i$，其内积加截距的值严格保持不变。为了使得参数在统计上具备可解释性与唯一性，本文构建了完备的正规化规范： $$\mathbb{E}_{\mathbb{P}_{\mathbf{F}}}(\mathbf{f}) = \mathbf{0}_d, \quad \mathcal{S}(\mathbb{P}_{\mathbf{F}}) = \mathbf{I}_d, \quad \mathbf{Z}^\top \mathbf{Z} = \text{diag}(\lambda_1, \ldots, \lambda_d), \quad \lambda_1 > \cdots > \lambda_d > 0$$ 其中 $\mathcal{S}(\cdot)$ 为等变正定尺度泛函（如二阶矩或协方差）。零均值约束锁定了潜空间的中心平移，尺度恒等约束消除了通用可逆线性变换将其约束至正交群，对 $\mathbf{Z}^\top \mathbf{Z}$ 施加严格降序特征值对角化则消除了任意旋转与坐标置换，使得模型参数在相差坐标轴符号翻转（sign-flip）的意义下严格可识别。

3. 多模态先验与变分推断：兼顾解析闭式解与非高斯扩散表达力 针对不同异质性形态，本文设计了由浅入深的推断架构： - 类别随机效应（HRL-Cat）：假设 $\mathbb{P}_{\mathbf{F}} = \sum_{k=1}^K \pi_k \delta_{\mathbf{f}_k}$。通过经典 EM 迭代更新超边类别后验响应度与类别发生率矩阵 $\mathbf{Q} \in (0,1)^{K \times n}$，最后借助低秩 logit 奇异值分解（SVD）闭式提取 $\mathbf{Z}$ 与 $\mathbf{F}$。 - 高斯混合随机效应（HRL-GM）：假设 $\mathbb{P}_{\mathbf{F}} = \sum_{k=1}^K \pi_k \mathcal{N}(\boldsymbol{\mu}_k, \boldsymbol{\Sigma})$。由于逻辑斯蒂似然与高斯先验非共轭，采用 Jaakkola-Jordan 局部变分下界引入逐项变分参数 $\xi_{jik}$，将后验转化为解析高斯形式，在 M 步推导出 $\mathbf{z}_i$、$\alpha_i$、$\boldsymbol{\mu}_k$ 的解析闭式更新公式。 - 基于分数的随机效应（HRL-Score）：利用保方差随机微分方程（VPSDE）建立非参数扩散先验 $\mathbb{P}_{\mathbf{F}, \boldsymbol{\theta}}$，在 E 步使用重要性重采样后验粒子估计一阶与二阶矩，在 M 步联合闭式更新 $(\mathbf{z}_i, \alpha_i)$，并通过似然加权去噪分数匹配（denoising score matching）优化分数网络 $\boldsymbol{\theta}$，能无缝适应非高斯与厚尾超边生成机制。

损失函数 / 训练策略¶

对于 HRL-GM 与 HRL-Score，算法通过极大化包含 Jaakkola-Jordan 变分下界的对证对数似然（ELBO）进行优化。以 HRL-Score 为例，在第 $t$ 轮迭代中，先通过逆扩散采样与重要性权重估计后验统计量： $$\bar{w}_{jb} \propto \exp\left(\mathbf{b}_j^\top \mathbf{f}^{(b)} - \frac{1}{2}\mathbf{f}^{(b)\top} \mathbf{A}_j \mathbf{f}^{(b)}\right), \quad \widehat{\mathbf{m}}_j = \sum_{b=1}^B \bar{w}_{jb} \mathbf{f}^{(b)}, \quad \widehat{\mathbf{S}}_j = \sum_{b=1}^B \bar{w}_{jb} \mathbf{f}^{(b)}\mathbf{f}^{(b)\top}$$ 随后联合求解节点参数的稳健块更新： $$\begin{pmatrix} \mathbf{z}_i \\ \alpha_i \end{pmatrix} = \left[ 2 \sum_{j=1}^m \eta(\xi_{ji}) \begin{pmatrix} \widehat{\mathbf{S}}_j & \widehat{\mathbf{m}}_j \\ \widehat{\mathbf{m}}_j^\top & 1 \end{pmatrix} \right]^{-1} \left[ \sum_{j=1}^m \left(v_{ji} - \frac{1}{2}\right) \begin{pmatrix} \widehat{\mathbf{m}}_j \\ 1 \end{pmatrix} \right]$$ 同时通过最小化去噪分数匹配损失更新扩散网络 $\boldsymbol{\theta}$： $$\mathcal{L}_{\text{DSM}}(\boldsymbol{\theta}) = \mathbb{E}\left[ \frac{w_{\text{ll}}(\tau)}{2 r_{\text{ll}}(\tau)} \|\boldsymbol{\epsilon} - \boldsymbol{\epsilon}_{\boldsymbol{\theta}}(\mathbf{f}_\tau, \tau)\|_2^2 \right]$$ 算法迭代直到 $\|\mathbf{Z}^{(t+1)} - \mathbf{Z}^{(t)}\|_F \le \epsilon$，最终执行中心化、协方差白化与特征分解旋转得到正规化解。

实验关键数据¶

主实验¶

在未见超边冷启动预测任务（Row-disjoint cold-start，观测比例 $r_{\text{obs}}=0.2$）中，模型在食物食谱（Food Recipe）、MIMIC-III 重症病历（ICD-9 代码）以及 MovieLens 电影超图上与经典二部图模型、超图神经网络展开对比（测试集评估 AUROC、AUPRC、BCE 与 Brier 分数）：

数据集	指标	HRL-Score (本文)	HRL-GM (本文)	HRL-Fixed (基线)	NeuMF	AllSet	MultiVAE
Food Recipe	AUROC ↑	0.826	0.827	0.769	0.755	0.758	0.789
Food Recipe	AUPRC ↑	0.195	0.194	0.130	0.132	0.123	0.147
Food Recipe	BCE ↓	0.120	0.121	0.206	0.133	0.131	0.127
Food Recipe	Brier ↓	0.029	0.030	0.041	0.031	0.031	0.030
MIMIC-III	AUROC ↑	0.796	0.795	0.745	0.768	0.765	0.769
MIMIC-III	AUPRC ↑	0.436	0.437	0.337	0.386	0.378	0.386
MIMIC-III	BCE ↓	0.314	0.315	0.506	0.330	0.331	0.330
MIMIC-III	Brier ↓	0.093	0.093	0.111	0.097	0.098	0.098
MovieLens	AUROC ↑	0.776	0.783	0.767	0.754	0.659	0.652
MovieLens	AUPRC ↑	0.703	0.712	0.682	0.664	0.572	0.569
MovieLens	BCE ↓	0.552	0.545	0.617	0.576	0.635	0.638
MovieLens	Brier ↓	0.187	0.184	0.199	0.196	0.222	0.223

消融与鲁棒性实验¶

在合成数据集上评估不同随机效应分布假设对节点潜在嵌入恢复（Frobenius 误差）以及超边聚类划分（ARI / NMI）的影响。实验对比了标准高斯混合先验与自由度 $df=4$ 的重尾 $t$-分布混合先验（超边数 $m=3000$）：

先验生成机理	评估方法	ARI ↑	NMI ↑	嵌入恢复误差 $\frac{\\|\widehat{\mathbf{Z}}-\mathbf{Z}^*\\|_F}{\sqrt{nd}}$ ↓	说明
高斯混合 (GM)	HRL-Cat	0.961	0.955	0.138	离散分类逼近混合连续分布
高斯混合 (GM)	HRL-GM	0.962	0.956	0.118	模型假设完全匹配真实机理
高斯混合 (GM)	HRL-Score	0.965	0.959	0.125	扩散模型自适应拟合高斯混合
高斯混合 (GM)	HRL-Fixed	0.962	0.956	0.152	固定效应基线，参数量大
重尾 $t$-混合 ($df=4$)	HRL-Cat	0.322	0.488	0.412	无法捕获厚尾离群交互
重尾 $t$-混合 ($df=4$)	HRL-GM	0.344	0.510	0.389	高斯方差假设在厚尾下失效
重尾 $t$-混合 ($df=4$)	HRL-Score	0.954	0.943	0.142	分数扩散准确捕获复杂非高斯厚尾
重尾 $t$-混合 ($df=4$)	HRL-Fixed	0.314	0.471	0.428	固定点估计受极端值扰动严重崩溃

关键发现¶

冷启动与稀疏观测优势显著：当新超边的已观测比例极低（$r_{\text{obs}}=0.2$）时，随机效应模型相较固定效应基线（HRL-Fixed）展现出压倒性优势（MIMIC-III 上 AUPRC 从 0.337 提升至 0.437，BCE 从 0.506 骤降至 0.314）。这是因为随机效应模型能够利用训练集中学到的群体先验分布 $\mathbb{P}_{\mathbf{F}}$ 作为正则，而固定效应仅凭有限的观测点极易过拟合。
非高斯厚尾场景下的稳健性：在合成重尾实验中，HRL-Cat 与 HRL-GM 的聚类 ARI 均暴跌至 0.34 附近，唯独 HRL-Score 保持在 0.954 的极高水准，验证了基于分数的连续扩散过程对于复杂多模态、厚尾极端分布的拟合适应能力。
医学表型无监督发现：在 MIMIC-III 的 ICD-9 节点聚类中，HRL-Score（$G=7$）展现出极具临床语义一致性的聚类划分，能够精准剥离原发性急性冠状动脉疾病与合并代谢病症，清晰隔离糖尿病特发性并发症与慢性肾病表型。

亮点与洞察¶

解耦超边多体异质性：巧妙运用统计学随机效应理论解决图表示学习中长期存在的“齐次假设与阶数刚性”问题，既不受超边包含节点数量变化的限制，又避免了张量填充带来的伪信息。
严格的可识别性与统计理论：为非线性逻辑斯蒂超图嵌入模型推导了完备的可识别性条件，并在放宽超边内部节点条件独立假设的情形下，证明了全局最大化估计量的统计一致性界。
理论统计与前沿生成模型的融合：将扩散 SDE 架构无缝嵌入到经典 EM 算法的先验建模中，用经验贝叶斯后验粒子采样替代复杂的解析变分分布，大幅拓宽了随机效应模型的表现力。

局限与展望¶

低秩结构错配风险：模型强依赖于节点交互的低秩假设，若超图的生成机制具备复杂的局部高秩或强稀疏组合逻辑，内积核的表达能力可能受限。
计算复杂度与局部极值：EM 算法对初始值具备一定敏感性（需依赖 USVT 谱阈值化辅助初始化）；HRL-Score 在 E 步严重依赖蒙特卡洛粒子重采样，采样规模 $B$ 较大时在超大规模图上的训练时间将显著增加。
扩展性边界：当前模型仅针对静态、无属性的单一超图设计，未来亟需拓展至包含节点属性、动态时序演化以及多层异构交互网络的超图场景。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统性地将随机效应与基于分数的扩散先验引入非均匀超图低秩表示学习，理论框架完备。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖合成厚尾混合、真实冷启动、节点语义聚类及多标签分类，对比方法详实深入。
写作质量: ⭐⭐⭐⭐⭐ 统计理论阐述严密，算法推导清晰，理论与经验分析紧密咬合。
价值: ⭐⭐⭐⭐⭐ 为超图这一高阶关系数据的表示学习建立了优雅的统计学基石，实用价值与方法学启发巨大。