Year: 2021

Abstract:
Theoretical understanding of the learning process of graph neural network (GNN) has been lacking, especially for node-level tasks where data are not independent and identically-distributed (I.I.D.). The common practice in GNN training is to adopt strategies from other machine learning families, despite the striking differences between learning non-graph and graph-structured data. This results in unstable learning quality (e.g., accuracy) for GNN. In this paper, we study the relation between the training set in the input graph and the performance of GNN. Combining the topology awareness of GNN and the dependence (topology) of data samples, we formally derive a structural relation between the performance of GNN and the coverage of the training set in the graph. More specifically, the distance of the training set to the rest of the vertexes in the graph is negatively correlated to the learning outcome of GNN. We further validate our theory on different graph data sets with extensive experiments. Using the derived result as guidance, we also investigate the initial data labelling problem in active learning of GNN and show that locality-aware data labelling substantially outperforms the prevailing random sampling approach.

heading: 1 INTRODUCTION
text: Graph Neural Network (GNN) is a family of machine learning (ML) models tailored for learning from graph-structured data (Duvenaud et al., 2015; Li et al., 2017b; Gilmer et al., 2017; You et al., 2019). Recently, great success has been shown using models such as GCN (Kipf & Welling, 2017), GraphSAGE (Hamilton et al., 2018) and GAT (Veličković et al., 2017) on tackling various graphrelated problems in domains such as chemistry (Gilmer et al., 2017), biology (Duvenaud et al., 2015), social networking (Hamilton et al., 2018; Chen et al., 2018; 2017b) and traffic networks (Li et al., 2017a). Despite their practicality and potential, theoretical understanding of the learning process of GNNs is still underexplored, especially given their difference in data dependency from other ML families.
In most ML settings, data samples are assumed to be created independently and identically (I.I.D.) from a certain distribution. Because of this, uniform sampling is effective in many data selection processes such as training/validation/test set partition, batch sampling and initial labelling set selection (Settles, 2009; Ren et al., 2020). For learning from graph-structured data, inherent dependencies exist among data samples, as captured by the graph structure. Taking training/validation/test set partition for example, different random partitions of the labelled nodes significantly impact the performance of the GNN model (Shchur et al., 2019), especially when the size of the training set is small relative to the data population. Fig. 1 illustrates this phenomenon on the Cora data set (Sen et al., 2008). This calls for a better understanding of the relation between the dependence among data samples and the learning process of GNN.
Network homophily (McPherson et al., 2001) is a fundamental principle that describes the dependence among data samples in many real-world networks. Network homophily implies that nodes close by in (graph) distance tend to have similar features and labels. Most existing GNN designs assume strong homophily in the graph data (Zhu et al., 2020) and exploit it by propagating features and aggregating them within various graph neighbourhoods using different mechanisms (Hamilton et al., 2018; Veličković et al., 2017; Kipf & Welling, 2017). The capability to capture topological information from the underlying graph structure is the key to contribute to the success of GNN.
The following question is raised: can we combine this network principle and topology awareness of GNN to derive useful insights for more effective graph learning via GNN? Most existing efforts focus on the (vertex) sampling strategy to accelerate GNN training (Chen et al., 2018) or to conserve memory during GNN training (Ying et al., 2018). There is little understanding or work on the underlying principle between the dependency of the data samples and the performance of GNN models Ma et al. (2021).
To address this question, we theoretically and experimentally investigate how and why different random partitions of training sets affect the learning outcome (test performance) of GNN in node-level tasks. We focus on graph data sets where the network homophily property holds. We formally show the spatial locality in the inference ability of GNN (under certain conditions), i.e., GNN predicts better on vertexes close to the training set.
Our main contributions are summarized as follows.
1. We prove that GNN predicts better on vertexes that are closer to the training set under certain assumptions. This implies that better coverage of the training set over the rest of the graph (in terms of neighbourhoods of a small radius) can translate into better generalization performance of the GNN model in the semi-supervised setting.
2. We experimentally validate our theory and assumptions on Cora, Citeseer and PubMed data sets with prevailing GNN models such as GCN, GAT and GraphSAGE.
3. Using the observation and theory as guidance, we formulate two optimization problems for studying (1) the “cold start” problem in active learning (Grimova et al., 2018), and (2) minimal size of the labelled data set with respect to the model performance. The first optimization provides a strategy for selecting the most “economic” initial data set to be labelled and the other gives insights on how many vertexes should be labelled initially for the desired learning outcome of a GNN model.
This work represents our first attempt to unwrap a better understanding of the learning process of GNN. It is novel to combine the network principle of the dependence among data samples and topology awareness of GNN to formally infer useful insights (based on graph structure) for GNN learning. The results suggest that the topology awareness of GNN is not only an important property to improve GNN performance, as shown in (Li et al., 2020; You et al., 2019; Xu et al., 2018; Nishad et al., 2021), but also useful guidance for making informed decisions in the learning process of GNN.

heading: 2 RELATED WORK
text: Expressive Power of GNN. Modern GNN architectures are inspired by the Weisfeiler–Lehman (WL) isomorphism test (Leman & Weisfeiler, 1968) which uses the graph structure to propagate information (Kipf & Welling, 2017). One idea in characterizing the power of GNN is to measure its ability in differentiating different graph structures, referred to as the expressive power of GNN (we refer to Sato (2020) for a survey on this line of works). In particular, Xu et al. (2018) proved that the expressive power of GNNs is no more than the WL test. This has inspired a number of studies on improving the expressive power of GNN by enabling it to differentiate graph structures that cannot be distinguished by the WL-test (Morris et al., 2020). The studies in (You et al., 2019; Li et al., 2020; Nishad et al., 2021; Zhou et al., 2020) show that combining graph topology information
(distance) into the learning process of GNN (e.g., for feature encoding, aggregation, normalization) can improve the performance of GNN on various tasks.
Generalization of GNN. Studies aiming to understand generalization performance of GNNs on node-level tasks are rather limited (Ma et al., 2021). To our best knowledge, there are two very recent studies that investigate/demonstrate similar observations as ours. Zhu et al. (2021) studied the problem in GNN learning that the test set and the training set are generated from different distributions. They found the test error of GNNs is inversely related to their defined metric (distance) between test set and training set, which is similar to our discovery here. However, their work focused on designing a regularization mechanism to allow the learnt distribution to approximate the distribution in the test set. Ma et al. (2021) studied a similar problem as ours by extending the PACBayesian analysis for I.I.D. data to analyzing the generalization performance of GNNs. They prove that given a fixed training set, GNN generalization performance varies among different subgroups of the test population defined by a feature distance. Our study complements their study in the case that graph distance metric is used. Our analysis provides a different and more direct perspective for understanding how graph structure information influences GNN learning performance.

heading: 3 PRELIMINARIES

heading: 3.1 GRAPH AND NOTATION
text: Let G = (V,E) be the input graph with node feature vector Xv for all v ∈ V . In this paper, we assume G is connected and focus our analysis on the node classification task where a label yv is associated with vertex v, and the objective is to learn a representation vector hv of v such that v’s label can be predicted as yv = f(hv), where f is the prediction function. We use d(x, y) to denote the distance between x and y: (1) d(., .) is defined to be the shortest path distance if x and y are vertexes in the graph; (2) d(., .) is the Euclidean distance if x and y are representations in the embedding space; (3) d(., .) is the distance between x and the closest element in Y , if Y is a set. For example, let u be a vertex and D be a set of vertexes, and then d(u,D) := minv∈D{d(u, v)}. Let N and R denote the set of natural numbers and real numbers, respectively. R+ is the set of non-negative real numbers.

heading: 3.2 GRAPH NEURAL NETWORK
text: GNN combines the graph structure and node features Xv to learn a representation vector hv of node v. Modern GNNs adopt a neighborhood aggregation scheme, where the representation of a node is updated iteratively by aggregating representations of its neighbors. After k iterations of aggregation, a node’s representation captures the structural information within its k-hop neighborhood in the graph. LetH ⊆ Rm be the embedding space of the learnt representations of vertexes and m ∈ N is the dimension. Mθ : V 7→ H denotes the GNN model with parameter θ that maps a vertex v ∈ V into a representation vector hv in the embedding space H, following a neighborhood aggregation scheme. Let f : H 7→ Rc be the prediction function that maps an embedding vector hv to a vector in Rc, in which c ∈ N is the number of classes and each entry represents the probability of belonging to the respective class. The GNN prediction process can be viewed as composition of f ◦Mθ : V 7→ Rc. Let L : Rc 7→ R+ denote the loss function which evaluates how accurate the prediction is.
As the graph structure (topology) among vertexes provides important information, it is important for GNN to preserve as much topological information as possible for embedding. Indeed, it has been formally and experimentally shown in (Li et al., 2020; You et al., 2019; Nishad et al., 2021) that improving the ability of GNN to preserve topological information such as shortest path distance can improve the expressive power of GNN. Here, we explore how to combine the topology awareness of GNN with the network homophily principle to derive useful insight for GNN learning. In particular, we focus on the ability of GNN to preserve distances information among vertexes, i.e., to have a low distortion between graph distance and embedding distance. The distortion of a function between two metric spaces is defined as follows. Definition 1 (distortion). Given two metric spaces (E , d) and (E ′, d′) and a mapping f : E 7→ E ′, f is said to have distortion α, if there exists a constant r > 0 such that ∀u, v ∈ E , rd(u, v) ≤ d′(f(u), f(v)) ≤ αrd(u, v)
You et al. (2019); Li et al. (2020); Nishad et al. (2021) have presented effective ways to increase the awareness of GNNs to vertex distances, i.e, to decrease the distortion rate α. For example, one can encode the shortest path distance (SPD) or other graph structure information to be part of the node feature for each vertex (Li et al., 2020). Based on Bourgains’ theorem (Bourgain, 1985), You et al. (2019) propose a vertex-distance-aware mechanism by selecting a set of anchor vertexes to provide positional information, and use the positional information to adjust the intermediate activation in GNN learning process. It is also discussed in (You et al., 2019) that the commonly used GNNs are a local version of the vertex-distance-aware mechanism they proposed, as the commonly used GNNs aggregate information for the training node from its neighbourhood. This neighbourhood aggregation mimics the existence of anchor vertexes and can provide local position information. This implies that common GNNs are already equipped with some ability to capture vertex distances (low distortion), at least between neighbours whose representations are aggregated. We conduct experiments in Sec. 4.3 to further validate this.

heading: 4 LOCALITY IN THE LEARNING PROCESS OF GNN

heading: 4.1 LOCALITY IN GNN PERFORMANCE
text: We now show how to use GNN properties to derive local structural behaviour in GNN learning. We make the following assumptions for our theoretical analysis.
Assumption 1 (Local curvature). For all representations h ∈ H, ddhL(f(h)) and d2
d2hL(f(h)) exist, and are continuous and bounded. Assumption 2 (Well-trained). For a given training setD, the training process of the GNN converges to a set of parameters θD such that for any > 0 and v ∈ D, we have L(f(MθD (v))) < .
Assumption 1 is a standard technical assumption to make the analysis feasible. Regarding Assumption 2, it has been formally proved that GNNs can achieve universal approximation power (Keriven & Peyré, 2019; Brüel-Gabrielsson, 2020; Maron et al., 2019), and under mild conditions and with enough parameters in the model (Oymak & Soltanolkotabi, 2019), a model with universal approximation power can achieve zero loss on the training set upon convergence, i.e., the property in Assumption 2, with high probability. This can be extended to the GNN case as long as there are no training vertexes with an identical neighbourhood and the same features but different labels. We assume the loss converges to zero for simplicity in our theoretical analysis, and show in our experiments in Sec. 4.3 that converging to a small loss (instead of zero) is sufficient for a GNN model to show the structural behaviour to be derived. Our first result below gives the locality in the predicting power of GNN around vertexes in the training set. Proposition 1. Let D be a given training set and θD be the set of parameters as defined in Assumption 2. Under Assumption 1, we have that for any v ∈ D and hv =MθD (v), there exists rv > 0 such that for representations h, h′ ∈ H, if d(h, hv) < d(h′, hv) < rv , then L(f(h)) < L(f(h′)).
We provide a proof for Proposition 1 in Appendix A. Proposition 1 states that given a GNN model with a large enough learning capacity (aka sufficient parameters in the model), for each vertex v in the training set, there exists a local neighbourhood of radius rv surrounding representation hv of v in the embedding space, on which the prediction performance (loss) admits simple monotonicity with respect to the distance between the representations. This result suggests that if we look at the landscape of the loss function from the perspective of the embedding space, the representation of each vertex in the training set induces a “valley” effect in the prediction performance (lowest loss at hv within the neighbourhood), where losses incurred by representations nearby are larger if the respective distance to hv is larger. Fig. 2 gives an illustration.

heading: 4.2 STRUCTURAL RELATION BETWEEN TRAINING SET AND GNN PERFORMANCE
text: We next study the prediction power of GNN with respect to the (graph) distance between training set and test set. We first extend the result in Proposition 1 to study the prediction performance of GNN on different test sets. Theorem 1. LetM be a GNN model trained on vertex set D with distortion α and θD is the set of learned model parameters upon convergence. Let T and T ′ be two test sets whose vertexes are in the
local region of some vertexes inD as given in Proposition 1. There is a one-to-one mapping g : T 7→ T ′ with d(u,D) < 1αd(g(u), D),∀u ∈ T . Under Assumptions 1 and 2, there exists δ > 0 such that if∑ v∈T ′ d(v,D) > αδ ∑ u∈T d(u,D), we have ∑ u∈T L(f(MθD (u))) < ∑ v∈T ′ L(f(MθD (v))).
The proof of Theorem 1 is given in Appendix B. The core idea of the proof is to connect graph distance of vertexes with embedding distance and to extend the result of Proposition 1 to analyze the relation between the distance of different test sets to the training set and the performance (test loss) of the learned model. Theorem 1 gives a structural relation on the prediction power of GNN on different vertexes with respect to their graph distance to the training set. More specifically, GNN predicts better on closer vertexes. We proved this structural relation in the case that the distortion of the GNN is small enough so that relative order of distances across different test sets is preserved in the embedding space. We provide experimental validation on this premise. Relaxing the condition on the distortion rate and obtaining a complete relation renders an interesting future direction to investigate. A similar result was proved in (Ma et al., 2021) using the distance between training set and test set in the feature space. Here, we motivate our result from the perspectives of network homophily and topology awareness of GNN. Further, we can extend the result above to compare different pairs of training set and test set.
Theorem 2. LetM be a GNN model trained on vertex sets D,D′ with distortion α. Let θD, θD′ be the learned model parameters upon convergence, respectively. Let T and T ′ be two test sets whose vertexes are in the local region of some vertexes in D,D′, respectively, as given in Proposition 1. There is a one-to-one mapping g : T 7→ T ′ with d(u,D) < 1αd(g(u), D
′),∀u ∈ T . Under Assumptions 1 and 2, there exists δ′ > 0 such that if ∑ v∈T ′ d(v,D ′) > αδ′ ∑ u∈T d(u,D), we
have ∑ u∈T L(f(MθD (u))) < ∑ v∈T ′ L(f(MθD′ (v))).
The proof of Theorem 2 is given in Appendix C. Theorem 2 extends the result of Theorem 1 and gives a structural relation of the performance of GNN on different pairs of training set and test set with respect to their graph distances. We can draw several implications from the theorems. First, an insight is obtained that to enable better learning quality of GNN, the training set should consist of vertexes within close proximity to the rest of the input graph. Fig. 3 gives an illustration and we will further validate it in Sec. 4.3. Second, the topology awareness of GNN not only is important for improving its expressive power, but also can be exploited to make other informed decisions in the learning process. We use our result in investigating the initial data labelling problem in Sec. 5, and briefly discuss the potential of applying it in other related problems such as vertex sampling for batch training of GNN in Sec. 6. Third, Theorem 1 and Theorem 2 give us a glimpse on the fundamental difference between the learning process in GNN and in other ML settings.

heading: 4.3 EXPERIMENTS
text: We next conduct experiments to verify our structural relation derived and some of the assumptions. We train four representative GNN models: (1) GCN (Kipf & Welling, 2017); (2) GAT (Veličković et al., 2017); (3) GraphSAGE (Hamilton et al., 2018); and (4) Position-aware Graph Neural Network (PGNN) (You et al., 2019) with a deliberately designed mechanism (described in Sec. 3.2) to enhance GNN’s capability to capture inter-vertex distances. We adopt popular graph data sets including Cora, Citeseer and PubMed (Sen et al., 2008; Li et al., 2018). Due to space limit, we mainly show experimental results using Cora (and GCN) in the main body of the paper, and present
the remaining experimental results on other data sets, as well as GNN architecture details and training hyperparameters, in Appendix F. For experiments on Cora, we consider the largest connected component (2485 out of the total 2708 vertexes) and use a training set of size 35 (5 vertexes for each class) that can bring larger variance on the distance of training set to the rest of the vertexes. The experimental results demonstrate that our assumptions and the derived structural relation are indeed common and persistent among GNNs on data sets with network homophily.
We first validate that GNNs preserve distances (with a small distortion rate) locally by evaluating the relation between the graph distances of vertexes to the training set and the embedding distances of vertex representations to the representations of the training set, namely the relation between d(v,D) and d(MθD (v),MθD (D)). In this experiment, we compute the graph distance and the embedding distance on the rest of the vertexes after training. As shown in Fig. 4, there exists a strong correlation between the graph distance and the embedding distance. Especially, when the graph distance is relatively small, the relation is close to linear and the relative orders are mostly preserved. This indicates that the distortion α is indeed small (at least within the first few hops) with different GNNs. This implies that the common aggregation mechanism in GNNs can well capture local graph structure information (graph distances), which in turn indicates that the premise on the distortion rate which we used to prove our theoretical results is not far from reality.
Next, we study the relation between the graph distance and the prediction loss following the same settings as in the previous experiment. As illustrated in Fig. 5, vertexes corresponding to smaller embedding distances (to representations of the training set in the embedding space) achieve smaller loss (the GNN is more certain and more likely to be correct with the prediction). This validates Proposition 1.
Combining the two experiments above, we can derive the positive relation between graph distance (to the training set) and prediction loss. A smaller graph distance (to the training set) translates into a smaller embedding distance (to representations of the training set) and then a smaller loss. Fig. 6 gives an illustration and validates the result in Theorem 1.
Further, we validate if the distance between different pairs of training set and test set is related to the prediction performance of GNN. As shown in Fig. 7, Table 1 and Table 2, this is indeed the case, which validates our result in Theoreom 2 that better performance (test accuracy/loss) is achieved when the distance between the training set and the test set is smaller.
|Dtest| .

heading: 5 APPLICATION ON INITIAL DATA LABELLING
text: We next present an application of our derived results on the initial data labelling problem in active learning of GNNs. Active learning deals with selecting samples in the data set to label and the goal is to maximize the gain on model performance while labelling the fewest samples possible. One common scheme of active learning is to first select an initial set D to label and have the model trained on D, and then select the data samples to be labelled next with “most uncertainty” (largest loss) using the trained model (Ren et al., 2020; Settles, 2009).
Unsatisfactory initial set selection may lead to slow learning progress (Grimova et al., 2018). How to select the most “economic/proper” initial labelled data set is referred to as the “cold start” problem, as the model itself is not ready to be used for selecting data samples yet. One natural objective for this selection is to find an initial set D from the complete data set V that could maximize the generalization performance of the model trained on D: argminD⊂V ∑ d∈V \D L(d|D).
For a GNN model, we have shown that how well it can learn from the data set is closely related to the coverage of the training set. A smaller mean distance of other vertexes to the training set leads to better GNN performance. The distance function used in our theoretical results is defined with the class label of the vertexes, which is unavailable in the initial labelling problem. Nevertheless, the general principle is that we want the labelled data to have good coverage on the rest of the data. This can be formulated into the following optimization problem.
max D⊂V ∑ u∈V \D Ir(u|D)
s.t. |D| ≤ k (1)
where k is the given initial set size and r is the given neighborhood radius. Ir(u|D) is an indicator function: Ir(u|D) = 1 if there exists a vertex v ∈ D such that u ∈ Nr(v), and Ir(u|D) = 0, otherwise. The problem can be reduced to the maximal coverage problem (Hochbaum, 1996), as given in Appendix D. The maximal coverage problem is NP-hard. There exist efficient greedy algorithms to achieve an approximation ratio of 1− 1e , e.g., by selecting a vertex whose neighbor has the most uncovered vertexes at each stage (Hochbaum, 1996). We evaluate the initial set selected by solving (1) using the greedy algorithm in (Hochbaum, 1996), and those chosen with common approaches of uniformly random selection (effective for active learning of DNN under the I.I.D data assumption) and importance-based selection (vertexes are sampled based on some graph properties distribution). In Table 3, we observe that our locality-based selection achieves a significant improvement of model performance over the other strategies, giving a better kick-start to the active learning process of GNNs.
In addition to finding an initial set of given size k, similar principle can be adopted to decide the minimal size of the initial labelled data set, for certain guarantee on the performance of the trained model. A lower bound of the initial labelled set size can be computed by solving the following problem: min
D⊂V |D| s.t. ∑
u∈V−D Ir(u|D) ≥ g|V |
(2)
where g ∈ [0, 1] and Ir(u|D) is the same indicator function as defined earlier. For given r and g, problem (2) finds the minimum cover which covers at least g portion of all the vertexes within its radius-r neighborhoods. By adjusting the ratio g and radius r, one can control the performance guarantee resulted from the initial set selection. (2) can be reduced to a minimal partial covering problem which is NP-hard with efficient approximation algorithms available (Gandhi et al., 2004). We provide a detailed reduction in Appendix E.

heading: 6 CONCLUDING DISCUSSIONS
text: In this paper, we investigate the role of the input graph in GNN learning, and show that data dependence has significant effects on GNN learning quality. We formally and experimentally show that there exists a structural relation between the coverage of the training set and the performance of the GNN on the test set. Using the obtained result, we investigate its application in tackling the “cold start” problem in the active learning of GNN. As our first attempt into in-depth understanding of GNN’s learning process, a number of interesting directions are opened up for further investigation.
Combining with other topological features and network principles. Besides the distance preserving property, the ideas in this work may be extended to combine other (useful) topology-preserving properties of GNN (e.g., group and community structures (Zhou et al., 2020)) and network principles (e.g., structure equivalence). Furthermore, similar ideas/analyses can also be extended to graph edge-related tasks by adapting the topological features from edges.
Size of the local neighborhood of the training set. It has been studied on other deep learning models that the curvature of these local neighborhoods (Keskar et al., 2016) is closely related to the performance of the deep learning models. Preliminary factors that affect the curvature of local minima have been studied in (Jastrzebski et al., 2018). Comparing with other deep learning models, GNNs allow for more rigorous analysis based on the underlying graph structure and the distancepreserving property. It is interesting to extend our analysis to formally unwrap the factors that affect the size/curvature of the local neighborhood, and how the curvature at the local minima could further affect the model performance.
Other applications of the results. Other than initial data labelling, we may apply our structural results in other data selection problems in GNN training, such as batch sampling for stochastic training (Chen et al., 2017a) and neighbor subsampling in the information aggregation process (Ying et al., 2018).

heading: A PROOF OF PROPOSITION 1
text: In this appendix, we provide a proof for Proposition 1.
Proof. Let θD be the set of parameters learnt by the GNN model that satisfy properties given in Assumption 2. Namely, for each vertex v ∈ D and any > 0, we have that
LθD (f(hv)) < , where hv = M(v). This means that LθD (f(hv)) 7→ 0 and we know that the L function is a continuous function of range R+. LθD (f(hv)) achieves the global minimum of the loss function in the embedding space.
By Assumption 1, we know that ddhL(f(hv)) and d2 d2hL(f(hv)) exist. This implies that
d
dh L(f(hv)) = 0,
as this is the necessary condition for hv to achieve a local minimum. Furthermore, as LθD (f(hv)) also achieves the global minimum, this implies that
d2
d2h L(f(hv)) ≥ 0.
This means that there must exist a rv > 0 such that ∀h ∈ Nrv (hv) ⊂ H, we have
d
dh L(f(hv)) ≥ 0.
For d(h, hv) ≤ d(h′, hv) ≤ rv , we can rewrite h′ = h+ d. Then we have,
L(f(h′)) = L(f(h+ d))
≥ L(f(h)) + d dh L(f(h))‖d‖
Because ddhL(f(h)) ≥ 0 and ‖d‖ > 0, we have that
L(f(h′)) > L(f(h)).

heading: B PROOF OF THEOREM 1
text: Before diving into the detailed proof, we present an outline of the structure of the proof and prove a lemma which we use in the proof of the theorem.
Outline of the proof for the thereom
1. Suppose we are given T and T ′, two test sets which satisfy the premise of the theorem; 2. Then, we can approximate and bound the loss of each vertex in the test set based on the
nearest vertex in the training set by extending the result from Proposition 1; 3. Based on smoothness of curvature assumed in Assumption 1, we can bound the behavior
of vertexes in the test set and derive the desired result. Lemma 1. Let D be a given training set. M and f are the GNN model and prediction function which have parameter θ and satisfy the property in Assumption 2. Let u, v be two arbitrary vertexes in D with representations hu =M(u) and hv =M(v). Let Nrv (hv) and Nru(hu) be the neighborhood given in Proposition 1. Furthermore, let Nrv,+(hv) := {h ∈ Nrv (hv)|L(f(h)) > 0}, i.e.,
the set whose elements have positive loss values. Nru,+(hu) is Similarly defined. Then, we have that
Nru,+(hu) ∩Nrv,+(hv) = ∅.
Proof. Suppose the opposite: there exists h which belongs toNru,+(hu) andNrv,+(hv) at the same time. In other words,
h ∈ Nrv,+(hv) ∩Nru,+(hu).
By their definition,Nrv,+(hv) andNru,+(hu) are open sets. By definition of an open set, there exist rh,v and rh,u such that the neighborhood Nrh,v (h) ⊆ Nrv (hv) and the neighborhood Nrh,u(h) ⊆ Nru(hu)
Let rh = min{rh,v, rh,u}. We have that neighborhood Nrh(h) are in both Nru(hu) and Nrv (hv). Consider h′ ∈ Nrh(h) such that
d(h, hv) < d(h ′, hv),
and d(h, hu) > d(h ′, hu). Such h′ exists because hv and hu are two distinct points in the embedding space. Next, let’s consider the loss value of h, h′ from the perspective of hv . Because
d(h, hv) < d(h ′, hv),
by Proposition 1, we have that L(f(h)) < L(f(h′)).
Similarly, if consider the loss value of h, h′ from the perspective of hu, we have that
L(f(h)) > L(f(h′)),
because d(h, hu) > d(h ′, hu).
We reach a contradiction.
Lemma 1 implies that each vertex can be in at most one of these neighborhoods at a time. Next, we provide the proof for Theorem 1.
Proof. Let G = (V,E) be the input graph with node feature vector Xv for all v ∈ V . Let D ⊂ V be the training sets. LetM be a given GNN model. Let f be the prediction function that maps the output ofM to the class representation. Let L be the loss function with range R+. Let θD be the sets of model parameters learnt using training set D, which satisfy Assumption 2. In other words, we have, ∑
u∈D L(f(MθD (u))) = 0 (3)
Let T, T ′ be the two test sets satisfy the premise of the theorem. In other words, we have a one-toone mapping g : T 7→ T ′ with αrd(u,D) < rd(g(u), D),∀u ∈ T . Now, let’s consider the loss on the test set T with the modelMD, which can be written as:∑
u∈T L(f(MθD (u))) (4)
By premise, we have that for each u ∈ T , there exists at least one v ∈ D such that M(u) ∈ Nrv (M(v)) where Nrv (M(v)) satisfies properties of Proposition 1. In other words, the loss function is monotonically increasing with respect to the embedding distance in Nrv (M(v)). By Lemma 1, we know that u can be in only one of this neighborhoods. Let Q : T 7→ D be the mapping that maps vertex u ∈ T to its corresponding simple neighborhood that is centered at a vertex Q(u) ∈ D. For simplicity, we denote the vertex as qu = Q(u). Due to Proposition 1 and
Assumption 1, we can do a quadratic approximation of u around qu and have the following upper bound:
L(f(MθD (u))) ≤ L(f(MθD (qu))) + 〈MθD (u)−MθD (qu), DMθD (qu)〉
+ Mu 2 ‖MθD (u)−MθD (qu)‖
(5)
where Mu = sup{D2L(f(h))|h ∈ Nrqu (qu)},
and rqu = ‖qu − u‖.
Let M∗D = max{‖Mu‖|u ∈ T} (6)
M∗D exists since T is finite. Then, we obtain the following upper bound that is universal for all vertexes in T :
∑ u∈T L(f(MθD (u))) ≤ ∑ u∈T L1(u) + M∗D 2 ‖Mθu(u)−MθD (qu)‖ (7)
where L1(u) = L(f(MθD (qu))) + 〈Mθu(u)−MθD (qu), DMθD (qu)〉.
Similarly, let Q′ : T ′ 7→ D be the mapping that maps vertex u ∈ T ′ to its corresponding simple neighborhood that is centered at a vertex Q′(u) ∈ D. For simplicity, we denote the vertex as q′u = Q
′(u). Again, due to Proposition 1 and Assumption 1, we can do a quadratic approximation of u around q′u and have the following lower bound:
L(f(MθD (u))) ≥ L(f(MθD (q′u))) + 〈MθD (u)−MθD (q′u), DMθD (q′u)〉
+ Lu 2 ‖MθD (u)−MθD (q′u)‖
(8)
where Lu = inf{D2L(f(h))|h ∈ Nrq′u (q ′ u)},
and rq′u = ‖q ′ u − u‖.
Let L∗D = min{‖Lu‖|u ∈ T ′} (9)
L∗D exists since T ′ is finite. Then, we obtain the following lower bound that is universal for all the vertexes in T ′:
∑ u∈T ′ L(f(MθD (u))) ≥ ∑ u∈T ′ L′1(u) + L∗D 2 ‖MθD (u)−MθD (q′u)‖ (10)
where L′1(u) = L(f(MθD (q′u))) + 〈MθD (u)−MθD (q′u), DMθD (q′u)〉.
For simplicity, suppose the cardinality of T and T ′ are k, and let I = {1, ..., k}. Let’s index and arrange the vertexes in T and T ′ such that,
T = {u1, ..., uk},
and T ′ = {v1, ..., vk},
such that vi = g(ui).
Let’s consider the difference between equation 25 and equation 22:
∑ u∈T ′ L(f(MθDu)))− ∑ u∈T L(f(MθD (u)))
= ∑ i∈I L(f(MθD (vi)))− L(f(MθD (ui)))
> ∑ i∈I L′1(vi) + L∗D 2 ‖MθD (vi)−MθD (q′vi)‖ − L1(ui)− M∗D 2 ‖MθD (ui)−MθD (qui)‖
= ∑ i∈I (L′1(vi)− L1(ui)) + ∑ i∈I [L∗D 2 ‖MθD (vi)−MθD (q′vi)‖ − M∗D 2 ‖MθD (ui)−MθD (qui)‖ ] = ∑ i∈I (L′1(vi)− L1(ui))+ L∗D 2 ∑ i∈I [ ‖MθD (vi)−MθD (q′vi)‖ ] − M ∗ D 2 ∑ i∈I [ ‖MθD (ui)−MθD (qui)‖
] (11)
Since qui and q ′ vi are local minima of the loss function, we get that
L′1(vi) = L1(ui).
This leads to that∑ i∈I L(f(MθD (vi)))− L(f(MθD (ui)))
> L∗D 2 ∑ i∈I [ ‖MθD (vi)−MθD (q′vi)‖ ] − M ∗ D 2 ∑ i∈I [ ‖MθD (ui)−MθD (qui)‖ ] (12) To simplify the notation, let’s denote
S = ∑ i∈I [ ‖MθD (ui)−MθD (qui)‖ ] ,
S′ = ∑ i∈I [ ‖MθD (vi)−MθD (q′vi)‖ ] .
and W = ∑ i∈I d(ui, D),
W ′ = ∑ i∈I d(vi, D)
By Definition 1, we have that rW ≤ S ≤ αrW,
and rW ′ ≤ S′ ≤ αrW ′.
Then, we can rewrite equation 27 as follows:∑ i∈I L(f(MθD (vi)))− L(f(MθD (ui)))
> L∗D 2 S′ − M ∗ D 2 S.
(13)
We know that M∗D > L ∗ D > 0. This means that there exists a constant β > 1 such that
M∗D = βL ∗ D.
Similarly, By the premise of the theorem, we have that,
S′ ≥ rW ′ > αrW ≥ S.
There exists a constant α > 1 such that S′ = γS.
Furthermore, we can obtain the following bound on the constant γ,
γ = S′
S
≥ rW ′
αrW
≥ 1 α
W ′
W
≥ 1 α δ
(14)
Substituting the above results into equation 28, we get that
1
2
[ L∗DS ′ −M∗DS ]
= 1
2
[ L∗DγS − βL∗DS ] = 1
2 L∗DS(γ − β)
(15)
Let’s take any δ > αβ and have that
γ − β = S ′
S − β,
> 1
α δ − β,
> 1
α αβ − β,
= 0.
(16)
Therefore, if δ > αβ, then we have∑ u∈Vtest L(f(MθD (u)))− L(f(MθD (u))) > 0 (17)
This completes the proof for Theorem 1.

heading: C PROOF FOR THEOREM 2
text: In this appendix, we provide a proof for Theorem 2. The proof is similar to the one presented for Theorem 1.
Proof. LetG = (V,E) be the input graph with node feature vectorXv for all v ∈ V . LetD,D′ ⊂ V be the training sets. LetM be a given GNN model. Let f be the prediction function that maps the output ofM to the class representation. Let L be the loss function with range R+. Let θD, θD′ be the sets of model parameters learnt using training set D,D′, which satisfy Assumption 2. In other words, we have,
∑ u∈D L(f(MθD (u))) = ∑ v∈D′ L(f(MθD′ (v))) = 0 (18)
Let T, T ′ be the two test sets satisfy the premise of the theorem. In other words, we have a one-toone mapping g : T 7→ T ′ with αrd(u,D) < rd(g(u), D′),∀u ∈ T . Now, let’s consider the loss on the test set T with the modelMD, which can be written as:∑
u∈T L(f(MθD (u))) (19)
By premise, we have that for each u ∈ T , there exists at least one v ∈ D such that M(u) ∈ Nrv (M(v)) where Nrv (M(v)) satisfies properties of Proposition 1. In other words, the loss function is monotonically increasing with respect to the embedding distance in Nrv (M(v)). By Lemma 1, we know that u can be in only one of this neighborhoods. Let Q : T 7→ D be the mapping that maps vertex u ∈ T to its corresponding simple neighborhood that is centered at a vertex Q(u) ∈ D. For simplicity, we denote the vertex as qu = Q(u). Due to Proposition 1 and Assumption 1, we can do a quadratic approximation of u around qu and have the following upper bound:
L(f(MθD (u))) ≤ L(f(MθD (qu))) + 〈MθD (u)−MθD (qu), DMθD (qu)〉
+ Mu 2 ‖MθD (u)−MθD (qu)‖
(20)
where Mu = sup{D2L(f(h))|h ∈ Nrqu (qu)},
and rqu = ‖qu − u‖.
Let M∗D = max{‖Mu‖|u ∈ T} (21)
M∗D exists since T is finite. Then, we obtain the following upper bound that is universal for all vertexes in T :
∑ u∈T L(f(MθD (u))) ≤ ∑ u∈T L1(u) + M∗D 2 ‖Mθu(u)−MθD (qu)‖ (22)
where L1(u) = L(f(MθD (qu))) + 〈Mθu(u)−MθD (qu), DMθD (qu)〉.
Similarly, let Q′ : T ′ 7→ D′ be the mapping that maps vertex u ∈ T ′ to its corresponding simple neighborhood that is centered at a vertex Q′(u) ∈ D′. For simplicity, we denote the vertex as q′u = Q
′(u). Again, due to Proposition 1 and Assumption 1, we can do a quadratic approximation of u around q′u and have the following lower bound:
L(f(MθD′ (u))) ≥ L(f(MθD′ (q ′ u))) + 〈MθD′ (u)−MθD′ (q ′ u), DMθD′ (q ′ u)〉
+ Lu 2 ‖MθD′ (u)−MθD′ (q ′ u)‖
(23)
where Lu = inf{D2L(f(h))|h ∈ Nrq′u (q ′ u)},
and rq′u = ‖q ′ u − u‖.
Let L∗D′ = min{‖Lu‖|u ∈ T ′} (24)
L∗D′ exists since T ′ is finite. Then, we obtain the following lower bound that is universal for all the vertexes in T ′:
∑ u∈T ′ L(f(MθD′ (u))) ≥ ∑ u∈T ′ L′1(u) + L∗D′ 2 ‖MθD′ (u)−MθD′ (q ′ u)‖ (25)
where L′1(u) = L(f(MθD′ (q ′ u))) + 〈MθD′ (u)−MθD′ (q ′ u), DMθD′ (q ′ u)〉.
For simplicity, suppose the cardinality of T and T ′ are k, and let I = {1, ..., k}. Let’s index and arrange the vertexes in T and T ′ such that,
T = {u1, ..., uk},
and T ′ = {v1, ..., vk},
such that vi = g(ui).
Let’s consider the difference between equation 25 and equation 22:
∑ u∈T ′ L(f(MθD′u)))− ∑ u∈T L(f(MθD (u)))
= ∑ i∈I L(f(MθD′ (vi)))− L(f(MθD (ui)))
> ∑ i∈I L′1(vi) + L∗D′ 2 ‖MθD′ (vi)−MθD′ (q ′ vi)‖ − L1(ui)− M∗D 2 ‖MθD (ui)−MθD (qui)‖
= ∑ i∈I (L′1(vi)− L1(ui)) + ∑ i∈I [L∗D′ 2 ‖MθD′ (vi)−MθD′ (q ′ vi)‖ − M∗D 2 ‖MθD (ui)−MθD (qui)‖ ] = ∑ i∈I (L′1(vi)− L1(ui))+ L∗D′
2 ∑ i∈I [ ‖MθD′ (vi)−MθD′ (q ′ vi)‖ ] − M ∗ D 2 ∑ i∈I [ ‖MθD (ui)−MθD (qui)‖ ] (26)
Since qui and q ′ vi are local minima of the loss function, we get that
L′1(vi) = L1(ui).
This leads to that∑ i∈I L(f(MθD′ (vi)))− L(f(MθD (ui)))
> L∗D′
2 ∑ i∈I [ ‖MθD′ (vi)−MθD′ (q ′ vi)‖ ] − M ∗ D 2 ∑ i∈I [ ‖MθD (ui)−MθD (qui)‖ ] (27)
To simplify the notation, let’s denote S = ∑ i∈I [ ‖MθD (ui)−MθD (qui)‖ ] ,
S′ = ∑ i∈I [ ‖MθD′ (vi)−MθD′ (q ′ vi)‖ ] .
and W = ∑ i∈I d(ui, D),
W ′ = ∑ i∈I d(vi, D ′)
By Definition 1, we have that rW ≤ S ≤ αrW,
and rW ′ ≤ S′ ≤ αrW ′.
Then, we can rewrite equation 27 as follows:∑ i∈I L(f(MθD′ (vi)))− L(f(MθD (ui)))
> L∗D′
2 S′ − M
∗ D
2 S.
(28)
Without loss of generality, we may assume M∗D > L ∗ D′ > 0. Otherwise, the proof is completed. This means that there exists a constant β > 1 such that
M∗D = βL ∗ D′ .
Similarly, By the premise of the theorem, we have that,
S′ ≥ rW ′ > αrW ≥ S.
There exists a constant α > 1 such that S′ = γS.
Furthermore, we can obtain the following bound on the constant γ,
γ = S′
S
≥ rW ′
αrW
≥ 1 α
W ′
W
≥ 1 α δ
(29)
Substituting the above results into equation 28, we get that
1
2
[ L∗D′S ′ −M∗DS ]
= 1
2
[ L∗D′γS − βL∗DS ] = 1
2 L∗D′S(γ − β)
(30)
Let’s take any δ′ > αβ and have that
γ − β = S ′
S − β,
> 1
α δ′ − β,
> 1
α αβ − β,
= 0.
(31)
Therefore, if δ′ > αβ, then we have∑ u∈Vtest L(f(MθD (u)))− L(f(MθD (u))) > 0 (32)
This completes the proof for Theorem 1.

heading: D MAXIMUM COVER
text: In this appendix we provide a detailed reduction of optimization (1) to the maximal coverage problem.
Let’s create binary variables Xv and yv for each vertex v ∈ V such that Xv indicates whether vertex v is selected in the cover and yv indicates whether vertex v is covered by some neighborhood of vertex in the selected set. We can rewrite optimization (1) as follows:
max ∑ v∈V yv
s.t. ∑ v∈V
Xv ≤ k∑ u∈Nr(v) Xu ≥ yv,∀v ∈ V
yv ∈ {0, 1} Xv ∈ {0, 1}
(33)
∑ v∈V Xv ≤ k ensures no more than k vertexes are selected into the set. ∑ u∈Nr(v)Xu ≥ yv,∀v ∈ V ensures that yv is 1 if and only if vertex v is covered by the neighborhood of some vertex u selected in the cover. The objective function is to maximize the number of vertexes covered. Optimization (33) has the standard form of maximal coverage problem as presented in (Hochbaum, 1996). Therefore, we can directly employ the heuristic algorithm and its performance guarantee in (Hochbaum, 1996).

heading: E PARTIAL COVER
text: In this appendix we provide a detailed reduction of optimization (2) to the partial coverage problem.
Let’s create binary variables Xv and yv for each vertex v ∈ V suc that Xv indicates whether vertex v is selected in the cover and yv indicates whether vertex v is covered by neighborhood of some vertex in the selected set. We can rewrite optimization (2) above as follows:
min ∑ v∈V Xv
s.t. ∑
u∈Nr(v)
Xu ≥ yv,∀v ∈ V
∑ v∈V yv ≥ g|V |
yv ∈ {0, 1} Xv ∈ {0, 1}
(34)
∑ u∈Nr(v)Xu ≥ yv,∀v ∈ V ensures that yv is 1 if and only if vertex v is covered by the neigh-
borhood of some vertex u selected in the cover. ∑ v∈V yv ≥ g|V | ensures that there are at least g|V | number of vertexes covered. The objective function is to minimize the number of vertex selected in the cover set. Optimization (34) has the standard form of partial coverage problem as presented in (Gandhi et al., 2004) and therefore, we can directly employ the heuristic algorithm and its performance guarantee in (Gandhi et al., 2004).

heading: F ADDITIONAL EXPERIMENTS
text: In this appendix, we provide additional experimental results and include detailed set-up of the experiments for reproducibility.
F.1 RANDOM PARTITION
In the experiments related to Fig. 1, all three models, GCN, GAT and GraphSage, have 3 layers with hidden dimensions of 16 and Relu as the activation function. We use 2 attention heads for GAT. We trained each model with Adam optimizer with a learning rate of 0.01, weight decay of 0.0005, and drop-out of 0. We keep all other hyperparameters as default. For each training, we randomly select a k (30 for Citeseer and 60 for PubMed) number of labelled vertexes as the training set and use the rest of labelled vertexes to evaluate the performance. We trained each model for 400 epochs and record the performance. Additional experimental results on Citeseer and PubMed are provided in Fig. 8 and Fig. 9.
Remark. From all these experiments, we can see that the variance on the performance of GNN induced by different training sets is indeed common and persistent across different data sets and GNN models.
F.2 GRAPH DISTANCE VS EMBEDDING DISTANCE
In the set of experiments related to Fig. 4, all three models, GCN, GAT and GraphSage, have 3 layers with hidden dimensions of 16 and Relu as the activation function. We trained each model with Adam optimizer with a learning rate of 0.01, weight decay of 0.0005, and drop-out of 0. We keep all other hyperparameters as default. For each training, we consider the largest connected component and randomly select k (30 for Citeseer and 60 for PubMed) number of labelled vertexes as the training set. We trained the model in 400 epochs. We randomly sample a set of vertexes from the graph that are not in the training set. We compute their graph/embedding distance (to the training set) and use them for the plots. The additional experimental results on Citeseer and PubMed datasets are provided in Fig. 10 and Fig. 11. In addition to the Euclidean distance metric, we also conducted similar experiments with the embedding distance computed by the cosine similarity. The results are provided in Fig. 12, Fig. 13 and Fig. 14.
Remark. Comparing to Cora and Citeseer, we can see that the distance preserving phenomenon on PubMed is significantly weaker and this could be due to the fact that PubMed data set does not have a strong network homophily property as the other two data sets. However, as we will see in later experiments, it is still strong enough to works well with our initial data labelling strategy. In addition, the above experiments show that the relation between graph distance and embedding
distance is persistent regardless of the metrics used for the computation (Euclidean and Cosine similarity).
F.3 TRAINING SET COVERAGE AND MODEL PERFORMANCE
In this set of experiments related to Table 2, all three models, GCN, GAT and GraphSage, have 3 layers with hidden dimensions of 16 and Relu as the activation function. We use 2 attention heads for GAT. We trained the model with Adam optimizer with a learning rate of 0.01, weight decay of 0.0005 and drop-out of 0. We keep all other hyperparameters as default. For Citeseer data set, we consider the largest connected component and randomly partition the labelled nodes into training set (of size 30) and test set for 100 times. Different partitions are ranked in increasing order of the distance between training set and test set. Metrics are evaluated in three cases: (1) “Random”: all 100 ways of partitions are used; (2) Top 50 %: top half of the ranked partitions are used; (3) Top 30 %: top 30 % of the ranked partitions are used. Mean distance is the average graph distance between training set and test set. For each training, we trained the model in 400 epochs and record the performance from each training. The additional experimental results on Citeseer are provided in Table 4.
F.4 INITIAL DATA LABELLING
In this set of experiments related to Table 3, all three models, GCN, GAT and GraphSage, have 3 layers with hidden dimensions of 16 and Relu as the activation function. We use 2 attention heads for GAT. We trained the model with Adam optimizer with a learning rate of 0.01, weight decay of 0.0005 and drop-out of 0. We keep all other hyperparameters as default. For each training, we trained the model in 400 epochs and record the best performance from each training. For the “cover” strategy following the greedy algorithm in (Hochbaum, 1996), we greedily select the next vertexes to be the vertexes whose r-hop neighborhood has the most uncovered vertexes. If there are more than one candidates, we randomly pick one from the candidate set, and then we update and repeat the selection procedure. The additional experimental results on Citeseer and PubMed are provided in Table 5 and Table 6.
Remark. Based on the experimental results, GAT models significantly outperform (in terms of accuracy and variance) the other two models when the size of the training set is small. This makes an interesting research question: why GAT is able to generalize much better than GCN and GraphSAGE? This could be interesting to explore in the future.

Review summaries:
This paper draws connection between performance of GNN and training set coverage in the graph. Specifically, it proposes theoretical study towards structural relation between them in terms of graph distance and empirical classification loss. A set of experiments are designed to validate the theory and assumption on three graph dataset. Further, the proposed idea is used in active learning as guidance.

This paper considers the problem of training set selection for graph neural network training. It shows that the generalization from the training to the test set in a well-trained graph neural network is closely tied to the shortest path distance in the graph, which motivates training strategies that "cover" the graph in this sense. The authors apply these ideas in a subset selection program, and verify their results with numerical experiments.