Abstract
Graph Neural Networks (GNNs) have emerged as a powerful tool for structured data analysis, yet they face significant challenges regarding scalability and resource constraints. This paper presents a suite of techniques designed to bridge the gap between theoretical expressivity and practical hardware limitations. We introduce GNN AutoScale (GAS), which utilizes historical embeddings to enable constant GPU memory usage on massive datasets. Furthermore, we explore Spatio-Temporal Random Fields (STRF) for efficient time-series modeling and GNN-based semantic retrieval for mathematical formulas. Our evaluations across large-scale benchmarks demonstrate that these methods significantly improve performance and memory efficiency without sacrificing predictive accuracy.
Introduction
The primary challenge in modern GNN research is the "neighbor explosion" problem. In standard GNN architectures, the representation of a single node depends recursively on its neighbors across multiple layers. For large, dense graphs, this dependency grows exponentially, quickly exhausting GPU memory and making "full-batch" training impossible.
Beyond scalability, there is a growing need to treat complex structures—such as mathematical formulas in scientific literature—as first-class citizens. Traditional keyword-based search methods often fail to capture the semantic nuances of equations. This work addresses these dual challenges by developing scalable GNN frameworks and applying them to complex structured data like formulas and spatio-temporal sensor networks.
Methods
The paper introduces several novel techniques to optimize graph-based learning:
- GNN AutoScale (GAS): Instead of recomputing the entire neighborhood for every mini-batch, GAS utilizes "historical embeddings" from previous training iterations. By pruning sub-trees of the computation graph and filling gaps with cached values, GAS maintains constant GPU memory consumption regardless of graph size.
- Spatio-Temporal Random Fields (STRF): For time-series data on graphs (e.g., traffic sensors), the authors propose a piecewise linear reparameterization. This reduces the parameter space significantly, allowing complex models to run on resource-constrained embedded devices.
- Formula Embeddings: Mathematical formulas are converted from LaTeX to MathML (XML) and treated as tree-structured graphs. GNNs are trained on unsupervised tasks—Contextual Similarity and Masking—to learn deep semantic representations that facilitate retrieval.
- Parallel Max-Cut: A framework for approximating the Max-Cut problem in directed graphs using shared memory, facilitating semi-supervised learning and data compression.
Key Results
Scalability and Efficiency
GNN AutoScale (GAS) achieved a 2x performance improvement over standard serial mini-batching while maintaining the expressive power of full-batch training. It successfully fit models on GPUs that would otherwise have crashed due to memory limits. Similarly, the STRF model achieved high accuracy with only 10% of the original model size by identifying sparse parameter sets.
Semantic Retrieval
The GNN-based formula search significantly outperformed traditional Bag-of-Words (BoW) and fastText baselines. In the "Top-10" accuracy metric (P@10), the GNN model achieved 0.5038 compared to BoW's 0.4567, proving that structural information is vital for scientific retrieval.
Discussion and Future Work
A key insight from this work is the "historical advantage": using "stale" embeddings from previous iterations in GAS does not necessarily hurt accuracy, provided they do not change too rapidly. This provides a mathematically sound approximation that breaks the memory bottleneck.
Future research will focus on tighter bounds for staleness control in GAS, extending the framework to truly distributed multi-node environments, and adapting the Weisfeiler-Leman paradigm to heterogeneous networks with diverse edge types and temporal information.
Summary updated