Leveraging Approximation for Efficient and Effective Graph Neural Network Inference and Training

PhD Thesis Proposal Defence


Title: "Leveraging Approximation for Efficient and Effective Graph Neural
Network Inference and Training"

by

Mr. Qiqi ZHOU


Abstract:

Graph Neural Networks (GNNs) obtain predictive power by repeatedly 
propagating learnable representations over graph structures and have achieved 
remarkable success in various graph-related tasks. However, on large-scale 
graphs, complete message passing is computationally expensive during both 
training and inference. Consequently, practical systems often rely on 
approximations, such as using shallower models to replace deep ones during 
inference or approximating the full neighborhood with sampled partial 
neighborhoods during training. While these approximations improve efficiency, 
they can lose critical information required for accurate prediction or 
optimization.

This thesis proposal investigates the limitations of these approximation 
strategies and explores how to recover the lost information through carefully 
designed strategies, reducing GNN computational costs while preserving the 
effectiveness of model inference and optimization.

In the first work, we study knowledge distillation from deep teacher GNNs to 
shallow student GNNs for efficient inference. Existing methods primarily 
encourage students to mimic the embeddings or predictions of their teachers, 
overlooking the difference in their receptive fields. A shallow student 
cannot directly access the distant neighborhood information available to its 
teacher, creating an input mismatch that limits knowledge transfer. To 
address this problem, we propose the Bayesian Receptive Field Expander 
(BRFE), a lightweight module that estimates the missing information and 
supplies it as additional input to the student. BRFE combines a graph-level 
estimate with a node-level conditional estimate based on the student's 
observable input through a Bayesian formulation. This enables shallow 
students to benefit from information beyond their receptive fields without 
performing the teacher's full message passing.

In the second work, we study gradient estimation errors in mini-batch GNN 
training with neighbor sampling. We identify two sources of error: inaccurate 
messages computed from sampled neighborhoods and missing gradient 
contributions from target nodes outside the current mini-batch. Existing 
methods mainly address message inaccuracies, leaving the latter source 
insufficiently explored. We propose Pseudo Full Neighborhood Compensation 
(PFNC), a framework that reuses historical embeddings and gradients to 
compensate for both sources. A selective embedding cache improves message 
accuracy with limited memory overhead, while a historical gradient cache 
supplements the gradient contributions available in the current iteration. 
PFNC supports diverse neighbor sampling strategies, and our theoretical 
analysis establishes conditions under which the compensation improves 
gradient approximation.

Experiments across multiple node classification benchmarks demonstrate that 
the proposed methods reduce inference costs or the training time required to 
reach a target accuracy, while maintaining competitive final accuracy.


Date:                   Monday, 5 October 2026

Time:                   2:00pm - 4:00pm

Venue:                  Room 3494
                        Lifts 25/26

Committee Members:      Prof. Lei Chen (Supervisor)
                        Dr. Dan Xu (Chairperson)
                        Prof. Ke Yi