Learning with Hypergraphs: Clustering, Classification, and Embedding

Dengyong ZhouJiayuan HuangB. Schölkopf

article2006NeurIPS1,626 citations

Generalizes spectral graph theory to hypergraphs by formulating normalized hypergraph cuts, Laplacians, and random walks to enable higher-order relational clustering, embedding, and transductive classification without losing multi-object structural information.

Listen

Real-world data often involves complex interactions where single relationships connect more than two entities simultaneously, such as multiple co-authors collaborating on a research paper or shared categorical features across records. Traditional machine learning techniques typically squeeze these high-order interactions into simple pairwise graphs, which inevitably discards critical relationship details. As organizations increasingly rely on complex networked data, addressing this structural information loss is vital for building accurate predictive and analytical models.

The main objective of the article is to establish a mathematically rigorous framework for hypergraph learning by extending spectral graph partitioning methods to hypergraphs, and to demonstrate its effectiveness in data embedding, clustering, and semi-supervised classification.

To accomplish this, the authors generalize normalized graph cut criteria and random walk models to hypergraphs, deriving an analogue known as the hypergraph Laplacian. They evaluate this framework across standard benchmark datasets—including the Zoo animal dataset (100 instances), the Mushroom dataset (8,124 instances), a text categorization task using the 20-Newsgroups collection (16,242 articles), and a subset of the Letter recognition dataset (3,865 instances across five letter categories)—benchmarking their approach directly against conventional simple graph methods.

The evaluation yielded several key findings. First, the hypergraph framework consistently outperformed traditional graph-based methods in classification accuracy across all test sets, yielding lower test error rates regardless of the number of labeled samples. Second, the hypergraph model proved significantly more robust and stable against variations in key regularization parameters compared to simple graphs, which exhibited high sensitivity and performance swings. Third, multi-dimensional hypergraph embedding successfully mapped categorical objects into continuous spaces while naturally capturing nuanced, intermediate semantic relationships that simple pairwise representations miss.

These findings indicate that hypergraph-based modeling offers substantial performance and reliability advantages for complex, multi-entity datasets. For decision-makers, adopting hypergraph representations mitigates the operational risk of misclassification and reduces sensitivity to hyperparameter tuning, leading to more resilient analytical systems. This demonstrates that moving beyond pairwise data representations is a necessary step when analyzing rich categorical and relational data.

Organizations handling complex interconnected data—such as social networks, biological pathways, and multi-attribute customer databases—should consider transitioning from pairwise graph pipelines to hypergraph representations. However, when deploying these methods, practitioners should account for current limitations: the empirical evaluations relied on uniform edge weights, and formal frameworks for automatically optimizing edge weights or extending the approach to directed hypergraphs remain areas for future implementation and study.

Max Planck Institute for Biological Cybernetics NEC Laboratories America, Inc.University of Waterloo bipartite graphs classification clustering methods hypergraph clustering spectral clustering transductive inference

Zhou et al (2006).pdf

No sufficiently relevant recommendations were found.

Paper: Hypergraph Neural Networks, Yifan Feng et al. (2018). This paper builds directly upon spectral hypergraph theory by formulating hypergraph neural networks with hyperedge convolutions to perform deep representation learning on complex high-order structures.
Paper: Networks beyond pairwise interactions: structure and dynamics, Federico Battiston et al. (2020). This survey provides a comprehensive synthesis of higher-order systems including hypergraphs and simplicial complexes, contextualizing spectral and dynamic methods beyond pairwise representations.

Cover for Learning with Hypergraphs: Clustering, Classification, and Embedding

Abstract

We usually endow the investigated objects with pairwise relationships, which can be illustrated as graphs. In many real-world problems, however, relationships among the objects of our interest are more complex than pairwise. Naively squeezing the complex relationships into pairwise ones will inevitably lead to loss of information which can be expected valuable for our learning tasks however. There we consider using hypergraphs instead to completely represent complex relationships among the objects of our interest, and thus the problem of learning with hypergraphs arises. Our main contribution in this paper is to generalize the powerful methodology of spectral clustering which originally operates on undirected graphs to hypergraphs, and further develop algorithms for hypergraph embedding and transductive classification on the basis of the spectral hypergraph clustering approach. Our experiments on a number of benchmarks showed the advantages of hypergraphs over usual graphs.

Topics

bipartite graphs classification clustering methods directed graphs spectral clustering weighted graph hier-archical clustering

Keywords

hypergraph clustering spectral clustering transductive inference image segmentation random walk categorical data

1 Introduction
2 Preliminaries
3 Normalized hypergraph cut
4 Random walk explanation
5 Spectral hypergraph partitioning
6 Spectral hypergraph embedding
7 Transductive inference
8 Experiments
9 Conclusion
References

Knowls

Knowl 1 — Normalized Hypergraph Laplacian
definition
Let $G = (V, E, w)$ be a weighted hypergraph with vertex set $V = \{v_1, \dots, v_n\}$ , hyperedge set $E = \{e_1, \dots, e_m\}$ , and positive hyperedge weights $w: E \to \mathbb{R}^+$ .

Let $H \in \{0, 1\}^{n \times m}$ be the incidence matrix with entries $h(v, e) = 1$ if $v \in e$ and $0$ otherwise. Let $D_v \in \mathbb{R}^{n \times n}$ and $D_e \in \mathbb{R}^{m \times m}$ denote the diagonal matrices of vertex degrees $d(v) = \sum_{e \in E} w(e) h(v,e)$ and hyperedge degrees $\delta(e) = \sum_{v \in V} h(v,e) = |e|$ , respectively. Let $W \in \mathbb{R}^{m \times m}$ be the diagonal matrix of hyperedge weights $W(e,e) = w(e)$ .

The transition operator $\Theta \in \mathbb{R}^{n \times n}$ and normalized hypergraph Laplacian $\Delta \in \mathbb{R}^{n \times n}$ are defined as:

$\Theta = D_v^{-1/2} H W D_e^{-1} H^T D_v^{-1/2}$

$\Delta = I - \Theta = I - D_v^{-1/2} H W D_e^{-1} H^T D_v^{-1/2}$

where $I$ is the $n \times n$ identity matrix. The hypergraph Laplacian $\Delta$ is symmetric and positive semidefinite. Its smallest eigenvalue is $0$ with associated eigenvector $\sqrt{d} = (\sqrt{d(v_1)}, \dots, \sqrt{d(v_n)})^T$ . For any function $f \in \mathbb{R}^n$ , $\Delta$ satisfies the quadratic form identity:

$f^T \Delta f = \frac{1}{2} \sum_{e \in E} \sum_{\{u,v\} \subseteq e} \frac{w(e)}{\delta(e)} \left( \frac{f(u)}{\sqrt{d(u)}} - \frac{f(v)}{\sqrt{d(v)}} \right)^2$

When every hyperedge contains exactly two vertices (a standard simple graph with $\delta(e) = 2$ ), $\Delta$ coincides with half the normalized graph Laplacian: $\Delta = \frac{1}{2}(I - D_v^{-1/2} A D_v^{-1/2})$ .
Knowl 2 — Hypergraph Normalized Cut Criterion
definition
Let $G = (V, E, w)$ be a weighted hypergraph where $V$ is the vertex set, $E$ is the set of hyperedges, and $w(e) > 0$ is the weight of hyperedge $e \in E$ . The degree of a vertex $v \in V$ is $d(v) = \sum_{e \in E, v \in e} w(e)$ , and the degree of a hyperedge $e \in E$ is $\delta(e) = |e|$ . For any subset $S \subset V$ , its volume is $\text{vol } S = \sum_{v \in S} d(v)$ , and its complement is $S^c = V \setminus S$ .

The hyperedge boundary $\partial S$ is the set of hyperedges incident to both $S$ and $S^c$ simultaneously:

$\partial S := \{e \in E \mid e \cap S \neq \emptyset, \; e \cap S^c \neq \emptyset\}$

The volume of the hyperedge boundary is defined as:

$\text{vol } \partial S := \sum_{e \in \partial S} w(e) \frac{|e \cap S| |e \cap S^c|}{\delta(e)}$

This formulation interprets each hyperedge $e$ as a clique of subedges with uniform weight $\frac{w(e)}{\delta(e)}$ , where cutting $e$ severs exactly $|e \cap S||e \cap S^c|$ subedges. The hypergraph normalized cut problem seeks a non-empty subset $S \subset V$ that minimizes:

$\arg\min_{\emptyset \neq S \subset V} c(S) := \text{vol } \partial S \left( \frac{1}{\text{vol } S} + \frac{1}{\text{vol } S^c} \right)$
Knowl 3 — Random Walk on Hypergraphs and Normalized Cut Duality
theoretical result
On a weighted hypergraph $G = (V, E, w)$ with vertex degrees $d(u) = \sum_{e \in E} w(e)h(u,e)$ and hyperedge degrees $\delta(e) = |e|$ , a natural random walk at vertex $u \in V$ first selects an incident hyperedge $e$ with probability $\frac{w(e)h(u,e)}{d(u)}$ and then selects a destination vertex $v \in e$ uniformly at random with probability $\frac{h(v,e)}{\delta(e)}$ .

The transition probability from $u$ to $v$ is given by:

$p(u, v) = \sum_{e \in E} w(e) \frac{h(u,e)}{d(u)} \frac{h(v,e)}{\delta(e)}$

In matrix notation, the transition matrix is $P = D_v^{-1} H W D_e^{-1} H^T$ , where $H$ is the incidence matrix, $D_v$ and $D_e$ are diagonal degree matrices, and $W$ is the diagonal hyperedge weight matrix.

The stationary distribution $\pi$ of this random walk on $V$ is:

$\pi(v) = \frac{d(v)}{\text{vol } V}$

where $\text{vol } V = \sum_{v \in V} d(v)$ . Under this stationary distribution, the volume of a subset $S \subset V$ and the volume of its cut boundary $\partial S$ satisfy:

$\frac{\text{vol } S}{\text{vol } V} = \sum_{v \in S} \pi(v)$

$\frac{\text{vol } \partial S}{\text{vol } V} = \sum_{u \in S} \sum_{v \in S^c} \pi(u) p(u, v)$

Thus, $\frac{\text{vol } \partial S}{\text{vol } V}$ is the stationary probability of the random walk crossing from $S$ to $S^c$ , demonstrating that minimizing the hypergraph normalized cut minimizes inter-cluster transitions while maximizing intra-cluster retention.
Knowl 4 — Spectral Lower Bound on k-Way Hypergraph Partitioning
theoretical result
Let $G = (V, E, w)$ be a connected weighted hypergraph with $n = |V|$ vertices. A $k$ -way partition of $V$ is a tuple $(V_1, \dots, V_k)$ of non-empty disjoint vertex subsets such that $\bigcup_{i=1}^k V_i = V$ and $V_i \cap V_j = \emptyset$ for all $1 \le i < j \le k$ .

The cost of a $k$ -way partition is defined as:

$c(V_1, \dots, V_k) = \sum_{i=1}^k \frac{\text{vol } \partial V_i}{\text{vol } V_i}$

where $\text{vol } V_i = \sum_{v \in V_i} d(v)$ and $\text{vol } \partial V_i = \sum_{e \in \partial V_i} w(e) \frac{|e \cap V_i| |e \cap V_i^c|}{\delta(e)}$ .

Let $c_k(G) = \min_{(V_1, \dots, V_k)} c(V_1, \dots, V_k)$ denote the minimum cost over all valid $k$ -way partitions. Let $\lambda_1 \le \lambda_2 \le \dots \le \lambda_n$ denote the eigenvalues of the normalized hypergraph Laplacian $\Delta = I - D_v^{-1/2} H W D_e^{-1} H^T D_v^{-1/2}$ in non-decreasing order. Then:

$\sum_{i=1}^k \lambda_i \le c_k(G)$

The sum of the $k$ smallest eigenvalues of the hypergraph Laplacian establishes a tight spectral lower bound on the combinatorial $k$ -way normalized cut problem.
Knowl 5 — Spectral Hypergraph Clustering and Embedding Algorithm
algorithm
Spectral hypergraph clustering embeds vertices into a $k$ -dimensional Euclidean space using the bottom $k$ eigenvectors of the normalized hypergraph Laplacian, followed by standard geometric clustering.
Input: Hypergraph incidence matrix $H \in \mathbb{R}^{n \times m}$ , diagonal hyperedge weight matrix $W \in \mathbb{R}^{m \times m}$ , number of clusters $k$ .
Output: Partition $(V_1, \dots, V_k)$ of the vertex set $V$ .
Compute vertex degrees $d(v) = \sum_{e \in E} w(e) h(v,e)$ and form diagonal matrix $D_v$
Compute hyperedge degrees $\delta(e) = \sum_{v \in V} h(v,e)$ and form diagonal matrix $D_e$
Form the normalized hypergraph Laplacian $\Delta = I - D_v^{-1/2} H W D_e^{-1} H^T D_v^{-1/2}$
Compute the $k$ smallest eigenvalues of $\Delta$ and their corresponding eigenvectors $\Phi_1, \Phi_2, \dots, \Phi_k \in \mathbb{R}^n$
Construct the embedding matrix $X = [\Phi_1, \Phi_2, \dots, \Phi_k] \in \mathbb{R}^{n \times k}$
Treat each row $i$ of $X$ as the $k$ -dimensional Euclidean representation of vertex $v_i$
Apply $k$ -means clustering to the $n$ row vectors of $X$ to obtain partitions $(V_1, \dots, V_k)$
return $(V_1, \dots, V_k)$
For 2-way partitioning ( $k=2$ ), the partition can alternatively be obtained directly by thresholding the eigenvector $\Phi_2$ corresponding to the smallest non-zero eigenvalue: $S = \{v \in V \mid \Phi_2(v) \ge 0\}$ and $S^c = \{v \in V \mid \Phi_2(v) < 0\}$ .
Knowl 6 — Transductive Inference on Hypergraphs
model/method
Transductive inference on a hypergraph $G = (V, E, w)$ predicts binary labels for unlabeled vertices given a subset of labeled vertices $S \subset V$ with labels in $\{-1, 1\}$ . Let $y \in \{-1, 0, 1\}^{|V|}$ be the initial label vector where $y(v) \in \{-1, 1\}$ if $v \in S$ and $y(v) = 0$ if $v \in V \setminus S$ .

A real-valued prediction function $f \in \mathbb{R}^{|V|}$ is obtained by solving the regularized least-squares optimization problem:

$\arg\min_{f \in \mathbb{R}^{|V|}} \left\{ \|f - y\|^2 + \mu f^T \Delta f \right\}$

where $\mu > 0$ is a regularization parameter and $\Delta = I - \Theta = I - D_v^{-1/2} H W D_e^{-1} H^T D_v^{-1/2}$ is the normalized hypergraph Laplacian.

The unique closed-form minimizer is:

$f = (I - \xi \Theta)^{-1} y$

where $\xi = \frac{1}{1 + \mu} \in (0, 1)$ . Final class assignments for unlabeled vertices $v \in V \setminus S$ are determined by $\text{sign}(f(v))$ .
Knowl 7 — Empirical Superiority of Hypergraph Transductive Learning over Pairwise Graphs
empirical result
Transductive classification using the normalized hypergraph Laplacian was compared against a simple graph spectral baseline across three categorical/relational benchmarks:
1. Mushroom: 8,124 instances with 21 categorical attributes (after excluding 1 attribute with missing values) classified into edible (4,208) vs. poisonous (3,916).
2. 20-Newsgroups: 16,242 text documents categorized into 4 top-level topics (sizes 4,605, 3,519, 2,657, and 5,461) with binary occurrence of 100 words.
3. Letter Recognition: 3,864 instances spanning classes A through E (sizes 789, 766, 736, 805, 768) described by 16 numerical attributes.
Hypergraphs were constructed by mapping each categorical attribute value to a hyperedge with weight $w(e) = 1$ . The baseline simple graph was formed via pairwise clique projection with adjacency matrix $A = H W H^T - D_v$ .

Experimental findings (averaged across 20 trials with regularization parameter $\alpha = 0.1$ and labeled instances varied from 20 to 200):
- The hypergraph method consistently achieved lower test error than the pairwise simple graph baseline across all labeled sample sizes on all three benchmarks.
- When varying the regularization parameter $\alpha \in [0.1, 0.9]$ on Letter recognition with 100 labeled points, the hypergraph model showed stable, low test error (between 0.14 and 0.18), whereas the simple graph baseline degraded substantially as $\alpha$ increased (error rising beyond 0.28).

Coverage note — None was omitted; the full methodological and empirical contribution of the paper (hypergraph normalized cut, random walk formulation, hypergraph Laplacian, spectral k-way relaxation bound, embedding/clustering algorithm, transductive learning formulation, and benchmark evaluations) is covered.

References

1.S. Agarwal, L. Zelnik-Manor J. Lim, P. Perona, D. Kriegman, and S. Belongie. Beyond pairwise clustering. In IEEE Conf. on Computer Vision and Pattern Recognition, 2005.
2.C. Berge. Hypergraphs. North-Holland, Amsterdam, 1989.
3.P. Bonacich, A.C. Holdren, and M. Johnston. Hyper-edges and multi-dimensional centrality. Social Networks, 26(3):189–203, 2004.
4.P.K. Chan, M.D.F. Schlag, and J. Zien. Spectral k-way ratio cut partitioning and clustering. IEEE Trans. on Computer Aided Design of Integrated Circuits and Systems, 13(9):1088–1096, 1994.
5.F. Chung. Spectral Graph Theory. Number 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Society, Providence, RI, 1997.
6.A. Corduneanu and T. Jaakkola. Distributed information regularization on graphs. In Advances in Neural Information Processing Systems 17, Cambridge, MA, 2005. MIT Press.
7.M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(98):298–305, 1973.
8.G. Gallo, G. Longo, and S. Pallottino. Directed hypergraphs and applications. Discrete Applied Mathematics, 42(2):177–201, 1993.
9.D. Gibson, J. Kleinberg, and P. Raghavan. Clustering categorical data: An approach based on dynamical systems. VLDB Journal, 8(3-4):222–236, 2000.
10.M. Gu, H. Zha, C. Ding, X. He, and H. Simon. Spectral relaxation models and structure analysis for k-way graph clustering and bi-clustering. Technical Report CSE-01-007, Department of Computer Science and Engineering, Pennsylvania State University, 2001.
11.L. Hagen and A.B. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Trans. on Computed-Aided Desgin of Integrated Circuits and Systems, 11(9):1074–1085, 1992.
12.D. Klein and C. Manning. Parsing and hypergraphs. In Proc. 7th Intl. Workshop on Parsing Technologies, 2001.
13.M. Meila and J. Shi. A random walks view of spectral segmentation. In Proc. 8th Intl. Workshop on Artificial Intelligence and Statistics, 2001.
14.A.Y. Ng, M.I. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm. In Advances in Neural Information Processing Systems 14, Cambridge, MA, 2002. MIT Press.
15.J.S. Oliveira, J.B. Jones-Oliveira, D.A. Dixon, C.G. Bailey, and D.W. Gull. Hyperdigraph–Theoretic analysis of the EGFR signaling network: Initial steps leading to GTP: Ras complex formation. Journal of Computational Biology, 11(5):812–842, 2004.
16.J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Tran. on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000.
17.K. Tsuda. Propagating distributions on a hypergraph by dual information regularization. In Proc. 22th Intl. Conf. on Machine Learning, 2005.
18.E.P. Xing and M.I. Jordan. On semidefinite relaxation for normalized k-cut and connections to spectral clustering. Technical Report CSD-03-1265, Division of Computer Science, University of California, Berkeley, 2003.
19.D. Zhou, O. Bousquet, T.N. Lal, J. Weston, and B. Sch¨olkopf. Learning with local and global consistency. In Advances in Neural Information Processing Systems 16, Cambridge, MA, 2004. MIT Press.
20.D. Zhou, J. Huang, and B. Sch¨olkopf. Learning from labeled and unlabeled data on a directed graph. In Proc. 22th Intl. Conf. on Machine Learning, 2005.
21.X. Zhu. Semi-supervised learning literature survey. Technical Report Computer Sciences 1530, University of Wisconsin - Madison, 2005.

Citation

MLA

Zhou, D., et al. “Learning with Hypergraphs: Clustering, Classification, and Embedding”. Advances in Neural Information Processing Systems, vol. 19, 2006, https://proceedings.neurips.cc/paper_files/paper/2006/file/dff8e9c2ac33381546d96deea9922999-Paper.pdf.

APA

Zhou, D., Huang, J., & Schölkopf, B. (2006). Learning with Hypergraphs: Clustering, Classification, and Embedding. Advances in Neural Information Processing Systems, 19. https://proceedings.neurips.cc/paper_files/paper/2006/file/dff8e9c2ac33381546d96deea9922999-Paper.pdf

Chicago

Zhou, D., J. Huang, and B. Schölkopf. 2006. “Learning with Hypergraphs: Clustering, Classification, and Embedding”. Advances in Neural Information Processing Systems 19. https://proceedings.neurips.cc/paper_files/paper/2006/file/dff8e9c2ac33381546d96deea9922999-Paper.pdf.

Harvard

Zhou, D., Huang, J. and Schölkopf, B. (2006) “Learning with Hypergraphs: Clustering, Classification, and Embedding”, Advances in Neural Information Processing Systems. Curran Associates, Inc. Available at: https://proceedings.neurips.cc/paper_files/paper/2006/file/dff8e9c2ac33381546d96deea9922999-Paper.pdf.

Vancouver

1. Zhou D, Huang J, Schölkopf B (2006) Learning with Hypergraphs: Clustering, Classification, and Embedding. Advances in Neural Information Processing Systems 19:

BibTeX

@inproceedings{zhou2006learning,
  title = {Learning with Hypergraphs: Clustering, Classification, and Embedding},
  author = {Zhou, Dengyong and Huang, Jiayuan and Schölkopf, Bernhard},
  year = {2006},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {19},
  url = {https://proceedings.neurips.cc/paper_files/paper/2006/file/dff8e9c2ac33381546d96deea9922999-Paper.pdf}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Learning with Hypergraphs: Clustering, Classification, and Embedding

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Normalized Hypergraph Laplacian

Knowl 2 — Hypergraph Normalized Cut Criterion

Knowl 3 — Random Walk on Hypergraphs and Normalized Cut Duality

Knowl 4 — Spectral Lower Bound on k-Way Hypergraph Partitioning

Knowl 5 — Spectral Hypergraph Clustering and Embedding Algorithm

Knowl 6 — Transductive Inference on Hypergraphs

Knowl 7 — Empirical Superiority of Hypergraph Transductive Learning over Pairwise Graphs

References

Citation

BibTeX

Access the Paper