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

Tensor SuperHyperGraph and Tensor Iterated Line Graph

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

摘要

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

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

1 預(yù)備知識(shí)

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

1.1 超超圖

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

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

1.2 張量圖與張量超圖

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

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

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

2 主要結(jié)果

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

2.1 張量超超圖

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

作為參考，張量圖、張量超圖和張量超超圖的概覽見(jiàn)表 3。

下面給出一個(gè)具體的例子。

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

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)造的一個(gè)張量裝飾變體。貫穿全文，所有圖均為有限簡(jiǎn)單圖（無(wú)自環(huán)且無(wú)平行邊），除非另有說(shuō)明。

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

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

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

4 未來(lái)工作

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

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