超超图神经网络与多元生成图神经网络：理论基础|图神经网络|图论|算法|超图

第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 在网络中非常活跃，互动频繁，而 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] 向超图领域的扩展。相关概念的定义和定理如下所示。