超级超图神经网络与多元生图神经网络：理论基础

超级超图神经网络与多元生图神经网络：理论基础

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 章 超级超图神经网络与多元生图神经网络：理论基础

摘要：

超图通过允许边连接多个节点来扩展传统图，而超级超图则进一步泛化这一概念，以表示更复杂的关系。

神经网络受生物系统启发，广泛用于模式识别、数据分类和预测等任务。图神经网络（GNNs）作为一个成熟的框架，最近已被扩展为超图神经网络（HGNNs），其性质与应用正被积极研究。

多元生图框架通过整合多值属性以及隶属度函数与矛盾函数，增强了图的表示能力，从而实现了对复杂关系的精细建模。在处理不确定性方面，模糊图与中性图等概念已获得广泛关注。众所周知，多元生图是模糊图与中性图的泛化。此外，模糊图神经网络已被提出，并成为一个活跃的研究领域。

本文建立了超级超图神经网络（SHGNNs）与多元生图神经网络的理论基础，将神经网络的适用性扩展至这些高级图结构。尽管本文提出了数学泛化与证明，但未来的计算实验仍有待开展。

关键词：超图，超级超图，神经网络，中性图，模糊图 MSC2010（2010 年数学学科分类）：05C65 - 超图，05C82 - 图论及其应用，03E72 - 模糊集理论

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-th-Power Set）[331] 概念的扩展。超级超结构和 n 次幂集的定义如下所示。

超级超结构的其他例子包括超级超代数 [197, 198, 212, 213, 221, 299, 300, 331, 342]、超级超拓扑 [348, 349, 358, 407, 422]、超级超函数 [345, 350] 以及超级超软集 [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] 等工作中得到广泛研究。此外，基于有向图的网络，如有向图神经网络 [177–179, 325, 450]，以及基于混合图结构的网络，如混合图神经网络 [163]，也广为人知。

鉴于这些领域研究的广泛应用，对图神经网络的研究至关重要。

1.3 不确定图

模糊集的概念于 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]。

本文考察了各种不确定图模型，包括模糊图、直觉模糊图、中性图和多元生图（Plithogenic Graphs）。这些模型通过引入不确定性程度扩展了经典图论，从而能够对模糊和复杂的关系进行更细致的分析 [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）已被广泛研究，但之前的研究尚未探索专为超级超图量身定制的 GNNs 的开发。

在本文中，我们引入了超级超图神经网络（SHGNN），这是超图神经网络的数学扩展，利用了超级超图的独特结构属性。此外，我们考察了不确定图神经模型，例如中性图神经网络和多元生图神经网络，它们解决了类似的挑战。重要的是，我们证明了中性图神经网络和多元生图神经网络都作为模糊图神经网络的数学泛化。 这项工作本质上是理论性的，专注于建立 SHGNNs 和 PGNNs 的数学框架。它不包含计算实验或实际实现。因此，我们希望专家和读者将来能进行计算实验。对于精确的定义和详细的符号，鼓励读者参考相关文献，例如 [115]。

在本文中，我们对图神经网络之间的关系进行了理论考察，如图 3 所示。该图表说明箭头起始处的概念被包含在（并被泛化为）箭头指向处的概念。

虽然与前面讨论的图神经网络没有直接关系，但本文还探讨了超图理论中的几个扩展概念，包括多级 k 路超图划分、超级超图随机游走和超级超图 Turán 问题。由于这些调查仅限于理论考虑，希望将来能根据需要开展计算实验和实际验证。

2 预备知识与定义

在本节中，我们简要概述了本文通篇使用的定义和符号。虽然我们力求使内容对不同背景的读者都具有可读性，但无法全面涵盖所有相关细节。鼓励读者根据需要参考所引用的文献以获取更多信息。

2.1 基本图概念

本子节概述了基础的图概念。为了全面理解图论和符号，请参考 [100–102, 158, 406]。此外，在讨论图论时，通常会使用基本的集合论概念。鼓励读者根据需要参考 [117, 182, 201, 389] 等文献。

2.1 基本图概念

本子节概述了基础的图概念。为了全面理解图论和符号，请参考 [100–102, 158, 406]。此外，在讨论图论时，通常会使用基本的集合论概念。鼓励读者根据需要参考 [117, 182, 201, 389] 等文献。

2.2 | 算法复杂性的基本定义

本子节介绍了用于分析后续部分中描述的算法的基本定义。

定义 2.7 (算法)。[320] 算法是逐步的、定义明确的程序或规则，用于解决问题或执行任务，通常在计算中实现。

定义 2.8 (时间复杂性)。(参见 [283, 320]) 算法的时间复杂性是执行它所需的计算时间总量，表示为输入大小的函数。设 T ( n , m )
表示大小为 n 和 m 的输入的时间复杂性。总时间复杂性定义为：

2.3 | 基本图神经网络概念

以下是图神经网络（GNNs）的几个定义。读者可参考讲义或引言以获取更多细节（参见 [3, 94, 111, 205, 269, 297, 316, 324, 415, 440]）。

定义 2.11. (参见 [32,135,260]) 矩阵是一个矩形数组，由数字、符号或表达式组成，排列成行和列。形式上，一个 m × n 矩阵 A 定义为：

例 2.22（图卷积网络）。设想一个社交网络（参见 [319]），其中每个人（节点）都有一个属性，例如他们对特定主题的兴趣（例如，体育、音乐或技术）。节点之间的边代表人与人之间的关系或友谊。每个人还有初始属性（节点特征），例如代表他们对这些主题兴趣的分数。

GCN 的目标是通过将他们自己的特征与来自他们朋友（相邻节点）的信息相结合，来预测一个人的整体兴趣概况。

通过堆叠这个过程的多个层，每个节点对其在图中更广泛的邻域获得更全面的理解。例如，在两层之后，一个人的概况不仅反映他们直接朋友的兴趣，还反映他们朋友的朋友的兴趣。

这个过程使得 GCN 能够有效地在图结构上学习和传播信息，使它们成为节点分类、图分类和链接预测等任务的强大工具。

2.4 超图概念

超图通过允许称为超边的边连接任意数量的顶点，而不是仅限于成对连接，从而扩展了传统图的概念 [51,140,152–154]。这种灵活性使得超图在各个领域（如计算机科学和生物学）中对建模复杂关系非常有效 [114,148,195,294]。形式化定义如下所示。

2.5 | 超级超图

超级超图是一种高级结构，通过允许顶点和边成为集合来扩展超图。定义如下所示 [340, 341]。

2.7 | 不确定图

模糊集的概念大约于半个世纪前被引入，推动了旨在建模不确定性的各种图论的发展 [430]。在本节中，我们概述了几种框架的定义，包括模糊图、直觉模糊图、中性图和单值五划分中性图。

模糊图经常在清晰图的背景下进行分析 [121]。为了提供基础，我们首先给出清晰图的定义 [121]。

我们提供了应用于实际场景的模糊图和中性图的例子。这些例子证明了不确定图以其能够对现实世界中的各种现象进行建模而闻名 [7, 18, 64, 160, 192, 329]。

例 2.38（模糊图：具有不同友谊强度的社交网络）。考虑一个社交网络，其中个体根据他们的友谊进行连接，且具有不同的强度（参见 [248, 252, 310, 402]）。这可以使用模糊图来建模，其中顶点代表个体，边代表具有不同强度程度的友谊。

爱丽丝在网络中高度活跃，频繁参与，而戴夫是最不活跃的。爱丽丝和鲍勃有着深厚的友谊，而卡罗尔和戴夫的连接较弱。 该模糊图通过对关系强度和活动水平的变化进行建模，允许对社交网络进行细致的分析，有助于社区检测或推荐系统等任务（参见 [71, 93, 409, 413]）。

例 2.39（中性图：具有不确定性的疾病传播网络）。在流行病学中，了解疾病在人群中的传播至关重要。中性图可以对感染状态和传播概率中的不确定性进行建模（参见 [4, 270, 328]）。

2.8 | 模糊图神经网络 (F-GNN)

在本子节中，我们介绍模糊图神经网络 (F-GNN) 的概念。模糊图神经网络 (F-GNN) 是一种图推理模型，结合了模糊逻辑和图神经网络 (GNNs) 的原理。它专门设计用于处理图结构信息内的模糊和不确定数据（参见 [78, 116, 162, 224, 295, 392, 439, 442]）。下面，我们展示 F-GNN 的形式化定义。

定义 2.43. [104] 一个 F-GNN 被定义为一个五元组：

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