張量超超圖和張量迭代線圖

張量超超圖和張量迭代線圖

Tensor SuperHyperGraph and Tensor Iterated Line Graph

https://www.techrxiv.org/users/868224/articles/1374006-tensor-superhypergraph-and-tensor-iterated-line-graph

摘要

超圖通過允許每條邊連接頂點集的任意非空子集，擴展了普通圖。通過將冪集構造再迭代一層，人們獲得嵌套（高階）頂點對象，從而得到有限超超圖，其頂點和邊本身可以是跨多層的集合值對象。線圖是一種變換，它將圖的每條邊替換為一個頂點，當且僅當原始圖中對應的邊共享一個公共端點時，連接兩個這樣的頂點。張量圖可以被視為一個多重網絡：公共頂點集上的圖的 r 元組，通過將其鄰接矩陣堆疊成一個單一的三階鄰接張量來編碼。在本文中，我們引入了張量超超圖的概念。利用線圖變換，我們進一步定義了張量線圖和張量迭代線圖，并研究了這些構造的基本性質。

關鍵詞：超超圖，超圖，張量超超圖，張量線圖，張量迭代線圖

1 預備知識

本節固定符號并回顧后續使用的基本對象。

1.1 超超圖

圖論研究由邊連接的頂點系統，強調數學、計算機科學和眾多應用中出現的連通性、結構性質和算法問題 [1]。超圖通過允許一條邊連接頂點集的任意非空子集來擴展普通圖，因此為真正的多路交互提供了自然的形式化方法 [2, 3]。這種更高元數的關系在現代學習流程中變得越來越重要，包括利用超圖結構的最近神經網絡架構 [3–7]。

如果進一步迭代冪集構造，那么頂點本身可以是嵌套的集合值對象。這導致了有限超超圖，其頂點集和邊集都可以存在于集合嵌套的多個“層級”上 [8, 9]。這些層級表示自然地出現在關系是分層的或多尺度的設置中，例如在分子設計、復雜網絡分析和神經網絡建模等應用中 [10–16]。相關的變體也已被研究，包括有向超超圖 [17, 18] 和元超超圖 [19]。

1.2 張量圖與張量超圖

張量圖是一種多重網絡：即共享頂點的 r 個圖構成的 r 元組，通過將它們的鄰接矩陣堆疊成一個張量來進行編碼 [26–28]。這一概念在神經網絡的背景下得到了積極研究，例如被稱為張量圖卷積網絡 [27, 29–31]。張量超圖通過一個對稱的 M 階鄰接張量來表示一個 M 階超圖，該張量編碼了頂點之間的多路超邊交互。在全文中，設 V 為一個有限頂點集，滿足 |V| = n，并且（在方便時）將 V 等同于 {1, ..., n}。對于整數 r ≥ 1，我們記 [r] := {1, ..., r} [32–36]。

作為參考，表 2 展示了圖、其線圖及其迭代線圖之間的比較。

雖然與本文的主要結果沒有直接關系，但附錄 A 討論并考察了迭代線圖的一個進一步推廣的概念。

2 主要結果

本節闡述本文的主要結果。

2.1 張量超超圖

我們現在將超超圖的嵌套頂點視角與超邊關聯的張量編碼相結合，本著與超圖的鄰接張量表示一致的精神。

作為參考，張量圖、張量超圖和張量超超圖的概覽見表 3。

下面給出一個具體的例子。

例 2.6（張量 n -超超圖的一個具體現實實例）。考慮大型制藥項目中的協作藥物發現。存在多個組織層級（個體研究人員、項目團隊、部門以及跨部門特別工作組），并且每個協作事件都在幾個并行的實驗條件下進行評估。張量 n -超超圖是這種情況的自然形式化，因為 (i) 頂點對象是嵌套的（團隊之團隊等），并且 (ii) 多路交互的強度/質量可以記錄為一個張量，其索引對應于測量軸。

3 附加結果：迭代張量線圖

張量線圖使用張量將線圖鄰接提升到超圖或高階結構，將邊關聯關系轉變為基于張量的連通性表示。迭代張量線圖重復應用張量線圖構造，產生連續的邊之邊張量鄰接，跟蹤跨迭代的高階交互傳播。我們形式化了經典線圖構造的一個張量裝飾變體。貫穿全文，所有圖均為有限簡單圖（無自環且無平行邊），除非另有說明。

張量標簽。 固定諸如以下的軸：

• 一天中的時段桶（早高峰、中午、晚高峰、夜間），
• 服務模式（普通/特快，工作日/周末），
• 指標（預期延誤、運力利用率、中斷風險、維護緊迫性）。

例如，條目可以表示歸一化的預期延遲、損壞概率、二氧化碳強度以及貨幣成本。

4 未來工作

我們預計未來的研究將探討基于模糊集 [49]、中性集 [50, 51] 和 plithogenic 集 [52, 53] 的擴展，以及它們在神經網絡等基于學習的方法中的應用。此外，我們注意到，基于元圖 [19, 54]、線超超圖 [47, 48]、超粗糙集 [55] 和粗糙集 [56] 等框架的進一步理論擴展與實證研究也有望被積極展開。

原文鏈接：https://www.techrxiv.org/users/868224/articles/1374006-tensor-superhypergraph-and-tensor-iterated-line-graph