More Like this

1. Hypergraph Partitioning with Embeddings

   https://doi.org/10.1109/TKDE.2020.3017120  

   Sybrandt, Justin; Shaydulin, Ruslan; Safro, Ilya (December 2020, IEEE Transactions on Knowledge and Data Engineering)

   null (Ed.)

   HYPERGRAPHS provide the formalism needed to solve problems consisting of interconnected item sets. Similar to a traditional graph, the hypergraph has the added generalization that “hyperedges” may connect any number of nodes. Domains such as very-large-scale integration for creating integrated circuits [1], machine learning [2], [3], [4], parallel algorithms [5], combinatorial scientific computing [6], and social network analysis [7], [8] all contain significant and challenging instances of hypergraph problems. One important problem, Hypergraph partitioning, involves dividing the nodes of a hypergraph among k similarly-sized disjoint sets while reducing the number of hyperedges that span multiple partitions. In the context of load balancing, this is the problem of dividing logical threads (nodes) that share data dependencies (hyperedges) among available machines (partitions) in order to balance the number of threads per machine and minimize communication overhead. However, hypergraph partitioning is both NP-Hard to solve [9] and approximate [10]. 

   more » « less
2. HygHD: Hyperdimensional Hypergraph Learning

   https://doi.org/10.23919/DATE58400.2024.10546871  

   Kang, Jaeyoung; Lee, You Hak; Zhou, Minxuan; Xu, Weihong; Rosing, Tajana (March 2024, IEEE)
3. Hypergraph-Based Image Processing

   https://doi.org/10.1109/ICIP40778.2020.9190874  

   Zhang, Songyang; Cui, Shuguang; Ding, Zhi (October 2020, 2020 IEEE International Conference on Image Processing)

   null (Ed.)

   Learning and processing of signals over hypergraph models have gained substantial traction owing to the ability of hypergraphs in characterizing multilateral interactions. In this work, we explore hypergraph spectral analysis and provide alternative definitions of frequency domain operations that are practically useful in image processing. We analyze hypergraph spectral properties and present several application examples, including compression, edge detection and segmentation. Successful experiment results demonstrate the effectiveness and the future prospect of the proposed hypergraph frequency operations in image processing. 

   more » « less
4. Practical Parallel Hypergraph Algorithms

   https://doi.org/https://doi.org/10.1145/3332466.3374527  

   Shun, Julian (February 2020, ACM SIGPLAN Symposium Principals and Practice of Parallel Programming)

   While there has been significant work on parallel graph processing, there has been very surprisingly little work on high-performance hypergraph processing. This paper presents a collection of efficient parallel algorithms for hypergraph processing, including algorithms for betweenness centrality, maximal independent set, k-core decomposition, hypertrees, hyperpaths, connected components, PageRank, and single-source shortest paths. For these problems, we either provide new parallel algorithms or more efficient implementations than prior work. Furthermore, our algorithms are theoretically-efficient in terms of work and depth. To implement our algorithms, we extend the Ligra graph processing framework to support hypergraphs, and our implementations benefit from graph optimizations including switching between sparse and dense traversals based on the frontier size, edge-aware parallelization, using buckets to prioritize processing of vertices, and compression. Our experiments on a 72-core machine and show that our algorithms obtain excellent parallel speedups, and are significantly faster than algorithms in existing hypergraph processing frameworks. 

   more » « less
5. Spectral Hypergraph Partitioning Revisited

   Pramanik, Bodhisatta; Koutis, Ioannis (July 2021, SIAM Conference on Applied and Computational Discrete Algorithms)

   Most state-of-the-art hypergraph partitioning algorithms follow a multilevel approach that constructs a hierarchy of coarser hypergraphs that in turn is used to drive partition refinements. These partitioners are widely accepted as the current standard, as they have proven to be quite effective. On the other hand, spectral partitioners are considered to be less effective in cut quality, and too slow to be used in industrial applications. In this work, we revisit spectral hypergraph partitioning and we demonstrate that the use of appropriate solvers eliminates the running time deficiency; in fact, spectral algorithms can compute competing solutions in a fraction of the time needed by standard partitioning algorithms, especially on larger designs. We also introduce several novel modifications in the common spectral partitioning workflow, that enhance significantly the quality of the computed solutions. We run our partitioner on FPGA benchmarks generated by an industry leader, generating solutions that are directly competitive both in runtime and quality. 

   more » « less