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

Tensor SuperHyperGraph and Tensor Iterated Line Graph

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

摘要

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

關(guān)鍵詞：超超圖，超圖，張量超超圖，張量線圖，張量迭代線圖

1 預(yù)備知識

本節(jié)固定符號并回顧后續(xù)使用的基本對象。

1.1 超超圖

圖論研究由邊連接的頂點系統(tǒng)，強調(diào)數(shù)學(xué)、計算機科學(xué)和眾多應(yīng)用中出現(xiàn)的連通性、結(jié)構(gòu)性質(zhì)和算法問題 [1]。超圖通過允許一條邊連接頂點集的任意非空子集來擴展普通圖，因此為真正的多路交互提供了自然的形式化方法 [2, 3]。這種更高元數(shù)的關(guān)系在現(xiàn)代學(xué)習(xí)流程中變得越來越重要，包括利用超圖結(jié)構(gòu)的最近神經(jīng)網(wǎng)絡(luò)架構(gòu) [3–7]。

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

1.2 張量圖與張量超圖

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

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

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

2 主要結(jié)果

本節(jié)闡述本文的主要結(jié)果。

2.1 張量超超圖

我們現(xiàn)在將超超圖的嵌套頂點視角與超邊關(guān)聯(lián)的張量編碼相結(jié)合，本著與超圖的鄰接張量表示一致的精神。

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

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

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

3 附加結(jié)果：迭代張量線圖

張量線圖使用張量將線圖鄰接提升到超圖或高階結(jié)構(gòu)，將邊關(guān)聯(lián)關(guān)系轉(zhuǎn)變?yōu)榛趶埩康倪B通性表示。迭代張量線圖重復(fù)應(yīng)用張量線圖構(gòu)造，產(chǎn)生連續(xù)的邊之邊張量鄰接，跟蹤跨迭代的高階交互傳播。我們形式化了經(jīng)典線圖構(gòu)造的一個張量裝飾變體。貫穿全文，所有圖均為有限簡單圖（無自環(huán)且無平行邊），除非另有說明。

張量標(biāo)簽。 固定諸如以下的軸：

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

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

4 未來工作

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

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