PaperlayerView exact revision on arXiv

Source-linked AI summary

You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks

Eli Chien, Chao Pan, Jianhao Peng, Olgica Milenkovic

arXiv:2106.13264v4cs.LGcs.AI

TL;DR

Existing hypergraph neural networks often use heuristic propagation rules, while different propagation schemes have distinct limitations across hypergraph structures and tasks. AllSet unifies these schemes through learnable compositions of two multiset functions, with Deep Sets and Set Transformer-based layers. Across ten benchmark and three newly curated datasets, AllSet consistently matches or outperforms other hypergraph neural networks.

  • Problem

    Existing hypergraph neural networks rely largely on heuristic propagation rules, while clique-based and tensor-based schemes have different limitations across datasets and tasks.

  • Method

    AllSet represents hypergraph neural-network layers as compositions of two learnable multiset functions and instantiates them with Deep Sets- and Set Transformer-inspired architectures.

  • Results

    AllSet matches or outperforms other hypergraph neural networks across ten benchmark and three newly curated datasets, with AllSetTransformer leading baselines on nine of ten datasets.

  • Takeaways & Limitations

    AllSet provides a unified framework that covers clique-based, tensor-based, and many existing hypergraph propagation rules while learning propagation schemes for individual datasets and tasks.

  • Takeaways & Limitations

    Zprop can suffer numerical instability for large hyperedges and has only been studied for d-uniform hypergraphs; HCHA's attention module requires suitable hyperedge features.

Abstract

from arXiv · show

Hypergraphs are used to model higher-order interactions amongst agents and there exist many practically relevant instances of hypergraph datasets. To enable efficient processing of hypergraph-structured data, several hypergraph neural network platforms have been proposed for learning hypergraph properties and structure, with a special focus on node classification. However, almost all existing methods use heuristic propagation rules and offer suboptimal performance on many datasets. We propose AllSet, a new hypergraph neural network paradigm that represents a highly general framework for (hyper)graph neural networks and for the first time implements hypergraph neural network layers as compositions of two multiset functions that can be efficiently learned for each task and each dataset. Furthermore, AllSet draws on new connections between hypergraph neural networks and recent advances in deep learning of multiset functions. In particular, the proposed architecture utilizes Deep Sets and Set Transformer architectures that allow for significant modeling flexibility and offer high expressive power. To evaluate the performance of AllSet, we conduct the most extensive experiments to date involving ten known benchmarking datasets and three newly curated datasets that represent significant challenges for hypergraph node classification. The results demonstrate that AllSet has the unique ability to consistently either match or outperform all other hypergraph neural networks across the tested datasets.

1 INTRODUCTION

Hypergraphs capture higher-order relationships that ordinary graphs miss, but existing hypergraph learning methods rely on propagation rules with important limitations. AllSet provides a general, learnable multiset-function framework and shows strong node-classification performance across broad benchmarks.

  • Motivation: Hypergraphs model higher-order relationships by connecting more than two nodes, extending graphs beyond pairwise interactions.This capability is relevant to machine-learning applications where modeling high-order relations can improve learning performance.
  • Motivation: Clique expansion replaces hyperedges with cliques but can distort the original structure and reduce learning performance.Many hypergraph neural-network propagation schemes are based on clique expansion or its variants.
  • Motivation: Existing hypergraph propagation rules have different strengths and weaknesses, motivating a framework that can encompass and learn among them.Tensor-based propagation can outperform clique-expansion schemes on some tasks, while Zprop also has numerical and applicability limitations.
  • AllSet framework: AllSet unifies clique-based, tensor-based, and many existing hypergraph neural-network propagation rules as compositions of two multiset functions.The framework also generalizes Message Passing Neural Networks from graphs to hypergraphs.
  • AllSet framework: AllDeepSets and AllSetTransformer provide end-to-end trainable layers inspired by Deep Sets and Set Transformer for learning hypergraph propagation schemes.These layers can be plugged into most graph neural networks to generalize them to hypergraphs.
  • Evaluation: AllSetTransformer outperforms the best baseline by close to 4% accuracy on Yelp and Zoo, 3% on Walmart, and matches or outperforms baselines on nine of ten datasets.The experiments compare ten baseline methods on ten benchmark datasets and three newly curated challenging datasets.

2 BACKGROUND

Hypergraph neural networks use propagation rules ranging from clique-expansion methods to tensor-based schemes, each with distinct trade-offs. These approaches motivate a framework that can accommodate different propagation choices.

  • Hypergraphs generalize graphs by allowing hyperedges to connect more than two nodes.
  • CE-based propagation on hypergraphs: Clique expansion replaces each hyperedge with a weighted clique, but can distort the original hypergraph and reduce learning performance.
  • CE-based propagation on hypergraphs: Many hypergraph convolutional layers, including HGNN and related methods, implement clique-expansion propagation with normalization or nonlinear hyperedge weights.
  • Tensor-based propagations: Tensor-based methods such as Multilinear PageRank relate hypergraph propagation to Z eigenproblems without using clique expansion.
  • Tensor-based propagations: Zprop can suffer numerical instability for large hyperedges and is studied only for uniform hypergraphs, limiting its relevance to general hypergraph learning.

3 ALLSET: ONE METHOD TO BIND THEM ALL

AllSet unifies hypergraph propagation by expressing layers as compositions of two multiset functions. It contains existing propagation methods as special cases while offering greater expressiveness and a computationally efficient formulation.

  • AllSet unifies existing hypergraph propagation methods by composing two permutation-invariant multiset functions.
  • The framework represents node-to-hyperedge and hyperedge-to-node updates through functions fV→E and fE→V applied to hidden representations.
  • AllSet can use node and hyperedge features when available, or all-zero initial representations otherwise, while allowing the hypergraph to support degree normalization.
  • The formulation in (5) is more computationally and memory efficient than (6) because each hyperedge uses one hidden representation instead of |e| distinct representations.
  • CEpropH, CEpropA, and Zprop are special cases of AllSet under suitable multiset functions, including sums for CE rules and products for Zprop.
  • HGNN, HCHA, HNHN, HyperSAGE, and HyperGCN are special cases of AllSet, while the listed layers are strictly less expressive than AllSet.
  • MPNN is a special case of AllSet on graphs, making AllSet a hypergraph generalization of MPNN.

4 HOW TO LEARN ALLSET LAYERS

AllSet learns hypergraph propagation through two multiset functions, instantiated with Deep Sets and Set Transformer architectures. These layers are permutation-aware universal approximators under finite multiset sizes, giving them greater expressive power than prior described hypergraph neural networks.

  • AllSet learns the multiset functions fV→E and fE→V for each dataset and task rather than fixing propagation rules.
  • AllDeepSets parameterizes multiset functions with multilayer perceptrons applied through the Deep Sets construction.
  • AllSetTransformer uses attention-based multiset processing, motivated by Set Transformer’s ability to learn the importance of individual contributing terms.
  • AllSetTransformer’s two multiset functions are permutation invariant and universal approximators when input multiset sizes are finite.
  • Because hyperedge sizes and node degrees are finite in practice, AllDeepSets and AllSetTransformer match AllSet’s expressive power and exceed prior described layers.
  • Full Set Attention Blocks and two-step pooling could extend AllSet, but efficient implementation and use of second-function arguments remain future work.
  • AllDeepSets and AllSetTransformer share universal expressive power, yet AllDeepSets performs worse than AllSetTransformer in practice.

5 RELATED WORKS

Related work spans hypergraph learning, multiset-function architectures, and graph-based unification approaches. AllSet is positioned among methods that model or analyze hypergraph propagation, while adapting propagation rules rather than fixing them.

  • Hypergraph learning: Hypergraph learning methods address higher-order structure, community detection, and alternatives to clique expansion, alongside several neural architectures.
  • Hypergraph learning: Some theoretical propagation studies interpolate between CE-prop and Z-prop, whereas AllSet learns propagation rules adaptively.
  • Star expansion, UniGNN and Heterogeneous GNNs: UniGNN also unifies hypergraph and graph neural network models, with Uni-GIN related to AllDeepSets through their GIN generalization.
  • Learning (multi)set functions: Deep Sets provides a universal parameterization for multiset functions, which are used across causality discovery, few-shot classification, and conditional prediction.
  • Table 1 defines |e| as hyperedge size and d_v as node degree in its dataset statistics.

6 EXPERIMENTS

Experiments evaluate AllSet on semi-supervised transductive node classification across established and newly curated datasets against ten baseline models. AllSetTransformer is robust across diverse datasets, with reported gains and comparable complexity.

  • The study uses semi-supervised transductive node classification with 50%/25%/25% train-validation-test splits and aggregates 20 experiments.
  • AllSetTransformer and AllDeepSets are compared with ten baseline models in full-batch and mini-batch settings.
  • The evaluation covers ten existing datasets and three newly curated datasets from multiple application domains.
  • AllSetTransformer is reported as the most robust model with the best overall performance, while every baseline performs poorly on at least two datasets.
  • 11.01% accuracy separates AllSetTransformer from UniGCNII on Walmart(1).
  • 9.14% and 16.89% are the reported AllSetTransformer accuracy gains over HAN on Mushroom and Walmart(1), respectively.
  • AllSet has complexity comparable to baseline hypergraph neural networks, so its reported performance gains do not require high computational complexity.
  • AllDeepSets trails AllSetTransformer despite equal universal expressive power, while clique-expansion methods can become memory-inefficient for large hyperedges.

7 ETHICS STATEMENT

The paper reports no known ethical issues and states that the three newly curated datasets contain no private personally identifiable information.

  • The authors report no potential ethical issues and state that the newly curated datasets contain no private personally identifiable information.

8 REPRODUCIBILITY STATEMENT

The paper emphasizes reproducibility through shared code, datasets, tested methods, and a standardized evaluation pipeline. The supplementary materials are intended to make the reported experiments readily repeatable.

  • Reproducibility: The authors built a PyTorch Geometric pipeline to standardize hypergraph neural network evaluation.The pipeline follows the style of recent GNN benchmarking work.
  • Reproducibility: The supplementary materials include all datasets and integrate all tested methods in the released code.The authors state that experiment results can be reproduced with a one-line command.
  • Framework verification: AllSet’s framework recovers CEpropH, CEpropA, and Zprop through suitable choices of its two multiset functions.The constructions use sums for the clique-expansion rules and product-plus-sum functions for Zprop.
  • Framework verification: The Zprop recovery uses a product for fV→E and a sum for fE→V, while ignoring the second input.The resulting composition matches the Zprop update rule.

D PROOF OF THEOREM 3.4

Theorem 3.4 is established by constructing AllSet choices that reproduce existing hypergraph neural network layers. The proof then argues that these earlier layers are strictly less expressive because they cannot approximate arbitrary multiset functions.

  • Special-case constructions: HGNN is recovered by choosing both AllSet multiset functions as weighted sums using node degrees, edge degrees, and edge weights.The second input is ignored in this construction.
  • Special-case constructions: HCHA is recovered because its attention expressions are permutation invariant and can serve as the two AllSet multiset functions.Combining the two functions reproduces the HCHA layer.
  • Special-case constructions: HyperGCN is represented by multiset functions based on hyperedge-wide node features and the layer’s specified pair-selection weights.Combining the constructed functions yields the HyperGCN layer.
  • Special-case constructions: HNHN is a special case because its update expressions use degree normalizations and linear transformations that define the two multiset functions.The hyperparameters α and β remain tunable within the recovered layer.
  • Special-case constructions: HyperSAGE is recovered using an lp power mean for vertex-to-edge aggregation and a composition of multiset functions for edge-to-vertex aggregation.The construction establishes the first universality claim for AllSet.
  • Expressiveness: Existing layers are strictly less expressive than AllSet because their components cannot approximate arbitrary multiset functions.Examples include HGNN’s inability to model products and HyperSAGE’s reliance on a linear transformation.

E PROOF OF THEOREM 3.5

Theorem 3.5 shows that message passing on graphs fits within AllSet. The proof also establishes permutation-invariant universal approximation for the multiset functions used by the AllSetTransformer construction, while noting efficiency limits of line expansion.

  • MPNN inclusion: The MPNN framework is recovered from AllSet by choosing fV→E and fE→V to implement neighborhood message aggregation and node updates.The functions Mt and Ut supply the propagation-step message and update operations.
  • MPNN inclusion: MPNN is a special case of AllSet when applied to graphs.Because graphs are special cases of hypergraphs, AllSet serves as a hypergraph generalization of MPNN.
  • Expressiveness: The AllSet multiset functions are universal approximators for permutation-invariant functions under the stated finite-input condition.The argument applies separately to fV→E and fE→V.
  • Efficiency: Line expansion can create Θ(d|E|) nodes and Θ(d^2|E|^2) edges for a fully connected d-uniform hypergraph.The resulting memory and computational costs motivate defining AllSet layers directly on hypergraphs.
  • H-propagation caveat: The H-propagation rule may produce imaginary features because its 1/(d−1)-th root is not guaranteed to preserve real-valued updates.The paper leaves a real-valued formulation as an open question.

I ADDITIONAL DETAILS PERTAINING TO THE TESTED DATASETS

The evaluation combines ten existing benchmark datasets with three newly introduced datasets. The new datasets derive hypergraphs from shared activity or membership and provide task-specific node features and labels.

  • Dataset statistics: Table 3 reports full dataset statistics, including hyperedge size |e| and node degree d_v.These quantities summarize structural properties of the tested datasets.
  • Dataset composition: The testbed contains 10 existing benchmark datasets from the hypergraph neural network literature.These include cocitation and coauthorship networks adapted from prior work.
  • Dataset composition: The authors introduce three datasets adapted from Yelp, House, and Walmart.These datasets are designed as additional evaluation settings for hypergraph learning.
  • New datasets: Yelp represents restaurants as nodes and connects restaurants visited by the same user in hyperedges.Node labels are average review ratings from 1 to 5 stars in 0.5-star increments.

J COMPUTATIONAL EFFICIENCY AND EXPERIMENTAL SETTINGS

The experiments report training-time measurements under specified hardware and tuned hyperparameter settings, with separate summaries for best choices and averages across choices.

  • Computational environment: Tests ran on a 48-core Linux machine with 376GB system memory and two NVIDIA Tesla P100 GPUs.Reported training times exclude one-time hypergraph preprocessing.
  • Hyperparameter settings: Hyperparameters include hidden dimensions, learning rates, weight decays, and attention heads where applicable.Hidden dimensions are tuned over {64, 128, 256, 512}, learning rates over {0.1, 0.01, 0.001}, and weight decays over {0, 0.00001}.
  • Architecture settings: AllSetTransformer and AllDeepSets use one full V →E →V propagation layer, whereas most other methods use two layers.HyperGCN and HAN have implementation-specific hidden-dimension constraints, and some models do not use attention-head hyperparameters.
  • Runtime reporting: Table 4 reports mean running time and standard deviation for each method at its best hyperparameter choice.Times are reported in seconds or hours per run.
  • Runtime reporting: Table 5 reports average running time and standard deviation across all hyperparameter choices.This complements the best-configuration runtime summary with an across-choice average.
Loading 2106.13264v4…