超級(jí)超圖神經(jīng)網(wǎng)絡(luò)與多元生圖神經(jīng)網(wǎng)絡(luò)：理論基礎(chǔ)

Superhypergraph Neural Networks and Plithogenic Graph NeuralNetworks: Theoretical FoundationsNetworks: Theoretical Foundations

https://digitalrepository.unm.edu/cgi/viewcontent.cgi?params=/context/math_fsp/article/1945/&path_info=SuperHyperGraphNeuralNetworks.pdf

第 17 章 超級(jí)超圖神經(jīng)網(wǎng)絡(luò)與多元生圖神經(jīng)網(wǎng)絡(luò)：理論基礎(chǔ)

摘要：

超圖通過允許邊連接多個(gè)節(jié)點(diǎn)來擴(kuò)展傳統(tǒng)圖，而超級(jí)超圖則進(jìn)一步泛化這一概念，以表示更復(fù)雜的關(guān)系。

神經(jīng)網(wǎng)絡(luò)受生物系統(tǒng)啟發(fā)，廣泛用于模式識(shí)別、數(shù)據(jù)分類和預(yù)測(cè)等任務(wù)。圖神經(jīng)網(wǎng)絡(luò)（GNNs）作為一個(gè)成熟的框架，最近已被擴(kuò)展為超圖神經(jīng)網(wǎng)絡(luò)（HGNNs），其性質(zhì)與應(yīng)用正被積極研究。

多元生圖框架通過整合多值屬性以及隸屬度函數(shù)與矛盾函數(shù)，增強(qiáng)了圖的表示能力，從而實(shí)現(xiàn)了對(duì)復(fù)雜關(guān)系的精細(xì)建模。在處理不確定性方面，模糊圖與中性圖等概念已獲得廣泛關(guān)注。眾所周知，多元生圖是模糊圖與中性圖的泛化。此外，模糊圖神經(jīng)網(wǎng)絡(luò)已被提出，并成為一個(gè)活躍的研究領(lǐng)域。

本文建立了超級(jí)超圖神經(jīng)網(wǎng)絡(luò)（SHGNNs）與多元生圖神經(jīng)網(wǎng)絡(luò)的理論基礎(chǔ)，將神經(jīng)網(wǎng)絡(luò)的適用性擴(kuò)展至這些高級(jí)圖結(jié)構(gòu)。盡管本文提出了數(shù)學(xué)泛化與證明，但未來的計(jì)算實(shí)驗(yàn)仍有待開展。

關(guān)鍵詞：超圖，超級(jí)超圖，神經(jīng)網(wǎng)絡(luò)，中性圖，模糊圖 MSC2010（2010 年數(shù)學(xué)學(xué)科分類）：05C65 - 超圖，05C82 - 圖論及其應(yīng)用，03E72 - 模糊集理論

1 引言

1.1 超圖與超級(jí)超圖

圖論作為數(shù)學(xué)的一個(gè)關(guān)鍵領(lǐng)域，專注于理解由頂點(diǎn)（節(jié)點(diǎn)）和邊（連接）組成的網(wǎng)絡(luò) [100, 102]。這些數(shù)學(xué)結(jié)構(gòu)有效地建模了元素之間的關(guān)系、依賴性和轉(zhuǎn)換，使其成為跨各個(gè)領(lǐng)域的通用工具 [45, 58, 95, 156]。

圖論的基礎(chǔ)重要性推動(dòng)了其在眾多學(xué)科中的發(fā)展和應(yīng)用，包括：

? 計(jì)算科學(xué)：圖在電路設(shè)計(jì)和優(yōu)化計(jì)算工作流中至關(guān)重要，正如最近關(guān)于基于圖的優(yōu)化技術(shù)的研究中所強(qiáng)調(diào)的那樣 [40, 41, 405]。

? 化學(xué)和生物學(xué)：化學(xué)圖論對(duì)分子結(jié)構(gòu)和相互作用進(jìn)行建模 [42, 380]，而生物信息學(xué)利用圖來研究蛋白質(zhì)結(jié)構(gòu)和基因相互作用 [6, 373, 377]。

? 項(xiàng)目管理：圖被用于分析工作流和依賴關(guān)系，促進(jìn)項(xiàng)目管理框架中的高效資源分配和調(diào)度 [202, 296, 368]。

? 概率建模：貝葉斯網(wǎng)絡(luò)采用圖結(jié)構(gòu)來表示隨機(jī)變量之間的條件依賴性 [277, 418]。

? 圖數(shù)據(jù)庫：現(xiàn)代數(shù)據(jù)存儲(chǔ)和檢索系統(tǒng)越來越依賴圖數(shù)據(jù)庫，因?yàn)樗鼈兡軌蛴行Ы?fù)雜關(guān)系 [21, 22, 31, 141, 166, 261, 304]。

超圖是傳統(tǒng)圖的泛化，擴(kuò)展并抽象了圖論中的概念 [51,60,152,153,164]。超圖在機(jī)器學(xué)習(xí)、生物學(xué)、社會(huì)科學(xué)和圖數(shù)據(jù)庫分析等領(lǐng)域有著廣泛的應(yīng)用（例如，[69,85,139,187,232,403,427,443]）。從集合論的角度來看，超圖可以被視為其頂點(diǎn)集的冪集，而不會(huì)有誤解的風(fēng)險(xiǎn)。

超級(jí)超圖（SuperHyperGraph）的概念最近作為超圖的一種更一般的擴(kuò)展而出現(xiàn)，產(chǎn)生了類似于超圖研究中的實(shí)質(zhì)性研究興趣 [126,130,340]。在該領(lǐng)域已經(jīng)進(jìn)行了大量的研究 [122,126,128,130,170,171,340,341,343,346,351]。

超級(jí)超圖是超級(jí)超結(jié)構(gòu)（Superhyperstructure）的一種類型。它可以被視為應(yīng)用于圖的 n 次冪集（n-th-Power Set）[331] 概念的擴(kuò)展。超級(jí)超結(jié)構(gòu)和 n 次冪集的定義如下所示。

超級(jí)超結(jié)構(gòu)的其他例子包括超級(jí)超代數(shù) [197, 198, 212, 213, 221, 299, 300, 331, 342]、超級(jí)超拓?fù)?[348, 349, 358, 407, 422]、超級(jí)超函數(shù) [345, 350] 以及超級(jí)超軟集 [126, 127, 265, 347, 360]，所有這些在該領(lǐng)域都廣為人知。因此，從數(shù)學(xué)和實(shí)踐的角度來看，對(duì)超圖和超級(jí)超圖的研究都具有重要意義。作為參考，超級(jí)超圖之間的關(guān)系如圖 1 所示。

1.2 圖神經(jīng)網(wǎng)絡(luò)

本子節(jié)提供了圖神經(jīng)網(wǎng)絡(luò)的概述。近年來，機(jī)器學(xué)習(xí)（參見 [28, 186, 273, 304, 405, 419]）、人工智能（參見 [5, 34, 321, 374]）和大數(shù)據(jù)（參見 [49, 79, 200, 257]）等領(lǐng)域獲得了顯著的關(guān)注。本文專注于在這些領(lǐng)域中發(fā)揮關(guān)鍵作用的神經(jīng)網(wǎng)絡(luò)。

神經(jīng)網(wǎng)絡(luò)是一種受生物神經(jīng)系統(tǒng)啟發(fā)的計(jì)算模型，旨在用于模式識(shí)別、數(shù)據(jù)分類和預(yù)測(cè)等任務(wù) [20, 25, 46, 223, 393, 411, 412]。在此基礎(chǔ)上，圖神經(jīng)網(wǎng)絡(luò) (GNN) 將神經(jīng)網(wǎng)絡(luò)擴(kuò)展到圖結(jié)構(gòu)，使得能夠?qū)?jié)點(diǎn)、邊及其相關(guān)特征之間的關(guān)系進(jìn)行建模 [94, 205, 269, 297, 316, 324, 386, 404, 429, 440, 447]。

基于這一概念，超圖神經(jīng)網(wǎng)絡(luò) (HGNNs) 通過利用超邊來捕捉同時(shí)涉及多個(gè)節(jié)點(diǎn)的高階關(guān)系，從而擴(kuò)展了傳統(tǒng)的圖神經(jīng)網(wǎng)絡(luò) (GNNs) [70, 115, 181, 183, 204, 369, 401]。相關(guān)概念包括超網(wǎng)絡(luò) (Hypernetworks)，已在 [76, 167, 225, 363, 388] 等工作中得到廣泛研究。此外，基于有向圖的網(wǎng)絡(luò)，如有向圖神經(jīng)網(wǎng)絡(luò) [177–179, 325, 450]，以及基于混合圖結(jié)構(gòu)的網(wǎng)絡(luò)，如混合圖神經(jīng)網(wǎng)絡(luò) [163]，也廣為人知。

鑒于這些領(lǐng)域研究的廣泛應(yīng)用，對(duì)圖神經(jīng)網(wǎng)絡(luò)的研究至關(guān)重要。

1.3 不確定圖

模糊集的概念于 1965 年被引入 [430]。模糊集為解決現(xiàn)實(shí)世界中的不確定性提供了一個(gè)框架，并已應(yīng)用于包括圖論、代數(shù)、拓?fù)浜瓦壿嬙趦?nèi)的各個(gè)領(lǐng)域。此外，模糊集的擴(kuò)展，如中性集（neutrosophic sets）[332,334]，已被開發(fā)出來以處理甚至更復(fù)雜形式的不確定性。

這些處理不確定性的概念與實(shí)際應(yīng)用高度兼容 [47,208,235,263,270,278,322]。例如，中性集通過引入三個(gè)隸屬度——真（truth）、 indeterminacy（indeterminacy）和假（falsity）——來擴(kuò)展模糊集，使它們?cè)谛畔⒉煌暾驔_突的場(chǎng)景中特別有價(jià)值。應(yīng)用包括：

• 醫(yī)療決策（Healthcare Decision-Making）： 當(dāng)數(shù)據(jù)不完整或矛盾時(shí)，中性集通過平衡有效性（真）、不確定性（ indeterminacy）和風(fēng)險(xiǎn)（假）來協(xié)助評(píng)估治療方案 [29,196]。
• 社交網(wǎng)絡(luò)分析（Social Network Analysis）： 它們?cè)谏缃痪W(wǎng)絡(luò)中建模用戶之間的關(guān)系，如信任、懷疑和分歧 [108,253,309,382]。
• 工程故障診斷（Fault Diagnosis in Engineering）： 中性集通過考慮不確定和沖突的診斷證據(jù)來識(shí)別機(jī)械系統(tǒng)中的故障（參見 [155,226,326]）。
• 市場(chǎng)分析（Market Analysis）： 企業(yè)利用它們來分析客戶偏好，整合正面反饋（真）、模糊響應(yīng)（ indeterminacy）和負(fù)面反饋（假）[43,264,312]。

本文考察了各種不確定圖模型，包括模糊圖、直覺模糊圖、中性圖和多元生圖（Plithogenic Graphs）。這些模型通過引入不確定性程度擴(kuò)展了經(jīng)典圖論，從而能夠?qū)δ：蛷?fù)雜的關(guān)系進(jìn)行更細(xì)致的分析 [120,121,123–127,129,131,132]。

不確定圖模型的例子包括以下內(nèi)容：

• 模糊圖（Fuzzy Graph）： 模糊圖利用隸屬函數(shù)來表示頂點(diǎn)和邊中的不確定性，從而實(shí)現(xiàn)更靈活的關(guān)系建模 [8,10,12,274,306]。
• 中性圖（Neutrosophic Graph）： 中性圖通過為頂點(diǎn)和邊引入真、 indeterminacy 和假程度來擴(kuò)展模糊圖，提供更豐富的數(shù)據(jù)表示 [26,63,192,272,371,372,420]。眾所周知，中性圖可以泛化模糊圖。
• 多元生圖（Plithogenic Graph）： 多元生圖框架利用隸屬函數(shù)和矛盾函數(shù)對(duì)具有多值屬性的圖進(jìn)行建模，提供復(fù)雜關(guān)系的詳細(xì)表示 [121,338,357]。人們廣泛認(rèn)為多元生圖可以泛化中性圖。

這些概念，包括基于集合的方法，被應(yīng)用于決策 [18] 以及神經(jīng)網(wǎng)絡(luò) [24,112,113,416,442] 和機(jī)器學(xué)習(xí) [96,142,238,246] 中。這突顯了研究與不確定圖相關(guān)概念的重要性。

作為參考，不確定圖之間的關(guān)系如圖 2 所示（參見 [126]）。由于圖 2 是一個(gè)高度簡(jiǎn)化的圖表，鼓勵(lì)讀者如有需要參考文獻(xiàn)（如 [126]）以獲取更多細(xì)節(jié)。

1.4 我們的貢獻(xiàn)

本子節(jié)突出了我們工作的關(guān)鍵貢獻(xiàn)。雖然針對(duì)超圖的圖神經(jīng)網(wǎng)絡(luò)（GNNs）已被廣泛研究，但之前的研究尚未探索專為超級(jí)超圖量身定制的 GNNs 的開發(fā)。

在本文中，我們引入了超級(jí)超圖神經(jīng)網(wǎng)絡(luò)（SHGNN），這是超圖神經(jīng)網(wǎng)絡(luò)的數(shù)學(xué)擴(kuò)展，利用了超級(jí)超圖的獨(dú)特結(jié)構(gòu)屬性。此外，我們考察了不確定圖神經(jīng)模型，例如中性圖神經(jīng)網(wǎng)絡(luò)和多元生圖神經(jīng)網(wǎng)絡(luò)，它們解決了類似的挑戰(zhàn)。重要的是，我們證明了中性圖神經(jīng)網(wǎng)絡(luò)和多元生圖神經(jīng)網(wǎng)絡(luò)都作為模糊圖神經(jīng)網(wǎng)絡(luò)的數(shù)學(xué)泛化。 這項(xiàng)工作本質(zhì)上是理論性的，專注于建立 SHGNNs 和 PGNNs 的數(shù)學(xué)框架。它不包含計(jì)算實(shí)驗(yàn)或?qū)嶋H實(shí)現(xiàn)。因此，我們希望專家和讀者將來能進(jìn)行計(jì)算實(shí)驗(yàn)。對(duì)于精確的定義和詳細(xì)的符號(hào)，鼓勵(lì)讀者參考相關(guān)文獻(xiàn)，例如 [115]。

在本文中，我們對(duì)圖神經(jīng)網(wǎng)絡(luò)之間的關(guān)系進(jìn)行了理論考察，如圖 3 所示。該圖表說明箭頭起始處的概念被包含在（并被泛化為）箭頭指向處的概念。

雖然與前面討論的圖神經(jīng)網(wǎng)絡(luò)沒有直接關(guān)系，但本文還探討了超圖理論中的幾個(gè)擴(kuò)展概念，包括多級(jí) k 路超圖劃分、超級(jí)超圖隨機(jī)游走和超級(jí)超圖 Turán 問題。由于這些調(diào)查僅限于理論考慮，希望將來能根據(jù)需要開展計(jì)算實(shí)驗(yàn)和實(shí)際驗(yàn)證。

2 預(yù)備知識(shí)與定義

在本節(jié)中，我們簡(jiǎn)要概述了本文通篇使用的定義和符號(hào)。雖然我們力求使內(nèi)容對(duì)不同背景的讀者都具有可讀性，但無法全面涵蓋所有相關(guān)細(xì)節(jié)。鼓勵(lì)讀者根據(jù)需要參考所引用的文獻(xiàn)以獲取更多信息。

2.1 基本圖概念

本子節(jié)概述了基礎(chǔ)的圖概念。為了全面理解圖論和符號(hào)，請(qǐng)參考 [100–102, 158, 406]。此外，在討論圖論時(shí)，通常會(huì)使用基本的集合論概念。鼓勵(lì)讀者根據(jù)需要參考 [117, 182, 201, 389] 等文獻(xiàn)。

2.1 基本圖概念

本子節(jié)概述了基礎(chǔ)的圖概念。為了全面理解圖論和符號(hào)，請(qǐng)參考 [100–102, 158, 406]。此外，在討論圖論時(shí)，通常會(huì)使用基本的集合論概念。鼓勵(lì)讀者根據(jù)需要參考 [117, 182, 201, 389] 等文獻(xiàn)。

2.2 | 算法復(fù)雜性的基本定義

本子節(jié)介紹了用于分析后續(xù)部分中描述的算法的基本定義。

定義 2.7 (算法)。[320] 算法是逐步的、定義明確的程序或規(guī)則，用于解決問題或執(zhí)行任務(wù)，通常在計(jì)算中實(shí)現(xiàn)。

定義 2.8 (時(shí)間復(fù)雜性)。(參見 [283, 320]) 算法的時(shí)間復(fù)雜性是執(zhí)行它所需的計(jì)算時(shí)間總量，表示為輸入大小的函數(shù)。設(shè) T ( n , m )
表示大小為 n 和 m 的輸入的時(shí)間復(fù)雜性?？倳r(shí)間復(fù)雜性定義為：

2.3 | 基本圖神經(jīng)網(wǎng)絡(luò)概念

以下是圖神經(jīng)網(wǎng)絡(luò)（GNNs）的幾個(gè)定義。讀者可參考講義或引言以獲取更多細(xì)節(jié)（參見 [3, 94, 111, 205, 269, 297, 316, 324, 415, 440]）。

定義 2.11. (參見 [32,135,260]) 矩陣是一個(gè)矩形數(shù)組，由數(shù)字、符號(hào)或表達(dá)式組成，排列成行和列。形式上，一個(gè) m × n 矩陣 A 定義為：

例 2.22（圖卷積網(wǎng)絡(luò)）。設(shè)想一個(gè)社交網(wǎng)絡(luò)（參見 [319]），其中每個(gè)人（節(jié)點(diǎn)）都有一個(gè)屬性，例如他們對(duì)特定主題的興趣（例如，體育、音樂或技術(shù)）。節(jié)點(diǎn)之間的邊代表人與人之間的關(guān)系或友誼。每個(gè)人還有初始屬性（節(jié)點(diǎn)特征），例如代表他們對(duì)這些主題興趣的分?jǐn)?shù)。

GCN 的目標(biāo)是通過將他們自己的特征與來自他們朋友（相鄰節(jié)點(diǎn)）的信息相結(jié)合，來預(yù)測(cè)一個(gè)人的整體興趣概況。

通過堆疊這個(gè)過程的多個(gè)層，每個(gè)節(jié)點(diǎn)對(duì)其在圖中更廣泛的鄰域獲得更全面的理解。例如，在兩層之后，一個(gè)人的概況不僅反映他們直接朋友的興趣，還反映他們朋友的朋友的興趣。

這個(gè)過程使得 GCN 能夠有效地在圖結(jié)構(gòu)上學(xué)習(xí)和傳播信息，使它們成為節(jié)點(diǎn)分類、圖分類和鏈接預(yù)測(cè)等任務(wù)的強(qiáng)大工具。

2.4 超圖概念

超圖通過允許稱為超邊的邊連接任意數(shù)量的頂點(diǎn)，而不是僅限于成對(duì)連接，從而擴(kuò)展了傳統(tǒng)圖的概念 [51,140,152–154]。這種靈活性使得超圖在各個(gè)領(lǐng)域（如計(jì)算機(jī)科學(xué)和生物學(xué)）中對(duì)建模復(fù)雜關(guān)系非常有效 [114,148,195,294]。形式化定義如下所示。

2.5 | 超級(jí)超圖

超級(jí)超圖是一種高級(jí)結(jié)構(gòu)，通過允許頂點(diǎn)和邊成為集合來擴(kuò)展超圖。定義如下所示 [340, 341]。

2.7 | 不確定圖

模糊集的概念大約于半個(gè)世紀(jì)前被引入，推動(dòng)了旨在建模不確定性的各種圖論的發(fā)展 [430]。在本節(jié)中，我們概述了幾種框架的定義，包括模糊圖、直覺模糊圖、中性圖和單值五劃分中性圖。

模糊圖經(jīng)常在清晰圖的背景下進(jìn)行分析 [121]。為了提供基礎(chǔ)，我們首先給出清晰圖的定義 [121]。

我們提供了應(yīng)用于實(shí)際場(chǎng)景的模糊圖和中性圖的例子。這些例子證明了不確定圖以其能夠?qū)ΜF(xiàn)實(shí)世界中的各種現(xiàn)象進(jìn)行建模而聞名 [7, 18, 64, 160, 192, 329]。

例 2.38（模糊圖：具有不同友誼強(qiáng)度的社交網(wǎng)絡(luò)）。考慮一個(gè)社交網(wǎng)絡(luò)，其中個(gè)體根據(jù)他們的友誼進(jìn)行連接，且具有不同的強(qiáng)度（參見 [248, 252, 310, 402]）。這可以使用模糊圖來建模，其中頂點(diǎn)代表個(gè)體，邊代表具有不同強(qiáng)度程度的友誼。

愛麗絲在網(wǎng)絡(luò)中高度活躍，頻繁參與，而戴夫是最不活躍的。愛麗絲和鮑勃有著深厚的友誼，而卡羅爾和戴夫的連接較弱。 該模糊圖通過對(duì)關(guān)系強(qiáng)度和活動(dòng)水平的變化進(jìn)行建模，允許對(duì)社交網(wǎng)絡(luò)進(jìn)行細(xì)致的分析，有助于社區(qū)檢測(cè)或推薦系統(tǒng)等任務(wù)（參見 [71, 93, 409, 413]）。

例 2.39（中性圖：具有不確定性的疾病傳播網(wǎng)絡(luò)）。在流行病學(xué)中，了解疾病在人群中的傳播至關(guān)重要。中性圖可以對(duì)感染狀態(tài)和傳播概率中的不確定性進(jìn)行建模（參見 [4, 270, 328]）。

2.8 | 模糊圖神經(jīng)網(wǎng)絡(luò) (F-GNN)

在本子節(jié)中，我們介紹模糊圖神經(jīng)網(wǎng)絡(luò) (F-GNN) 的概念。模糊圖神經(jīng)網(wǎng)絡(luò) (F-GNN) 是一種圖推理模型，結(jié)合了模糊邏輯和圖神經(jīng)網(wǎng)絡(luò) (GNNs) 的原理。它專門設(shè)計(jì)用于處理圖結(jié)構(gòu)信息內(nèi)的模糊和不確定數(shù)據(jù)（參見 [78, 116, 162, 224, 295, 392, 439, 442]）。下面，我們展示 F-GNN 的形式化定義。

定義 2.43. [104] 一個(gè) F-GNN 被定義為一個(gè)五元組：

https://digitalrepository.unm.edu/cgi/viewcontent.cgi?params=/context/math_fsp/article/1945/&path_info=SuperHyperGraphNeuralNetworks.pdf