Learning the effective order of a hypergraph dynamical system

學習超圖動力系統的有效階

https://www.science.org/doi/epdf/10.1126/sciadv.adh4053

在超圖上運行的動態系統可以展現出豐富多樣的行為，這些行為在僅具有成對相互作用的系統中是無法觀察到的。對于一個具有潛在超圖結構的分布式動態系統，一個有趣的問題是：為了真實地復現觀察到的動態行為，這種超圖結構到底在多大程度上是必要的。為了回答這個問題，我們提出了一種方法來確定準確近似相應動態行為所需的超圖的最小階數。具體來說，我們開發了一個數學框架，允許我們在已知動態類型的情況下確定這一階數。我們將這些想法與超圖神經網絡結合起來，直接從包含觀察到的系統軌跡的合成數據集和真實數據集中學習動態行為本身以及由此產生的超圖的階數。

引言

超圖上的動態過程最近受到了廣泛關注。其例子包括同步（3, 4）、共識動態（5–7）、傳染病傳播（8–10）、隨機游走（11, 12）、標簽傳播（13–15）和社會傳染（16, 17）。一般來說，人們發現，對于在超圖而非普通圖上運行的動態系統，動態的重要特征可能會發生變化。例如，超圖上的傳染病過程可能具有不同的流行病暴發閾值（9, 10），或者群體強化效應可能會顯著改變超圖上意見形成的最終結果（17–19）。超圖還因其作為圖神經網絡的擴展而受到關注，并被應用于從計算機視覺中的三維形狀檢索（20）和姿態估計（21）到群體推薦任務（22）或醫學應用（例如癌癥組織分類）（23）等廣泛領域。

盡管在描述超圖上動態系統的數學方程中，這兩個方面通常被合并在一起，但從建模的角度來看，區分（i）限制系統中可能相互作用的拓撲關系（如超圖中所編碼的）和（ii）在每個超邊發生的局部多體動態模型（例如傳染病傳播、擴散和同步）是十分重要的。正是這兩個方面的相互作用導致了（可能的）高階效應的出現（2, 18, 24）。

例如，如果我們考慮超圖上的線性動態，那么我們不能期望出現任何高階效應。因為任何有限維空間之間的線性映射都可以用矩陣表示，對于線性動態，我們總能找到一個基于圖的成對相互作用動態來精確地模擬系統，即將矩陣與一個有效的加權圖等同起來（5, 6）。在實踐中，這意味著只要考慮線性動態，就可以使用圖而不是基于超圖的動態系統。同樣，研究表明，超圖上的半監督和無監督譜聚類問題的各種表述形式可以簡化為一個有效的基于圖的問題（25–27）。

更一般地，我們可以設想，根據局部動態的不同，我們可能能夠將一個在一般階數為 k 的超圖上運行的超圖動態系統重寫為在階數最多為 的超圖上發生的動態。這種簡化為低階關系是相關的，因為使用超圖存在幾個挑戰：最突出的是，由于超邊的數量可能會隨著節點數量的增加而呈組合式增長，使用超圖模型可能會帶來巨大的計算成本。對于大規模系統，這一點尤其重要。

然而，在實踐中，我們通常既不知道實體之間的確切關系集合，也不知道局部相互作用動態的解析形式，而只能獲得觀測數據，例如以軌跡的形式。例如，我們可以觀察到傳染病在人群中的傳播，作為個體及其接觸模式的軌跡，這些接觸模式可以用超圖表示。另一個例子是測量生態系統中物種的豐度及其相互作用。人們已經探索了許多不同的方法來近似這類時間序列數據。例如，最近有人提出將神經網絡視為具有連續層的模型（28）。這種觀點允許將神經網絡的前向傳播重新表述為常微分方程（ODE）的初值問題的解。使用這種對前向傳播的重新解釋的深度學習架構被稱為神經ODE，它們適用于構建連續時間的時間序列模型。神經ODE最近也被推廣到圖上（29, 30）。從測量數據中發現控制動態系統的方程是一個重要問題，已有大量文獻進行了研究（31–34）。這里的主要挑戰是找到一個足夠復雜以描述現有數據但又不至于過于復雜而引入過擬合的模型。

對于超圖上的動態系統，有許多可能的方法來抽象觀察到的分布式動態。例如，我們可以將其建模為在相對復雜的超圖上出現的簡單局部動態的結果。或者，我們也可以考慮更復雜的局部動態，通過實體之間更受限的關系集合進行相互作用。這引發了我們是否應該將模型的復雜性包含在相互作用的拓撲結構中，還是包含在動態模型中這一問題：在實踐中，我們需要在模型中編碼哪些多體關系？

在這里，我們考慮了一類廣泛的超圖動態系統，并引入了系統的拓撲階和動態階的概念，這些概念從不同角度衡量動態的復雜性。基于拓撲階和動態階的結合，我們可以確定超圖動態系統的有效階，即精確表示相應動態所需的超圖的最小階數。特別是，我們提出了一個框架，允許我們在給定動態的函數形式時推導出動態階和有效階。此外，為了從經驗數據中推斷有效動態階，我們提出了一種超圖神經網絡架構，允許我們直接從數據中學習超圖動態和由此產生的有效階，我們在合成數據集和真實數據集上對其進行了測試。總之，我們提出了一種有效的方法，用于降低一類超圖動態系統的復雜性，并從數據中學習它們的表示。

超圖動態系統的可約性

為了說明超圖上動態系統的動態階和有效階的概念，我們以超圖上的Kuramoto型動態（35）為例來具體闡述。Kuramoto振子動態已被應用于各種相位振子的同步現象（36），從電力網絡（37）到大腦活動（38）。許多研究工作致力于將其推廣到單純復形（3, 4）和超圖（39）。在這里，我們將比較兩種不同的超圖Kuramoto動態的表述形式。

因此，盡管我們在這里處理的是超圖上的非線性動態，但每個超邊上的動態是成對的，我們可以將其簡化為成對網絡動態：超圖的拓撲結構僅僅是通過矩陣 A 對系統進行了縮放。

總體而言，我們的Kuramoto振子動態示例表明，超圖是否可以投影到低階系統取決于每個超邊所支持的動態形式：如果超邊上的動態可以重寫為低階函數的線性組合，則動態是可約的。更一般地，對于某些函數形式，非線性動態總是可以簡化為低階超圖系統。在附錄S1中，我們展示了動態必須具有的類似線性的屬性，以便可以將其簡化為網絡動態系統。

在接下來的部分中，我們通過區分超圖的拓撲階和動態的動態階來形式化這種動態簡化方法。將拓撲結構與動態相結合，就形成了一個超圖動態系統，其有效階數不能大于這兩個階數的最小值。

動態階和有效階

這種動態具有動態階 ，因此動態可以分解為所有超邊上的成對函數之和，從而它們實際上是網絡動態。總體而言，求和順序與正弦函數的順序交換是使方程1和2的動態階不同的關鍵，從而導致系統具有不同的有效階。

盡管從概念上很有用，但如本節所述推導有效階需要知道動態的解析形式。因此，在下一節中，我們提出了一種方法，通過推導出一個超圖神經網絡模型來學習相應的函數。利用這種計算模型，我們可以從數據中學習動態，從而隱含地學習系統的有效階，而無需事先知道動態的函數形式。

從數據中學習局部動態和有效階

在本節中，我們提出了一種方法，直接從數據中學習系統的局部動態，從而確定系統的動態階和有效階。

學習超圖動態系統

結果

在本節中，我們展示了如何使用我們的框架從數據中學習超邊上的更新函數。然后，我們展示了如何利用這些結果推斷超圖動態系統的有效階。

數據集

數值實驗：學習更新函數

數值實驗：學習超圖動態系統

合成數據

我們提出了一種框架，用于推斷超圖動態系統，權衡拓撲復雜性和動態復雜性。我們利用這一框架，基于觀測數據，從解析和數據驅動兩個角度為給定的動態推導出一個有效的超圖動態系統。特別是，利用神經網絡作為一種靈活的方式來近似局部相互作用動態，我們能夠準確地學習超圖動態，并在尊重觀測到的動態的同時降低超圖的階。在這種情況下，找到一個小于超圖拓撲階的有效動態階表明，我們可以“修剪”一些超邊，使其階數更小，因為它們對特定的動態并不起作用。更具體地說，相關超邊被所有階子邊的集合所取代，然后動態被重寫，使其明確地在較小的子邊上演化。從模型復雜性降低的角度來看，這是非常有趣的。此外，學習到的模型能夠預測動態系統的長期行為。

我們相信，我們的方法論具有廣泛的應用潛力，并為一個目前研究相對較少的研究問題提供了起點，即在超圖、單純復形和細胞復形等高階領域中，拓撲復雜性和動態復雜性之間的權衡。未來的研究需要進一步探索（超圖）拓撲、動態和有效階之間的聯系。

方法

在本節中，我們將更詳細地形式化我們的超圖動態系統模型。特別是，我們從拓撲結構和局部動態兩個方面來考慮動態。系統的拓撲結構決定了系統中哪些組成部分在局部相互作用。動態，特別是邊上的更新函數，決定了這些組成部分如何相互作用（更新），而這些局部相互作用如何全局組合（投影）則再次由拓撲結構決定。

HyDy-GNN 的技術細節

數據集與數值實驗中考慮的動力學

我們在合成數據集（Erd?s-Rényi 超圖）和真實拓撲數據集（高中生接觸模式數據集）上進行實驗。我們假設圖的拓撲結構以鄰接表的形式給出，并從中提取提升算子。基于這一拓撲結構，我們模擬特定的動力學過程。

在本研究中，我們特別關注網絡科學中的四種常見線性和非線性動力學：Kuramoto 動力學（同步）、SI 動力學（流行病傳播）、MCM（意見動力學）和擴散過程。我們在定義 3 的記號下對這些動力學進行一般階數 p 的定義。

同步（Kuramoto 振子動力學）

Kuramoto 模型已被應用于各種相振子的同步現象，涵蓋從電力網絡到大腦活動等多個領域。該模型的研究已擴展至超圖。節點狀態 x i 表示振子 i 的相位，而（超）邊表示振子之間的耦合關系。

流行病傳播（易感-感染模型，SI 模型）

傳染病的傳播可以用簡單的 SI 模型來描述。節點狀態 x i 表示節點 i 的感染概率。（超）邊表示人與人之間的感染率。

意見動態與強化（MCM）

MCM（多邊共識模型）用于模擬具有群體效應的意見形成過程。這些效應通過一個非線性函數來體現，該函數對模型中的共識項進行縮放。根據其形式，縮放函數可以捕捉超邊成員之間的強化效應，我們在這里特別選擇模型的一個方面——MCMI模型，它模擬了同質性。

線性共識動態（擴散）

這種簡單的共識協議可以捕捉自主代理之間尋求某種合作形式時的信息交換（41）。其中的連接描述了節點之間的相互影響。其應用范圍從社會網絡中信息的傳播到最優控制。

合成和真實世界的超圖

對于我們的合成超圖，我們使用了一組包含 20 個節點的 500 個 Erd?s-Rényi 超圖。任意兩個節點之間生成一條邊的概率為 0.1，任意三個節點之間生成一條邊的概率為 0.01，任意四個節點之間生成一條邊的概率為 0.001。超圖是根據文獻（43）中描述的方法，通過 xgi 包（42）生成的。

作為真實世界超圖的例子，我們使用了一個從高中學生佩戴的可穿戴傳感器記錄的交互數據中構建的時序高階數據集的靜態版本（44, 45）。該超圖包含 327 個節點和 7818 條超邊，平均大小為 2.3 個節點，最大大小為 5。然而，由于數據集中只包含 7 條大小為 5 的邊，我們將超圖簡化為只考慮大小不超過 4 的超邊，從而得到一個階數為 4 的超圖。最終得到的數據集包括 222 條四邊，2091 條三邊和 5498 條二邊。在這個超圖上，我們模擬了可以在接觸數據集上發生的三種社會動態：傳染病傳播（SI）、帶有同伴壓力的意見動態（MCM）和擴散。

原文鏈接： https://www.science.org/doi/epdf/10.1126/sciadv.adh4053