Source-linked AI summary
Hyper-SAGNN: a self-attention based graph neural network for hypergraphs
Ruochi Zhang, Yuesong Zou, Jian Ma
TL;DR
Existing hypergraph methods have limited ability to represent heterogeneous, variable-sized hyperedges and support diverse learning tasks. Hyper-SAGNN uses self-attention within tuples to learn representations for general hypergraphs, and it improves or matches state-of-the-art performance across benchmark, genomics, and outsider-identification evaluations. The authors conclude that the framework is flexible and computationally efficient, while identifying broader neighbor aggregation as future work.
Problem
Existing methods are not generic across hypergraph types and tasks, and prior approaches do not provide models for predicting variable-sized heterogeneous hyperedges.
Method
Hyper-SAGNN uses self-attention within each tuple to learn hyperedge-prediction functions, with node features generated from attributes or graph structure.
Results
Hyper-SAGNN improves or matches state-of-the-art hypergraph representation-learning performance, including 81.9% outsider-identification accuracy on the drug dataset.
Takeaways & Limitations
The framework supports homogeneous and heterogeneous, uniform and non-uniform hypergraphs and can be applied across different applications, including single-cell genomics.
Takeaways & Limitations
Future work is needed to aggregate information over all first-order neighbors, which would add computational cost and may improve link prediction and semi-supervised learning.
Abstract
from arXiv · showhide
Graph representation learning for hypergraphs can be used to extract patterns among higher-order interactions that are critically important in many real world problems. Current approaches designed for hypergraphs, however, are unable to handle different types of hypergraphs and are typically not generic for various learning tasks. Indeed, models that can predict variable-sized heterogeneous hyperedges have not been available. Here we develop a new self-attention based graph neural network called Hyper-SAGNN applicable to homogeneous and heterogeneous hypergraphs with variable hyperedge sizes. We perform extensive evaluations on multiple datasets, including four benchmark network datasets and two single-cell Hi-C datasets in genomics. We demonstrate that Hyper-SAGNN significantly outperforms the state-of-the-art methods on traditional tasks while also achieving great performance on a new task called outsider identification. Hyper-SAGNN will be useful for graph representation learning to uncover complex higher-order interactions in different applications.
1 Introduction
Hyper-SAGNN addresses the challenge of learning from higher-order interactions by supporting diverse hypergraph structures and variable hyperedge sizes. Across benchmark, outsider-identification, and single-cell genomics tasks, it outperforms existing methods.
- Hypergraphs capture higher-order relationships, including co-authorships involving more than two authors and heterogeneous tuples such as “(human, location, activity)”
- Hyper-SAGNN supports homogeneous and heterogeneous hypergraphs with variable hyperedge sizes.
- The model improves over DHNE across multiple tasks and performs better in multi-task edge and hyperedge prediction.
- In single-cell Hi-C data, Hyper-SAGNN embeddings cluster cells by type and achieve the highest ARI, Micro-F1, and Macro-F1 among three methods.
2 Related Work
Prior hypergraph methods learn object or hyperedge representations but often decompose higher-order relationships or impose fixed-size constraints. DHNE models tuple-wise relationships directly, yet remains limited to k-uniform hypergraphs.
- HEBE learns embeddings for objects in specific heterogeneous events represented as hyperedges but performs poorly on sparse hypergraphs.
- Previous methods commonly decompose hyperedges into pair-wise relationships using explicit or implicit strategies.
- DHNE directly models tuple-wise relationships with an MLP and outperforms several graph and hypergraph methods on multiple tasks.
- Because its MLP requires fixed-size input, DHNE handles only k-uniform hypergraphs containing k nodes per hyperedge.
3 Method
Hyper-SAGNN formulates hyperedge prediction for variable-sized, non-ordered node tuples and uses self-attention to model their higher-order relationships. It combines static and tuple-dependent dynamic embeddings, compares each pair, and averages node-level probability scores.
- Problem formulation: Hyperedge prediction learns functions from node features to hyperedge probabilities while requiring variable-sized, non-ordered inputs.The formulation does not assume k-uniform hypergraphs or identical hyperedge types.
- Model motivation: Hyper-SAGNN addresses prior limitations by directly modeling tuple-wise relationships without fixed-size MLP inputs or separate functions for different hyperedge types.DHNE handles tuple-wise relationships but is restricted by fixed-size input and requires individual functions for different hyperedge types.
- Self-attention mechanism: Self-attention aggregates information for each node only from the other nodes in its given tuple, rather than from all first-order neighbors.The model uses attention coefficients, softmax normalization, and weighted transformed features within each tuple.
- Embedding architecture: A position-wise network produces static embeddings, while a multi-head graph attention layer produces dynamic embeddings dependent on all node features in the tuple.Static embeddings remain unchanged for a node across tuples; dynamic embeddings encode tuple context.
- Prediction function: The model transforms each static–dynamic difference into a sigmoid probability score and averages the node-level scores into the final hyperedge probability.The score is based on the Hadamard power of the difference and is interpreted as a squared weighted pseudo-euclidean distance.
- Feature generation: Node features can use observed attributes, an encoder over the incident matrix, or biased second-order hypergraph walks trained with Skip-gram.The walk-based approach uses a second-order Markov process so nodes appearing in similar contexts obtain similar embeddings.
4 Results
Hyper-SAGNN was evaluated against DHNE and node2vec across reconstruction, prediction, classification, heterogeneous, mixed-edge, and outsider-identification settings. It generally improved performance while supporting heterogeneous hypergraphs and variable hyperedge sizes.
- 4.1 Evaluation Datasets: The evaluation used four DHNE benchmark datasets: GPS, MovieLens, drug, and wordnet.These datasets represent GPS, social, medicine, and semantic networks with distinct three-node hyperedge relations.
- 4.3 Performance Comparison with Existing Methods: Hyper-SAGNN captured network structure better than DHNE across all datasets with both encoder-based and random-walk-based representations.Network reconstruction was evaluated using AUC and AUPR.
- 4.3 Performance Comparison with Existing Methods: 24.6% increase in AUPR was observed on wordnet for unseen hyperedge prediction over DHNE.The random-walk and encoder variants showed only minor differences on reconstruction and hyperedge prediction.
- 4.3 Performance Comparison with Existing Methods: Hyper-SAGNN consistently achieved higher Micro-F1 and Macro-F1 than DHNE across training-data fractions for MovieLens and wordnet.The random-walk variant generally achieved the best classification performance.
- 4.4 Performance on Non-k-uniform Hypergraph: Including pairwise edges alongside hyperedges changed hyperedge-prediction AUC/AUPR by about 1% while preserving graph structure at different levels.The mixed training setting therefore did not cause obvious changes in hyperedge-prediction performance.
- 4.5 Outsider Identification: Outsider identification uses node probability scores and predicts the outsider as the node with the smallest probability after fine-tuning with min pooling.The task extends hyperedge prediction by identifying why a node group does not form a hyperedge.
5 Conclusion
Hyper-SAGNN is a general hypergraph representation-learning model that handles homogeneous or heterogeneous hypergraphs with uniform or non-uniform hyperedges. Its attention input is bounded by maximum hyperedge size, while future work proposes broader neighbor aggregation at additional computational cost.
- Hyper-SAGNN handles homogeneous and heterogeneous, uniform and non-uniform hypergraphs.
- The model addresses prior inability to predict hyperedges for non-k-uniform heterogeneous hypergraphs.
- Graph attention input size is bounded by maximum hyperedge size rather than the number of first-order neighbors.
- Future work could aggregate information over all first-order neighbors before computing node embeddings, with additional computational cost.
A.1 Comparison of Hyper-SAGNN with Its Variants
Across multiple datasets and tasks, Hyper-SAGNN generally matched or exceeded its two variants, with stronger advantages for the random-walk approach than for the encoder approach.
- The comparison evaluated AUC, AUPR, Micro-F1, and Macro-F1 across network reconstruction, hyperedge prediction, and node classification.Experiments covered MovieLens, wordnet, drug, and GPS, with five repeated trainings per experiment.
- Random-walk approach: Random-walk Hyper-SAGNN was best on all metrics for GPS, MovieLens, and wordnet.
- Encoder-based approach: Encoder-based models performed similarly on GPS and drug, while Hyper-SAGNN generally matched variant I and exceeded variant II on MovieLens and wordnet.
- Overall, the chosen Hyper-SAGNN structure achieved higher or comparable performance to both variants across multiple tasks and datasets.