超超圖神經網絡與多元生成圖神經網絡：理論基礎

第17章 超超圖神經網絡與多元生成圖神經網絡：理論基礎

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

摘要：

超圖通過允許邊連接多個節點擴展了傳統圖，而超超圖進一步推廣了這一概念以表示甚至更復雜的關系。神經網絡受生物系統啟發，廣泛用于模式識別、數據分類和預測等任務。

圖神經網絡（GNNs）是一個成熟的框架，最近已被擴展到超圖神經網絡（HGNNs），其性質和應用正在被積極研究。多元生成圖框架通過整合多值屬性以及隸屬度和矛盾函數來增強圖表示，從而實現對復雜關系的詳細建模。

在處理不確定性的背景下，模糊圖和中智圖等概念已變得突出。已充分確立的是，多元生成圖作為模糊圖和中智圖的推廣。此外，模糊圖神經網絡已被提出，并且是一個活躍的研究領域。

本文建立了超超圖神經網絡（SHGNNs）和多元生成圖神經網絡發展的理論基礎，將神經網絡的適用性擴展到這些高級圖結構。雖然提出了數學推廣和證明，但期待未來的計算實驗。

關鍵詞：超圖，超超圖，神經網絡，中智圖，模糊圖

1 引言

1.1 超圖與超超圖

圖論是數學的一個關鍵領域，專注于理解由頂點（節點）和邊（連接）組成的網絡 [100, 102]。這些數學結構有效地對元素之間的關系、依賴性和轉換進行建模，使它們成為各個領域的通用工具 [45, 58, 95, 156]。

圖論的基礎重要性激發了其在眾多學科中的發展和應用，包括：

• 計算科學：圖在設計電路和優化計算工作流方面至關重要，正如最近關于基于圖的優化技術的研究中所強調的那樣 [40, 41, 405]。
• 化學與生物學：化學圖論對分子結構和相互作用進行建模 [42, 380]，而生物信息學利用圖來研究蛋白質結構和基因相互作用 [6, 373, 377]。
• 項目管理：圖被用于分析工作流和依賴關系，促進項目管理框架中的高效資源分配和調度 [202, 296, 368]。
• 概率建模：貝葉斯網絡采用圖結構來表示隨機變量之間的條件依賴 [277, 418]。
• 圖數據庫：現代數據存儲和檢索系統越來越依賴于圖數據庫，因為它們能夠有效地對復雜關系進行建模 [21, 22, 31, 141, 166, 261, 304]。

超圖是傳統圖的推廣，擴展并抽象了圖論中的概念 [51, 60, 152, 153, 164]。超圖在機器學習、生物學、社會科學和圖數據庫分析等各個領域有著廣泛的應用（例如，[69, 85, 139, 187, 232, 403, 427, 443]）。從集合論的角度來看，超圖可以毫無誤解地被視為其頂點集的冪集。

超超圖（SuperHyperGraph）的概念最近作為一種更一般的超圖擴展而出現，產生了與超圖研究類似的實質性研究興趣 [126, 130, 340]。在該領域已經進行了大量的研究 [122, 126, 128, 130, 170, 171, 340, 341, 343, 346, 351]。

超超圖是一種超超結構（Superhyperstructure）。它可以被視為應用于圖的 n n 次冪集（ n n-th-Power Set）概念的擴展 [331]。超超結構和 n n 次冪集的定義如下所述。

超超結構的其他例子包括超超代數（Superhyperalgebras）[197, 198, 212, 213, 221, 299, 300, 331, 342]、超超拓撲（Superhypertopology）[348, 349, 358, 407, 422]、超超函數（Superhyperfunctions）[345, 350] 和超超軟集（Superhypersoft sets）[126, 127, 265, 347, 360]，這些在該領域都是眾所周知的。因此，從數學和實踐角度來看，超圖和超超圖的研究都具有重要意義。

作為參考，超超圖之間的關系如圖 1 所示。

1.2 圖神經網絡

本小節概述圖神經網絡。近年來，機器學習（參見 [28, 186, 273, 304, 405, 419]）、人工智能（參見 [5, 34, 321, 374]）和大數據（參見 [49, 79, 200, 257]）等領域已獲得顯著的重要性。本文專注于在這些領域中發揮關鍵作用的神經網絡。

神經網絡是一種受生物神經系統啟發的計算模型，設計用于模式識別、數據分類和預測等任務 [20, 25, 46, 223, 393, 411, 412]。在此基礎上，圖神經網絡（GNN）將神經網絡擴展到圖結構，使得能夠對節點、邊及其相關特征之間的關系進行建模 [94, 205, 269, 297, 316, 324, 386, 404, 429, 440, 447]。

基于這一概念，超圖神經網絡（HGNNs）通過利用超邊來捕捉同時涉及多個節點的高階關系，從而擴展了傳統圖神經網絡（GNNs）[70, 115, 181, 183, 204, 369, 401]。相關概念包括超網絡（Hypernetworks），已在 [76, 167, 225, 363, 388] 等著作中得到廣泛研究。此外，基于有向圖的網絡，如有向圖神經網絡（Directed Graph Neural Networks）[177–179, 325, 450]，以及基于混合圖結構的網絡，如混合圖神經網絡（Mixed Graph Neural Networks）[163]，也是眾所周知的。

鑒于這些領域研究的廣泛應用，圖神經網絡的研究至關重要。

1.3 不確定圖

模糊集（fuzzy sets）的概念于 1965 年引入 [430]。模糊集為解決現實世界中的不確定性提供了一個框架，并已應用于包括圖論、代數、拓撲和邏輯在內的各個領域。此外，為了處理甚至更復雜形式的不確定性，人們開發了模糊集的擴展，例如中智集（neutrosophic sets）[332, 334]。

這些處理不確定性的概念與現實世界的應用高度兼容 [47, 208, 235, 263, 270, 278, 322]。例如，中智集通過引入三個隸屬度——真（truth）、 indeterminacy（indeterminacy）和假（falsity）——擴展了模糊集，這使得它們在信息不完整或相互沖突的場景中特別有價值。應用包括：

• 醫療決策（Healthcare Decision-Making）： 當數據不完整或相互矛盾時，中智集通過平衡有效性（真）、不確定性（ indeterminacy）和風險（假）來協助評估治療方案 [29, 196]。
• 社交網絡分析（Social Network Analysis）： 它們在社交網絡中對用戶之間的關系（如信任、懷疑和分歧）進行建模 [108, 253, 309, 382]。
• 工程故障診斷（Fault Diagnosis in Engineering）： 中智集通過考慮不確定和沖突的診斷證據來識別機械系統中的故障（參見 [155, 226, 326]）。
• 市場分析（Market Analysis）： 企業利用它們來分析客戶偏好，整合正面反饋（真）、模棱兩可的回應（ indeterminacy）和負面反饋（假）[43, 264, 312]。

本文考察了各種不確定圖模型，包括模糊圖、直覺模糊圖、中智圖和多元生成圖。這些模型通過結合不確定性程度擴展了經典圖論，從而能夠對模糊和復雜的關系進行更細致的分析 [120, 121, 123–127, 129, 131, 132]。

不確定圖模型的例子包括以下內容：

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

這些概念，包括基于集合的方法，被應用于決策 [18] 以及神經網絡 [24, 112, 113, 416, 442] 和機器學習 [96, 142, 238, 246] 中。這突顯了研究與不確定圖相關概念的重要性。

作為參考，不確定圖之間的關系如圖 2 所示（參見 [126]）。由于圖 2 是一個高度簡化的圖表，鼓勵讀者在必要時參考文獻（如 [126]）以獲取更多細節。

1.4 我們的貢獻

本小節強調了我們工作的關鍵貢獻。雖然針對超圖的圖神經網絡（GNNs）已被廣泛研究，但尚無先前的研究探討針對超超圖（SuperHyperGraphs）的 GNN 開發。

在本文中，我們引入了超超圖神經網絡（SHGNN），這是超圖神經網絡的數學擴展，利用了超超圖獨特的結構性質。此外，我們考察了不確定圖神經模型，如中智圖神經網絡和多元生成圖神經網絡，它們解決了類似的挑戰。重要的是，我們要證明中智圖神經網絡和多元生成圖神經網絡都作為模糊圖神經網絡的數學推廣。

這項工作本質上是理論性的，專注于建立 SHGNN 和 PGNN 的數學框架。它不包括計算實驗或實際實現。因此，我們希望未來的計算實驗將由專家和讀者共同進行。為了精確的定義和詳細的符號，鼓勵讀者查閱相關文獻，如 [115]。

在本文中，我們對圖神經網絡之間的關系進行了理論考察，如圖 3 所示。該圖表說明箭頭起點的概念被包含在（并被推廣為）箭頭終點的概念中。

雖然與前面討論的圖神經網絡沒有直接關系，但本文還探討了超圖理論中的幾個擴展概念，包括多級 k-路超圖劃分（Multilevel k-way Hypergraph Partitioning）、超超圖隨機游走（Superhypergraph Random Walk）和超超圖 Turán 問題（Superhypergraph Turán Problem）。由于這些研究僅限于理論考慮，希望未來在需要時進行計算實驗和實際驗證。

2 預備知識與定義

在本節中，我們簡要概述了全文使用的定義和符號。雖然我們要使內容對各種背景的讀者都可訪問，但不可能全面涵蓋所有相關細節。鼓勵讀者在需要時查閱參考文獻以獲取更多信息。

2.1 基礎圖概念

本小節概述了基礎圖論概念。為了全面理解圖論和符號，請參閱 [100–102, 158, 406]。此外，在討論圖論時，經常使用基本集合論概念。鼓勵讀者根據需要查閱參考文獻，如 [117, 182, 201, 389]。

2.2 算法復雜度的基本定義

本小節介紹了用于分析后續章節所述算法的基本定義。

定義 2.7（算法）。 [320] 算法是解決問題或執行任務的逐步、明確定義的過程或規則，通常在計算中實現。

定義 2.8（時間復雜度）。 （參見 [283, 320]）算法的時間復雜度是執行它所需的總計算時間，表示為輸入大小的函數。設表示大小為 n n 和 m m 的輸入的時間復雜度。總時間復雜度定義為：

2.3 基礎圖神經網絡概念

以下是圖神經網絡（GNNs）的幾個定義。讀者可以參考講義或引言以獲取更多細節（參見 [3,94,111,205,269,297,316,324,415,440]）。

當圖的大小發生變化時，該函數特別有用，因為它保留了特征的總幅度。定義 2.20（通用框架）。（參見 [449, 453]）第 層所有節點的節點更新規則可以用矩陣形式表示：

例 2.22（圖卷積網絡）。 想象一個社交網絡（參見 [319]），其中每個人（節點）都有一個屬性，例如他們對特定主題（例如，體育、音樂或技術）的興趣。節點之間的邊代表人與人之間的關系或友誼。每個人還有初始屬性（節點特征），例如代表他們對這些主題興趣的分數。

GCN 的目標是通過結合一個人自身的特征與其朋友（鄰居節點）的信息來預測這個人的整體興趣畫像。

在 GCN 的每一層：

通過堆疊多層此過程，每個節點對其在圖中更廣泛的鄰域有了更全面的了解。例如，經過兩層后，一個人的畫像不僅反映了其直接朋友的興趣，還反映了其朋友的朋友的興趣。

這個過程允許 GCN 在圖結構上有效地學習和傳播信息，使它們成為節點分類、圖分類和鏈接預測等任務的強大工具。

2.4 超圖概念

超圖通過允許邊（稱為超邊）連接任意數量的頂點，從而擴展了傳統圖的概念，而不是局限于成對連接 [51, 140, 152–154]。這種靈活性使得超圖在計算機科學和生物學等各個領域中對于建模復雜關系非常有效 [114, 148, 195, 294]。形式化定義如下。

2.6 HGNN：超圖神經網絡

超圖神經網絡是一個旨在更高層次利用通用圖神經網絡的概念，并且它已經在眾多的框架和概念中得到了廣泛的研究[115, 229, 231, 236, 239, 239, 244, 410, 425, 426]。定義如下所示。

超圖神經網絡 (HGNN) 是一個專為超圖上的表示學習設計的神經網絡框架。它利用超圖結構通過超邊聚合來自頂點及其連接的特征。HGNN 的關鍵組件定義如下：

2.7 不確定圖 (Uncertain Graph)

大約半個世紀前引入的模糊集（Fuzzy Set）概念，激發了旨在對不確定性進行建模的各種圖論的發展[430]。在本節中，我們概述了幾種框架的定義，包括模糊圖（Fuzzy Graphs）、直覺模糊圖（Intuitionistic Fuzzy Graphs）、中性圖（Neutrosophic Graphs）和單值五劃分中性圖（Single-Valued Pentapartitioned Neutrosophic Graphs）。

模糊圖經常在清晰圖（Crisp Graph）[121]的背景下進行分析。為了提供基礎，我們首先給出清晰圖[121]的定義。

接下來，我們介紹模糊圖、直覺模糊圖、中性圖、猶豫模糊圖（Hesitant Fuzzy Graph）、四劃分中性圖（QNG）和單值五劃分中性圖的概念。如果需要更詳細的信息，鼓勵讀者參考綜述論文（例如，[121, 123]）。

我們提供了應用于現實場景的模糊圖（Fuzzy Graphs）和中性圖（Neutrosophic Graphs）的示例。這些示例展示了不確定圖（Uncertain Graphs）如何以其對現實世界中各種現象進行建模的能力而聞名[7,18,64,160,192,329]。

例 2.38（模糊圖：具有不同友誼強度的社交網絡）。考慮一個社交網絡，其中個體基于他們的友誼相互連接，且友誼強度各不相同（參見[248,252,310,402]）。這可以使用模糊圖來建模，其中頂點代表個體，邊代表具有不同強度等級的友誼。

Alice 在網絡中非?；钴S，互動頻繁，而 Dave 的活躍度最低。Alice 和 Bob 擁有深厚的友誼，而 Carol 和 Dave 之間的聯系很微弱。

這個模糊圖通過對關系強度和活躍水平的不同強度進行建模，實現了對社交網絡的細致分析，有助于社區發現或推薦系統等任務（參見[71, 93, 409, 413]）。

例 2.39（中性圖：具有不確定性的疾病傳播網絡）。在流行病學中，了解疾病在人群中的傳播至關重要。中性圖可以對感染狀態和傳播概率中的不確定性進行建模（參見[4, 270, 328]）。

病人1極有可能被感染，并可能將疾病傳播給病人2。病人2和病人3之間的傳播是不確定的。病人4極不可能被感染，且被他人傳播的幾率很低。

中性圖有助于對不確定的感染和傳播動態進行建模，從而支持接觸者追蹤、資源分配和風險評估等工作。

命題 2.40. 中性圖可以推廣模糊圖。

2.8 模糊圖神經網絡 (F-GNN)

在本小節中，我們介紹模糊圖神經網絡（F-GNN）的概念。模糊圖神經網絡（F-GNN）是一種圖推理模型，它結合了模糊邏輯和圖神經網絡（GNNs）的原理。它專門設計用于處理圖結構信息中的模糊和不確定數據（參見[78, 116, 162, 224, 295, 392, 439, 442]）。下面，我們給出 F-GNN 的形式化定義。

3 結果：超超圖神經網絡

在本節中，我們探討超超圖神經網絡。

3.1 超超圖神經網絡

在本小節中，我們探討超超圖神經網絡的定義和理論框架。這一概念是超圖神經網絡的數學擴展。需要注意的是，本研究純屬理論性質，未在實際系統上進行實際實現或測試。

3.2 超超圖神經網絡 (SHGNN) 的算法

我們提出了一個用于實現超超圖神經網絡 (SHGNN) 的詳細算法，并附帶對其時間復雜度和空間復雜度的分析。該算法描述如下。

3.4 動態超超圖神經網絡

在本小節中，我們在動態超圖神經網絡 [204] 的概念基礎上，定義動態超超圖神經網絡。動態超圖神經網絡對超圖內不斷演變的關系進行建模，通過從時變的節點和超邊交互中學習，以促進動態數據分析（參見 [172, 210, 240, 395, 400, 454]）。動態超圖神經網絡也可以被視為動態圖神經網絡 [118, 159, 237, 361] 向超圖領域的擴展。相關概念的定義和定理如下所示。

我們提出了基于當前特征嵌入在每一層動態構建超超圖的算法。

3.5 多圖神經網絡及其推廣

多圖神經網絡在近年來已被提出[421]。然而，我們證明了它們可以在 n n-超超圖神經網絡的框架內被數學推廣。下面，我們給出相關的定義和定理，包括相關概念。

。。。。。。。

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