Heterogeneous Hypergraph Embedding for Graph Classification

Xiangguo Sun, Hongzhi Yin, Bo Liu, Hongxu Chen, Jiuxin Cao, Yingxia Shao, Nguyen Quoc Viet Hung

TL;DR

This paper introduces a novel framework for learning representations of heterogeneous hypergraphs, which capture complex, multi-node relationships (like group chats or co-authorship) that standard graphs ignore. By using localized graph wavelets and an efficient polynomial approximation, the authors achieve state-of-the-art accuracy in node classification and spammer detection while significantly outperforming traditional Fourier-based methods in speed.

What Problem Does This Paper Address?

Most Graph Neural Networks (GNNs) operate on "dyadic" relationships—simple pairs of nodes connected by an edge. However, real-world data is often "polyadic." For example, a research paper isn't just a series of pairs between authors; it’s a single event involving a group. While hypergraphs (where one "edge" can connect any number of nodes) can model these higher-order relations, most existing hypergraph models assume all nodes and edges are of the same type (homogeneous).

The authors identify two main challenges:

  1. Heterogeneity: Real-world hypergraphs have different types of nodes and semantic relations (e.g., a user posting vs. a user commenting).
  2. Computational Complexity: Spectral hypergraph methods usually rely on the Fourier basis, which requires a time-consuming process called Laplacian decomposition—a major bottleneck for large datasets.

Methods

The authors propose the Heterogeneous Hypergraph Embedding framework, powered by a Hypergraph Wavelet Neural Network (HWNN). Their approach follows three main steps:

  1. Snapshot Decomposition: To handle heterogeneity, they project the complex hypergraph into a series of "snapshots." Each snapshot represents a specific type of relationship (defined by meta-paths or hyperedge types), making the sub-problems more manageable and parallelizable.
  2. Wavelet-Based Convolution: Instead of the standard Fourier transform (which is global and "blurry"), they use a Wavelet basis. Wavelets are localized in the vertex domain, meaning they better capture the immediate neighborhood of a node.
  3. Polynomial Approximation: To solve the speed issue, they use the Stone-Weierstrass theorem to create a polynomial approximation of the wavelet basis. This allows them to perform convolutions without ever having to calculate the expensive eigen-decomposition of the hypergraph Laplacian.

Datasets

The model was evaluated on four primary datasets:

  • Pubmed & Cora: Standard citation networks treated as hypergraphs (where citations or shared attributes form hyperedges).
  • DBLP: An academic network used specifically to test heterogeneous simple graphs.
  • Sina Weibo (Spammer Dataset): A real-world dataset of 14,774 users used for a case study on online spammer detection.

Key Insights and Ideas

  • Localization is King: The shift from Fourier to Wavelet transforms is the "aha moment." Because wavelets are localized, the model doesn't get "distracted" by distant, unrelated parts of the graph, leading to better feature extraction.
  • Sparsity Equals Speed: Wavelet matrices are naturally much sparser than Fourier matrices. This makes them far more compatible with modern GPU architectures, which thrive on sparse matrix operations.
  • Hypergraphs for Security: In the spammer detection case study, the authors found that spammers often hide their tracks in pairwise interactions but stand out when you look at their "group" behavior (hyperedges). This suggests hypergraphs are a potent tool for fraud and anomaly detection.

Key Results

  • Superior Accuracy: HWNN consistently outperformed six state-of-the-art baselines (including HGNN and GCN). On the Cora dataset, it achieved a 4.6% improvement in accuracy over the best baseline.
  • Significant Speedup: Thanks to the polynomial approximation, the model achieved a 1.45x to 1.55x speedup compared to Fourier-based hypergraph methods.
  • Spammer Detection: In the Sina Weibo case study, the model outperformed the second-best baseline by 21.8% in F1-score, proving that non-pairwise relationships are crucial for identifying malicious actors.

Limitations and Future Work

While the paper demonstrates strong results, a few areas remain open for exploration:

  • Hypergraph Construction: The model relies on four specific methods to build hyperedges (neighbor-based, attribute-based, etc.). The paper does not discuss a "learned" way to construct these hyperedges automatically from raw data.
  • Meta-path Selection: For heterogeneous data, the choice of meta-paths is currently a manual process based on domain knowledge. Automating this selection could make the model more "plug-and-play."
  • Dynamic Graphs: The current framework is designed for static snapshots; extending this to evolving, time-varying hypergraphs is a logical next step.

Summary updated

Abstract

Recently, graph neural networks have been widely used for network embedding because of their prominent performance in pairwise relationship learning. In the real world, a more natural and common situation is the coexistence of pairwise relationships and complex non-pairwise relationships, which is, however, rarely studied. In light of this, we propose a graph neural network-based representation learning framework for heterogeneous hypergraphs, an extension of conventional graphs, which can well characterize multiple non-pairwise relations. Our framework first projects the heterogeneous hypergraph into a series of snapshots and then we take the Wavelet basis to perform localized hypergraph convolution. Since the Wavelet basis is usually much sparser than the Fourier basis, we develop an efficient polynomial approximation to the basis to replace the time-consuming Laplacian decomposition. Extensive evaluations have been conducted and the experimental results show the superiority of our method. In addition to the standard tasks of network embedding evaluation such as node classification, we also apply our method to the task of spammers detection and the superior performance of our framework shows that relationships beyond pairwise are also advantageous in the spammer detection. To make our experiment repeatable, source codes and related datasets are available at https://xiangguosun.mystrikingly.com
BibTeX
@inproceedings{sun2021heterogeneous,
  author = {Xiangguo Sun and Hongzhi Yin and Bo Liu and Hongxu Chen and Jiuxin Cao and Yingxia Shao and Nguyen Quoc Viet Hung},
  title = {{Heterogeneous Hypergraph Embedding for Graph Classification}},
  booktitle = {WSDM},
  year = {2021},
  doi = {10.1145/3437963.3441835},
}
Figure