HyperGraphX: Graph Transductive Learning with Hyperdimensional Computing and Message Passing

AI summary

Overview

• Research area: Graph machine learning — specifically transductive node classification, sitting at the intersection of Graph Neural Networks (GNNs) and hyperdimensional computing (HDC).
• Technical level: Intermediate. Readers need some familiarity with graph convolution, message passing, and the idea of high-dimensional vector representations, but the paper's core idea is described with relatively simple algebra.
• Scope: The paper presents HyperGraphX, a weightless graph convolution algorithm that replaces learnable neural transformations with HDC binding and bundling operations, and evaluates it against four GNN families and state-of-the-art HDC graph learners on three homophilic and four heterophilic graphs.

What This Paper Is About

GNNs achieve strong accuracy on graph tasks but are expensive: their irregular memory access patterns and repeated matrix multiplications create high bandwidth and energy costs. Hyperdimensional computing offers cheap, noise-tolerant operations on large vectors and is well suited to emerging hardware, but existing HDC graph methods (RelHD, GraphHD, HDGL) generally trail GNNs in predictive accuracy, use very large vectors (HDGL uses dimension 50,000, according to the paper), rely on floating point, and are not evaluated on heterophilic graphs at all. This paper's goal is to cross-pollinate the two: build a transductive graph learner that keeps HDC's cheap operations while matching or beating the accuracy of major GNNs, including GCNII.

Key Contributions

1. A new transductive graph learning algorithm, HyperGraphX, that incorporates message passing and other modern GNN operations into HDC graph learning using binding and bundling, with node vectors kept in their original input dimension rather than much larger ones.
2. Reported (average) test accuracy that beats all GNNs and HDC approaches the authors evaluated on their benchmarks, with particularly large gains on heterophilic graphs.
3. An implementation reported to be at least two orders of magnitude faster in training than prior approaches, running a fraction of a second for the hypervector computation.
4. A binary-vector aggregation scheme using logical OR, which is bounded in {0,1}^d regardless of neighbor count and idempotent, avoiding the need to scale incoming messages.

Main Findings

• Average accuracy: Across the seven graphs, HyperGraphX reaches a mean test accuracy of 0.749, versus 0.740 for GCNII, 0.657 for HDGL*, 0.636 for HDGL, 0.627 for GAT, and 0.592 for GCN. The paper states HyperGraphX averages approximately 15.5, 12.0, and 1.0 percentage points higher accuracy than GCN, GAT, and GCNII respectively.
• Per-graph accuracy: HyperGraphX records 0.783 on Cora, 0.690 on Citeseer, 0.750 on Pubmed, 0.703 on Chameleon, 0.754 on Cornell, 0.722 on Texas, and 0.844 on Wisconsin. GCNII records 0.855 (64 layers), 0.734 (32 layers), 0.802 (16 layers), 0.606 (8), 0.748 (16), 0.694 (32), and 0.741 (16), so GCNII is higher on the three citation graphs while HyperGraphX leads on all four heterophilic graphs.
• Heterophilic gains: On the four heterophilic graphs, HyperGraphX is reported as on average 29.8, 24.3, 17.4, 12.2, 17.6, and 5.8 percentage points more accurate than GCN, GAT, Geom-GCN-I, Geom-GCN-P, Geom-GCN-S, and GCNII respectively. Against Geom-GCN-P on Chameleon it is about 10 percentage points better.
• Training speed: HyperGraphX trains in 0.0046 s on Cora, 0.0130 s on Citeseer, 0.0102 s on Pubmed, 0.0066 s on Chameleon, 0.0016 s on Cornell, and 0.0013 s on both Texas and Wisconsin. GCNII takes 104.88 s on Cora. The paper reports HyperGraphX as on average about 410.1 and 489.1 times faster than GCN and GAT for the seven graphs, 2860.1, 2713.8, and 2811.1 times faster than Geom-GCN-I, Geom-GCN-P, and Geom-GCN-S for the four heterophilic graphs, and 144.5 times faster than HDGL.
• Speedup range and a reported discrepancy: The minimum speedup reported is 150.77 (Citeseer over GCN) and the maximum is 22800.0 (Cora over GCNII). The abstract states HyperGraphX is on average 9561.0 and 144.5 times faster than GCNII and HDGL, while Section 4 states it is on average 21484.2 times faster than GCNII for all seven graphs; the paper does not reconcile these two figures.
• Stability and tuning: Accuracy for HyperGraphX is reported as consistent between different runs for a given setting. Heterophilic accuracy numbers are averages over 10 different splits. HyperGraphX uses the shallowest networks (L = 1) and the fewest hyperparameters, with only α to tune (default α = 0.5), versus GCNII having the most hyperparameters.
• Heterophilic setup: The three citation graphs use only 20 labeled nodes per class; for Pubmed the training samples constitute less than 1% of the total. The heterophilic graphs use roughly a 6:2:2 train:validation:test split.

Methodology in Plain English

Each node is represented by a high-dimensional vector, kept at the original input feature dimension rather than an inflated one. Instead of a learned weight matrix, the method performs a weightless graph convolution: at each layer, every node's new vector is formed by bundling (summing, or logical OR for binary features) the vectors of its neighbors. When features are floating point, neighbor contributions are scaled by 1/sqrt(d_u d_v); when they are binary, the OR operation makes scaling unnecessary because the result stays in {0,1}^d and repeated aggregation has no cumulative effect. The graph is made undirected by adding reverse edges and self-loops are added to every node. To counteract over-smoothing from repeated aggregation, a final bundling step blends the original input vector with the vector after L layers using weights α and (1 − α); in the experiments L is set to 1 and α defaults to 0.5. For inference, the method computes a class center by averaging the hypervectors of that class's training samples, then assigns each test node to the most similar center.

Experiments compare against GCN, GAT, GeomGCN (three embedding variants: Isomap, Poincaré, and struc2vec), GCNII, and the HDC methods HDGL and HDGL*. Implementations use PyTorch 2.1 and Deep Graph Library version 1.0.1, with GCNII taken from Chen et al. and their hyperparameter settings, and prior methods' accuracy numbers taken from their original publications. All experiments run on NVIDIA Tesla V100S-PCIE-32GB GPUs.

Why This Matters

• Research impact: The paper shows that HDC-style operations, when fused with message passing, can compete with and sometimes exceed carefully tuned deep GNNs, and that a shallow single-layer, weightless convolution is enough on heterophilic benchmarks. It also opens heterophilic evaluation for HDC graph learning, which the paper states prior HDC implementations did not cover.
• Real-world applications (as implied by the evaluated domains):
  • Citation network analysis, using Cora, Citeseer, and Pubmed.
  • Web-page and entity classification on heterophilic networks, using Chameleon, Cornell, Texas, and Wisconsin.
  • Social network analysis, listed among the application areas the paper attributes to GNNs.
  • Materials research, also listed by the paper as a GNN application area.
• Industry relevance: Because the majority of the learning operates on binary vectors, the authors expect outstanding energy performance on neuromorphic and emerging process-in-memory devices. Sub-millisecond training times on graphs with up to 19,717 nodes (Pubmed) point to settings where models must be retrained frequently, and the absence of a weight matrix removes the memory bandwidth burden the paper attributes to GNNs' non-coalesced memory access on GPUs, TPUs, and clusters.

Future Directions

• Implementing HyperGraphX on emerging neuromorphic devices, which the authors state as a plan, and testing the energy-efficiency expectation the paper only asserts.
• Evaluating the method on graph classification tasks rather than only transductive node classification.
• Replicating and extending the heterophilic evaluation across more datasets, since the current heterophilic results are averages over 10 splits on only four graphs, three of which are small (Cornell and Texas have 183 nodes; Wisconsin has 251).
• Investigating the sensitivity of HyperGraphX to the single tuning parameter α, since all reported experiments use the default α = 0.5 and the paper reports no sweep.
• Reconciling the reported average speedup over GCNII, where the abstract states 9561.0 and Section 4 states 21484.2.

Target Audience

Readers who will benefit most are researchers and practitioners working on graph representation learning who want a lightweight, fast alternative to deep GNNs, especially for heterophilic graphs and for very small labeled training sets. It is also relevant to hardware and systems researchers interested in hyperdimensional computing, in-memory computing, and neuromorphic accelerators, since the method's reliance on binary vectors and its measured runtimes speak directly to those platforms. Students with an intermediate grasp of GNN message passing and basic vector algebra should be able to follow the method, though the paper assumes prior exposure to GNN terminology and HDC binding/bundling concepts.

Authors’ abstract

We present a novel algorithm, \hdgc, that marries graph convolution with binding and bundling operations in hyperdimensional computing for transductive graph learning. For prediction accuracy \hdgc outperforms major and popular graph neural network implementations as well as state-of-the-art hyperdimensional computing implementations for a collection of homophilic graphs and heterophilic graphs. Compared with the most accurate learning methodologies we have tested, on the same target GPU platform, \hdgc is on average 9561.0 and 144.5 times faster than \gcnii, a graph neural network implementation and HDGL, a hyperdimensional computing implementation, respectively. As the majority of the learning operates on binary vectors, we expect outstanding energy performance of \hdgc on neuromorphic and emerging process-in-memory devices.