Inhomogeneous Hypergraph Clustering with Applications

Abstract

Hypergraph partitioning is an important problem in machine learning, computer vision and network analytics. A widely used method for hypergraph partitioning relies on minimizing a normalized sum of the costs of partitioning hyperedges across clusters. Algorithmic solutions based on this approach assume that different partitions of a hyperedge incur the same cost. However, this assumption fails to leverage the fact that different subsets of vertices within the same hyperedge may have different structural importance. We hence propose a new hypergraph clustering technique, termed inhomogeneous hypergraph partitioning, which assigns different costs to different hyperedge cuts. We prove that inhomogeneous partitioning produces a quadratic approximation to the optimal solution if the inhomogeneous costs satisfy submodularity constraints. Moreover, we demonstrate that inhomogenous partitioning offers significant performance improvements in applications such as structure learning of rankings, subspace segmentation and motif clustering.

To appear in NIPS 2017

References in corpus (6)

• Higher-order organization of complex networks
• Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
• Maximum Likelihood Estimation of Functionals of Discrete Distributions
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• On the Approximation of Submodular Functions
• Estimation of KL Divergence: Optimal Minimax Rate

Cited by in corpus (12)

• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks
• Mapping flows on hypergraphs
• Higher-Order Spectral Clustering under Superimposed Stochastic Block Model
• Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Local Hypergraph Clustering using Capacity Releasing Diffusion
• Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning
• Flow-based Community Detection in Hypergraphs
• Hypergraph Random Walks, Laplacians, and Clustering
• How Do Hyperedges Overlap in Real-World Hypergraphs? -- Patterns, Measures, and Generators
• Geometry of Similarity Comparisons
• Mixed-Order Spectral Clustering for Networks