超圖之表示、信號處理、分割、學習及其應用

Hypergraph: Representation, Signal Processing, Partitioning, Learning and Its Applications

萬昱廷(Yu-Ting Wan)

指導教授 ： 貝蘇章

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2022年)

https://doi.org/10.6342/NTU202201027

摘要

在現代社會當中，在我們身邊的各種設備往往能夠產生大量的非結構性的資料，而從這些資料當中去萃取重要的資訊是一項重要而且有價值的課題。超圖是一種特殊的資料表示法。和圖相比，超圖中的每條超邊不只能夠連接兩個節點，因此相較於傳統的圖，超圖在資料的組織上更佳的彈性。除此之外，超圖可以有系統地將多模態的資料組織在一起，並且進行深層的資訊萃取。在本論文當中，會從圖開始介紹，再進一步推導超圖在代數上的表示方法及其性質。基於此並進一步地介紹超圖的各種學理：如超圖訊號處理、如何在超圖上做分割來進行分群、以及超圖機器學習。由於在高維度的超圖張量上求取基底需要花費大量的時間以及空間，這使得在大規模的超圖上做訊號處理的代價是高昂的，我們提出了稱為虛基底的方式以跳過評估張量基底。在最後展示這些學理如何應用來解決生活中所遇到的問題，如影像處理等應用。

關鍵字

圖 ； 圖論 ； 超圖 ； 超圖論 ； 分割 ； 信號處理 ； 機器學習 ； 應用

並列摘要

In modern society, various devices around us can generate a large amount of nonstructural data, and extracting information from these data is an important and valuable topic. Hypergraphs are a special kind of data representation. Compared to a graph, each hyperedge in a hypergraph can connect more than two nodes, so it is more flexible in data organization than a traditional graph. In addition, hypergraphs can systematically organize multi-modal data together and extract information. In this thesis, we will start with graphs and then further introduce the algebraic representation of hypergraphs and their properties. On the basis of these representations, various theories of hypergraphs are further introduced, such as hypergraph signal processing, segmentation on hypergraphs for grouping, and hypergraph machine learning. Since it takes a lot of time and space to obtain the bases on a high-dimensional hypergraph tensor, which makes it costly to do signal processing on large hypergraphs, we propose a method called pseudo bases to skip the evaluation of the tensor bases. Finally, it is shown how these theories can be applied to solve problems encountered in life, such as image processing applications.

並列關鍵字

graph ； graph theory ； hypergraph ； hypergraph theory ； partitioning ； signal processing ； machine learning ； application

參考文獻

[1] Yannan Chen, Liqun Qi, and Xiaoyan Zhang. The fiedler vector of a laplacian tensor for hypergraph partitioning. SIAM Journal on Scientific Computing, 39(6):A2508–A2537, 2017.

[2] Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. Slic superpixels, 2010.

[3] Stanford University. The stanford 3d scanning repository, 1994.

[4] Natasha Noy, Yuqing Gao, Anshu Jain, Anant Narayanan, Alan Patterson, and Jamie Taylor. Industry-scale knowledge graphs: Lessons and challenges. Communications of the ACM, 62 (8):36–43, 2019.

[5] Bernhard Schölkopf, John Platt, and Thomas Hofmann. Learning with Hypergraphs: Clustering, Classification, and Embedding, pages 1601–1608. 2007.