Subgroup Generalization and Fairness of Graph Neural Networks
Year: 2021

Abstract:
Despite enormous successful applications of graph neural networks (GNNs), theoretical understanding of their generalization ability, especially for node-level tasks where data are not independent and identically-distributed (IID), has been sparse. The theoretical investigation of the generalization performance is beneficial for understanding fundamental issues (such as fairness) of GNN models and designing better learning methods. In this paper, we present a novel PAC-Bayesian analysis for GNNs under a non-IID semi-supervised learning setup. Moreover, we analyze the generalization performances on different subgroups of unlabeled nodes, which allows us to further study an accuracy-(dis)parity-style (un)fairness of GNNs from a theoretical perspective. Under reasonable assumptions, we demonstrate that the distance between a test subgroup and the training set can be a key factor affecting the GNN performance on that subgroup, which calls special attention to the training node selection for fair learning. Experiments across multiple GNN models and datasets support our theoretical results4.

heading: 1 Introduction
text: Graph Neural Networks (GNNs) [13, 35, 20] are a family of machine learning models that can be used to model non-Euclidean data as well as inter-related samples in a flexible way. In recent years, there have been enormous successful applications of GNNs in various areas, such as drug discovery [18], computer vision [29], transportation forecasting [49], recommender systems [48], etc. Depending on the type of prediction target, the application tasks can be roughly categorized into node-level, edge-level, subgraph-level, and graph-level tasks [46].
In contrast to the marked empirical success, theoretical understanding of the generalization ability of GNNs has been rather limited. Among the existing literature, some studies [9, 11, 25] focus on the analysis of graph-level tasks where each sample is an entire graph and the samples of graphs are IID. A very limited number of studies [36, 42] explore GNN generalization for node-level tasks but they assume the nodes (and their associated neighborhoods) are IID samples, which does not align with the commonly seen graph-based semi-supervised learning setups. Baranwal et al. [3] investigate GNN generalization without IID assumptions but under a specific data generating mechanism.
In this work, our first contribution is to provide a novel PAC-Bayesian analysis for the generalization ability of GNNs on node-level tasks with non-IID assumptions. In particular, we assume the node features are fixed and the node labels are independently sampled from distributions conditioned on the node features. We also assume the training set and the test set can be chosen as arbitrary subsets of nodes on the graph. We first prove two general PAC-Bayesian generalization bounds (Theorem 1
∗School of Information, University of Michigan, Ann Arbor, Michigan, USA †Equal contribution. ‡Department of EECS, University of Michigan, Ann Arbor, Michigan, USA 4Code available at https://github.com/TheaperDeng/GNN-Generalization-Fairness.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
and Theorem 2) under this non-IID setup. Subsequently, we derive a generalization bound for GNN (Theorem 3) in terms of characteristics of the GNN models and the node features.
Notably, the generalization bound for GNN is influenced by the distance between the test nodes and the training nodes in terms of their aggregated node features. This suggests that, given a fixed training set, test nodes that are “far away” from all the training nodes may suffer from larger generalization errors. Based on this analysis, our second contribution is the discovering of a type of unfairness that arises from theoretically predictable accuracy disparity across some subgroups of test nodes. We further conduct a empirical study that investigates the prediction accuracy of four popular GNN models on different subgroups of test nodes. The results on multiple benchmark datasets indicate that there is indeed a significant disparity in test accuracy among these subgroups.
We summarize the contributions of this work as follows:
(1) We establish a novel PAC-Bayesian analysis for graph-based semi-supervised learning with non-IID assumptions.
(2) Under this setup, we derive a generalization bound for GNNs that can be applied to an arbitrary subgroup of test nodes.
(3) As an implication of the generalization bound, we predict that there would be an unfairness of GNN predictions that arises from accuracy disparity across subgroups of test nodes.
(4) We empirically verify the existence of accuracy disparity of popular GNN models on multiple benchmark datasets, as predicted by our theoretical analysis.

heading: 2 Related Work

heading: 2.1 Generalization of Graph Neural Networks
text: The majority of existing literature that aims to develop theoretical understandings of GNNs have focused on the expressive power of GNNs (see Sato [34] for a survey along this line), while the number of studies trying to understand the generalizability of GNNs is rather limited. Among them, some [9, 11, 25] focus on graph-level tasks, the analyses of which cannot be easily applied to node-level tasks. As far as we know, Scarselli et al. [36], Verma and Zhang [42], and Baranwal et al. [3] are the only existing studies investigating the generalization of GNNs on node-level tasks, even though node-level tasks are more common in reality. Scarselli et al. [36] present an upper bound of the VC-dimension of GNNs; Verma and Zhang [42] derive a stability-based generalization bound for a single-layer GCN [20] model. Yet, both Scarselli et al. [36] and Verma and Zhang [42] (implicitly) assume that the training nodes are IID samples from a certain distribution, which does not align with the common practice of node-level semi-supervised learning. Baranwal et al. [3] investigate the generalization of graph convolution under a specific data generating mechanism (i.e., the contextual stochastic block model [8]). Our work presents the first generalization analysis of GNNs for non-IID node-level tasks without strong assumptions on the data generating mechanism.

heading: 2.2 Fairness of Machine Learning on Graphs
text: The fairness issues of machine learning on graphs start to receive research attention recently. Following conventional machine learning fairness literature, the majority of previous work along this line [1, 5–7, 22, 32, 39, 50] concerns about fairness with respect to a given sensitive attribute, such as gender or race, which defines protected groups. In practice, the fairness issues of learning on graphs are much more complicated due to the asymmetric nature of the graph-structured data. However, only a few studies [19] investigate the unfairness caused by the graph structure without knowing a sensitive feature. Moreover, in a node-level semi-supervised learning task, the non-IID sampling of training nodes brings additional uncertainty to the fairness of the learned models. This work is the first to present a learning theoretic analysis under this setup, which in turn suggests how the graph structure and the selection of training nodes may influence the fairness of machine learning on graphs.

heading: 2.3 PAC-Bayesian Analysis
text: PAC-Bayesian analysis [27] has become one of the most powerful theoretical framework to analyze the generalization ability of machine learning models. We will briefly introduce the background in
Section 3.2, and refer the readers to a recent tutorial [14] for a systematic overview of PAC-Bayesian analysis. We note that Liao et al. [25] recently present a PAC-Bayesian generalization bound for GNNs on IID graph-level tasks. Both Liao et al. [25] and this work utilize results from Neyshabur et al. [30], a PAC-Bayesian analysis for ReLU-activated neural networks, in part of our proofs. Compared to Neyshabur et al. [30], the key contribution of Liao et al. [25] is the derivation of perturbation bounds of two types of GNN architectures; while the key contribution of this work is the novel analysis under the setup of non-IID node-level tasks. There is also an existing work of PAC-Bayesian analysis for transductive semi-supervised learning [4]. But it is different from our problem setup and, in particular, it cannot be used to analyze the generalization on subgroups.

heading: 3 Preliminaries
text: In this section, we first formulate the problem of node-level semi-supervised learning. We also provide a brief introduction of the PAC-Bayesian framework.

heading: 3.1 The Problem Formulation and Notations
text: Semi-supervised node classification. Let G = (V,E) ∈ GN be an undirected graph, with V = {1, 2, . . . , N} being the set of N nodes and E ⊆ V × V being the set of edges. And GN is the space of all undirected graphs with N nodes. The nodes are associated with node features X ∈ RN×D and node labels y ∈ {1, 2, . . . ,K}N . In this work, we focus on the transductive node classification setting [47], where the node features X and the graph G are observed prior to learning, and every quantity of interest in the analysis will be conditioned on X and G. Without loss of generality, we treat X and G as fixed throughout our analysis, and the randomness comes from the labels y. In particular, we assume that for each node i ∈ V , its label yi is generated from an unknown conditional distribution Pr(yi | Zi), where Z = g(X,G) and g : RN×D × GN → RN×D ′ is an aggregation function that aggregates the features over (multi-hop) local neighborhoods5. We also assume that the node labels are generated independently conditional on their respective aggregated features Zi’s.
Given a small set of the labeled nodes, V0 ⊆ V , the task of node-level semi-supervised learning is to learn a classifier h : RN×D × GN → RN×K from a function family H and perform it on the remaining unlabeled nodes. Given a classifier h, the classification for a node i is obtained by
ŷi = argmax k∈{1,...,K} hi(X,G)[k],
where hi(X,G) is the i-th row of h(X,G) and hi(X,G)[k] refers to the k-th element of hi(X,G).
Subgroups. In Section 4, we will present an analysis of the GNN generalization performance on any subgroup of the set of unlabeled nodes, V \ V0. Note that the analysis on any subgroup is a stronger result than that on the entire unlabeled set, as any set is a subset of itself. Later we will show that the analysis on subgroups (rather than on the entire set) further allows us to investigate the accuracy disparity across subgroups. We denote a collection of subgroups of interest as V1, V2, . . . , VM ⊆ V \ V0. In practice, a subgroup can be defined based on an attribute of the nodes (e.g., a gender group), certain graph-based properties, or an arbitrary partition of the nodes. We also define the size of each subgroup as Nm := |Vm|,m = 0, . . . ,M .
Margin loss on each subgroup. Now we can define the empirical and expected margin loss of any classifier h ∈ H on each subgroup Vm,m = 0, 1, . . . ,M . Given a sample of observed node labels yi’s, the empirical margin loss of h on Vm for a margin γ ≥ 0 is defined as
L̂γm(h) := 1
Nm ∑ i∈Vm 1 [ hi(X,G)[yi] ≤ γ + max k 6=yi hi(X,G)[k] ] , (1)
where 1 [·] is the indicator function. The expected margin loss is the expectation of Eq. (1), i.e.,
Lγm(h) := Eyi∼Pr(y|Zi),i∈VmL̂ γ m(h). (2)
5A simple example is gi(X,G) = 1|N (i)|+1 ( Xi + ∑ j∈N (i) Xj ) , where gi(X,G) is the i-th row of
g(X,G) and N (i) := {j | (i, j) ∈ E} is the set of 1-hop neighbors of node i.
To simplify the notation, we define ym := {yi}i∈Vm ,∀m = 0, . . . ,M , so that Eq. (2) can be written as Lγm(h) = EymL̂γm(h). We note that the classification risk and empirical risk of h on Vm are respectively equal to L0m(h) and L̂0m(h).

heading: 3.2 The PAC-Bayesian Framework
text: The PAC-Bayesian framework [27] is an approach to analyze the generalization ability of a stochastic predictor drawn from a distribution Q over the predictor familyH that is learned from the training data. For any stochastic classifier distributionQ andm = 0, . . . ,M , slightly overloading the notation, we denote the empirical margin loss of Q on Vm as L̂γm(Q), and the corresponding expected margin loss as Lγm(Q). And they are given by
L̂γm(Q) := Eh∼QL̂γm(h), Lγm(Q) := Eh∼QLγm(h).
In general, a PAC-Bayesian analysis aims to bound the generalization gap between Lγm(Q) and L̂γm(Q). The analysis is usually done by first proving that, for any “prior” distribution6 P over H that is independent of the training data, the generalization gap can be controlled by the discrepancy between P and Q; the analysis is then followed by careful choices of P to get concrete upper bounds of the generalization gap. While the PAC-Bayesian framework is built on top of stochastic predictors, there exist standard techniques [23] that can be used to derive generalization bounds for deterministic predictors from PAC-Bayesian bounds.
Finally, we denote the Kullback-Leibler (KL) divergence as DKL(Q‖P ) := ∫
ln dQdP dQ, which will be used in the following analysis.

heading: 4 The Generalization Bound and Its Implications for Fairness
text: As we mentioned in Section 2.3, existing PAC-Bayesian analyses cannot be directly applied to the nonIID semi-supervised learning setup where we care about the generalization (and its disparity) across different subgroups of the unlabeled samples. In this section, we first present general PAC-Bayesian theorems for subgroup generalization under our problem setup; then we derive a generalization bound for GNNs and discuss fairness implications of the bound.

heading: 4.1 General PAC-Bayesian Theorems for Subgroup Generalization
text: Stochastic classifier bound. We first present the general PAC-Bayesian theorem (Theorem 1) for subgroup generalization of stochastic classifiers. The generalization bound depends on a notion of expected loss discrepancy between two subgroups as defined below.
Definition 1 (Expected Loss Discrepancy). Given a distribution P overH, for any λ > 0 and γ ≥ 0, for any two subgroups Vm and Vm′ (0 ≤ m,m′ ≤M ), define the expected loss discrepancy between Vm and V0 with respect to (P, γ, λ) as
Dγm,m′(P ;λ) := lnEh∼P e λ(Lγ/2m (h)−L γ m′ (h)),
where Lγ/2m (h) and Lγm′(h) follow the definition of Eq. (2).
Intuitively, Dγm,m′(P ;λ) captures the difference of the expected loss between Vm and Vm′ in an average sense (over P ). Note that Dγm,m′(P ;λ) is asymmetric in terms of Vm and Vm′ , and can be negative if the loss on Vm is mostly smaller than that on Vm′ .
For stochastic classifiers, we have the following Theorem 1. Proof can be found in Appendix A.1.
Theorem 1 (Subgroup Generalization of Stochastic Classifiers). For any 0 < m ≤M , for any λ > 0 and γ ≥ 0, for any “prior” distribution P onH that is independent of the training data on V0, with
6The distribution is called “prior” in the sense that it doesn’t depend on training data. “Prior” and “posterior” in PAC-Bayesian are different with those in conventional Bayesian statistics. See Guedj [14] for details.
probability at least 1− δ over the sample of y0, for any Q onH, we have7
Lγ/2m (Q) ≤ L̂ γ 0(Q) +
1
λ
( DKL(Q‖P ) + ln 1
δ +
λ2
4N0 +Dγm,0(P ;λ)
) . (3)
Theorem 1 can be viewed as an adaptation of a result by Alquier et al. [2] from the IID supervised setting to our non-IID semi-supervised setting. The terms DKL(Q‖P ), ln 2δ , and λ2 4N0 are commonly seen in PAC-Bayesian analysis for IID supervised setting. In particular, when setting λ = Θ( √ N0), 1λ ( ln 2δ + λ2
4N0
) vanishes as the training size N0 grows. The divergence between Q
and P , DKL(Q‖P ), is usually considered as a measurement of the model complexity [14]. And there will be a trade-off between the training loss, L̂γ0(Q), and the complexity (how far can the learned “posterior” Q go from the “prior” P ).
Uniquely for the non-IID semi-supervised setting, there is an extra term Dγm,0(P ;λ), which is the expected loss discrepancy between the target test subgroup Vm and the training set V0. Note that this quantity is independent of the training labels y0. Not surprisingly, it is difficult to give generalization guarantees if the expected loss on Vm is much larger than that on V0 for any stochastic classifier P independent of training data. We have to make some assumptions about the relationship between Vm and V0 to obtain a meaningful bound on 1λD γ m,0(P ;λ), which we will discuss in details in Section 4.2.
Deterministic classifier bound. Utilizing standard techniques in PAC-Bayesian analysis [23, 27, 30], we can convert the bound for stochastic classifiers in Theorem 1 to a bound for deterministic classifiers as stated in Theorem 2 below (see Appendix A.2 for the proof).
Theorem 2 (Subgroup Generalization of Deterministic Classifiers). Let h̃ be any classifier inH. For any 0 < m ≤M , for any λ > 0 and γ ≥ 0, for any “prior” distribution P onH that is independent of the training data on V0, with probability at least 1− δ over the sample of y0, for any Q onH such that Prh∼Q ( maxi∈V0∪Vm ‖hi(X,G)− h̃i(X,G)‖∞ < γ 8 ) > 12 , we have
L0m(h̃) ≤ L̂ γ 0(h̃) +
1
λ
( 2(DKL(Q‖P ) + 1) + ln 1
δ +
λ2
4N0 +D
γ/2 m,0(P ;λ)
) . (4)
Theorem 1 and 2 are not specific to GNNs and hold for any (respectively stochastic and deterministic) classifier under the semi-supervised setup. In Section 4.2, we will apply Theorem 2 to obtain a subgroup generalization bound that explicitly depends on the characteristics of GNNs and the data.

heading: 4.2 Subgroup Generalization Bound for Graph Neural Networks
text: The GNN model. We consider GNNs where the node feature aggregation step and the prediction step are separate. In particular, we assume the GNN classifier takes the form of hi(X,G) = f(gi(X,G);W1,W2, . . . ,WL), where g is an aggregation function as we described in Section 3.1 and f is a ReLU-activated L-layer Multi-Layer Perceptron (MLP) with W1, . . . ,WL as parameters for each layer8. Denote the largest width of all the hidden layers as b. Remark 1. There is a technical restriction on the possible choice of the aggregation function g. For the following derivation of the generalization bound (6) to be valid, we need the condition that the node labels yi’s are independent conditional on their aggregated features gi(X,G)’s, as introduced in the problem formulation in Section 3.1. However, we also note that this condition tends to hold when the aggregated features gi(X,G)’s contain rich information about the labels.
Upper-bounding Dγm,0(P ;λ). To derive the generalization guarantee, we need to upper-bound the expected loss discrepancy Dγm,0(P ;λ). It turns out that we have to make some assumptions on the data in order to get a meaningful upper bound.
So far we have not had any restrictions on the conditional label distributions Pr(yi = k | gi(X,G)). If the label distributions on V \ V0 can be arbitrarily different from those on V0, the generalization
7Theorem 1 also holds when we substitute Lγ/2m (h) and Lγ/2m (Q) as Lγm(h) and Lγm(Q) respectively. But we state Theorem 1 in this form to ease the presentation of the later analysis.
8SGC [45] and APPNP [21] are special cases of GNNs in this form.
can be arbitrarily poor. We therefore assume that the label distributions conditional on aggregated features are smooth (Assumption 1). Assumption 1 (Smoothness of Data Distribution). Assume there exist c-Lipschitz continuous functions η1, η2, . . . , ηK : RD
′ → [0, 1], such that, for any node i ∈ V , Pr(yi = k | gi(X,G)) = ηk(gi(X,G)),∀k = 1, . . . ,K.
We also need to characterize the relationship between a target test subgroup Vm and the training set V0. For this purpose, we define the distance from Vm to V0 and the concept of near set below. Definition 2 (Distance To Training Set and Near Set). For each 0 < m ≤ M , define the distance from the subgroup Vm to the training set V0 as
m := max j∈Vm min i∈V0 ‖gi(X,G)− gj(X,G)‖2.
Further, for each i ∈ V0, define the near set of i with respect to Vm as
V (i)m := {j ∈ Vm | ‖gi(X,G)− gj(X,G)‖2 ≤ m}. Clearly,
Vm = ∪i∈V0V (i)m .
Then, with the Assumption 2 and 3 below, we can bound the expected loss discrepancy Dγm,0(P ;λ) with the following Lemma 1 (see the proof in Appendix A.3). Assumption 2 (Equal-Sized and Disjoint Near Sets). For any 0 < m ≤M , assume the near sets of each i ∈ V0 with respect to Vm are disjoint and have the same size sm ∈ N+. Assumption 3 (Concentrated Expected Loss Difference). Let P be a distribution onH, defined by sampling the vectorized MLP parameters fromN (0, σ2I) for some σ2 ≤ (γ/8 m) 2/L
2b(λN−α0 +ln 2bL) . For anyL-
layer GNN classifier h ∈ H with model parameters Wh1 , . . . ,WhL , define Th := maxl=1,...,L ‖Wl‖2. Assume that there exists some 0 < α < 14 satisfying
Pr h∼P
( Lγ/4m (h)− L γ/2 0 (h) > N −α 0 + cK m | TLh m > γ
8
) ≤ e−N 2α 0 .
Lemma 1 (Bound for Dγm,0(P ;λ)). Under Assumption 1, 2 and 3, for any 0 < m ≤ M , any 0 < λ ≤ N2α0 and γ ≥ 0, assume the “prior” P on H is defined by sampling the vectorized MLP parameters from N (0, σ2I) for some σ2 ≤ (γ/8 m) 2/L
2b(λN−α0 +ln 2bL) . We have
D γ/2 m,0(P ;λ) ≤ ln 3 + λcK m. (5)
Intuitively, what we need to bound Dγm,0(P ;λ) is that the training set V0 is “representative” for Vm. This is reasonable in practice as it is natural to select the training samples according to the distribution of the population. Specifically, Assumption 2 assumes that Vm can be split into equalsized partitions indexed by the training samples. The elements of each partition V (i)m are close to the corresponding training sample i but not so close to training samples other than i. This assumption is stronger than needed to obtain a meaningful bound on Dγm,0(P ;λ), and we can relax it by only assuming that most samples in Vm have proportional “close representatives” in V0. But we keep Assumption 2 in this work, as it is intuitively clear and significantly eases the analysis and notations. Assumption 3 essentially assumes that the expected margin loss on Vm is not much larger than that on V0 when the number of samples becomes large. We first note that this assumption becomes trivially true in the degenerate case that all samples in Vm and V0 are IID. In this case, Lγ/4m (h) = Lγ/40 (h) < L γ/2 0 (h) ≤ 0 for any classifier h. In Appendix A.5, we further provide a simple non-IID example where Assumption 3 holds.
The bound (5) suggests that the closer between Vm and V0 (smaller m), the smaller the expected loss discrepancy.
Bound for GNNs. Finally, with an additional technical assumption (Assumption 4) that the maximum L2 norm of aggregated node features does not grow too fast in terms of the number of training samples, we obtain a subgroup generalization bound for GNNs in Theorem 3. The proof of Theorem 3 can be found in Appendix A.4.
Assumption 4. Define Bm := maxi∈V0∪Vm ‖gi(X,G)‖2. For any classifier h̃ ∈ H with parameters {W̃l}Ll=1, assume ‖W̃l‖F ≤ C for l = 1, . . . , L. Assume Bm, C are constants with respect to N0. Theorem 3 (Subgroup Generalization Bound for GNNs). Let h̃ be any classifier inH with parameters {W̃l}Ll=1. Under Assumptions 1, 2, 3, and 4, for any 0 < m ≤M , γ ≥ 0, and large enough N0, with probability at least 1− δ over the sample of y0, we have
L0m(h̃) ≤ L̂ γ 0(h̃) +O ( cK m + b ∑L l=1 ‖W̃l‖2F
(γ/8)2/LNα0 ( m)
2/L + 1
N1−2α0 +
1 N2α0 ln LC(2Bm)
1/L
γ1/Lδ
) .
(6)
Next, we investigate the qualitative implications of our theoretical results.

heading: 4.3 Implications for Fairness of Graph Neural Networks
text: Theoretically predictable accuracy disparity. One merit of our analysis is that we can apply Theorem 3 on different subgroups of the unlabeled nodes and compare the subgroup generalization bounds. This allows us to study the accuracy disparity across subgroups from a theoretical perspective.
A major factor that affects the generalization bound (6) is m, the aggregated-feature distance (in terms of g(X,G)) from the target test subgroup Vm to the training set V0. The generalization bound (6) suggests that there is a better generalization guarantee for subgroups that are closer to the training set. In other words, it is unfair for subgroups that are far away from the training set. While our theoretical analysis can only tell the difference among upper bounds of generalization errors, we empirically verify that, in the following Section 5, the aggregated-feature distance m is indeed a strong predictor for the test accuracy of each subgroup Vm. More specifically, the test accuracy decreases as the distance increases, which is consistent with the theoretical prediction given by the bound (6).
Impact of the structural positions of nodes. We further investigate if the aggregated-feature distance can be related to simpler and more interpretable graph characteristics, in order to obtain a more intuitive understanding of how the structural positions of nodes influence the prediction accuracy on them. We find that the geodesic distance (length of the shortest path) between two nodes is positively related to the distance between their aggregated features in some scenarios9, such as when the node features exhibit homophily [28]. Empirically, we also observe that test nodes with larger geodesic distance to the training set tend to suffer from lower accuracy (see Figure 2).
In contrast, we find that common node centrality metrics (e.g., degree and PageRank) have less influence on the test accuracy (see Figure 3). These centrality metrics only capture the graph characteristics of the test nodes alone, but do not take their relationship to the training set into account, which is a key factor suggested by our theoretical analysis.
Impact of training data selection. Another implication of the theoretical results is that the selection of the training set plays an important role on the fairness of the learned GNN models. First, if the training set is selected unevenly on the graph, leaving part of the test nodes far away, there will likely be a large accuracy disparity. Second, a key ingredient in the proof of Lemma 1 is that the GNN predictions on two nodes tend to be more similar if they are closer in terms of the aggregated node features. This suggests that, if an individual training node is close to many test nodes, it may bias the predictions of the learned GNN on the test nodes towards the class it belongs to.

heading: 5 Experiments
text: In this section, we empirically verify the fairness implications suggested by our theoretical analysis.
General setup. We experiment on 4 popular GNN models, GCN [20], GAT [41], SGC [45], and APPNP [21], as well as an MLP model for reference. For all models, we use the implementations by Deep Graph Library [43]. For each experiment setting, 40 independent trials are carried out.

heading: 5.1 Accuracy Disparity Across Subgroups
text: Subgroups. We examine the accuracy disparity with three types of subgroups as described below. 9A more detailed discussion on such scenarios is provided in Appendix D.1.
Subgroup by aggregated-feature distance. In order to directly investigate the effect of m on the generalization bound (6), we first split the test nodes into subgroups by their distance to the training set in terms of the aggregated features. We use the two-step aggregated features to calculate the distance. In particular, denote the adjacency matrix of the graph G as A ∈ {0, 1}N×N and the corresponding degree matrix as D, where D is an N ×N diagonal matrix with Dii = ∑N j=1Aij ,∀i = 1, . . . , N . Given the feature matrix X ∈ RN×D, the two-step aggregated features Z are obtained by Z = (D + I)−1(A + I)(D + I)−1(A + I)X . For each test node i, we calculate its aggregated-feature distance to the training set V0 as di = minj∈V0 ‖Zi −Zj‖2. Then we sort the test nodes according to this distance and split them into 5 equal-sized subgroups.
Strictly speaking, our theory does not directly apply to GCN and GAT as they are not in the form as we defined in Section 4.2. Moreover, the two-step aggregated feature does not match exactly to the feature aggregation function of SGC and APPNP. Nevertheless, we find that even with such approximations, we are still able to observe the expected descending trend of test accuracy with respect to increasing distance in terms of the two-step aggregated features, on all four GNN models.
Subgroup by geodesic distance. As we discussed in Section 4.3, geodesic distance on the graph may well relate to the aggregated-feature distance. So we also define subgroups based on geodesic distance. We split the subgroups by replacing the aggregated-feature distance di of each test node i with the minimum of the geodesic distances from i to each training node on the graph.
Subgroup by node centrality. Lastly, we define subgroups based on 4 types of common node centrality metrics (degree, closeness, betweenness, and PageRank) of the test nodes. We split the subgroups by replacing the aggregated-feature distance di of each test node i with the centrality score of i. The purpose of this setup is to show that the common node centrality metrics are not sufficient to capture the monotonic trend of test accuracy.
Experiment setup. Following common GNN experiment setup [38], we randomly select 20 nodes in each class for training, 500 nodes for validation, and 1,000 nodes for testing. Once training is done,
we report the test accuracy on subgroups defined by aggregated-feature distance, geodesic distance, and node centrality in Figure 1, 2, and 3 respectively10.
Experiment results. First, as shown in Figure 1, there is a clear trend that the accuracy of a test subgroup decreases as the aggregated-feature distance between the test subgroup and the training set increases. And the trend is consistent for all 4 GNN models on all the datasets we test on (except for APPNP on Cora). This result verifies the existence of accuracy disparity suggested by Theorem 3.
Second, we observe in Figure 2 that there is a similar trend when we split subgroups by the geodesic distance. This suggests that the geodesic distance on the graph can sometimes be used as a simpler indicator in practice for machine learning fairness on graph-structured data. Using such a classical graph metric as an indicator also helps us connect graph-based machine learning to network theory, especially to understandings about social networks, to better analyze fairness issues of machine learning on social networks, where high-stake decisions related to human subjects may be involved.
Furthermore, as shown in Figure 3, there is no clear monotonic trend for test accuracy when we split subgroups by node centrality, except for some particular combinations of GNN model and dataset. Empirically, the common node centrality metrics are not as good as the geodesic distance in terms of capturing the accuracy disparity. This contrast highlights the importance of the insight provided by our analysis: the “distance” to the training set, rather than some graph characteristics of the test nodes alone, is the key predictor of test accuracy.
Finally, it is intriguing that, in both Figure 1 and 2, the test accuracy of MLP (which does not use the graph structure) also decreases as the distance of a subgroup to the training set increases. This result is perhaps not surprising if the subgroups were defined by distance on the original node features, as MLP can be viewed as a special GNN where the feature aggregation function is an identity mapping, so the “aggregated features” for MLP essentially equal to the original features. Our theoretical analysis can then be similarly applied to MLP. The question is why there is also an accuracy disparity w.r.t. the aggregated-feature distance and the geodesic distance. We suspect this is because these datasets present homophily, i.e., original (non-aggregated) features of geodesically closer nodes tend to be more similar. As a result, a subgroup with smaller geodesic distance may also have closer node
10The main paper reports the results on a small set of datasets (Cora, Citeseer, and Pubmed [37, 47]). Results on more datasets, including large-scale datasets from Open Graph Benchmark [17], are shown in Appendix C.
features to the training set. To verify this hypothesis, we repeat the experiments in Figure 1, but with independent noises added to node features such that they become less homophilious. As in Figure 4, the decreasing pattern of test accuracy across subgroups remains for the 4 GNNs on all datasets; while for MLP, the pattern disappears on Cora and Pubmed and becomes less sharp on Citeseer.

heading: 5.2 Impact of Biased Training Node Selection
text: In all the previous experiments, we follow the standard GNN training setup where 20 training nodes are uniformly sampled for each class. Next we investigate the impact if the selection of training nodes is biased, verifying our discussions in Section 4.3. We will demonstrate that the node centrality scores of the training nodes play an important role in the learned GNN model.
We choose a “dominant class” and construct a manipulated training set. For each class, we still sample 20 training nodes but in a biased way. For the dominant class, the sample is biased towards nodes of high centrality; while for other classes, the sample is biased towards nodes of low centrality. We evaluate the relative ratio of False Positive Rate (FPR) for each class between the setup using manipulated training set and the setup using uniformly sampled training set.
As shown in Figure 5, compared to MLP, the GNN models have significantly worse FPR for the dominant class when the training nodes are biased. This is because, after feature aggregation, there will be a larger proportion of test nodes that are closer to the training nodes of higher centrality. And the learned GNN model will be heavily biased towards the training labels of these nodes.

heading: 6 Conclusion
text: We present a novel PAC-Bayesian analysis for the generalization ability of GNNs on node-level semi-supervised learning tasks. As far as we know, this is the first generalization bound for GNNs for non-IID node-level tasks without strong assumptions on the data generating mechanism. One advantage of our analysis is that it can be applied to arbitrary subgroups of the test nodes, which allows us to investigate an accuracy-disparity style of fairness for GNNs. Both the theoretical and empirical results suggest that there is an accuracy disparity across subgroups of test nodes that have varying distance to the training set, and nodes with larger distance to the training nodes suffer from a lower classification accuracy. In the future, we would like to utilize our theory to analyze the fairness of GNNs on real-world applications and develop principled methods to mitigate the unfairness.

heading: Acknowledgements
text: This work was in part supported by the National Science Foundation under grant number 1633370. The authors claim no competing interests.

Review summaries:
This paper investigates the subgroup generalization for graph neural networks. In particular, the authors present a PAC-Bayesian analysis for the generalization ability of GNNs on node-level semi-supervised learning tasks. By some theoretical analysis and empirical results, the authors demonstrate the claims to some extent.

This paper studies the non-IID sample generalization in Graph Neural Networks in a subgroup PAC-Bayesian analysis framework. Non-IID training samples are widely existing in real-world applications. It first derives several interesting theories based on several reasonable assumption on smoothness and node features. Several key observations are found between different subgroups in aggregated-feature and graph distance space support the theoretical discoveries.

This work presents PAC-Bayesian analysis for GNNs under a non-IID semi-supervised learning setup. It first analyzes the generalization performance for general settings, and then applies the results to GNNs. The theoretical results have been backed up with empirical evaluations on several graph benchmarks.