Learning the effective order of a hypergraph dynamical system
學(xué)習(xí)超圖動力系統(tǒng)的有效階
https://www.science.org/doi/epdf/10.1126/sciadv.adh4053
在超圖上運行的動態(tài)系統(tǒng)可以展現(xiàn)出豐富多樣的行為，這些行為在僅具有成對相互作用的系統(tǒng)中是無法觀察到的。對于一個具有潛在超圖結(jié)構(gòu)的分布式動態(tài)系統(tǒng)，一個有趣的問題是：為了真實地復(fù)現(xiàn)觀察到的動態(tài)行為，這種超圖結(jié)構(gòu)到底在多大程度上是必要的。為了回答這個問題，我們提出了一種方法來確定準(zhǔn)確近似相應(yīng)動態(tài)行為所需的超圖的最小階數(shù)。具體來說，我們開發(fā)了一個數(shù)學(xué)框架，允許我們在已知動態(tài)類型的情況下確定這一階數(shù)。我們將這些想法與超圖神經(jīng)網(wǎng)絡(luò)結(jié)合起來，直接從包含觀察到的系統(tǒng)軌跡的合成數(shù)據(jù)集和真實數(shù)據(jù)集中學(xué)習(xí)動態(tài)行為本身以及由此產(chǎn)生的超圖的階數(shù)。
引言
超圖上的動態(tài)過程最近受到了廣泛關(guān)注。其例子包括同步（3, 4）、共識動態(tài)（5–7）、傳染病傳播（8–10）、隨機游走（11, 12）、標(biāo)簽傳播（13–15）和社會傳染（16, 17）。一般來說，人們發(fā)現(xiàn)，對于在超圖而非普通圖上運行的動態(tài)系統(tǒng)，動態(tài)的重要特征可能會發(fā)生變化。例如，超圖上的傳染病過程可能具有不同的流行病暴發(fā)閾值（9, 10），或者群體強化效應(yīng)可能會顯著改變超圖上意見形成的最終結(jié)果（17–19）。超圖還因其作為圖神經(jīng)網(wǎng)絡(luò)的擴展而受到關(guān)注，并被應(yīng)用于從計算機視覺中的三維形狀檢索（20）和姿態(tài)估計（21）到群體推薦任務(wù)（22）或醫(yī)學(xué)應(yīng)用（例如癌癥組織分類）（23）等廣泛領(lǐng)域。
盡管在描述超圖上動態(tài)系統(tǒng)的數(shù)學(xué)方程中，這兩個方面通常被合并在一起，但從建模的角度來看，區(qū)分（i）限制系統(tǒng)中可能相互作用的拓撲關(guān)系（如超圖中所編碼的）和（ii）在每個超邊發(fā)生的局部多體動態(tài)模型（例如傳染病傳播、擴散和同步）是十分重要的。正是這兩個方面的相互作用導(dǎo)致了（可能的）高階效應(yīng)的出現(xiàn)（2, 18, 24）。
例如，如果我們考慮超圖上的線性動態(tài)，那么我們不能期望出現(xiàn)任何高階效應(yīng)。因為任何有限維空間之間的線性映射都可以用矩陣表示，對于線性動態(tài)，我們總能找到一個基于圖的成對相互作用動態(tài)來精確地模擬系統(tǒng)，即將矩陣與一個有效的加權(quán)圖等同起來（5, 6）。在實踐中，這意味著只要考慮線性動態(tài)，就可以使用圖而不是基于超圖的動態(tài)系統(tǒng)。同樣，研究表明，超圖上的半監(jiān)督和無監(jiān)督譜聚類問題的各種表述形式可以簡化為一個有效的基于圖的問題（25–27）。
更一般地，我們可以設(shè)想，根據(jù)局部動態(tài)的不同，我們可能能夠?qū)⒁粋€在一般階數(shù)為 k 的超圖上運行的超圖動態(tài)系統(tǒng)重寫為在階數(shù)最多為 的超圖上發(fā)生的動態(tài)。這種簡化為低階關(guān)系是相關(guān)的，因為使用超圖存在幾個挑戰(zhàn)：最突出的是，由于超邊的數(shù)量可能會隨著節(jié)點數(shù)量的增加而呈組合式增長，使用超圖模型可能會帶來巨大的計算成本。對于大規(guī)模系統(tǒng)，這一點尤其重要。
然而，在實踐中，我們通常既不知道實體之間的確切關(guān)系集合，也不知道局部相互作用動態(tài)的解析形式，而只能獲得觀測數(shù)據(jù)，例如以軌跡的形式。例如，我們可以觀察到傳染病在人群中的傳播，作為個體及其接觸模式的軌跡，這些接觸模式可以用超圖表示。另一個例子是測量生態(tài)系統(tǒng)中物種的豐度及其相互作用。人們已經(jīng)探索了許多不同的方法來近似這類時間序列數(shù)據(jù)。例如，最近有人提出將神經(jīng)網(wǎng)絡(luò)視為具有連續(xù)層的模型（28）。這種觀點允許將神經(jīng)網(wǎng)絡(luò)的前向傳播重新表述為常微分方程（ODE）的初值問題的解。使用這種對前向傳播的重新解釋的深度學(xué)習(xí)架構(gòu)被稱為神經(jīng)ODE，它們適用于構(gòu)建連續(xù)時間的時間序列模型。神經(jīng)ODE最近也被推廣到圖上（29, 30）。從測量數(shù)據(jù)中發(fā)現(xiàn)控制動態(tài)系統(tǒng)的方程是一個重要問題，已有大量文獻進行了研究（31–34）。這里的主要挑戰(zhàn)是找到一個足夠復(fù)雜以描述現(xiàn)有數(shù)據(jù)但又不至于過于復(fù)雜而引入過擬合的模型。
對于超圖上的動態(tài)系統(tǒng)，有許多可能的方法來抽象觀察到的分布式動態(tài)。例如，我們可以將其建模為在相對復(fù)雜的超圖上出現(xiàn)的簡單局部動態(tài)的結(jié)果。或者，我們也可以考慮更復(fù)雜的局部動態(tài)，通過實體之間更受限的關(guān)系集合進行相互作用。這引發(fā)了我們是否應(yīng)該將模型的復(fù)雜性包含在相互作用的拓撲結(jié)構(gòu)中，還是包含在動態(tài)模型中這一問題：在實踐中，我們需要在模型中編碼哪些多體關(guān)系？
在這里，我們考慮了一類廣泛的超圖動態(tài)系統(tǒng)，并引入了系統(tǒng)的拓撲階和動態(tài)階的概念，這些概念從不同角度衡量動態(tài)的復(fù)雜性?；谕負潆A和動態(tài)階的結(jié)合，我們可以確定超圖動態(tài)系統(tǒng)的有效階，即精確表示相應(yīng)動態(tài)所需的超圖的最小階數(shù)。特別是，我們提出了一個框架，允許我們在給定動態(tài)的函數(shù)形式時推導(dǎo)出動態(tài)階和有效階。此外，為了從經(jīng)驗數(shù)據(jù)中推斷有效動態(tài)階，我們提出了一種超圖神經(jīng)網(wǎng)絡(luò)架構(gòu)，允許我們直接從數(shù)據(jù)中學(xué)習(xí)超圖動態(tài)和由此產(chǎn)生的有效階，我們在合成數(shù)據(jù)集和真實數(shù)據(jù)集上對其進行了測試?？傊?，我們提出了一種有效的方法，用于降低一類超圖動態(tài)系統(tǒng)的復(fù)雜性，并從數(shù)據(jù)中學(xué)習(xí)它們的表示。
超圖動態(tài)系統(tǒng)的可約性
為了說明超圖上動態(tài)系統(tǒng)的動態(tài)階和有效階的概念，我們以超圖上的Kuramoto型動態(tài)（35）為例來具體闡述。Kuramoto振子動態(tài)已被應(yīng)用于各種相位振子的同步現(xiàn)象（36），從電力網(wǎng)絡(luò)（37）到大腦活動（38）。許多研究工作致力于將其推廣到單純復(fù)形（3, 4）和超圖（39）。在這里，我們將比較兩種不同的超圖Kuramoto動態(tài)的表述形式。
因此，盡管我們在這里處理的是超圖上的非線性動態(tài)，但每個超邊上的動態(tài)是成對的，我們可以將其簡化為成對網(wǎng)絡(luò)動態(tài)：超圖的拓撲結(jié)構(gòu)僅僅是通過矩陣 A 對系統(tǒng)進行了縮放。
總體而言，我們的Kuramoto振子動態(tài)示例表明，超圖是否可以投影到低階系統(tǒng)取決于每個超邊所支持的動態(tài)形式：如果超邊上的動態(tài)可以重寫為低階函數(shù)的線性組合，則動態(tài)是可約的。更一般地，對于某些函數(shù)形式，非線性動態(tài)總是可以簡化為低階超圖系統(tǒng)。在附錄S1中，我們展示了動態(tài)必須具有的類似線性的屬性，以便可以將其簡化為網(wǎng)絡(luò)動態(tài)系統(tǒng)。
在接下來的部分中，我們通過區(qū)分超圖的拓撲階和動態(tài)的動態(tài)階來形式化這種動態(tài)簡化方法。將拓撲結(jié)構(gòu)與動態(tài)相結(jié)合，就形成了一個超圖動態(tài)系統(tǒng)，其有效階數(shù)不能大于這兩個階數(shù)的最小值。
動態(tài)階和有效階
這種動態(tài)具有動態(tài)階 ，因此動態(tài)可以分解為所有超邊上的成對函數(shù)之和，從而它們實際上是網(wǎng)絡(luò)動態(tài)?？傮w而言，求和順序與正弦函數(shù)的順序交換是使方程1和2的動態(tài)階不同的關(guān)鍵，從而導(dǎo)致系統(tǒng)具有不同的有效階。
盡管從概念上很有用，但如本節(jié)所述推導(dǎo)有效階需要知道動態(tài)的解析形式。因此，在下一節(jié)中，我們提出了一種方法，通過推導(dǎo)出一個超圖神經(jīng)網(wǎng)絡(luò)模型來學(xué)習(xí)相應(yīng)的函數(shù)。利用這種計算模型，我們可以從數(shù)據(jù)中學(xué)習(xí)動態(tài)，從而隱含地學(xué)習(xí)系統(tǒng)的有效階，而無需事先知道動態(tài)的函數(shù)形式。
從數(shù)據(jù)中學(xué)習(xí)局部動態(tài)和有效階
在本節(jié)中，我們提出了一種方法，直接從數(shù)據(jù)中學(xué)習(xí)系統(tǒng)的局部動態(tài)，從而確定系統(tǒng)的動態(tài)階和有效階。
學(xué)習(xí)超圖動態(tài)系統(tǒng)
結(jié)果
在本節(jié)中，我們展示了如何使用我們的框架從數(shù)據(jù)中學(xué)習(xí)超邊上的更新函數(shù)。然后，我們展示了如何利用這些結(jié)果推斷超圖動態(tài)系統(tǒng)的有效階。
數(shù)據(jù)集
數(shù)值實驗：學(xué)習(xí)更新函數(shù)
數(shù)值實驗：學(xué)習(xí)超圖動態(tài)系統(tǒng)
合成數(shù)據(jù)
我們提出了一種框架，用于推斷超圖動態(tài)系統(tǒng)，權(quán)衡拓撲復(fù)雜性和動態(tài)復(fù)雜性。我們利用這一框架，基于觀測數(shù)據(jù)，從解析和數(shù)據(jù)驅(qū)動兩個角度為給定的動態(tài)推導(dǎo)出一個有效的超圖動態(tài)系統(tǒng)。特別是，利用神經(jīng)網(wǎng)絡(luò)作為一種靈活的方式來近似局部相互作用動態(tài)，我們能夠準(zhǔn)確地學(xué)習(xí)超圖動態(tài)，并在尊重觀測到的動態(tài)的同時降低超圖的階。在這種情況下，找到一個小于超圖拓撲階的有效動態(tài)階表明，我們可以“修剪”一些超邊，使其階數(shù)更小，因為它們對特定的動態(tài)并不起作用。更具體地說，相關(guān)超邊被所有階子邊的集合所取代，然后動態(tài)被重寫，使其明確地在較小的子邊上演化。從模型復(fù)雜性降低的角度來看，這是非常有趣的。此外，學(xué)習(xí)到的模型能夠預(yù)測動態(tài)系統(tǒng)的長期行為。
我們相信，我們的方法論具有廣泛的應(yīng)用潛力，并為一個目前研究相對較少的研究問題提供了起點，即在超圖、單純復(fù)形和細胞復(fù)形等高階領(lǐng)域中，拓撲復(fù)雜性和動態(tài)復(fù)雜性之間的權(quán)衡。未來的研究需要進一步探索（超圖）拓撲、動態(tài)和有效階之間的聯(lián)系。
方法
在本節(jié)中，我們將更詳細地形式化我們的超圖動態(tài)系統(tǒng)模型。特別是，我們從拓撲結(jié)構(gòu)和局部動態(tài)兩個方面來考慮動態(tài)。系統(tǒng)的拓撲結(jié)構(gòu)決定了系統(tǒng)中哪些組成部分在局部相互作用。動態(tài)，特別是邊上的更新函數(shù)，決定了這些組成部分如何相互作用（更新），而這些局部相互作用如何全局組合（投影）則再次由拓撲結(jié)構(gòu)決定。
HyDy-GNN 的技術(shù)細節(jié)
數(shù)據(jù)集與數(shù)值實驗中考慮的動力學(xué)
我們在合成數(shù)據(jù)集（Erd?s-Rényi 超圖）和真實拓撲數(shù)據(jù)集（高中生接觸模式數(shù)據(jù)集）上進行實驗。我們假設(shè)圖的拓撲結(jié)構(gòu)以鄰接表的形式給出，并從中提取提升算子?；谶@一拓撲結(jié)構(gòu)，我們模擬特定的動力學(xué)過程。
在本研究中，我們特別關(guān)注網(wǎng)絡(luò)科學(xué)中的四種常見線性和非線性動力學(xué)：Kuramoto 動力學(xué)（同步）、SI 動力學(xué)（流行病傳播）、MCM（意見動力學(xué)）和擴散過程。我們在定義 3 的記號下對這些動力學(xué)進行一般階數(shù) p 的定義。
同步（Kuramoto 振子動力學(xué)）
Kuramoto 模型已被應(yīng)用于各種相振子的同步現(xiàn)象，涵蓋從電力網(wǎng)絡(luò)到大腦活動等多個領(lǐng)域。該模型的研究已擴展至超圖。節(jié)點狀態(tài) x i 表示振子 i 的相位，而（超）邊表示振子之間的耦合關(guān)系。
流行病傳播（易感-感染模型，SI 模型）
傳染病的傳播可以用簡單的 SI 模型來描述。節(jié)點狀態(tài) x i 表示節(jié)點 i 的感染概率。（超）邊表示人與人之間的感染率。
意見動態(tài)與強化（MCM）
MCM（多邊共識模型）用于模擬具有群體效應(yīng)的意見形成過程。這些效應(yīng)通過一個非線性函數(shù)來體現(xiàn)，該函數(shù)對模型中的共識項進行縮放。根據(jù)其形式，縮放函數(shù)可以捕捉超邊成員之間的強化效應(yīng)，我們在這里特別選擇模型的一個方面——MCMI模型，它模擬了同質(zhì)性。
線性共識動態(tài)（擴散）
這種簡單的共識協(xié)議可以捕捉自主代理之間尋求某種合作形式時的信息交換（41）。其中的連接描述了節(jié)點之間的相互影響。其應(yīng)用范圍從社會網(wǎng)絡(luò)中信息的傳播到最優(yōu)控制。
合成和真實世界的超圖
對于我們的合成超圖，我們使用了一組包含 20 個節(jié)點的 500 個 Erd?s-Rényi 超圖。任意兩個節(jié)點之間生成一條邊的概率為 0.1，任意三個節(jié)點之間生成一條邊的概率為 0.01，任意四個節(jié)點之間生成一條邊的概率為 0.001。超圖是根據(jù)文獻（43）中描述的方法，通過 xgi 包（42）生成的。
作為真實世界超圖的例子，我們使用了一個從高中學(xué)生佩戴的可穿戴傳感器記錄的交互數(shù)據(jù)中構(gòu)建的時序高階數(shù)據(jù)集的靜態(tài)版本（44, 45）。該超圖包含 327 個節(jié)點和 7818 條超邊，平均大小為 2.3 個節(jié)點，最大大小為 5。然而，由于數(shù)據(jù)集中只包含 7 條大小為 5 的邊，我們將超圖簡化為只考慮大小不超過 4 的超邊，從而得到一個階數(shù)為 4 的超圖。最終得到的數(shù)據(jù)集包括 222 條四邊，2091 條三邊和 5498 條二邊。在這個超圖上，我們模擬了可以在接觸數(shù)據(jù)集上發(fā)生的三種社會動態(tài)：傳染病傳播（SI）、帶有同伴壓力的意見動態(tài)（MCM）和擴散。
原文鏈接： https://www.science.org/doi/epdf/10.1126/sciadv.adh4053
熱門跟貼