# Inhomogeneous Hypergraph Clustering with Applications

arXiv: https://arxiv.org/abs/1709.01249 · HTML: https://mlsanity.com/paper/1709.01249/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2017.

## Built on by (most cited first, 30 of 31)

- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)
- [You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks](https://mlsanity.com/paper/2106.13264/) (2021)
- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [Hypergraph Transformer for Skeleton-based Action Recognition](https://mlsanity.com/paper/2211.09590/) (2022)
- [Hyper-3DG: Text-to-3D Gaussian Generation via Hypergraph](https://mlsanity.com/paper/2403.09236/) (2024)
- [From Hypergraph Energy Functions to Hypergraph Neural Networks](https://mlsanity.com/paper/2306.09623/) (2023)
- [Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs](https://mlsanity.com/paper/2203.16939/) (2022)
- [Hypergraph Neural Networks through the Lens of Message Passing: A Common Perspective to Homophily and Architecture Design](https://mlsanity.com/paper/2310.07684/) (2023)
- [Neural Predicting Higher-order Patterns in Temporal Networks](https://mlsanity.com/paper/2106.06039/) (2021)
- [A nonlinear diffusion method for semi-supervised learning on hypergraphs](https://mlsanity.com/paper/2103.14867/) (2021)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [Learning from Heterogeneity: A Dynamic Learning Framework for Hypergraphs](https://mlsanity.com/paper/2307.03411/) (2023)
- [CAT-Walk: Inductive Hypergraph Learning via Set Walks](https://mlsanity.com/paper/2306.11147/) (2023)
- [Towards Multi-agent Reinforcement Learning based Traffic Signal Control through Spatio-temporal Hypergraphs](https://mlsanity.com/paper/2404.11014/) (2024)
- [Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs](https://mlsanity.com/paper/2203.01388/) (2022)
- [Finding Bipartite Components in Hypergraphs](https://mlsanity.com/paper/2205.02771/) (2022)
- [Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality](https://mlsanity.com/paper/2411.03331/) (2024)
- [Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning](https://mlsanity.com/paper/2102.10169/) (2021)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Decentralized Graph Neural Network for Privacy-Preserving Recommendation](https://mlsanity.com/paper/2308.08072/) (2023)
- [Modeling Edge-Specific Node Features through Co-Representation Neural Hypergraph Diffusion](https://mlsanity.com/paper/2405.14286/) (2024)
- [Tokenized Bandit for LLM Decoding and Alignment](https://mlsanity.com/paper/2506.07276/) (2025)
- [Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components](https://mlsanity.com/paper/2110.14859/) (2021)
- [Hypergraph Modeling via Spectral Embedding Connection: Hypergraph Cut, Weighted Kernel k-means, and Heat Kernel](https://mlsanity.com/paper/2203.09888/) (2022)
- [Hypergraphs with Edge-Dependent Vertex Weights: Spectral Clustering based on the 1-Laplacian](https://mlsanity.com/paper/2305.00462/) (2023)
- [Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach](https://mlsanity.com/paper/2505.18043/) (2025)
- [AGP: A Novel Arabidopsis thaliana Genomics-Phenomics Dataset and its HyperGraph Baseline Benchmarking](https://mlsanity.com/paper/2508.14934/) (2025)
- [Beyond Convolution: Advancing Hypergraph Neural Networks with Hypergraph U-Nets](https://mlsanity.com/paper/2606.09051/) (2026)

## Abstract (arXiv)

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.