Table of Links

Abstract and 1 Introduction

2 Related Work

3 Framework

4 Main Results

5 A Case Study on Shortest-Path Distance

6 Conclusion and Discussion, and References

7 Proof of Theorem 1

8 Proof of Theorem 2

9 Procedure for Solving Eq. (6)

10 Additional Experiments Details and Results

11 Other Potential Applications

2.1 Topology Awareness of GNNs

Modern GNN architectures take inspiration from the Weisfeiler-Lehman isomorphism test [12,19], which employs the graph structure to propagate information. Consequently, a significant portion of existing literature on GNNs concentrates on understanding their ability to differentiate various graph structures, known as the expressive power of GNNs [28–30, 44, 48, 50]. Inspired by the expressiveness studies, it is commonly believed that increasing topology awareness is universally beneficial and many studies focus on enabling GNNs to preserve more structural properties in the learned representation [29, 33, 48]. Nevertheless, the precise ramifications of heightened topology awareness on GNNs’ generalization performance remain shrouded in ambiguity. The intricate variations within structures across different domains and tasks further compound this complexity, underscoring the necessity for a unified framework—akin to the one proposed in this paper—to shed light on these intricacies.

2.2 Generalization of GNNs

Relatively few studies focus on understanding the generalization performance of GNNs in node-level tasks. [3, 9, 18, 23, 25, 34, 39, 41, 45] extend the conventional statistical learning or information-theoretic framework to GNNs, providing different generalization bounds based on concepts such as Vapnik–Chervonenkis dimension, mutual information, and algorithm stability. In light of this, despite empirical indications highlighting the critical role of GNNs’ topology awareness in generalization performance [20,29,48], there remains limited understanding of the relationship between topology awareness of GNNs and their generalization. Our proposed framework addresses this gap by utilizing the distortion concept in the approximate metric embedding to connect the topology awareness of GNNs and their generalization performance.

2.3 Active Learning in Graph

Active Learning (AL) seeks to enhance model performance within a limited labeling budget by identifying the most representative samples for annotation [32]. The AL methodology generally involves two phases: 1) selecting a small, preliminary subset of samples for labeling; 2) utilizing this labeled subset to iteratively discover the most informative sample for future labeling. The initial selection of an effective subset represents the cold-start problem in AL [11]. While AL has proven effective in settings with independent and identically distributed (i.i.d.) data, such as images and text, applying it to Graph Neural Networks (GNNs) poses unique challenges. These challenges stem from the necessity to account for node interdependencies and the computational complexity of iterative sample selection and retraining, especially when considering multi-hop neighbors. Recent AL methodologies for GNNs, such as AGE [5], FeatProp [42], and GraphPart [26], aim to overcome these obstacles by leveraging the graph structure and initial node features to boost efficiency and efficacy, although their success may significantly hinge on the quality of the initial features. In this work, we focus on the cold-start problem of graph active learning and introduce a novel approach (based on our analysis) that relies exclusively on graph structure, thus eliminating the reliance on feature quality at the onset of learning.