第 2H 章补充正文：超图表示与随机超图模型
第 2H 章 超图表示与随机超图模型（Hypergraph Representations and Random Hypergraph Models）
许多网络数据由成对关系构成，例如两位用户之间的通信或两个网页之间的链接。然而，一篇由多位作者共同完成的论文、一次多人会议和一张包含若干商品的购物篮，原始观测单位都是一个节点集合。若把每个集合立即展开成所有节点对，得到的图可以记录两两共现，却可能无法判断若干条边究竟来自同一次群体事件，还是来自多次彼此独立的成对事件。超图以节点集合为基本关系单位，因而为这类数据提供了直接表示。
论文作者表、多人邮件收件人和一次化学反应的参与物直接给出节点集合；由位置轨迹划定接触群体或由脑信号识别共同激活集合，则要先选择阈值、时间窗或统计识别方法。两类数据最终都表示为 $H=(V,\mathcal E,w)$。
对构造得到的超边，构造规则属于观测机制。阈值和时间窗会改变超边数、大小、重叠及社区结构，因此结果应同时记录构造参数、敏感性分析和两级不确定性。
内容依次覆盖超图表示、随机基线、随机游走、随机分块模型、四类推断方法、社区恢复术语和生成式检查。模型主线与第 2 章平行：Erdős–Rényi 图对应独立随机超图，SBM 对应 simple HSBM，DC-SBM 对应带节点活跃度参数的 Poisson DCHSBM。
2H.1 超图与表示（Hypergraphs and Representations）
2H.1.1 基本对象与记号
有限简单加权超图记为
$$ H=(V,\mathcal E,w), \tag{2H.1} $$其中 $V=\{1,\ldots,n\}$ 是节点集，$\mathcal E\subseteq 2^V\setminus\{\varnothing\}$ 是超边族，$w:\mathcal E\to(0,\infty)$ 是超边权重。普通集合族 $\mathcal E$ 表示简单超图（simple hypergraph）：每个节点集合至多出现一次，每条超边由互异节点组成。重复事件使用带索引的超边族；边内节点可重复时使用节点多重集合。
描述层允许 $|e|=1$ 的单节点事件；从第 2H.2 节起，“交互”与随机候选超边默认满足 $|e|\ge2$。二元（无权）简单超图取 $w\equiv1$。重复次数对应 $w(e)\in\mathbb N$，持续时间、剂量或强度可取一般正实数。单节点事件 $\{v\}$ 的大小为 1；多重集合自环 $\{\!\{v,v\}\!\}$ 的大小为 2。重数、连续权重与边内节点重复对应三种不同的样本空间。
若 $\mathcal E\ne\varnothing$，超图的秩为 $\operatorname{rank}(H)=\max_{e\in\mathcal E}|e|$；对空超边族约定 $\operatorname{rank}(H)=0$。若 $\mathcal E\ne\varnothing$ 且所有超边均满足 $|e|=d$，则称 $H$ 为 $d$-均匀超图（$d$-uniform hypergraph）。普通无向图是 $d=2$ 的特例。
作为贯穿本章的例子，令
$$ V=\{1,2,3,4,5\},\qquad \mathcal E=\{e_1,e_2,e_3\}, $$
其中
$$ e_1=\{1,2\},\qquad e_2=\{1,2,3\},\qquad e_3=\{3,4,5\}, $$
且 $w(e_1)=w(e_2)=w(e_3)=1$。该超图同时含二元和三元超边，所以它是非均匀简单超图。
该例有 $n=5$ 个节点和 $M=3$ 条超边，超边大小为 $(2,3,3)$，故 $\operatorname{rank}(H)=3$ 且图非均匀。关系 $e_2\cap e_3=\{3\}$ 展示超边重叠，$e_1\subset e_2$ 展示超边包含。
有些文献把 $|V|$ 称为 hypergraph order、把 $|\mathcal E|$ 称为 hypergraph size，也常用“阶数”描述 $|e|$。以下统一使用“节点数 $n$”“超边数 $M$”“超边大小 $|e|$”和“秩 $\max_e|e|$”。
单纯复形（simplicial complex）在超图定义上增加向下闭合条件：若集合 $e$ 属于复形，则 $e$ 的每个子集也属于复形。一般超图允许任意超边族。例如，一次三人会议可以作为单独事件记录，是否同时记录两人子集由数据生成语义决定（Bick et al., 2023）。
2H.1.2 关联矩阵与星形展开
图 2H.1 把这个对象放进四个常用计算入口。
超图的节点—超边关联矩阵（incidence matrix）$B\in\{0,1\}^{n\times |\mathcal E|}$ 定义为
$$ B_{ve}=\mathbf 1\{v\in e\}. $$
贯穿例子的关联矩阵为
$$ B= \begin{pmatrix} 1&1&0\\ 1&1&0\\ 0&1&1\\ 0&0&1\\ 0&0&1 \end{pmatrix}. \tag{2H.2} $$
节点 $v$ 的加权关联度、未加权关联度和超边 $e$ 的大小分别记为
$$ d(v)=\sum_{e\in\mathcal E}w(e)B_{ve}, \qquad d_0(v)=\sum_{e\in\mathcal E}B_{ve}, \qquad \delta(e)=\sum_{v\in V}B_{ve}=|e|. \tag{2H.3} $$
在例子中所有权重均为 1，因而 $d=d_0$，节点关联度向量为 $(2,2,2,1,1)$，超边大小向量为 $(2,3,3)$。$d_0(v)$ 计数节点参与了多少个不同事件，$d(v)$ 则累计这些事件的权重；只有在权重均为 1 时，两句话才可以互换。超边大小 $\delta(e)$ 描述单个事件包含多少个节点，与两类节点关联度承担不同的统计含义。后文的无权随机超图中，$D_i$ 指 $d_0(i)$。
对 $r\ge1$，令 $\mathcal E_r=\{e\in\mathcal E:|e|=r\}$，并记 $\mathcal E_{\ge2}=\bigcup_{r\ge2}\mathcal E_r$。对简单超图，交互层的分阶密度、分阶关联度与总关联度分别为
$$ \rho_r=\frac{|\mathcal E_r|}{\binom nr}, \qquad d_r(v)=\sum_{e\in\mathcal E_r}\mathbf1\{v\in e\}, \qquad d_{\ge2,0}(v)=\sum_{r\ge2}d_r(v), \qquad d_0(v)=d_1(v)+d_{\ge2,0}(v). \tag{2H.3a} $$若最大允许超边大小事先固定为 $R$，还可以定义总体密度
$$ \rho_{\le R} =\frac{|\mathcal E_{\ge2}|}{\sum_{r=2}^{R}\binom nr} =\frac{\sum_{r=2}^{R}|\mathcal E_r|}{\sum_{r=2}^{R}\binom nr}, \tag{2H.3b} $$式 (2H.3b) 假定研究设计允许的交互大小为 $2,\ldots,R$，因而分子也只计这些阶数。若数据保留单节点事件，应以 $|\mathcal E_1|$ 单独报告，不把它混入交互密度。若把观测最大值直接当作 $R$，分母会随样本极值改变，跨数据集可比性也随之改变。贯穿例子中 $\mathcal E_1=\varnothing$、$n=5$、$|\mathcal E_2|=1$、$|\mathcal E_3|=2$，所以 $d_0=d_{\ge2,0}$、$\rho_2=1/10$、$\rho_3=2/10$；若预先规定候选空间包含二元和三元事件，则 $\rho_{\le3}=3/(10+10)=3/20$。
开始拟合模型前，至少同时检查分阶关联度 $(d_r(v))$、总关联度、超边大小分布、分阶密度 $(\rho_r)$ 和超边重叠；若原始数据允许同一事件重复，还要检查权重或重数。分阶关联度尤其重要：某个节点可能只在大型事件中活跃，把各阶度数相加会隐藏这种机制差异。
节点 3 对应的行是 $(0,1,1)$，所以它参加了 $e_2,e_3$ 两个事件，$d_0(3)=d(3)=2$。超边 $e_2$ 对应的列是 $(1,1,1,0,0)^T$，所以 $\delta(e_2)=3$。所有行和为 $2+2+2+1+1=8$，所有列和为 $2+3+3=8$；二者都是对关联矩阵中全部 1 的计数：
$$ \sum_{v\in V}d(v)=\sum_{e\in\mathcal E}\delta(e)w(e)=8. $$复算点：若把 $e_3$ 的权重改为 2，左侧应变为 $(2,2,3,2,2)$ 的元素和 11；右侧则为 $2+3+2\times3=11$。
星形展开（star expansion）把每条超边变成第二类节点，从而得到二部图
$$ G_\star=(V\sqcup\mathcal E,E_\star), \qquad E_\star=\{(v,e):v\in e\}. $$
若原节点排在前、超边节点排在后，则该二部图的邻接矩阵为
$$ A_\star= \begin{pmatrix} 0&B\\ B^T&0 \end{pmatrix}. \tag{2H.4} $$
对普通简单超图，关联矩阵和星形展开都保留超边身份：给定一列 $B_{\bullet e}$ 或事件节点 $e$ 的邻居集合，可以恢复原超边。星形展开包含“实体节点”和“事件节点”两类对象；应用普通图算法时，两侧节点类型应分别编码和解释。
这个对应关系在含重复事件的数据中更值得仔细写。给定一个已指定两侧语义的简单二部图
$$ G_B=(V\sqcup U,F), \qquad \mathcal E^\sharp=(e_u)_{u\in U}, \qquad e_u=N_{G_B}(u)\cap V, \tag{2H.4a} $$
其中 $U$ 是没有孤立节点的事件节点集，$(e_u)_{u\in U}$ 是带事件索引的超边族。具有相同邻域的两个事件节点对应两次成员相同而身份不同的事件；度为 1 的事件节点对应单节点事件。保留 $U$ 的事件身份后，式 (2H.4a) 与二部图在事件节点重命名意义下一一对应。两侧的“实体—事件”语义也属于数据定义；交换 $V$ 与 $U$ 会产生以原事件为节点的对偶关联对象。
若随后强制投到“无重复且只含交互”的简单超图空间，例如取
$$ \mathcal E_{\mathrm{simp},\ge2} =\operatorname{uniq}\{e_u:u\in U,\ |e_u|\ge2\}, \tag{2H.4b} $$
式 (2H.4b) 合并相同邻域并过滤单节点事件，因此不再保留原来的事件数与事件身份。其中 $|e_u|\ge2$ 选取交互事件，$\operatorname{uniq}$ 将重复列压成一个集合；这两步都会使映射不可逆。
把一个已经观测的超图确定性地写成 $B$ 或 $G_B$ 时，节点、事件和全部关联都已固定，没有引入概率假设。若改为在固定的 $V\sqcup U$ 上随机生成二部边 $X_{vu}$，则 $|U|$ 个事件槽在采样前已经给定；随机的是每个槽由哪些节点参加。除非额外条件化，这种模型还可能生成空列、单节点列和重复列。
直接的 Bernoulli 超图模型为每个候选节点集合 $e$ 生成出现指标 $Y_e$，实现后的超边数 $M_H=\sum_eY_e$ 通常是随机的。“固定 $|U|$、随机成员关系”和“固定候选集合、随机哪些超边出现”因此具有不同的样本空间；二者之间的渐近联系需要单独证明。
在二部 SBM 中，令实体节点标签 $Z_v\overset{\mathrm{iid}}{\sim}\operatorname{Categorical}(\pi)$、事件节点标签 $C_u\overset{\mathrm{iid}}{\sim}\operatorname{Categorical}(\eta)$，并令 $\Theta_{qs}$ 为跨两侧群组的连接概率。给定 $(Z,C)$ 后，所有关联变量 $(X_{vu})$ 条件独立。于是，一个固定事件槽同时包含标签为 $q_1,\ldots,q_r$ 的给定节点的概率具有乘积混合形式
$$ X_{vu}\mid(Z_v=q,C_u=s)\sim\operatorname{Bernoulli}(\Theta_{qs}), \qquad \mathbb P(X_{i_1u}=\cdots=X_{i_ru}=1\mid Z) =\sum_{s=1}^{S}\eta_s\prod_{t=1}^{r}\Theta_{q_t s}. \tag{2H.4c} $$式 (2H.4c) 给出一个事件槽至少包含这 $r$ 个节点的概率。若要求 $N(u)$ 恰好等于这组节点，还需乘上其余节点不连接的概率；多个事件槽还涉及重复邻域与去重。二部 SBM 预设有限个事件群组，并把参与概率参数化为有限个乘积项的混合；一般 HSBM 则允许更一般的对称亲和张量。
| 对象 | 采样前固定什么 | 随机什么 | 对超边数与事件身份的含义 |
|---|---|---|---|
| 已观测超图的星形展开 | $V$、事件族及全部关联 | 无 | 事件身份保留；确定性表示 |
| 固定两侧的随机二部图 | $V$ 与 $U$，故事件槽数 $|U|$ 固定 | 关联变量 $(X_{vu})$ | 每个槽的成员随机；可能出现空、单节点或重复事件 |
| 候选集合上的 Bernoulli 超图 | $V$ 与允许的候选集合 | 出现指标 $(Y_e)$ | 实现超边数通常随机；每个候选集合至多出现一次 |
| 二部 configuration 型零模型 | 行和、列和及事件槽数 | 满足边际的关联排列 | 节点总度和事件大小固定，节点与事件大小的对应关系随关联排列变化 |
2H.1.3 节点投影、事件线图与信息损失
团投影（clique projection）或 2-截面（2-section）把每条超边内部的所有节点对连接起来。一种直接的共现权重为
$$ A^{\mathrm{raw}}_{uv} =\sum_{e\in\mathcal E}B_{ue}B_{ve}, \qquad u\ne v. \tag{2H.5} $$
在贯穿例子中，节点对 $\{1,2\}$ 同时出现在 $e_1$ 和 $e_2$ 中，故 $A^{\mathrm{raw}}_{12}=2$；节点对 $\{1,3\}$ 只出现在 $e_2$ 中，故 $A^{\mathrm{raw}}_{13}=1$。投影保留了两两共现次数，却不再说明 $A^{\mathrm{raw}}_{12}=2$ 分别来自一条二元超边和一条三元超边。
若所有超边大小至少为 2，并希望每条权重为 $w(e)$ 的超边对其中每个节点贡献总图度 $w(e)$，可以采用归一化权重
$$ A^{\mathrm{cl}}_{uv} =\sum_{e\in\mathcal E:\,u,v\in e} \frac{w(e)}{\delta(e)-1}, \qquad u\ne v. \tag{2H.6} $$
此时贯穿例子中 $A^{\mathrm{cl}}_{12}=3/2$，$A^{\mathrm{cl}}_{13}=A^{\mathrm{cl}}_{23}=1/2$，投影图的加权度仍为 $(2,2,2,1,1)$。式 (2H.5) 和式 (2H.6) 都是常见的团投影约定；投影结果应同时注明权重和归一化规则。
不同超图可能产生同一张投影图。投影对推断目标是否充分取决于目标量：节点对共现强度可以由合适的投影保留，超边大小、事件身份和一条超边中的标签组成通常会在团投影中丢失。
令 $H_1$ 只有一条超边 $\{1,2,3\}$，令 $H_2$ 有三条超边 $\{1,2\},\{1,3\},\{2,3\}$。两者的式 (2H.5) 投影都满足三个非对角元素为 1，因此只给定投影矩阵时无法判定原始数据包含一次还是三次事件。
然而，两者的关联矩阵分别有 1 列和 3 列，超边大小序列分别为 $(3)$ 与 $(2,2,2)$。如果研究问题是“群体事件有多大”，投影显然不充分；如果问题只要求判断三对节点是否曾经共现，则这次信息损失可能无关紧要。
团投影把原节点留作图节点；线图（line graph）恰好反过来，把每条超边视为一个事件节点。对不同超边 $e,f$，定义事件重叠矩阵
$$ O_{ef}= \begin{cases} |e\cap f|,&e\ne f,\\ 0,&e=f. \end{cases} \tag{2H.6a} $$若 $D_e=\operatorname{diag}(\delta(e_1),\ldots,\delta(e_M))$，则 $O=B^TB-D_e$。无权线图在 $O_{ef}>0$ 时连接 $e$ 与 $f$；以 $O_{ef}$ 为边权则保留重叠节点的数量。对贯穿例子，
$$ O= \begin{pmatrix} 0&2&0\\ 2&0&1\\ 0&1&0 \end{pmatrix}. $$因此 $e_2$ 同时连接 $e_1$ 与 $e_3$，而 $e_1,e_3$ 不相交。若只保留无权线图，就连“共享 1 个还是 2 个节点”也会丢失；即使保留 $O$，仍无法知道具体共享的是哪些节点。把邻接门槛改为 $O_{ef}\ge k$ 可以研究至少共享 $k$ 个成员的事件链，但它同样是对原超图的压缩。
对整数 $k\ge1$，令 $\mathcal E_{\ge k}=\{e\in\mathcal E:|e|\ge k\}$。$k$-线图 $L_k(H)$ 以 $\mathcal E_{\ge k}$ 中的超边为节点，并且只在 $|e\cap f|\ge k$ 时连接 $e,f$。等价地，一条长度为 $\ell$ 的 $k$-walk 是超边序列
$$ e_{i_0},e_{i_1},\ldots,e_{i_\ell}, \qquad e_{i_t}\in\mathcal E_{\ge k}, \qquad |e_{i_{t-1}}\cap e_{i_t}|\ge k \quad(t=1,\ldots,\ell). \tag{2H.6b} $$
两条超边间的 $k$-distance 是最短 $k$-walk 的长度；若不存在则记为 $\infty$。它就是 $L_k(H)$ 上的普通图距离。贯穿例子中，$e_1\to e_2\to e_3$ 是长度 2 的 1-walk，所以 $d_1(e_1,e_3)=2$；但第二步只有 $|e_2\cap e_3|=1$，故 $e_3$ 在 $L_2(H)$ 中孤立，$d_2(e_1,e_3)=\infty$。参数 $k$ 控制事件邻接所需的重叠宽度。
2H.1.4 均匀超图的邻接张量
对 $d$-均匀简单超图，Cooper and Dutle (2012) 定义了 $d$ 阶对称邻接张量。其一种标准归一化为
$$ \mathcal A_{i_1\cdots i_d}= \begin{cases} \dfrac{1}{(d-1)!},&\{i_1,\ldots,i_d\}\in\mathcal E,\\ 0,&\text{其他情形}. \end{cases} \tag{2H.7} $$
固定首个指标后，每条包含该节点的超边对应其余 $d-1$ 个节点的 $(d-1)!$ 个排列，因此该归一化使张量在其余指标上求和时恢复节点关联度。对贯穿例子的三元子超图 $\{e_2,e_3\}$，非零张量元素取值为 $1/2$。标准三阶张量容纳这两条三元超边；二元超边 $e_1$ 需要分阶保存、空节点扩充或其他非均匀张量约定。
矩阵特征方程 $Ax=\lambda x$ 在 $d$ 阶张量上变为非线性方程。Cooper–Dutle 邻接张量的一个特征对 $(\lambda,x)$ 满足
$$ \mathcal A x^{d-1}=\lambda x^{[d-1]}, \qquad (\mathcal A x^{d-1})_i =\sum_{i_2,\ldots,i_d=1}^n \mathcal A_{ii_2\cdots i_d}x_{i_2}\cdots x_{i_d}, \tag{2H.7a} $$
其中 $x^{[d-1]}=(x_1^{d-1},\ldots,x_n^{d-1})^T$。与矩阵情形不同，这是一组 $d-1$ 次多项式方程；“取最大特征向量”需要先说明采用哪一种张量特征值概念、归一化和数值算法。
只取节点 $\{1,2,3\}$ 和超边 $\{1,2,3\}$。令 $x=(1,1,1)^T$。对第 1 个坐标，只有 $(i_2,i_3)=(2,3),(3,2)$ 两项非零，故
$$ (\mathcal A x^2)_1 =\tfrac12x_2x_3+\tfrac12x_3x_2=1=x_1^2. \tag{2H.7b} $$另外两个坐标同理，所以 $(\lambda,x)=(1,\mathbf1)$ 是特征对。这个计算验证了式 (2H.7) 的排列归一化。
综上，关联矩阵和星形展开保留事件身份，团投影压缩为节点间共现，线图压缩为事件间重叠，邻接张量直接表达固定阶交互。表示选择先于算法选择，并决定了后续分析可用的信息。
2H.2 随机超图基线（Random Hypergraph Baselines）
2H.2.1 Bernoulli 模型 $H_d(n,p)$
固定节点集 $V=[n]$ 和整数 $d\ge2$。对每个候选 $d$-节点集合 $e\in\binom Vd$，独立生成
$$ X_e\sim\operatorname{Bernoulli}(p), \qquad \mathcal E=\{e:X_e=1\}. \tag{2H.8} $$
所得 $d$-均匀随机超图记为 $H_d(n,p)$。它是 Erdős–Rényi 模型 $G(n,p)$ 的直接高阶对应物。由于候选超边总数为 $\binom nd$，超边数满足
$$ |\mathcal E|\sim \operatorname{Binomial}\!\left(\binom nd,p\right), \qquad \mathbb E|\mathcal E|=\binom ndp. \tag{2H.9} $$
在 $H_d(n,p)$ 中，对任意固定节点 $i$，令 $D_i=|\{e\in\mathcal E:i\in e\}|$。则
$$ D_i\sim\operatorname{Binomial}\!\left(\binom{n-1}{d-1},p\right), \qquad \mathbb ED_i=\binom{n-1}{d-1}p. \tag{2H.10} $$ 在学习笔记中查看逐步完整证明8 个节点共有 $\binom83=56$ 条候选三元超边，所以 $\mathbb E|\mathcal E|=56\times0.1=5.6$。对固定节点 $i$，另两个端点可从其余 7 个节点中选择，故候选数为 $\binom72=21$，从而
$$ D_i\sim\operatorname{Binomial}(21,0.1),\qquad \mathbb ED_i=2.1,\qquad \mathbb P(D_i=0)=0.9^{21}\approx0.109. $$双重计数提供了立即可用的验算：$\sum_i\mathbb ED_i=8\times2.1=16.8$，而每条三元超边贡献 3 次关联，故 $3\mathbb E|\mathcal E|=3\times5.6=16.8$。该恒等式也可用来发现 $\binom83$ 与 $\binom72$ 的混用。
若希望 $n\to\infty$ 时平均关联度保持常数量级，应令
$$ p_n=\Theta\!\left(n^{-(d-1)}\right). $$
当 $d=2$ 时，该标度退化为随机图中的 $p_n=\Theta(1/n)$。这个标度控制节点参与的超边数；团投影邻居数还会受到每条 $d$ 元超边同时产生多个节点对的影响。
2H.2.2 固定超边数模型 $H_d(n,M)$
$H_d(n,M)$ 从 $\binom nd$ 条候选超边中均匀抽取 $M$ 条。由于总超边数固定，单个节点的关联度服从超几何分布：
$$ D_i\sim\operatorname{Hypergeometric}\!\left( \binom nd,\binom{n-1}{d-1},M \right), \qquad \mathbb ED_i=\frac{dM}{n}. \tag{2H.11} $$
式 (2H.11) 的期望也可由双重计数得到：所有节点关联度之和恒等于 $dM$。$H_d(n,p)$ 与 $H_d(n,M)$ 的区别正对应于 $G(n,p)$ 与 $G(n,M)$：前者使超边数随机，后者对超边数作条件化。
固定 $d\ge3$。Karoński and Łuczak (2002, Abstract and §1) 将 $H_d(n,M)$ 的相变尺度定位为
$$ M=\frac{n}{d(d-1)}+O(n^{2/3}). \tag{2H.12} $$粗粒度的三阶段数量级来自 Schmidt-Pruzan and Shamir (1985)，并由 Karoński and Łuczak (2002, §1) 回顾：若 $M=cn$，则以高概率在 $c<1/[d(d-1)]$ 时最大分量为对数阶，在 $c=1/[d(d-1)]$ 时最大分量规模为 $\Theta(n^{2/3})$，在 $c>1/[d(d-1)]$ 时出现唯一的线性阶巨分量。Karoński–Łuczak 进一步分析临界附近，并给出亚临界和早期超临界阶段最大分量规模的局部极限定理。$d=2$ 时相同临界尺度退化为经典随机图结论。上述连通性采用 Berge 路径口径。
该阈值可由分支过程给出直觉解释。若局部节点关联度近似分布为 $D$，沿一条已发现的超边到达节点后，可继续探索的事件数具有过剩均值 $\mathbb E[D(D-1)]/\mathbb ED$；每个新事件最多带来 $d-1$ 个节点。因此有效繁殖数近似为
$$ (d-1)\frac{\mathbb E[D(D-1)]}{\mathbb ED}. $$
对稀疏 $H_d(n,M)$，局部关联度渐近为均值 $\lambda=dM/n$ 的 Poisson 分布，过剩均值也为 $\lambda$。令 $(d-1)\lambda=1$，便得到 $M=n/[d(d-1)]$。
2H.2.3 非均匀独立超边模型
若允许超边大小属于 $\mathcal R\subseteq\{2,3,\ldots,M_0\}$，可以对不同阶数分别指定概率：
$$ X_e\sim\operatorname{Bernoulli}(p_{|e|}), \qquad \mathbb ED_i= \sum_{r\in\mathcal R}\binom{n-1}{r-1}p_r. \tag{2H.13} $$
要使每个阶数对平均关联度贡献常数量级，通常取 $p_r=\Theta(n^{-(r-1)})$。不同阶数共同影响分量增长和局部结构，需要分别纳入各层的概率与组合系数；最大秩 $M_0$ 本身无法替代式 (2H.12) 中固定的 $d$。
2H.2.4 Configuration 型零模型
独立超边模型把节点视为同质对象。若观测中节点活跃度和事件规模差异很大，许多看似特殊的结构可能只由这两类边际量造成。Configuration 型零模型保留节点关联度序列与超边大小序列，再随机化“哪些节点参加哪些事件”，用来检验边际量之外是否还存在额外结构。
令 $M=|\mathcal E|$，$\mathbf d_0=(d_0(1),\ldots,d_0(n))^T$，$\boldsymbol\delta=(\delta(e_1),\ldots,\delta(e_M))^T$。将事件列视为有标号对象时，一个直观的约束状态空间是
$$ \mathfrak F(\mathbf d_0,\boldsymbol\delta) =\left\{ B'\in\{0,1\}^{n\times M}: B'\mathbf1_M=\mathbf d_0, \ {B'}^T\mathbf1_n=\boldsymbol\delta \right\}. \tag{2H.13a} $$
式 (2H.13a) 定义边际约束，完整概率模型还需指定状态空间和其上的分布。二元矩阵排除了边内重复节点；允许相同列时仍包含重复超边，简单超图则要求列互异。对无标号事件，列置换表示同一个超图，因此矩阵上的均匀分布与无标号超图上的均匀分布通常不同。报告 configuration 模型时，应说明对象是否带标号、是否允许重复或退化超边，以及实际采样分布。
固定行和与列和还有一个容易漏掉的含义：它保留每个节点的总关联度 $d_0(v)$ 和每个事件的大小 $\delta(e)$，却一般不保留交叉统计量 $d_r(v)$。也就是说，“节点 $v$ 经常参加大事件”这一节点—事件大小关联会被重连随机化。若该关联本身是待控制的混杂因素，标准二部 configuration 基线可能随机化得过多；需要按事件大小分层重连，或把 $(d_r(v))_{v,r}$ 纳入更强的约束，并重新说明状态空间和采样正确性。
- $H_d(n,p)$ 只控制阶数与共同出现概率，适合作为同质独立基线；
- $H_d(n,M)$ 进一步固定超边总数，适合把“数量波动”从比较中移除；
- 若问题是观测结构能否由节点活跃度与事件大小异质性解释，则应考虑同时保留节点关联度序列和超边大小序列的 configuration 型零模型。
最后一类模型的精确均匀抽样可能困难，因此报告时应区分精确样本与交换、重连等近似样本。下面的一次局部交换用于展示边际如何保持；完整采样器还需给出目标分布与混合依据。
在贯穿例子的关联矩阵中，$(1,e_1)$ 与 $(4,e_3)$ 是两个关联位置，而 $(1,e_3)$ 与 $(4,e_1)$ 是两个空位置。把前两项的 1 移到后两项，相当于作如下替换：
| 交换前 | 交换后 |
|---|---|
| $e_1=\{1,2\}$ | $e'_1=\{2,4\}$ |
| $e_3=\{3,4,5\}$ | $e'_3=\{1,3,5\}$ |
$e_2=\{1,2,3\}$ 保持不变。交换前后，节点关联度均为 $(2,2,2,1,1)$，超边大小均为 $(2,3,3)$；$|e_1\cap e_2|$ 则从 2 变为 $|e'_1\cap e_2|=1$，说明事件重叠已被随机化。节点—事件大小关联也发生变化：节点 1 的 $(d_2,d_3)$ 从 $(1,1)$ 变为 $(0,2)$，节点 4 则从 $(0,1)$ 变为 $(1,0)$，二者总关联度保持不变。反复执行合法交换可以构造 Markov 链；其目标分布由转移规则和平稳分布决定，有限运行的可靠性由混合诊断评估。
2H.2.5 软约束：超图 $\boldsymbol\beta$-model
Configuration 模型把观测关联度当作必须逐项保持的硬约束。若只想用节点活跃度解释边际异质性，同时保留候选超边之间的条件独立性，可以使用超图 $\boldsymbol\beta$-model。对固定大小 $r$ 的简单候选超边 $e\in\binom Vr$，令
$$ \mathbb P_{\boldsymbol\beta}(X_e=1) =\frac{\exp\!\left(\sum_{i\in e}\beta_{r,i}\right)} {1+\exp\!\left(\sum_{i\in e}\beta_{r,i}\right)}. \tag{2H.13b} $$
参数 $\beta_{r,i}$ 描述节点 $i$ 参与 $r$ 元事件的倾向。若允许 $r=2,\ldots,R$，每个阶数可以有自己的参数向量 $\boldsymbol\beta_r$，相应的分阶关联度应分别保留。忽略与参数无关的常数，第 $r$ 层的对数似然为
$$ \ell_r(\boldsymbol\beta_r) =\sum_{i=1}^n\beta_{r,i}d_r(i) -\sum_{e\in\binom Vr} \log\!\left[1+\exp\!\left(\sum_{i\in e}\beta_{r,i}\right)\right]. \tag{2H.13c} $$
式 (2H.13c) 说明，关于 $\boldsymbol\beta_r$ 的数据项通过分阶关联度序列 $(d_r(i))_{i=1}^n$ 进入，因此它是该指数族的充分统计量。极大似然方程把每个观测 $d_r(i)$ 与模型期望关联度匹配。Configuration 模型在给定边际的纤维上随机化；$\boldsymbol\beta$-model 以边际为充分统计量作软匹配。二者都控制活跃度异质性，分别对应硬约束与期望约束。
取 $n=4,r=3$，令 $\beta_{3,1}=\log2$，其余三个参数为 0。任何包含节点 1 的三元候选集合出现概率均为 $2/3$；唯一不含节点 1 的集合 $\{2,3,4\}$ 出现概率为 $1/2$。于是 $\mathbb E d_3(1)=3\times(2/3)=2$，而 $\mathbb E d_3(2)=2\times(2/3)+1/2=11/6$。该例的概率差完全来自节点级活跃度，模型中未设置社区标签。
2H.3 随机游走与超图拉普拉斯（Random Walks and Hypergraph Laplacians）
在没有孤立节点的超图上，令 $D_v=\operatorname{diag}(d(v))$、$D_e=\operatorname{diag}(\delta(e))$ 和 $W=\operatorname{diag}(w(e))$。Zhou, Huang, and Schölkopf (2006) 考虑如下两阶段随机游走：在节点 $u$ 处，先以 $w(e)/d(u)$ 选择一条包含 $u$ 的超边 $e$；随后在 $e$ 中均匀选择下一个节点 $v$，其中允许 $v=u$。转移矩阵为
$$ P_{uv}=\sum_{e\in\mathcal E} \frac{w(e)B_{ue}}{d(u)} \frac{B_{ve}}{\delta(e)}, \qquad P=D_v^{-1}BWD_e^{-1}B^T. \tag{2H.14} $$
式 (2H.14) 中的 $P$ 是行随机矩阵，且
$$ \pi(v)=\frac{d(v)}{\operatorname{vol}(V)}, \qquad \operatorname{vol}(V)=\sum_{u\in V}d(u), \tag{2H.15} $$是其平稳分布。该链满足细致平衡关系 $\pi(u)P_{uv}=\pi(v)P_{vu}$。
对固定 $u$，先对 $v$ 求和，再使用 $\sum_vB_{ve}=\delta(e)$，得到 $\sum_vP_{uv}=1$。另一方面，
$$ \pi(u)P_{uv} =\frac{1}{\operatorname{vol}(V)} \sum_{e\in\mathcal E} \frac{w(e)B_{ue}B_{ve}}{\delta(e)}, $$右侧关于 $u,v$ 对称，因此满足细致平衡，进而 $\pi^TP=\pi^T$。∎
图 2H.4 把式 (2H.14) 拆成一棵概率树。它同时解释了为什么转移概率必须对所有包含起点与终点的超边求和，以及为什么该定义天然允许自环概率。
节点 3 同时属于 $e_2$ 和 $e_3$，两条超边权重都为 1，而 $d(3)=2$，所以第一阶段各以概率 $1/2$ 选择一条超边。两条超边大小都为 3，第二阶段在其中每个节点上取概率 $1/3$。
终点 1、2 只能经 $e_2$ 到达，终点 4、5 只能经 $e_3$ 到达，故概率均为 $(1/2)(1/3)=1/6$。终点 3 可经两条超边返回，所以概率为 $1/6+1/6=1/3$：
$$ P_{3,\bullet}= \left(\frac16,\frac16,\frac13,\frac16,\frac16\right), \qquad \sum_{v=1}^5P_{3v}=1. $$退化到普通图：若所有超边大小均为 2，第二阶段仍可能选回起点，因此该链对应带有自环概率的惰性随机游走。
Zhou 等定义的对称归一化超图拉普拉斯为
$$ L_H=I-D_v^{-1/2}BWD_e^{-1}B^TD_v^{-1/2}. \tag{2H.16} $$
对任意 $f\in\mathbb R^{|V|}$，
$$ f^TL_Hf =\frac12\sum_{e\in\mathcal E}\frac{w(e)}{\delta(e)} \sum_{u,v\in e} \left( \frac{f_u}{\sqrt{d(u)}}- \frac{f_v}{\sqrt{d(v)}} \right)^2\ge0. \tag{2H.17} $$因此 $L_H\succeq0$，且 $D_v^{1/2}\mathbf1$ 是零特征向量。若超图连通，则零特征值为单重。
在学习笔记中查看逐步完整证明半正定性保证连续目标有下界。切分与特征向量的联系来自 Zhou 等定义的超图边界体积与归一化切分：
$$ \operatorname{vol}(\partial S) =\sum_{e\in\mathcal E} \frac{w(e)}{\delta(e)}|e\cap S|\,|e\cap S^c|, \qquad \operatorname{Ncut}_H(S) =\operatorname{vol}(\partial S) \left(\frac1{\operatorname{vol}(S)}+\frac1{\operatorname{vol}(S^c)}\right). \tag{2H.17a} $$
对一个非平凡切分 $S\sqcup S^c=V$，令 $a=\operatorname{vol}(S)$、$b=\operatorname{vol}(S^c)$，并定义
$$ y_u= \begin{cases} \sqrt{b/a},&u\in S,\\ -\sqrt{a/b},&u\in S^c, \end{cases} \qquad f=\frac{D_v^{1/2}y}{\sqrt{\operatorname{vol}(V)}}. \tag{2H.17b} $$
直接代入式 (2H.17) 可得
$$ f^Tf=1,\qquad f^TD_v^{1/2}\mathbf1=0,\qquad f^TL_Hf=\operatorname{Ncut}_H(S). \tag{2H.17c} $$
因此离散切分向量落在单位球面与零特征向量的正交补上。去掉“$f$ 必须只取两种数值”这一离散约束，便得到
$$ \min_{f^Tf=1,\ f^TD_v^{1/2}\mathbf1=0} f^TL_Hf, \tag{2H.17d} $$
其解是 $L_H$ 最小非零特征值对应的特征向量。$Q$ 路切分的对应松弛为 $\min_{X^TX=I_Q}\operatorname{tr}(X^TL_HX)$；取 $Q$ 个最小特征向量后，通过行归一化和 $k$-means 得到离散标签，因此结果一般是原离散目标的近似解。完整代数见学习笔记中的 NH-Cut 推导。
贯穿例子的节点体积为 $(2,2,2,1,1)$。取 $S_1=\{1,2\}$ 时，只有 $e_2$ 被切开，故 $\operatorname{vol}(\partial S_1)=2/3$，且两侧体积均为 4，于是 $\operatorname{Ncut}_H(S_1)=1/3$。
取 $S_2=\{1,2,3\}$ 时，只有 $e_3$ 被切开，边界体积仍为 $2/3$，但两侧体积变成 6 与 2，因此 $\operatorname{Ncut}_H(S_2)=4/9$。在这两个候选中，$S_1$ 的归一化切分更小；这也显示相同边界体积会因两侧不平衡而得到不同惩罚。
式 (2H.14) 定义的是节点上的线性 Markov 链。Chitra and Raphael (2019) 证明，当第二阶段的节点权重不依赖所选超边时，该链等价于某个加权团图上的随机游走。若节点 $v$ 在不同超边中的作用不同，可以引入 edge-dependent vertex weights $\gamma_e(v)$：
$$ P_{uv}=\sum_{e\ni u}\frac{w(e)}{d(u)} \frac{\gamma_e(v)}{\sum_{x\in e}\gamma_e(x)}. \tag{2H.18} $$
边依赖节点权重时，所得链可能超出无向加权图上的可逆随机游走。判断一个超图线性算子保留了多少高阶信息，可以检查它是否完全由某个投影图确定。
2H.4 超图随机分块模型（Hypergraph Stochastic Block Models）
2H.4.1 Simple Bernoulli HSBM
令 $V=[n]$，允许超边大小 $r=2,\ldots,M_0$。节点标签独立生成：
$$ Z_i\overset{\mathrm{iid}}{\sim} \operatorname{Categorical}(\pi_1,\ldots,\pi_Q). \tag{2H.19} $$
对每个由互异节点构成的无序集合 $e=\{i_1,\ldots,i_r\}$，令 $Y_e=\mathbf1\{e\in\mathcal E\}$。给定标签后，各候选超边条件独立，且
$$ Y_e\mid Z \sim\operatorname{Bernoulli}\!\left( \mathsf P^{(r)}_{Z_{i_1},\ldots,Z_{i_r}} \right). \tag{2H.20} $$
$\mathsf P^{(r)}$ 是关于指标排列对称的 $r$ 阶概率张量。该模型的样本空间是简单非均匀超图：同一节点集合只有出现与不出现两种状态，超边内部由互异节点组成（Brusa and Matias, 2024）。亲和张量记为 $\mathsf P^{(r)}$，关联矩阵记为 $B$。
记 $p_e(Z)=\mathsf P^{(|e|)}_{Z_e}$。完整数据 $(Y,Z)$ 的似然为
$$ \mathbb P_\theta(Y,Z) =\prod_{i=1}^n\pi_{Z_i} \prod_{r=2}^{M_0}\prod_{e\in\binom Vr} p_e(Z)^{Y_e}[1-p_e(Z)]^{1-Y_e}. \tag{2H.21} $$观测似然为 $\mathbb P_\theta(Y)=\sum_{Z\in[Q]^n}\mathbb P_\theta(Y,Z)$。
在学习笔记中查看逐步完整证明只区分“整条超边是否完全位于同一群组”的 affiliation 子模型定义为
$$ \mathsf P^{(r)}_{q_1,\ldots,q_r}= \begin{cases} \alpha_r,&q_1=\cdots=q_r,\\ \beta_r,&\text{至少出现两个不同标签}. \end{cases} \tag{2H.22} $$
通常取 $\alpha_r>\beta_r$ 表示同群组超边更常见；一般 HSBM 也容纳异配结构。图 2H.5 用所有可能的二群组三元标签组成显示标签如何进入概率。
在贯穿例子中令 $(Z_1,Z_2,Z_3,Z_4,Z_5)=(1,1,1,2,2)$。三元集合 $e_2=\{1,2,3\}$ 的标签组成为 $(1,1,1)$，故在 affiliation HSBM 中出现概率为 $\alpha_3$；$e_3=\{3,4,5\}$ 的标签组成为 $(1,2,2)$，故出现概率为 $\beta_3$。
在 $H_3(n,p)$ 中，所有标签组成共享概率 $p$，因此两条候选超边具有相同概率。社区效应体现为生成概率随标签组成而变化。
给定完整标签向量 $Z=z$，
$$ \mathbb E[D_i\mid Z=z] =\sum_{r=2}^{M_0} \sum_{\substack{S\subseteq V\setminus\{i\}\\|S|=r-1}} \mathsf P^{(r)}_{z_i,z_S}. \tag{2H.23} $$在式 (2H.22) 的 affiliation 子模型中，若只条件于 $Z_i=a$，则
$$ \mathbb E[D_i\mid Z_i=a] =\sum_{r=2}^{M_0}\binom{n-1}{r-1} \left[ \alpha_r\pi_a^{r-1} +\beta_r(1-\pi_a^{r-1}) \right]. \tag{2H.24} $$ 在学习笔记中查看逐步完整证明只考虑三元超边，令 $n=20$、$\pi_1=0.6$、$\pi_2=0.4$、$\alpha_3=0.2$、$\beta_3=0.02$。由式 (2H.24)，群组 1 中节点的期望关联度为
$$ \binom{19}{2}\left[0.2(0.6)^2+0.02\bigl(1-(0.6)^2\bigr)\right] =171\times0.0848=14.5008, $$群组 2 中节点的对应期望为 $171\times[0.2(0.4)^2+0.02(1-(0.4)^2)]=8.3448$。模型未设置节点级 $\theta_i$，这一区别完全由群组比例与同配概率产生。因此，群组平均关联度差异也可能来自群组规模。
式 (2H.24) 表明，即使模型没有节点级度参数，不同群组比例也会造成期望关联度差异。若 $\alpha_r$ 和 $\beta_r$ 不随 $n$ 缩小，候选集合数 $\binom{n-1}{r-1}$ 会使模型变得稠密。保持常数平均关联度通常要求 $\mathsf P^{(r)}=O(n^{-(r-1)})$。
HSBM 至少具有标签置换不识别：同时重命名所有群组，并按相同置换重排 $\pi$ 与各 $\mathsf P^{(r)}$，观测分布不变。因此标签损失必须在群组排列后计算。单个 $r$ 阶对称概率张量含
$$ \binom{Q+r-1}{r} \tag{2H.25} $$
个不同参数；当群组数或最大阶数增大时，参数量会迅速上升。
从式 (2H.21) 到估计量还差一步：观测似然中的 $\sum_Z$ 包含 $Q^n$ 个标签配置。Brusa and Matias (2024, §2.3) 用节点间因子化分布 $Q_\tau(Z)=\prod_{i,q}\tau_{iq}^{\mathbf1\{Z_i=q\}}$ 近似后验。记 $\varphi(y,b)=y\log b+(1-y)\log(1-b)$，并把候选集合写成 $e=\{i_1<\cdots<i_r\}$，则证据下界可写为
$$ \begin{aligned} \mathcal J(\theta,\tau) ={}&\sum_{i=1}^n\sum_{q=1}^Q \tau_{iq}\log\frac{\pi_q}{\tau_{iq}}\\ &+\sum_{r=2}^{M_0}\sum_{e\in\binom Vr} \sum_{(q_1,\ldots,q_r)\in[Q]^r} \left(\prod_{\ell=1}^r\tau_{i_\ell q_\ell}\right) \varphi\!\left(Y_e,\mathsf P^{(r)}_{q_1\cdots q_r}\right). \end{aligned} \tag{2H.25a} $$
它满足 $\mathcal J=\log P_\theta(Y)-\operatorname{KL}(Q_\tau\|P_\theta(Z\mid Y))$，所以是观测对数似然的下界。固定参数后，VE 步的内点解满足以下固定点方程：
$$ \log\tau_{iq} =c_i+\log\pi_q +\sum_{r=2}^{M_0} \sum_{\substack{S\subseteq V\setminus\{i\}\\|S|=r-1}} \sum_{\mathbf q_S\in[Q]^{r-1}} \left(\prod_{j\in S}\tau_{j,q_j}\right) \varphi\!\left(Y_{\{i\}\cup S},\mathsf P^{(r)}_{q,\mathbf q_S}\right), \tag{2H.25b} $$
其中 $c_i$ 使 $\sum_q\tau_{iq}=1$。该式明确显示：更新节点 $i$ 的软标签时，所有包含 $i$ 的候选超边——包括未出现的候选集合——都会提供证据。
M 步则是软计数。对按非降序排列的标签多重组 $\mathbf q=(q_1,\ldots,q_r)$，令 $\mathfrak O(\mathbf q)$ 为其不同排列，并定义
$$ \omega_{e,\mathbf q}(\tau) =\sum_{\mathbf a\in\mathfrak O(\mathbf q)} \prod_{\ell=1}^r\tau_{i_\ell a_\ell}. $$
则完整 simple HSBM 的更新为
$$ \widehat\pi_q=\frac1n\sum_{i=1}^n\tau_{iq}, \qquad \widehat{\mathsf P}^{(r)}_{\mathbf q} =\frac{\sum_{e\in\binom Vr}\omega_{e,\mathbf q}(\tau)Y_e} {\sum_{e\in\binom Vr}\omega_{e,\mathbf q}(\tau)}. \tag{2H.25c} $$
分子是该软标签组成下的期望出现次数，分母是相应候选次数。VE 与 M 步交替进行，多初值运行后保留较大的 ELBO。Brusa and Matias (2024) 指出，式 (2H.25b) 的固定点缺少一般的存在性与唯一性保证；数值收敛和标签的一致恢复需要分别评估。
群组数可用论文给出的 ICL 型准则比较。对完整模型，若 $\widehat Z_i=\arg\max_q\tau_{iq}$，则
$$ \operatorname{ICL}_{\mathrm{full}}(Q) =\log P_{\widehat\theta}(Y,\widehat Z) -\frac{Q-1}{2}\log n -\frac12\sum_{r=2}^{M_0} \binom{Q+r-1}{r}\log\binom nr. \tag{2H.25d} $$
最后一项同时惩罚参数数目和每一阶的有效候选样本量。最大化 ICL 提供模型选择规则；阶数选择的一致性需要额外理论条件。Affiliation 子模型应使用其较少的参数维数。
2H.4.2 Poisson degree-corrected HSBM（进阶）
Simple HSBM 在给定标签组合后仍把节点视为同质。若节点本身的活跃程度差异显著，可以引入节点参数 $\theta_i$。Chodrow, Veldt, and Benson (2021) 的 DCHSBM 以节点多重集合为超边位置。令 $\mathcal R_r$ 为总大小恰为 $r$ 的无序节点多重集之集，并固定 $\mathcal R=\bigcup_{r=2}^{M_0}\mathcal R_r$。对 $R\in\mathcal R$，$a_R\in\{0,1,2,\ldots\}$ 是该位置上的超边数，$b_R$ 是 $R$ 中节点的不同排列数。给定 $(z,\theta,\Omega)$ 后，各位置的计数 $(a_R)_{R\in\mathcal R}$ 相互独立，且
$$ a_R\mid z,\theta,\Omega \sim\operatorname{Poisson}\!\left( b_R\prod_{i\in R}\theta_i\,\Omega(z_R) \right),\qquad R\in\mathcal R. \tag{2H.26} $$
乘积按节点在 $R$ 中的重数计算。$\theta_i$ 控制节点活跃度，$\Omega(z_R)$ 控制标签组合及超边大小的亲和度。与 Bernoulli simple HSBM 相比，该模型允许同一位置出现多条超边，并在原始定义中允许超边内部重复节点。
设 $R_{\mathrm{high}}=\{h,u,v\}$ 与 $R_{\mathrm{low}}=\{\ell,u,v\}$ 中三个节点互异且都属于群组 A，并令 $\theta_h=2$、$\theta_\ell=0.5$、$\theta_u=\theta_v=1$。两条位置都有 $b_R=3!=6$，故
$$ \lambda_{\mathrm{high}}=12\Omega(AAA),\qquad \lambda_{\mathrm{low}}=3\Omega(AAA),\qquad \frac{\lambda_{\mathrm{high}}}{\lambda_{\mathrm{low}}}=4. $$这个比值来自活跃度而非社区。另一方面，若把该群组所有 $\theta_i$ 同乘 2，并把三元亲和度 $\Omega(AAA)$ 除以 $2^3=8$，每条三元位置的强度保持不变；这正是命题 2H.5 所要求规范化的原因。
对每个群组 $q$ 任取常数 $c_q>0$，并令
$$ \theta_i'=c_{z_i}\theta_i, \qquad \Omega'(z_R)= \frac{\Omega(z_R)}{\prod_{i\in R}c_{z_i}}. \tag{2H.27} $$则式 (2H.26) 中每个 Poisson 强度保持不变。因此，$\theta$ 与 $\Omega$ 需要规范化才能分别确定尺度。
在学习笔记中查看逐步完整证明Chodrow 等采用规范化
$$ \sum_{i:z_i=q}\theta_i =\operatorname{vol}(q) =\sum_{i:z_i=q}d_i, \tag{2H.28} $$
并在固定标签下得到条件极大似然估计 $\widehat\theta_i=d_i$。也可以规定每组的 $\theta_i$ 之和为 1，此时 $\Omega$ 获得相应的新尺度与解释；跨规范化比较时应先完成尺度换算。
该模型的超图 modularity 目标可以从条件对数似然推出。记 $\Pi(\theta_R)=\prod_{i\in R}\theta_i$，略去只依赖数据的常数后，标签与亲和函数进入
$$ \mathcal Q_{\mathrm{DC}}(z,\Omega,\theta) =\sum_{R\in\mathcal R}\left[ a_R\log\Omega(z_R) -b_R\Pi(\theta_R)\Omega(z_R) \right]. \tag{2H.28a} $$
在式 (2H.28) 的规范化下代入 $\widehat\theta=d$，并要求 $\Omega$ 只依赖一条超边中各群组出现次数的排序向量 $\mathbf p=\phi(z_R)$，Chodrow 等把同类项合并为
$$ \mathcal Q_{\mathrm{DC}}(z,\Omega,d) =\sum_{\mathbf p}\left[ \operatorname{cut}_{\mathbf p}(z)\log\Omega(\mathbf p) -\operatorname{vol}_{\mathbf p}(z)\Omega(\mathbf p) \right]. \tag{2H.28b} $$
$\operatorname{cut}_{\mathbf p}$ 计数观测超边中标签组成等于 $\mathbf p$ 的权重；$\operatorname{vol}_{\mathbf p}$ 是度校正零模型下相应组成的暴露量。“cut” 按完整标签组成分箱，信息多于一个跨组指示量。
最常用的 all-or-nothing（AON）亲和函数只区分一条 $r$ 元超边是否全部位于同一群组。若同组与跨组亲和度分别为 $\omega_{r1}$ 与 $\omega_{r0}$，令
$$ \kappa_r=\log\frac{\omega_{r1}}{\omega_{r0}}, \qquad \xi_r=\frac{\omega_{r1}-\omega_{r0}}{\kappa_r}, $$
当 $\omega_{r1}=\omega_{r0}=\omega_r$ 时，以连续延拓定义 $\xi_r=\omega_r$；此时 $\kappa_r=0$，该阶不提供划分信号。与标签有关的目标可整理为
$$ \mathcal Q_{\mathrm{DC}}(z,\Omega,d) =-\sum_{r=2}^{M_0}\kappa_r \left[ \operatorname{cut}_r(z) +\xi_r\sum_{q=1}^Q\operatorname{vol}(q)^r \right]+J(\Omega), \tag{2H.28c} $$
其中 $\operatorname{cut}_r$ 是含至少两个群组的观测 $r$ 元超边总权重，$J(\Omega)$ 与 $z$ 无关。若 $\omega_{r1}>\omega_{r0}$，最大化似然等价于在度校正体积惩罚下减少跨组超边，由此得到 modularity 型目标。论文先在无约束亲和函数下得到 $\widehat\theta=d$ 与亲和度闭式更新，再施加对称结构；群组体积不等时，这些更新是受限条件极大似然的近似。式 (2H.28c) 的精确 profile-likelihood 解释相应依赖群组体积条件。
Bernoulli HSBM 观测互异节点集合的出现指标，Poisson DCHSBM 观测节点多重集合位置上的超边计数。在稀疏且强度较小时，Poisson 分布可以近似 Bernoulli 分布；重复事件、似然常数和参数解释仍按各自样本空间定义。
2H.5 推断路线与恢复保证（Inference and Recovery）
2H.5.1 四类计算路线
比较超图方法时，可从原始观测、表示、优化目标和保留的信息四个方面展开。
| 路线 | 直接输入 | 典型对象 | 主要优势 | 信息与计算特点 |
|---|---|---|---|---|
| 关联矩阵谱方法 | $B,W,D_v,D_e$ | $L_H$ 的特征向量、节点随机游走 | 线性代数成熟，易扩展到聚类与半监督学习 | 常见线性算子可能等价于加权投影图 |
| 完整超边似然 | $\{Y_e\}$ 或 $\{a_R\}$ | HSBM/DCHSBM 似然、VEM、profile likelihood | 参数和样本空间明确，可进行模型比较 | 条件独立、未出现超边与稀疏标度都进入目标函数 |
| 低秩超图嵌入 | 原始超边；非均匀时可加入空节点 | 节点嵌入、惩罚似然、嵌入空间中的聚类 | 可容纳同一社区内部的连续异质性 | 目标非凸，依赖初始化；空节点扩充本身也是建模约定 |
| 固定阶张量方法 | $m$-阶邻接或亲和张量 | HOSVD、tensor trace maximization、张量幂迭代 | 在松弛前显式保留固定阶多元结构 | 非均匀数据需分阶或扩充，完整张量的时间与存储代价高 |
2H.5.1.1 关联矩阵谱聚类
给定群组数 $Q$，先由式 (2H.16) 构造归一化超图 Laplacian $L_H$。取其 $Q$ 个最小特征值对应的正交特征向量组成 $X\in\mathbb R^{n\times Q}$，将 $X$ 的每一行归一化，再对这些行向量运行 $k$-means；第 $i$ 行所属的簇就是节点 $i$ 的估计标签。二分时，也可由最小非零特征值对应特征向量的符号给出切分。该算法先求解 normalized hypergraph cut 的连续松弛，再由聚类步骤完成离散舍入。
Ghoshdastidar and Dukkipati (2017a) 对植入分区模型中的这条管线给出一致性分析。其逻辑依次是：总体 Laplacian 的群组结构形成特征间隙，样本 Laplacian 集中于总体算子，特征子空间扰动保持可控，最后 $k$-means 将嵌入还原为标签。该保证要求足够的稠密度、总体特征间隙和稳定的近似聚类。由于 $L_H$ 可写成一个加权图算子，这条路线使用的是可图化的成对信息。
在该文的 planted-partition 模型中，设 $\bar D$ 为期望度矩阵，群组大小满足 $n_1\ge\cdots\ge n_Q$。原文的最低期望度 $d=\min_i\bar D_{ii}$ 在此记为 $d_{\min}$，可识别性量 $\delta$ 记为 $\Delta_{\mathrm{id}}$。总体收缩矩阵可写成 $\bar A=ZGZ^T-J$，其中 $J$ 为群组内常数的对角矩阵，且
$$ \Delta_{\mathrm{id}} =\lambda_{\min}(G) \min_{1\le i\le n}\frac{n_{z_i}}{\bar D_{ii}} -\max_{1\le i,j\le n} \left| \frac{J_{ii}}{\bar D_{ii}}- \frac{J_{jj}}{\bar D_{jj}} \right|. $$存在绝对常数 $C>0$，使得当 $n$ 足够大、$\Delta_{\mathrm{id}}>0$ 且
$$ d_{\min}>C\frac{Qn_1(\log n)^2}{\Delta_{\mathrm{id}}^2n_Q}, \tag{2H.28d} $$论文的谱算法以至少 $1-O((\log n)^{-1/4})$ 的概率满足
$$ \operatorname{Err}_{\#}(\widehat z,z) =O\!\left(\frac{Qn_1\log n}{\Delta_{\mathrm{id}}^2d_{\min}}\right), \tag{2H.28e} $$其中 $\operatorname{Err}_{\#}$ 表示最佳标签置换后的错分节点数。把式 (2H.28d) 代入可得 $\operatorname{Err}_{\#}/n=o(1)$，即论文所称 weak consistency；按本章统一口径，这是几乎精确恢复。结论适用于该文的 planted-partition 模型、算子与近似 $k$-means 条件。
在学习笔记中逐项读取条件与误差链2H.5.1.2 完整超边似然与变分 EM
Bernoulli HSBM 从式 (2H.21) 出发，把每个候选节点集合的出现与未出现都纳入似然。精确 E 步需要计算含 $Q^n$ 个标签配置的后验，因此 Brusa and Matias (2024) 采用节点间因子化的近似分布
$$ Q_\tau(Z)=\prod_{i=1}^n\prod_{q=1}^Q \tau_{iq}^{\mathbf1\{Z_i=q\}}, \qquad \sum_q\tau_{iq}=1, $$
并交替增大证据下界（ELBO）。一个最小可执行流程是：先用随机标签或谱聚类初始化 $\tau$；在 VE 步中固定模型参数并迭代更新 $\tau_{iq}$；在 M 步中把 $\pi_q$ 和各阶亲和概率更新为由 $\tau$ 加权的频率；ELBO 收敛后输出 $\widehat z_i=\arg\max_q\tau_{iq}$。不同初值应分别运行并比较最终 ELBO，$Q$ 与最大建模阶数还可用 ICL 型准则选择。算法收敛描述数值固定点或局部最优点，统计一致性则由独立的恢复分析给出。
候选节点集合的数量随阶数呈组合爆炸。若所有大小 $2,\ldots,n$ 都允许，简单超图共有
$$ \sum_{r=2}^{n}\binom nr=2^n-n-1 $$
个候选位置；即使最大阶数 $R$ 固定，最高阶也有 $\binom nR=\Theta(n^R)$ 个位置。因此“大规模”包含两个轴：节点数与观测事件数决定数据结构和迭代开销，单条超边大小与最大阶数决定候选空间、张量和单次事件处理开销。报告复杂度时应分别给出这两类尺度。
一个可扩展近似是保留全部已出现超边，并抽样部分未出现候选集合来近似总体目标。抽样目标具有自己的单调性、估计性质和恢复条件，需要根据具体抽样方案分析。
2H.5.1.3 空节点扩充与低秩嵌入
Zhen and Wang (2023) 处理最大超边大小为 $m$ 的非均匀超图时，只加入一个空节点 $0$，并允许它重复出现：大小为 $\ell<m$ 的超边补成含 $m-\ell$ 个空节点的 $m$-元多重集合。扩充后的邻接张量记为 $\mathcal A$，节点 $i$ 由低维向量 $\alpha_i\in\mathbb R^r$ 表示，并令变换后的概率张量具有对称低秩形式
$$ \Theta=\mathcal I_r\times_1\alpha\times_2\cdots\times_m\alpha. $$
估计目标由超边负对数似然和“嵌入应靠近某个群组中心”的 $k$-means 型惩罚共同组成。计算时可用 HOSVD 暖启动，随后交替执行两步：固定标签和中心，对 $\alpha$ 做梯度更新；固定 $\alpha$，用 $k$-means 更新标签矩阵与中心。输出同时包含连续嵌入、估计超边概率和离散社区。该方法比“先做团投影再嵌入”保留更多阶数信息，但目标非凸，论文保证依赖适当的初始化、群组分离与稀疏度条件。
2H.5.1.4 固定阶张量与 TTM
对 $m$-均匀加权超图，可先形成 $m$ 阶亲和张量 $\mathcal A$。Ghoshdastidar and Dukkipati (2017b) 的 tensor trace maximization（TTM）以“群组内部归一化亲和度较大”为离散目标；其可计算谱松弛先把后 $m-2$ 个指标求和，得到
$$ C_{ij}=\sum_{i_3,\ldots,i_m}\mathcal A_{ij i_3\cdots i_m}, \qquad S=D^{-1/2}CD^{-1/2}, $$
再取 $S$ 的 $Q$ 个最大特征值对应特征向量，逐行归一化并运行 $k$-means。TTM 从张量目标出发，在谱松弛中压缩为矩阵。HOSVD、CP 分解和张量幂迭代更直接地操作张量，并分别需要低秩、正交性或可分解性条件。完整张量通常有 $O(n^m)$ 个位置，实际计算一般使用稀疏超边表或抽样表示。
一个二群组三元 affiliation HSBM 可以把“生成概率—矩阵信号—错分率”连成一条可算主线。令 $n=2s$，两个群组各有 $s$ 个节点；同组候选三元组以概率 $\alpha$ 出现，其余三元组以概率 $\beta$ 出现。为去掉不影响特征向量的固定归一化常数，下面直接使用未归一化节点对计数（它与前述三阶张量收缩只差一个固定比例）
$$ C_{ij}=\sum_{k\notin\{i,j\}}Y_{\{i,j,k\}}. \tag{2H.28f} $$
若 $i,j$ 同组，可选的第三个节点中有 $s-2$ 个保持全同组、$s$ 个形成混合三元组；若 $i,j$ 异组，则所有 $2s-2$ 个第三节点都形成混合三元组。因此
$$ \mathbb E[C_{ij}\mid z_i=z_j] =(s-2)\alpha+s\beta, \qquad \mathbb E[C_{ij}\mid z_i\ne z_j] =(2s-2)\beta, \tag{2H.28g} $$
两类配对的总体差恰为 $(s-2)(\alpha-\beta)$，因此 $\alpha>\beta$ 时矩阵化后的总体算子保留块信号。有限样本表现还取决于噪声规模，矩阵化后的可用信息则由收缩映射决定。计数证明见学习笔记。
在三元无权超图中，这个矩阵收缩与式 (2H.16) 的 Zhou 算子有精确对应。记 $D_h=\operatorname{diag}(d_0(i))$，并令 $C_{ii}=0$；由于 $BB^T=D_h+C$ 且 $\sum_jC_{ij}=2d_0(i)$，若 $D_C=\operatorname{diag}(C\mathbf1)=2D_h$，则在非孤立节点上
$$ D_h^{-1/2}BD_e^{-1}B^TD_h^{-1/2} =\frac13I+\frac13D_h^{-1/2}CD_h^{-1/2} =\frac13I+\frac23D_C^{-1/2}CD_C^{-1/2}. \tag{2H.28h} $$
两者只相差正比例缩放与单位阵平移，因而具有相同特征向量。该等价性成立于三元、无权且采用上述收缩的情形。
图 2H.8 对这条主线做一个可复现的有限样本检查：$n=60$、两组等大、$\beta=0.02$，每个 $\alpha-\beta$ 取值独立生成 40 次样本；每次由稀疏三元超边表累计 $C$，计算 $D^{-1/2}CD^{-1/2}$ 的主非平凡特征向量，再做一维二均值聚类。曲线使用最佳标签置换后的错分率。有限 $n$ 下要在两种标签排列中取较小者，因此无信息点的经验中位数可以略低于 $0.5$；虚线表示大样本随机猜测基准。
配套学习笔记的第 9 节给出四条路线的计算模板和五节点例子。
2H.5.2 恢复术语
对真实标签 $z\in[Q]^n$ 和估计标签 $\widehat z$，定义置换不变错分率
$$ \operatorname{err}(\widehat z,z) =\min_{\sigma\in\mathfrak S_Q} \frac1n\sum_{i=1}^n \mathbf1\{\widehat z_i\ne\sigma(z_i)\}. \tag{2H.29} $$
- 检测（detection）：以非平凡功效区分含植入结构的模型与相应零模型；它未必输出节点标签。
- 弱恢复（weak recovery）：对一列群组比例收敛到 $\pi$ 的模型，记 $\pi_{\max}=\max_q\pi_q$；存在常数 $\varepsilon>0$，使 $\mathbb P\{1-\operatorname{err}(\widehat z,z)\ge\pi_{\max}+\varepsilon\}\to1$。它优于恒猜最大群组的平凡基线，但错分比例未必趋于 0。平衡 $Q$ 群组时基线为 $1/Q$。
- 几乎精确恢复（almost exact recovery）：$\operatorname{err}(\widehat z,z)\xrightarrow{P}0$，仍允许错分 $o(n)$ 个节点。
- 精确恢复（exact recovery）：$\mathbb P(\operatorname{err}(\widehat z,z)=0)\to1$。
设 $n=1000$，在最佳标签置换后有 20 个节点错分，则 $\operatorname{err}(\widehat z,z)=20/1000=0.02$。这表示有限样本中有 2% 节点错分；精确恢复要求错分节点数为 0。
在平衡二群组模型中，若一列规模增长的问题始终约有 $0.02n$ 个错分节点，准确率保持在 0.98，因而达到弱恢复但不达到几乎精确恢复。若错分数以高概率为 $\sqrt n$ 量级，则 $\sqrt n/n\to0$，对应几乎精确恢复。精确恢复进一步要求全体节点同时正确的概率趋于 1。
不同论文对 detection 与 weak recovery 的命名存在差异：有些文献把 detection 专用于模型检验，另一些文献用它表示估计标签与真值具有正相关。因此，引用恢复阈值时应同时给出原文的损失函数、参数标度和概率模式。
恢复结论包含三个层次：信息论上是否存在达到目标的估计器，多项式时间算法能否达到同一阈值，以及具体算法在给定条件下达到何种误差。Chien, Lin, and Wang (2018) 研究均匀 HSBM 的 minimax 错分率；Zhang and Tan (2023) 给出一般均匀 HSBM 的精确恢复阈值；Dumitriu and Wang (2026) 将精确恢复分析推广到一般非均匀 HSBM。Chernoff–Hellinger 型散度、局部 refinement 和信息论下界构成后续社区发现专题的理论主线。
四条计算路线支持的恢复层次各不相同。下表按本章引用的论文逐项对应。
| 路线 | 本章采用的代表结果 | 适用条件或限制 |
|---|---|---|
| 关联矩阵谱聚类 | Ghoshdastidar and Dukkipati (2017a) 在 planted-partition 模型下证明错分数为次线性，并在部分稠密均匀情形得到零错分 | 总体特征间隙、最低稠密度、群组可识别性及 $k$-means 的近似质量 |
| HSBM–VEM | Brusa and Matias (2024) 给出可计算估计程序和经验评估 | 该文的结论集中在估计程序与经验评估；ELBO 收敛与统计恢复保证分开判断 |
| HEM 低秩嵌入 | Zhen and Wang (2023) 给出概率张量估计与社区检测的一致性 | 低秩模型、群组分离、$s_n\gg n^{1-m}\log n$ 量级及取得足够好的局部解 |
| TTM 张量目标 | Ghoshdastidar and Dukkipati (2017b) 在稀疏加权均匀 planted-partition 模型下证明错分比例趋零（原文称 weak consistency），并覆盖部分稠密精确恢复情形 | 固定阶、模型特征间隙、稠密度、矩阵化松弛和 $k$-means 条件 |
因此，“算法迭代已经收敛”“经验错分率很低”和“满足渐近恢复定理”对应数值、经验与理论三个层次。引用保证时，应同时给出算法、生成模型、参数标度和概率口径。
2H.5.3 模型与表示的选择原则
给定一组群体事件数据，可以按以下顺序建立统计模型。
- 首先确定一条观测是互异节点集合、节点多重集合，还是带时间和属性的事件。该决定确定样本空间。
- 在聚类前定义“社区”要奖励什么，并说明不同超边大小是否等权；同样的内外超边条数，在按事件计数与按参与规模加权时可能给出不同判断。
- 若需要回溯事件身份，保存关联矩阵或星形展开；构造投影图时同时确定目标与权重约定。
- 无潜在群组时先使用 $H_d(n,p)$、$H_d(n,M)$ 或分阶独立模型建立同质基线；若需要控制节点活跃度与事件规模，则改用明确定义样本空间的 configuration 型基线。
- 群组改变超边概率时使用 simple HSBM；节点活跃度异质性显著且重复事件有意义时考虑 DCHSBM。
- 在算法比较中同时报告表示、目标函数、正则化、初始化和恢复指标，使不同统计问题保持可比。
这套流程把建模假设转化为可检查的选择。投影、Poisson 化和条件独立都应作为统计假设记录并验证。
把非均匀超图写成共享节点集上的分层集合 $(H_r)_{r\ge2}$ 后，社区信息可能只存在于部分阶数。设二群组模型的二元层对所有标签组成都取概率 $p_2$，而三元层满足同组概率 $\alpha_3$ 大于混合概率 $\beta_3$。此时二元层对标签没有总体辨识力，三元层才携带社区信号；若二元事件数量远多于三元事件，无权合并或统一投影反而可能稀释后者。
不同阶数也可能支持不同分组。分阶样本量、权重和信号检查说明每一层提供的证据，联合目标则说明这些证据如何组合。
2H.5.4 拟合之后：生成式检查
参数估计和标签输出之后还需检查模型拟合。给定拟合模型 $P_{\widehat\theta}$，可在相同节点集与观测规则下生成复制样本 $H^{(1)},\ldots,H^{(B)}$，再比较观测超图与复制样本中未被拟合过程固定的统计量。一个适合本章的最小诊断向量是
$$ T(H)=\left( (|\mathcal E_r|)_r, \operatorname{quantile}\{d_0(v):v\in V\}, (I_k)_k, |C_{\max}| \right), \qquad I_k=\sum_{\{e,f\}\subseteq\mathcal E}\mathbf1\{|e\cap f|=k\}. \tag{2H.30} $$
其中 $C_{\max}$ 是按 Berge 路径口径得到的最大连通分量。四部分依次检查超边大小、节点活跃度、事件重叠和连通结构。诊断应优先选择拟合过程没有锁定的统计量。例如，以 $\widehat p=|\mathcal E|/\binom nd$ 拟合 $H_d(n,p)$ 后，复制样本的超边总数期望已经与观测值对齐；节点关联度上尾、$I_2,I_3,\ldots$ 和最大分量大小能提供更多拟合信息。
若 $H_d(n,\widehat p)$ 能复现超边数，却系统性低估高关联度节点，偏离指向活跃度异质性，可以进一步比较 configuration 基线或带度修正的模型。若 configuration 基线已复现节点关联度和超边大小，却仍系统性低估 $I_k$ 的大 $k$ 尾部，偏离则指向额外的事件重叠结构。
生成式检查用于定位当前模型遗漏的结构。后续模型再结合样本空间、可识别性、计算代价和外部任务选择。
若所有合成数据都由 HSBM 生成，再比较 HSBM 似然法与非模型法，实验同时检验了算法和“谁知道真实模型”两件事，容易偏向模型匹配的方法。更稳妥的基准应同时包含模型内数据与模型外数据，例如固定边际的重连样本、潜在几何或增长机制、混合阶且分层信号强弱不同的样本；评价也应同时报告标签损失与未被拟合强制匹配的结构统计量。
模型内实验回答“假设正确时能否恢复”，模型外实验回答“假设偏离时怎样失效”。两类结果分别报告。
2H.6 进一步说明（Further Notes）
以下方向把本章的表示与模型连接到后续专题。
中心性与非线性谱。 均匀超图的邻接张量可以定义多种节点与超边特征向量中心性。不同张量特征值概念具有各自的代数性质，非均匀超图则可采用分阶张量或扩充方案。Cooper–Dutle 归一化连接到 resultant、特征多项式和张量幂法等谱方法。
重叠路径与 motif。 超图中的“闭合”可以定义在节点、超边、不同重叠宽度或不同大小的 motif 上，因此 transitivity 与 clustering coefficient 有多种推广。式 (2H.6b) 给出 $k$-walk 与 $k$-distance；高阶 cycle、motif 频率及相应中心性由所选对象和归一化决定。
增长与潜在几何。 Preferential attachment 模型解释事件与节点如何随系统增长而加入；latent-space 模型让一组连续潜在位置共同决定超边概率。前者适合机制与重尾形成问题，后者适合相似性或空间邻近机制。相应专题进一步研究参数估计与可识别性。
直接超图正则化。 式 (2H.16) 属于线性、clique-based 的拉普拉斯路线。若目标依赖一条超边内部的最大差异或其他不可加群体效应，可以使用 hypergraph total variation 等非线性正则项。此时优化问题和谱解释都会改变。
高级社区恢复。 非回溯谱、belief propagation、高级张量分解与幂迭代、半正定松弛和局部 refinement 分别对应不同稀疏区间与计算假设。具体算法阈值由模型、参数标度和算法条件共同确定。
时间、抽样与神经网络。 当超边带时间戳时，事件形成、解散和记忆会破坏静态条件独立性；当超图只能通过抽样观察时，节点随机游走与超边随机游走会诱导不同的包含概率；超图神经网络则还需区分其消息传递是否超越了某种图投影。这些内容分别进入后续时间网络、抽样和学习专题。
2H.7 本章来源与逐项定位（Sources and Traceability）
本章综合多项高阶网络研究。Bick et al. (2023) 与 Battiston et al. (2020) 提供概念框架，Matias (2026) 提供统计建模地图、描述统计和可扩展性分析；公式、模型和定理分别对应其原始研究论文。下表列出主要主张与来源位置。
| 本章内容 | 来源中的定位 | 正文采用方式 |
|---|---|---|
| 超图、简单超图与单纯复形 | Bick et al. (2023), §§1.1, 2.1.1–2.1.2 | 采用集合族定义与向下闭合区分，并分别声明多重超图的样本空间 |
| 基本记号、观测对象、分阶描述统计、事件线图、二部模型、模型地图、分层信号与可扩展性 | Matias (2026), §§1–6 | 用作术语对照和统计问题地图；读图卡、式 (2H.3a)–(2H.3b)、式 (2H.4a)–(2H.4c)、式 (2H.6a)、式 (2H.13a)、局部交换、算例及生成式诊断为项目展开 |
| 二部表示的可逆条件、固定事件槽与 bipartite SBM 约束 | Brusa and Matias (2024), Supplement A.1–A.3 | 区分带索引的重复事件、单节点事件与去重后的简单超边集合；式 (2H.4c) 表示一个事件槽的共同包含概率；图 2H.1a 为项目构造 |
| $k$-walk、$k$-line graph 与超边距离 | Aksoy et al. (2020), Definitions 5 and 7, Proposition 1, §§4.2–4.4 | 采用 edge-level walk 与 distance；图 2H.2a 由贯穿例子构造 |
| 分层超图 $\boldsymbol\beta$-model | Nandy and Bhattacharya (2024), Definition 1.1, Eqs. (1.2), (2.2)–(2.3) | 对应式 (2H.13b)–(2H.13c) 的软度约束与充分统计量；MLE 收敛率、置信区间和检验阈值见原文 |
| $H_d(n,M)$ 的相变尺度 | Karoński and Łuczak (2002), Abstract, §1 | 式 (2H.12) 来自该文；§1 将粗粒度三阶段结果归于 Schmidt-Pruzan and Shamir (1985)，本章据此拆分归因 |
| 巨分量三阶段数量级 | Schmidt-Pruzan and Shamir (1985)；Karoński and Łuczak (2002), §1 | 原始三阶段结果归前者；后者负责临界附近的精细分析 |
| 关联矩阵、两阶段游走、$L_H$ 与 NH-Cut | Zhou et al. (2006), §§2–6, Eqs. (1)–(5), Theorem 1 | 对应式 (2H.2)–(2H.3)、(2H.14)–(2H.17d)；从边界体积逐式推到 Rayleigh 松弛，并说明离散舍入步骤 |
| 随机游走何时可图化 | Chitra and Raphael (2019), §3, Theorems 3.1–3.2 | 边无关节点权重对应加权团图；边依赖权重包含不可图化情形 |
| $d$-均匀邻接张量与特征对 | Cooper and Dutle (2012), Definitions 2.3, 3.1, Eq. (3) | 式 (2H.7)–(2H.7b) 用于简单均匀超图；单边算例核对排列归一化，非均匀情形采用分阶或扩充约定 |
| Simple Bernoulli HSBM、VEM 与 ICL | Brusa and Matias (2024), §§2.1–2.4, Propositions 4–6 | 对应式 (2H.19)–(2H.25d)，展开 VE 固定点、M 步、完整模型 ICL 及局部最优性质 |
| Poisson DCHSBM 与 modularity | Chodrow et al. (2021), §§2–3.2, Eqs. (1), (3)–(4), (9)–(16), Appendix A | 对应式 (2H.26)–(2H.28c)；保留多重集合样本空间、尺度规范化，以及不等群组体积时近似 MLE 的条件 |
| 谱划分的一致性定理 | Ghoshdastidar and Dukkipati (2017a), §4.1, Lemma 4.1, Theorem 4.2 | 按本章记号 $d_{\min},\Delta_{\mathrm{id}}$ 给出最低期望度、可识别性量、$n_1/n_Q$、概率口径和错分节点数阶；保证限定于原文模型 |
| HEM 低秩嵌入 | Zhen and Wang (2023), §§3.1–3.3, Eqs. (1)–(5) | 采用单空节点扩充、低秩嵌入、惩罚目标、交替更新及原文一致性条件 |
| TTM 谱松弛 | Ghoshdastidar and Dukkipati (2017b), §§3–4, Algorithm TTM, Theorem 2 | 张量在该松弛中收缩为矩阵；理论保证对应 TTM 的模型与算法条件 |
| 三元收缩算例与图 2H.8 | affiliation HSBM 定义；tools/generate_hypergraph_figures.py |
期望对比由项目组合计数推导；固定种子 Monte Carlo 展示有限样本趋势 |
| Sample-to-population 近似 | Fritz, Yuan, and Schweinberger (2026), §§4–5 | 采用其抽样估计框架、可识别性和估计界 |
| 错分率与精确恢复 | Chien et al. (2018), Theorems 3.1–3.2；Zhang and Tan (2023), Definitions 1–2, Theorems 1–3；Dumitriu and Wang (2026), Theorems 1.12, 1.17–1.18 | 本章统一损失与保证层级；具体阈值连同模型、稀疏标度和概率口径引用 |
完整书目信息如下。
- Battiston, F. et al. (2020), “Networks beyond pairwise interactions: Structure and dynamics,” Physics Reports, 874, 1–92. DOI
- Bick, C., Gross, E., Harrington, H. A., and Schaub, M. T. (2023), “What Are Higher-Order Networks?” SIAM Review, 65(3), 686–731. DOI
- Karoński, M. and Łuczak, T. (2002), “The phase transition in a random hypergraph,” Journal of Computational and Applied Mathematics, 142(1), 125–135. DOI
- Zhou, D., Huang, J., and Schölkopf, B. (2006), “Learning with Hypergraphs: Clustering, Classification, and Embedding,” Advances in Neural Information Processing Systems, 19, 1601–1608. 论文页
- Chitra, U. and Raphael, B. (2019), “Random Walks on Hypergraphs with Edge-Dependent Vertex Weights,” ICML 2019, PMLR 97, 1172–1181. 论文页
- Cooper, J. and Dutle, A. (2012), “Spectra of uniform hypergraphs,” Linear Algebra and its Applications, 436(9), 3268–3292. DOI
- Ghoshdastidar, D. and Dukkipati, A. (2017a), “Consistency of spectral hypergraph partitioning under planted partition model,” The Annals of Statistics, 45(1), 289–315. DOI
- Brusa, L. and Matias, C. (2024), “Model-based clustering in simple hypergraphs through a stochastic blockmodel,” Scandinavian Journal of Statistics, 51(4), 1661–1684. DOI
- Chodrow, P. S., Veldt, N., and Benson, A. R. (2021), “Generative hypergraph clustering: From blockmodels to modularity,” Science Advances, 7(28), eabh1303. DOI
- Zhen, Y. and Wang, J. (2023), “Community detection in general hypergraph via graph embedding,” Journal of the American Statistical Association, 118(543), 1620–1629. DOI
- Chien, I., Lin, C.-Y., and Wang, I.-H. (2018), “Community Detection in Hypergraphs: Optimal Statistical Limit and Efficient Algorithms,” Proceedings of AISTATS 2018, PMLR 84, 871–879. 论文页
- Zhang, Q. and Tan, V. Y. F. (2023), “Exact Recovery in the General Hypergraph Stochastic Block Model,” IEEE Transactions on Information Theory, 69(1), 453–471. DOI
- Dumitriu, I. and Wang, H. (2026), “Optimal and exact recovery on the general non-uniform Hypergraph Stochastic Block Model,” The Annals of Statistics, 54(1), 48–73. DOI
- Ghoshdastidar, D. and Dukkipati, A. (2017b), “Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques,” Journal of Machine Learning Research, 18(50), 1–41. 论文页
- Matias, C. (2026), “A statistical perspective on higher-order interactions modeling,” arXiv:2603.28273v1 [stat.AP], 30 March 2026. arXiv
- Aksoy, S. G., Joslyn, C., Ortiz Marrero, C., Praggastis, B., and Purvine, E. (2020), “Hypernetwork science via high-order hypergraph walks,” EPJ Data Science, 9, 16. DOI
- Nandy, S. and Bhattacharya, B. B. (2024), “Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph $\boldsymbol\beta$-Model,” IEEE Transactions on Information Theory, 70(8), 6000–6024. DOI · arXiv v4
- Schmidt-Pruzan, J. and Shamir, E. (1985), “Component structure in the evolution of random hypergraphs,” Combinatorica, 5(1), 81–94. DOI
- Fritz, C., Yuan, Y., and Schweinberger, M. (2026), “Scalable Sample-to-Population Estimation of Hyperbolic Space Models for Hypergraphs,” arXiv:2509.07031v2 [stat.ME], revised 1 February 2026. arXiv
本章的详细推导、易混点、公式卡片和自检题见配套学习笔记。