Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks
Authors: Shuai Zhang
Meng Wang
Pin-Yu Chen
Sijia Liu
Songtao Lu
Miao Liu
Venue: ICLR 2023 poster (2023)
Keywords: Learning theory
Graph neural networks
Generalization analysis
Graph sparisification

Abstract: Due to the significant computational challenge of training large-scale graph neural networks (GNNs), various sparse learning techniques have been exploited to reduce memory and storage costs. Examples include graph sparsification that samples a subgraph to reduce the amount of data aggregation and model sparsification that prunes the neural network to reduce the number of trainable weights. Despite the empirical successes in reducing the training cost while maintaining the test accuracy, the theoretical generalization analysis of sparse learning for GNNs remains elusive. To the best of our knowledge, this paper provides the first theoretical characterization of joint edge-model sparse learning from the perspective of sample complexity and convergence rate in achieving zero generalization error. It proves analytically that both sampling important nodes and pruning neurons with lowest-magnitude can reduce the sample complexity and improve convergence without compromising the test accuracy. Although the analysis is centered on two-layer GNNs with structural constraints on data, the insights are applicable to more general setups and justified by both synthetic and practical citation datasets.

Published as a conference paper at ICLR 2023
JOINT EDGE-MODEL SPARSE LEARNING IS PROVABLY EFFICIENT FOR GRAPH NEURAL NETWORKS
Shuai Zhang
Meng Wang
Pin- Yu Chen
Rensselaer Polytechnic Institute zhangs292 98 rpii. edu
Rensselaer Polytechnic Institute wangm? rppi edu
IBM Research
Pin Pin-Yu, Chen@ i.mm com
Sijia Liu
Songtao Lu IBM Research s songtao www.aoiiiioo...mmm com
Miao Liu
Michigan State University liusi i @mau. edu
IBM Research
miao. miao.lium lww.llllleee @ibm. com
ABSTRACT
Due to the significant computational challenge training large-scale graph neural networks (GNNs), various sparse learning techniques have been exploited to reduce memory and storage costs. Examples include graph sparsification that samples subgraph to reduce the amount of data aggregation and model sparsification that prunes the neural network to reduce the number of trainable weights. De- spite the empirical successes in reducing the training cost while maintaining the test accuracy, the theoretical generalization analysis of sparse learning for GNNs remains elusive. To the best of our knowledge, this paper provides the first theoreti- cal characterization of joint edge-model sparse learning from the perspective of sample complexity and convergence rate achieving zero generalization error. It proves analytically that both sampling important nodes and pruning neurons with swwest-manittde can reduce the sample complexity and improve convergence without compromising the test accuracy. Although the analysis is centered on two-layer GNNs with structural constraints on data, the insights are applicable to more general setups and justified by both synthetic and practical citation datasets.
INTRODUCTION
Graph neural networks (GNNs) can represent graph structured data effectively and find applications in objective detection (Shi & Rajkumar, 2020; Yan et al., 2018), recommendation system (Ying al., 2018; Zheng et al., 2021), rational learning (Schlichtkrull et al., 2018), and machine translation (Wu et al., 2020; 2016). However, training GNNs directly on large-scale graphs such as scientific citation networks (Hull & King, 1987; Hamilton al., 2017: Xu et al., 2018), social networks (Kipf & Welling, 2017; Sandryhaila & Moura, 2014; Jackson, 2010), and symbolic networks (Riegel et al., 2020) becomes computationally challenging or even infeasible, resulting from both the exponential aggregation of neighboring features and the excessive model complexity, e.g., training two-layer GNN on Reddit data (Tailor et al., 2020) containing 232,965 nodes with an average degree of 492 be twice costly ResNet-50 on ImageNet (Canziani al., 2016) in computation resources.
The approaches accelerate GNN training can be categorized into two paradigms: sparsifying the graph topology (Hamilton et al., 2017; Chen et al., 2018; Perozzi et al., 2014; Zou et al., 2019), and (ii) sparsifying the network model (Chen al., 202 You et al., 2022). Sparsifying the graph topology means selecting subgraph instead of the original graph to reduce the computation of neighborhood aggregation. One could either use fixed subgraph (e.g.. the graph typology (Hübler al., 2008), graph shift operator (Adhikari et al., 2017; Chakeri et al., 2016), or the degree distribution (Leskovec & Faloutsos, 2006; Voudigari et al., 2016; Eden et al., 2018) is preserved) or apply sampling algorithms, such as edge sparsification (Hamilton et al., 2017), or node sparsification (Chen et al., 2018; Zou et al., 2019) to select a different subgraph in each iteration. Sparsifying the network model means reducing the complexity of the neural network model, including removing the non- non-linear activation (Wu et al., 2019; He et al., 2020), quantizing neuron weights (Tailor et al., 2020; Bahri et al., 2021) and output of the intermediate layer (Liu et al., 2021), pruning network (Frankle & Carbin, 2019),

---

Published as a conference paper at ICLR 2023
knowledge distillation (Yang et al., 2020; Hinton et al., 2015; Yao al., 2020; Jaiswal et al., 2021). Both sparsification frameworks can be combined, such as joint edge sampling and network model pruning in (Chen et al., 2021b; You et al., 2022).
Despite many empirical successes in accelerating GNN training without sacrificing test accuracy, the theoretical evaluation of training GNNs with sparsification techniques remains largely unexplored. Most theoretical analyses are centered on the expressive power of sampled graphs (Hamilton et al., 2017; Cong et al., 2021; Chen et al.. 2018; Zou et al., 2019; Rong et al., 2019) pruned networks (Malach al.. 2020; Zhang et al., 2021; da Cunha et al., 2022). However, there limited gen- eralization analysis, i.e., whether the learned model performs well on testing data. Most existing generalization analyses are limited to two-layer cases, even for the simplest form of fera-dorward neural networks (NNs), see, e.g., (Zhang al., 2020a; Oymak & Soltanolkotabi, 2020; Huang et al., 2021; Shi et al., 2022) as examples. To the best of our knowledge, only Li et al. (2022); Allen al. (201 9a) go beyond two layers by considering three-layer GNNs and NNs, respectively. However, Li et al. (2022) requires a strong assumption, which cannot be justified empirically or theoretically, that the sampled graph indeed presents the mapping from data to labels. Moreover, Li et al. (2022); Allen-Zhu et al. (2019a) focus on a linearized model around the initialization, and the learned weights only stay near the initialization (Allen-Zhu & Li, 2022). The linearized model cannot justify the advantages of using multi-layer (G)NNs and network pruning. As far as we know. there is no imite-sample generalization analysis for the joint sparsification, even for two-layer GNNs.
Contributions. This paper provides the first theoretical generalization analysis of joint topology- model sparsification in training GNNs, including (1) explicit bounds of the required number of known labels, referred to as the sample complexity, and the convergence rate of stochastic gradient descent (SGD) to return model that predicts the unknown labels accurately; (2) quantitative proof for that joint topology and model sparsification is a win-win strategy in improving the learning performance from the sample complexity and convergence rate perspectives.
We consider the following problem setup to establish our theoretical analysis: node classification on a one-hidden-layer GNN, assuming that some node features are class-relevant (Shi et al., 2022), which determines the labels, while some node features are class-irrelevant, which contains only irrelevant information for labeling, and the labels of nodes are affected by the class-relevant features of their neighbors. The data model with this structural constraint characterizes the phenomenon that some nodes more influential than other nodes, such in social networks (Chen et al., 2018; Veličković et al., 2018), or the case where the graph contains redundancy information (Zheng et al., 2020).
Specifically, the sample complexity is quadratic in (1 B3/aa, where in (0, 1] is the probability of sampling nodes of class-relevant features, and larger means class-relevant features are sampled more frequently. / in [0. 1) is the fraction of pruned neurons in the network model using the magnitude- based pruning method such as (Frankle Carbin, 2019). The number of SGD iterations to reach desirable model is linear in (1 - 3)/a. Therefore, our results formally prove that graph sampling reduces both the sample complexity and number of iterations more significantly provided that nodes with class-relevant features are sampled more frequently. The intuition is that importance sampling helps the algorithm learns the class-relevant features more efficiently and thus reduces the sample requirement and convergence time. The same learning improvement is also observed when the pruning rate increases as long as 3 does not exceed a threshold close to 1.
2
GRAPH NEURAL NETWORKS: FORMULATION AND ALGORITHM
2.1 PROBLEM FORMULATION
w
b
Σ
Yo
Given an undirected graph G(V, E), where V is the set of nodes, & is the set of edges. Let R denote the maximum node degree. For any node v E V. let D. E 2d and yo E 1+1 denote its input feature and corresponding label', respectively. Given all node features (ær, vey and partially known labels {vr) Juw>eED for nodes in D C V. the semi- unii-supervised node classification problem aims to predict all unknown labels yo for u E V/DD
Ouegut laper
Hegton Unaavniiual
Aggresation
Figure I: Illustration of node classification in the GNN
'The analysis can be extended multi-class classification, see Appendix I.
2

---

Published as a conference paper at ICLR 2023
This paper considers graph neural network with non-linear aggregator functions, as shown in Figure The weights of the K neurons in the hidden layer are denoted as (w) E k== and the weights in the linear layer are denoted as {by E R} Let W E Æa* and b E R be the concatenation of
{wr)E-1 and { respectively. For any node v, let (w) denote the set of its (I-hop) neighbors (with self connectnnnt,,, and X (w) E [dd([((r) contains features in (()).
Therefore, the output of the GNN for node v can be written as:
( b; (N()))
by AGG((X(u)> wk),
where AGG(X N w) denotes a general aggregator using features XN(o) and weight w, e-g.. weighted sum of neighbor nodes (Veličković et al., 201 8), max-pooling (Hamilton et al., 2017), or min-pooling (Corso et al., 2020) with some non-linear activation function. We consider ReLU as <(+) = max 0}. Given the GNN, the label yo at node is predicted by sign(g W, b; Xx(o))).
(x))
We only update W due to the homogeneity of ReLU function, which is common practice to simplify the analysis (Allen-Zhu et al., 2019a; Arora et al., 2019; Oymak & Soltanolkotabi, 2020; Huang et al., 2021). The training problem minimizes the following empirical risk function (ERF):
min W
(W ((0) = D
Σ RED
Vo g ((W, (W,be (WV,,)))()))))
XN()).
(2)
The test error is evaluated by the following generalization emor function:
[g((W b)) = M Σ max {1 - yv M.w.9WWe
(W, b; X Xx)m))o)).
(3)
NEV
If ((g(W, b)) = 0. y. sign b; Xx(o)) for all v, indicating zero test error. Albeit different from practical GNNs, the model considered this paper can be viewed as a one- hidden-layer GNN, which is the state-of-the-ard practice in generalization and convergence analyses with structural data (Brutzkus & Globerson, 2021; Damian et al., 2022: Shi et al., 2022; Allen-Zhu & Li, 2022). Moreover, the optimization problem of (2) is already highly non-convex due to the non-linearity of ReLU functions. For example, as indicated in (Liang et al., 2018; Safran & Shamir, 2018), one-hidden-layer (G)NNs contains intractably many spurious local minima. In addition, the VC dimension of the GNN model and data distribution considered in this paper is proved to be at least an exponential function of the data dimension (see Appendix G for the proof). This model is highly expressive, and it is extremely nontrivial to obtain a polynomial sample complexity, which is one contribution of this paper.
2.2 GNN LEARNING ALGORITHM VIA JOINT EDGE AND MODEL SPARSIFICATION
The GNN learning problem (2) is solved via a mini-batch SGD algorithm, as summarized in Algorithm 1. The coefficients by 's randomly selected from +1 -1 and remain unchanged during training. The weights wa in the hidden layer are initialized from a multi-variate Gaussian (0, 6 *aa with small constant e.g. d 0.1. The training data are divided into disjoint subsets, and one subset is used in each iteration to update W through SGD. Algorithm contains two training stages: pre- pre-training on W (lines 1-4) with few iterations, and re-training on the pruned model M 3 W (lines 5-8), where @ stands for entry-wise multiplication. Here neuron-wise magnitude pruning is used to obtain weight mask M and graph topology sparsífication achieved by node sampling (line 8). During each iteration, only part of the neighbor nodes is fed into the aggregator function in (1) at each iteration, where (t)) denotes the sampled subset of neighbors of node at iteration t.
Edge sparsification samples subset of neighbors, rather than the entire (w), for every node v in computing (1) to reduce the per-iteration computational complexity. This paper follows the GraphSAGE framework (Hamilton et al., 2017), where (r < R) neighbors sampled (all these neighbors are sampled if [N(v)] < r) for each node at each iteration. At iteration t, the gradient is
((t) (W, (()
1 D
Σ yo Vwg(W, ((0); x (.))))) RD
(4)
3

---

Published as a conference paper at ICLR 2023
Algorithm 1 Training GNN via Joint Edge and Model Sparsification
Input:
Node features X, known node labels Jve with D S V. step size Co 106 with constant 6, the
number of sampled edges r, the pruning rate B, the pre-training iterations T || /// Cey the number of iterations T'.
Initialization: W 6tth as w ~ (0, 8 La) and ( Uniform(1 +111 +1] for &s E [K];
Pre-training: update model weights W through maii--batch SGD with edge sampling
1: Divide DD into disjoint subsets (D(t))T"
2: for l' ""=0, 1,2, .2......
,T" "2.""
do
3: Sample 1 (n) for every node in D(C);
4:
W(t++1 With c Vw (0) (Wit", b());
5: end for
Pruning: set fraction of neurons W with lowest magnitude weights to 0, and obtain the corre- sponding binary mask M:
Re-training: rewind the weights the original initialization as M W and update model weights through SGD with edge sampling:
6: Divide D into disjoint subsets (D J2-1
7: for t 2, ,T' do
8: Sample A1 (v) for every node in D(t);
9:
((++1) w eo Vw p()) (M
10: end for
Return: ( and (o)
where D S V the subset of training nodes with labels. The aggregator function used in this paper is the max max-pooling function, i.e.,
A
NS (0) w) max <(( w Z. ));
(5)
nEAd"
which has been widely used in GraphSAGE (Hamilton et al., 2017) and its variants (Guo et al., 2021; Oh et al., 2019; Zhang et al., 2022b; Lo et al., 2022). This paper considers an importance sampling strategy with the idea that some nodes are sampled with higher probability than other nodes, like the sampling strategy in (Chen et al., 2018; Zou et al., 2019; Chen et al., 2021b).
Model sparsification first pre-trains the neural network (often by only few iterations) and then prunes the network by setting some neuron weights to zero. It then re-trains the pruned model with fewer parameters and is less computationally expensive to train. Existing pruning methods include neuron pruning and weight pruning. The former sets all entries of a neuron w/ to zeros simultaneously, while the latter sets entries of Wy to zeros independently.
This paper considers neuron pruning. Similar to (Chen al., 2021b), we first train the original GNN until the algorithm converges. Then, magnitude pruning is applied to neurons via removing 3 (3 E [0, 1)) ratio of neurons with the smallest norm. Let M E (0, 1] j]= be the binary mask matrix with all zeros in column k if neuron & is removed. Then, we rewind the remaining GNN to the original initialization (i.e., M @ (0)) and re-train on the model M @ W.
THEORETICAL ANALYSIS
3.1 TAKEAWAYS OF THE THEORETICAL FINDINGS
Before formally presenting our data model and theoretical results, we first briefly introduce the key takeaways of our results. We consider the general setup that the node features as a union of the noisy realizations of some class-relevant features and class-irrelevant ones, and denotes the upper bound of the additive noise. The label yo of node is determined by class-relevant features in (v). We assume for simplicity that NVv) contains the class-relevant features for exactly one class. Some major parameters are summarized in Table 1. The highlights include:
(TI) Sample complexity and convergence analysis for zero generalization error. We prove that the learned model (with or without any sparsification) can achieve zero generalization error with high probability over the randomness in the initialization and the SGD steps. The sample complexity is linear in a² and K-1, The number of iterations is linear in and K1//2, Thus, the learning
4

---

Published as a conference paper at ICLR 2023
Table 1: Some Important Notations
Number of neurons in the hidden layer:
o Upper bound of additive noise in input features;
Number of sampled edges for each node;
R The maximum degree of original graph G:
the number of class-relevant and class-irrolevant pattern;;
the probability of containing class rells-te nodes in the sampled neighbors of one node;
Pruning rate of model weights; 3 E [0, 1/L); 8 0 means pruning;
performance is enhanced in terms of smaller sample complexity and faster convergence if the neural network is slightly werrparameeterzze.
(T2) Edge sparsification and importance sampling improve the learning performance. The sample complexity is a quadratic function of r, indicating that edge sparsification reduces the sample complexity. The intuition is that edge sparsification reduces the level of aggregation of class-relevant with class-irrelevant features. making it easier to learn class-relevant patterns for the considered data model, which improves the learning performance. The sample complexity and the number of iterations are quadratic and linear in a respectively. As a larger means the class-relevan features are sampled with a higher probability. this result is consistent with the intuition that a successful importance sampling strategy helps to learn the class-relevant features faster with fewer samples.
(T3) Magnitude-based model pruning improves the learning performance. Both the sample complexity and the computational time are linear in (1 ? indicating that if more neurons with small magnitude are pruned, the sample complexity and the computational time are reduced. The intuition is that neurons that accurately learn class-relevant features tend to have a larger magnitude than other neurons', and removing other neurons makes learning more efficient.
(T4) Edge and model sparsification is a win-win strategy in GNN learning. Our theorem provides a theoretical validation for the success of joint edge-model sparsification. The sample complexity and the number of iterations are quadratic and linear in I-8 respectively, indicating that both techniques can be applied together to effectively enhance learning performance.
3.2 FORMAL THEORETICAL RESULTS
Data model. Let P {pi)_ (AL S d) denote an arbitrary set of orthogonal vectors2 in Rd. Let P+ := Pi and p- := P2 be the positive-class and negative-class pattern, respectively, which bear the causal relation with the labels. The remaining vectors in P are class irrelevant patterns. The node features I. of every node v is a noisy version of one of these patterns, i.e., D. = Pe + Ze, where E P. and zy is an arbitrary noise at node with ||>||2 S for some d.
Yo is 11 (or -1) if node u or any of its neighbors contains p+ (or p-). Specifically, divide V into four disjoint sets V4, V_, VN+ and VN - based on whether the node feature is relevant or not (N in the subscript) and the label, i.c., Pv = p+. Ye E V4: P. = p-, Ve E V~; and p. E {Ps..... PL}, Vo e VN+ U VN- Then, we have yo 1, Vo E V+ U UV and yo - 1, Vo VNUVN
We assume
V4 1
V NN+
1 N
V_ 4
(A1) Every v in VN+ (or Vx- connected to at least one node in V4, (or V-). There is no edge between V4, and VN_ There is no edge between V_ and VN+.
(A2) The positive and negative labels in D are balanced, i..., [DD()) (Dn(2- |I| = (VV)D))
Figure 2: Toy example of the data model. Node 1 and 2 have label +1. Nodes and 4 are labeled as -1. Nodes and 4 have class- relevant features. Nodes 2 and have class- irrelevant features. V-= = {1), VN+ (2), VN- = (3), Vー [1]
(A1) indicates that connected nodes in the graph tend to have the same labels and eliminates the case that node v is connected to both p+ and p- to simplify the analysis. numerical justification of such an assumption Cora dataset can be found in Appendix F.2. (A2) can be relaxed to the case that the observed labels are unbalanced. One only needs to up-weight the minority class in the ERF in (2) accordingly, which is a common trick in imbalance GNN learning (Chen et al., 2021a). and our analysis holds with minor
Thhe orthogonality constraint simplifies the analysis and has heen employed in (Brutzkus & Globerson, 2021). We relaxed this constraint in the experiments on the synthetic data in Section 4.
5

---

Published as a conference paper at ICLR 2023
modification. The data model of orthogonal patterns is introduced in (Brutzkus & Globerson, 2021) to analyze the advantage of CNNs over fully connected neural networks. It simplifies the analysis by eliminating the interaction of class-relevan and class-irrelevan patterns. Here generalize to the case that the node features contain additional noise and are no longer orthogonal.
To analyze the impact of importance sampling quantitatively, let a denote a lower bound of the probability that the sampled neighbors of e contain at least one node in V+ or V- for any node v (see Table 1). Clearly, a r R is a lower bound for uniform sampling" A larger ar indicates that the sampling strategy indeed selects nodes with class-relevant features more frequently.
Theorem 1 concludes the sample complexity (C1) and convergence rate (C2) of Algorithm 1 in learning graph graph- structured data via graph sparsification. Specifically, the returned model achieves zero generalization error (from (8)) with enough samples (C1) after enough number of iterations (C2).
Theorem 1. Let the step size On be some positive constant and the pruning rate 3 E [0, L/ Given the bounded noise such that < L/L and sufficient large model such that K > L2 log q for some constant > 0. Then, with probability at least 1 - q 10 when
(C1) the number of labeled nodes satisfies
D = ((1 + L² + +K (-'))-aa" a 2.
LL2 -lgg))
(6)
(C2) the number of iterations in the re-training stage satisfies
T T= (1, (1+ (1+ Lo + K K-1/2) (1 -1- L),
the model returned by Algorithm I achieves zero generalization error, i.e.,
(T =0
(8)
3.3 TECHNICAL CONTRIBUTIONS
Although our data model is inspired by the feature learning framework of analyzing CNNs (Brutzkus & Globerson, 2021), the technical framework in analyzing the learning dynamics differs from existing ones in the following aspects.
First, our work provides the first polynomial-order sample complexity bound in (6) that quantitatively characterizes the parameters' dependence with zero generalization error. In (Brutzkus & Globerson, 2021), the generalization bound is obtained by updating the weights in the second layer (linear layer) while the weights in the non-linear layer are fixed. However, the high expressivity of neural networks mainly comes from the weights in non-linear layers. Updating weights in the hidden layer can achieve smaller generalization error than updating the output layer. Therefore, this paper obtains a polynomial-order sample complexity bound by characterizing the weights update in the non- non-linear layer (hidden layer), which cannot be derived from (Brutzkus & Globerson, 2021). In addition, updating weights in the hidden layer is a non-convex problem, which more challenging than the case of updating weights in the output layer as convex problem.
Second, the theoretical framework in this paper can characterize the magnitude-based pruning method while the approach in (Brutzkus & Globerson, 2021) cannot. Specifically, our analysis provides a tighter bound such that the lower bound of "lucky neurons" can be much larger than the upper bound of "unlucky neurons" (see Lemmas 2-5), which is the theoretical foundation in characterizing the benefits of model pruning but not available (Brutzkus & Globerson, 2021) (see Lemmas 5.3 & 5.5). On the one hand, (Brutzkus & Globerson, 2021) only provides a uniform bound for "unlucky neurons" in all directions, but Lemma in this paper provides specific bounds in different directions. On the other hand, this paper considers the influence of the sample amount, and we need to characterize the gradient offsets between positive and negative classes. The problem is challenging due to the existence of class inreevitellvantt patterns and edge sampling in breaking the dependence between the labels and pattern distributions, which leads to unexpected distribution shifts. We characterize groups of special data as the reference such that they maintain fixed dependence on labels and have controllable distribution shift to the sampled data.
Third, the theoretical framework in this paper can characterize the edge sampling while the approach in (Brutzkus & Globerson, 2021) cannot. (Brutzkus & Globerson, 2021) requires the data samples
'hhe lower bounds of for some sampling strategy are provided in Appendix G.I.

---

Published as a conference paper at ICLR 2023
containing class-relevant patterss in training samples via margin generalization bound (Shalev- Shwartz Ben-David, 2014; Bartlett & Mendelson, 2002). However, with data sampling, the sampled data may no longer contain class-relevant patterns. Therefore, updating the second layer not robust, but our theoretical results show that updating in the hidden layer is robust to outliers caused by egde sampling.
3.4 THE PROOF SKETCH
Before presenting the formal roadmap of the proof, we provide a high-level illustration by borrowing the concept of "lucky neuron", where such node has good initial weights, from (Brutzkus & Globerson, 2021). We emphasize that only the concept borrowed, and all the properties of the "lucky neuron", c.g., (10) to (13), are developed independently with excluded theoretical findings from other papers. In this paper, we justify that the magnitude of the "lucky neurons" grows at a rate of sampling ratio of class-relevant features, while the magnitude of the "unlucky neurons" is upper bounded by the inverse of the size of training data (see proposition 2). With large enough training data, the "lucky neurons" have large magnitudes and dominate the output value. By pruning neurons with small magnitudes, we can reserve the "lucky neurons" and potentially remove "unlucky neurons" (see proposition 3). In addition, we prove that the primary direction of "lucky neurons" is consistence with the class-relevant patterns, and the ratio of "lucky neurons" is sufficiently large (see proposition 1). Therefore, the output is determined by the primary direction of the "lucky neuron", which the corresponding class-relevant pattern Specifically, we will prove that, for every node with ye- 1, the prediction by the learned weights WT is accurate, i.e., g g(M O W(T), b(o); X XN())) > 1. The arguments for nodes with negative labels are the same. Then, the zero test error achieved from the defined generalization error in (3).
1}. We first show that there exist some neurons in B+ with weights (t)) that are close to p+ for all iterations t 2 0. These neurons, referred to "lucky neurons," play dominating role in classifying v, and the fraction of these neurons is at least close to 1/L. Formally,
Divide the neurons into two subsets B+ = [k b = +1} and B_ = (k b/
Proposition 1. Let K++ S B4 denote the set of "lucky neurons" that for any in K.+,
min (w) 1>
P+ +2)
max PEP/p+.ll S/P//P.1==1225
(D)") .p+z) for all t.
Then holds that
(1- K-1/2 Lo)/L.
(10)
We next show in Proposition 2 that when |D| is large enough, the projection of the weight w of lucky neuron on P+ grows rate of a, Then importance sampling with large a corresponds to high rate. In contrast, the neurons in B_ increase much slower in all directions except for p...
Proposition 2. (w))) p+ ) 2 (a (a- (a-oo/(11))/D)) ViE Vt 1( (w p) S
(11)
Vj E B vp E V/p_.Vt
Proposition shows that the weights magnitude of "lucky neuron" in K2, is larger than that of neuron in B Combined with (10), "lucky neurons" will not be pruned by magnitude pruning, as long as 3 < 1 1/L. Let K.g denote the set of neurons after pruning with [Kgl = (1 3)K. Proposition There exists a small positive integer such that
||w ||2 Moreover, KC nC+ K4 for all 3 < 1-1LLL
|| (9) 1|,, Vi Vj E /
(12)
Therefore, with sufficiently large number of samples, the magnitudes of lucky neurons increase much faster than those of other neurons (from proposition 2). Given sufficiently large fraction of lucky neurons (from proposition 1), the outputs of the learned model will be strictly positive. Moreover, with a proper pruning rate, the fraction of lucky neurons can be further improved (from proposition 3), which leads to reduced sample complexity and faster convergence rate.
In the end, we consider the case of feature noise illustrate the main computation
7

---

Published as a conference paper at ICLR 2023
o(M @ W M o : XN(c))
K (EIEB,, (V) @1( (((1)))) (T) ax,)) LREB_nK, (ax o(l wn)") m. ()))))
2 k E max o({ !
(T), Lu {=))- -
E max 1( 1( P)l
(13)
1EK+ dEN(t)
jEB_rKg DEP/D
2 [/]C+I/KK - (1- 3)(1+ +))+ G,2 > 1,
where the first inequality follows from the fact that K.3 n K4 K+,, & is the nonnegative ReLU function, and (vx) does not contain p- for a node e with Ye = +1. The second inequality follows from Proposition 2. The last inequality follows from (10), and conclusions (C1) & (C2). That
completes the proof. Please see the supplementary material for details.
4 NUMERICAL EXPERIMENTS
4.1 SYNTHETIC DATA EXPERIMENTS
We generate graph with 10000 nodes, and the node degree is 30. The one-hot vectors and e2 are selected as p+ and p respectively. The class-irrelevant patterns are randomly selected from the null space of p+ and p-. That is relaxed from the orthogonality constraint in the data model. ||pl|2 is normalized to for patterns. The noise 2, belongs Gaussian (00, o²). The node features and labels satisfy (A1) and (A2), and details of the construction can be found in Appendix F. The test error is the percentage of incorrect predictions of unknown labels. The learning process is considered success if the returned model achieves zero test error.
Sample Complexity. We first verify our sample complexity bound (6). Every result is averaged over 100 independent trials. A white block indicates that all the trials are successful, while a black block means all failures. In these experiments, we vary one parameter and fix all others. In Figure 3, = 15 and we vary the importance sampling probability a. The sample complexity is linear in 2 Figure indicates that the sample complexity almost linear in (1 - 3)² up a certain upper bound, where 3 is the pruning rate. All these are consistent with our theoretical predictions in (6).
165
Number of ileratioon
250
135
80
0.05
190
A
105
130
75
60
45
15
4
3.1
2.2
1.0 0.8 0.6 0.4 0.2
40
(1 A3²
Figure 3: [D] against the impor-
Figure 4: |D] against the pruning
Figure 5: The number of iterations against
tance sampling probability
rate 3
Training Convergence Rate. Next, we evaluate how sampling and pruning reduce the required number of iterations to reach zero generalization error. Figure 5 shows the required number of iterations for different a under different noise level a. Each point averaged over 1000 independent realizations, and the regions in low transparency denote the error bars with one standard derivation. We can see that the number of iterations is linear in 1/a, which verifies our theoretical findings in (6). Thus, importance sampling reduces the number of iterations for convergence. Figure 6 illustrates the required number of iterations for convergence with various pruning rates. The baseline is the average iterations of training the dense networks. The required number of iterations by magnitude pruning is almost linear in B, which verifies our theoretical findings in (7). In comparison, random pruning degrades the performance by requiring more iterations than the baseline to converge.
Magnitude pruning removes neurons with irrelevant information. Figure 7 shows the distribution of neuron weights after the algorithm converges. There are 10s points by collecting the neurons in 100 independent trials. The y-axis is the norm of the neuron weights Wx, and the y-axis stands for the angle of the neuron weights between P+ (bottom) p- (top). The blue points in cross represent wy's 's with by = 1, and the red ones in circle represent wA 's with by = -1. In both cases, we with a small norm indeed has large angle with p+ (or p-) and thus, contains class-irrelevan information for classifying class +1 (or -1). Figure 7 verifies Proposition 3 showing that magnitude pruning removes neurons with class-irrelavant information.
8

---

Published as a conference paper at ICLR 2023
Performance enhancement with joint edge-model sparsification. Figure illustrates the learning success rate when the importance sampling probability a and the pruning ratio 3 change. For each pair of and B. the result is averaged over 100 independent trials. We can observe when either or ( increases, it becomes more likely to learn a desirable model.
150
Angle betwers seuron welgltee p
Number of temrttons
0.97
Magaitude of neussa wrisht
100
Majaiaaa puanin
100
O Prneeet grann
0.87
50
50-
0.77
x/2
Angle wrights and
0:45
Figure 6: Number of iterations
Figure 7: Distribution of the neu-
Figure 8: Learning success rate of join edge-model sparsification
against the pruning rate |
ron weights
4.2 JOINT-SPARSIFICATION ON REAL CITATION DATASETS
We evaluate the joint edge-model sparsification algorithms in real citation datasets (Cora, Citeseer, and Pubmed) (Sen et al., 2008) on the standard GCN (a two-message passing GNN) (Kipf & Welling, 2017). The Unified GNN Sparsification ( (UGS) in (Chen et al., 2021b) is implemented here as the edge sampling method, and the model pruning approach is magnitude-basee pruning.
Figure 9 shows the performance of node classification on Cora dataset. As we can see, the joint sparsification helps reduce the sample complexity required to meet the same test error of the original model. For example, P2. with the joint rates of sampled edges and pruned neurons as (0.90,0.49), and P3. with the joint rates of sampled edges and pruned neurons as (0.81 1,,600,,, return models that have better testing performance than the original model (P1) trained on a larger data set. By varying the training sample size, we find the characteristic behavior of our proposed theory: the sample complexity reduces with the joint sparsification.
Figure 10 shows the test errors on the Citeseer dataset under different sparsification rates, and darker colors denote lower errors. In both figures, we observe that the joint edge sampling and pruning can reduce the test еттоr even when more than 90% of neurons are pruned and 25% of edges are removed, which justifies the efficiency of joint siggemmdell sparsification. In addition, joint model- edge sparsification with smaller number of training samples can achieve similar or even better performance than that without sparsification. For instance, when we have 120 training samples, the test error is 30.4% without any specification. However, the joint sparsification error to 28.7% with only 96 training samples. We only include partial results due to the space limit. synthetic and real datasets.
improve the test
Please see the supplementary materials for more experiments
Nada clastiication on Cura
Tule jeused peuroes (log soabl))
Cileseer (ID = 120)
Cileseer (DI=96)
0,50
a E38
0.93
63M
6:30
033
6038 po0) 0063
0.22
0,60
1:5
12
63M
0:33
0230
0287
Toxt omee
0.21
1.28
0.84
0301
12.44
8:38
0.74
6:32
02.2)
0.22
0.19
(1.00, (.006 19:85, 0/991
72, 6.75) 10.8, (.87)
Rate sampled Rate pruned
Rate of sampled edges
Rate somgled edges
Figure 10: Heatmaps depicting the test error on Citeseer with 96 and 120 training nodes.
Figure 9: Test error on Cora.
5 CONCLUSIONS
Encouraged by the empirical success of sparse learners in accelerating GNN training, this paper characterizes the impact of graph sampling and neuron pruning on the sample complexity and convergence rate for a desirable test accuracy quantitatively. To the best of our knowledge, this is the first theoretical generalization analysis of joint mdgel sparsification in training GNNs. Future directions include generalizing the analysis to multi-layer cases, other graph sampling strategies, e.g.. FastGCN (Chen et al., 2018 8), link-based classification problems.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This work was supported by AFOSR FA9550-20-1-0122, ARO W911NF-21-110255, NSF 1932196 and the Rensselaer-IBM AI Research Collaboration (http:/airc..ri.eduu part of the IBM AI Horizons Network (http://ibm. http://ibm..i//AHHorriii biz/AlHorizons). We thank Kevin Li and Sissi Jian at Rensselaer Polytechnic Institute for the help in formulating numerical experiments. We thank all anonymous reviewers for their constructive comments.
REPRODUCIBILITY STATEMENT
For the theoretical results in Section 3.2, we provide the necessary lemmas in Appendix D and a complete proof of the major theorems based on the lemmas in Appendix E. The proof of all the lemmas are included in Appendix H. For experiments in Section 4, the implementation details in generating the data and figures are summarized the Appendix F, and the source code can be found in the supplementary material.
REFERENCES
Bijaya Adhikari, Yao Zhang, Sorour E Amiri, Aditya Bharadwaj. and B Aditya Prakash. Propagation- based temporal network summarization. IEEE Transactions on Knowledge and Data Engineering, 30(4):729-742, 2017.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 977-988. IEEE, 2022.
Zeyuan Allen-Zhiee -hu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems, pp. 6158-6169, 2019a.
Zeyuan Aluen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 242 252.. PMLR, 2019b.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-graing analysis of optimization and generalization for overparameterized two-layer neural networks. International Conference Machine Learning, pp. 322-332. PMLR, 2019.
Mehdi Bahri, Gaétan Bahl, and Stefanos Zafeiriou. Binary graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9492-9501 2021.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
Alon Brutzkus and Amir Globerson. An optimization and generalization analysis for max- max- pooolig networks. In Uncertainty in Artificial Intelligence, pp. 1650-1660. PMLR, 2021.
Alfredo Canziani, Adam Paszke, and Eugenio Culurciello. An analysis of deep neural network models for practical applications. arXiv preprint arXiv:1605.07678 2016.
Alireza Chakeri, Hamidreza Farhidzadeh, and Lawrence O Hall. Spectral sparsification in spectral clustering. 2016 23rd International Conference on Pattern Recognition (ICPR), pp. 2301-2306. IEEE, 2016.
Deli Chen, Yankai Lin, Guangxiang Zhao, Xuancheng Ren, Peng Li, Jie Zhou, and Xu Sun. Topology- imbalance learning for supe-supe node classification. Advances in Neural Information Processing Systems. 34:29885 298297, 202la..
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
10

---

Published as a conference paper at ICLR 2023
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning, pp. 1695-1706. PMLR, 2021b.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in train- ing graph convolutional networks. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: //openreview net wwt/ -
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260- 13271, 2020.
Arthur da Cunha, Emanuele Natale, and Laurent Viennot. Proving the strong lottery ticket hypothesis for convolutional neural networks. In International Conference on Learning Representations, 2022.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference Learning Theory, pp. 5413-5452, PMLR, 2022.
Amit Daniely and Eran Malach. Learning parities with neural networks. Advances in Neural Information Processing Systems, 33:20356-20365 2020.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2018.
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems, pp. 5724-5734, 2019.
Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C Seshadhri. Provable and practical approxima- tions for the degree distribution using sublinear graph samples. In Proceedings of the 2018 World Wide Web Conference, pp. 449-458, 2018.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019. https:
//oopnneevew.net.... htw.://wwwne///oomommiid/rdre
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pp. 3419-3430. PMLR, 2020.
Fangtai Guo, Zaixing He, Shuyou Zhang, Xinyue Zhao, Jinhui Fang, and Jianrong Tan. Normalized edge convolutional networks for skeleton-based hand gesture recognition. Pattern Recognition, 118:108044, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034 2017.
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 639-648 2020.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. stat, 1050:9, 2015.
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. Advances in neural information processing systems, 33:22118 12-223,,, 2020.

---

Published as a conference paper at ICLR 2023
Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. Fl-ntk: A neural tangent kernel-based framework for federated learning analysis. In International Conference on Machine Learning, pp. 4423 4434. PMLR, 2021.
Christian Hübler, Hans-Peter Kriegel, Karsten Borgwardt, and Zoubin Ghahramani. Metropolis algorithms for representative subgraph sampling. In 2008 Eighth IEEE International Conference on Data Mining. pp. 283-292 292. IEEE, 2008.
Richard Hull and Roger King. Semantic database modeling: Survey, applications, and research issues. ACM Computing Surveys, 19(3):001-200 1987.
Matthew O Jackson. Social and economic networks. Princeton university press, 2010.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018.
Ajay Kumar Jaiswal, Haoyu Ma, Tianlong Chen, Ying Ding, and Zhangyang Wang. Spending your winning lottery better after drawing it. arXiv preprint arXiv:2101 03255, 2021.
Svante Janson. Large deviations for sums of partly dependent random variables. Random Structures & Algorithms, 24(3):234 248, 2004.
Stefani Karp, Ezra Winston, Yuanzhi Li, and Aarti Singh. Local signal adaptivity: Provable feature learning in neural networks beyond kernels. Advances in Neural Information Processing Systems, 21124883-248977 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. In International Conference on Learning Representations, 2018
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 631-636, 2006.
Hongkang Li, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Generalization guarantee of training graph convolutional networks with graph topology sampling. In International Conference on Machine Learning, pp. 13014-13051. PMLR, 2022.
Hongkang Li, Meng Wang, Sijia Liu, and Pin-Yu Chen. A theoretical understanding of vision trans- formers: Learning, generalization, and sample complexity. In International Conference on Learn- ing Representations, 2023. URL https: http///eeeeeeeeeeeeeeeeeeeeeeeee n forum " (i jbb.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent structured data. In Advances in Neural Information Processing Systems, pp. 3157-8166. 2018.
Shiyu Liang, Ruoyu Sun, Yixuan Li, and Rayadurgam Srikant. Understanding the loss surface of neural networks for binary classification. In International Conference on Machine Learning, pp- 2835-2845 PMLR, 2018.
Zirui Liu. Kaixiong Zhou, Fan Yang, Li Li, Rui Chen, and Xia Hu. Exact: Scalable graph neural networks training via extreme activation compression. In International Conference on Learning Representations, 2021.
Wai Weng Lo, Siamak Layeghy, Mohanad Sarhan, Marcus Gallagher, and Marius Portmann. E- graphsage: graph neural network based intrusion detection system for iot. In NOMS 2022-2022 IEEE/IFIP Network Operations and Management Symposium, pp. 1-9, IEEE, 2022.
Eran Malach, Gilad Yehudai, Shai Shalev-Schwarte and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. International Conference on Machine Learning, pp. 6682-6691. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2023
Jihun Oh, Kyunghyun Cho, and Joan Bruna. Advancing graphsage with a data-driven node sampling. arXiv preprint 1rX4v:1904. 1ww.e1444..2235. 1295,, 2019.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterization:: Global con-
vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84-105, 2020.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. arXiv preprint 1XXi::802.004007 2018.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 701-710, 2014.
Ryan Riegel, Alexander Gray, Francois I Luus, Naweed Khan, Ndivhuwo Makondo, Ismail Yunus Akhalwaya, Haifeng Qian, Ronald Fagin, Francisco Barahona, Udit Sharma, al. Logical neural networks. arXiv preprint arXiv:2006. 13155, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification, In International Conference on Learning Representations. 2019.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks In International Conference on Machine Learning, pp. 4430-4438, 2018.
Aliaksei Sandryhaila and Jose MF Moura. Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure. IEEE Signal Processing Magazine, 3 (155:800-9, 2014.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervonenkk dimension of graph and recursive neural networks. Neural Networks, 108:248-259, 2018.
Michael Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In Proceedings of European Semantic Web Conference, pp. 593-607. Springer, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-RR Rad. Collective classification in network data. Al magazine, 29(3):93-95 2008.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Weijing Shi and Raj Rajkumar. Point-gnn: Graph neural network for 3d object detection in a point cloud. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1711-1719, 2020.
Zhenmei Shi, Junyi Wei, and Yingyu Liang. A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features. In International Conference on Learning Representations, 2022.
Shyam Anil Tailor, Javier Femandez-Marquee and Nicholas Donald Lane. Degree-quant: Quantization-aware training for graph neural networks. In International Conference on Learning Representations, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2018.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Elli Voudigari, Nikos Salamanos, Theodore Pupageorgiou, and Emmanuel J Yannakoudakis. Rank degree: An efficient algorithm for graph sampling. In 2016 IEEE/ACM International Conference Advances in Social Networks Analysis and Mining, pp. 120-129. IEFF, 2016.
13

---

Published as a conference paper at ICLR 2023
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1): 396-413, 2020.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. In International Conference on Machine Learning, pp. 11112-11122. PMLR, 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International Conference on Machine Learning, Pp- 6861-6871, 2019.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's 's neural machine translation sys- tem: Bridging the gap between human and machine translation. arXiv preprint arXiv: 1609.08144. 2016.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462. PMLR, 2018.
Keyulu Xu, Mozhi Zhang, Stefanie Jegelka, and Kenji Kawaguchi. Optimization of graph neural networks: Implicit acceleration by skip connections and more depth. In International Conference on Machine Learning. pp. 11592-128 1602. PMLR, 2021.
Sijie Yan, Yuanjun Xiong, and Dahua Lin. Spatial temporal graph convolutional networks for skeleton-based action recognition. Proceedings of Association for the Advancement of Artificial Intelligence, 2018.
Yiding Yang. Jiayan Qiu, Mingli Song. Dacheng Tao, and Xinchao Wang. Distilling knowledge from graph convolutional networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7074-7083, 2020.
Huaxiu Yao, Chuxu Zhang, Ying Wei, Meng Jiang, Suhang Wang, Junzhou Huang, Nitesh Chawla, and Zhenhui Li. Graph few-shot learning via knowledge transfer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp- 6656-6663, 2020.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974-983, 2018
Haoran You, Zhihan Lu, Zijian Zhou, Yonggan Fu, and Yingyan Lin. Early-bird gens: Graph-network co-optimization towards more efficient gen training and inference via drawing early- bird lottery tickets. AAAI Conference on Artificial Intelligence, 2022.
Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Fast learning of graph neural networks with guaranteed generalizability.one heweee-hhddd-d-ddeeeee case. In International Conference Machine Learning, 2020a.
Shuai Zhang, Meng Wang. Jinjun Xiong, Sijia Liu, and Pin- Yu Chen. Improved linear convergence of training cnns with generalizability guarantees: A one-hidden layer case. IEEE Transactions Neural Networks and Learning Systems, 32(6):2622 26335, 2020b.
Shuai Zhang, Meng Wang. Sijia Liu, Pin-Yu Yu Chen, and Jinjun Xiong. How unlabeled data improve generalization in self-training? one-hidden-llaer theoretical analysis. In International Conference on Learning Representations, 2022a.
Tao Zhang, Hao-Ran Shan, and Max A Little. Causal graphsage: A robust graph method for classification based on causal sampling. Pattern Recognition, 128: 108696, 2022b.
14

---

Published as a conference paper at ICLR 2023
Zeru Zhang, Jiayin Jin, Zijie Zhang, Yang Zhou, Xin Zhao, Jiaxiang Ren, Ji Liu, Lingfei Wu, Ruoming Jin, and Dejing Dou. Validating the lottery ticket hypothesis with inertial manifold theory. Advances in Neural Information Processing Systems, 34, 2021.
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning, pp. 14558-1468.. PMLR, 2020.
Liyuan Zheng, Zhen Zuo, Wenbo Wang, Chaosheng Dong, Michinari Momma, and Yi Sun. Het- erogeneous graph neural networks with neighbor-sim attention mechanism for substitute product recommendation. AAAI Conference on Artificial Intelligence, 2021.
Kai Zhong, Zhao Song. Prateek Jain, Peter L Bartlett, and Inderjit Dhillon. Recovery guarantees for one-hidden-layer neural networks. In International Conference Machine Learning, pp- 4140-4149, 2017.
Xianchen Zhou and Hongxia Wang. The generalization error of graph convolutional networks may enlarge with more layers. Neurocomputing. 424:97-106, 2021.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. Proceedings of Advances in Neural Information Processing Systems, 32, 2019.
15

---

Published as a conference paper at ICLR 2023
Supplementary Materials for:
Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks
In the following contexts, the related works are included in Appendix A. Appendix B provides high-level idea for the proof techniques. Appendix summarizes the notations for the proofs, and the useful lemmas included in Appendix D. Appendix E provides the detailed proof of Theorem 2, which is the formal version of Theorem 1. Appendix F describes the details of synthetic data experiments in Section 4, and several other experimental results are included because of the limited space in the main contexts. The lower bound of the VC-dimension is proved in Appendix G. Appendix G.I provides the bound of a for some edge sampling strategies. Additional proofs for the useful lemmas are summarized in Appendix H. In addition, we provide a high-level idea in extending the framework this paper to a multi-class classification problem in Appendix
A RELATED WORKS
Generalization analysis of GNNs. Two recent papers (Du et al., 2019; Xu et al., 2021) exploit the neural tangent kernel (NTK) framework (Malach al., 2020; Allen-Zhu al., 2019b; Jacot et al., 2018; Du et al., 2018; Lee et al., 2018) for the generalization analysis of GNNs. It is shown in (Du et al., 2019) that the graph neural tangent kernel (GNTK) achieves a bounded generalization error only if the labels are generated from some special function, e.g., the function needs to be linear or even. (Xu et al., 2021) analyzes the generalization of deep linear GNNs with skip connections. The NTK approach considers the regime that the model is sufficiently over- wer--paramterrized i.e., the number of neurons is a polynomial function of the sample amount, such that the landscape of the risk function becomes almost convex near any initialization. The required model complexity is much more significant than the practical case, and the results are irrelevant of the data distribution. As the neural network learning process strongly correlated with the input structure (Shi al., 2022), distribution-free analysis, such as NTK, might not accurately explain the learning performance on data with special structures. Following the model recovery frameworks (Zhong et al., 2017: Zhang et al., 2022a; 2020b), Zhang et al. (2020a) analyzes the generalization of one- mee-hidden-laye layer GNNs assuming the features belong to Gaussian distribution, but the analysis requires special tensor initialization method and does not explain the practical success of SGD with random initialization. Besides these, the generalization gap between the training and test errors is characterized through the classical Rademacher complexity in (Scarselli al., 2018; Garg et al., 2020) and uniform stability framework in (Verma & Zhang, 2019; Zhou & Wang, 2021).
Generalization analysis with structural constraints on data. Assuming the data come from mixtures of well-separated distributions, (Li & Liang, 2018) analyzes the generalization of one- hidden-layer fully-comnected neural networks. Recent works (Shi et al., 2022; Brutzkus & Globerson, 2021; Allen-ZIi -Zu & Li, 2022; Karp al., 2021; Wen & Li, 2021; Li al., 2023) analyze one- me-hidden- layer neural networks assuming the data can be divided into discriminative and background patterns. Neural networks with non-linear activation functions memorize the discriminative features and have guaranteed generalization in the unseen data with same structural constraints, while no linear classifier with random initialization can learn the data mapping in polynomial sizes and time (Shi et al., 2022; Daniely & Malach, 2020). Nevertheless, none of them has considered GNNs sparsification.
B OVERVIEW OF THE TECHNIQUES
Before presenting the proof details, we will provide a high-level overview of the proof techniques in this section. To warm up. first summarize the proof sketch without edge and model sparsification
16

---

Published as a conference paper at ICLR 2023
methods. Then, illustrate the major challenges in deriving the results for edge and model sparsification approaches.
B.1 GRAPH NEURAL NETWORK LEARNING ON DATA WITH STRUCTURAL CONSTRAINTS
For the convenience of presentation, and negative labels in D, respectively, where D+ = (V+ VN+) n 'D and D = (V- VN n DD Recall that p+ only exists in the neighbors of node u D+, and p- only exists in the neighbors of node e E D_. In contrast, class irrelevant patterns are distributed identically for data in D+ and D_.. In addition, for some neuron, the gradient direction will always be near p+ for E D+, while the gradient derived from e E D_ is always almost orthogonal to p+. Such neuron is the lucky neuron defined in Proposition in Section 3.4, and we will formally define the lucky neuron in Appendix C from another point of view.
D+ and D_ denote the of nodes with positive
Take the neurons in B+ for instance, where B+ {k by +1} denotes the set of neurons with positive coefficients in the linear layer. For a lucky neuron A E K+, the projection of the weights on p+ strictly increases (see Lemma 2 in Appendix D). For other neurons, which are named unlucky neurons, class irrelevant patterns are identically distributed and independent of yos the gradient generated from D4 and D_ are similar. Specifically, because of the offsets between D4, and D_, the overall gradient is in the order of /(1 /+)/ where R the degree of graph. With a sufficiently large amount of training samples, the projection of the weights on class irrelevant patterns grows much slower than that on class relevant patterns. One can refer to Figure 11 for an illustration of neuron weights update.
p PN
Gradient from D+
1 + R² |D]
C+
w(0)
p E PN
1 R² [D]
(()
C + o
2(2) 2)
w(4)
Gradient from D_
w(3)
(1)
p+ or p_
p+ or P-
(a)
(b)
Figure 11: Illustration of iterations (100))=11 (a) lucky neuron, and (b) unlucky neuron.
Similar to the derivation of w for E B4, we can show that neurons in K_,, which are the lucky neurons with respect to & B_, have their weights updated mainly in the direction of p.. Recall that the output of GNN model is written as (20), the corresponding coefficients in the linear layer for k E B_ are all positive. With these in hand, know that the neurons in B4 have relatively large magnitude in the direction of p+ compared with other patterns, and the corresponding coefficients by are positive. Then, for the node e E V4 VN+. the calculated label will be strictly positive. Similar to the derivation above, the calculated label for the node E V_ U VN will be strictly negative.
Edge sparsification. Figure 1 ((b) shows that the gradient in the direction of any class irrelevant patterns is linear function of +I+12 12 without sampling. Sampling reduce the degree of the graph, i.e., the degree of the graph is reduced to r when only sampling r neighbor nodes. Therefore, the projection of neuron weights any p E Pv becomes smaller, and the neurons are less likely to learn class irrelevant features. In addition, the computational complexity per iteration is reduced since we only need to traverse subset of the edges. Nevertheless, sampling
edges can significantly
17

---

Published as a conference paper at ICLR 2023
graph edges may lead missed class-relevan features in some training nodes (a smaller a:), which will degrade the convergence rate and need a larger number of iterations.
Model sparsification. Comparing Figure 1 (a) and 1 ((b), we can see that the magnitudes of a lucky neuron grow much faster than these of unlucky neuron. addition, from Lemma we know that the lucky neuron at initialization will always be the lucky neuron in the following iterations. Therefore, the magnitude-ban based pruning method on the original dense model removes unlucky neurons but preserves the lucky neurons. When the fraction of lucky neurons is improved, the neurons learn the class-relevant features faster. Also, the algorithm can tolerate larger gradient noise derived from the class irrelevant patterns the inputs, which is in the order of //v/D/ from Figure 1 (b.... Therefore, the required samples for convergence can be significantly reduced.
Noise factor z. The noise factor degrades the generalization mainly in the following aspects. First, in Brutzkus & Globerson (2021), the sample complexity depends on the size of (rr which, however, can be as large [D] when there noise. Second, the fraction of lucky neurons reduced as function of the noise level. With a smaller fraction of lucky neurons, we require a larger number of training samples and iterations for convergence.
C NOTATIONS
In this section, we implement the details data model and problem formulation described in Section 3.2, and some important notations defined to simplify the presentation of the proof. In addition, all the notations used in the following proofs are summarized in Tables and
C.1 DATA MODEL WITH STRUCTURAL CONSTRAINTS
Recall the definitions in Section 3.2, the node feature for node e is written as
Fe Pa + Zuy
(14)
where Pa: P, and z, is bounded noise with || S a. In addition, there are L orthogonal patterns in P, denoted {pe)é- p+ : Pi is the positive class relevant pattern, p- :- P2 is the negative class relevant pattern, and the rest of the patterns, denoted as PN, are the class irrelevant patterns. For node v, its label yu is positive or negative if its neighbors contain p+ or p.. By saying a node contains class relevant feature, we indicate that Pe P+ or p-..
Depending v. and you divide the nodes in V into four disjoint partitions, i.e., V = V+ UV_ VN+ VN-, where
V4 {u P. pp };
V_ = (u Pr = p-}:
(15)
VN+ = (u P. E PN, Yo +1};
Vy- = {v P. E PN -11.
Then, consider the model such that (i) the distribution of p+ and p- identical, namely,
Prob(p, = p+) = Prob(p, = p-), and (ii) p Pn are identically distributed in VN+ and Vx namely,
(16)
Prob(p E VN+) = Prob(p v Vx-) for any p PN.
(17)
is easy to verify that, when (16) and (17) hold, the number of positive and negative labels in are balanced, such that
Prob(y- = +1) = Prob(y, =-1 2
(18)
If DD and D_ are highly unbalanced, namely, ||++| | > VPDi. the objective function in (2) be modified as
fo:=
1
Σ yo g W; X
yo g g(W; XN(W))
2|D+|
2|D__ RED
(19)
D
and the required number of samples |D] in (6) is replaced with min[|D.1 +| I.D
18

---

Published as a conference paper at ICLR 2023
C.2 GRAPH NEURAL NETWORK MODEL
It is easy to verify that (1) is equivalent to the model
g(W, U;
1 K
E AGG(( wx)
1 Σ AGG(XN(o))uu)) K
(20)
where the neuron weights {wE) in (20) are with respect to the neuron weights with by = +1 in (I), and the neuron weights {u in (20) are respect to the neuron weights with by = - in
(I). Here, we abuse K to represent the number of neurons in {k|b, = =11 {k|bb, = -1}, which differs from the K in (1) by factor 2. Since this paper aims at providing order-wise analysis, the bounds for K in (1) and (20) are the same.
Corresponding the model in (20), we denote M as the mask matrix after pruning with respect W and M_ as the mask matrix after pruning with respect to U. For the convenience of analysis, we consider balanced pruning W and U. i.e., || llo M
Kd
C.3 ADDITIONAL NOTATIONS FOR THE PROOF
Pattern function M(u). Now, recall that at iteration t, the aggregator function for node v is written
as
AGG(X (()))) (0)== max nEA(t((v)
<({ (
(1) Fn })-
(21)
Then, iteration t, we define the pattern function M(4) : P(OO} at iteration t
0, if max o({ o((w, w, In S
M M (u:w)
(EN((())
(22)
argmax oi w En }) otherwise (2.1IEA())))))
Similar to the definition of in (14), we define M and M such that M is the noiseless pattern with respect to (1 while M noise with respect to M
In addition, we define M: V + PU( for the case without edge sampling such that
0, if max o({ w. Fn )) 00 nEAie)
M(U;w)
(23)
argmax (m.)nEN(())
d(1 w. Fn }),
otherwise
Definition of lucky neuron. We call neuron is the lucky neuron at iteration / if and only if its (t) 1
weights vector in E jkmt satisfies
Mp (1) p+ for any V
(24)
(1KK or its weights vector in {u = satisfies
for any v V V. Let W(t), the set the lucky neuron at t-th iteration such that
Male; (1) ) =
(25)
W(t) {k (M (v; w(()) p+ for any V V}. u(t)= {k: (M(() (u; (t) p for any VE V}
(26)
All the other other neurons, denoted (t) and (t), the unlucky neurons iteration t.
Compared with the definition of "lucky neuron" in Proposition in Section 3.4, we have nT_ W(t) =
K. From the contexts below (see Lemma 6), can verify that K.+ W(1 W(0).
19

---

Published as a conference paper at ICLR 2023
Gradient of the lucky neuron and unlucky neuron. We can rewrite the gradient descent in (4)
f
Oro
(1)
k
(g( ; Xx(r())
(27)
[D]
k !9)
@g(W ( (1) U Xxww
1
(g( U x
2(D+|
(8)
2
Ow (t)
VED+
where D+ and D_ stand for the set of nodes in D with positive labels and negative labels, respectively. According to the definition of ( in (22), is easy to verify that
0g( W (0, U0 XN()) = (1;
(28)
Ow
and the update of wy is
1++1) (t)
w cn BEED yo (M) (1;
w
(29)
= w + Cn M w - Cy BEED BBED_MMM (u;
or k/
where we abuse the notation Eges to denote
f(v) Evess()) [S] DES
(30)
for any set S and some function f. Additionally, without loss of generality, the neuron that satisfies maxpep( (0) p) < O is not considered because (1) such neuron not updated at all; (2) the probability of such neuron is negligible as 2-
Finally, as the focus of this paper is order-wiss analysis, some constant numbers may be ignored in part of the proofs. particular, we use h1 (L) 2 (L) to denote there exists some positive constant C' such that h1 (L) 2 C ( when L E R is sufficiently large. Similar definitions can be derived for (L) F (L) and (L) S (T.).
D USEFUL LEMMAS
Lemma I indicates the relations of the number of neurons and the fraction of lucky neurons. When the number of neurons in the hidden layer is sufficiently large as (31), the fraction of lucky neurons is at least (1 - 6 - La fa/mi ///L from (32), where a is the noise level, and L is the number of patterns.
Lemma 1. Suppose the initialization (w Jk=1 and {u (0) K
(0) (K)
are generated through i.i.d. Gaus-
sian. Then, if the number of neurons K is large enough as
K ex -2 L2 log 4,
(31)
the fruction of lucky neuron, which is defined in (24) and (25), satisfies
La 1
2 - 6K
(32)
L
Lemmas 2 and 3 illustrate the projections of the weights for lucky neuron in the direction of class relevant patterns and class irrelevant patterns.
Lemma 2. For lucky neuron W(t), let w ((+1) be the next iteration returned by Algorithm 1. Then, the neuron weights satisfy the following inequality:
1. In the direction of p+, we have
( w
(1+1)
p+ )
(w)
10kk
p+ +
cn
V
(1 + r2)
log 9
D
20

---

Published as a conference paper at ICLR 2023
Table Important notations of sets
[2], Z E N+
The set of (1,
,2,
V
The set of nodes in graph G The set of edges in graph G The set of class relevant and class irrelevant patterns
E
P
K+
The set of lucky neurons with respect (
K-
The set of lucky neurons with respect (
Ka+ (4)
The set of unpruned neurons with respect to W
Ka (t)
The set unprumed neurons with respect to U(9)
PN
The set of class irrelevant patterns
D
The set of training data
D+
The set of training data with positive labels
D_
The set of training data with negative labels
V
The neighbor nodes of node (including itself) in graph f
N1 (u).ee) v
The sampled nodes of node at iteration t
W(t)
The set of lucky neurons with respect weights () iteration
u(tt)
The set lucky neurons with respect weights (+)) iteration
("))
The set unlucky neurons with respect weights ( iteration
(t)
The set of unlucky neurons with respect to weights (+() at iteration t
2. In the direction of p- or class irrelevant patterns such that for any p E P/D+, we have
( (11(1
(1+1)
pp- - (mm x pp) 2 CGp a Cy V
(1 r2 logg
k
-
D
and
(1+ logg
(++1) ( [wkk
p)) - (t)
p) S. (1+
[
Lemma 3. For lucky neuron l E ((1), let ug the neuron weights satisfy the following inequality:
(t+1) be the next iteration returned by Algorithm 1. Then,
1. In the direction p-, we have p-,
(1+1) U
p- ) 21 Uu
P- + co (a(aaoo)
a-
(1 + x2) log 9
D
2. In the direction of p. or class irrelevant patterns such that for any p E P/p_, we have
( [us
(t+1)
pP) - -(ut (t)
.p) 2 Cn -G VV
(1 + r2)
log
D
and
(1+
(1+1) [
p) - (u p) S .1 (1+0)
D
Lemmas 4 and 5 show the update of weights in an unlucky neuron in the direction of class relevant patterns and class irrelevant patterns.
21

---

Published as a conference paper at ICLR 2023
Table 3: Important notations of scalars and matrices
π
Mathematical constant that is the ratio of a circle's circumference to its diameter
d
The dimension of input feature
K
The number of neurons in the hidden layer
Cey v
The input feature for node e in R
Pos v
The noiseless input feature for node in R
Zv, v
The noise factor for node in Rd
ye, o E v
The label of node e [-1, +11
The degree of original graph G
W.U
The neuron weights in hidden layer
Xx
The collection of {mn hee in [dXX[
r
The size of sampled neighhor nodes
L
The size of class relevant and class irrelevant features
P+
The class relevant pattern with respect to the positive lahel
p-
The class relevant pattern with respect the negative label
The additive noise in the input features
a
The upper bound of || for the noise factor z
M
The mask matrix for of the pruned model
M- The mask matrix for U of the pruned model
Lemma 4. For unlucky neuron k W*(t), let w Then, the neuron weights satisfy the following inequality.
(+++) be the next iteration returned by Algorithm
1. In the direction p+, we have
( w
(1+1)
p+) 2 p+ Cg.
(1)
-cy V
(1 + r2) log
[D]
2. In the direction of p-, have
(w) ((+1)
pp - (w)) P- -c - -G -
(1 + r2
log
D
and
(1 + r2) logg
(w] (t+1)
p- p (w(() p-) cn
D
3. In the direction of class irrelevant patterns such that any E PNs we have
[1 (1+ log
w
(t+1) (e+1) p)) (w) p)l o (1 (1+
D
((+1) be the next iteration returned by Algorithim 1. Then, the neuron weights satisfy the following inequality.
Lemma' 5. For an unlucky neuron k E (t), ler u
1. In the direction of p_, we have
(++1) U
(t) p- 2 ( (u
(1 + 2
log
p_) Go 0
D
22

---

Published as a conference paper at ICLR 2023
2. In the direction of p+, we have
{ ukk (t-1)
-p+ - (1k (t)
P+ )+)) -cg - -a-a V
(1+ + r2) log
D
and
(1 + r2) log
4 (1+1)
P+ P+) (uk)
(u uuk's P+ Sc a.
(
3. In the direction of class irrelevant patterns such that any p E PN, we have
(1 + +2) log
(++1) 1( u p - uuk p)l - (1+
Lemma indicates the lucky neurons at initialization are still the lucky neuron during iterations, and the number of lucky neurons is at least the same the the one at initialization. Lemma 6. Let W(t), U(t) be the set of the lucky neuron at t-th iteration (26). Then, we have
W(t) S W(t + 1), U(t)) S ((t++)
(33)
if the number of samples
ž a + (1+))l
Lemma 7 shows that the magnitudes of some lucky neurons are always larger than those of all the unlucky neurons.
Lemma 7. Let (W')) be iterations returned by Algorithm I before pruning. Then, let WC(1) be the set of unlucky neuron at f'-th iteration, then we have
(w/)
(t)
w (1')
(t')
w (f))
k/2
(34)
for any k1 e W(t') and l2 E (O))).
Lemma 8 shows the moment generation bound for partly dependent random variables, which can be used characterize the Chernoff bound of the graph structured data.
Lemma 8 (Lemma 7, Zhang et al. (2020a)). Given set of X = {x J. that contains N partly dependent but identical distributed random variables. For each n E [N], suppose 2n is dependent with at most dx random variables in X (including In itself), and the moment generate function of Cs² In satisfies Ex, e < cs² for some constant C that may depend the distribution of In. Then, the moment generation function of EN In is bounded as
Exe ENN In S CdxxNo
(35)
E PROOF OF MAIN THEOREM
In what follows, we present the formal version the main theorem (Theorem 2) and its proof.
Theorem 2. Let EN E (0.1) and ελ E (0, oL) be some positive constant. Then, suppose the number of training samples satisfies
oL
D 2
(1 (1-3)3 -1+0)) (1 - -EK
(1+r3) 2 logg.
(36)
and the number of neurons satisfies
K K E L log q.
(37)
for some positive constant q. Then, after T number of iterations such that
Cg (1 3)
T a. (1 (1-68 EN σ) (1 EK oL/T)'
(38)
the generalization error function in (3) satisfies
(T( U(T))) =0
(39)
with probability at least 1 C for some constant C 0.
23

---

Published as a conference paper at ICLR 2023
Proof of Theorem 2. Let K3+ and K33- be the indices of neurons with respect to M, W and M_ 3 U, respectively. Then, for any node u E V with label yv = 1, we have
g(M+ 3 W M c 2(
max neN(o)
"((w) W (1) Vn
Σ
max nEN(u)
(6) o({
u on
KG-
kER
kEKA
2
Σ
max (EN(ee
o((w)) w
(t) In
|1C++ kE
Σ
1(
(1) Pn >
Σ
(0
max nEN(o)
max nEN(1))
2n
KK3-
|K3
kEK
kEK
E
(wk p+ + zn ) + |Kett
(t)
E
max neN(o)
o(( (t)
In ))
(40)
[1C++
kEW(()
kEK (W())
1
Σ
1( ((( Pn)) |Kg-1
Σ
max nEN(v)
K ku 2n
(0)
|Ka-1
nEA(e)
kEK
keKgg
1
Σ
(w) p+ + 2n
(t)
1G&+
kEW(L)
Σ
max
1( (( Pr >
Σ
max nEN(1)
K Ku
(1)
2m >1-
nEN(w)
KCg
kER
kEK
where W(I) is the set of lucky neurons at iteration L. Then, we have
Σ
(1) P+
2n
+
>
1-0 Σ (wh) P+))
Kg+1
Kg++1
kEW(()
kEW(O)
1-
|M(0O] cy (a-
(1 + r2)
log q
(41)
-
Kg+1
D
1
2V
[W(0]] Gn a
Kg+1
where the first inequality comes from Lemma the second inequality comes from Lemma 2. On the one hand, from Lemma 2, we know that at least (1 E واع K neurons out of [w (0) ===1 are lucky neurons. On the other hand, we know that the magnitude neurons in W(0) before pruning is always larger than all the other neurons. Therefore, such neurons will not be pruned after magnitude based pruning. Therefore, we have
x
[V(O) (1 EK
oh K = (1 oL
1ittctt (3)
(42)
Hence, we have
(w))) (t) p+ p+) 2(1
EK oI
1
[Co+] keW())
(1- t.
(43)
In addition, Xx(o) does not contain p- when yo Then, from Lemma and Lemma 5, we have
Σ
max 1( 1(
( Pn Pa 1 (1 + +
(1 r
log q
K
neA(v)
D
kE
(44)
σL
1
SEN (1 EK
a (1 3)L t
π
where the last inequality comes from (36).
24

---

Published as a conference paper at ICLR 2023
Moreover, have
Σ
(u4 (0)
2n )l 1 EEEK 1144 112 ||2.|12
max neV(o)
|Kg- k
S a EREKS E PEP/D-
(uk p))
(t)
(45)
(1- -t
x2++2)
Sa. Gn L(1 1(1+0))
[D]
Combining (43), (44), and (45), we have
(W()) 2 (1 - E1 - EK - oL/T)(1 - oL)
(1- B) Co .
a
(46)
Therefore, when the number of iterations satisfies
Cy 11-(1-1 (1- -3.
T a (1 EN - 0) -E-- oL/m) (1 oL)'
(47)
have (W U()))) > 1.
Similar to the proof of (46), for any v V with label yo 11, we have
g(M+ O W M
1KR+|
max nEN(1)
o0( ((ww) (T) En )) KKp-
Σ
max nEN(v)
(((u) (T)
xn ))
kEK
REK
o({ ((w(
(T) In
max BEN(v)
KKgl
kEK
Ku (T) Po >l + |Ke+1 AEKg
1( 1(u Zn >
(T)
max nEV(")
max nEN(e)
Kg++
keX
Σ
w
(T)
P + +z)) |Ka-1 (W()
Σ
max nEN(w)
o(( ((wwk)
(T)
Fn 1)
Kg-l REW(T)
Σ
max
1( (TTT) Pn >1
(T)
1
max nEN(e)
K6 uu 2n
[Cg+1
NEN(v)
|1o+1
kEK
AEK,+
(48)
(t)
2 K kEW(T)
Wwk
p- + zzn)
1
Σ
max
1( ((
(1) Pa )1+
max nEN(p)
1( (( (1)
2n >b
Kg++
nEN(M)
Ki++1
kEK
keK
S Kg-l
(U(T)] Gy aT
(1+r2)logs
(1 (+r2)log D
log T
tG (1 (1+ T. V.V
c, 0. (1+
(
$ (1 (x cx - -
oL/T) (1 oL)
a
1-
Hence, we have o( (W()), (())) < for any with label yn = -1 In conclusion, the generalization function in (3) achieves zero when conditions (36), (37), and (38) hold.
25

---

Published as a conference paper at ICLR 2023
F NUMERICAL EXPERIMENTS
F.1 IMPLEMENTATION THE EXPERIMENTS
Generation of the synthetic graph structured data. The synthetic data used in Section generated in the following way. First, we randomly generate three groups of nodes, denoted as V+, V_, and Vx. The nodes in V+ are assigned with noisy p+, and the nodes in V- are assigned with noisy p-. The patterns of nodes in Vn are class-irrelevant patterns. For any node in VN. will contact to some nodes in either V+ or V- uniformly. the node connects to nodes in V+, then its label is +1. Otherwise, its label is 1. Finally, we will add random connections among the nodes within V4 4. V_ or V. To verify our theorems, each node in VN will connect to exactly one node in V+ or V_ and the degree of the nodes in VN is exactly M by randomly selecting M - other nodes in Vx. We use full batch gradient descent for synthetic data. Algorithm terminates the the maximum of iteration 500 is reached. If not otherwise specified, 0.1, Gy = 1, r 20, a = r R, 3 0.2, = 50, L = 200, o = 0.2, and [D] = 100 with the rest of nodes being test data.
training error becomes
Implementation of importance sampling on edges. We are given the sampling rate of importance edges and the number of sampled neighbor nodes r. First, we sample the importance edge for each node with the rate of a. Then, we randomly sample the remaining edges without replacement until the number of sampled nodes reaches r.
Implementation of magnitude pruning model weights. The pruning algorithm follows exactly the same as the pseudo-code in Algorithm 1. The number of iterations T" is selected as
Illustration of the error bars. In the figures, the region in low transparency indicates the error bars. The upper envelope of the error bars is based on the value of mean plus one standard derivation, and the lower envelope of the error bars is based on the value of mean minus one standard derivation.
F.2 EMPIRICAL JUSTIFICATION DATA MODEL ASSUMPTIONS
In this part, we will use Cora dataset as example demonstrate that our data assumptions can model some real application scenarios.
Cora dataset is a citation network containing 2708 nodes, and nodes belong to seven classes, namely, "Neural Networks". "Rule Learning", "Reinforcement Learning". "Probabilistic Methods", "TThory", "Genetic Algorithms"" and "Case Based". : For the convenience of presentation, we denote the labels above as "class 1" to "class 7", respectively. For each node, we calculate the aggregated features vector by aggregating its 1-hop neighbor nodes, and each feature vector is in a dimension of 1433. Then, we construct matrices by collecting the aggregated feature vectors for nodes with the same label, and the largest singular values of the matrix with respect each class can be found in Table 4. Then, the cosine similarity, i.e., arccos |T= <21.22>
2 among the first principal components, which the right singular vector with the largest singular value, for different classes provided, and results summarized in Table 5.
Table 4: The top 5 largest singular value (SV) of the collecting feature matrix for the classes
Labels
First SV
Second SV
Third SV
Fourth SV
Fifth SV
class
8089.3
101.6
48.1
46.7
42.5
class 2
4451.2
48.7
28.0
26.7
22.4
class 3
4634.5
53.1
29.4
28.1
24.1
class 4
6002.5
72.9
37.0
35.6
31.4
class 5
5597.8
67.4
33.3
33.1
29.1
class 6
5947.9
72.1
36.7
35.5
31.3
class
5084.6
62.0
32.3
30.7
27.2
26

---

Published as a conference paper at ICLR 2023
Table 5: The cosine similarity among the classes
class
class
class 3
class 4
class 5
class
class 7
class
0
89.3
88.4
89.6
87.4
89.4
89.5
class 2
89.3
89.1
89.5
88.7
89.7
88.7
class
88.4
89.1
0
89.7
89.9
89.0
89.1
class
89.6
89.5
89.7
88.0
88.9
88.7
class 5
87.4
88.7
89.9
88.0
89.8
88.2
class 6
89,4
89.7
89.0
88.9
89.8
89.5
class 7
89.5
88.7
89.1
88.7
88.3
89.5
0
From Table 4, we can see that the collected feature matrices are all approximately rank-one. In addition, from Table 5, we can see that the first principal components different classes are almost orthogonal. For instance, the pair-wise angles of feature matrices that correspond to "class 1", "class 2", and "class 3" are 89.3, 88.4, and 89.2, respectively. Table 4 indicates that the features of the nodes are highly concentrated in one direction, and Table 5 indicates that the principal components for different classes are almost orthogonal and independent. Therefore, we can view the primary direction of the feature matrix as the class-relevant features. If the node connects to class-relevant features of two classes frequently, the feature matrix will have at least two primary directions, which leads matrix with a rank of two higher. If the nodes in class connect class-relevant features for two classes frequently. the first principal component for this class will be mixture of at least two class-relevant features, and the angles among the principal components for different classes cannot be almost orthogonal. Therefore, we can conclude that most nodes in different classes connect different class-relevant features, and the class-relevant are almost orthogonal to each other.
addition, following the same experiment setup above, we implement another numerical experiment on large-scat scage- dataset Ogbn-Arxiv further justify our data model. The cosine similarity between the estimated class- class-relevas relevant features for the first 10 classes are summarized in Table 6. As we can see, most of the angles are between 65 to 90, which suggests sufficiently large distance between the class-relevant patterns for different classes. Moreover, to justify the existence of node features have included comparison of the node features and the estimated
in (V_) and V'N+(VN) class-relevant features from the same class. Figure 12 illustrates the cosine similarity between the node features and the estimated class-relevant features from the same class. As we can see, the node with an angle smaller than 40 can be viewed as V+-V-), and the other nodes can be viewed as VN+ (VN-), which verifies the existence of relevate and class-irrelevant patterns. Similar results to ours that the node embeddings are distributed in a small space are also observed in (Pan al., 2018) via clustering the node features.
F.3 ADDITIONAL EXPERIMENTS ON SYNTHETIC DATA
Figure 13 shows the phase transition of the sample complexity when K changes. The sample complexity almost a linear function of 1/K. Figure 14 shows that the sample complexity increases as linear function of o2, which is the noise level in the features. In Figure 15, is fixed at 0.8 while increasing the number of sampled neighbors r. The sample complexity is linear in y2?
Figure 16 illustrates the required number of iterations for different number of sampled edges, and black dash line, is a linear function of a for r/R. We can see that the fitted curve matches the empirical results for a = r/R, which verifies the bound in (7). Also, applying importance sampling, the number of iterations is significantly reduced with a large a.
R 30. The fitted curve, which denoted
Figure 17 illustrates the required number of iterations for convergence with different pruning rates B. All the results are averaged over 100 independent trials. The black dash line stands for the baseline, the average number of iterations of training original dense networks. The blue line with circle marks is the performance of magnitude pruning of neuron weights. The number of iterations is almost a linear function of the pruning rate, which verifies our theoretical findings in (7). The red line with star
27

---

Published as a conference paper at ICLR 2023
Table 6: The cosine similarity among the classes
class
class 2
class 3
class 4
class 5
class 6
class
class 8
class 9
class 10
class 1
0
84.72
77.39
88.61
86.81
89.88
87.38
86.06
83.42
72.54
class 2
84.72
0
59.15
69.91
54.85
48.86
58.39
72.35
67.11
57.93
class
77.38
59.15
67.62
63.26
46.55
54.32
66.43
57.17
45.48
class
88.61
69.91
67.62
75.27
73.23
33.58
68.16
38.80
84.71
86.81
54.85
63.26
75.27
0
35.00
66.68
52.44
72.37
65.64
class 6
71.22
70.83
65.44
66.64
61.99
0.00
67.58
71.60
64.31
67.88
class 7
71.90
68.03
68.43
69.68
67.64
67.58
0.00
68.24
70.38
60.50
class 8
61.19
70.86
70.43
62.79
63.24
71.60
68.24
0.00
64.58
70.65
class 9
62.25
70.73
64.69
71.03
71.70
64.31
70.38
64.58
0.00
71.88
class 10
69.69
67.38
68.49
64.92
67.17
67.88
60.50
70.65
71.88
0.00
x10
6
4
20
40
60
80
100
120
A ngle between the node feature and the estimated rels-relevant feature from the same class
Figure 12: Distribution the cosine similarity between the node feature and the estimated class- relevant feature from the same class
marks shows the convergence without rewinding to the original initialization, whose results are worse than the baseline because random initialization after pruning leads a less overparameterized model.
Figure indicates the test errors with different numbers of samples by averaging over 1000 inde- pendent trials. The red line with circle marks shows the performance of training the original dense model. The blue line with star marks concerns the model after magnitude pruning, and the test error reduced compared with training the original model. Additional experiment by using random pruning summarized as the black line with the diamond mark, and the test error consistently larger than those by training the original model.
Further, we justify our theoretical characterization in Cora data. Compared with synthetic data, is not the sampling rate of edges but the sampling rate of class-relevan features, which is unknown for real datasets. Also, there no standard method for us define the success the experiments for training practical data. Therefore, we make some modifications in the experiments to fit into our theoretical framework. We utilize the estimated class-relevant feature from Appendix F.2 to determine whether the node is class-relevant not, i.e., if we call the node feature a class-relevant feature if the angle between the node feature and Mlass-relevamt feature is smaller than 30. For synthetic data, define the success of trial if it achieves we call the trial is success the test accuracy is larger than 80%. Figure 19 illustrates the sample complexity against -2, and the curve of the phrase transition is almost line, which justify
generalization error. Instead, for practical data,
28

---

Published as a conference paper at ICLR 2023
320
200
200
260
200
- 160
140
140
120
80
80
20
0.1 0.08 0.06 0.04 0.02
0.04
0.12 0.20
0.28
0.36
100
420 740,
10601380
1/K
Figure 13: [P] against the number of neurons K
Figure 14: [D] against the noise
Figure 15: [D] against the number of sampled neighbors
level o²
Number of ttemtions
Numberoi Itentiions
160
Kewisding ribslizzton autiiintio
u -lxeR
140
-6-a = =2xxR
60
Filtad
Test ertor
100
40
60
Magnitude proning
10
Ocginal priming
30
24
12
0.2
0.4
0.6
0.8
40
120
200
280
Number samples
Figure 16: Number of iterations against the edge sampling rate with random & important sam- pling-
Figure 17: Number of iterations against pruning rate of the model weights.
Figure 18: The test error against the number of samples.
theoretical results in (6). Figures 20 and 21 illustrate the convergence rate of the first 50 epochs when training on the Cora test. We can see that the convergence rates are linear functions of the pruning rate and as indicated by our theoretical results in (6).
140
Convergence rale training Cora
0.962
133
112
Convergesce rale
0.962
Convergecoe rale
126
0.96
0.961
119
0.958
0.96
0.959
112
0.956
0.96
1.8
1.6 1.4 1.2 1
0.954
1.1
12
-2
0.2
0.4
0.6
Figure 19: D against the es-
Figure 21: The convergence rate against the estimated importance sampling probability a.
Figure 20: D against the pruning
timated importance sampling rate B.
probability a.
F.4 ADDITIONAL EXPERIMENTS ON RELAXED DATA ASSUMPTIONS
In the following numerical experiments, relax the assumption (A1) by adding extra edges between (1) V+ and Vy- (2) V- and VAr, and (3) V+ and V_. We randomly select 7y fraction of the nodes that it will connect nodes "outlier nodes", and the other nodes are denoted as "clean nodes". Please note that two identical nodes from the of "outlier nodes" can have different labels, which suggests that one cannot find any mapping from the "outlier nodes" to its label. Therefore, we evaluate the generalization only on these "clean nodes" but train the GNN on the mixture of "clean nodes" and "outlier nodes".
node in V/_ (or V+) if its label is positive (or negative). We call the selected
Figure 23 illustrates the phase transition the sample complexity when y changes. The number of sampled edges 20, pruming rate 3 0.2, the data dimension
50, and the number of patterns = 200. We can see that the sample complexity remains almost the same when ? is smaller than 0.3, which indicates that theoretical insights still hold with relaxed assumption (A1).
29

---

Published as a conference paper at ICLR 2023
165
1
V N+
V N
V-
135
105
75
Figure 22: Toy example of the data model. Node 1 and have label +1. Nodes 3 and are labeled as -1. Nodes and have class-relevant features. Nodes and 3 have class- irrelevant features. V+ {1}, VN+ {2). Vx- (3).
15
0.15
0.30
0.45
0.60
Figure 23: The number of training
V_ [4].
nodes [D] against 7
Cora (ID) = 112)
Cora ([D) 140)
neurons (log scale)
0.99
neurons (log scale)
0.99
Rate of pruned
0.97
0.3
Rate of pruned
0.97
0.3
0.93
0.93
0,25
0.84
0.84
0.6
0.2
0.6
0.2
0
0.86
0.73
0.63
0.86
0.73
0.63
Rate of sampled edges
Rate of sampled edges
Citeseer ([D) 120)
Citeseer ([D) 96)
Rate prumed
neurons (log scale)
0.97
0.99
0.34
Rate of pruned
neurons (log scale)
0.97
0.99
0.34
0.93
0.32
0.93
0.32
0.84
0.3
0.84
0.3
0.6
0.6
0.28
0.28
0
1
0.86
0.73
0.63
1
0.86
0.73
0.63
Rate sampled edges
Rate of sampled edges
Pubmed (ID) 48)
Pubmed ([D) 60)
neurons (log scale)
0.99
0.26
neurons (log scale)
0.99
0.26
Rate of pruned
0.97
Rate pruned
0.97
0.24
0.24
0.93
0.93
0.84
0.22
0.84
0.22
0.6
0.6
0.2
0.2
0.86
0.73
0.63
0.86
0.73
0.63
Rate of sampled edges
Rate of sampled edges
Figure 24: Heatmaps depicting the test errors on Cora isub-figures in the first row), Citeseer (sub- figures in the second row), Pubmed (sub-figures, in the third row) with different number of labeled nodes.
F.5 ADDITIONAL EXPERIMENTS ON SMALL-SCALE REAL DATA
In Figures 26-25, implement the edge sampling methods together with magnitude-based neuron pruning methods. In Figures 26 and 24, the Unified GNN Sparsification (UGS) in Chen et al. (2021b) implemented the edge sampling method 4, and the GNN model used here is the standard graph
'The experiments are implemented using the codes from https: htt////tttt thub. com/V /tt//VVTA-Grrupp Uni fied- L.TH-GNN
30

---

Published as a conference paper at ICLR 2023
convolutional neural network (GCN) Kipf & Welling (2017) (two m passing). In Figure 25, implement GraphSAGE with pooling aggregation as the sampling method 5. Except in Figure 24, we use 140 (Cora), 120 (Citeseer) and 60 (PubMed) labeled data for training. 500 nodes for validation and 1 1000 nodes for testing. In Figure 24, the number training data is denoted in the title of each sub-figure.
Cora (ID) 140)
Citeseer [D) =120)
Pubmed ((2) 60)
neurons (log scale)
0.99
neurons (log scale
0.99
neurnns (log scale)
0.99
0.24
Rate of pruned
0.97
Rate of pruned
0.97
Rate pruned
0.26
0.23
0.93
0.24
0.22
0.84
0.84
0.84
0.6
0.2
0.6
0.28
0.6
0.21
0.86
0.73
0.63
0.86
0.73
0.63
0.86
0.73
0.63
Rate of sampled edges
Rate of sampled edges
Rate of sampled edges
Figure 25: Node classification performance of joint GrrahhSAGE-pooling and model pruning.
Figure 26 show that both edge sampling using UGS and magnitude- maggitude-based neuron pruning can reduce the test error on Cora, Citeseer, and Pubmed datasets, which justify our theoretical findings that joint sparsification improves the generalization. In comparison, random pruning degrades the performance with large test errors than the baseline.
Figures 24 and 25 show the test errors on Cora, Citeseer, and Pubmed datasets under different sampling and pruning rates, and darker colors denote lower errors. In all the sub-figures, we can observe that the joint edge sampling and pruning can reduce the test error, which justifies the efficiency of joint edge-model sparsification. For Figures 24, by comparing the performance joint sparsification the same dataset but with different training samples, one can conclude that joint model-edge sparsification with a smaller number training samples can achieve similar or even better performance than that without sparsification.
Cora
C Citeseer
Pubmed
0.4
UGS
UGS
LGS
Tost Trst.ono
0.35
Random sampling
asseline
Test error
Random sampling - goccine
Test enor
Daseline
Random sampling
0.3
0.35
0.25
0.25
0.2
0.3
0.2
geg eag
0.8
0.6
0.2
Rate of sampled edges
Rate sampled edges
Rate sampled edges
0.4
0.3
Magnitude-bar
Maguitude- based mudel gruning
Magnilude besed
0.35
model prining
model praming
Test ervr
Random pruning
Test erbr
Rancom proning
Test emrr
Bandom pruning
0.3
Basatlie
0.35
0.25
Baseline
0.25
0.2
0.9
0.99
0.99
0.99
0.999
Model sparsity (log scale)
Model sparsity (log scale)
Model spansily (log scale)
Figure 26: Node classification performance of GCN Cora (sub-figures in the first column), Citeseer (sub-figures in the second column), Pubmed (sub-figures in the third column).
F.6 ADDITIONAL EXPERIMENTS ON LARGE-SCALE REAL DATA
In this part, we have implemented the experiment on large-scale protein dataset named Ogbn- Proteins Hu et al. (2020) and Citation dataset named Obgn-Arxiv Wang et al. (2020) via 28- layer ResGCN. The experiments follow the same setup Chen et al. (2021b) by implementing Unified GNN sparsification (UGS) and magnitude-based neuron pruning method as the training
'The experiments are implemented using the codes from https: // wiigttub..o.. com/wi 1 fmmmleff/// GraphSAGE.
31

---

Published as a conference paper at ICLR 2023
algorithms. The Ogbn-proteiie dataset is undirected graph with 132,534 nodes and 39,561,252 edges. Nodes represent proteins, and edges indicate different types of biologically meaningful associations between proteins. All edges come with 8-dimensional features, where each dimension represents the approximate confidence of a single association type and takes values between O and 1. The Ogbn-Arxiv dataset is citation network with 169,343 nodes and 1,166,243 edges. Each node is an arXiv paper and each edge indicates that one paper cites another one. Each node comes with 128-dimensional feature vector obtained by averaging the embeddings of words in its title and abstract.
The test errors of training the ResGCN on the datasets above using joint edge-model sparsitification are summarized in Figure 27. We can see that the joint model sparsification can improve the generalization error, which have justified our theoretical insights of joint sparsification in reducing the sample complexity.
est error on Ogbn-Proteing
' est error on 0 Ogbn-Arxiv
0.16
0.288
0.1580
0.286
Test estterrr
0.156
Test eerorr
0.284
0.154
0.282
0.152
0.28
0.15
0.278
(1.00, 0.00)
(0.85,0.49)
(0.72,0.74)
(1.00, 0.00)
(0.85.0.49)
(0.72.0.74)
Rate of sampled edges x Rate of pruned neurons
Rate of sampled edges x Rate of pruned neurons
Ogbn- Proteins
(b) Ogbn-Arxiv.
Figure 27: Test error on (a) Peone-roteins and (b) Ogbn-Arxiv.
G THE VC DIMENSION OF THE GRAPH STRUCTURED DATA AND TWO-LAYER GNN
Following the framework in Scarselli et al. (2018), we define the input data as (Gv, v), where G, is the sub-graph with respect to node v. The input data distribution considered in this paper is denoted as G x V. To simplify the analysis, for any (G., v) E V. (v)) includes exactly one feature from (p+.P_) }. and all the other node features comes from PN- Specifically, we summarize the VC dimension of the GNN model as follows.
Definition 1 (Section 4.1, Scarselli et al. (2018)). Let be the GNN model and data set D be from x V. g is said to shatter 'D if for any set binary assignments y (0, 1)PP,, there exist parameters θ such that g ( (G., v)) > 0 if yo 1 and g(O; (9v,v)) < 0 if = O. Then, the VC-dim of the GNN is defined as the size of the maximum set that can be shattered, namely,
VC-dim(g)
max
(D]
(49)
D is shattered
Based on the definition above, we derive the VC-dimension of the GNN model over the data distribution considered in this paper, which is summarized in Theorem 3. Theorem 3 shows that the VC-dimension of the GNN model over the data distribution is at least 24/2-1, which is an exponential function of L. Inspired by Brutzkus & Globerson (2021) for CNNs, the major idea is to construct special dataset that the neural network can be shattered. Here, we extend the proof by constructing a set of graph structured data as in (51). Then, for any combination of labels, from (54), one can construct a solvable linear system that can fit such labels.
Theorem (VC-dim). Suppose the number of orthogonal features is L, then the VC dimension of the GNN model over the data G x V satisfies
VC-dim(HHawdd V)) > 2
(50)
32

---

Published as a conference paper at ICLR 2023
Proof. Without loss of generality, denote the class irrelevant feature {p:N=n? Therefore, P (p:)_ Up+ Up-. Let define set / such that
J - [0, (0, -
Then, we define subset D
with the size of 2 based on the set J.
For any (Ges v), we consider the graph structured data G. that connects to exactly L/2 - neighbors. Recall that for each node v, the feature matrix Xx(v) must contain either p+ or p-. we randomly pick one node E (V),, and let au be p+ p-. Next,
all the other nodes in (V()) and
label them as {0:) 1./2-1 Then, given an element J E J, we let the feature of node o; as
TS. J.p2-1 + - J:)
(51)
where J; is the i-th entry of vector J. we denote such constructed data (9., v) as Dy. Therefore, the data set D defined as
D DD
(52)
Next, we consider the GNN model in the form of (20) with K = 2 Given the label for each data D, E 'D, we obtain group of a, E R by solving the following equations
Σ
aj W.
(53)
J'
where J = - J. We can that (53) can be re- re-written
0
an
9/t
1 0
1
a2
3/21
(54)
1
1
0
011/2-1
(1122-1))
It is easy to verify that the matrix in (54) is invertible. Therefore, have unique solution of {aJ]JeJ given any fixed {yJ)Jer.
As K is selected as 2r/2-1, denote the neuron weights as {w> Jeer and {uilser by defining
wy = max(aj,
Σ
Ee'
of (EN(U)
(55)
Σ
Zy'.
V'EN(o).EED
Then, for each Dj E D, we substitute (55) into (20):
g = Σ max
a(l ((ww. F.l ))
max vEN(()
a((ur, x. 1))
(56)
WEN(()
J'ET
When o. 2 0, we have u, = 0, and
o(( (((w.: zee
('EN(()
Σ
Σ
=0. max
('
d'EN(U),NED
(57)
=0 max
(Jipai + J()pz)
0,
if J' = 1-
aa'
otherwise
33

---

Published as a conference paper at ICLR 2023
where the second equality comes from (51), and the last equality comes from the orthogonality of E P. Similar to (57), when aj < O, we have
a o(uy uy Deot
max r'E(())
Σ d'EN(D),EEDs =0, max (J.p2-1 + (1 - J:)p2s)
- (-aar) max
Σ
WEN(w),EDD
(58)
(J.p-11 J))p2)
0, if J'-
aJ, otherwise
Therefore, (55) can be calculated
=
Σ
max o(wws, Ie (EN((e
max (EN(v)
o((us' xv 1))
J'EJT
(59)
Σ
aj = VI,
J'EJ/JI
which completes the proof.
G.1 THE IMPORTANCE SAMPLING PROBABILITY FOR VARIOUS SAMPLING STRATEGY
In this part, provide the bound of for different sampling strategies. For simplification, consider a graph such that every node degree is (R r), and we sample fixed neighbor nodes for any node E V.
Lemma 9 provides the value of for uniform sampling strategy, and in the order of r/R R and depends on the average degree of nodes containing class-relevant patterns. Formally, we have
Lemma 9, For uniform sampling strategy such that all neighbor nodes are sampled with the same probability, we have
1-(1-
F) (10--(1---Ct))
S Ea Ea
(60)
where è is the degree of the nodes in 'D (V UV-).
Corollary 9.1, For uniform sampling strategy, when the node in Vx connects to exactly one node in V4 NVV V-, then Ea Corollary 9.2. For uniform sampling strategy, Ea 2 when 4 R.
Remark 9.1: Given a f. (6) yields the same sample complexity bound for all r. which leads to no improvement by using graph sampling. In addition, from (7), of iterations increase by a factor R/r, while the sampled edges during each iteration is reduced by factor of r/ R. Considering the computational resources used in other steps, should expect increased total computational time.
that the required number
Remark 9.2: From Corollary 9.2, we can see that uniform sampling can save the sample complexity by factor of when & R on average. However, one realization of a may have large variance with too small r. In practice, a medium range of r is desired for both saving sample complexity and algorithm stability.
For FastGCN Chen et al. (2018), each node is assigned with a sampling probability. We consider a simplified version of such importance sampling approach by dividing training data D into two subsets D, and Dú, and the sampling probability of the nodes in the same subset is identical. Let be the ratio of sampling probability of two groups, i.e.,
Prob(u e Dyis sampled)
(> 2 1).
Prob(e E Dpris sampled)
Lemma 10 describes the importance sampling strategy when sampling class-relevan nodes is higher than sampling Plass-ireeevaan nodes by a factor of y. From Corollary 10.1, we know that a can be improved uniform sampling by factor of y. Formally, have
34

---

Published as a conference paper at ICLR 2023
Lemma 10. Suppose Dj V+ UV_, and Du VN. we have
Y R R
Ba
(61)
Corollary 10.1. For the importance sampling strategy in Lemma 10, Eo 2 when R >
Remark 10.1: From Corollary 10.1, we can see that the applied importance sampling in Lemma 10 the sample complexity by factor of 7oz when < R average.
72
Lemma 10 describes the importance sampling strategy when fraction of nodes with class-irrelevant features are assigned with a high sampling probability. From Corollary 10.1, we know that a can be improved over uniform sampling by a factor of I+(7-1JX where À is the fraction VN n Drl/[xxl. Formally, have
Lemma 11.
Suppose D1 = V+ UV, where V> S VN with [Vx] A/Val- We have
75 (1 - 1)A)
Ea
(62)
Corollary 11.1. For the importance sampling strategy in Lemma 11, Ea 2 1+(7-1ja when R r.
Remark 11.1: From Corollary 11.1, we can see that the applied importance sampling in Lemma 11
can save the sample complexity by factor of (1+(=)1))) when r R on average.
H PROOF OF USEFUL LEMMAS
H.1 PROOF OF LEMMA I
The major idea is to obtain the probability of being lucky neuron shown in (66). Compared with the noiseless case, which can easily solved by applying symmetric properties Brutzkus Globerson (2021), this paper takes extra steps to characterize the boundary shift caused by the noise in feature vectors, which are shown in (65).
Proof of Lemma 1. For a random generated weights we that belongs to Gaussian distribution, let us define the random variable ig such that
11
if Wt is the lucky neuron
is = { otherwise
(63)
Next, we provide the derivation of i distribution. Let 0, be the angle between p+ and the initial weights w. Let {6 be the angles between p- and p E Py- Then, it is easy to verify that (0:)-_ belongs the uniform distribution on the interval [0, 2T). Because p E P are orthogonal to each other. Then, ( ww, p with p E P are independent with each other given belongs to Gaussian distribution.
equivalent to saying that (0r)/-, are independent with each other. Consider the noise level (in the order of 1/L) is significantly smaller than 1, then the probability of lucky neuron can be bounded as
Prob 01 + A0 < 0r 20 20, 2m, 25(5
40
(64)
where A0 σ. Then, have
Prob 01 + A0 < 02 A0 2m, 1.
I.
Prob
0, + A0 < 0 - A6 < 2T
(65)
2=1
01 A9 --1
2t
35

---

Published as a conference paper at ICLR 2023
Next, we can bound the probability as
2x 1
2nT
01
A0)
Prob(w is the lucky neuron)
d0,
2m
2m
1
2T
2
(66)
~
L
2m
1
Lo
L
We know d belongs to Bernoulli distribution with probability 2. know that
La), ). By Hoeffding's 's inequality,
1
1
Lo C log
1
Σ
K
is
1
1
Lo π
+
C'log q K
(67)
π
K
K
k=1
with probability at least y
Let K
D( 1.2 log q). we have
K
Lo
ik 2 - EK
(68)
K
T.
k=1
To guarantee the probability in (68) is positive, the noise level needs to satisfy
(69)
T.
n
H.2 PROOF OF LEMMA 2
The bound of the gradient is divided into two parts in (74), where I1 and I2 concern the noiseless features and the noise, respectively. The term Ig can be bounded using standard Chernoff bound, see (80) for the final result. While for I,, the gradient derived from D is always in the direction of p.- with lucky newron. Therefore, the neuron weights keep increasing the direction of p+ from (83). Also, if W): E. ) > 0 for some ye 1,, the gradient derived from will force wi moving in the opposite directions of Φe. Therefore, the gradient derived from D_ only has a negative contribution in updating Wk. For any pattern existing in {poheE__. which is equivalent to say for any p E P/ P/P+. the value of ( wk p ) has a upper bound, see (90).
Proof of Lemma 2. For any D_ and lucky neuron with weights w( we have
M(u; (2) p+ M_(3; w (t)).
(70)
If the neighbor node with class relevant pattern is sampled in (V the gradient is calculated
dg( (x(())
P + (.
(71)
Own
For E D._. and a lucky neuron w we have
M M (c: (1) (amIneN(o) U(o).
(72)
and the gradient can be represented as 0g (9), U(!; (x))()))
-M00 (0))
Ow
(73)
(u; + M. (o))
36

---

Published as a conference paper at ICLR 2023
Definition of 1 and Iz. From the analysis above, have
(w)
(t+1) (w(+!) p) - (wo P)
on BBED yo M (o (
) p)
(74)
cn (BvED( Be M (o; ( p) + EVED yo Mo p))
=G,(T1 + 12)-
Bound of 12. Recall that the noise factor 2, identical and independent with it is easy to verify that yo and Mu (u;e) ( are independent. Then, I2 (74) can bounded as
12 DBE EBED( M2 (9) p)1
< | |EEDD( M2 p)l
(75)
S De
Recall that the number of sampled neighbor nodes is fixed r. Hence, for any fixed node there
are most (1 + 2²) (including itself) elements in { (u/u D} are dependent with ye. Also, from assumption (A2), we have Prob(y = 1) = and Prob(y -) z.2 From Lemma 8, the moment generation function of EvED(M Ey,)) satisfies
EEED (b.- S ((4+)))))s
(76)
where Ey.- 0 and C' is some positive constant.
By Chernoff inequality, we have
> th c(1++))D
Prob
Σ
(yo E yo)
(77)
e Dl.th.s
VED
for any > Let th/(CC1++++ + r2 and th /(1 r2) D
log g, we have
Σ (ve E yu)
<C (1 D log
(78)
WED
with probability at least 1- 5. From (A2) in Section 3.2, we know that
Ryll S DD..
(79)
Therefore, Ig is bounded
12
yu
D
RED
1
(yo E yo)
+ BB yol
[D]
(80)
(1 + 22) logg
Say
D
Bound of [ when -++ Because the neighbors of node with negative label do not contain p+ Mp w (1) in (73) cannot be p.. addition, p.. is orthogonal (pa)neN()) U(0). Then, we have
0g W, U: UN()))
p+:
(p+ (v
(81)
Own
w(=w(()
Let us use (t) to denote the set of nodes that the class relevant pattern is included in the sampled neighbor nodes. Recall that a, defined Section 3, is the sampling rate of nodes with important edges, we have
D a|D+
(82)
37

---

Published as a conference paper at ICLR 2023
Combining (71), (73) and (81), we have
B
BeEeDMMplee Mp (0 (0)) EVED
Mp(e; BUED_MM(er p-)
{ EVED+ Mp (p (1)
) p+)
(83)
2 ( EVED Mp Mp(u; p+}
Bound of 1 when p # p+- Next, for any p P/P+, we will prove the following equation:
(1 + +
h
(84)
[
When w (e+1)) p)) 5 -0, have
(u; wk (1)) + p. and (u; (.)) p) = for any 8 U D.
(85)
Therefore, we have
I1 = ( (EEDD M (1; BOED_ M (1; (t)) p 0.
(86)
(++1)
When (w
p) > -o, have
[ = ( (EVDD. M (o EVED_ M (t) (u; (o (() p
(87)
(EEED) //HED,/D,HA /D, M
(( MD (u; (²)) EVED_ M (v: 20 p).
Let us define mapping H: Rdd - Rdd such that
p- if Pe =+
H(P.)) (p otherwise
(88)
Then, we have
h = EVED, M (1; - EVED M (1;utt) P))
= EVED+// /D. MI (v; wo (1) EVED (1; (1)) ( p))
=(Th FVEED+ /D. M (H( (0) RVED
(0) p))
(89)
I( EVED, M (H(V): w (1) EVED (1) p)
=( E (H()) (0) ELED (H(U)) (1) p)
where the third equality holds because (v) does not contain p+ for E D+/D,, and H.(X H((Nwor))) ())) = (v) Also, the last equality holds because o. does not contain p+ for node E D__. Therefore, we have
(EEED, (H((H( w(()) - EVED wH()) p)
=EvED yoMe "
(H(u)) u (1) p)
< BuBuDD EVEDY M (H(v): ())) p)
(90)
(1 + r2)
log
D
with probability at least q for some positive constant.
Proof of statement 1. From (80) and (83), the update of ww in the direction of p. is bounded as
( w k
(1+1) p+ ) - (w p+ ) (I - [2])
(1+ + r2 log 9
(91)
c (a V
D
38

---

Published as a conference paper at ICLR 2023
Then, have
[I + (2+ 1 3)- )-C.
w P+
(1)
(wk (0)
P+ cg (a V
-V
(92)
D
Proof of statement 2. From (80) and (90), the update of wy the direction of p E P/p+ is upper bounded
k p (w (t)
(++1)
p) S cy (T + (T2l)
(1 r2) logg
(93)
cn : (1 (1+
[
Therefore, have
w (1)
p) (w (0)
p) < G. (1+
(1 + r²) log
(94)
[D]
The update of wy in the direction of p E P/p- is lower bounded as
p (w (0) { w (++1)
p 2 cn cI(11 - (I2))
2 Gn (1+0.
(1 + r²) logg
(95)
D
To derive the lower bound, we prove the following equation via mathematical induction:
(1) .)) 2 -cn (1+o+
(1 + r²)
logg
(96)
[D]
It is clear that (96) holds when t = O. Suppose (96) holds for
When w (t)
p S -0, we have
(1) (c; 1
w (1) + p. and (M (u; w) (1)
p =0 for any
v D.
(97)
Therefore, we have
== ( BEEDD M (1) EVED_ (1; (1)), p) 0,
(98)
and
( W ((+1)
p) = (w (t)
p + cn (11 + 1z)
k
+ Gq 12
72) log
+ r2) log
2 Gq
1
+
(99)
Cq
D
D
(1+5
(1+ r2)
log q
- Cn
+ l(t + +1) 1).
Cg
D
When k p > -0, we have
( (wk p
(1+1)
( [ p) + cn - 12)
( (urk (t)
P) ) On' (EEED, M (u: w (t)) - E.ED M. (o p) + c712
(100)
(w (t)
p Cn' (EVED, M,) (v: (()) p)) + c,l2
(1 (1+ r
2 σ - - G
[D]
Therefore, from (99) and (100), know that (96) holds for /. 1.
39

---

Published as a conference paper at ICLR 2023
H.3 PROOF OF LEMMA 4
The bound of the gradient divided into two parts in (101), where 13 and I4 are respect to the noiseless features and the noise, respectively. The bound for I4 is similar to that for Iz in proving Lemma 2. However, for a unlucky neuron, the gradient derived from D+ not always of p+. We need extra techniques to characterize the offsets between D+ and 'D_. One critical issue is to guarantee the independence of M (v) and yo. which is solved by constructing matched data, see (108) for the definition. We show that the magnitude of w from (113).
direction
(t) scale the order of v(1 + /
Proof of Lemma 4. Definition of 1 and 1z. Similar to (74), we define the items 13 and 44
(wk (wbktt) (1+1)
p)) k P)
=n BBED Ue M (1; (0)) P) + EVED( (1; p)
(101)
= Cy (Is T4).
Bound of 4. Following the similar derivation of (80), we can obtain
+ logg
|La 2 V
(102)
D
Bound of 13 when = p+. From (101), we have
13 = ( EEED__Mi M (e; w (0) - M0
p+
= ( EvED_ M MM (2; ( p+)
w
(103)
2 0.
Bound of /3 when E Pv. To bound 14 for any fixed E Pv, we maintain the subsets St) D
such that Sx( {o D_ M (u; w()) }-
First, when (t) = V. is easy to verify that
13 = 0.
(104)
Therefore, St (ft++1) and (t) @ for all t' 2 t. Second, when (t) + 0, then we have
(t)) D__ 1p- 112
1 =
(105)
Note that if ( (w to || t number of iterations, (4o) = 0. and S₁ 0 with to from (104).
(t) p- < - then Sp(() must be an empty set. Therefore, after at most
Next, for some large to and any V, we define mapping F V - Rdd such that
F(v) oo o
(106)
From (101), we have
I4 EvEv yorMi ( (w; w (1) p))
(107)
where (ei...., - (v) and
Ov. Im,,
if Ir, p+ orp.
(108)
Ov. = O. if Ir, = p+ or p
When = 1, we have
(M( (2), p) = (MMP if (F(e)) #p+
(109)
00 (F(()) p), if (F()) p+
40

---

Published as a conference paper at ICLR 2023
When y -1 and & to, recall that Sx(t) D-, then have
(M (x), p) (F(x)), p).
(110)
Combining (109) and (110), we have
13 SEvev ( (M.) p)].
(111)
From assumptions (A2) and (17), know that the distribution of p+ and p. identical, and the distributions of any class irrelevant patterns p E Py are independent with Therefore, it is easy to verify that y and F(v) are independent with each other, then we have
13 SEUDDY EE, ((F(()) P)-
(112)
From (112) and (78), we have
+ 22) logg D
13 S
(113)
for any PN-
Proof of statement 1. From (102) and (103), have
(w ((+1)
p
(m) (1)
p Cqj (Iz T4)
2 Cnll4 /4
(114)
(1+ r2)
log q
2 1
D
Therefore, have
( (1)
p)) - (wwk (0)
pp) 2 C1f07
(1 + r2)
log
(115)
D
Proof of statement 2. When = p_, from the definition of I3 in (101), we know
13 = ( EVED M (o; w (t)
EVED (a (x; p-
= ( (EEED M (v; D-), p-)
(116)
< 0,
The update of we in the direction of p- is upper bounded as
(f+1) ( [
p- ) w p-
S en cn + I4)
S c
(117)
(1 + r2) log
$ Cg o V
D
Therefore, have
(1+ r2) log q .t.
( Tw p_) )-)- (w (0) p) S c. a
(118)
D
To derive the lower bound, we prove the following equation via mathematical induction:
( (t) p-) 2 cn (1 (1 r2 log 9
(119)
(
is clear that (119) holds when 0. Suppose (119) holds for t.
When (w (t)
p-) ) S -a, we have
M (v; (n)) a p-, and (M (v; (1; p- = for any D.
(120)
41

---

Published as a conference paper at ICLR 2023
Therefore, have
13 { , (u; (w )) EVED_ _
(v; (1; p-) 0,
(121)
and
( [wk
(1+1)
p
w p- } + cn (13 + 14)
(t)
{ W p-
(t)
+ Cn' 14
(1 + log
(1 + r2) logg
2 Cq
1
ot V
- crl
(122)
Cn
DD
D
(1 )llgggg
On
|
+ (t+
Cn
(D)
When W (t)
p-) > -0, we have
( (w (1+1) p
= -ww p + (13 - 14)
(w) P- + Cn (LEED M (v; w0 (t) EVED M (u;
p- + +
(123)
(m) p- -G D M (u: un (1) p- + cnp
(1 + r2)
2 on c, V
[D]
Therefore, from (122) and (123), know that (119) holds for 1.
Proof of statement 3. From (102) and (113), have
{( u (++1) p 2 (t)
p = Go 1/3 + Ia]
(1 r2) p²)log
(124)
S . (1 ())
D
Therefore, we have
(1+ 22)
logg 4.
1( (w p)) ( (0)
p>l S -1 (1+0).
(125)
D
H.4 PROOF OF LEMMA 6
The major idea is to show that the weights of lucky neurons will keep increasing in the direction of class-relevant patterns. Therefore, the lucky neurons consistently select the class-relevant patterns in the aggregation function.
Proof of Lemma 6. For any E (0)), have
(0) (1 [ a) p+ 2 (w (0)
(1 σ) p)
(126)
for any p P/p+ by the definition of lucky neuron in (24).
Next, from Lemma 2, we have
(w))) P+ 2 Cn a a--a- 01
(8)
(1 + r2) log
(D)
(127)
and
(w p)) < c, + oo)
(1)
(1 + r2)
log
D
42

---

Published as a conference paper at ICLR 2023
Combining (126) and (127), have
(1) w P+ ) 1 a
1- ( w/ p) (a- /
(1+ r²)
log
t.
(128)
D
When D 2 a2 (1 r²) log q, have ( w p+ 2 1t
I-0
w k
(1)
p)-
Therefore, we have k E W(t) and
W(O) C W(I).
(129)
One can derive the proof for U(t)) following similar steps above.
H.5 PROOF OF LEMMA 7
The proof is built upon the statements of the lucky neurons and unlucky neurons in Lemmas and 4. The magnitude of the lucky neurons in the direction of p+ is in the order of a, while the magnitude of unlucky neurons most 1/ VIDi. Given sufficiently large (D), the magnitude lucky neuron is always larger than that of an unlucky neuron.
Proof of Lemma 7. From Lemma 6, we know that (1) if 20k, is lucky neuron, wk, is still lucky neuron for any L' 2 0; (2) if w//)) is unlucky neuron, (t")
(0)
(f)
ky is still unlucky neuron for any t" S 1
For any k E W()), from Lemma 2, we have
(t') (t)) (t)) ) 2 w/(1) p+)
[w wkk
(1 + r²)
log 9
(130)
Z aa-o)
d.
D
For any 12 E WT''', from Lemma 2, we have
(
k2
(t))
k2
(1')
}
Σ
(t')
P))
PEP
Σ
(t')
p + (()()) p+
pEP/Dt
(131)
Σ PEP/P+
(w))) ,p)
(t')
(w)k) P))
(C)
PEPiP+
(1+ r2)
log
<L Cn (1 (1+
-t.
D
Therefore, ( (w) wk y < ki wk
(P)
(t))
(t') ) if [D] is greater than a -2((1 2 log
H.6 PROOF OF LEMMA 8
Proof of Lemma 8. According to the Definitions in Janson (2004), there exists a family of {(K},w;;}} where X, C X and wy E [0, 1), such that Σ, Wy Em., Ex, Σ, Wy S dxx by equations 12.1) and (2.2) in Janson (2004). Then, let Pý be any positive numbers with E, Pj = 1. By Jensen's 's inequality, for any s E R, we have
EX, :n, En Zn. and
M on Es =n s2y X, < Σ
Kw
X,
pie
(132)
where X, = -Eor,, EX, Iny.
43

---

Published as a conference paper at ICLR 2023
Then, have
E exee Σn'
SEx
Σ
Pje
Pj
E
E
Ps
Ow?
Σ Pj
(133)
N2
$ Pje
10, [2 11/2
Let Pj Σ, wi 77 then we have
Exe EN on Exsed(, = =
(134)
By Kauchy-Schwand inequality, we have
11,11111133 - Σ w Σ
Wy|KKy S Nx
(135)
j
Hence, we have
Exc² En an < No2
(136)
I EXTENSION TO MULTI-CLASS CLASSIFICATION
Consider the classification problem with four classes, we use the label E (+1,-1)3 to denote the corresponding class. Similarly the setup in Section 2, there are four orthogonal class relevant patterns, namely P P2, P3, P4. In the first layer (hidden layer), we have K neurons with weights wy Rdd the second layer (linear layer), the weights are denoted as bş R for the k-th neuron. Let W E Rdd K and B E 2 be the collections of wy, 's and by 's, respectively. Then, the output of the graph neural network, denoted as g E IR. calculated as
1
g(w X = K
by AGG wx).
(137)
A=1
Then, the label generated by the graph neural network is written as Yeu sg.n
(138)
Given the set of data D, we divide them into four groups as
W
b
ReLU
Pr11
yo
Vr.2
X (P)
b2
Nagative label
Aggregation
Hidden Hayer
Output Layer
Unkorsen
Figure 28: Illustration of graph neural network learning for multi-class classification
D; {(xx y) y (1, 1)),
D2 = {(x, y) = (1,1))}
(139)
D3 {(x, v) y (-1,1)),
and D4 { y) (-1,-1))
44

---

Published as a conference paper at ICLR 2023
The corresponding loss function in (2) can be revised as
fo(W.U) = D
Σ VED
ye g. b; bw(w)
(140)
Then, we initialize the weights of by as (1, 1), (1, (1), (-1,1) and (-1, equally. Next, we divide the weights wy into four groups based on the value of bg. such that
Wi = {k by = (1,1)}
W2 {kr by -11--1);
(141)
W3s = {A: by =)
and
W. {k by
Hence, for any & in Wi, have
Øf Sw
Ogi
0g2 dw
yo,1 Sw
Vv.
(142)
NED
When D1, we have
0g1
0g2
Mu.1
Ow
Vo.
Ow
-20' (wo x)) x0.
(143)
When x E D2, we have
0gi
Og2 0.
Vo.1
Sw
yo.2
Ow
(144)
When E D3. we have
0gi
Og2 0.
yo,1
Vu.2
(145)
dw
dw
When D4, we have
0g1
0g2
vv.1 Bw
Ve.2
20'(20 Tx)) x.
xx)
(146)
Then, for any E Wi, we have
w (t+1)
w (t) + Cy BUED, ( Go MLE (w (
(147)
Comparing (147) with (29), one can derived that the weights w (1) will update mainly along the direction of P1 but have bounded magnitudes in other directions. By following the steps in (142) to (147), similar results can be derived for for any & W; with 1 < <
45


Reviews:
[{"review_id": "us03s2C6mx", "reviewer": "Reviewer_swLg", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper proposes an approach for GNNs to jointly prune \n and sub-sample neighboring nodes (importance sampling) and provides theoretical and empirical evaluation to show the improvements in sample complexity and converge rate.\nThe paper provides a theoretical generalization analysis of GNN training with sparsified dataset and/or GNN model.\nThe analysis is restricted to node classification on a two-layer GNN and provides a few interesting theoretical results.\nThe method was evaluated  on three common small-scale  benchmarks(Citeseer, Cora, and Pubmed)", "summary_of_the_review": "Overall the paper is interesting paper addresses an important research field on GNNs, i.e, graph sparsification.\nThe provided theoretical analysis seems interesting and important.\nHowever, for my opinion, the paper is still in its preliminary stage, and to making a clear contribution (publication in a top-tier venue),\nthe provided theoretical analysis should be extended to multi-layer GNN models with different realistic GNN architectures\nand different known sparsification methods. \nIn addition, more experimental results on large-scale graphs should be provided.\n\nPre-rebuttal score: I give 5 (BR), and looking forward to receiving the author's responses to my concerns.", "strength_and_weaknesses": "*Strengths:* The theoretical analysis of GNN models/datasets sparsification is essential for developing more efficient algorithms on large-scale graphs.\n\n*Weaknesses:* The theoretical analysis and experimental results seem interesting, but I still have a few concerns regarding:\n\n1) In the introductory part is mentioned \n\"We consider the following problem setup to establish our theoretical analysis: node classification on a two-layer GNN,\" \nhowever, Figure 1 shows that the setup contains only a single GNN layer. \nFrom my understanding, two-layer GNN models consist of two sequential 1-hop aggregators. \n\n2) When we have a single-layer GNN model like it is presented in Figure 1, \nthe whole aggregation part can be done during the data preprocessing stage, \nin that case, the whole network can be considered a single fully connected layer.\nAs a result, it is hard to see the contribution of this theoretical analysis to realistic scenarios where we have a deal with multi-layer GNN models.\n\n3) The setup in section 2.1 is unclear.\nAccording to Figure 1, non-linear activation (ReLU) is placed before the \"Hidden Layer,\" whereas from eq. 5, it seems ReLU is placed between W and b.\n\n\n4) The assumptions A1 and A2 seem very restrictive for real datasets. \nCan the authors provide numerical justification of these on other, preferable large-scale datasets?\n\n5) Cora, Citeseer, and Pubmed are relatively small datasets. Their sparsification is less important. \nCan authors provide numerical results for larger datasets such as ogbn-arxiv, and ogbn-product?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "r5NY4ri5zG2", "reviewer": "Reviewer_X7Xt", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The paper provides a theoretical generalization analysis to show that jointly applying sparsification methods on both the graph edges (network topology) and neurons (model) of a graph neural network (GNN)  makes training more efficient in terms of sample complexity (required number of known labels) and convergence rate (stochastic gradient descent). The paper's main takeaways are as follows: (1) the learning performance is improved if the neural network is slightly over-parameterized (in terms of smaller sample complexity and faster convergence). (2) Edge sparsification reduces sample complexity. (3) Magnitude-based model pruning (removing neurons of smaller magnitude) also improves learning performance. (4) When applied together, joint edge and model sparsification enhance the learning performance. \n\nThe paper theoretically elates the sample complexity and the number of iterations to the edge sampling rate and magnitude-based pruning fraction. This analysis is based on two key assumptions - (1) every node with class-relevant features is connected to at least one similar node, and there are no edges between +ve relevant and -ve non-relevant nodes (or vice versa). (2) The positive and negative labels in the dataset are balanced. The paper presents the justification for the assumptions for the citation Cora dataset. Experiments on synthetic and real datasets support the conclusions of the theoretical analysis. \n", "summary_of_the_review": "The paper presents theoretical and experimental results on the connection of joint sparsification of GNN models with generalization error. While this framework is used in the field, this work emphasizes understanding different aspects of the GNN model and their relationship to training performance. The results on synthetic and real-world citation datasets are promising. However, it would be useful to think carefully about the generalization of the main assumptions to other types of graphs like proteins, social networks, etc. \n", "strength_and_weaknesses": "Strengths:\n- While previous works have shown the advantages of joint edge-model sparsification experimentally, this paper introduces a theoretical understanding of how sparsification improves training efficiency.\n- This paper does not solely focus on graph and model sparsity but also uses iterations to convergence and sample complexity to show how the joint sparse framework helps improve training efficiency.\n- The experiments on synthetic and real citation datasets back up their theoretical findings.\n\n\nWeaknesses:\n\n- The synthetic experiments clearly show the relationship between edge sampling rate and neuron pruning rate with the number of iterations and input samples. However, there are no such experiments for real-world citation datasets. It seems to me that this relationship is central to the paper’s contribution. Is there a reason for excluding this analysis? \n\n- While figures 11 and 13 represent the relationship between the sampling rates and test performance, we see different behavior in the graphs. For synthetic data, there is a consistent improvement in test performance as both rates increase, but for real data, there is an improvement only to a certain extent. An explanation of this difference in behavior can help the reader understand how well the theory generalizes to real-world applications.\n\n- The paper presents a numerical analysis of the Cora dataset to show that the important assumption A1 holds for this data. However, a similar analysis would be useful for a graph dataset that is not a citation network and represents another real-world application (like a protein or social network). Since all the datasets used in this paper are citation datasets that likely share similar underlying structures, it is unclear how generalizable this assumption (and, by extension, the theory) is to other GNN applications.\n\n\n\nMinor points:\n- Page 3 - “We only update W due to the homogeneous of ReLU function”  → “homogeneous nature of ReLU”\n- Page 5 (T1) - “can achieve zero generalization with” → “can achieve zero generalization error with”\n- Page 8, paragraph 3 - “The sample complexity is almost a linear function of K” → “a linear function of 1/K”.\n- Figure 11 - The paper states that α is a probability value (that lies between 0 and 1), but the labels for α in figure 11 are higher than 1.\n- The variable “L” is used a lot in the theorem and proofs, and thus I believe it should be added to table 1 (instead of in the supplementary).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jQ0YNFVvAi", "reviewer": "Reviewer_LzNm", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper introduces an approach for GNNs to jointly prune neurons (magnitude pruning) and sub-sample neighbouring nodes (importance sampling) and provides theoretical and empirical evaluation to show the improvements in sample complexity (less samples required for learning) and converge rate (less epochs required). Results of their method are demonstrated on three common benchmarks (Citeseer, Cora and Pubmed) using a UGS (Chen et al. 2021b) edge sampling approach. The results show that the pruning and the edge sampling combined do improve the sample complexity, convergence rate and can reduce the error beyond the model without pruning or edge sampling.", "summary_of_the_review": "It seems that the proof is reasonable, but it is hard to follow the intuition behind the idea easily. It takes from the ideas of other proofs, but then adds to these, and it's not crystal clear what contirbutions there are here. I also found a few parts that did not seem completely correct, and I did not check all of the proof, just some preliminary parts. I would say that the main novelty here is the theoretical analysis, and that as this is difficult to follow, understand and some checks on preliminary parts seem to be lacking the paper is not yet ready. The findings themselves are also not so surprising: that pruning and edge sparsification reduce the amount of data needed, the epochs required and can reduce the error. I like that the work is showing that most of the Cora dataset in practise seems to be homogenous, where nodes mostly have class-relevant nodes with class-relevant features, but this is not a very large contribution for a paper.\n\nI also think that the scalability of a single-hidden-layer GCN is not so interesting as the problem of why GNNs fail when more hidden layers are added. I refer to the DropEdge paper as an example of research in that direction, and DropEdge is also missing from this paper as a recent method of GNN edge sparsification with theoretical analysis. It seems that this paper could include analysis of multiple hidden layers to make this work much more interesting to the GNN community.\n\n[After Rebuttal Period]\n\nThe reviewers have clearly addressed many questions and concerns. Assumption A1 still seems very strong, and the analysis still seems to be missing details to be completely convincing that these connections are as assumed. However, the analysis certainly is a novel and imaginative approach to analyse graph node feature data relations, and gives some empirical evidence of A1, and is a valuable contribution in my opinion. I have therefore increased my score thanks to the discussions and clarifications and the amendments in the paper.", "strength_and_weaknesses": "The idea of showing theoretical evidence for GNN that pruning and graph-edge sparsification can jointly improve the sample complexity and the converge rate is valuable to guide future work in this area, addressing an important problem of the challenge of GNN on large data.\n\n\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster