PaperlayerView exact revision on arXiv

Source-linked AI summary

HyperSAGE: Generalizing Inductive Representation Learning on Hypergraphs

Devanshu Arya, Deepak K. Gupta, Stevan Rudinac, Marcel Worring

arXiv:2010.04558v1cs.LGstat.ML

TL;DR

Pairwise graphs miss higher-order relations, while existing hypergraph methods can fail to infer representations for unseen nodes. HyperSAGE uses two-level message passing within and across hyperedges; it is reported to outperform other methods on representative datasets and to produce more stable node-classification results.

  • Problem

    Pairwise connections alone cannot represent some collective relations, and existing hypergraph frameworks can fail to infer characteristics for nodes unseen during training.

    Source: §1 · pp. 1–2

  • Method

    HyperSAGE learns inductively with two-level neural message passing that aggregates within and across hyperedges without reducing the hypergraph to a graph.

    Source: §1 · p. 2, §3.2 · p. 4, §3.3 · p. 5

  • Results

    On representative datasets, HyperSAGE outperforms other hypergraph-learning methods; it is also reported as more stable, with reduced variance on node-classification tasks.

    Source: §1 · p. 2, §5 · p. 8

  • Takeaways & Limitations

    The inductive framework supports learning representations for previously unseen hypergraph nodes and is also applicable to graphs.

    Source: §1 · p. 2, §3.3 · p. 5

    A stated design condition is global-neighborhood invariance when a hyperedge is split into smaller hyperedges that share dominant nodes.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

Graphs are the most ubiquitous form of structured data representation used in machine learning. They model, however, only pairwise relations between nodes and are not designed for encoding the higher-order relations found in many real-world datasets. To model such complex relations, hypergraphs have proven to be a natural representation. Learning the node representations in a hypergraph is more complex than in a graph as it involves information propagation at two levels: within every hyperedge and across the hyperedges. Most current approaches first transform a hypergraph structure to a graph for use in existing geometric deep learning algorithms. This transformation leads to information loss, and sub-optimal exploitation of the hypergraph's expressive power. We present HyperSAGE, a novel hypergraph learning framework that uses a two-level neural message passing strategy to accurately and efficiently propagate information through hypergraphs. The flexible design of HyperSAGE facilitates different ways of aggregating neighborhood information. Unlike the majority of related work which is transductive, our approach, inspired by the popular GraphSAGE method, is inductive. Thus, it can also be used on previously unseen nodes, facilitating deployment in problems such as evolving or partially observed hypergraphs. Through extensive experimentation, we show that HyperSAGE outperforms state-of-the-art hypergraph learning methods on representative benchmark datasets. We also demonstrate that the higher expressive power of HyperSAGE makes it more stable in learning node representations as compared to the alternatives.

1 INTRODUCTION

Hypergraphs represent multi-way relations that graphs cannot capture through pairwise links alone, but existing learning methods often reduce them to graphs or cannot handle unseen nodes. HyperSAGE uses inductive, two-level message passing to retain hypergraph information while supporting flexible aggregation and neighborhood sampling.

1 INTRODUCTION

  • Hypergraphs represent multi-way relations across objects, which pairwise graph connections may fail to capture.Source: §1 · p. 1
  • Graph reductions can lose hyperedge information, while existing hypergraph methods are often transductive and cannot predict for previously unseen nodes.Source: §1 · p. 2
  • HyperSAGE jointly captures intra-relations within hyperedges and inter-relations across hyperedges through message passing.Source: §1 · p. 2
  • HyperSAGE is inductive, enabling predictions on previously unseen nodes and use with evolving hypergraphs.Source: §1 · p. 2
  • HyperSAGE supports neighborhood sampling and flexible choices for aggregating neighborhood information.Source: §1 · p. 2
  • HyperSAGE is reported to be more stable than state-of-the-art methods, with more accurate node classification and reduced output variance.Source: §1 · p. 2

2 RELATED WORK

Prior hypergraph-learning approaches include matrix- and tensor-based formulations and methods that reduce hypergraphs to graphs. HyperSAGE instead draws on message passing to use hypergraph structure while supporting inductive learning.

2 RELATED WORK

  • Matrix formulations can rigidly describe higher-order structure, while tensor formulations can be computationally expensive and restricted to small datasets; some tensor methods are limited to uniform hypergraphs.Source: §2 · p. 3
  • Clique-expansion methods apply graph convolutions after reducing hypergraphs, but can discard structural information and yield unreliable learning performance.Source: §2 · p. 3
  • HyperGCN uses mediator-weighted pairwise edges, but for some cases such as Fano planes it is equivalent to clique expansion.Source: §2 · p. 3
  • HyperSAGE draws inspiration from GraphSAGE and avoids matrix- or tensor-based formulations to use hypergraph information in an inductive message-passing framework.Source: §2 · p. 3

3 PROPOSED MODEL: HYPERSAGE

HyperSAGE learns node representations through nested intra-hyperedge and inter-hyperedge aggregation without requiring hypergraph-to-graph reduction. Its framework supports unseen nodes and flexible aggregation choices.

3.1 PRELIMINARIES

  • Hyperedges can contain different numbers of nodes; graphs are the M=2 special case, with intra-edge, inter-edge, and sampled condensed neighborhoods defined.Source: §3.1 · pp. 3–4

3 PROPOSED MODEL: HYPERSAGE

  • HyperSAGE combines intra-edge and inter-edge message passing to learn node representations, including for previously unseen nodes.The framework applies feature aggregation across hyperedges at each of its L layers.Source: §3 · p. 3, §3.2 · p. 4, §3.3 · p. 5

3.2 GENERALIZED MESSAGE PASSING FRAMEWORK

  • The nested F2(F1(·)) scheme first aggregates within hyperedges and then across them, while decoupling message passing from the aggregation-function choice.Source: §3.2 · pp. 4–5
  • Aggregation should be permutation-invariant and preserve dominant-node representations when hyperedges split without changing a node’s global neighborhood.The framework identifies these as properties for accurate hypergraph message aggregation.Source: §3.2 · pp. 4–5
  • Generalized means span arithmetic mean at p=1 to max pooling for large p; matched intra-edge and inter-edge powers with scaling support global-neighborhood invariance.The scaling term balances bias from varying hyperedge cardinalities.Source: §3.2 · p. 5
  • Neighborhood sampling can reduce training-time computation and act as regularization; using full neighborhoods at test time avoids randomness in predictions.Source: §3.2 · p. 5

3.3 INDUCTIVE LEARNING ON HYPERGRAPHS

  • HyperSAGE unifies graph-based formulations: GCN is a special case with |M|=2 and F2=M1, while GraphSAGE can be matched with specified aggregators and sampling.Source: §3.3 · p. 6

4 EXPERIMENTS

Experiments compare HyperSAGE with existing methods on document-topic classification and test its stability, aggregation choices, and generalization to unseen nodes. HyperSAGE improves on benchmark baselines in most reported comparisons and performs well on unseen nodes.

4.1 EXPERIMENTAL SETUP

  • Experiments use four co-authorship and co-citation datasets, two-layer neural networks, and 80 runs per method and dataset for the benchmark comparison.The 80 runs comprise 10 data splits across eight random weight initializations.Source: §4.1 · p. 6, §4.2 · p. 6

4.2 SEMI-SUPERVISED NODE CLASSIFICATION ON HYPERGRAPHS

  • HyperSAGE variants consistently outperform benchmark methods except on Cora co-citation, while gains over the best baselines reach 6.3% on DBLP and 4.3% on Pubmed.The authors report no improvement over HGNN on Cora co-citation.Source: §4.2 · pp. 6–7, Table 1 · p. 7
  • Across five train-test ratios, HyperSAGE has lower prediction standard deviation than HyperGCN and significantly outperforms it at smaller training ratios.Both methods improve with more training data and perform approximately equally at a 1/3 train-test ratio.Source: §4.2 · p. 7, Figure 3 · p. 7
  • Higher generalized-mean p usually reduces performance; p = −1 lowers performance across cases, while p = 0.01 fits Pubmed best.The aggregation study varies p and the number of sampled neighbors α.Source: §4.2 · pp. 7–8, Table 2 · p. 8
  • The effect of neighborhood sample count α varies by dataset: DBLP improves as α increases, while Pubmed improves through α = 5 before dropping slightly.The authors suggest stochastic sampling may regularize noisy hyperedges; for Pubmed, sampling is almost absent at α = 10.Source: §4.2 · p. 8

4.3 INDUCTIVE LEARNING ON EVOLVING GRAPHS

  • On unseen nodes from four evolving-graph datasets, HyperSAGE performs significantly better than MLP+HLR, with results not drastically different from its seen-node results.The datasets are DBLP, Pubmed, Citeseer, and Core; each was split at a 1:4 train-test ratio.Source: §4.3 · p. 8, Table 3 · p. 8

5 CONCLUSION

HyperSAGE is a generic message-passing framework for inductive hypergraph learning that uses higher-order structure without reducing hypergraphs to regular graphs.

5 CONCLUSION

  • HyperSAGE uses the inherent higher-order relations in hypergraphs without reducing them to regular graphs.The conclusion reports that numerical experiments on representative datasets show it outperforms other hypergraph learning methods.Source: §5 · p. 8
  • Its flexible aggregation and neighborhood sampling framework can derive graph-learning variants such as GCN and GraphSAGE.The authors present it as a framework for node representation learning on both hypergraphs and graphs.Source: §5 · p. 9

A EXPERIMENTS: ADDITIONAL DETAILS

The additional-details section describes multi-class document-topic prediction on co-authorship and co-citation datasets.

A EXPERIMENTS: ADDITIONAL DETAILS

A.1 DATASET DESCRIPTION

The datasets represent documents as nodes and co-authorship or co-citation relations as hyperedges, with bag-of-words node features.

A.1 DATASET DESCRIPTION

  • Each document is represented as a node in the co-authorship and co-citation datasets.Source: §A.1 · p. 11
  • Hyperedges group documents co-authored by an author or documents cited together by one document.Source: §A.1 · p. 11
  • Each node uses bag-of-words features, and the experiments use the dataset and train-test splits from Yadati et al. (2019).Source: §A.1 · p. 11

A.2 IMPLEMENTATION DETAILS

All models use hyperparameters similar to prior work by Kipf & Welling (2016), including a 32-unit hidden layer and 150 training epochs.

A.2 IMPLEMENTATION DETAILS

  • The models use a hidden layer size of 32 and train for 150 epochs.Both settings are part of the shared hyperparameter configuration.Source: §A.2 · p. 11
  • The shared optimization settings are a learning rate of 0.01 and weight decay of 0.0005.Source: §A.2 · p. 11
  • Dropout is set to 0.5, and explicit Laplacian regularization uses λ = 0.001.Source: §A.2 · p. 11

B CHOICE OF INTER-EDGE AND INTRA-EDGE AGGREGATIONS

This appendix derives conditions for preserving aggregation when a hyperedge is split, assuming matched aggregation exponents and a specified neighbor assignment. It gives corresponding weights for the split edges.

B CHOICE OF INTER-EDGE AND INTRA-EDGE AGGREGATIONS

  • The proof expresses the aggregation output F1(vi) using generalized means before rearranging terms.The appendix also states that the inter-edge aggregation F2(·) can be expressed in this derivation.Source: B CHOICE OF INTER-EDGE AND INTRA-EDGE… · pp. 11–13
  • The derivation seeks weights that make the original inter-edge aggregation F2(vi) equal the aggregation ˜F2(vi) after splitting.It assumes p1 = p2 and matches terms to solve for the weights.Source: B CHOICE OF INTER-EDGE AND INTRA-EDGE… · p. 12
  • The weight derivation assumes every other neighbor of vi in the original hyperedge is assigned to only one resulting hyperedge.This permits matching the coefficients of neighbor features to solve for wq.Source: B CHOICE OF INTER-EDGE AND INTRA-EDGE… · p. 13
  • For a split hyperedge, the aggregations hold when p1 = p2 and each split-edge weight is |N(vi,e)| / |N(vi,eq)|.The equivalent formulation for edges obtained from a single hyperedge uses |N(vi,e)| / |N(vi)|.Source: B CHOICE OF INTER-EDGE AND INTRA-EDGE… · p. 13
Loading 2010.04558v1…