國立虎尾科技大學 |

High-Performance Spectral Algorithms for Hypergraph Compression.

紀錄類型:	書目-語言資料,手稿 : Monograph/item
正題名/作者:	High-Performance Spectral Algorithms for Hypergraph Compression./
作者:	Aghdaei, Ali.
面頁冊數:	1 online resource (90 pages)
附註:	Source: Dissertations Abstracts International, Volume: 84-11, Section: B.
Contained By:	Dissertations Abstracts International84-11B.
標題:	Computer engineering. -
電子資源:	click for full text (PQDT)
ISBN:	9798379565985

High-Performance Spectral Algorithms for Hypergraph Compression.
Aghdaei, Ali.

High-Performance Spectral Algorithms for Hypergraph Compression. - 1 online resource (90 pages)

Source: Dissertations Abstracts International, Volume: 84-11, Section: B.

Thesis (Ph.D.)--Stevens Institute of Technology, 2023.

Includes bibliographical references

The spectral theory has been extensively studied for compressing undirected graphs, including coarsening and sparsification. With the surge of multi-relational datasets, there is increasing pressure to use hypergraphs to capture higher-order relationships among entities within the network. However, spectral methods are less developed for hypergraphs due to the absence of a practical method for computing the hypergraph Laplacian matrix, the lack of a robust method for computing the eigenvalues/eigenvectors of a hypergraph, and the non-linear quadratic operator of hypergraphs. As a result, it is necessary to develop efficient spectral hypergraph algorithms to reduce hypergraph size while preserving spectral properties. This dissertation explores the leverage of the spectral theory to develop hyper/graph compression algorithms, utilizing nearly-linear time methods to identify less spectrally important hyper/edges. Our approach is effective in hypergraph coarsening, and maximum s-t flow computation in undirected graphs.The first part of this dissertation focuses on a scalable algorithmic framework for spectral coarsening of large-scale hypergraphs by exploiting hyperedge effective resistances. It aims at decomposing large hypergraphs into multiple node clusters with only a few inter-cluster hyperedges and incorporates the latest diffusion-based nonlinear quadratic operators defined on hypergraphs. The algorithm further improves the performance by leveraging a strongly-local max-flow-based clustering algorithm for detecting sets of hypergraph vertices that minimize ratio cut.The second part proposes a practically efficient algorithm for approximating maximum flows in large undirected graphs, based on the recent high-performance spectral graph algorithms. The proposed approach treats the undirected graph as a resistor network and exploits a resistor-network optimization framework that can be further accelerated by leveraging current nearly-linear-time graph Laplacian solvers.Extensive experiment results demonstrate the effectiveness and efficiency of these algorithms on real-world VLSI design benchmarks, social networks, and other public-domain network cases, and show significant improvement in runtime efficiency and multi-way conductance over existing state-of-the-art algorithms.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798379565985Subjects--Topical Terms:

569006
Computer engineering.
Subjects--Index Terms:

ClusteringIndex Terms--Genre/Form:

554714
Electronic books.

High-Performance Spectral Algorithms for Hypergraph Compression.
LDR:03636ntm a22003857 4500 001 1143595
005 20240517104607.5
006 m o d
007 cr mn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798379565985
035 $a (MiAaPQ)AAI30491506
035 $a AAI30491506
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Aghdaei, Ali. $3 1468328
245 1 0 $a High-Performance Spectral Algorithms for Hypergraph Compression.
264 0 $c 2023
300 $a 1 online resource (90 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 84-11, Section: B.
500 $a Advisor: Feng, Zhuo.
502 $a Thesis (Ph.D.)--Stevens Institute of Technology, 2023.
504 $a Includes bibliographical references
520 $a The spectral theory has been extensively studied for compressing undirected graphs, including coarsening and sparsification. With the surge of multi-relational datasets, there is increasing pressure to use hypergraphs to capture higher-order relationships among entities within the network. However, spectral methods are less developed for hypergraphs due to the absence of a practical method for computing the hypergraph Laplacian matrix, the lack of a robust method for computing the eigenvalues/eigenvectors of a hypergraph, and the non-linear quadratic operator of hypergraphs. As a result, it is necessary to develop efficient spectral hypergraph algorithms to reduce hypergraph size while preserving spectral properties. This dissertation explores the leverage of the spectral theory to develop hyper/graph compression algorithms, utilizing nearly-linear time methods to identify less spectrally important hyper/edges. Our approach is effective in hypergraph coarsening, and maximum s-t flow computation in undirected graphs.The first part of this dissertation focuses on a scalable algorithmic framework for spectral coarsening of large-scale hypergraphs by exploiting hyperedge effective resistances. It aims at decomposing large hypergraphs into multiple node clusters with only a few inter-cluster hyperedges and incorporates the latest diffusion-based nonlinear quadratic operators defined on hypergraphs. The algorithm further improves the performance by leveraging a strongly-local max-flow-based clustering algorithm for detecting sets of hypergraph vertices that minimize ratio cut.The second part proposes a practically efficient algorithm for approximating maximum flows in large undirected graphs, based on the recent high-performance spectral graph algorithms. The proposed approach treats the undirected graph as a resistor network and exploits a resistor-network optimization framework that can be further accelerated by leveraging current nearly-linear-time graph Laplacian solvers.Extensive experiment results demonstrate the effectiveness and efficiency of these algorithms on real-world VLSI design benchmarks, social networks, and other public-domain network cases, and show significant improvement in runtime efficiency and multi-way conductance over existing state-of-the-art algorithms.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Computer engineering. $3 569006
650 4 $a Electrical engineering. $3 596380
653 $a Clustering
653 $a Coarsening
653 $a Hypergraph
653 $a Maximum flow
653 $a Sparsification
655 7 $a Electronic books. $2 local $3 554714
690 $a 0544
690 $a 0464
710 2 $a Stevens Institute of Technology. $b Electrical Engineer. $3 1190572
710 2 $a ProQuest Information and Learning Co. $3 1178819
773 0 $t Dissertations Abstracts International $g 84-11B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30491506 $z click for full text (PQDT)