{ "id": "ep3k73yz0e", "slug": "hypergraph-convolutional-network", "title": "Hypergraph convolutional network", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_computation" }, { "id": "technology.computing.ai.neural_deep", "label": "Neural networks and deep learning", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.neural_deep" }, { "id": "technology.computing.ai.nn_architectures", "label": "Neural network architectures", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.nn_architectures" }, { "id": "technology.computing.ai.nn_architectures.graph_networks", "label": "Graph neural network architectures", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.nn_architectures.graph_networks" } ], "geo": [ { "id": "geo.nongeo.t2001.technology.computing.ai.neural_deep", "label": "Non-geographic · 2001 to 2020: Neural networks and deep learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.neural_deep", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t2001", "label": "Non-geographic · 2001 to 2020", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001" }, { "id": "geo.nongeo.t2001.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology" }, { "id": "geo.nongeo.t2001.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing" }, { "id": "geo.nongeo.t2001.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai" }, { "id": "geo.nongeo.t2001.technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.ml_computation" }, { "id": "geo.nongeo.t2001.technology.computing.ai.neural_deep", "label": "Neural networks and deep learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.neural_deep" } ] } ], "excerpt": "A hypergraph convolutional network (HGNN) is a neural network that generalizes graph convolution to hyperedges linking many vertices, introduced by Yifan Feng in 2018 and published at AAAI 2019.", "snippet": "A hypergraph convolutional network (HGNN) is a neural network that generalizes graph convolution to hyperedges linking many vertices, introduced by Yifan Feng in 2018 and published at AAAI 2019.", "node": "technology.computing.ai.nn_architectures.graph_networks", "markdown": "# Hypergraph convolutional network\n\nA hypergraph convolutional network (HGNN) is a neural network architecture that generalizes the [graph convolutional network](https://www.edgepedia.org/graph-convolutional-network) to hypergraphs, learning node representations connected by multi-way hyperedges rather than pairwise edges. Because a hyperedge can link any number of vertices at once, the architecture captures higher-order relationships that pairwise graph structures lose, and it is used for semi-supervised node classification, visual object recognition, recommendation, and other representation-learning tasks.[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) • [2](https://dl.acm.org/doi/10.1145/3637528.3671457)\n\n| Key fact | Detail |\n|---|---|\n| Defining operation | Hyperedge convolution propagates features through the incidence matrix \\( H \\), mixing all vertices of a hyperedge in one step[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) |\n| Core propagation | \\( X^{(l+1)} = \\sigma(D_v^{-1/2} H W D_e^{-1} H^{\\top} D_v^{-1/2} X^{(l)} \\Theta^{(l)}) \\)[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) |\n| Introducing paper | \"Hypergraph Neural Networks\" by Yifan Feng and colleagues, arXiv 2018, published at AAAI 2019[3](https://doi.org/10.48550/arxiv.1809.09401) • [1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) |\n| Original benchmarks | 81.6% accuracy on Cora and 80.1% on Pubmed (average of 100 runs), versus 81.5% and 79.0% for GCN[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) |\n| Main variants | HGNN+, HyperGAT, HyperGCN/FastHyperGCN, HNHN, AllSet, UniGNN[4](https://ieeexplore.ieee.org/document/9795251) • [5](https://www.sciencedirect.com/science/article/abs/pii/S0031320320304404) • [6](https://proceedings.neurips.cc/paper/2019/file/1efa39bcaec6f3900149160693694536-Paper.pdf) • [7](https://doi.org/10.48550/arxiv.2006.12278) • [8](https://arxiv.org/pdf/2106.13264) • [9](https://www.ijcai.org/proceedings/2021/353) |\n| Known failure modes | Over-squashing (measured as worse than in graph networks), over-smoothing, and memory cost of dense clique expansion[10](https://proceedings.mlr.press/v269/yadati25a.html) • [11](https://dl.acm.org/doi/abs/10.1609/aaai.v39i20.35472) • [12](https://proceedings.iclr.cc/paper_files/paper/2026/file/4f25c9511feb3d6496450d68ca21efb9-Paper-Conference.pdf) |\n| Applications | Recommendation, bioinformatics and medical science, time series analysis, computer vision, finance, sociology[2](https://dl.acm.org/doi/10.1145/3637528.3671457) • [13](http://dmlab.kaist.ac.kr/~kijungs/papers/hnnCIKM2025.pdf) |\n\n## How it works\n\nA hypergraph \\( G \\) is written as a \\( |V| \\times |E| \\) incidence matrix \\( H \\), with \\( h(v,e) = 1 \\) if vertex \\( v \\) belongs to hyperedge \\( e \\) and 0 otherwise. Spectral convolution on this structure is \\( g \\star x = \\Phi((\\Phi^{\\top} g) \\odot (\\Phi^{\\top} x)) = \\Phi g(\\Lambda) \\Phi^{\\top} x \\), using the eigenvectors of the hypergraph Laplacian as Fourier bases; applying an exact spectral filter with a precomputed eigenbasis costs \\( O(n^2) \\) per signal, while computing a dense eigendecomposition generally costs \\( O(n^3) \\); HGNN therefore follows the \\( K \\)-order Chebyshev parametrization used for graphs and simplifies it with \\( K = 1 \\) and \\( \\lambda_{\\max} \\approx 2 \\).[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235)\n\nThe resulting layer-wise propagation is\n\n\\[ X^{(l+1)} = \\sigma\\left(D_v^{-1/2} H W D_e^{-1} H^{\\top} D_v^{-1/2} X^{(l)} \\Theta^{(l)}\\right), \\]\n\nwhere \\( W = \\mathrm{diag}(w_1, \\ldots, w_{|E|}) \\) is the hyperedge weight matrix, \\( D_v \\) and \\( D_e \\) are the vertex and hyperedge degree matrices, and \\( \\Theta \\in \\mathbb{R}^{C_1 \\times C_2} \\) is the learned parameter.[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) HyperGAT's authors prove that graph convolution is a special case of hypergraph convolution when non-pairwise relationships degenerate to pairwise ones.[5](https://www.sciencedirect.com/science/article/abs/pii/S0031320320304404)\n\nNormalization matters because \\( H W H^{\\top} \\) has no constrained spectral radius; stacking unnormalized layers risks numerical instability and exploding or vanishing gradients. HyperGAT therefore uses the symmetric form \\( X^{(l+1)} = \\sigma(D^{-1/2} H W B^{-1} H^{\\top} D^{-1/2} X^{(l)} P) \\), with a random-walk variant \\( X^{(l+1)} = \\sigma(D^{-1} H W B^{-1} H^{\\top} X^{(l)} P) \\).[5](https://www.sciencedirect.com/science/article/abs/pii/S0031320320304404)\n\n## How it is done\n\nA practical workflow has four steps. First, construct the hypergraph from the data. In visual object classification, each hyperedge connects one vertex and its \\( K \\) nearest neighbors by [Euclidean distance](https://www.edgepedia.org/euclidean-distance), giving \\( N \\) hyperedges that link \\( K+1 \\) vertices and an incidence matrix \\( H \\in \\mathbb{R}^{N \\times N} \\) with \\( N \\times (K+1) \\) entries equal to 1; for \\( M \\) modalities, the \\( N \\times N \\) matrices are concatenated column-wise into a combined \\( N \\times MN \\) matrix \\( H \\).[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) On citation data, DGL's tutorial builds a \"co-cite\" hypergraph where each paper's hyperedge contains all papers it cited plus itself, making the incidence matrix the adjacency matrix plus the identity.[14](https://www.dgl.ai/dgl_docs/en/2.2.x/notebooks/sparse/hgnn.html)\n\nSecond, feed the node features and \\( H \\) into the model; the DeepHypergraph implementation pre-computes \\( \\mathcal{L}_{HGNN} = D_v^{-1/2} H W_e D_e^{-1} H^{\\top} D_v^{-1/2} \\) and stores it as an attribute.[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) • [15](https://deephypergraph.readthedocs.io/en/latest/tutorial/model.html) Third, train a two-layer HGNN with a softmax output by back-propagating cross-entropy loss over the labeled training nodes to update \\( \\Theta \\).[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) Fourth, predict test labels. The authors' official implementation is hosted at iMoonLab/HGNN.[16](https://github.com/iMoonLab/HGNN)\n\n## Origin\n\nThe HGNN framework with its hyperedge convolution operation was reported by Yifan Feng and colleagues in \"Hypergraph Neural Networks\", posted to arXiv in 2018 and published at AAAI 2019.[3](https://doi.org/10.48550/arxiv.1809.09401) • [1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) It cites [hypergraph learning](https://www.edgepedia.org/hypergraph-learning) as formulated as a propagation process on hypergraph structure, and notes that those traditional methods suffer from high computation complexity and storage cost, which motivated a neural approach.[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) On the spectral side, it adapts the Chebyshev graph convolution parametrization and its \\( K=1 \\), \\( \\lambda_{\\max} \\approx 2 \\) simplification from the graph convolutional network literature.[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) HyperGCN, by Naganand Yadati and colleagues, appeared on arXiv the same year as a pairwise-approximation alternative.[17](https://doi.org/10.48550/arxiv.1809.02589)\n\n## Variants\n\n**HGNN+** extends the conference model into a general framework for multi-modal and multi-type data correlation: hyperedge groups from different modalities are fused adaptively within a single hypergraph, and a new spatial-domain hypergraph convolution scheme replaces the fixed spectral form.[4](https://ieeexplore.ieee.org/document/9795251) **HyperGAT** enriches the incidence matrix \\( H \\) with an attention module, yielding hypergraph attention alongside hypergraph convolution, implemented in PyTorch.[5](https://www.sciencedirect.com/science/article/abs/pii/S0031320320304404)\n\n**HyperGCN** and its faster variant FastHyperGCN approximate each hyperedge by a set of pairwise edges connecting its vertices and treat learning as a graph problem, requiring \\( O(s) \\) edges per hyperedge of size \\( s \\) where HGNN's clique approximation needs a quadratic number.[6](https://proceedings.neurips.cc/paper/2019/file/1efa39bcaec6f3900149160693694536-Paper.pdf) **HNHN**, by Dong, Sawin, and Bengio (2020), applies nonlinear activations to both hypernodes and hyperedges via the incidence matrix \\( A \\): \\( X'_E = \\sigma(A^{\\top} X_V W_E + b_E) \\) and \\( X'_V = \\sigma(A X'_E W_V + b_V) \\), with a normalization scheme, and avoids explicitly instantiating \\( A \\), which has size \\( O(mn) \\).[7](https://doi.org/10.48550/arxiv.2006.12278) **AllSet** expresses propagation as a composition of two multiset functions, covering the propagation rules of HyperGCN, HGNN, HCHA, HNHN, and HyperSAGE; its normalized update is \\( X_{v,:}^{(t+1)} = \\sigma(([1/\\sqrt{d_v} \\sum_{e:v \\in e} w_e/|e| \\sum_{u:u \\in e} X_{u,:}^{(t)}/\\sqrt{d_u}]) \\Theta^{(t)} + b^{(t)}) \\).[8](https://arxiv.org/pdf/2106.13264) **UniGNN**, by Huang and Yang (2021), gives one message-passing framework for graphs and hypergraphs, generalizing GCN, GAT, GIN, and [GraphSAGE](https://www.edgepedia.org/graphsage) into UniGCN, UniGAT, UniGIN, and UniSAGE; its hyperedge update computes \\( h_e = \\phi_1(\\{x_j\\}_{j \\in e}) \\) from the set of incident node features.[9](https://www.ijcai.org/proceedings/2021/353) **DPHGNN** (Siddhant Saxena and colleagues, 2024) is a dual-perspective hypergraph network.[18](https://doi.org/10.48550/arxiv.2405.16616)\n\n## Applications\n\nReported accuracies vary strongly with the hypergraph construction and data splits, so numbers should be quoted with their conditions. In the original paper's setup, HGNN averages 81.6% on Cora and 80.1% on Pubmed over 100 runs, a slight gain over GCN (81.5% and 79.0%).[1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) Third-party comparisons give very different values: the HNHN paper reports HGNN at 58.2±0.3 on Cora and 63.3±2.2 on PubMed.[7](https://doi.org/10.48550/arxiv.2006.12278)\n\nA KDD 2024 survey organizes [hypergraph neural networks](https://www.edgepedia.org/hypergraph-neural-network) into four design components: input features, input structures, message-passing schemes, and training strategies.[2](https://dl.acm.org/doi/10.1145/3637528.3671457) HyperGAT's hypergraph convolution reaches 82.19 on Cora versus GCN* at 81.80 (significant at the 5% level, \\( p = 0.016 \\)).[5](https://www.sciencedirect.com/science/article/abs/pii/S0031320320304404) UniGNN raises DBLP semi-supervised classification accuracy from 77.4% to 88.8%.[9](https://www.ijcai.org/proceedings/2021/353)\n\n## Limitations and alternatives\n\nThree failure modes are documented. Over-squashing: using three benchmark problems (HyperEdgeSingle, HyperEdgePath, HyperEdgeRing), a 2025 analysis finds, counter-intuitively, that state-of-the-art hypergraph neural networks are more susceptible to over-squashing than their graph counterparts, shown theoretically and experimentally.[10](https://proceedings.mlr.press/v269/yadati25a.html) KHGNN (AAAI 2025) likewise identifies the limited feature-propagation scope of existing HGNNs as exacerbating over-squashing and over-smoothing, and addresses it with bisection nested convolution that extracts features along all shortest paths between nodes or hyperedges.[11](https://dl.acm.org/doi/abs/10.1609/aaai.v39i20.35472) [Scalability](https://www.edgepedia.org/scalability): clique expansion requires \\( O(|N_j|^2) \\) edges per hyperedge, giving graph convolution cost \\( O(n \\delta_V \\delta_E d) \\), while linear-expansion methods such as HyperGCN and HNHN are faster.[7](https://doi.org/10.48550/arxiv.2006.12278) • [6](https://proceedings.neurips.cc/paper/2019/file/1efa39bcaec6f3900149160693694536-Paper.pdf)\n\nAgainst plain GCN and GAT, hypergraph convolution is a strict generalization in the sense proven by HyperGAT, but on citation benchmarks where the hypergraph mirrors the graph it offers only small gains.[5](https://www.sciencedirect.com/science/article/abs/pii/S0031320320304404) • [1](https://ojs.aaai.org/index.php/AAAI/article/view/4235) Pairwise-graph approximations (HyperGCN, and clique-expansion baselines like CEGCN/CEGAT) trade exact multi-way propagation for graph-tool compatibility and speed.[6](https://proceedings.neurips.cc/paper/2019/file/1efa39bcaec6f3900149160693694536-Paper.pdf) • [12](https://proceedings.iclr.cc/paper_files/paper/2026/file/4f25c9511feb3d6496450d68ca21efb9-Paper-Conference.pdf) On expressivity, UniGNN proved its message-passing models are at most as powerful as the 1-dimensional Generalized Weisfeiler-Leman (1-GWL) algorithm, and a 2025 theory paper states that most hypergraph neural networks remain limited to 1-GWL's expressive power.[9](https://www.ijcai.org/proceedings/2021/353) • [19](https://proceedings.mlr.press/v267/zhang25dc.html) [Complexity](https://www.edgepedia.org/complexity) itself is a cost: on Yelp, ED-HNN and EHNN give only marginal accuracy gains over the simple HGNN while training over 9× and 23× longer, and 8 of the 17 benchmarked methods hit memory bottlenecks on large datasets.[12](https://proceedings.iclr.cc/paper_files/paper/2026/file/4f25c9511feb3d6496450d68ca21efb9-Paper-Conference.pdf)\n\n## References\n\n1. [Hypergraph Neural Networks (Feng et al., AAAI 2019)](https://ojs.aaai.org/index.php/AAAI/article/view/4235)\n2. [A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guide (KDD 2024)](https://dl.acm.org/doi/10.1145/3637528.3671457)\n3. [Feng, Yifan and colleagues (2018). Hypergraph Neural Networks. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1809.09401)\n4. [HGNN+: General Hypergraph Neural Networks (IEEE)](https://ieeexplore.ieee.org/document/9795251)\n5. [Hypergraph convolution and hypergraph attention (HyperGAT; Pattern Recognition, publisher version; excerpts merged from arXiv 1901.08150, the Oxford ORA copy, and the ar5iv mirror)](https://www.sciencedirect.com/science/article/abs/pii/S0031320320304404)\n6. [HyperGCN: A New Method For Training Graph Convolutional Networks on Hypergraphs (NeurIPS 2019)](https://proceedings.neurips.cc/paper/2019/file/1efa39bcaec6f3900149160693694536-Paper.pdf)\n7. [Dong, Yihe, Sawin, Will, Bengio, Yoshua (2020). HNHN: Hypergraph Networks with Hyperedge Neurons. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2006.12278)\n8. [AllSet: Learning Multiset Functions for Hypergraph Neural Networks](https://arxiv.org/pdf/2106.13264)\n9. [UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks (IJCAI 2021; excerpts merged from the ar5iv mirror of arXiv 2105.00956)](https://www.ijcai.org/proceedings/2021/353)\n10. [Oversquashing in Hypergraph Neural Networks (PMLR v269, 2025)](https://proceedings.mlr.press/v269/yadati25a.html)\n11. [K-hop hypergraph neural network (KHGNN, AAAI 2025)](https://dl.acm.org/doi/abs/10.1609/aaai.v39i20.35472)\n12. [DHG-BENCH (ICLR 2026)](https://proceedings.iclr.cc/paper_files/paper/2026/file/4f25c9511feb3d6496450d68ca21efb9-Paper-Conference.pdf)\n13. [A Tutorial on Hypergraph Neural Networks (CIKM 2025)](http://dmlab.kaist.ac.kr/~kijungs/papers/hnnCIKM2025.pdf)\n14. [Hypergraph Neural Networks, DGL 2.2.1 documentation](https://www.dgl.ai/dgl_docs/en/2.2.x/notebooks/sparse/hgnn.html)\n15. [Building HGNN and HGNN+ models (DeepHypergraph documentation)](https://deephypergraph.readthedocs.io/en/latest/tutorial/model.html)\n16. [iMoonLab/HGNN official code repository](https://github.com/iMoonLab/HGNN)\n17. [Yadati, Naganand and colleagues (2018). HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1809.02589)\n18. [Saxena, Siddhant and colleagues (2024). DPHGNN: A Dual Perspective Hypergraph Neural Networks. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2405.16616)\n19. [Improved Expressivity of Hypergraph Neural Networks through High-Dimensional Generalized Weisfeiler-Leman Algorithms (PMLR v267, 2025)](https://proceedings.mlr.press/v267/zhang25dc.html)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Machine learning and neural computation › Neural networks and deep learning › Neural network architectures › Graph neural network architectures*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/hypergraph-convolutional-network", "markdown_url": "https://www.edgepedia.org/hypergraph-convolutional-network.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Hypergraph convolutional network\", Edgepedia (EdgeChat), https://www.edgepedia.org/hypergraph-convolutional-network. Edgepedia Community License 1.0.", "credit_md": "\"[Hypergraph convolutional network](https://www.edgepedia.org/hypergraph-convolutional-network)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/hypergraph-convolutional-network](https://www.edgepedia.org/hypergraph-convolutional-network). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Hypergraph convolutional network\", Edgepedia (EdgeChat), https://www.edgepedia.org/hypergraph-convolutional-network. Edgepedia Community License 1.0.", "speakable": "A hypergraph convolutional network is a neural network that generalizes graph convolution to hyperedges linking many vertices, introduced by Yifan Feng in 2018 and published at AAAI 2019." }