Georgia Institute of Technology
Scalable and Verifiable Foundations for Graph Learning
Abstract
dc:description.abstractGraph neural networks (GNNs) are increasingly deployed in high-stakes domains such as fraud detection, traffic prediction, and social network analysis. However, real-world graphs are heterogeneous, dynamic, and privacy-critical, posing challenges in structural complexity, scalability, and verifiability across the model lifecycle. This thesis argues that graph learning problems contain inherent structural regularities that, when explicitly leveraged in model and system design, enable scalable and verifiable graph learning across critical stages of the model lifecycle. First, we present HetTree, a scalable heterogeneous GNN that exploits the natural tree hierarchy among metapaths — the observation that metapaths form parent-child relationships through shared prefixes. HetTree constructs a semantic tree representation and introduces a subtree attention mechanism that captures hierarchical relationships among metapaths, combined with metapath-matched label utilization for heterogeneous graphs. Evaluation on five open benchmarks and a commercial email graph with 7.8 million nodes demonstrates state-of-the-art accuracy with low computation and memory overhead. Second, we present ReD, a system for scalable dynamic GNN training. ReD’s key insight is that while temporal dependencies exist within sequences of graph snapshots, different sequences are independent training samples. This enables a sequence-parallel partitioning scheme that eliminates cross-machine communication, combined with sequence-first mini-batch training and a two-level cache store tailored to dynamic GNN computation patterns. ReD outperforms state-of-the-art systems by 3.1–17.5× while supporting both stacked and integrated dynamic GNN architectures. Third, we present TaiTee, a system that establishes verifiable training provenance by integrating training recording with Confidential Computing. TaiTee hooks standard ML training APIs to record comprehensive provenance information and executes training within Trusted Execution Environments to generate cryptographically signed training certificates. Evaluation on 15 training scripts demonstrates minimal overhead: up to 5.3% for small models and as low as 0.006% for billion-parameter models. Together, the three contributions span the graph learning lifecycle — what to compute, how to compute it efficiently, and whether the training was conducted as claimed — providing scalable and verifiable foundations for deploying graph learning models in practice.
Degree
thesis:*- Name thesis:degree_name
- Computer Science, PhD
- Department thesis:degree_department
- Computer Science
- Grantor
- Georgia Institute of Technology
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Guan, Mingyu
- Advisors dc:contributor.advisor
-
- Padmanabha Iyer, Anand
- Kim, Taesoo
- Committee members dc:contributor.committeemember
-
- Gavrilovska Habl, Ada
- Rong, Kexin
- Stokes, Jack
- ORCID person:identifier.orcid
Rights
- Language dc:language.iso
- English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/82144