Source-linked AI summary
HNHN: Hypergraph Networks with Hyperedge Neurons
Yihe Dong, Will Sawin, Yoshua Bengio
TL;DR
Hypergraph learning needs methods that preserve hyperedge structure and choose suitable weighting for hypernodes and hyperedges. HNHN addresses this with nonlinear representations for both entity types and dataset-adaptive normalization, achieving improved classification accuracy and speed on real-world datasets while preserving dedicated hyperedge representations.
Problem
Existing clique-based hypergraph conversions lose information, while fixed normalization may weight high-degree vertices or large hyperedges poorly for a given dataset.
Method
HNHN learns separate hypernode and hyperedge representations, applies nonlinear activation to both, and optimizes normalization hyperparameters for each dataset.
Results
HNHN improves classification accuracy and speed on real-world datasets compared with state-of-the-art methods, while reduced-feature experiments preserve its accuracy advantage.
Takeaways & Limitations
Dedicated hyperedge representations support downstream edge-related tasks, including hyperedge classification when only hyperedge labels are available.
Takeaways & Limitations
Clique expansion can lose hypergraph information, so graph convolution on the resulting graph cannot solve tasks whose answers change under hypernode-label permutations.
Abstract
from arXiv · showhide
Hypergraphs provide a natural representation for many real world datasets. We propose a novel framework, HNHN, for hypergraph representation learning. HNHN is a hypergraph convolution network with nonlinear activation functions applied to both hypernodes and hyperedges, combined with a normalization scheme that can flexibly adjust the importance of high-cardinality hyperedges and high-degree vertices depending on the dataset. We demonstrate improved performance of HNHN in both classification accuracy and speed on real world datasets when compared to state of the art methods.
1 Introduction
HNHN learns hypergraph representations by applying nonlinear transformations to both hypernodes and hyperedges, while flexibly normalizing their contributions. The framework addresses limitations of clique-based graph conversions and adapts weighting choices to dataset characteristics.
- Hypergraphs represent relations involving more than two objects, such as authors connecting multiple papers in paper-authorship data.
- Prior hypergraph methods based on adjacency matrices can reduce hyperedges to weighted cliques, limiting their accuracy to that of the corresponding graph algorithm.
- HNHN maintains separate representations for hypernodes and hyperedges and applies nonlinear activation to both through the incidence matrix.
- Its normalization flexibly weights hypernodes and hyperedges using dataset-optimized hyperparameters rather than a fixed formula.
- The paper motivates normalization choices by noting that high-degree vertices may be influential users in one dataset but random-connecting bots in another.
- The paper contributes HNHN, a hypergraph convolution network combining hypernode and hyperedge nonlinearities with flexible normalization.
2 Model architecture and analysis
HNHN represents hypernodes and hyperedges separately, updates them through the incidence matrix, and applies nonlinear transformations to both. Its formulation preserves hypergraph structure beyond clique expansion while relating to star and clique graph convolutions under restricted parameter choices.
- HNHN convolution: HNHN maintains separate representations for hypernodes and hyperedges and updates them using the hypergraph incidence matrix.The update uses nonlinear activation, distinct weight matrices, and bias terms for the two object types.
- Star expansion: The star expansion models hypernodes and hyperedges as vertices in a bipartite graph connected according to incidence.There are no edges between hypernodes or between hyperedges in this construction.
- Relation to graph convolution: With shared weights and biases, HNHN is equivalent to graph convolution on the star expansion.This equivalence sets WE = WV and bE = bV.
- Relation to graph convolution: Without nonlinear activation, HNHN is equivalent to graph convolution on the clique expansion, whose adjacency matrix satisfies C = AAT.The equivalence follows by composing the hyperedge and hypernode linear maps and using the incidence-based identity.
- Clique expansion: Clique expansion can map distinct hypergraphs to the same graph, preventing graph convolution from solving tasks whose answers change under hypernode-label permutations.The Fano plane yields 30 distinct hypergraphs with the same clique expansion K7, while HNHN can distinguish the illustrated pair.
- Star expansion: Unlike star expansion, HNHN allows hypernodes and hyperedges to use different weight matrices, providing additional expressive power when they represent different objects.The paper motivates this distinction because hypernodes and hyperedges can describe fundamentally different entities in datasets.
3 Experiments
Experiments evaluate HNHN across co-authorship and co-citation hypergraphs, measuring hypernode and hyperedge prediction, accuracy, timing, and normalization effects. HNHN outperforms state-of-the-art techniques across datasets while retaining competitive timing, and its accuracy advantage persists with reduced feature dimensions.
- Datasets: The evaluation spans CiteSeer and PubMed co-citation datasets plus Cora and DBLP co-authorship datasets, varying graph structure and class counts.Hypernodes are papers; hyperedges represent shared authors or citation relations.
- Experimental setup: Hypernode prediction uses labels on a small subset of hypernodes, cross-entropy loss, Adam optimization, and dataset-tuned hyperparameters.At most two convolution layers were needed for the reported accuracies.
- Reduced feature dimensions: 63.69±0.58% accuracy and 10.84±0.14 seconds training time are achieved by HNHN on reduced-feature Cora, versus 56.63±0.33% and 152.34±1.14 seconds for HGNN.Reducing dimensions from 1000 to 300 preserves HNHN's accuracy advantage when computational resources are limited.
- Hyperedge prediction: 62.79±1.43% hyperedge classification accuracy on CiteSeer with 15% hyperedge labels is comparable to 64.76±1.63% hypernode prediction accuracy with 15% hypernode labels.HNHN provides one dedicated vector representation per hyperedge, supporting edge-related prediction tasks.
- Hypernode prediction: HNHN outperforms state-of-the-art techniques across datasets while achieving competitive timing results.Table 2 reports hypernode classification accuracy in percent and training timings in seconds.
- Normalization effects: On CiteSeer, normalization parameters affect node-prediction accuracy, and α = β = 0 is not necessarily optimal; β has the larger observed effect.The reported degree-variation ratios are 1.49 for vertices and 0.60 for hyperedges.