Hypergraph Sparsification and Its Application to Partitioning

Abstract—The data one needs to cope to solve today’s problems is large scale, so are the graphs and hypergraphs used to model it. Today, we have BigData, big graphs, big matrices, and in the future, they are expected to be bigger and more complex. Many of today’s algorithms will be, and some already are, expensive to run on large datasets. In this work, we analyze a set of efficient techniques to make “big data”, which is modeled as a hypergraph, smaller so that its processing takes much less time. As an application use case, we take the hypergraph partitioning problem, which has been successfully used in many practical applications for various purposes including parallelization of complex and irregular applications, sparse matrix ordering, clustering, community detection, query optimization, and improving cache locality in shared-memory systems. We conduct several experiments to show that our techniques greatly reduce the cost of the parti-tioning process and preserve the partitioning quality. Although we only measured their performance from the partitioning point of view, we believe the proposed techniques will be beneficial also for other applications using hypergraphs. Keywords-Hypergraph sparsification; hypergraph partition-ing; multi-level approach; identical nets; identical vertices; Jaccard similarity. I