Constant Time Graph Neural Networks
Authors: Ryoma Sato
Makoto Yamada
Hisashi Kashima
Venue:  (2020)
Keywords: graph neural networks
constant time algorithm

Abstract: The recent advancements in graph neural networks (GNNs) have led to state-of-the-art performances in various applications, including chemo-informatics, question-answering systems, and recommender systems. However, scaling up these methods to huge graphs such as social network graphs and web graphs still remains a challenge. In particular, the existing methods for accelerating GNNs are either not theoretically guaranteed in terms of approximation error, or they require at least a linear time computation cost. 
In this study, we analyze the neighbor sampling technique to obtain a constant time approximation algorithm for GraphSAGE, the graph attention networks (GAT), and the graph convolutional networks (GCN). The proposed approximation algorithm can theoretically guarantee the precision of approximation. The key advantage of the proposed approximation algorithm is that the complexity is completely independent of the numbers of the nodes, edges, and neighbors of the input and depends only on the error tolerance and confidence probability. To the best of our knowledge, this is the first constant time approximation algorithm for GNNs with a theoretical guarantee. Through experiments using synthetic and real-world datasets, we demonstrate the speed and precision of the proposed approximation algorithm and validate our theoretical results.

Under review as a conference paper at ICLR 2020
ON THE APPROXIMATION ERRORS OF NODE SAM- PLING FOR GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
The recent advancements in graph neural networks (GNNs) have led to state-of-the art performances in various applications, including answering systems, and recommender systems. However, scaling up these methods to huge graphs such as social network graphs and web graphs still remains a challenge. In particular, the existing methods for accelerating GNNs are either not theoretically guaranteed in terms of approximation error, or they require at least linear time computation cost. In this study, we reveal the query complexity of the uniform node sampling scheme for GraphSAGE, the graph attention networks (GAT), and the graph convolutional networks (GCN). The key advantage of our analysis is that the complexity is completely independent of the numbers of the nodes, edges, and neighbors of the input and depends only on the error tolerance and confidence probability while providing theoretical guarantee for the approximation error. To the best of our knowledge, this is the first work to give a theoretical guarantee of approximation for GNNs within constant time complexity. Through experiments using synthetic and real-world datasets, we demonstrate the speed and precision of the node sampling scheme and validate theoretical results.
question-
INTRODUCTION
Machine learning on graph structures has various applications such as chemo-informatics (Gilmer et al.] 2017), question answering systems (Schlichtkrull al., 2018), and recommender systems (Fan et al. 2019). Recently, a novel machine learning model for graph data called graph neural
networks (GNNs) Gori al. 2005 Scarselli et al.) 2009 Kipt & Welling 2017 Hamilton et al.
2017) demonstrated tfae-offthh--in performances in various graph learning tasks. However, large scale graphs such as social network graphs and web graphs contain billions of nodes, and even linear time computation cost per iteration is prohibited. Therefore, applying GNNs to huge graphs is challenging. Although Ying et al. (2018) succeeded in applying GNNs a web-scale network using MapReduce, it still requires massive computational resources.
There are several node sampling techniques to reduce GNN computation. For example, an empirical neighbor sampling scheme is used to speed up GraphS (Hamilton et al., 2017). FasIGCN employs a random layer-wise node sampling (Chen et al., 2018b). |Huang et al. (018)) further improved FastGCN by using adaptive sampling technique to reduce the variance of estimators. Chen et al. (2018a) proposed a variant of neighbor sampling, which used historical activations to reduce the estimator variance. Overall, the existing sampling techniques for GNNs work well in practice. However, these techniques are either not theoretically guaranteed in terms of approximation error, or thy require least a linear time computation cost.
In this study, we consider the problem of approximating the embedding of one node using GNNs in constant time with maximum precision We analyze the neighbor sampling technique (Hamilton et al. 2017) to show that a constant number of samples are needed to guarantee the approximation error. should be noted that the neighbor sampling was introduced as a heuristic method originally. and they did not provide any theoretical guarantees. Specifically, given an error tolerance = and
'e.g. predicting whether a user of an SNS clicks an advertisement by GNNs in real-tine mil-time (i.e., when the user accesses). A user may have many neighbors, but GNNs must respond in limited time, which prohibits exact computation. motivates us approximate the exact computation in limited time with theoretical guarantce.

---

Under review as a conference paper at ICLR 2020
Table / indicates neighbor sampling approximates the network in constant time. indicates any algorithm cannot approximate the network in constant time. / in the Gradient column indicates the error between the gradient of the approximated embedding and that of the exact embedding is also needs an additional condition to approximate it in constant time.
theoretically bounded. /
GAT, GraphSAGE- (GCN, mean)
GraphSAGE-pool
GCN
Activation
Embedding
Gradient
Embedding
Gradient
X
sigmoid / tanh
Thm.
Thm.
Thm.
Thm.
Thm.
/
X
x
ReLU
Thm.
Thm.
Thm.
Thm.
Thm.
X
X
x Thm.
X
ReLU + normalization
Thm.
Thm.
Thm.
Thm.
confidence probability 1 1- 6, our analysis shows that the estimate &, of the exact embedding R
of node such that Pr[l zull2 2 s] S 5 and the estimate
dz.. of the exact gradient "0
dzu of 30
the embedding 2, with respect to the network parameters 0, such that Pr[ll 0z.
|| e)
can be computed in a constant time. Especially, the uniform node sampling can approximate the exact embedding and gradients within O ( _ + log 2) - log {) time, where denotes number of layers. This complexity is completely independent of the number of nodes, edges, and neighbors of the input, which enables us to deal with graphs irrespective of their size. Moreover, the complexity is polynomial with respect to 1 and log 5. We demonstrate that the time complexity is optimal when L = with respect the eπror tolerance E.
Through experiments, show that the approximation error between the exact computation and its approximation rapidly converges to zero. To the best of our knowledge, this is the first constant time approximation algorithm for GNNs with theoretical guarantee in terms of approximation error.
Contributions: The contributions of this paper are summarized follows:
We analyze the neighbor sampling technique for GraphS AGE, GAT, and GCN to provide theoretical justification. Especially, our analysis shows that the complexity is completely independent of the number of nodes, edges, and neighbors of the input.
We show that some existing GNNs, including the original GraphSAGE (Hamilton et al. 2017), cannot be approximated in constant time by any algorithm (see Table for details).
We empirically validate theorems using synthetic and real-world datasets.
RELATED WORK
2.1 GRAPH NEURAL NETWORKS
Graph neural networks (GNNs) were first introduced by Gori et al. (2005) and and (Scarslll et al. (200))
They obtained node embedding by recursively applying the propagation function until convergence.
Kipf & Welling (2017) proposed graph convolutional networks (GCN), which significantly outper- formed the existing methods, including non-neural network based approaches. Gilmer et (2017)
proposed the message passing neural networks (MPNNs), a general framework of GNNs using the message passing mechanism. Veličković al. (2018) proposed the graph attention networks (GAT),
which incorporate the attention mechanism into GNNs. With the advent of GAT, various GNN models
with the attention mechanism have been recently proposed (Wang et al., 2019 Park et al. 2019).
GraphSAGE (Hamilton et al. 2017) is another GNN model, which employs neighbor sampling to reduce the computational costs of training and inference. Owing to neighbor sampling, GraphSAGE can deal with large graphs. However, neighbor sampling guarantee, and the number of samples is chosen empirically. An alternative computationally efficient GNN would be FastGCN (Chen et al.) 2018b), which employs lase random node sampling to speed up training and inference. Huang et al. (2018) further improved FastGCN by using an adaptive node sampling technique reduce the variance of estimators. Thanks to the adaptive
introduced without any theoretical
2

---

Under review as a conference paper at ICLR 2020
sampling technique, it reduces the computational costs and outperforms neighbor sampling in terms of classification accuracy and convergence speed. [Cen et al. (2018a) proposed an alternative neighbor sampling technique. which uses historical activations to reduce the estimator variance. Additionally, could achieve zero variance after a certain number of iterations. However, because used the same sampling technique of GraphSAGE: to obtain the initial solution, the approximation error was not theoretically bounded until the {2(n)-th iteration. Overall, the existing sampling techniques work well in practice. However, these techniques are either not theoretically guaranteed in terms of approximation error, or they require at least linear time computation cost to calculate the embedding of a node and its gradient of GNN models. Moreover, it is not clear whether we can apply the sampling techniques to state-of-the-art GNN models such as GAT.
2.2 SUBLINEAR TIME ALGORIHHM
The sublinear time algorithms were originally proposed for property testing (Rubinfeld & Sudan 1996). Sublinear property testing algorithms check whether the input has some property or the input is sufficiently far from the property π with high probability in sublinear time with respect to the input size. Sublinear time approximation algorithms More specifically, they calculate a value sufficiently close to the exact value with high probability in sublinear time. Constant time algorithms only in sublinear time with respect to the input size but also in constant time. The proposed algorithm classified constant time approximation algorithm.
another type of sublinear time algorithms.
subelass of sublinear time algorithms. They work not
The examples of sublinear time approximation algorithms include minimum spanning tree in metric space (Czumaj & Sohler 2004) and minimum spanning tree with integer weights (Chazelle et al.) 2005). Parnas& & Ron (2007) proposed a method to convert distributed local algorithms into constant time approximation algorithms. In their study, they proposed method to construct constant time algorithms for the minimum vertex cover problem and dominating set problem. A classic example of sublinear time algorithms related to machine learning includes clustering (Indyk 1999; Mishra et al. (001). Examples of recent work in this stream include constant time approximation of the minimum value of quadratic functions (Hayashi & Yoshida 2016) and constant time approximation of the residual error of the Tucker decomposition (Hayashi & Yoshida 2017). They adopted simple sampling strategies to obtain theoretical guarantee similar to our work.
In this paper, provide theoretical guarantee for approximation of GNNs within constant time for the first time.
BACKGROUND
3.1 NOTATIONS
Let G' be the input graph, V = 21. be the set of nodes, = V be the number of nodes, be the set of edges, m |8| be the number of edges, deg(v) be the degree of a node v, N(v) be the set of neighbors of node v, Fe E Rd be the feature vector associated to node E V. (æ), x2 .e.,.... )T)] x be the stacked feature vectors, and denotes the matrix transpose.
X =
3.2
NODE EMBEDDING MODEL.
Algorithm O2: Exact embedding
We consider the node embedding problem using GNNs. Especially, we employ the message passing neural networks (MPNNs) framework (Gilmer et al.] 2017). This framework includes many GNN models, such as GraphS AGE and GCN. Algorithm
Require: Graph G (V.E); Features X E R=xdo; Node index V: Model parameters O.
Ensure: Exact embedding z,
1: 2 < x; (ViE V)
2: for E (1,..., L.) do
T shows the algorithm of MPNNs. We re- fer to (L)) as 2g simply. The aim of this study is to develop constant time approxi- mation algorithm for calculating the embed- ding vector 2, and gradients dz with the given model parameters 0 and node
3: for i E do
h (1) + EveN(y) Mii(
(1-1) (1-1) 22 Einy
4:
2!)) < (1((((-1) (1,((1)))))))
6: end for
7: end for
d0
8: return 20)
3

---

|| are the Under review as a conference paper at ICLR 2020
3.3 COMPUTATIONAL MODEL ASSUMPTIONS
We have to specify how to access the input to design constant time algorithms because the constant time algorithms cannot read the entire input. We follow the standard convention of sublinear time algorithms (Parnas & Ron 2007; Nguyen & Onak 2008). We model our algorithm as an oracle machine that can generate queries regarding the imput, and we measure the complexity by query complexity. Algorithms can access the input only by querying the following oracles: (1) ddeg (w): the degree of node v (2) (G( i): the i-th neighbor of node v, and (3) Peeuuuee() the feature node v. We assume that our algorithm can query the oracles in constant time per query.
3.4 PROBLEM FORMULATION
Given a node v, we calculate the following functions with the least number of oracle accesses: (1) (v): the embedding 2 and (2) (v)) the gradients of parameters 8z, However, the exact computation of O and O, needs least deg(v) queries to aggregate the features from the neighbor nodes, which is not constant time with respect to the input size. Thus, it is computationally expensive to execute the algorithm for huge network. Therefore, we consider making the following approximations:
80
Ō (1, e, 8): an estimate 2. of 2, such that Pr]]
2, 2
Og(u, e, 8): an estimate
8z of Usn such that Pr[l| 00
8z 20
8x 20
2 E 6
80
where E > 0 is the error tolerance, 1 - is the confidence probability, and Euclidean and Frobenius norm, respectively.
|| ||2 and
Under the fixed model structure (i.e., the number of layers I,, the message passing functions, and the update functions), we construct an algorithm that calculates O₂ and O₂ in constant time irrespective of the number of nodes, edges, and neighbors of the input.
However, it is impossible to construct a constant time algorithm without any assumption about the inputs. Therefore, we make the following mild assumptions:
Assumption 3B s.t. ||æ,112 S B. |eeulll S B, and ||0||2 B.
Assumption deg(1)Mis, and U/ are uniformly continuous any bounded domain.
Assumption (Only for gradient computation) deg(i) DM and DU, are uniformly continuous in any bounded domain, where 1) denotes the Jacobian operator.
Building constant time algorithm is impossible without these assumptions shown in Section 5) Furthermore, we derive the query complexity of our algorithm when the message functions and update functions satisfy the following assumptions.
Assumption 3K E RR s.t. deg(i) Mia and U/ are K K-Lipschitz continuous any bounded domain.
Assumption (Only for gradient computation) 3バ" E IR s.t. Deg and DU, are K' Lipschitz continuous in any bounded domain.
4 PROPOSED METHOD
4.1 CONSTANT TIME EMBEDDING APPROXIMATION
Here, we build constant time approximation algorithm based on neighbor sampling, which approxi- mates the embedding 2, with an absolute error of most and probability 1 1- 8. We recursively construct the algorithm layer by layer by sampling (!) neighboring nodes layer 1. We refer to the algorithm that calculates the estimate of embeddings in the I-th layer z as (1_
The pseudo code is presented in Algorithm 2 Here, 6 (v +- u) means calling the function Ó!!- with the same parameters as the current function except for v. which is replaced by u. In the following, demonstrate the theoretical properties of Algorithm 2
4

---

Under review as a conference paper at ICLR 2020
Algorithm 2 ! Estimate the embedding z!
Require: Graph G (V. E. (as oracle); Features X Raxdo (as oracle); Node index v E V;
Model parameters 0: Error tolerance E; Confidence probability -.
Ensure: Approximation of the embedding =
1: 8()) + sample y (E, 6) neighbors of v with uniform random with replacement.
(1)
pll) Euesto) Mion(Ciemm (r), Oreature (u), Cius 0)
(1 (=1)
2: feg
Oun(v)
ml0) Enegio) M (o. (v v), - (u
u), Ciuu 0)
(1> 1)
3: 2()
Ui( (1-1)) (v v), ho 0) if otherwise Ui(O (eeaturr (v), h 0)
4:
return 2,
Theorem 1. For all E 0, 8 >> O, there exists (E, 5) (I 1, 1.....,I, L) such that for all inputs satisfying Assumptions and 2, the following property holds true:
Pr[]O=(V,
2, 22 8| 6.
Theorem [ shows that the approximation error of Algorithms is bounded by with the probability
1 - 6. It is proved by Hoeffding's 's inequality (Hoeffding 1963). The complete proof is available in the appendices. Because the number of sampled nodes depends only on and å and independent of the number of nodes, edges, and neighbors of the input, Algorithm 2 works in constant time. We provide the complexity when the functions are Lipschitz continuous.
Theorem 2. Under Assumption and 4, ,(L) O log ()) and (1)) ,(I),.... (.....,((--11) -(L-1) -0 (log
log })) are sufficient, and the query complexity of Algorithms 2 is O ( (log ! + log //2 ) log
We show that the query complexity of Algorithm is optimal with respect if the number of layers is one. In other words, a one-layer model cannot be approximated in o(2²) time by any algorithm.
Theorem 3. Under Assumptions and 4 and = 1, the time complexity of Algorithm 2 in Theorem 2 is optimal with respect to the error tolerance
The proof is based on Chazelle et al.'s lemma CCazelle et al. 2005 The optimality when L 2 2 is an open problem.
4.2 CONSTANT TIME GRADIENT APPROXIMATION
Next, propose constant time algorithm that approximates the gradient of embeddings with respect to the model parameters with an absolute error of most e and probability 1 1- 8. The basic
strategy to execute Algorithm 2 and calculate the gradients of the embedding z,. Let 0s. be the gradient of the embedding 2y with respect to the model parameter O (i.c., ( (0su
70
80 )ısk = 8x.2) ). 80,K.
Theorem 4. For all > 0, 1 > 8 > 0, there exists (E, 5) (1 = 11=1,..., 1,...,A. L) such thut for all inputs satisfying Assumptions 1, 2, and 3, the following property holds true:
(L)
0z(1) (L)
Pr[l|
F
2 5.
00
00
(1))) 30
is the gradient of (L)) which is obtained by 0 (v, 8), with respect to 0.
where
Therefore, we can calculate an estimate of the gradient of the embedding with respect to parameters with an absolute eтror of at most e and probability - 8 by running !!4) (v, 8) and calculating the gradient of the obtained estimate of the embedding. We provide the complexity when the functions are Lipschitz continuous.
Theorem 5. Under Assumptions 1, 4, and 5, (L) O log and (1)....,p(le.
0 (log + log })) sufficient, and the gradient of the embedding with respect pa- rameters can be approximated with an absolute error of at most e and probability in O frr (log 1 + log - log }) time.
5

---

Under review as a conference paper at ICLR 2020
Note that, technically, MPNNS do not include GAT because GAT uses embeddings of other neighbor- ing nodes to calculate the attention value. However, Theorem [nd Land4pen can be naturally extended to GAT, and we can approximate GAT in constant time by neighbor sampling. The details described in the appendices.
5 INAPPROXIMABILITY
In this section, we show that some existing GNNs cannot be approximated in constant time. These theorems state that these models cannot be approximated in constant time not only by our algorithm but also by any other algorithm. In other words, for any algorithm that works in constant time, there exists an eтror tolerance E, confidence probability approximation error for the input is more than e with probability 5. It indicates that the application of an approximation method to these models requires great supervision because the obtained embedding may be significantly different from the exact embedding.
6, and counter example input such that the
Theorem 6. If ||0 or ||@]] is not bounded, even under Assumption I and 2. the embeddings of GraphSAGE-GGN cannot be approximated with arbitrary precision and probability in constant time.
Theorem 7. Even under Assumption 1, the embeddings and gradients of GraphSAGE- -CGN with ReLU uctivation and normalization cannot be approximated with arbitrary precision and probubility in conslant time.
We confirm Theorem
7 Tthrough computational experiments in Section 6
Theorem 8. Even under Assumptions and 2, the gradients of GraphSAGE-GCT with ReLU activation cannot be approximated with arbitrary precision and probability in constant time.
However, it should be noted that the embeddings of GraphS with ReLU activation (without normalization layer) can be approximated in constant time using our algorithm by Theorem [| The following two theorems state that these models cannot be approximated in constant time even under Assumptions 1, 2, and 3.
Theorem 9. Even under assumptions 1, 2, and 3, the embeddings of GraphSAGE cannot be approximated with arbitrary precision and probability in constant time.
Theorem 10. Even under Assumptions and 3, the embeddings of GCN cannot be approximated with arbitrary precision and probability in constant time.
Constant Time Approximaiton for GCN: Due to the inapproximability theorems, we cannot approximate GCN in constant time. However, we can approximate GCN constant time the input graph satisfies the following property:
Assumption 6 There exists constant C' E R such that for any input graph G = (V.E) and node U, u E V, the ratio deg(v) to deg(u) at most C' (i.e., deg(v)))))) S C).
Assumption prohibits input graphs that have skewed degree distribution. GCN needs Assumption 6 because (1) the norm of the embedding is not bounded and (2) the influence of anomaly nodes with low degrees is significant without Assumption 6. It should be noted that the GraphSAGE-pol cannot be approximated in constant time even under Assumption 6.
EXPERIMENTS
We will answer the following questions through experiments:
Q1: How fast is the constant time approximation algorithm (Algorithm ?
Q2: Does Algorithm Algorithmmaaccurattee aaccuratlyy approximate the embeddings GraphSAGE-GGN without nor- malization (Theorem D.. whereas it cannot approximate the original one (Theorem ?
Q3: Does Algorithm 2 accurately approximate the gradients of GraphSAGE-GCH with sigmoid (Theorem 4 whereas it cannot approximate that with ReLU activation (Theorem 8
Q4: Is the theoretical rate of the approximation error of Algorithm tight?

---

Under review as a conference paper at ICLR 2020
tine GAT reast ShiphSADE eirddart tiee Drspksaae
OAT: 190000
6.125
1.-
0.532
termal
name lualan Suumphi
Pell samp
2.075
Hett samssko
with soma oitiin 183 cample
-dBlast cureltio minie pice
2.050
samples
0.022
como 1c0 camples
GraphSAGE: 150liiits
(a) Speed.
(b) Inference.
(c) Gradient.
meniall
GespitAst-GEN GAT
Nomotzed 12 asprox, crur
GCN
12 enor
GraphSAGE GAAGEE-GON
12
GCN
10-7
12-
10000
semples
comples
samples
(d) Theoretical rate.
(c) BA model.
(f) ER model.
Figure I: (a) The inference speed of each method. (b) The approximation error of the original GraphSAGE-GCN (i.e., with ReLU activation and normalization) and GraphS with ReLU
activation. (c) The approximation error of the gradient with ReLU and sigmoid activations. (d) The approximation error of Algorithm 2 and its theoretical bound. (e) The approximation error of GraphSAGE-GGN, GAT, and GCN with the Barabasi-Alhert model. (f) The approximation error of GraphSAGE-GON, GAT, GCN, and GraphSAGE- with the Rédös model.
Q5: Does neighhor sampling fail to approximate GCN when the degree distribution is skewed (Theorem ? Does it succeed when the node distribution is flat (Assumption 6)?
Q6: Does neighbor sampling efficiently work for real data?
It should be noted that we focus on showing the approximation error of neighbor sampling in this study as Hamilton et al. (017) have already reported the effect of neighbor sampling for downstream machine learning tasks ge.g. classification). The experimental details are described in the appendices.
Experiments for Q1: We measure the speed of exact computation and the constant time approxima- tion of the two-layer GraphS and two-layer GAT. We initialize parameters using the i.i.d. standard multivariate normal distribution. The input graph is clique K,, We ten-dimensional vectors from the i..d. standard multivariate normal distribution as the node features. We take (1)) (2) 100 samples. Figure (a) shows the speed of these methods as the number of nodes increases. This shows that the constant time approximation is several orders of magnitude faster than the exact computation when the number of nodes large.
Experiments for Q2: We use the original one-layer GraphSAGE-GGN (with ReLU activation and normalization) and one-layer GraphS with ReLU activation. The input graph is a clique K,,, whose features are 21 = (1, and æ; = (0, 1/n)T (i + 1), and the weight matrix is an identity matrix Iz. We use (1) = 5, 30, and 100 as the sample size. If a model can be approximated in constant time, the approximation error goes zero the sample size increases even if the graph size reaches infinity. The approximation errors of both models are illustrated Figure [ (b). The approximation error of the original GraphSAGE-GCN, converges to approximately 0.75 even if the sample size increases. In contrast, the approximation error without normalization becomes increasingly bounded as the sample size increases. This is consistent with Theorems and 7
Experiments for Q3: We study the approximation errors of the gradients. We use the one-layer GraphSAGE- GCN with ReLU activation and sigmoid activation. The input graph is a clique Kn. whose features are 3i = 21, and x, = (1, 1) (i * 1), and the weight matrix is ((-1,1)). We use (()) = 5, 30, and 100 as the sample size. The approximation error of both models are illustrated in Figure D (c). The approximation eтror with ReLU activation converges to approximately 1.0 even the sample size increases. In contrast, the approximation error with sigmoid activation becomes increasingly bounded as the sample size increases. This is consistent with Theorems 4 and g
7

---

Under review as a conference paper at ICLR 2020
Experiments for Q4: We use the one-layer GraphSAGE- with sigmoid activation. The input graph is a clique Kn, where the number of nodes is n = 40000. We set the dimensions of intermediate embeddings as 2, and each feature value is set to with probability 0.5 and -1 otherwise. This satisfies Assumption (i.e., ||æ I v2), We compute the approximation errors of Algorithm 2 with different numbers of samples. Figure (d) illustrates the 99-th percentile point of empirical approximation errors and the theoretical bound by Theorem 2 (i.e., & = Orr (())). ). shows that the approximation error decreases along with the theoretical rate. It indicates the theoretical rate is tight.
We analyze the instances when neighbor sampling succeeds and fails for variety of models. First, we use the Barabasi-Albert model (BA model) (Barabasi & Albert 1999) to generate input graphs. The degree distribution of the BA model follows power-law. Therefore, neighbor sampling will fail to approximate GCN (Theorem TO Assumption 6). We use two-layer GAT, and GCN with ReLU activation. We use ten-dimensional vectors from the ii.d. standard multivariate normal distribution as the node features. In this experiment, we use the same number r of samples in the first and second layer (i.e., r = ((1) = r(2)) and we change from 8 to 1000. We use graphs with n = 22 nodes. Note that if the constant time approximation possible, the error is bounded as the number of samples increases even if the number of nodes increases. Figure (e) shows the approximation error. shows that the error of GCN linearly increases even the and GAT gradually decrease as the number of samples increases. It indicates that we cannot bound the approximation error of GCN however large number of examples we use. This is consistent with Theorem I0 This result indicates that approximating GCN requires great supervision when the input graph is a social network because the degree distribution of social network presents the power-law as the BA-model.
Experiments for Q5:
GraphSAGE-Gon
number of samples increases. However, the errors of GraphSAGE-
Next, we use the Erdōs-Rénn Rényi model (ER model) (Erdös & Rényi 1959). It generates graphs with flat degree distribution. We use the two-layer GraphSAGE-GGN, GAT, GCN, and GraphSAGE-poo Figure [ shows the approximation error. It shows that the errors of GraphS GCN gradually decrease as the number of samples increases. This is consistent with Theorem [ and Assumption In contrast, the approximation error of GraphSAGE-pood does not decrease even if the input graphs are generated by the ER model. This consistent with Theorem 9
GAT, and
Experiments for Q6: We use three real-world datasets: Cora, PubMed, and Reddit. They contain 2708, 19717, and 232965 nodes, respectively. We We randomly choose 500 nodes for validation and 1000 nodes for test and use the remaining nodes for training. We use the two-layer GraphSAGE-On in this experiment. The dimensions of the hidden layers are set
Cara
orter (nomma/odd (oddd
0.9
Reodi
Cora Will
Corn gilt
with sigmoid activation
PutMed gett
0.4-
Reodi
to 128, and we use an additional fully connected layer to predict the labels of the nodes from the embeddings. We train the models with Adam (Kingma & Ba 2015) with a learning rate of 0.001. We first train ten models with training nodes for each dataset. The micro-FI scores of Cora, PubMed, and Reddit are 0.877, 0.839, and 0.901, respectively. It should be noted that we do not aim to obtain high classification accuracy here but intend to sanity check the models. In this experiment, we use the same number r of samples
0.0
60
&samples
Figure 2: Real data.
in the first and second layer (i.e., = (1) = (()) and we change r from 1 to 100. We also calculate the gradient of parameter matrices (1) and (22) with respect to the embedding obtained by Algorithm [ We compare these values with exact embeddings and exact gradients. Figure illustrates the 99-th percentile point of the empirical approximation errors. We normalize them to ensure that the value is 1.0 at r demonstrate the decreasing rate of each error. It shows that the approximation errors of embeddings and gradients rapidly decrease for the real-world data.
7 CONCLUSION
We proposed a constant time approximation algorithm for the embedding and gradient computation of GNNs, where the complexity is completely independent of the number of nodes, edges, and neighbors of the input. We proved its theoretical guarantee in terms of the approximation error. This is the first constant time approximation algorithm for GNNs in the literature. We further demonstrated that some existing GNNs cannot be approximated in constant time by any algorithm. Lastly, we validate the theory through experiments using synthetic and woaldworld datasets.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Albert-Laszlo Barabasi and Reka Albert. Emergence of scaling in random networks. Science, 286 (5439):509-512, 1999.
Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput., (166))1370-1379 2005.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In Proceedings of the 35th International Conference on Machine Learning, ICMI,, pp. 941-949, 20.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In Proceedings of the Sixth International Conference Learning Representations, ICLR, 20.
Artur Czumaj and Christian Sohler. Estimating the weight of metric minimum spanning trees in sublinear-time. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC, pp. 175-183, 2004.
Paul Erdōs and Alfréd Rényi. On random graphs I. Publicationes Mathematicae, 6:290-297, 1959.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Yihong Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In Proceedings of the 2019 World Wide Web Conference, WWW, pp. 417-426, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, ICML, pp. 1263-1272, 2017.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS, pp. 249-256, 2010.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings of the International Joint Conference on Neural Networks, IJCNN, volume 2, pp. 729-734 2005.
William L. Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30, NIPS, pp. 1025-1035, 2017.
Kohei Hayashi and Yuichi Yoshida. Minimizing quadratic functions in constant time. In Advances in Neural Information Processing Systems 29, NIPS, pp. 2217-2225, 2016.
Kohei Hayashi and Yuichi Yoshida. Fitting low-rank tensors in constant time. In Advances in Neural Information Processing Systems 30, NIPS, pp. 2470-2478, 2017.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13 March 1963.
Wen-bing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in Neural Information Processing Systems 31, NeurIPS, 2018.
Piotr Indyk. A sublinear time approximation scheme for clustering in metric spaces. Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS, pp. 154-159, 1999.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the Third International Conference on Learning Representations, ICLR, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the Fifth International Conference on Learning Representations, ICLRR 2017.
Nina Mishra, Daniel Oblinger, and Leonard Pitt. Sublinear time approximate clustering, In Proceed- ings of the Twelfth Annual Symposium Discrete Algorithms, SODA, pp. 439 2001.

---

Under review as a conference paper at ICLR 2020
Huy N. Nguyen and Krzysztof Onak. Constant-timg time approximation algorithms via local improvements. In Proceedings of the 49th Anmual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 327-336, 2008.
Namyong Park, Andrey Kan, Xin Luna Dong, Tong Zhao, and Christos Faloutsos. Estimating node importance in knowledge graphs using graph neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Diseovery Data Mining, KDD, pp. 596-606 2019.
Michal Parnas and Dana Ron. Approximating the minimum vertex cover in sublinear time and connection to distributed algorithms. Theor. Comput. Sci., (81((-3):1833-199)) 2007.
Ronitt Rubinfeld and Madhu Sudan. Robust characterizations polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271 1996.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 20(1))61-80, 2009.
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In Proceedings of the 15th European Semantic Web Conference, ESWC, pp. 593-607, 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proceedingy of the Sixth International Conference on Learning Representations, ICLR, 2018.
Hongwei Wang. Miao Zhao, Xing Xie, Wenjie Li, and Minyi Guo. Knowledge graph convolutional networks for recommender systems. In Proceedings of the 2019 World Wide Web Conference, WWW, pp. 3307-3313, 2019.
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 the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, pp. 974-983, 2018.
10

---

Under review as a conference paper at ICLR 2020
A MODELS
We introduce GraphSAGE- GCN, mraphn, GraphSAGE-pool the graph convolutional networks (GCN), and the graph attention networks (GAT) for completeness of our paper.
GraphSAGE-GCN (Hamilton et al. 2017): The message function and the update function of this model is
Moou Bus Cous 0)
deg(
Ui(zv, Nu, 0) = o ( h.),
where W is a parameter matrix and is activation function such sigmoid and ReLU. GraphSAGE-GCN includes the center node itself in the set of adjacent nodes (ie.,N(() + N(v) (u)).
GraphSAGE-mean (Hamilton et al. 2017 The message function and the update function of this model
Miou (Zu: Zue Con. 0) deg( v)
Ui(ze: h 0) = o Zz. hw)):
where [-] denotes concatenation
GraphSAGE-pool (Hamilton al. 2017): We do not formulate GraphSAGE-pool using the message function and the update function because takes maximum instead of summation. The model of GraphSAGE-pool is
20) (max(((WW ((1-1) b) u E (())))
GCN (Kipf & Welling 2017 : The message function and the update function of this model is
Meeu (Zur Rus evrs 0) / deg (r)deg(u)
Ui(zo, h 0) ().))
GAT (Veličković al. 2018) The message function and the update function of this model is
exp(LEAkYRBLU(a") (W()) 2p, (1) z2.)))
E EweN(w) (xp(LFARYRFL (W W02,,
Mivu(Zo, Zu. Cva. i) a Zu.
Ui(z., hv, 0) (WW(),))) h.).
Note that, technically, MPNNs do not include GAT' because GAT uses embeddings of other neigh- boring nodes to calculate the attention value O However, we can apply the same argument as MPNNs GAT, and neighbor sampling can approximate GAT in constant time other MPNNs. To be precise, the following proposition holds true.
Proposition 11. If Assumptions holds true and a is Lipschitz continuous, if we take p(L) = 0 log }) and (1)) ,..., ((..1) O (log log })) samples, and let
2(0) 2 (0)
11

---

Under review as a conference paper at ICLR 2020
COpLEEARREL W 21
h(0 Σ
6 2(1-1),
wES())
Ui(E! h
Then, the following property holds true.
Pr Pr[l 2(4) 1a 2 2
We prove Proposition 11 Section
B EXPERIMENTAL SETUP
Experiments for Q1: For each algorithm and for n 22,, ...., 2 we (1) run the algorithm with an input graph, (2) we calculate the exact embedding of one node and its estimate using 100 samples (i.e., (()) = (2) = 100), (3) calculate the approximation error. We run the process above 10 times, and we report the mean value of time consumption.
We initialize the weight matrix (1)) with normal distribution and then normalize it so that the operator norm || lop of the matrix equal to 1. This satisfies Assumption 1 (i.e., ||0||2 S v2). For each r = I.... 10000, we (1) initialize the weight matrix, (2) choose 400 nodes, (3) calculate the exact embedding of each chosen node, (4) calculate the estimate for each chosen node with r samples (i.e., (1) r), and (5) calculate the approximation error of each chosen node.
Experiments for Q4:
Experiments for Q5: In the experiment for the AB model, we (1) iterate from 8 to 1000, (2) set n = r², (3) generate 10 graphs with n nodes using the BA model, (4) choose the node that has maximum degree for each generated graph, (5) calculate the exact embeddings and its estimate for each chosen node with samples (i.e., (1) = (2) = r), and (6) calculate the approximation error.
The experimental process for the ER model is similar to that for the ER model, but we (1) use the ER model instead of BA model and (2) set floor()..55 instead of r2 to reduce the computational cost.
Experiments for Q6: To calculate the approximation errors of embeddings, for each trained model, for r 1... 100, we (1) calculate the exact embedding of each test node, (2) calculate an estimate of embedding of each test node with r samples (i.c., y(1) = (2) = r), and (3) calculate the approximation error of each test node. To calculate the approximation errors of gradients, for each dataset, we (1) initialize ten models with Xavier initializer (Glorot & Bengio 2010), (2) choose random 1000 nodes, and (3) for each model, for each chosen node, and for
100, calculate
the exact and approximation gradients of the classification loss with respect to the parameters, and calculate their approximation error.
C PROOFS
We introduce the following multivariate version of the Hoeffding's inequality (Hoeffding 1963 to prove the theoretical bound (Theorem (anooremmaanlll
Lemma 12 (multivariate Hoeffding's inequality). Let 21,, Sh,,......5 Ba be independent d-dimensional random variables whose two-norms are bounded ||æ,;12 S B, and let be the empirical mean of these variables क = 1.x Σi= x;. Then, for any E > 0,
ns²
Pr[] - E[ 2 E] < 2dexp
2
holds true.
12

---

Under review as a conference paper at ICLR 2020
Lemma 12 states that the empirical mean of O 22 log 3)) samples independently sampled from the same distribution is the approximation of the exact mean with an absolute error of at most e and probability 1 8.
Lemma 13 (Hoeffding's s inequality (Hoeffding 1963). , Let X1, X2...... Xn be independent random variables bounded by the intervals [- B, BJ and let X be the empirical mean of these variables
X 1 Eis X4. Then, for any E > 0,
n
Pr|lX - E| 2 a) 5 expp
2
holds true.
Proof of Lemma 12
Apply Lemma 13 to each dimension i of X,. Then,
nE²
Pr[|Xx - E| 2 Vd S exxp
2B2d
should be noted that [x < because 12 < B. Therefore,
ne²
Pr[ak E 21, ...2................. d} Xx
E E[ 2 Vd
2xe
2
| - R[X]&| < Va
holds true for all dimension k, then
82 =E. va
1 E[
Σ (X. - E[8]k]2
A=1
Therefore,
ne² 2
Pr[l |[[]]l22 2 e| 2dexp
First, we prove that the embedding in each layer is bounded.
11 Lemma 14. Under Assumptions and 2, the norms of the embeddings || 11
!|
1|2.
(1
1|2.
and [[ (1) ll2 (1 =1= 1,......, L.) are bounded by a constant E R.
Proof of Lemmal 14 We prove the theorem by performing mathematical induction. The norm of the input to the first layer is bounded by Assumption 1. The message function deg(i) and the update function Uj is continuous by Assumption Since the image f(X) compact set X Rd is compact if f is continuous, the images of deg(i) Mia and U₁ are bounded by induction.
L
Proof of Theurem We prove the theorem by performing mathematical induction on number of layers L.
Base case: It is shown that the statement holds true for I.
Because UL is uniform continuous,
3e' Vzv. h h 0 lh, h1,12 < || hv. 0) U2(2v, h/ 0)12 <E. (0)
(1)
Let 2y be the k--th sample in ((I) and Xx deg(v) (x1 22x Cuvx 0). Then,
E[xx]= = Σ MLeu 2 Cou, 0) = (2)
(2)
uEN(2>)
There exists constant C' E IR such that for any input satisfying Assumption 1, [ < C
(3)
holds true because ||= [|, | i I|, |le ll,, and ||0||2 are bounded by Assumption 1 and
deg(v)MLvv is continuous. Therefore, if we take (L) = 0( 1/2 log 4) samples, Pr[] _n
_ (1.)
||2 2
el < 8 by the Hoeffding's inequality and equations 2 and Therefore, Pr[]I((F) 2b 1|2 2
I 8.
13

---

Under review as a conference paper at ICLR 2020
Inductive step: is shown that the statement holds true for L= 1=I it holds true for L I. The
induction hypothesis is VE > 0, 0,1> >>100 6 > 0, 3r(1) o)...,..................... (E, such that Ve E V,
Pr|llo! (u, (u,E, zul2 2 el S 8.
Because Uz is uniform continuous,
3e's 0, Vzu, nu: z/y ni,, 0. [| ho] [2 h,lll2 < = [1UL(Zu hr; 0) UL(21 h', 0)1l <e, (4)
where [:]
denotes concatenation. By the induction hypothesis,
3r( (.t,,..,''((I.. such that (r(l)O!(>)))) 2((-11) 112-1)11222 12226//V2 8/2.
p'(L-1)
(5)
holds true. Let
deg(v) r(L)
(2 2/4 2((1-11 Cvus 0). uES(()
Σ
Let 2y be the k-th sample in S(T.) and X₁
(xm 22z Cuay 0). Then.
(b-1) (b-1)
B[Xa] Σ
MEna(z!
(1)11), (1-1)) Coze, 0) (b)))
(6)
2z
wEN(v)
There exists a constant C' E R such that for any input satisfying Assumption 1,
|| X < C,
because ||=/(-1) 12, (|=(41111 12, Ile 112. and |012 are bounded by Assumption 1 and Theorem 14 and deg(v) is continuous. If we take (LL) O L log }.. then
Pr[l 1o (1 2 e'/(2/2) S 8/4, by the Hoeffding's inequality and equations (6) and 77. Because deg()) uniform continuous,
3s" > 0 such that ||[=!--1) =u =[[-1)]-- [x] =u 2111-111122 E
+ deg(r))) (z! (2) zn (1-11), Svus 0) M (2 (x)(111), zuu (((-11)
evu, 0)(l S //(222).
By the induction hypothesis,
3, (() such that Pr[l) 2 2((ا0)112 2 2 < 6/(8/(4))
(10)
Therefore, the probability that the errors of all oracle calls are bounded is
Pr|Bu E S(4), (v), - [x(1- 21 (L-11)|11 2 5"1 s 8//4.
(11)
By equations 99) and
Pr(Eu E SLL)
deg())][MLzn122 (L-1), (L-1) =u
Cvu, 0) ML (b(6-1) MIva(ElL-1 2(L-1) (,( Cru,
s 6/4.
P h 2| 2 (2v/2) - 8/4.
(12)
By the triangular inequality and equations
(8) and 12
Pr[l h [1) 1|2 2 / e//22// $ 8/2.
(13)
Therefore, if we take (1) max (1) 111) (L-1) max (r" (L- ,(L-1)),, by equations 5 and (13
Pr Pr[I[[=!--1), h((0 - ( 1 50
(14)
Therefore, by equations and 14
Pr Pr[lI((L) x3(0) 1/ 5.
14

---

Under review as a conference paper at ICLR 2020
Proof of Theorem
We prove this by performing mathematical induction the number of layers.
Base case: It is shown that the statement holds true for I. -= 1.
If Ur is K K-Lipschitz continuous, s' (e) in equation Therefore, p(L) O log t.
Inductive step: It is shown that the statement holds true for I. = 1 + 1 if it holds true for I. = I.
Ur and MAva are K Lipischhiz continuous, e' (s) in equation 4 and = O(s) in equation
(9). Therefore, م(م O + log f)) We call ( (v) such that Pr Pr(l (v) 20 (2-1) 12 || >
e//v2] S 6/2 in equation
Therefore, r()), ,.... ((1-1) = 0 (log log are sufficient
by the induction hypothesis. We call (x) such that Pr[]| Pr[l
/v2 < 0 (log ! + log ()) are sufficient
2 2
(/())(()) in equation (10). Therefore, rr()), ...... (((--)) (((()
by the induction hypothesis because log 8/(8812T) Ollog 1 log f). In total, the complexity is 0 22 (log ! g
+ log - log }
Lemma 15 Chazellle et al. ).005). Let D be Bernoulli ). Let n-dimentional distribution D be (1) pick 8 with probability 1/2 and otherwise; (2) then draw n values from DD Any probabilistic algorithm that can guess the value of with probability error below 1 1/4 requires O ) bit lookup on average.
Proof of Theorem 3 We prove there is a counter example in the GraphSAGE-GCN models. Sup- pose there is an algorithm that approximates the one-layer GraphSAGE-Gon within o(E²) queries. We prove that this algorithm can distinguish D in Lemma 15 within o(E?) queries and derive a contradiction.
Let o be any non-constant K K-Lipschitz activation function. There exists a, E R (a > b) such that a-b
a(a) * a(b) because is not constant. Let S = a(a)-a(b) > 0. Let > 0 be any sufficiently small positive value and & E {0, 1)"h be random variable drawn from D. We prove that we can determine s with high provability within o(e?) queries using the algorithm. Let G be clique Kn, and (11) = 1. Let us calculate ag and be using the following steps: (1) set a2 = a and b = b; (2) a - bg < E, return a₂ and b5; (3) m = = (4) if (a()) - (m)) > (a(m) - obb)),, )l. then set b = m, otherwise a₂ m, and (5) back to (2). Here, E/2 S a b <,, a I a < b. and (az) (bb)) 2 e hold true. Let Dr the (2t. 1) d be for all Elh, 1] = a, and Eh,, s= --1 b. Therefore, Pr[1z, (a.)) < $ s = n + co and Pr[12 o (b=)l < &e | -1] enror tolerance to S and to sufficiently large number. Then = 1 if 22, a(az)l < S and otherwise with high probability. However, the algorithm accesses (i.e., accesses renture) Li
V. Then,
1 as as n - o because o is K-Lipschitz. We set the
of times. This contradicts with Lemma 15
Lemma 16. Under Assumptions 1, 2 and 3, the norms of the gradients of the mes- sage functions and the update functions [|DUi(z!-!) 1-1) n1 0))r. |DDU(E"!")) n 0)]lr. DonguuDMiuull (1111) Du Cvu, 0)l and [deg(u) DMvu (1-1) ou Ceu, 0)ll are bounded by
a constant B' E IR.
Proof of Lemma T6 The input of each function is bounded by Lemma Dao is uniform continuous, these images are bounded.
Because DU, and
Proof of Theorem layers
We prove the theorem by performing mathematical induction on the number of
Base case: It is shown that the statement holds true for I. 1.
15

---

Under review as a conference paper at ICLR 2020
When the number of layers is one,
0z!4)
0UL (0)
aU (2
h (1) 0) (4)
(2)
0 0) +
00
00
Oh [L)
00
OUL (0) (1) 0) (T.)
aU
(2) h (L) 0) 0M (z! (0)) Evus 0).
00 (z())
0h
00
mEN(e)
22!4)
JUL (2(0), 1 0)
oh! (L) (z h ,0) ah
ØUL
00
00
00
aUl (0) (L)
aUl L (0) (L) deg(v)
iM (z , =z4 Evas 0).
00 (2()
0) +
(L) (Zg
oh
L()
00
(ES(L)
Because DU, is uniform continuous,
3 > 0 s.t. for all input,
[1 (0 1l2 < E +
OUL (z(0) h (L) 0)
0UL
(Il 00
(0) h( 00)|F 5/2A
00
0UL (2(0) h 0)
ØUL (2( h(t) 0)( < e/(4B'))
(15)
0h! (L)
oh! (L)
If we take (L) 0 log )
Pr(l (1) h 12 2 E¹1 S 8/2
(16)
holds true for any input by the argument of the proof of Theorem !
Let Fg be the k-th sample in ((L) and X deg(u) 0M
(z) 200) Cruy 0). Then,
0e
oh!") (L)
aMLeu (2(0), 200) Cou 0)
Σ
(17)
00
00
(c)
There exists constant C E IR such that for any input satisfying Assumption 1,
| ll C,
(18)
||2, 12000 2| levr 2|,, and ||0||2 are bounded by Assumption and deg(t) is continuous. Therefore, if we take (L) = log })) samples,
because ||=.5)|12,
ah. (L)
oh!") (L)
Pr[1
||r 2 e/(B < 8/2
(19)
00
a0
holds true by the Hoeffding ' inequality and equations
17 and 18). If
ah!4)
oh!
(L)
||F E/(AB')
00
00
and
aUL (z("),
aUL
(L) 0)
(z( ( 00)1|| < <<(BB))
(n()))
ah!
hold true, then
oh! (L)
aU 1
Th! (L)
aUr. 1. (0))) (1 0)
ah! [1) (2
(. 0)
00
a0 ah!L)
(L)
16

---

Under review as a conference paper at ICLR 2020
OUL
ah
(L)
aU,
(2
(( 0)
(z)
1 ,))l
00 oh!
00 0h
oh!
a...
Oh (1)
OUL
(x) h (L) 0
F
(0) (1) 0)1l
00
dh!
00 Oh
0h!
aU
aUL (0) h
||
(0)
(L)) 0)
(L) 0)I
80
0h (1)
Oh
oh (D)
0UL
|||||
(0)
h (L) 0)
80
00
Oh.
[L)
0UL
0UL
(1)
(I)
B'||
(2
h()) 0)
(
(0) h 0)([= B'|
||
dh:
(L)
Oh.
(L)
00
00
B'
+ B'
4B
4B
2
Therefore, Pr[l (z(4)
(z(L)
|| 2 E| < 8 by equations 15 (1 and (1)..
00
Inductive step: It is shown that the statement holds true for L = + 1 if it holds true for =
0z!4)
JUL
OUL
(2 (1-1) (1,)) 0)
Oz (1-1) (2) (1b-1) (((,)) ,0 00
00
00
aU,
MMimu (L-1) 2(6-1) Cou, 0)
oh! (T) (2) (1-1)) ( 0)
(z) =u
00
(EA(o)
Ozb (1-11
OUr, (L-1), h 0) Σ
aMronn (b--)) - ا|[-11 erau 0)
ah
(T)
Ozl (1-1)
00
aU, (L-1)
aM (x(1-1) 2((-11
dzl (1-11)
0h. (1) (2) 1 0)
Ozl (1-1) =2 eva, 0)
00
uEN(())
03(4) OUL (z( (1 0) +
OUL
(2((-1),, ((, 0Ell-1)
00
00
(1
00
00.
deg(v)
2(L-1) Mi (2(6-1), 2/11 e 0) 00
(=( (
oh!!
P(L)
LES(L
OU, ((L-1) 1) h (L)
deg(u)
OM (x(L-1), 2(L-1) (2(L-1)
ds!
2/ e 1)
0h( (L)
D()
00
LE
OUL (2((.-1) ((())
deg(v) p(L)
ÖMLva (2(1-11)
(2(L-1)
(2-1-1) 2 2(I.-1) eva 0)
ah!4) (L.)
00
HES(L)
Because DU is uniform continuous,
Be' > s.t. for all input.|l=(!!-111
(1-11) 1 (1 - 12( <
aUL
0UL (( (1- ((()) 0)]| < <(E)) A
(1)
(z (L-1)
h (I)
0) d0
00
OU. (2(2-1) (L) 0)
aU. (L-L1)
k 0)|F < <0(e)
ah!!)
(L)
ah(
17

---

Under review as a conference paper at ICLR 2020
au (2( 0z (2-1) (
au
1 ,0)
(2( h .0]| ,,)1 < O()))
(20)
Oz
Because deg(t) is uniform continuous,
3e"
0 s.t. for all input.
||]=([11]] 2((1-111 (2((-1) 2uu
2/1--11112 <=" =
LUL (x(1-1)) x(1-11
(deg(v))
00
(2(1-1)
2u ((1-11) Cou, 0)
00
=2
Cou. 0)|(r < O(e) A
|| iM
aU
deg(v)]
(T) (z) =/ (((-1)
(L-11)
Svus 0)
(2 (1((-1) 2(1-1) Svu, 0)|| < 0(e) A
@h(
0h!
LM (2(4-1),
aUL
deg(v)]l
Zu 2(1-11 Cvu, 0)
(L (2
1 2(1-1)
Cou. 0)|| < (c)). (21)
O2 (L-1)
By the argument of the proof of Theorem
if take sufficiently large number of samples,
Pr[l 2/6 2(1-1)122 2 Ommin('' = s O(s)),
(22)
Prilin (C) 11 2 0(5')) = 0(8).
(23)
By the induction hypothesis, there exists (1)) ...., , (1-1)) such that
(1-11)
(1-1-
Pr[l 00
|| 5 Osed),
Pr[11 dz1
(L-1)
02(L-1)
||r 2 0(s) S O(e)),
00
00
If we take ((() = = log t)
aMLva (1-1) (1-1)
Prll Σ
(z! 26 Cvus 0)
00
(EN(w)
deg(v)
aM (z! (I-11) ((--1) Euu, 0) 0(s)] & 0(8),
(24)
(())
30
NES(L
aM (1-1)) (b-1)
02
Prill Σ
wEN(v) (1- (2) 22 Cous 0)
00
dz(1-11) (f--1)
deg(u) UU)
aMLva (z(1-1) (I--1) Evas 0
Oz
(L)
NES(L) (L-L-1)
=2u
00
2 0()) S 0()),
(25)
(1--1) iMLow (2(1--1) 1) 2/ Cou, 0) (4-1)
02
Prill Σ
00
wEN((v)
(f-11-)
(L-1)
deg(u) U) (L)
OMLva (2(1-1) 1), = (L-111
(1.-1) evar 0
2 0()) S (0)),
(26)
00
NES(L)
holds true by the Hoeffding's inequality. Therefore.
((--1) MM (2(1-1) =z evn, 0)
Pr[l Σ
00
(e)
18

---

Under review as a conference paper at ICLR 2020
(e
Lo (2(4-1), 2/ 2((-11 Guu 0)1 0(e) - 0(6),
(27)
r(2)
00
UES(L)
dzlL-11
Lou (11-1) 2(11-1), Sous 0
Pr[ll Σ
02!4-1) :2
00
(EN(")
deg(u)
OMLve (2(4-1), 2n =(1-1) Evay 0
02l
2 0()) s (0(),,
(28)
r(L)
0e(h-1)
00
LES(L)
0z(L-1)
OM Lou OzL (EN(2)
Pr[ll
Σ
22
(1-11) 1) =
(11--1) Sou; 0
00
deg(v)
OM (2(4-1), 2/ Evan 0)
(1-1)
a(L-1)
2 0()) S 00)),
(29)
(L)
02(1-11
00
(ES(L)
holds true by equations 20
22
25 and 26
Therefore, if we take (1))
(LL sufficiently large, Pr[l] (z)))
(z(1)
2 E| S holds true by
00
00
equations (20 21..
27
28
and
29
Proof of Theorem 5
We prove this by performing mathematical induction on the number of layers.
Base case: It is shown that the statement holds true for L = 1.
If DUz is K' K'-Lipschitz continuous, E' = Oc) in equation 15
Therefore, rLL = = log )) is
sufficient.
Inductive step: It is shown that the statement holds true for T, = 1 + 1 i it holds true for T. T, I.
If DU2 and (e is K" -ipsshict continuous, E' = OE)) in equation 20 and e" = (s))
in equation 21). b. Therefore, (L) = O log and (1)) (L-1) = O ( (log + log !) are
sufficient.
Proof of Theorem 6 We show that one-layer GraphSAGE-Grr whose activation function is not constant cannot be approximated in constant time if || or ||0 la are not bounded. There exists a E IR such that (a) * o()) because a is not constant. We consider the following two types of inputs:
G is the clique K,, (1) L, and x; for all nodes V.
G is the clique K,. (1) 1, x. = 0(i 전 v) for some e E V, and æ, = an.
Then, for the former input, (1)) = (0). For the latter type of inputs, z(1) = (a). Let A be arbitrary constant algorithm and C be the number of queries A makes when set lo(a) a (0) When A calculates the embedding of u + E V, the states of all nodes but u are symmetrical until A makes a query about that node. Therefore, if n is sufficiently large, A does make any query about o with high probability (i.e., at least (1 ر )). If A does not make any query about v, the state of AA the same for both types of inputs. If the approximation error less than for the first type of inputs, the approximation error is larger than e for the second type of inputs by the triangle inequality and vice versa. Therefore, A fails to approximate the embeddings of either type of inputs with the absolute error of at most e. As for 0, we set ((1) an and x, 1 for the second type of inputs. Then, the same argument follows.
19

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 7 We consider the one-layer SAAAAAGG-GGNN with ReLU and normalization
(i.e., 0 (x) = REL (z)/ (2)2()) We use the following two types of inputs:
G is the clique Kn, W(I) is the identity matrix I,, (0,0) (a + v) for some node
V E V. and B, = (1,0)T.
G is the clique Kn, W is the identity matrix 1,, H, (0.0) (i # v) for some node V E V. and x2 = (0, T)
Then, for the former type of inputs, h; = (1/n,0)T,* = (1,0) and Oay. = 1 for all i E V. For 2W arbitrary constant algorithm and C' be the number of queries A makes when we set & = 1/3. When A calculates the embedding or gradient of * v V, the states of all nodes but u are symmetrical until A makes a query about that node. Therefore, if is sufficiently large, A does not make any query about with high probability (i.e., at least (1 n-1 )2) If A does not make any query about v, the state of A is the same for both types of inputs. If the approximation error is less than e for the first type of inputs, the approximation error is larger than e for the second type of inputs by the triangle inequality and vice versa. Therefore, A fails to approximate the embeddings and gradients of either type of inputs with the absolute error of at most E.
aW
the latter type of inputs, h, - (0, 10.1/n) 2; = (0.1) (o.1))aami and Øz.2. 0 for all E V. Let A be an
Proof of Theorem &
We consider the one-layer GraphSAGE-GGN with ReLU (i.e., axx (x) We use the following two types of inputs:
G is the clique Kn. w(1) = (-1,,),, a, = (1, (i * v) for some node v E V, and
Fp = (1, 2)
G is the clique Kn. w(1) (-1, x; (1, (i + v) for some node E V, and
x, = (1,
Then, for the former type of inputs, MEAN(( a (
h. 2, m OW = (1, + ) for all i E V. For the latter type of inputs, MEAN(( | u N())) and az.
Oz 4) T h = -1 2u 0. and OW (0, 0) for all E V. Let A be arbitrary constant
algorithm and C' be the number of queries A makes when we set E = 1/3. When calculates the gradient of u # v V. the states of all nodes but are symmetrical until A makes query about that node. Therefore, if n is sufficiently large, A does not make any query about u with high probability (i.e., at least (1 9). If A does not make any query about v, the state of A is the same for both types of inputs. If the approximation error is less than e for the first type of inputs, the approximation error is larger than e for the second type of inputs by the triangle incquality and vice versa. Therefore, A fails approximate the gradients of either type of inputs with the absolute error of most Li
We consider the one-layer GraphSAGE-pool whose activation function satisfies (1) # (0) and the following two types of inputs:
Proof of Theorem 9
G is the clique Kn, (11) 1, b 0, and a; 0 for all nodes E V.
G is the clique K,, ((1) (1) = 1, b = 0, x; = 0 (i + v) for some node e E V, and B. 1.
Then, for the former type of inputs, 2; = (0) for all i E V. For the latter type of inputs, z; = a (1) for all i E V. Let A be arbitrary constant algorithm and C' be the number of queries A makes when we set = = [1(1) - (0)1/3. When A calculates the embedding u * U E V, the states of all nodes but are symmetrical until A makes a query about that node. Therefore, if n is sufficiently large, A does not make any query about e with high probability (i.e., at least (1 = )). If A does not make any query about v, the state of A is the same for both types of inputs. If the approximation error is less than for the first type of inputs, the approximation error is larger than for the second type of inputs by the triangle inequality and vice versa. Therefore, A fails to approximate the embeddings of either type of inputs with the absolute error of at most e.
20

---

Under review as a conference paper at ICLR 2020
Proof of Lemma 10 We consider the one-layer GCN whose activation function satisfies o + (0))
We use the following two types of inputs:
a star graph, where E the center of G, W 1, and all features are
G is a star graph, where v E V is the center of G, W 1, and the features of /2n leaf's are and the features of other nodes
Then, for the former type of inputs, 2; - (0). For the latter type of inputs, 2, - o(). Let A be arbitrary constant algorithm and C' be the number of queries A makes when we & [o(1)- (0)) When A calculates the embedding of u E V that x = 0, the states of all nodes but are symmetrical until A makes query about that node. Therefore, if n sufficiently large, does not make any query about with high probability (i.e., at least (1 ) If A does not make any query about v, the state AA is the same for both types of inputs. the approximation error is less than for the first type of inputs, the approximation error is larger than for the second type of inputs by the triangle inequality and vice versa. Therefore, A fails to approximate the embeddings of either type of inputs with the absolute error of most e.
We prove the following lemma to prove Proposition 11
Lemma 17. If Assumptions 1 holds true and is Lipschitz continuous, || l|2 and ||2!0 ll2 of the GAT model are bounded by a constant
L) 1,...,
Proof of Lemmal 17 We prove this by performing mathematical induction on the number of layers. The norm of the input of the first layer is bounded by Assumption 1. If || (1-1) ll and || ll2 are bounded for all V.
|| |l2 and || |l2 are bounded because h!!) and h are the weighted sum of zu (t-1) and zu (1-1) Therefore, || l|2 and || are bounded because Uj is continuous.
(4)
Proof of Proposition 17 We prove the theorem by performing mathematical induction on the number of layers L.
Base case: It is shown that the statement holds true for T. =
Because UL is Lipschitz continuous,
Vz., Ne h', 0, l/2 - 1'll2 < 0(E) - ||U2 h., 0) UL(2.. h', 0)12 <E.
(30)
Let Cu cxp(LEAKYRELU(a (w))) (0)) (0)) 2000 u])). Then,
( (L)
Σ
(0)
avuz (0)
WES(L)
(EN(v)
=00) deg(v) wEN(() deg(v)
eu
(0)
r(D)
Σ
Eneestn) Bu'
Σ EvEN(W) ew'
Zu
BESL)
Let 2g be the k-th sample S(L) and Xx = Eep Then,
[[Xa] N(v) uEN(()
Σ eu.
(31)
There exists constant > 0, C' > 0 such that for any input satisfying Assumption 1,
<< Xx C,
(32)
because || (0) ||2 22 2 w (0) F, and ())
(0) ||2 are bounded by Assumption 1. Therefore, if we
take (4( = ( log ) samples,
Pr( (L)
Cu
Nwv)
Σ eul 0(0) < 06))
KES
())(e)
21

---

Under review as a conference paper at ICLR 2020
by the Hoeffding's inequality and equations 31 and continuous in c O,
32
Because f(x) 1/2 is Lipschitz
Pr[
0(s)] S O
(33)
RLD EnESc Pa
N( E EMEN(N) Ca
Let
Yx
CxR.
(0) 10
((1) (v(EN(r) Ew
Then,
Σ
Cu
zu 0))
(34)
N(u)
EVENTiO ear
NEN(0) MO
There exists constant C" E R such that for any input satisfying Assumption 1,
| C
(35)
holds true because || ||2 are bounded, and c < leal < C. Therefore, we take r(4) = 0 samples,
Pr[l r(L)
Σ
Cu
(0)
EV'EN(O) Cul
aES(e)
deg(v)
Cu
(0)
12 2 S 5((8)
(36)
deg(
EVrEN(U) ew
(E.(())
(e
holds true by the Hoeffding's s inequality and equations
and
35 Therefore,
Pr[l
Σ
Cu
Zu
(())
pTzy Evesus ext
aES(2)
Σ uE.((o)
Cu (0)
12 2 0(e)] S (6)
(37)
deg(v) (T)
En'EN( Cw²
holds true by the triangle inequality and equations (33) and (36), and Pr[l Pr[l 2142 112 2 2 <
holds true by equations (30) and
(37).
Inductive step: is shown that the statement holds true for L = + 1 if holds true for
Because UL is Lipschitz continuous,
Vzu, hng h² 0, ||,, h'll2 0(s) [1,((Z, hv; 0) U2. 1/ 0)]
(38)
holds true.
Pr[l p(L) Σ
Cy Evesoo Oxl
2
(1-1)
wES(L)
F(l
En
(1-11)/2 2 0()) s 0
(39)
deg(u)
EveNTo Car
NEN()))
deg(v)
holds true by the same argument as the base step. If we take (()) (..,,,,(-,1111,, (l- 0( (log + +log ))) samples,
Pr[ll=((-1)) 2(1-1)112 0(E)] < 0(E6)
(40)
holds true by the induction hypothesis. Therefore, Prille! 2!'1|/2 2 E] < 5 holds true by
equations (38 (39.. and (40)
22

---

Under review as a conference paper at ICLR 2020
D COMPUTATIONAL MODEL ASSUMPTIONS
In this study, we model our algorithm as an oracle machine that can make queries about the input and measure the complexity by query complexity. Modeling our algorithm an oracle machine and measuring the complexity by query complexity are reasonable owing to the following reasons:
realistic setting, data stored in a storage or cloud and we may not be able to load all the information of huge network
the main memory. Sometimes the network is constructed for access to the information on demand (e.g., in web graph mining, the edge information is retrieved when queried). In such cases, reducing the number of queries is crucial because accessing storage or cloud is very expensive.
Our algorithm executes a constant number of elementary operations of O n) bits (c.g., accessing the O(n)-th address, sampling if we assume that these operations can be done in constant time, the total computational complexity of algorithms will be constant. This assumption is natural because most computers in the real-world can handle 64 bit integers at once and most of the network data contain less than 264 10a nodes.
element from (nn) elements). Therefore,
Even if the above assumption is not satisfied, our algorithm can be executed in Olog time in terms of the strict meaning of computational complexity. This indicates that our algorithm is still aub-linear and therefore it scales well. It should be noted that it is impossible to access even a single node in ollog n) time in the strict meaning of computational complexity because cannot distinguish n nodes with o(log n) bits. Therefore, our algorithm has optimal complexity with respect to the number nodes n.
E
GRAPH EMBEDDING
In this study, we model our algorithm as an oracle machine that can make queries about the input and measure the complexity by query complexity. Modeling our algorithm an oracle machine and measuring the complexity by query complexity are reasonable owing to the following reasons:
a realistic setting, data is stored a storage or cloud, and we may not able to load the main memory. Sometimes the network is constructed for access to the information on demand (e.g., in web graph mining, the edge information retrieved when queried). In such cases, reducing the number of queries is crucial because accessing storage or cloud is very expensive.
all the information of huge network
Our algorithm executes a constant number of elementary operations of O n) bits (e.g., accessing the ((n)-th address, sampling if we assume that these operations can be done in constant time, the total computational complexity of algorithms will be constant. This assumption is natural because most computers in the real-worid can handle 64 bit integers at once, and most of the network data contain less than 264 1029 nodes.
element from O(n) elements). Therefore,
Even if the above assumption is not satisfied, our algorithm can be executed in O time in terms of the strict meaning of computational complexity. This indicates that our algorithm is still sub-linear and therefore, it scales well. It should be noted that it is impossible to access even a single node in o(log n)) time in the strict meaning of computational complexity because cannot distinguish n nodes with olog n) bits. Therefore, our algorithm has optimal complexity with respect to the number of nodes n.
23

---

Under review as a conference paper at ICLR 2020
Table 2: Time complexity of embedding algorithms. A denotes the maximum degree. It should be noted that that in the dense graph, (m) = O by definition.
Sparse
Dense
Proposed
O Oztir (log + log " log 1)
Of (log _ + log 1) log }) O(mL) = O(n
Exact
F TIME COMPLEXITY
We summarize the time complexity of approximation and exact algorithms in Table Let B {v} and B = U. (u) [L = 0,....., L - 1). In other words, By- is the k-hop neighbors of node We need all features of Bo to calculate the exact embedding of node If the graph is sparse, the size of B,.- & grows exponentially with respect to k because deg(u) nodes are added to -++ for each node BL Namely, it is bounded by A If the graph is dense, B z V (1 S & S L) Therefore, complexity is linear with respect to the number of layers L and edges m. contrast, the approximation algorithm runs in constant time irrespective of the density of the input graph.
24


Reviews:
[{"review_id": "SyxRgpTntr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors provide a theoretical framework for characterizing the approximation guarantees provided by node sampling to estimate embeddings in various GNN architectures. In particular, they prove several PAC learning-style bounds on the embedding and gradient estimation when using node sampling approaches. They also observe that since the number of nodes selected for sampling is not dependent on the size of the graph, this amounts to a constant time operation for determining embedding and gradient estimates.\n\nImportantly, a variety of existing works have already proposed node sampling (“constant-time GNNs”), so the contribution of this work lies in the theoretical bounds. A moderate set of experiments suggests the empirical behavior follows the theoretical expectations.\n\nOverall (and described in the comments below), I believe this paper provides some interesting theoretical results for an approach that is widely-used in practice. However, I believe the title and abstract are misleading; this paper does not suggest some new sampling strategy; it only gives a theoretical approximation error for existing approaches and network architectures.\n\nComments\n\nWhile the authors do make this clear later in the paper, the contributions of this work are only the theoretical bounds; the node sampling algorithms have been proposed in existing work. Both the title and abstract are misleading.\n\nStill, the theoretical bounds do provide an interesting understanding of an approach which is commonly used in practice.\n\nIt would be helpful to give the intuition behind the assumptions and proofs. Currently, it is difficult for a non-expert to follow the reasoning and practical implications of much of this work.\n\nCurrently, it is not clear if these results are “constructive”, in the sense that they do not obviously suggest some new sampling strategy, etc. Of course, it is still interesting to characterize commonly-used practices, but one does wish the theory suggested, say, a better sampling strategy, etc.\n\nTypos, etc.\n\n“r”, the number of sampled nodes, is not defined in the main body of the paper.\n\nThe text in Footnote 1 is a little confusing, in that the text refers to approximating the embedding, while the text in the footnote describes a prediction problem. A reader could easily interpret this to mean that the error on the downstream prediction problem will be bounded (which is not what this work shows).\n\nThe text mentions that O_G (v,i) refers to the i^th “neighborhood” of v. Presumably, this should be “neighbor”.\n\n“we take” -> “We take”\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SylT42ubYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a constant-time approximation for graph convolution operation via theoretical analysis on the number of sampling from each neighbor. The authors prove that both node embedding and gradient can be approximated via constant number of samples among the neighbors. Extensive experiments are carried out to verify the correctness of the proposed bounds.\n\nStrength:\n1. The authors establish rigorous bounds on the number of required neighbors to sample to guarantee good approximation of the graph convolution operations. The bounds are established on both nodes embedding and gradients.\n2. The authors corroborate the theoretical results with extensive experiments. The experiments are carried under the case both when the assumption holds and not.\n\nWeakness:\n1. Though the bounds do not depend on number of nodes, it does have an exponential dependence on the number of layers. For common GCN with L=2, even \\epsilon = 0.1 requires more than 10^4 samples. As a result, the bound is less practical in providing guidance for real-world application. Moreover, the bound does not depend on the embedding dimension at all. Is this to be expected?\n2. The authors only provide constant bound for convolution on individual nodes. For the final metrics like classification accuracy, we need to guarantee good approximation for all node’s convolution. In this case, the bounds will definitely depend on number of nodes at least through the union bounds among all nodes.\n3. The proposed method is exactly the uniform neighbor sampling methods. There is little contribution on the methodology side from the paper. Also, it would be interesting if the authors could provide theoretical analysis for adaptive sampling methods as well.\n4. The authors provide in-approximability results under certain conditionals. However, uniform sampling methods works well empirically under this case as well. It would be better if the authors could explain the gap between theory and empirical performance.\n\nDetailed Comments:\n1. Algorithm 2, please define notation like O(v<-v).\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJl97FAk2r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Paper strengths:\n\n1. Overall it is a solid and well-written article. \n2. The interesting and novel part is the theoretical demonstration that a fixed number of neighbors can approximate well some algorithms in the literature (it approximates well w.r.t to the forward embedding produced by those algorithms and to the backward gradients in relation to the parameters), \n3.It also demonstrates that some algorithms are impossible to approximate in constant time.\n\nWeaknesses:\n\n1. They do not introduce a new method, the algorithm is message-passing in which not all the neighbors are considered - authors choose a fixed number of neighbors by sampling. This gives them constant time for the calculation of the embedding w.r.t to the number of neighbors\n\nMain points:\n\nOverall, the article is well supported theoretically and quite complete. They generally show that if the assumptions made are contradicted, the approximation becomes impossible.\n\nThe experiments seem quite well chosen for the cases studied. In general, the experiments in which authors want to show the impossibility of an approximation, are done exactly on the corner cases chosen for the theoretical demonstrations. However,  they also have experiments on real datasets, used in the literature.\n\nOther observations:\n\nIt is not very clear what do they mean by \"standardization layer from GCN\" which intervenes in several theorems.\n\nIt may have been good to show how accuracy varies relative to the chosen error. It is not very intuitive what an embedding approximation error of e = 0.01 means. For example, to have 0.1 error and 95% confidence I would have to choose 300 neighbors.... That seems to be a very large number, how practical is that?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There was some interest in the ideas presented, but this paper was on the borderline and ultimately not able to be accepted for publication at ICLR.

The primary reviewer concern was about the level of novelty and significance of the contribution. This was not sufficiently demonstrated.
Decision: Reject