# Efficient Heterogeneous Graph Learning via Random Projection

arXiv: https://arxiv.org/abs/2310.14481 · HTML: https://mlsanity.com/paper/2310.14481/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 50 references that are in the map.
- First posted on arXiv 23 Oct 2023.

## Builds on (most cited first, 30 of 31)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Distributed Representations of Sentences and Documents](https://mlsanity.com/paper/1405.4053/) (2014)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding](https://mlsanity.com/paper/2002.01680/) (2020)
- [GPT-GNN: Generative Pre-Training of Graph Neural Networks](https://mlsanity.com/paper/2006.15437/) (2020)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networks](https://mlsanity.com/paper/2112.14936/) (2021)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Graph Attention Multi-Layer Perceptron](https://mlsanity.com/paper/2206.04355/) (2022)
- [An Attention-based Graph Neural Network for Heterogeneous Structural Learning](https://mlsanity.com/paper/1912.10832/) (2019)
- [Simple and Efficient Heterogeneous Graph Neural Network](https://mlsanity.com/paper/2207.02547/) (2022)
- [HINormer: Representation Learning On Heterogeneous Information Networks with Graph Transformer](https://mlsanity.com/paper/2302.11329/) (2023)
- [Scalable Graph Neural Networks for Heterogeneous Graphs](https://mlsanity.com/paper/2011.09679/) (2020)
- [Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering](https://mlsanity.com/paper/2305.02931/) (2023)
- [Heterogeneous Graph Contrastive Learning for Recommendation](https://mlsanity.com/paper/2303.00995/) (2023)
- [Higher-Order Attribute-Enhancing Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2104.07892/) (2021)
- [Label-Enhanced Graph Neural Network for Semi-supervised Node Classification](https://mlsanity.com/paper/2205.15653/) (2022)

## Built on by (most cited first, 16 of 16)

- [DGP: A Dual-Granularity Prompting Framework for Fraud Detection with Graph-Enhanced LLMs](https://mlsanity.com/paper/2507.21653/) (2025)
- [NTSFormer: A Self-Teaching Graph Transformer for Multimodal Isolated Cold-Start Node Classification](https://mlsanity.com/paper/2507.04870/) (2025)
- [RGL: A Graph-Centric, Modular Framework for Efficient Retrieval-Augmented Generation on Graphs](https://mlsanity.com/paper/2503.19314/) (2025)
- [ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion](https://mlsanity.com/paper/2504.15920/) (2025)
- [Simple and Efficient Heterogeneous Temporal Graph Neural Network](https://mlsanity.com/paper/2510.18467/) (2025)
- [Loss-aware Curriculum Learning for Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2402.18875/) (2024)
- [Heterogeneous Graph Neural Networks with Loss-decrease-aware Curriculum Learning](https://mlsanity.com/paper/2405.06522/) (2024)
- [Short-video Propagation Influence Rating: A New Real-world Dataset and A New Large Graph Model](https://mlsanity.com/paper/2503.23746/) (2025)
- [Echoless Label-Based Pre-computation for Memory-Efficient Heterogeneous Graph Learning](https://mlsanity.com/paper/2511.11081/) (2025)
- [Top K Enhanced Reinforcement Learning Attacks on Heterogeneous Graph Node Classification](https://mlsanity.com/paper/2408.01964/) (2024)
- [STAMP: Symmetric Temporal Averaging Message Passing for Domain Adaptation in Chronologically Split Graphs](https://mlsanity.com/paper/2411.10957/) (2024)
- [HeteroBA: A Structure-Manipulating Backdoor Attack on Heterogeneous Graphs](https://mlsanity.com/paper/2505.21140/) (2025)
- [Improving statistical learning methods via features selection without replacement sampling and random projection](https://mlsanity.com/paper/2506.00053/) (2025)
- [Are Heterogeneous Graph Neural Networks Truly Effective for Node Classification? A Causal Perspective](https://mlsanity.com/paper/2510.05750/) (2025)
- [HeteroHBA: A Generative Structure-Manipulating Backdoor Attack on Heterogeneous Graphs](https://mlsanity.com/paper/2512.24665/) (2025)
- [Blackknife: Query-Free Black-Box Rewiring Attacks on Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2606.29240/) (2026)

## Abstract (arXiv)

Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Typical HGNNs require repetitive message passing during training, limiting efficiency for large-scale real-world graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors, enabling efficient mini-batch training. Existing pre-computation-based HGNNs can be mainly categorized into two styles, which differ in how much information loss is allowed and efficiency. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN), which combines the benefits of one style's efficiency with the low information loss of the other style. To achieve efficiency, the main framework of RpHGNN consists of propagate-then-update iterations, where we introduce a Random Projection Squashing step to ensure that complexity increases only linearly. To achieve low information loss, we introduce a Relation-wise Neighbor Collection component with an Even-odd Propagation Scheme, which aims to collect information from neighbors in a finer-grained way. Experimental results indicate that our approach achieves state-of-the-art results on seven small and large benchmark datasets while also being 230% faster compared to the most effective baseline. Surprisingly, our approach not only surpasses pre-processing-based baselines but also outperforms end-to-end methods.