Introduction
Graph Neural Networks (GNNs) have traditionally focused on pairwise relationships between nodes. However, real-world systems—such as academic citations, biological pathways, and social networks—often exhibit more complex structures, including multi-node group interactions (hyperedges) and nested organizational levels (hierarchies). While specialized models exist for hypergraphs and hierarchical graphs, they are frequently treated in isolation and evaluated on small-scale, simplistic datasets like Cora or CiteSeer. This paper introduces Hybrid Graphs, a unified mathematical framework that integrates these diverse relational structures, alongside the Hybrid Graph Benchmark (HGB) to facilitate rigorous evaluation on large-scale, real-world data.
The Hybrid Graph Framework
The authors define a Hybrid Graph as $G = (V, E, f_p)$, where $V$ represents the set of nodes, $E$ is a set of hyperedges containing two or more nodes, and $f_p$ is an acyclic parent function defining the hierarchy. This generalized definition allows for the representation of standard graphs, hypergraphs, and hierarchical graphs by adjusting specific constraints.
To address scalability, the authors introduced HybridGraphSAINT, a sampling strategy based on GraphSAINT that preserves higher-order relationships in subgraphs. Furthermore, they proposed Linear Probe GNNs (LP-GNNs) as a baseline. LP-GNNs operate by running two distinct GNN architectures (e.g., a standard GCN and a Hypergraph Convolution) in parallel and concatenating their outputs, effectively leveraging both pairwise and group-level information.
The Hybrid Graph Benchmark (HGB)
The HGB suite comprises 23 datasets across three primary domains:
- MUSAE: 11 networks (social and Wikipedia) where hyperedges denote cliques or shared categories.
- GRAND: 10 gene regulatory networks where hyperedges are derived from chromosomal positions.
- Amazon: 2 e-commerce datasets where hyperedges are constructed via clustering product images using CLIP embeddings.
These datasets provide a significant increase in scale and complexity compared to traditional benchmarks, offering a more realistic environment for testing advanced GNN architectures.
Experimental Results and Key Insights
The benchmarking process revealed several critical findings regarding the performance of complex graph models:
- The Complexity Paradox: Sophisticated hypergraph GNNs do not consistently outperform simpler models on large-scale networks. In many MUSAE and GRAND datasets, standard GCNs performed comparably to or better than specialized architectures.
- The Power of Hybrid Information: The most significant performance gains were observed when models integrated both pairwise and higher-order information. LP-GNN variants consistently outperformed standalone models, suggesting that different relational levels provide complementary semantic signals.
- Sampling as a Regularizer: HybridGraphSAINT not only improved training efficiency but also enhanced accuracy, likely by mitigating the over-smoothing problem common in deep GNNs.
On the Amazon datasets, hypergraph GNNs showed a distinct advantage, indicating that hyperedges derived from image clusters capture semantic relationships that simple co-purchase links overlook.
Conclusion and Future Work
This work establishes a unified foundation for complex graph representation and provides the necessary tools for large-scale evaluation. While the current HGB focuses on "shallow" hierarchies, future research will explore deeper multi-layered structures, more sophisticated fusion operations for hybrid information, and refined methods for hyperedge construction.
Summary updated