keyword
hypergraph partitioning
Hypergraph partitioning is the process of dividing the vertices of a hypergraph, which generalizes standard graphs by allowing hyperedges to connect arbitrary subsets of two or more vertices simultaneously, into a set of disjoint parts. The goal is typically to minimize a cut objective, such as the number or total weight of hyperedges that span multiple parts, while satisfying balance constraints that ensure the parts remain relatively equal in size or weight. Because hyperedges directly capture multi-way and higher-order relationships rather than simple pairwise interactions, hypergraph partitioning is widely applied to solve complex optimization problems, including parallel computation and workload balancing, integrated circuit design, data clustering ensembles, and the analysis of complex networks.
3 items
Higher-order organization of complex networks
Austin R. Benson, David F. Gleich, Jure Leskovec
Why you should read this
Develops a scalable, mathematically rigorous framework for clustering complex networks based on higher-order subgraph patterns rather than simple edges, exposing functional modular structures in massive biological, neural, and transportation systems.
Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuroscience, engineering, and social science. Many networks are known to exhibit rich, lower-order connectivity patterns that can be captured at the level of individual nodes and edges. However, higher-order organization of complex networks---at the level of small network subgraphs---remains largely unknown. Here we develop a generalized framework for clustering networks based on higher-order connectivity patterns. This framework provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges. The framework reveals higher-order organization in a number of networks including information propagation units in neuronal networks and hub structure in transportation networks. Results show that networks exhibit rich higher-order organizational structures that are exposed by clustering based on higher-order connectivity patterns.
Added
2026-09-25
PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs
Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, Carlos Guestrin
Why you should read this
Introduces a distributed graph-parallel abstraction that factors computation over edges using the Gather-Apply-Scatter model and vertex-cut partitioning, overcoming the severe communication and storage bottlenecks caused by power-law degree distributions in real-world graphs.
Large-scale graph-structured computation is central to tasks ranging from targeted advertising to natural language processing and has led to the development of several graph-parallel abstractions including Pregel and GraphLab. However, the natural graphs commonly found in the real-world have highly skewed power-law degree distributions, which challenge the assumptions made by these abstractions, limiting performance and scalability. In this paper, we characterize the challenges of computation on natural graphs in the context of existing graph-parallel abstractions. We then introduce the PowerGraph abstraction which exploits the internal structure of graph programs to address these challenges. Leveraging the PowerGraph abstraction we introduce a new approach to distributed graph placement and representation that exploits the structure of power-law graphs. We provide a detailed analysis and experimental evaluation comparing PowerGraph to two popular graph-parallel systems. Finally, we describe three different implementation strategies for PowerGraph and discuss their relative merits with empirical evaluations on large-scale real-world problems demonstrating order of magnitude gains.
Added
2026-09-17
Cluster Ensembles – A Knowledge Reuse Framework for Combining Multiple Partitions
Alexander Strehl, Joydeep Ghosh
Why you should read this
Proposes a framework for cluster ensembles that combines multiple data partitions without accessing raw features, introducing three graph- and similarity-based consensus algorithms optimized through shared mutual information.
This paper introduces the problem of combining multiple partitionings of a set of objects into a single consolidated clustering without accessing the features or algorithms that determined these partitionings. We first identify several application scenarios for the resultant ‘knowledge reuse’ framework that we call cluster ensembles. The cluster ensemble problem is then formalized as a combinatorial optimization problem in terms of shared mutual information. In addition to a direct maximization approach, we propose three effective and efficient techniques for obtaining high-quality combiners (consensus functions). The first combiner induces a similarity measure from the partitionings and then reclusters the objects. The second combiner is based on hypergraph partitioning. The third one collapses groups of clusters into meta-clusters which then compete for each object to determine the combined clustering. Due to the low computational costs of our techniques, it is quite feasible to use a supra-consensus function that evaluates all three approaches against the objective function and picks the best solution for a given situation. We evaluate the effectiveness of cluster ensembles in three qualitatively different application scenarios: (i) where the original clusters were formed based on non-identical sets of features, (ii) where the original clustering algorithms worked on non-identical sets of objects, and (iii) where a common data-set is used and the main purpose of combining multiple clusterings is to improve the quality and robustness of the solution. Promising results are obtained in all three situations for synthetic as well as real data-sets.
Added
2026-09-10
