Subgroup Generalization and Fairness of Graph Neural Networks
Authors: Jiaqi Ma
Junwei Deng
Qiaozhu Mei
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Graph Neural Networks
Generalization
Fairness
PAC-Bayesian Analysis

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 results.

Subgroup Generalization and Fairness of Graph Neural Networks
Jiaqi Ma + j jiaqima@umic ch. edu
Junwei Deng + junweid@umich edu
Qiaozhu Mei qmei @umi ch edu
Abstract
Despite enormous successful applications of graph neural networks (GNNs), theo- retical understanding of their generalization ability, especially for node-level tasks where data are not independent and identically-distribuce (IID), has been sparse. The theoretical investigation of the generalization performance beneficial for understanding fundamental issues (such fairness) of GNN models and designing better learning methods. In this paper, we present a novel PAC-Bayesie analysis for GNNs under non-IID remi-superviise learning setup. Moreover, analyze the generalization performances on different subgroups of unlabeled nodes, which allows to further study accuracy (dis) (arrii)))atysttiiil (un)fairmess of GNNs from a theoretical perspective. Under reasonable assumptions, we demonstrate that the distance between test subgroup and the training set can be 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 results
1 Introduction
are a family of machine learning models that can be used model non-Euclidean data well as inter-related samples in flexible way. In recent years, there have been enormous successful applications 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)
Graph Neural Networks (GNNs) [3 35 20
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 [1 25 focus the analysis of graph-level tasks where each sample an entire graph and the samples of graphs are IID. A very limited number of studies [3 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
graph-based semi- cemi-supervised learning setups. Baranwal al. (3) investigate GNN generalization without IID assumptions but under a specific data generating mechanism.
In this work, our first contribution is provide 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 (Theoreml
"chool of Information, University of Michigan, Ann Arbor, Michigan, USA 'Equal contribution.
I DDpaarment EECS. University of Michigan, Ann Arbor, Michigan, USA *Code available at http://hhh....aaooooo//////////a Pairiess
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and Theorem under this non-llI setup. Subsequently, we derive generalization bound for GNN (Theorem 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 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 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 novel PAC-Bayesian analysis for graph-based semi-supervised learning with non- assumptions.
(2) Under this setup. we derive 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 unfaireess 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.
2 Related Work
2.1 Generalization of Graph Neural Networks
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 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 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 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 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 the data generating mechanism.
2.2 Fairness of Machine Learning Graphs
The fairness issues machine learning on graphs start to receive research attention recently. Fol- lowing conventional machine learning fairness literature, the majority of previous work along this
50 concerns about fairnsss with respect to a given sensitive attribute, such as gender race, which defines protected groups. In practice, the fairesss issues of learning graphs are much more complicated due to the asymmetric nature of the graph-structure data. However, only few studies [19] investigate the unfairness caused by the graph structure without knowing sensitive feature. Morcover, a node-level semi-supervised learning task, the non-IID sampling of training nodes brings additional uncertainty 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 fairnsss of machine learning graphs.
line D 5 22
32
39
2.3 PAC-Bayesian Analysis
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

---

and refer the readers to a recent tutorial 14] for systematic overview of PAC-Bayesian analysis. We note that Liao et al. 25 recently present a AAC-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 Rel.U-activated neural networks, in part of our proofs. Compared to Neyshabur et al. [O), 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 is different from our problem setup and, in particular, it cannot be used to analyze the generalization subgroups.
Section 3.2
3 Preliminaries
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.
3.1 The Problem Formulation and Notations
Semi-supervised node classification. Let G = (V, E GN be an undirected graph, with V (1, . being the of N nodes and E V x 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 NxD and node labels y (I, 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, node E V. its label yi is generated from an unknown conditional distribution Pr(ys Z.). where Z g(X, G) and g : R RNND x IN 7 R N is an aggregation function that aggregates the features over (multi-hop) local neighborhood We also assume that the node labels are generated independently conditional on their respective aggregated features Zj's.
assume that for each
Given a small set of the labeled nodes, Vo C V. the task of node-level semi-supervised learning is to learn a classifier h NDD x GN + N from a function family H and perform on the remaining unlabeled nodes. Given classifier h, the classification for node is obtained by
9. argmax h hx(X,G) [k]]
k).....,)
where (x, G) is the i-th row of k(X, G) and (x,X, G)] refers the le-th element of hx,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 Vn- Note that the analysis on any subgroup is stronger result than that the entire unlabeled set, any set is 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, V,,... VM C V \ Vo. 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 := [Vml, m = O.... M.
Margin loss on each subgroup. Now we can define the empirical and expected margin loss of any classifier h H. on each subgroup Vn, y 's, the empirical margin loss of on Vm for a margin 7 2 0 is defined as
0,..... .. Given sample of observed node labels
Σ hx I1
(x) == Nm VEV...
G)aa S max (x, (X, kA
(1)
where 1 [-] is the indicator function. The expected margin loss is the expectation of Eq. I i.e.
C% (h) = Ey
(h).
A simple example is g. G) प X, ΣSEN(H) X;). where gx C) is the i-th row of g(X, G) and AV(i)= (i (i.5) E) is the set of l-hop neighbors of node i.
3

---

To simplify the notation, we define y" := fEi vm = ..... so that Eq. 2 can be written L% (h) Enn C% (h). We note that the classification risk and empirical risk of h Vn. respectively equal to Cm (h) and Co (h).
3.2 The PAC-Bayesian Framework
The PAC-Bayesian framework 27 is an approach to analyze the generalization ability of stochastic predictor drawn from a distribution Q over the predictor family H that is learned from the training data. For any stochastic classifier distribution Q and m 0, ..... M, slightly overloading the notation, denote the empirical margin loss of Q on Vn 2% (Q), and the corresponding expected margin loss as L. (Q). And they are given by
...
2 (Q) = E 2m (h), 2 (Q) := En-q Cm (h).
In general, PAC-Bayesian analysis aims to bound the generalization gap between C% (Q) and C7, (Q). The analysis is usually done by first proving that, for any "prior" distribution P over H that is independent of the training data, the generalization gap be controlled by the discrepancy between P and Q; the analysis is then followed by careful choices P to get concrete upper bounds of the generalization gap. While the PAC-Bayesial framework built 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 DRL. (Q = f 4Q dfdQ, which will be used in the following analysis.
2/
4 The Generalization Bound and Its Implications for Fairness
As we mentioned in Section 2.3 existing MiC-Bayesian analyses cannot be directly applied the non- IID semi-supervised learning setup where we care about the generalization (and its disparity) across different subgroups the unlabeled samples. In this section, we first present general PAC-Bayesian theorems for subgroup generalization under our problem setup; then we derive generalization bound for GNNs and discuss fairness implications the bound.
4.1 General PAC-Bayesian Theorems for Subgroup Generalization
Stochastic classifier bound. We first present the general PAC-Bayesian theorem (Theorem I for subgroup generalization of stochastic classifiers. The generalization bound depends on a notion of expected loss discrepancy between two subgroups as defined below.
Definition (Expected Loss Discrepancy). Given a distribution P over H. for any >> and y 2 O, for any two subgroups Vn, and Vn (0 S m, m' < M), define the expected loss discrepancy between Vm and Vn with respect to (P, 7; A) as
D Dm (P; In Ee
where CT/2(h)
(h) and CT (h) follow the definition of Eq. 2
Intuitively, D m (P:A) captures the difference of the expected loss between Vn and Vn in an average sense (over P). Note that D Trn...( (P; A) is asymmetric terms of Vm, and Vnc, and can be negative if the loss on Vn, mostly smaller than that on Vnn..
For stochastic classifiers, we have the following Theorem I Proof can be found in Appendix A.
Theorem (Subgroup Generalization of Stochastic Classifiers). For any 0 < m S Mo any X > O and 7 2 0, for any "prior" distribution on H. that is independent of the training data on Vo. with
'The distribution is called "prior" in the sense that it doesn't it depend on training data. "Prior" and "posterior"
PAC-Bayesian different with those in conventional Bayesian statisties. See Guedj [14 for details.

---

probability at least - 8 over the sample of for any Q on H, we have
1 { + In 1 X²
(Q)
+ Dm Pimol::))
(3)
4No
Theorem [ can be viewed as an adaptation of a result by Alquier et al. from the IID super- vised setting to our non-lID semi-supervised setting. The terms (KL(Q] In g. and 4No are commonly seen in PAC-Bayesian analysis for IID supervised setting. In particular, when setting
X
vanishes the training size No grows. The divergence between Q and P. DKL(Q]1)), is usually considered measurement of the model complexity
(o) x In 2
X²
ANo
[14. And there will be a trade-off between the training loss, (Q)), and the complexity (how far can the learned "posterior" Q go from the "prior" P).
Uniquely for the non-IlD semi- supervised setting, there is an extra term D (P: A), which is the expected loss discrepancy between the target test subgroup Vn and the training set Vo. Note that this quantity is independent of the training labels yo. Not surprisingly, it is difficult give generalization guarantees if the expected loss on Vm is much larger than that on Vo for any stochastic classifier P independent of training data. We have to make some assumptions about the relationship between V... and Vo to obtain a meaningful bound on D (P; A), which we will discuss in details in Section 4.2
Deterministic classifier bound. Utilizing standard techniques in PAC-Bayesian analysis 2 21 30). we can convert the bound for stochastic classifiers in Theorem to a bound for deterministic classifiers as stated in Theorem below (see Appendix A.2 for the proof).
Theorem 2 (Subgroup Generalization of Deterministic Classifiers). Let h be any classifier in H. For any m S M. for any X 0 and 7 2 O, for any "prior" distribution P on H. that is independent of the training data on Vo, with probability at least 1 5 over the sample of y for any Q on H such
that Pra~Q maxievooV [1,,(X, G) - hx, G) < } >
2, we have
c (h) S (h) + 1 } 1 ((DK), 1) + In x
X + D(ABPP:))
(4)
4No
Theorem 1 and 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 subgroup generalization bound that explicitly depends on the characteristics of GNNs and the data.
4.2 Subgroup Generalization Bound for Graph Neural Networks
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 h,(X, G) (X, G); Wi, W2,..., Wr.), where g is an aggregation function as we described in Section 3.] and ff is a ReLU-activated L-layer Multi-Layer Perceptron (MLP) with W1,.. WL as parameters for each layer) Denote the largest width of all the hidden layers as
Remark 1. There is technical restriction 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 's are independent conditional on their aggregated features gi 9x,XX G)'s ss as introduced in the problem formulation in Section 3.7 However, we also note that this condition tends to hold when the aggregated features gi G) contain rich information about the labels.
Upper-bounding Di (P; A). To derive the generalization guarantee, need upper-bound the expected loss discrepancy D% of (P: A). It turns out that we have to make some assumptions on the data in order to get meaningful upper bound.
So far we have not had any restrictions the conditional label distributions Pr(y: k 9 (X,G)) G)). If the label distributions on V Vo can be arbitrarily different from those on Vo. the generalization
Theerrmm also holds when we substitute ( and / as Ch (h) and CT, (Q) respectively. But we state Theorem in this form to ease the presentation of the later analysis. $SGC [45) and APPNP 21 special cases of GNNs in this form.
5

---

can be arbitrarily poor. We therefore assume that the label distributions conditional on aggregated features are smooth (Assumption D..
Assumption 1 (Smoothness of Data Distribution). Assume there exist c-Lipschitz continuous func- lions 11, 12,
[] RRD' > [0, 1.. such that, for any node E V,
Pr(ys k g:(X G)) The ( G)), Ak- ,,..., K.
We also need characterize the relationship between a target test subgroup Vm and the training set Vo. For this purpose, we define the distance from Vm to Vo 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 Vo as
== max min (X, (X, G) - (X G) jeVm VEVo
Further, for each E Vo, define the near set of i with respect to Vm as
Vii = ti Vm [X, - (x G) S cm)
Clearly,
V = UKEVo V m
Then, with the Assumption 2 and 3 below, we can bound the expected loss discrepancy D m (P; A) with the following Lemma (see the proof in Appendix A.33)
Assumption 2 (Equal-Sized and Disjoint Near Sets). For any 0 < m S M, assume the near sets of each i Vo with respect to Vm are disjoint and have the same size 8m. E EN+
Assumption 3 (Concentrated Expected Loss Difference). Let P be distribution on H. defined by sampling the vectorized MLP parameters from (rommN(. (0, o0, I) some 0² S [t//8em) )2/L
For any L- Wh; define Tn max |Will
25(ANo +Io 26L)'
layer GNN classifier h H. with model parameters Wi...., w...... Assume that there exists some 0 < satisfying
(c/l C7
12 (h) > N + CcKm The Em Se No ~NO
Pr hwwP
and 3 for any O < m S M, any 0 < X S No and 2 0, assume the "prior" P on H is defined by sumpling the vectorized MLP parameters from N N(0, (0, 1) 1) for some o² S [n/88... 12/2
Lemma 1 (Bound for DT (P (P:A), Under Assumption
We have
28(AN6 +In 26L)
D DM In AcKem.
(5)
Intuitively, what we need to bound D (P:o((P)) is that the training set Vo is "representative" for Vm. This is reasonable practice as it is natural select the training samples according to the distribution of the population. Specifically, Assumption] 2 assumes that Vm can be split into equal- sized partitions indexed by the training samples. The elements of each partition V((i)
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 (P: A), and we can relax it by only assuming that most samples in Vm have proportional "close representatives" in Vo. But we keep Assumption
2 in this work, as it intuitively clear and significantly eases the analysis and notations. Assumption essentially assumes that the expected margin loss on V,, is not much larger than that on Vo when the number of samples becomes large. We first note that this assumption becomes trivially true in the degenerate case that all samples in V,, and V. are IID. In this case, (,/ /3 (h) (h) < for any classifier h. In Appendix A.S we further provide simple IID example where (issuppioon3]oolee
The bound 5 suggests that the closer between Vn and Vo (smaller cm), 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 subgroup generalization bound for GNNs in Theorem The proof of Theorem can be found in Appendix A.4

---

Assumption 4. Define Bm == max ( G) For any classifier h E H. with parameters (Wi)EE assume ||ii] F S C I,..., L. Assume Bm, C are constants with respect to No- Theorem 3 (Subgroup Generalization Bound for GNNs), Let h be any classifier in H with parameters (Wi)f Under Assumptions /
and 4 for any 0 < m S M, 72 2 0, and large enough No. with probability at least 8 over the sample of y", we have
Ca. (h) & (h) + + (cckee
b DE W (Em) 2/L
1
LC(2Bm)
In
(7/8)2/2N8
No
N1-2a 2a
No
71/48
(6)
Next, we investigate the qualitative implications of our theoretical results.
4.3 Implications for Fairness of Graph Neural Networks
Theoretically predictable accuracy disparity. One merit of our analysis is that we can apply Theorem JJ different subgroups the unlabeled nodes and compare the subgroup generalization
bounds. This allows us to study the accuracy disparity across subgroups from theoretical perspective.
major factor that affects the generalization bound (6) Ema the aggregated distance (in terms of 9XX, G)) from the target test subgroup Vm to the training set Vo. The generalization bound (6) suggests that there 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 | the beggreaated-featue distance Cm 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-featur distance 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 scenario 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
9 such as
In contrast, 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 that the selection of the training set plays 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 large accuracy disparity. Second, key ingredient in the proof of Lemma I 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.
Experiments
In this section, we empirically verify the fairness implications suggested by our theoretical analysis.
General setup. We experiment on popular GNN models, GCN 20 GAT [11, SGC 45), and APPNP (21), as well as an MLP model for reference. For all models, we use the implementations by For each experiment setting, 40 independent trials are carried out.
Deep Graph Library
(3
5.1 Accuracy Disparity Across Subgroups
Subgroups. We examine the accuracy disparity with three types of subgroups as described below.
A more detailed discussion such scenarios is provided in Appendix D.1
7

---

0.60
0.85
0.75
0.70
8
0.65
0.55
0.30
0.50
0.00
12345
12345
12365
12345
12345
12345
12345
12385
12345
12355
12345
12345
12345
12335
12365
S0C
50C
SBC
(a) Cora.
(b) Citeseer.
(c) Pubmed.
Figure Test accuracy disparity across subgroups by aggregated-feature distance. Each figure corresponds to a dataset, and each bar cluster corresponds to a model. Bars labeled 1 to 5 represent subgroups with increasing distance training Results averaged over 40 independent trials with different random splits of the data, and the error bar represents the standard error of the mean.
0.825
0.775
80.70
8 0.55
3.750
0.725
0.60
0.675
0.55
0.30
12345
12345
12345
12345
12345
0.59
12345
12345
12345
12345
12345
6.050
12345
12345
12345
12345
12345
(a) Cora.
(b) Citeseer.
(c) Pubmed.
Figure 2: Test accuracy disparity across subgroups by geodesic distance. The experiment and plot settings are the same as Figure except for the bars labeled from to 5 here represent subgroups with increasing shortest-path distance to training set.
Subgroup by aggregrtted-feature distance. In order to directly investigate the effect of em the generalization bound (6). we first split the test nodes into subgroups by their distance to the training set 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, 11 x and the corresponding degree matrix D. where D is an N N diagonal matrix with D Σ Ar,, Vi 1,...,N. N. RNXD, the two-step aggregated features Z are obtained by = 1D+1)-1(A + I)(D + 1)-1 (A 7)X. For each test node i, we calculate its aggregated-featd feature distance to the training set Vy as d; = mingev, I Zyl12- Then we sort the test nodes according to this distance and split them into 5 equal-sized subgroups.
Given the feature matrix
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 the two-step aggregated features, on four GNN models.
Subgroup by geodesic distance. As we discussed in Section 4.3 geodesic distance on the graph may well relate the aggregated-feature distance. So also define subgroups based geodesic distance. We split the subgroups by replacing the settregated-fftttre distance d, of each test node i with the minimum of the geodesic distances from to each training node on the graph.
Subgroup by node centrality. Lastly, we define subgroups based on types of common node centrality metrics (degree, closeness, betweenness, and PageRank) of the test nodes. We split the subgroups by replacing the aggregated-featur distance d, of each test node with the centrality score of i. The purpose of this setup is to show that the common node centrality metrics not sufficient to capture the monotonic trend of test accuracy.
Experiment setup. Following common GNN experiment setup 38 we randomly select nodes in each class for training, 500 nodes for validation, and 1,000 nodes for testing, Once training is done,

---

6:00
/ 6.250
6.70
0.72
6,10
6.72
6:375
6.70
0.25
(a) GCN Cora.
(b) GAT on Cora.
(c) APPNP on Cora.
6.75
5.00
5.70
1.05
6.70
0.25
0.99
0:43
1.50
0.50
4-244
0:35
12249
(d) GCN on Citeseer.
(c) GAT on Citeseer.
(f) APPNP on Citeseer.
1.70
6.42
6.70
0.30
5.N0-
6..70
1.00
0.79
(g) GCN on Pubmed.
(h) GAT on Pubmed.
(i) APPNP on Pubmed.
Figure 3: Test accuracy disparity across subgroups by node centrality. Each figure corresponds to
the results of pair of model and dataset, and each bar cluster corresponds to the subgroups defined by a certain centrality metric. In each cluster, the hars labeled from to 5 represent subgroups with decreasing node centrality. Other settings are the same as Figure I
we report the test accuracy on subgroups defined by aggregated-feall feature distance, geodesic distance, and node centrality in Figure 2 and rrespcctively [T0
Experiment results. First, as shown in Figure D there is a clear trend that the accuracy of a test subgroup decreases as the sagregated-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 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 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.
simpler
Furthermore, as shown in Figure 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 intriguing that, in both Figure I and the test accuracy of MLP (which does not use the graph structure) also decreases as the distance of a subgroup 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 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- -feture 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
The main paper reports the results on small set of datasets (Cora, Citeseer, and Pubmed (37 47,47) Results more datasets, including large-scale datasets from Open Graph Benchmark [17]. shown in Appendix C

---

9.8
0.7
0.4
0.5
0.3
12345
12345
12335
12345
12345
12345
12345
12585
12345
12355
12365
12345
12345
32355
12365
SGC
SGC
SGC
(a) Cora.
(b) Citeseer.
(c) Pubmed.
Figure 4: Test accuracy disparity across subgroups by aggregated-feauuee distance, experimented [
except for the node features perturbed by independent noises such that they less homophilious.
with noisy features. The experiment and plot settings are the same as Figure
Relative Ratio of FPR
Relative Ratio Ratio of FPR
Relative Ratto of FPR
degme Jo www.aeooooaaagggoooo.... poperonk
degree d' Siggeeeeeee pooeeink
degree
CO www.eeeeeteeeeeooooooooooo PateERTR
(a) GCN on Cora.
(b) GAT on Cora.
(c) MLP on Cora.
Figure 5: Relative ratio between the FPR under biased training node selection and the FPR under
uniform training node selection. Each bar in each cluster corresponds class (there are 7 classes in total). The red shaded bar indicates the class with high centrality training nodes under the biased setup. Each cluster corresponds to a centrality metric being used for the biased node selection.
features to the training set. To verify this hypothesis, we repeat the experiments in Figure I 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 GNNs on all datasets; while for MLP, the pattern disappears on Cora and Pubmed and becomes less sharp on Citeseer.
5.2 Impact of Biased Training Node Selection
In 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 biased, verifying our discussions in Section 4.3 We will demonstrate that the node centrality scores of the training nodes play important role in the learned GNN model.
We choose "dominant class" and construct 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 MIP, the GNN models have significantly worse FPR for the dominant class when the training nodes biased. This is because, after feature aggregation, there will be 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.
6 Conclusion
We present a novel PAC-Bayesian analysis for the generalization ability of GNNs on node-level semi-supervised learning tasks. As far we know, this the first generalization bound for GNNs for non-IID node-level tasks without strong assumptions advantage of our analysis is that it can be applied to arbitrary subgroups of the test nodes, which allows us to investigate an accuracy-disparti 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 lower classification accuracy. the future, we would like utilize our theory to analyze the fairness of GNNs real-world applications and develop principled methods to mitigate the unfairness.
the data generating mechanism. One
style of fairness for GNNs. Both the theoretical and
10

---

Acknowledgements
This work was in part supported by the National Science Foundation under grant number 1633370. The authors claim no competing interests.
References
[1] Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards unified framework for fair and stable graph representation learning. CoRR, abs/2102.13186, 2021. URL https //arxiv. www.///g//////////////.///..ee//
abs/2102. 2102 13186
[2] Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approx- imations of gibbs posteriors. The Journal of Machine Learning Research, 17(1):837488414 8414,
2016.
[3] Aseem Baranwal, Kimon Fountoulakis. and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. arXiv preprint arXiv:2 2021.
[4] Lue Bégin, Pascal Germain, François Laviolette, and Cean-Francis Roy. Pac-bayesian theory for transductive learning. In Artificial Intelligence and Statistics, pages 105-113. PMLR, 2014.
[5] Avishek Joey Bose and William L. Hamilton. Compositional faimess constraints for graph embeddings. CoRR, abs/1905 10674, 2019. URL http:http:///teee /ttpvv//xvvvvv.////v///a//a..ava http:///axxxvv..o/bbbbaa// wtwp
10674 10674
[6] Maarten Buyl and Tijl De Bie. The kl-divergence between graph model and its fair i-oojeccion as fairness regularizer. CoRR, (asss//13.0884 2021. URL URL httphhtttt///aaeee www.xvv.rrg/ab//uueee
01846
[7] Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, WSDM '21, page 680-688, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450335 14033829777 doi: 10. 10.1145/3437963.
3441752. URL http::ttt:::oorrr//// 10. 1145/3437963 3441752
[8] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. NeurlPS, 2018.
[9] Simon S Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. arXiv preprint 190t::9995.1199 2019.
[10] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbich, Gabriel Arpino, and Daniel Roy. On the role of data in pac-bayes. In International Conference on Artificial Intelligence and Statistics, pages 604-612 PMLR, 2021.
[11] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pages 3419-3430. PMLR, 2020.
[12] Pascal Germain, Alexandre Lacasse, Francois Laviolette, Mario March, and Jean- Francis Roy. Risk bounds for the majority vote: From a pac-bayesian analysis to learning algorithm. Journal of Machine Learning Research, 16(26):787-660, 2015.
[13] Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., volume 2, pages 729-734. IEEE, 2005.
[14] Benjamin Guedj. A primer pac-bayesian learning, arXiv preprint
2019.
[15] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works Wassily Hoeffdding, pages 409-426 Springer, 1994.

---

[16] Yifan Hou, Jian Zhang. James Cheng, Kaili Ma, Richard TB Ma, Hongzhi Chen, and Ming- Chang Yang. Measuring and improving the use of graph information graph neural networks. In International Conference on Learning Representations, 2019.
[17] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 2020.
[18] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning, pages 2323-2332. PMLR, 2018.
[19] Ahmad Khajehnejad, Moein Khajehnejad, Mahmoudreza Babaei, Krishna Gummadi, Adrian Weller, and Baharan Mirzasoleiman. Crosswalk: ing. 2021.
node representation learn-
[20] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint
2016.
[21] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
[22] Charlotte Laclau, levgen Redko, Manvi Choudhary. and Christine Largeron. All of the fairess for edge prediction with optimal transport. CoRR, abs/2010. 16326. 2020. URL https 16326
[23] John Langford and John Shawe-Taylor Pac-bayes & margins. Advances in neural information processing systems, pages 439-446, 2003.
[24] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for superviid learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
[25] Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. In ICLR, 2021.
[26] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. homophily a necessity for graph neural networks? arXiv preprint arXiv:2/06.06/34 2021.
[27] David McAllester. Simplified pac-bayesian margin bounds. In Learning theory and Kernel machines, pages 203-215. Springer, 2003.
[28] Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology. 27(1):1154444 2001.
[29] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings the 5125-5124, 2017.
the IEEE conference on computer vision and pattern recognition, pages
[30] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spertrally-norrmaiieed margin bounds for neural networks. 2018.
[31] Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: M0X5v:9995005550 2019.
[32] Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. In Proceedings of the Eventy-Eightl International Joint Conference on Artificial Intelligence, IJCAI-19, pages 3289-3295. International Joint Conferences on
Artificial Intelligence Organization. 7 2019, doi: 20.24963/jcaa.22119443 URL https
//doi.org// 14963/1jcal 2019/459 456
[33] Omar Rivasplata. Subgaussian random variables: An expository note. Internet publication, PDF, 2012.
12

---

[34] Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078, 2020.
[35]
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):11-80, 2008
[36] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248 259, 2018.
[37] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. magazine, 29(3):33-93, 2008.
[38] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. CoRR, abs/181 1.05868, 2018. URI. http://
arxiv.org/aal hatps/1811.0000 05868
[39] Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. Biased edge dropout for enhancing faimesss in graph representation learning, 2021.
[40] Joel Tropp. An introduction matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230, 2015.
[41] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
[42] Saurabh Verma and Zhi-Li Zhang. Stability and generalization graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1539-1548, 2019.
[43] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song. Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, highiy-performant package for graph neural networks. arXiv preprint 19Xiv:1909001315 2019.
[44] Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world networks. nature, 393(6684):440444 442, 1998.
[45] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference machine learning, pages 6861-6871. PMLR, 2019.
[46] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
[47] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48, PMLR, 2016.
[48] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William I. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 974-983, 2018
[49] Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: a deep learning framework for traffic forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 3634-3640, 2018
[50] Ziqian Zeng, Rashidul Islam, Kamrun Naher Keya, James R. Foulds, Yangqiu Song, and Shimei Pan. Fair representation learning for heterogencous information networks. CoRR. abs/2104.08766 2021. URL /tttp:://axxii....tt/ httg//bs/21000 08769
[51] Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P Adams, and Peter Orbanz. Non- vacuous generalization bounds at the imagenet scale: a pac-bayesian compression approach. In International Conference Learning Representations, 2018.
13

---

[52] Jiong Zhu, Yujun Yan. Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
14


Reviews:
[{"review_id": "llklhzLQGSE", "reviewer": "Reviewer_AWUG", "summary": "This paper proposes a novel PAC-Bayesian analysis for the generalization ability of GNNs on the node-level semi-supervised learning tasks. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies an important problem, the generalization ability of GNNs on node-level semi-supervised learning tasks. The proposed generalization bound is interesting, without relying on very strong assumptions. Experiments on several real-world datasets also demonstrate the effectiveness of the proposed theoretical analysis.\n\nI have the following suggestions:\n\n1. I would suggest the authors provide more details on how the generalization capability is linked to GNN fairness. What's the definition of GNN fairness?\n2. Experiments are conducted on several small-scale data. Can it be easily generalized to large-scale graphs? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "OTEMbX9iDmV", "reviewer": "Reviewer_bVjk", "summary": "This work presents PAC-Bayesian analysis for GNNs under a non-IID\nsemi-supervised learning setup. It first analyzes the generalization performance\nfor general settings, and then applies the results to GNNs. The theoretical\nresults have been backed up with empirical evaluations on several graph\nbenchmarks.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work presents PAC-Bayesian analysis for GNNs under a non-IID\nsemi-supervised learning setup. It first analyzes the generalization performance\nfor general settings, and then applies the results to GNNs. The theoretical\nresults have been backed up with empirical evaluations on several graph\nbenchmarks.\n\nThe theoretical analysis is solid. It provides new theoretical results for\nclassification problems in non-IID semi-supervised settings. The implications\nand findings from the theoretical and empirical results are also interesting,\nwhich suggest that nodes with larger geodesic distance to the training nodes\nsuffer from a lower classification accuracy.\n\nHowever, the main analysis is not specific to graphs and GNNs per se. The\nmajority of the theoretical work is more about PAC-Bayesian analysis for\nsubgroups under non-IID semi-supervised setting. Theorem 1 & 2 provide the\ngeneralization bounds for stochastic and deterministic settings, respectively.\nTheorem 3 applies Theorem 2 to obtain a subgroup generalization bound for GNNs.\nHowever, the required assumption (Assumption 3) can be strong, for which\nreal-world graphs may not satisfy. Also, the generalization bound in Equation 6\ndepends on epsilon_m, how can this term be estimated in practice?\n\nThe fairness component of this work is relative weak compared to the\ngeneralization performance analysis. Most of the theoretical contributions are\nmore devoted to generalization performance under the subgroup assumptions, while\nthe relationships to fairness is marginal. I suggest not emphasizing the\nfairness aspect in the title.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "HIvzbVnWzNa", "reviewer": "Reviewer_8vwm", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In my opinion, this is a very good paper on two folds. First, non-IID samples are seen everywhere in the real-world applications, where IID annotations are hard to obtain. Without too many assumptions, the PAC generalization bound brings $\\epsilon_m$ into the central role of the disparity or distance between groups. Second, the experiment design specifically constructs different subgroups and reproduce the outcome indicated by the theorem. By comparing Figure 2 and Figure 4, the author use the MLP ablation to reveal the graph homophily in an interesting perspective. \n\nOne question:\nIs the aggregated feature same as the final hidden representation (before activation) for GCNs? If not, the final hidden representation might be a unified measure for both graph distance and aggregated feature for subgroup.\n\nI believe the proposed analysis framework can guide the fair(unbiased) training of graph neural networks in the community. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "CvRnjwcboGE", "reviewer": "Reviewer_E1Li", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper considers the subgroup generalization for GNNs, which may potentially influence the performance of different subgroups, thus it may partly contribute to the choice of test set in the experiments of GNNs. However, several main concerns should be addressed by the authors.\n\n1. The paper indeed explores accuracy disparity across subgroups by three subgroup split methods, and through the theoretical analysis and empirical results, the diversity of subgroups may more or less involve some disparity across subgroups. But in my opinion, the investigation of influence on performance by different subgroups is a relatively trivial task, which is an easy thing to think about. In particular, the split of subgroups can be regarded as splitting the nodes by some kind of sensitive attribute. In other words, the proposed distance (such as aggregated-feature distance or geodesic distance) can be viewed as one specific kind of sensitive attribute.\nTherefore, though with some theoretical analysis, I still think the main contribution of this paper is limited. That is, this paper first proposes several findings on subgroup generalization for GNNs, and then provides some theoretical analysis to these findings, yet no effective models/suggestions are proposed by the authors to deal with the underlying bias (or unfairness). This makes the paper tend to be a technical report.\n\n\n2. In lines 109-110 of Sect-3.1, the authors said \"Note that the analysis on any ... on the entire unlabeled set, as the entire set is a subset\". I'm a bit confused here, and why the reason is \"as the entire set is a subset\"?\n\n3. In Sect-5.1, the two-step aggregated features are calculated and they can facilitate the computation of distances between nodes. However, I doubt that the two-step aggregated features cannot truly reflect the involved feature information of each node in the two-layers aggregation, since in each GNN layer, the GNN model would filter the aggregated information (such as by transformation, or even attention mechanism to assign different weights) for each node instead of directly aggregating. This may impair the credibility of the results.\n\nAfter rebuttal: I have read the authors' responses, and suggest the authors make further modifications to the current version to make it more solid.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the Main Review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The review scores are stable towards "clear accept". Some concerns raised by a reviewer are properly addressed during the discussion period, making the paper have a unanimous consensus. Also, it makes an interesting connection with "fairness" concerning accuracy disparity, thereby opening up interesting problems along with this direction in the community. 
Decision: Accept (Spotlight)