大规模高阶网络的广谱结构发现
Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks
https://arxiv.org/pdf/2505.21748v1
高阶交互的建模需求：
- 复杂系统（社会、生物、技术等）通常由多个节点之间的高阶交互驱动
- 传统图模型只能捕捉成对交互，而超图（hypergraph）能够自然表示高阶交互
- 理解超图中的依赖结构对理解和预测复杂系统行为至关重要
现有方法的局限性：
- 严格同配性假设：现有方法大多假设节点只与同类节点交互（同配结构）
- 无法建模异配结构：许多系统存在异配性（不同类别节点间的交互），如生态系统的捕食者-猎物关系
- 组合爆炸问题：高阶交互导致模型参数数量呈指数级增长
- 数据降维损失：将高阶数据简化为成对交互会丢失关键结构信息
模型名称含义：
- Omni（全谱）：能够捕捉从严格同配到高度异配的完整结构谱系
- Hype（超图）：针对超图数据
- SMT（对称多重张量）：基于对称多张量分解
关键创新点：
- 双层聚类框架
- 第一层：将节点软聚类为C个"类别"（classes）
- 第二层：将类别软聚类为K个"社区"（communities）
- 允许节点属于多个类别，类别属于多个社区
- 低秩张量分解
- 使用节点-类别隶属矩阵Θ（N×C）
- 使用类别-社区隶属矩阵W（C×K）
- 通过低秩分解避免参数组合爆炸
- 全谱同配性
- 通过参数设置可灵活调节从严格同配到高度异配的结构
- 允许类别间在特定社区内发生交互
- 通过社区-阶速率参数γ_k^(d)控制不同阶数的交互强度
- 模型可识别性保证
- 隶属矩阵列位于概率单纯形上（非负且和为1）
- W的前C列构成单位矩阵（每个类别有对应的"纯社区"）
- 证明在两个合理假设下模型参数可唯一识别：
概率生成模型：
- 假设不同节点集合的高阶交互次数服从泊松分布
- 交互速率μ通过低秩分解参数化
- 使用张量Tucker分解和CP分解的数学框架
高效推断算法：
- 利用模型的概率性质推导高效的参数更新规则
- 可处理大规模、高阶的超图数据
- 支持合成超图的可扩展生成
数据集：
- 两个药物相互作用数据集（DAWN, NDC-substances）
- 两个国会级数据集（参议院委员会、参议院法案）
- 两个人类接触数据集（工作场所、高中接触）
主要发现：
- 药物相互作用案例（DAWN数据库）：
- 成对交互主要是"娱乐性药物"之间（如酒精+大麻）
- 高阶交互（d≥3）揭示重要医学模式：
- 心血管药物（如赖诺普利）常与精神类药物（如喹硫平）或阿片类药物（如羟考酮）同时出现
- 这些医学处方的药物混合后会增强药效，增加临床风险
- 识别出15个药物类别（如心血管药物、阿片类镇痛药、精神类药物等）
- 发现50个社区，揭示不同药物类别的混合模式
- 关键洞察
- 发现"Q-ball"现象（喹硫平+可卡因）在d=6和d=10时权重显著
- 医院接触网络
- 清晰区分患者和医护人员两个类别
- 准确建模跨类别交互（高度异配结构）
- 链路预测AUC：0.91（全谱模型）vs 0.85（严格同配模型）
- 最高法院判决网络
- 法官主要同意同意识形态的法官（核心）
- 但也偶尔同意对立意识形态的法官（如一致裁决）
- 识别出民主党任命与共和党任命的法官类别
- 捕捉核心-外围结构：
- 避免将共和党法官错误分配到民主党主导的类别
性能优势：
- 链路预测优于最先进方法
- 发现更具可解释性的节点聚类
- 揭示超越严格同配性的多样化介观结构
- 证明现有模型的局限性
- 证明最先进的严格同配模型是本模型的特例（受限实例）
- 展示随着交互阶数增加，建模异配结构的重要性增强
- 模型可识别性证明
- 结合张量分解和非负矩阵分解的唯一性结果
- 确保参数估计的可靠性和解释的稳健性
- 计算可扩展性
- 提供严格的统计推断框架
- 实现大规模数据驱动的介观结构发现
- 临床风险评估
- 揭示成对分析中被掩盖的高阶药物交互模式
- 为更安全的多药治疗方案设计提供依据
- 科学发现工具
- 将大规模高阶数据纳入科学发现过程
- 提供可解释的潜在结构发现
- 跨领域适用性
- 适用于生物、社会、政治等多个领域
- 灵活适应不同的介观结构类型
"随着交互阶数的增加，恰当地建模异配结构变得愈发重要"
论文强调，在复杂的高阶数据中发现具有临床和科学意义的模式，需要对全谱介观结构（从同配到异配）进行建模，而不仅限于传统的同配假设。这为理解复杂系统提供了更全面、更准确的框架。
复杂系统通常由多个单元之间的高阶交互所驱动，自然地表示为超图。理解这些超图内的依赖结构对于理解和预测复杂系统的行为至关重要，但其组合复杂性和计算需求使其面临挑战。在本文中，我们引入了一类概率模型，能够高效地表示并发现大规模超图中广谱的介观结构。使该方法成为可能的关键洞见是，将相似单元的类别本身视为潜在超图中的节点。通过使用低秩表示对类别间的潜在交互进行建模，进而对观测到的节点交互进行建模，我们的方法在确保模型可识别性的同时，以可处理的方式捕获了丰富的结构模式。这允许直接解释不同的节点级和类别级结构。实证上，我们的模型在链路预测方面优于最先进的方法，并在包括药理和社交网络在内的多种真实世界系统中发现了可解释的结构，推进了我们将大规模高阶数据纳入科学过程的能力。
I. 引言
复杂系统——包括社会、生物或技术系统等类型——通常由众多节点之间的高阶相互作用所驱动（1）。此类系统可被建模为超图，它将传统图或网络的概念从二元或成对相互作用扩展至高阶相互作用。
与传统网络类似，现实世界的超图也展现出介观结构（2, 3）——即节点群组之间的相互作用模式。广义上讲，对这种结构进行建模可归结为将节点聚类为群组，并刻画这些群组之间（如果存在）的相互作用方式。通过这样做，人们可以降低系统的概念复杂性和数据的维度，从而有可能揭示驱动观测相互作用的真实功能组件和潜在机制（4）。
介观结构有多种不同形式，并非所有形式都能被有效建模。或许最常被建模的结构是同配结构，其中节点形成“社区”，并且主要与同一社区内的其他相似节点发生相互作用。近期研究开发了在超图数据中高效检测这些社区的方法（5–7）。然而，许多复杂系统也表现出一定程度的异配结构，其中相似节点形成“类别”，但可能不会在这些类别内部发生相互作用。在这些类别中，节点具有相似的特征，但可能（专门）与其他类别中的节点发生相互作用。生态学中的捕食者-猎物网络就是一个此类例子，其中物种分为两类之一（捕食者或猎物），并主要与另一类的物种发生相互作用。
即使在传统网络设置中，任何程度的异配性（不同类别节点之间的相互作用）通常都难以建模。这一挑战源于对“节点如何形成群组”以及“这些群组组合如何相互作用”两者进行建模所需的基础复杂性。对于超图而言，这种复杂性会叠加：节点之间的高阶相互作用引入了群组内部和群组之间的高阶相互作用，导致模型参数数量出现组合爆炸，使得参数估计变得不可能。近期的研究通过开发能够揭示超图中高度受限的异配性形式的模型来应对这一问题，例如可通过Bethe近似建模的结构（7），或核心-外围结构，其中紧密连接节点的密集核心可与松散连接节点的稀疏外围区分开来（8, 9）。
尽管先前的研究已从理论上分析了广泛的超图场景（5, 10–14），但从业者在有效建模超图介观结构时仅限于少数几种选择，且每种选择都有其自身的缺点。一种方法将分析限制在同配（或类似约束）结构上，这存在错误表征非同配系统的风险。另一种方法将数据限制为中等数量的低阶相互作用（例如三阶或四阶），以便应用现有的某些更灵活的方法，但这些方法在大规模高阶超图上扩展性较差。第三种策略将高阶数据降维为成对相互作用，可能在数据预处理步骤中丢弃关键的结构信息（6, 15, 16）。总体而言，这些局限性严重阻碍了研究人员利用大规模数据对其研究的复杂系统得出可靠结论的能力。
受这些挑战的启发，本文引入了一族概率生成模型，以可计算地捕捉大规模超图底层广泛范围的介观结构。该模型族涵盖了若干现有模型，并跨越了涵盖全范围同配性的结构谱系，从严格同配延伸至高度异配。给定模型在该谱系中的具体位置由其参数值决定。
推动该方法的核心思想是将节点共同聚类为类别，并将类别进一步聚类为社区。每次聚类都是软聚类，允许节点属于多个类别，类别属于多个社区，如图1b所示。我们将其称为Omni-Hype-SMT的所提模型，通过规定类别仅在社区内部发生相互作用，避免了与建模所有类别间相互作用组合相关的组合爆炸。通过将类别聚类为社区，Omni-Hype-SMT允许节点之间发生异配相互作用。由于类别由相似节点组成，不同类别之间的相互作用会导致这些类别节点之间产生异配相互作用。正是通过这一框架，所提模型捕捉了支配节点间高阶相互作用的丰富且可解释的潜在结构。
我们利用基于严格理论原则的统计推断框架，以严谨地识别超图数据中的介观结构。我们对所提模型的定义确保其参数可从数据中被严格证明是可识别的，从而增强了参数解释的可靠性和稳健性。除了提供模型可识别性的严格证明外，我们通过利用所提模型的概率性质及其内部的条件分布，推导出了高效的参数更新方法。正是这种效率使得在实践中能够进行大规模、数据驱动的介观结构发现。我们展示了这种效率如何促成一个极其简单但可扩展的算法的开发，该算法用于生成具有可调介观结构的合成超图——由于超图高维特性带来的计算挑战，当前文献中 largely 缺失这一能力（5, 17）。总而言之，我们方法在解析和计算上的可处理性，加上其理论保证，使其成为一种原则性且有效的方式，用于解构大规模复杂系统底层不同类型的介观结构。
我们通过对两个生物数据集、三个人际接触网络和三个政治数据集的广泛实验，展示了Omni-Hype-SMT的表达力和可扩展性，每个数据集都具有自然的超图表示。我们发现了一系列超越严格同配性的多样化介观结构。我们证明了最先进的同配模型（6）是所提模型类的一个特定且受限的实例。我们在此重点进行比较，以展示所提模型的先进能力。我们灵活的建模方法在下游任务上带来了更好的性能，与现有方法相比，实现了增强的高阶链路预测和更具可解释性的节点聚类。
我们的结果反映了一个直观的洞见：随着相互作用阶数的增加，恰当地建模异配结构变得愈发重要。在一项关于急诊室（ER）患者高阶药物组合的案例研究中，我们展示了学习多种类型的介观结构如何为药物类别及其相互作用模式提供更细致的见解。例如，药物之间的成对相互作用往往发生在“娱乐性药物”之间——这是模型推断出的类别，并事后借助生成式AI进行标注——如酒精和大麻。另一方面，在体内含有多种药物的患者中，如果其中一种是“心血管药物”如赖诺普利或美托洛尔，其他药物通常是“精神类药物”（喹硫平、氯硝西泮）或“阿片类镇痛药”（羟考酮、氢可酮、芬太尼）。当混合使用时，这些通常出于医疗益处而开具的药物类别会增强药效。这些见解可能通过揭示在成对分析中被掩盖的潜在高阶相互作用模式，为临床风险评估和更安全的多重用药方案的设计提供参考。
综上所述，这些发现凸显了在复杂、高阶数据中发掘具有临床和科学意义的模式时，对全谱介观结构进行建模的重要性。
II. 结果A. 脱离严格同配性的动机：两个案例研究
我们首先展示，当拟合到表现出真实程度异配性的超图时，基于严格同配性假设的现有概率方法如何提供次优的数据表示。我们分析了两个数据集，每个数据集都表现出一种不同于严格同配性的介观结构类型。
首先，我们利用一个医院内人类接触互动的数据集，其中节点要么是工作人员（即医生、护士或行政助理），要么是患者（18）。在该数据集中，超边描述了通过可穿戴蓝牙设备测量的近距离接触互动。我们通过移除不包含至少一名患者的超边，创建了该数据的一个半合成版本。因此，所有互动要么完全发生在患者之间，要么由至少一名患者和一名工作人员组成。随后我们拟合两个模型：1）上述最先进的严格同配模型（6），以及 2）我们的全谱同配（omniassortative）模型。
从高层次来看，这两个模型均可理解为将 N 个节点软聚类为 C 个潜在类别，由一个 N × C 的节点-类别隶属矩阵表示。我们在图 2a 的下方面板中可视化了每个模型学习到的矩阵。严格同配模型（左列）要求不同类别的节点不发生互动，未能恢复底层的工作人员与患者的块状结构。另一方面，全谱同配模型（右列）清晰地将节点划分为患者和工作人员，并恰当地建模了群组之间的互动。除了提供更具可解释性的群组级数据描述外，全谱同配模型对留出超边的预测也优于严格同配模型（AUC 为 0.91 对比 0.85）。
在我们的第二个例子中，我们使用了 2005 年至 2024 年间的美国最高法院案件数据集。该数据形成一个超图，其中节点是最高法院法官，每个超边对应同意特定案件多数意见的法官集合。在此，两个模型都恢复了相似的块状结构，如图 2b 的上方面板所示。然而，如节点-类别隶属矩阵的熵 H(Θ)（定义见第 II.D 节）所衡量的，同配模型推断出的类别区分度较低。另一方面，全谱同配模型清晰地区分了主要对应民主党任命与共和党任命法官的类别。严格同配模型将共和党任命的法官罗伯茨、肯尼迪、阿利托、托马斯和斯卡利亚部分隶属到一个由民主党任命者主导的类别中，而全谱同配模型则没有。全谱同配模型允许类别之间的互动——因此，它不需要高度混合的类别隶属关系来解释有时同意民主党任命法官的共和党任命法官之间的互动。图 2b 最下方的两个面板描绘了类别之间的亲和关系，我们注意到严格同配亲和矩阵（蓝色）被约束为对角矩阵。
这些例子代表了两种截然不同的脱离严格同配性的情况。第一个例子展示了高度异配的结构，其中患者和工作人员主要在类别之间而非类别内部进行互动。第二个例子展示了核心-外围结构，其中法官主要同意意识形态相似的其他法官（即保守派同意保守派），但也同意意识形态相反的法官（如在一致裁决中），尽管频率较低。这些简单的例子为我们接下来描述的建模方法提供了动机。
B. Omni-Hype-SMT：基于对称多重张量的高阶图全谱同配模型
在此，我们引入 OMNI-HYPE-SMT，这是一种概率模型，能够从大规模超图数据中推断出灵活多样的介观结构。在其具体设定中，该模型将传统网络随机块模型方法（19–21）的结构模式与多层网络多线性张量分解方法（22–25）相融合。具体而言，节点在一组类别中具有重叠的成员资格（即节点可同时属于多个类别），而这些类别本身随后展现出高阶相互作用。类别级的相互作用速率由一个亲和多重张量 Λ ( ⋅ )
所控制，其参数设置决定了超图中存在的介观结构类型。 Λ ( ⋅ ) ⋅) 具有非常高的维度——我们对其施加了特定的低秩分解，这使得模型既可识别（从而能够恢复有意义的潜在结构），又便于估计。
所提模型建立在先前工作（5–7）的基础上，假设不同节点集合之间观测到的高阶相互作用次数服从条件泊松分布——即：
这些假设在我们所有的实验中均得到满足，使得能够从数据中识别出类别和社区。这是一个非平凡的结果，它源于结合了张量分解与非负矩阵分解的唯一性结果（28, 29）。有关证明及其他结果，请参阅补充说明4。
C. 从大规模药理学数据中自动发现药物类别及其相互作用
在此，我们应用 OMNI-HYPE-SMT 来分析药物滥用预警网络（DAWN）数据库（30）。在此设定中，节点代表药物，每条超边代表急诊室患者自述服用的一组药物。该数据集包含 2,558 个节点和 141,178 条超边；更多细节请见表 1。我们选取 C = 15 个类别和 K = 50 个社区（关于选取标准的细节请参考补充说明 3），将模型拟合至整个数据集，并对推断出的潜在结构进行探索性分析。
推断的药物类别。我们首先解释由节点-类别隶属矩阵 Θ 表示的推断药物类别。在图3中，我们将六个类别可视化为栗色茎状图，展示了每个类别 c 中 θ i c值最大的药物 i 。赋予每个类别的标签由 OpenAI 的 GPT-4o（访问于2025年5月4日）分配，我们向其提供了每个类别的顶级药物列表作为提示。我们发现，推断出的类别通常代表具有共同功能或用途的药物组，例如“心血管药物”（如赖诺普利、美托洛尔）、“阿片类镇痛药”（如羟考酮、吗啡）或“精神类药物”（如喹硫平、氯硝西泮）。我们要指出，同一类别中的药物并不一定是急诊室患者经常被发现有共同服用记录的药物。例如，虽然推断出的“心血管药物”类别中的药物具有相似的药理学功能，但它们在我们的数据中通常与其他推断类别的药物一起出现——即，这是一个异配类别。除了“酒精”（由于其在数据中极高的流行度而出现在许多类别中）之外，我们发现各类别的顶级药物具有高度的一致性，并与 GPT-4o 赋予它们的标签相符。
D. 跨领域适用性：预测、可解释性与异质性
数据集。我们考虑六个源自实证数据的超图：两个药物相互作用数据集（DAWN、NDC-substances）（5, 30），两个国会级别数据集（senate-committees（参议院委员会）（32），senate-bills（参议院法案）（5, 33, 34）），以及两个额外的人际接触互动数据集（workplace（工作场所）（35），contact-high-school（高中接触）（36））。每个数据集的详细信息在方法部分及表1中提供。
分别是留出对数似然度，以及一个对每个阶数赋予均匀权重的加权留出对数似然度。这些指标在图 4a 中分别显示为“overall”和“overall (unif)”。
对数似然度差异巨大，我们按如下方式对它们进行归一化，以便跨数据集比较结果。我们计算相对于严格同配基线模型 (6) 的相对增益；对于给定的 d d，这是
图 4c 展示了三个高阶数据集的这些比例。每个数据集都包含最大阶数 ( D D) 超过 15 的高阶交互。在每种设置中，对全谱同配性进行建模都提高了预测性能。曲线的定性行为因数据集而异。例如，在 DAWN 中，我们观察到异配性单调增加直到大约阶数 d = 10 ，此后该比例在接近1 的位置趋于平稳。这些结果说明了在超图设置中仔细建模全谱同配性以恰当捕捉底层潜在结构的重要性。
E. 快速超图生成
最后，OMNI-HYPE-SMT 是一个生成模型，在此我们展示如何使用它来生成具有预设介观结构的合成超图。由于计算方面的挑战，超图生成问题仍然是一个未解难题 (5, 17, 38)。然而，利用所提模型的特性使我们能够以可处理的方式解决这一任务。我们在方法部分描述了一种算法，该算法能生成任意阶数的超图，且其计算复杂度与超边的期望数量呈线性关系。
为了实证地展示该算法，我们使用在 DAWN 数据上学习到的模型参数来生成合成超图数据，如第 II.C 节所述。我们的方法速度很快：在配备单个 CPU 的个人笔记本电脑上运行，仅用 70 秒就生成了 833,564 个高阶药物相互作用（数量与真实数据相似），阶数范围从 d = 2 到 d = 16 。
为了检查合成数据是否与真实数据相似，我们比较了一系列统计量：节点度分布、超边阶数分布、包含出现分布 (39) 以及投影邻接矩阵。图 5 展示了这些比较。图表看起来几乎完全一致，表明合成数据与真实数据高度吻合。
III. 结论
本文引入了一族针对高阶交互数据的概率生成模型，该模型能够表示并高效发现大规模超图中广谱的介观结构，范围涵盖从严格同配到异配。不同类型的此类结构提供了对复杂系统根本不同的描述。因此，能够灵活地对其底层超图中的广谱结构进行建模，对于理解和预测此类系统的行为至关重要。
我们通过将块模型技术与低秩分解表示相结合，解决了高阶交互数据带来的核心计算挑战。所提模型将节点划分为类别，然后表示类别之间的高阶交互。关键洞见在于将类别本身视为形成一个结构严格同配的潜在超图。与先前假设观测超图是同配的工作不同，正如我们所证明的，这一假设仍然允许观测图呈现广泛的结构。因此，所提模型利用了潜在类别间同配结构的计算优势，同时仍能表示和发现观测节点间的全谱同配（omniassortative）结构。
我们的理论结果提供了严格的保证，指导并支持该模型在广泛场景中的应用。其中，我们证明了该模型保持数据的对称性，泛化了现有的严格同配模型，并且参数是可识别的。实证上，我们证明了该模型具有足够的灵活性，能够捕捉源自各种现实社会、政治和生物医学场景的多种高阶网络数据集中的多种潜在介观结构。我们展示了介观结构如何随超边阶数变化，因为同一类节点可能在某一阶的超边中表现为同配，而在另一阶中表现为异配。通过一项关于急诊就医患者服用药物的案例研究，我们展示了所提模型如何能够学习具有相似功能的药物类别，并预测急诊患者可能同时服用了哪些不同类别的药物。在另外两个案例研究（一个在医院内部，另一个关于最高法院法官）中对不同建模方法的比较，进一步凸显了所提方法的重要性。
最后，我们展示了如何在所提框架下高效采样具有预定义介观结构的合成超图。我们提出了一种源自模型概率性质的算法，该算法能够快速生成展现多样结构和不同阶数的大规模超图。我们通过快速大规模生成大型超图，实证展示了该算法的速度。此外，我们证明了合成数据与现实世界的超图数据高度吻合。这一结果具有深远的影响，可能使研究人员能够在受控环境中研究具有各种结构的逼真高阶网络。
我们的结果指出了未来工作的许多方向。所提模型允许不同阶数的超边对社区结构做出不同的贡献。然而，在若干情况下，观察到超边表现出嵌套性或其他形式的层次结构 (40–43)。这可能会在不同阶数的超边之间产生强相关性，从而可能需要对这些参数之间施加显式的函数依赖关系，例如在对应于连续阶数超边的参数之间。我们在此考虑了具有离散权重的超图，但一个自然的模型扩展将是允许实数值权重，例如通过复合泊松构造 (44, 45)。类似地，我们在此专注于静态超图，其中节点和超边的集合是固定的。在结构随时间变化的时序超图中，将超边形成的动态机制直接纳入模型将更为合适 (46–50)。在超图中存在节点属性的情况下，除了超边内在包含的信息之外，一个自然的扩展是将这些额外信息纳入模型公式中 (51, 52)。最后，所提模型针对的是无向超图，其中组织在超边中的节点顺序未定义。一个未来的方向是将我们的公式改编为适用于有向超图 (53)，在此可以识别扮演不同角色的节点子集，例如网络中的发送者和接收者节点。在此设置下，某些对称性被打破，可能允许纳入来自非对称张量分解的思想，用于建模多层网络数据 (23–25)。
原文链接：https://arxiv.org/pdf/2505.21748v1
热门跟贴