大規模高階網絡的廣譜結構發現

大規模高階網絡的廣譜結構發現

Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks

https://arxiv.org/pdf/2505.21748v1

論文概述：大規模高階網絡中的廣譜結構發現 研究背景與動機

高階交互的建模需求：

• 復雜系統（社會、生物、技術等）通常由多個節點之間的高階交互驅動
• 傳統圖模型只能捕捉成對交互，而超圖（hypergraph）能夠自然表示高階交互
• 理解超圖中的依賴結構對理解和預測復雜系統行為至關重要

現有方法的局限性：

1. 嚴格同配性假設：現有方法大多假設節點只與同類節點交互（同配結構）
2. 無法建模異配結構：許多系統存在異配性（不同類別節點間的交互），如生態系統的捕食者-獵物關系
3. 組合爆炸問題：高階交互導致模型參數數量呈指數級增長
4. 數據降維損失：將高階數據簡化為成對交互會丟失關鍵結構信息

模型名稱含義：

• Omni（全譜）：能夠捕捉從嚴格同配到高度異配的完整結構譜系
• Hype（超圖）：針對超圖數據
• SMT（對稱多重張量）：基于對稱多張量分解

關鍵創新點：

1. 雙層聚類框架

• 第一層：將節點軟聚類為C個"類別"（classes）
• 第二層：將類別軟聚類為K個"社區"（communities）
• 允許節點屬于多個類別，類別屬于多個社區

• 低秩張量分解

• 使用節點-類別隸屬矩陣Θ（N×C）
• 使用類別-社區隸屬矩陣W（C×K）
• 通過低秩分解避免參數組合爆炸

• 全譜同配性

• 通過參數設置可靈活調節從嚴格同配到高度異配的結構
• 允許類別間在特定社區內發生交互
• 通過社區-階速率參數γ_k^(d)控制不同階數的交互強度

• 模型可識別性保證

• 隸屬矩陣列位于概率單純形上（非負且和為1）

• W的前C列構成單位矩陣（每個類別有對應的"純社區"）

• 證明在兩個合理假設下模型參數可唯一識別：

概率生成模型：

• 假設不同節點集合的高階交互次數服從泊松分布
• 交互速率μ通過低秩分解參數化
• 使用張量Tucker分解和CP分解的數學框架

高效推斷算法：

• 利用模型的概率性質推導高效的參數更新規則
• 可處理大規模、高階的超圖數據
• 支持合成超圖的可擴展生成

數據集：

1. 兩個藥物相互作用數據集（DAWN, NDC-substances）
2. 兩個國會級數據集（參議院委員會、參議院法案）
3. 兩個人類接觸數據集（工作場所、高中接觸）

主要發現：

1. 藥物相互作用案例（DAWN數據庫）：

• 成對交互主要是"娛樂性藥物"之間（如酒精+大麻）
• 高階交互（d≥3）揭示重要醫學模式：

• 心血管藥物（如賴諾普利）常與精神類藥物（如喹硫平）或阿片類藥物（如羥考酮）同時出現
• 這些醫學處方的藥物混合后會增強藥效，增加臨床風險

• 識別出15個藥物類別（如心血管藥物、阿片類鎮痛藥、精神類藥物等）
• 發現50個社區，揭示不同藥物類別的混合模式
• 關鍵洞察
• 發現"Q-ball"現象（喹硫平+可卡因）在d=6和d=10時權重顯著

• 醫院接觸網絡

• 清晰區分患者和醫護人員兩個類別
• 準確建?？珙悇e交互（高度異配結構）
• 鏈路預測AUC：0.91（全譜模型）vs 0.85（嚴格同配模型）

• 最高法院判決網絡

• 法官主要同意同意識形態的法官（核心）
• 但也偶爾同意對立意識形態的法官（如一致裁決）

• 識別出民主黨任命與共和黨任命的法官類別
• 捕捉核心-外圍結構：
• 避免將共和黨法官錯誤分配到民主黨主導的類別

性能優勢：

• 鏈路預測優于最先進方法
• 發現更具可解釋性的節點聚類
• 揭示超越嚴格同配性的多樣化介觀結構

1. 證明現有模型的局限性

• 證明最先進的嚴格同配模型是本模型的特例（受限實例）
• 展示隨著交互階數增加，建模異配結構的重要性增強

• 模型可識別性證明

• 結合張量分解和非負矩陣分解的唯一性結果
• 確保參數估計的可靠性和解釋的穩健性

• 計算可擴展性

• 提供嚴格的統計推斷框架
• 實現大規模數據驅動的介觀結構發現

1. 臨床風險評估

• 揭示成對分析中被掩蓋的高階藥物交互模式
• 為更安全的多藥治療方案設計提供依據

• 科學發現工具

• 將大規模高階數據納入科學發現過程
• 提供可解釋的潛在結構發現

• 跨領域適用性

• 適用于生物、社會、政治等多個領域
• 靈活適應不同的介觀結構類型

"隨著交互階數的增加，恰當地建模異配結構變得愈發重要"

論文強調，在復雜的高階數據中發現具有臨床和科學意義的模式，需要對全譜介觀結構（從同配到異配）進行建模，而不僅限于傳統的同配假設。這為理解復雜系統提供了更全面、更準確的框架。

復雜系統通常由多個單元之間的高階交互所驅動，自然地表示為超圖。理解這些超圖內的依賴結構對于理解和預測復雜系統的行為至關重要，但其組合復雜性和計算需求使其面臨挑戰。在本文中，我們引入了一類概率模型，能夠高效地表示并發現大規模超圖中廣譜的介觀結構。使該方法成為可能的關鍵洞見是，將相似單元的類別本身視為潛在超圖中的節點。通過使用低秩表示對類別間的潛在交互進行建模，進而對觀測到的節點交互進行建模，我們的方法在確保模型可識別性的同時，以可處理的方式捕獲了豐富的結構模式。這允許直接解釋不同的節點級和類別級結構。實證上，我們的模型在鏈路預測方面優于最先進的方法，并在包括藥理和社交網絡在內的多種真實世界系統中發現了可解釋的結構，推進了我們將大規模高階數據納入科學過程的能力。

I. 引言

復雜系統——包括社會、生物或技術系統等類型——通常由眾多節點之間的高階相互作用所驅動（1）。此類系統可被建模為超圖，它將傳統圖或網絡的概念從二元或成對相互作用擴展至高階相互作用。

與傳統網絡類似，現實世界的超圖也展現出介觀結構（2, 3）——即節點群組之間的相互作用模式。廣義上講，對這種結構進行建?？蓺w結為將節點聚類為群組，并刻畫這些群組之間（如果存在）的相互作用方式。通過這樣做，人們可以降低系統的概念復雜性和數據的維度，從而有可能揭示驅動觀測相互作用的真實功能組件和潛在機制（4）。

介觀結構有多種不同形式，并非所有形式都能被有效建模。或許最常被建模的結構是同配結構，其中節點形成“社區”，并且主要與同一社區內的其他相似節點發生相互作用。近期研究開發了在超圖數據中高效檢測這些社區的方法（5–7）。然而，許多復雜系統也表現出一定程度的異配結構，其中相似節點形成“類別”，但可能不會在這些類別內部發生相互作用。在這些類別中，節點具有相似的特征，但可能（專門）與其他類別中的節點發生相互作用。生態學中的捕食者-獵物網絡就是一個此類例子，其中物種分為兩類之一（捕食者或獵物），并主要與另一類的物種發生相互作用。

即使在傳統網絡設置中，任何程度的異配性（不同類別節點之間的相互作用）通常都難以建模。這一挑戰源于對“節點如何形成群組”以及“這些群組組合如何相互作用”兩者進行建模所需的基礎復雜性。對于超圖而言，這種復雜性會疊加：節點之間的高階相互作用引入了群組內部和群組之間的高階相互作用，導致模型參數數量出現組合爆炸，使得參數估計變得不可能。近期的研究通過開發能夠揭示超圖中高度受限的異配性形式的模型來應對這一問題，例如可通過Bethe近似建模的結構（7），或核心-外圍結構，其中緊密連接節點的密集核心可與松散連接節點的稀疏外圍區分開來（8, 9）。

盡管先前的研究已從理論上分析了廣泛的超圖場景（5, 10–14），但從業者在有效建模超圖介觀結構時僅限于少數幾種選擇，且每種選擇都有其自身的缺點。一種方法將分析限制在同配（或類似約束）結構上，這存在錯誤表征非同配系統的風險。另一種方法將數據限制為中等數量的低階相互作用（例如三階或四階），以便應用現有的某些更靈活的方法，但這些方法在大規模高階超圖上擴展性較差。第三種策略將高階數據降維為成對相互作用，可能在數據預處理步驟中丟棄關鍵的結構信息（6, 15, 16）?？傮w而言，這些局限性嚴重阻礙了研究人員利用大規模數據對其研究的復雜系統得出可靠結論的能力。

受這些挑戰的啟發，本文引入了一族概率生成模型，以可計算地捕捉大規模超圖底層廣泛范圍的介觀結構。該模型族涵蓋了若干現有模型，并跨越了涵蓋全范圍同配性的結構譜系，從嚴格同配延伸至高度異配。給定模型在該譜系中的具體位置由其參數值決定。

推動該方法的核心思想是將節點共同聚類為類別，并將類別進一步聚類為社區。每次聚類都是軟聚類，允許節點屬于多個類別，類別屬于多個社區，如圖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