Back to search

Georgia Institute of Technology

Scalable and Verifiable Foundations for Graph Learning

Abstract

dc:description.abstract

Graph 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

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Guan, Mingyu. Scalable and Verifiable Foundations for Graph Learning. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/82144