PaperlayerView exact revision on arXiv

Source-linked AI summary

UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks

Jing Huang, Jie Yang

arXiv:2105.00956v1cs.LGcs.SI

TL;DR

Hypergraph learning needs methods that preserve higher-order structure while adapting successful GNN architectures and deeper learning strategies. UniGNN provides a unified message-passing framework for this adaptation, with strong benchmark performance and a 1-GWL expressiveness bound. The paper also identifies limitations in existing HyperSAGE, including redundant computation, non-injective aggregation, and unresolved over-smoothing.

  • Problem

    Adapting powerful GNN variants and over-smoothing mitigation strategies directly to hypergraphs remains challenging, while existing methods can lose hypergraph information or fail to support classic GNN designs.

  • Method

    UniGNN unifies graph and hypergraph message passing to generalize GCN, GAT, GIN, and GraphSAGE, and introduces UniGCNII for deep hypergraph neural networks.

  • Results

    UniGNNs consistently outperform state-of-the-art approaches across hypergraph learning tasks; on DBLP semi-supervised hypernode classification, accuracy increases from 77.4% to 88.8%.

  • Takeaways & Limitations

    The framework provides expressive hypergraph representations and supports incorporating graph architectures and deep-learning strategies into hypergraph models.

  • Takeaways & Limitations

    HyperSAGE remains limited by redundant computation, poor parallelism, non-injective power means, and unresolved over-smoothing in deep hypergraph networks.

Abstract

from arXiv · show

Hypergraph, an expressive structure with flexibility to model the higher-order correlations among entities, has recently attracted increasing attention from various research domains. Despite the success of Graph Neural Networks (GNNs) for graph representation learning, how to adapt the powerful GNN-variants directly into hypergraphs remains a challenging problem. In this paper, we propose UniGNN, a unified framework for interpreting the message passing process in graph and hypergraph neural networks, which can generalize general GNN models into hypergraphs. In this framework, meticulously-designed architectures aiming to deepen GNNs can also be incorporated into hypergraphs with the least effort. Extensive experiments have been conducted to demonstrate the effectiveness of UniGNN on multiple real-world datasets, which outperform the state-of-the-art approaches with a large margin. Especially for the DBLP dataset, we increase the accuracy from 77.4\% to 88.8\% in the semi-supervised hypernode classification task. We further prove that the proposed message-passing based UniGNN models are at most as powerful as the 1-dimensional Generalized Weisfeiler-Leman (1-GWL) algorithm in terms of distinguishing non-isomorphic hypergraphs. Our code is available at \url{https://github.com/OneForward/UniGNN}.

1 Introduction

UniGNN addresses the challenge of adapting graph neural network designs to hypergraphs while supporting deeper architectures and analyzing their expressive power. It generalizes classic GNNs, introduces a deep variant for over-smoothing, and establishes a 1-GWL upper bound.

  • Motivation: Hypergraphs model higher-order relationships, but learning powerful representative embeddings for them remains challenging despite GNN success on graphs.Existing approaches either reduce hypergraphs to graphs or use specialized propagation that does not directly adapt classic GNN designs.
  • Research questions: Graph learning has developed architectures and strategies for mitigating over-smoothing, but their direct application to hypergraphs remains an open question.Over-smoothing occurs when node embeddings converge as layers are stacked and performance degrades.
  • Contributions: UniGNN generalizes GCN, GAT, GIN, and GraphSAGE into hypergraphs as UniGCN, UniGAT, UniGIN, and UniSAGE.The framework is presented as a unified approach for graph and hypergraph neural networks.
  • Contributions: UniGCNII is proposed as the first deep hypergraph neural network and is evaluated for resolving over-smoothing.This contribution transfers deep-network design to hypergraph neural networks.
  • Contributions: Message-passing-based UniGNNs are proved to be at most as powerful as the 1-dimensional Generalized Weisfeiler-Leman algorithm for distinguishing non-isomorphic hypergraphs.The result characterizes the expressive-power ceiling claimed for the proposed models.

2 Preliminaries

The preliminaries define graph and hypergraph structures and describe message passing, spectral hypergraph methods, and HyperSAGE's two-stage spatial aggregation. They also identify computational, expressiveness, and depth-related limitations of HyperSAGE.

  • Notations: A hypergraph allows each hyperedge to connect any number of vertices, extending ordinary graph edges beyond pairwise relationships.Vertices form a set, while each hyperedge is a non-empty subset of that set.
  • General GNNs: Message-passing GNNs update node embeddings by aggregating information from neighboring embeddings across layers.GCN, GAT, GIN, and GraphSAGE share this broad message-passing paradigm.
  • Spectral-based HyperGNNs: Spectral hypergraph methods use normalized or generalized hypergraph Laplacians that emphasize pairwise relations after representing hyperedges through graph-like connections.HyperGCN additionally uses weighted pairwise mediator edges.
  • Spatial-based HyperGNNs: HyperSAGE avoids reduction to graphs by aggregating hypergraph messages in two stages using intraedge neighborhoods and power mean functions.The method samples intraedge neighbors and applies successive aggregation operations.
  • Spatial-based HyperGNNs: HyperSAGE has redundant nested-loop computation, poor parallelism, non-injective aggregation that can miss multiplicities, and no solution to deep-hypergraph over-smoothing.These limitations affect efficiency, structural discrimination, and depth.

3 UniGNN: a Unified Framework

UniGNN reframes graph and hypergraph neural networks as a shared two-stage message-passing process, enabling GNN architectures and deepening strategies to transfer directly to hypergraphs.

  • 3 UniGNN: a Unified Framework: UniGNN unifies graph and hypergraph message passing through two permutation-invariant aggregation stages over vertices and incident hyperedges.The first stage aggregates vertices within each hyperedge; the second updates each vertex from its incident hyperedges.
  • 3 UniGNN: a Unified Framework: The framework directly generalizes GCN, GAT, GIN, and GraphSAGE into UniGCN, UniGAT, UniGIN, and UniSAGE for hypergraphs.When hyperedges represent ordinary graph neighborhoods, the formulation reduces to the corresponding graph message-passing model.
  • 3 UniGNN: a Unified Framework: UniGCN assigns less aggregation weight to high-degree hyperedges through their average vertex degree.The formulation uses the average degree of the vertices contained in each hyperedge.
  • 3 UniGNN: a Unified Framework: UniGAT reweights a center vertex’s neighboring hyperedges using attention, unlike HyperGAT’s preprocessing of hyperedges into a homogeneous vertex domain.The paper describes HyperGAT’s preprocessing as inflexible and unreliable in practice.
  • 3.2 Towards Deep Hypergraph Neural Networks: Existing hypergraph methods commonly use shallow two-layer networks, while deeper stacking causes over-smoothing and leaves hypergraph deepening unresolved.The paper motivates UniGCNII as a hypergraph adaptation of a graph strategy for addressing this problem.
  • 3.2 Towards Deep Hypergraph Neural Networks: UniGCNII transfers GCNII’s initial residual connections and identity mapping to hypergraphs, combining two-stage aggregation with initial and previous features.Experiments validate that UniGCNII circumvents over-smoothing as models become deeper.

4 How Powerful are UniGNNs?

The paper studies UniGNN expressiveness through the 1-GWL algorithm for hypergraph isomorphism. It shows that UniGNNs are bounded by 1-GWL, with injective aggregation and readout conditions characterizing stronger distinguishing ability.

  • 4 How Powerful are UniGNNs?: The paper introduces a variant of the 1-dimensional Generalized Weisfeiler-Leman algorithm for testing hypergraph isomorphism.The algorithm begins with identical initial labels and iteratively updates vertex labels using hypergraph structure.
  • 4 How Powerful are UniGNNs?: 1-GWL distinguishes two hypergraphs as non-isomorphic when their updated label multisets differ at some iteration.The proposition states that a successful 1-GWL test implies the hypergraphs are not equal.
  • 4 How Powerful are UniGNNs?: If a message-passing UniGNN distinguishes two non-isomorphic hypergraphs, 1-GWL also distinguishes them, bounding UniGNN expressiveness by 1-GWL.The analysis assigns identical features to all vertices so that distinctions depend on hypergraph structure.
  • 4 How Powerful are UniGNNs?: Local-level distinguishing requires both two-stage aggregation functions to be injective, while global-level distinguishing additionally requires an injective graph-level readout.The local structures are defined as k-height subtrees of the hypergraph’s incidence graph.

5 Experiments

Experiments evaluate UniGNN variants on semi-supervised classification, inductive prediction, deeper architectures, and self-loop sensitivity. UniGNNs generally outperform baselines, while UniGCNII supports deeper hypergraph models and self-loops are important for UniGCN and UniGAT.

  • Experimental setup: UniGNN variants are evaluated on academic coauthorship and cocitation hypergraphs for semi-supervised hypernode classification.The task predicts test-node labels from hypergraph structure, node features, and limited training labels.
  • Semi-supervised hypernode classification: UniGNNs consistently outperform baselines, improving DBLP accuracy from 77.4% to 88.8% with negligible variance.Results are generally more stable than baselines, as indicated by lower standard deviation.
  • Semi-supervised hypernode classification: Cora cocitation shows only slight improvement, where the mean hyperedge size is |M| = 3.0 ± 1.1 and clique-expansion information loss might be negligible.The paper attributes the smaller gain to the dataset’s relatively small hyperedges.
  • Self-loop sensitivity: Removing self-loops causes significant performance drops for UniGCN and UniGAT on most datasets.This supports the correctness of their formulations requiring self-loop preprocessing.
  • Inductive learning on evolving hypergraphs: In inductive learning, UniGNNs consistently score better across benchmark datasets, raising DBLP accuracy from 78.1% to 89.6% on seen data and from 73.2% to 83.4% on unseen data.The task predicts unseen-node labels from a historical hypergraph; 40% of vertices are randomly removed as unseen during training.
  • Deep-layered UniGNNs: UniGCNII generally improves as layers increase, outperforming the best shallow models on Cora, Pubmed, and Citeseer, while vanilla models degrade with depth.UniGCNII obtains competitive DBLP results and incorporates deep GNN designs into hypergraph learning.

6 Conclusion

The conclusion presents UniGNN as a unified framework that generalizes classic GNNs to hypergraphs and supports deep hypergraph learning. It reports stable gains over recent state-of-the-art methods and characterizes the expressive-power limit of the framework.

  • Conclusion: UniGNN naturally generalizes several classic GNNs to hypergraphs, with models that consistently achieve more stable performance than recent state-of-the-art methods.The conclusion also identifies UniGCNII as addressing over-smoothing in deep hypergraph neural networks.
  • Conclusion: The models learn expressive hypergraph representations that can benefit a broad range of downstream tasks.The paper identifies more powerful UniGNNs and hypergraph subtree kernels as future directions.

A.1 Proof for Proposition 1

The proof establishes that isomorphic hypergraphs preserve the correspondence of vertex labels through every UniGNN iteration. Therefore, the framework cannot distinguish graphs that are structurally identical up to bijective relabeling.

  • Proof of Proposition 1: For isomorphic hypergraphs, vertex and hyperedge bijections preserve hyperedge incidence across corresponding structures.The proof uses bijections f over vertices and g over hyperedges.
  • Proof of Proposition 1: Because isomorphic hypergraphs have equal vertex counts and matching initial labels, the induction begins with corresponding iteration-zero labels.The argument then assumes matching labels at iteration t.
  • Proof of Proposition 1: The induction step preserves matching labels at iteration t + 1, so corresponding UniGNN outputs remain equal for every iteration.The proof concludes the proposition by applying the induction rules across all iterations.

A.2 Proof for Proposition 2

The proof shows that UniGNN message passing cannot distinguish hypergraphs that 1-GWL leaves indistinguishable. It proceeds by matching initial labels and inductively preserving corresponding neighborhood aggregations.

  • Proof of Proposition 2: UniGNN and 1-GWL start from the same vertex labels or features, establishing the base case at iteration T = 0.The lemma explicitly notes that no second equation is needed when T = 0.
  • Proof of Proposition 2: The proof assumes a minimal iteration T where UniGNN distinguishes two hypergraphs although 1-GWL does not.This sets up a contradiction between the assumed UniGNN distinction and the 1-GWL equivalence.
  • Proof of Proposition 2: The contradiction proves that message-passing UniGNNs cannot distinguish any pair of hypergraphs that 1-GWL cannot decide as non-isomorphic.The final contradiction completes the proposition.
  • Proof of Proposition 2: If 1-GWL labels correspond through earlier iterations, the assumed correspondence at iteration T supplies the conditions needed for the induction lemma.The proof tracks matching labels across t = 0, ..., T − 1 and iteration T.
  • Proof of Proposition 2: Matching 1-GWL neighborhoods make UniGNN’s two-stage aggregations produce identical outputs for corresponding vertices.This contradicts the assumption that UniGNN distinguishes the hypergraphs.

A.3 Proof for Theorem 1

The proof constructs injective mappings across UniGNN iterations, establishing an upper bound by 1-GWL and conditions for matching its distinguishing power. Local substructure discrimination requires only the local-level conditions, whereas graph-level discrimination additionally requires an injective readout.

  • Proof strategy: The proof initializes an injective mapping because corresponding vertex labels/features are identical at t = 0.
  • Proof strategy: Assuming an injective mapping at iteration t, composing the two injective aggregation functions yields an injective mapping at iteration t + 1.
  • Proof strategy: Induction therefore establishes an injective mapping M_t throughout the message-passing process.
  • Expressive power: UniGNN’s graph-level expressive power is upper bounded by 1-GWL, and an injective global READOUT enables it to distinguish every pair that 1-GWL distinguishes.
  • Local substructures: For local substructures, injective two-stage aggregation is sufficient because the proof remaps the incidence-graph neighborhood to a subhypergraph without using global READOUT.

B.2 Experimental Details

The experiments use repeated training across multiple splits and random seeds, with separate protocols for semi-supervised classification, evolving hypergraphs, and deep-layer models.

  • Semi-supervised hypernode classification: Semi-supervised hypernode classification trains each model for 200 epochs and reports the final-epoch performance over 80 runs.The 80 runs use 10 train/test splits and 8 random seeds.
  • Inductive learning on evolving hypergraphs: Inductive learning on evolving hypergraphs generally uses 200 epochs, while PubMed uses zero input dropout and 300 epochs.Each model and dataset is evaluated over 80 runs with 10 train/test splits and 8 random seeds.
  • Performance of deep-layered UniGNNs: Deep-layer experiments reserve 20% of the original testing split for validation and train UniGCNII for 1000 epochs with patience-150 early stopping.Shallow models are selected by their highest validation score, whereas the remaining 80% forms the new test split.

C Details of Datasets

The dataset details summarize structural, feature, class, and labeling statistics, while distinguishing the two Cora dataset variants by their coauthorship and cocitation settings.

  • Dataset statistics: The reported statistics include hyperedge count, average hyperedge size, input-feature dimension, number of classes, and label rate.The passage defines d, C, and η as feature dimension, class count, and label rate, respectively.
  • Dataset variants: Cora 1 denotes the Cora coauthorship dataset, whereas Cora 2 denotes the Cora cocitation dataset.
  • Dataset statistics: Table 6 summarizes the statistics of the datasets.
Loading 2105.00956v1…