高階網(wǎng)絡(luò)表征：圖框架綜述（第二版）

Representing Higher-Order Networks: A Survey of Graph-Based Frameworks(Second Edition)

https://philarchive.org/archive/FUJRHN

摘要

許多現(xiàn)實(shí)世界的現(xiàn)象可以自然地用圖和網(wǎng)絡(luò)進(jìn)行建模。然而，經(jīng)典圖模型通常局限于成對(duì)交互（pairwise interactions），可能無(wú)法充分捕捉實(shí)踐中出現(xiàn)的更豐富結(jié)構(gòu)。高階圖形式化方法（higher-order graph formalisms）通過(guò)納入多路（multiway）、層級(jí)（hierarchical）、時(shí)序（temporal）、多層（multilayer）、遞歸（recursive）以及基于張量（tensor-based）的交互，擴(kuò)展了這一框架，從而為復(fù)雜系統(tǒng)提供更具表達(dá)力的表征。

本書(shū)全面概述了可用于建模高階網(wǎng)絡(luò)的數(shù)學(xué)概念。書(shū)中綜述了基礎(chǔ)概念、外延性框架（extensional frameworks）以及新近引入的形式化方法，著重闡述其結(jié)構(gòu)原理、相互關(guān)系及建模作用。本書(shū)旨在提供一個(gè)統(tǒng)一的視角，幫助讀者比較多樣的高階網(wǎng)絡(luò)模型，并為理論研究與實(shí)際應(yīng)用識(shí)別合適的工具。

本書(shū)為第二版（Edition 2.0）。主要新增內(nèi)容包括若干概念的補(bǔ)充，以及對(duì)排版錯(cuò)誤和解釋說(shuō)明的修正與完善。

關(guān)鍵詞：超圖（Hypergraph），超超圖（Superhypergraph），高階圖（Higher-Order Graphs）

1 引言

1.1 高階圖

眾所周知，許多現(xiàn)實(shí)世界的現(xiàn)象可以使用圖和網(wǎng)絡(luò)進(jìn)行建模 [1, 2]。然而，許多此類系統(tǒng)展現(xiàn)出超越成對(duì)交互（pairwise interactions）的結(jié)構(gòu)：它們可能涉及多路關(guān)系（multiway relations）、層級(jí)組織、嵌套或遞歸依賴、時(shí)間演化，或多層耦合。經(jīng)典圖模型通常不足以以數(shù)學(xué)上忠實(shí)的方式表示這些特征。

為了解決這一局限性，人們已經(jīng)開(kāi)發(fā)了廣泛的高階形式化方法（higher-order formalisms），包括超圖（hypergraphs）[3]、超超圖（superhypergraphs）[4]、基于元圖的模型（metagraph-based models）[5]、基于單純形和胞腔復(fù)形的框架（simplicial and cell-complex-based frameworks）、多層和時(shí)間網(wǎng)絡(luò)，以及更近期的范疇論或語(yǔ)義方法。例如，超超圖通過(guò)允許頂點(diǎn)域本身是分層的，從而擴(kuò)展了高階網(wǎng)絡(luò)模型，使得集合值（set-valued）和迭代結(jié)構(gòu)能夠直接在對(duì)象域中進(jìn)行編碼 [4]。結(jié)果是，高階圖論已經(jīng)發(fā)展成為一個(gè)廣泛且異質(zhì)的領(lǐng)域，許多概念源自不同的數(shù)學(xué)視角和建模目標(biāo)（參見(jiàn) [6, 7, 8, 9, 10, 11]）。

高階網(wǎng)絡(luò)（或高階結(jié)構(gòu)）的概念已應(yīng)用于如下領(lǐng)域。當(dāng)然，應(yīng)用范圍并不局限于這些：

• 交通與物流網(wǎng)絡(luò)（參見(jiàn) [12, 13, 14, 15, 16]）：與普通成對(duì)圖相比，高階圖能更自然地表示多站配送計(jì)劃、樞紐協(xié)調(diào)、共享路線以及群組流約束。
• 社交網(wǎng)絡(luò)分析（參見(jiàn) [17, 18, 19, 20, 21, 22]）：它們對(duì)群組對(duì)話、團(tuán)隊(duì)互動(dòng)、重疊社區(qū)和層級(jí)成員關(guān)系進(jìn)行建模，超越了簡(jiǎn)單的人與人之間的鏈接。
• 知識(shí)表示與語(yǔ)義網(wǎng)絡(luò)（參見(jiàn) [23, 24]）：它們對(duì)于在知識(shí)系統(tǒng)中編碼多實(shí)體關(guān)系、類型化事實(shí)、上下文關(guān)聯(lián)和層級(jí)語(yǔ)義結(jié)構(gòu)很有用。
• 分子與化學(xué)結(jié)構(gòu)分析（參見(jiàn) [25, 26, 27]）：它們可以描述化學(xué)系統(tǒng)中的多原子相互作用、反應(yīng)機(jī)制、分子復(fù)合物以及高階結(jié)構(gòu)依賴。
• 神經(jīng)科學(xué)與腦網(wǎng)絡(luò)（參見(jiàn) [28, 29]）：它們支持對(duì)集體神經(jīng)相互作用、多區(qū)域同步、分層腦連接以及時(shí)間依賴的功能組織進(jìn)行建模。
• 機(jī)器學(xué)習(xí)與圖神經(jīng)網(wǎng)絡(luò)（參見(jiàn) [30, 31, 32, 10, 33]）：高階圖應(yīng)用于涉及群組、層級(jí)或嵌套結(jié)構(gòu)的關(guān)系的學(xué)習(xí)任務(wù)中，例如超圖神經(jīng)網(wǎng)絡(luò)（HyperGraph Neural Networks）及相關(guān)模型。
• 推薦系統(tǒng)（參見(jiàn) [34, 35, 36]）：它們可以同時(shí)捕捉用戶、物品、上下文、時(shí)間和屬性交互，提供比普通二部圖更豐富的關(guān)系表示。
• 供應(yīng)鏈與組織系統(tǒng)（參見(jiàn) [37]）：它們對(duì)供應(yīng)商、資源、部門和流程之間的多方依賴進(jìn)行建模，包括層級(jí)和跨層級(jí)的協(xié)調(diào)結(jié)構(gòu)。
• 通信與信息網(wǎng)絡(luò)（參見(jiàn) [38]）：它們適合表示多播通信、分層協(xié)議、群組傳輸以及動(dòng)態(tài)變化的高階連接模式。
• 決策制定與運(yùn)籌學(xué)（參見(jiàn) [39, 40, 41, 42]）：它們可以在復(fù)雜決策問(wèn)題中表達(dá)交互準(zhǔn)則、分組備選方案、層級(jí)評(píng)估結(jié)構(gòu)以及感知不確定性的關(guān)系依賴。

1.2 我們的貢獻(xiàn)

已經(jīng)開(kāi)發(fā)了多種多樣的用于表示高階網(wǎng)絡(luò)的數(shù)學(xué)框架。然而，這些框架通常分散在不同的數(shù)學(xué)傳統(tǒng)、術(shù)語(yǔ)和應(yīng)用領(lǐng)域中，這使得系統(tǒng)性的比較變得困難。出于這個(gè)原因，我們認(rèn)為編寫(xiě)一本將這些概念匯集在一個(gè)連貫參考中的綜述類書(shū)籍是有價(jià)值的。

因此，本書(shū)提供了可用于建模高階網(wǎng)絡(luò)的數(shù)學(xué)概念的廣泛且結(jié)構(gòu)化的概述。其目的是為這些形式化方法提供一個(gè)統(tǒng)一的切入點(diǎn)，闡明它們的基礎(chǔ)思想，并強(qiáng)調(diào)它們的共同特征及其本質(zhì)差異。通過(guò)這種方式，本書(shū)旨在支持進(jìn)一步的理論發(fā)展以及在人工智能（AI）和相關(guān)領(lǐng)域的應(yīng)用。

然而，值得注意的是，這里收集的概念并非在單一統(tǒng)一的意義上是“高階”的。一些框架通過(guò)增加交互的元數(shù)（arity）來(lái)推廣圖，如在超圖類模型中。另一些引入了層級(jí)、嵌套或遞歸，如在超超圖類構(gòu)造中。還有一些通過(guò)層、時(shí)間索引或多方面組織來(lái)編碼高階性，如在多層和時(shí)間網(wǎng)絡(luò)中。最后，一些方法完全源自不同的數(shù)學(xué)語(yǔ)義，包括運(yùn)算子（operadic）、幺半（monoidal）、關(guān)系、基于張量、基于閉包和余代數(shù)的觀點(diǎn)。

為了使這種多樣性更易于理解和比較，本書(shū)中的概念根據(jù)摘要表中采用的實(shí)際分類被組織成四個(gè) broad families（大類）：

1. 組合、集合論和序論結(jié)構(gòu)，
2. 幾何、拓?fù)浜突趶?fù)形的結(jié)構(gòu)，
3. 因式分解、約束、分層、時(shí)間和基于張量的結(jié)構(gòu)，以及
4. 語(yǔ)義、組合、基于知識(shí)和邏輯的結(jié)構(gòu)。

作為參考，本書(shū)中使用的高階網(wǎng)絡(luò)概念的實(shí)用四大家族組織形式見(jiàn)表 1.1。

2 組合、集合論與序論族

在本章中，我們描述高階圖的主要類型。作為參考，本書(shū)中探討的組合、集合論和序論高階結(jié)構(gòu)列于表 2.1 中。

2.1 超圖與超超圖

超超圖通過(guò)允許頂點(diǎn)域本身是分層的，從而擴(kuò)展了高階網(wǎng)絡(luò)模型。具體而言，從一個(gè)基礎(chǔ)集開(kāi)始并迭代冪集運(yùn)算；頂點(diǎn)（通常稱為超頂點(diǎn)）可以是位于該迭代規(guī)定層級(jí)上的集合值對(duì)象，而（超）邊則編碼這些高層頂點(diǎn)之間的關(guān)聯(lián) [4]。相關(guān)的層級(jí)構(gòu)造已在應(yīng)用中得到探索 [43]。

此外，已知有幾種超圖的擴(kuò)展，包括模糊超圖 [44, 45, 46]、中性超圖 [47, 48, 49] 和 plithogenic 超圖 [50]。同樣，超超圖的擴(kuò)展，如模糊超超圖 [41]、中性超超圖 [51, 52] 和 plithogenic 超超圖 [53, 54, 55] 也已被研究。此外，作為有向圖概念，以下概念是已知的：有向超圖 [56, 57]、雙向超圖 [58]、有向超超圖 [59, 60] 和雙向超超圖 [61, 58]。如需更廣泛的概述，我們建議讀者參考綜述專著 [62]。

2.2 多重圖與迭代多重圖

多重圖是一種允許平行邊和自環(huán)的圖；形式上，邊是頂點(diǎn)之間可能具有重?cái)?shù)的多重集 [68, 69, 70]。作為擴(kuò)展，已知的概念包括模糊多重圖 [71, 72, 73]、二分多重圖 [74, 75]、完全多重圖 [76, 77]、中性多重圖 [68, 78]、軟多重圖 [79] 和有向多重圖 [80]。迭代多重圖使用迭代多重集作為頂點(diǎn)對(duì)象，因此頂點(diǎn)本身可以是遞歸嵌套至深度 n 的多重集。

2.3 h-模型

一個(gè) h-模型是一個(gè)結(jié)構(gòu) ?S, H, I?，由一個(gè)基集 S、S 上超圖的一個(gè)有限集合 H，以及一個(gè)解釋映射 I 組成，該映射將每個(gè)命題原子指派為 H 中的一個(gè)超圖 [82]。

一個(gè) sh-模型可被視為基于超超圖的 h-模型對(duì)應(yīng)物：它不是為每個(gè)命題原子指派一個(gè)超圖，而是指派一個(gè)固定基集上的有限 n-超超圖。

2.4 無(wú)鏈子集

偏序集（poset）的一個(gè) k-無(wú)鏈子集是一個(gè)不包含長(zhǎng)度為 k 的嚴(yán)格遞增鏈的子集；等價(jià)地，它避免 k 個(gè)相互可比的元素 [83]。

2.5 冪集圖

冪集圖的頂點(diǎn)由一個(gè)集合的非空真子集給出，邊存在于通過(guò)包含關(guān)系可比的子集之間 [84]。迭代冪集圖重復(fù)應(yīng)用非平凡冪集構(gòu)造；在每一深度，頂點(diǎn)是嵌套子集，當(dāng)通過(guò)包含關(guān)系可比時(shí)相鄰。

2.6 約翰遜圖

約翰遜圖的頂點(diǎn)由 [n] 的 w-子集給出，邊連接相差一個(gè)元素的頂點(diǎn)對(duì) [85, 86, 87]。約翰遜圖的相關(guān)概念也是已知的，例如廣義約翰遜圖 [88, 89]。

2.7 克涅瑟圖

克涅瑟圖（Kneser graph）的頂點(diǎn)由 [n] 的 k-子集給出，邊連接不相交的頂點(diǎn)對(duì) [91, 92, 93, 94]。相關(guān)概念也是已知的，例如克涅瑟超圖 [95, 96]、二分克涅瑟圖 [97, 98]、穩(wěn)定克涅瑟圖 [99, 100] 和廣義克涅瑟圖 [101, 102]。

2.8 元圖與迭代元圖

元圖以圖作為頂點(diǎn)；邊表示這些圖之間帶標(biāo)簽的關(guān)系，滿足關(guān)系定義的關(guān)聯(lián)約束（參見(jiàn) [103, 104, 105, 106, 107]）。元圖也被稱為圖之圖。迭代元圖重復(fù)這一構(gòu)造：頂點(diǎn)是較低深度的元圖，并通過(guò)提升的關(guān)系遞歸地鏈接它們 [103]。

定義 2.8.1（元圖（Metagraph；圖之圖））。[103] 固定一個(gè)有限圖的非空全集 G（默認(rèn)無(wú)向且無(wú)環(huán)），并固定 G 上二元關(guān)系的一個(gè)非空族 R，即

2.9 元超圖與元超超圖

元超圖是一種頂點(diǎn)為對(duì)象的超圖；每個(gè)超邊通過(guò)帶標(biāo)簽的關(guān)系關(guān)聯(lián)有限的頂點(diǎn)集（參見(jiàn) [5, 108]）。它也可以被描述為超圖的超圖。

元超超圖的頂點(diǎn)為超超圖；超邊關(guān)聯(lián)它們的有限集合，且受關(guān)系標(biāo)簽約束 [5]。它也可以被描述為超超圖的超超圖。

成立，因此按照定義 2.9.1 的意義，M 是 (U, R) 上的元超圖。直觀上，M 是一個(gè)“超圖之超圖”，其元超邊斷言某些城市級(jí)超圖族在產(chǎn)品目錄上存在強(qiáng)烈的重疊。該示例的概覽圖見(jiàn)圖 2.9。

2.10 嵌套超圖與嵌套超超圖

嵌套超圖允許超邊將其他超邊作為元素包含在內(nèi)，并通過(guò)秩強(qiáng)制實(shí)施無(wú)環(huán)的良基嵌套 [109]。嵌套超超圖使用來(lái)自迭代冪集的超頂點(diǎn)；超超邊可以包含其他超超邊，并通過(guò)秩排序以避免環(huán) [109]。

2.11 多重超圖與多重超超圖

多重超圖是一種允許重復(fù)超邊的超圖；邊構(gòu)成非空頂點(diǎn)子集的多重集，并帶有重?cái)?shù)計(jì)數(shù) [110, 111]。已知多重超圖同時(shí)推廣了超圖和多重圖。多重超超圖是一種允許重復(fù)超邊的超超圖；頂點(diǎn)是嵌套集合對(duì)象，且超邊攜帶重?cái)?shù)。

定義 2.11.1（多重超圖）。[110, 111] 設(shè) V 是一個(gè)有限非空集。記：

2.13 迭代全圖

全圖的頂點(diǎn)同時(shí)包含圖的頂點(diǎn)和邊，并通過(guò)鄰接或關(guān)聯(lián)關(guān)系將它們連接起來(lái)（參見(jiàn) [127, 128]）。

2.14 層級(jí)超超圖

層級(jí)超超圖是一種超超圖，其頂點(diǎn)存在于多個(gè)冪集層級(jí)上，允許邊連接混合層級(jí)的超頂點(diǎn)，同時(shí)保持向下封閉一致性（參見(jiàn) [131, 132]）。

原文鏈接：https://philarchive.org/archive/FUJRHN