Hybrid Graph: A Unified Graph Representation with Datasets and Benchmarks for Complex Graphs

Zehui Li, Xiangyu Zhao, Mingzhu Shen, Guy-Bart Stan, Pietro Liò, Yiren ZhaoarXiv 2023 · DOI · OpenReview

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.

Conceptual comparison of Hybrid, Hierarchical, and Hypergraphs.

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:

  1. MUSAE: 11 networks (social and Wikipedia) where hyperedges denote cliques or shared categories.
  2. GRAND: 10 gene regulatory networks where hyperedges are derived from chromosomal positions.
  3. 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.
Performance comparison between Simple GNNs and Hyper GNNs across different datasets.

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

Abstract

Graphs are widely used to encapsulate a variety of data formats, but real-world networks often involve complex node relations beyond only being pairwise. While hypergraphs and hierarchical graphs have been developed and employed to account for the complex node relations, they cannot fully represent these complexities in practice. Additionally, though many Graph Neural Networks (GNNs) have been proposed for representation learning on higher-order graphs, they are usually only evaluated on simple graph datasets. Therefore, there is a need for a unified modelling of higher-order graphs, and a collection of comprehensive datasets with an accessible evaluation framework to fully understand the performance of these algorithms on complex graphs. In this paper, we introduce the concept of hybrid graphs, a unified definition for higher-order graphs, and present the Hybrid Graph Benchmark (HGB). HGB contains 23 real-world hybrid graph datasets across various domains such as biology, social media, and e-commerce. Furthermore, we provide an extensible evaluation framework and a supporting codebase to facilitate the training and evaluation of GNNs on HGB. Our empirical study of existing GNNs on HGB reveals various research opportunities and gaps, including (1) evaluating the actual performance improvement of hypergraph GNNs over simple graph GNNs; (2) comparing the impact of different sampling strategies on hybrid graph learning methods; and (3) exploring ways to integrate simple graph and hypergraph information. We make our source code and full datasets publicly available at https://zehui127.github.io/hybrid-graph-benchmark/.
BibTeX
@misc{li2023hybrid,
  author = {Zehui Li and Xiangyu Zhao and Mingzhu Shen and Guy-Bart Stan and Pietro Liò and Yiren Zhao},
  title = {{Hybrid Graph: A Unified Graph Representation with Datasets and Benchmarks for Complex Graphs}},
  year = {2023},
  eprint = {2306.05108},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.05108},
}
Figure