Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters
Authors: Takanori Maehara
Hoang NT
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph parameters
Benjamini-Schramm convergence
random sampling
graph learning theory
graph classification
GNN

Abstract: Theoretical analyses for graph learning methods often assume a complete observation of the input graph. Such an assumption might not be useful for handling any-size graphs due to the scalability issues in practice. In this work, we develop a theoretical framework for graph classification problems in the partial observation setting (i.e., subgraph samplings). Equipped with insights from graph limit theory, we propose a new graph classification model that works on a randomly sampled subgraph and a novel topology to characterize the representability of the model. Our theoretical framework contributes a theoretical validation of mini-batch learning on graphs and leads to new learning-theoretic results on generalization bounds as well as size-generalizability without assumptions on the input.

Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters
Takanori Maehara Facebook AI London, United Kingdom tmaehara@fb.. com
Hoang NT Tokyo Tech & RIKEN AIP
Tokyo, Japan hoangnt&net. c. www.ch....cc.c......c ac
Abstract
Theoretical analyses for graph learning methods often assume a complete obser- vation of the input graph. Such an assumption might not be useful for handling any-size graphs due to the scalability issues in practice. In this work, we develop a theoretical framework for graph classification problems in the partial observation setting (i.e., subgraph samplings). Equipped with insights from graph limit theory, we propose new graph classification model that works on a randomly sampled subgraph and novel topology to characterize the representability of the model. Our theoretical framework contributes theoretical validation of mini-batch learn- ing graphs and leads to new learning- results on generalization bounds as well as sizalgenerllzzabiiiyy without assumptions on the input.
Introduction
Going beyond regular structural inputs such as grids (images), sequences (time series, sentences), or general feature vectors is an important research direction of machine learning and computational sciences. Arguably, most interesting objects and problems in nature can be described as graphs [37]. For such reason, graph learning methods, especially Graph Neural Networks (GNN) [60], have recently proven to be useful solution to many problems in computer vision [10, 12, 24, 63), complex network analyses [22, 30, 73], molecule modeling [17, 32, 41, 45], and physics simulations [3, 31, 54).
The significant value of graph learning models in practice has inspired a large amount of theoretical work dedicated to exploring their representational limits and the possibilities of improving them. Most notably, the representational capability of GNNs has been in the spotlight of recent years. To answer the question "Can GNNs approximate all functions on graphs?", researchers discussed universal invariant and equivariant neural networks [27, 40, 43, 51] as theoretical upper limits for neural architectures or showed the correspondence between message- saaaggeg GNNs (MP-GNNs) to the Weisfeiler-Leman (WL) algorithm [68] as practical upper limits [46, 70].
often impractical to keep the whole graph in the working memory. Therefore, practical graph learning methods often utilize neighborhood samplings [22, 73] or random walks [53] handle this scalability issue. Because existing analyses assumed complete observation of the input graphs [27, 51, 57]. it is unclear what can be learned we combine graph learning models with random samplings. Thus, the relevant question this scenario is "What graph functions are representable by GNNs when we can only observe random neighborhoods? This question adds another dimension to the discussion of GNN expressivity; even if we have powerful GNN (in both theoretical and practical senses), what kind of graph functions can we learn the input graphs are too large to be computed whole?
Given an extremely large graph an input,
Contributions This study proposes theoretical approach to address graph learning problems on large graphs by identifying a novel topology of the graph space. We discuss the graph classification
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

problem in the main part of the paper and extend the discussion to the vertex classification problem in Appendix C. The extension to vertex classification can be realised by viewing rooted-graph classification problem. We first introduce random ball sampling GNN (RBS-GNM) which is mathematical model of GNNs implementable in a random neighborhood computational model, and prove that the model is universal in the class of estimable functions (Theorem 4). Our main contribution is introducing randomized Benjamini- Schramm topology in the space of all graphs and identifying the estimability of the function as the uniform continuity in this topology (Theorem 7). By applying our main theorem, we obtain the following learning-theoretic results.
We show the equivalent of estimability and continuity (Theorems 4 and 7). This implies the continuity assumption a sufficient condition for the mini- batch learning on graphs.
We prove that the functions representable by RBS-GNNS are generalizable by showing an upper bound of the Rademacher complexity of Lipschitz graph functions (Theorem 10). We identify size-gen geberaeneall functions with estimable functions (Theorem 11). Then, by recognizing the sizegennraaizzatinn as a domain adaptation, we provide a -izeagenerllization error based on the Wasserstein distance (Theorem 13).
Unlike existing studies, which assumed a random graph model [26, 28] boundedness [11, 27, 51, 58), our framework does not assume anything about the graph class; instead, we assume the continuity of the graph functions. Our results listed above are model-agnostic, i.e., we only discuss the property of the function space, regardless of how GNN models are implemented. The model-agnostic nature of our results gives a systematic view to general graph parameters learning: their generality is especially useful as there are many different GNN architectures in practice [57, 69, 78).
2 Related Work
Large-scale GNNs The success of GNNs, especially vertex classification models like GCN [30] and GraphSAGE [22], has led to various large-scale industrial GNN systems (see [1] and references therein). Aiming to increase computational throughput while maintaining the predictive performance, most of these systems implemented fixed-size neighborhood sampling [22] to enable large-scale batching [23, 73, 76, 77J. GNNs have also been applied to the 3D point clouds classification problem [67], which translates computer vision problem the large graph classification problem, and the random sampling was empirically shown to be effective [35]. In this context, our work contributes a theoretical justification for the random sampling procedure.
Graph Parameter Learning Graph function, graph parameter, or graph invariant refer to (real or integer value) property of graphs, which only depends on the graph structure. other words, they are functions defined on isomorphism classes of graphs [37]. Determining graph properties from data has long been a topic of interest in theoretical computer science [8, 37] and an important machine learning task in computational chemistry [9, 17] and biology [6, 16]. Recently, GNNs have been proven successful on a wide range of graph learning benchmark datasets. Current literature analyzed their expressivity gain a better understanding of the architectures [27, 44, 51]. Several works identify MP-GNNs to the I-dimensional WL isomorphism test [70] and further improve the GNN architectures to more expressive variants such as k-dimensional WL [46], port-numbered message passing [58], and sparse WL [48]. GNNs are also linked to the representational power of logical expressions [2]. These theoretical results assumed the complete observation of the input graph; therefore, it is difficult to see to what extent these results would hold when the only partial observation is available. By studying the RBS-GNN model, we give answer this issue. We use GNNs because they are the most expressive graph learning methods [27, 70]. Nonetheless, our results generalize for other universal (Theorem 4) and partially-universal (Theorem 17) methods.
Generalization Besides expressivity, another challenge in graph learning is to understand the gener- alization bounds. Scarselli al. [61] introduced an upper bound for the VC-dimension of functions computable by GNNs, in which the output is defined on special supervised vertex. Garg et al. [15] derived tighter Rademacher complexity bounds for similar MP-GNNs by considering the local com- putational tree structures. Liao et al. [36] obtained generalization gap of MP-GNNs and GCNs [30] using PAC-Bayes techniques. Du et al. [11] obtained a sample complexity using a result in the kernel method for their graph neural tangent kernel model in learning propagation
functions. Verma and Zhang [66] obtained a generalization gap of single-layer GCNs by analyzing the stability and dependency on the largest eigenvalue of the graph; Lv [39] derived Rademacher bound for similar

---

GCN model with similar dependency. Keriven et al. [28] assumed an underlying random kernel (similar to graphons [37]) and analyzed the stability of discrete GCN using continuous counterpart c-GCN. They derived the convergence bounds by looking at stability when diffeonorphisms [42] are applied to the underlying graph kernel, the distribution, and the signals. All these methods placed some assumptions on the graph space; either bounded degree [15, 36, 39], bounded number of ver- tices [11, 61, 66], or graphs belong to a random model [28]. Therefore, all these results become either inapplicable or unbounded in the general graph space. Our Theorem 10 contributes a complexity bound without assumptions on the graphs.
Property Testing and Constant-Time Local Algorithms Property testing on graphs is task to identify whether the input graph satisfies a graph property or c-far from II [18]. Often a researcher in this area tries to derive algorithm whose complexity is constant (i.e., only depends c) or sublinear in the input size [56]. Several graph properties admit sub-linear (or constant-time) algorithms: the examples include bipartite testing, triangle-free testing, edge connectivity, and matching [49, 74). Recently, by bridging the constant-time algorithms and the GNN literature, Sato et al. [59] showed that, for each vertex, the neighborhood aggregation procedure of GNN layer (they called it "node embedding") can be approximated in constant time. However, this does not result in constant-time learning algorithm for GNNs because we still need access all the vertices to get the desired outputs. Our results provide the first "fully constant-time" GNNs in the sense that the whole learning and prediction process runs in time independent of the size of the graphs (Section 4).
Statistical Theory for Network Analysis Learning graph property from samples is traditional topic in statistical network analysis [14, 21, 34]. Klusowski and Wu [33] proved that it is hard to estimate the number of connected components using sublinear-size samples. Bhattacharya et al. [5] showed that the Horvitz-Thmmpson estimator for the number of subgraphs of constant size consistent and asymptotic normal if the fourth-moment condition holds. Our result is consistent with these results as the number of connected components is non-continuous and the number of motifs is continuous in the randomized Sunjamini-Schrame topology. These studies indicate future direction of this study; for example, the asymptotic normality and consistency of RBS-GNNs.
3 Preliminaries
3.1 Graphs
A (directed) graph G is tuple (V, E) E) of the set of vertices V and the set of edges E C CV V. We use V(G) for V and E(G) for E when the graph is unclear from the context. A graph is weakly connected if the underlying undirected graph has a path between any two vertices. A weakly connected component is a maximal weakly connected subgraph. Two graphs G and H are isomorphic if there is a bijection Φ (GG) + V(H) such that (ő(u), (()) E E(H) if and only if (u, v) E E().. Let be the set of all directed graphs. A ball of radius centered at v. (v) (also simply B). is the set of vertices whose shortest path distance from is bounded by r. For U S (G). G(U] is the subgraph of G induced by U.
A rooted graph (G, v) is graph G augmented with vertex v in V(G). The isomorphism between (G, v) and (H, u) is defined in the same way as for graphs with the extra requirement that maps e u. k-rooted graph (G,v1, UI,..., U&) is defined similarly. We often recognize the graph induced by the ball (v) as a rooted graph whose root is v and by the union of k balls as k-rooted graph.
Modern graph learning problems ask for a function p G - D from training data, where D is "learning-friendee
domain such as the set of real numbers I, a d'-imensional real vector space Q C IRC or some finite sets. In most cases, the function p is required to be isomorphism-invarian (or invariant for short). This notion of graph functions coincides with the definition of graph parameters. Another term used in the literature is graph property, which can be formalized as graph function whose co-domain is (0, 1}. Our work focuses on the case in which the co-domain is IR.
3.2 Computational Model
Extremely large graphs are usually stored in some complicated storage. Thus, there are some constraints on how we can access the graphs. In the area of property testing, such a situation is modeled by introducing a computational model, which is oracle for accessing the graph.
3

---

Importantly, each computational model induces topology on the graph space. As we will show in later sections, the ability to represent graph functions related to this topology.
There are three main computational models in the literature: the adjacency predicate model [20], the incidence function model [19], and the general graph model [25, 52]. The adjaceney predicate model, also known as the dense graph model, allows randomized algorithms to query whether two vertices are adjacent or not. With the incidence function model, also known the bounded-degree graph model, algorithms can query a specific neighbor of a vertex. The general graph model lets the algorithms ask for both a specific neighbor and for whether two vertices are adjacent; hence, this is the most realistic model for actual algorithmic applications [18].
In this study, consider the following random neighborhood model, which allows us access the input graph G via the following queries:
Sample
Sample vertex u E V uniformly randomly.
SampleNeighbor((G u): Sample a vertex e from the neighborhood of u uniformly randomly, where is an already obtained vertex.
IsAdjacent(G, u, v): Return whether the vertices u and e are adjacent, where u and v are already obtained vertices.
This model a randomized version of the general graph model. Czumaj al. [8] proposed a similar model to analyze edge streaming algorithms for property testing. However, their model does not have the IsAdjacent query, i.e., it is randomized version of the incidence function model. Note that the computational model naturally specifies the estimability of the graph parameters. More formally, we have the following definition of estimability with respect to our random neighborhood model.
Definition 1 (Constant- Time Estimable Graph Parameter). A graph parameter is constant-timg estimable on the random neighborhood model (estimable for short) for any >> there exists an integer N and randomized algorithm A in the random neighborhood model such that A performs at most N queries and A(GG) - p(G)] < 6 with probability at least 1 - for all graphs G E G.
Some examples of noon-)estimable graph parameters are:
Example 2. The number of vertices, min/max degree, and connectivity are not estimable. Example 3. The triangle density and the local clustering coefficient are estimable.
Additional examples of estimable graph parameters and experimental results are provided in Ap- pendix D. In the next section, implement GNN following the proposed random neighborhood computational model. By showing the connection between the GNN and algorithms in the random neighborhood model, we obtain several theoretical results in Section 5.
4 Random Balls Sampling Graph Neural Networks (RBS-GNN)
This section introduces RBS-GNN, theoretical GNN architecture based on the random neighborhood model. RBS stands for "Random Balls Sampling" and also "Random Benjamini- Benjamini-Schramm' because our random neighborhood model extends the topology of the Senjamini-Schrame Given an input graph, an RBS- EBS-GNN samples i random vertices and proceeds to sample random balls Bi..... B₁ rooted at each of these vertices. A random ball of radius r and branching factor is subgraph obtained by the procedure RandomBallSample, illustrated in Figure 1 for r 1 and The exact procedure is presented in Algorithm 1. It is trivial to see that RandomBall implemented under the random neighborhood model with SampleVertex and Nempheee
convergence [4].
can be
After sampling l random balls, the next step is identifying the induced subgraph Gi G U... Bx] using the IsAdjacent procedure and computing the weakly connected components Ci...., ONe of the induced subgraph (Step 3 of Figure 1). The classifier part of an RBS-GNN has two trainable components: multi-layer perceptron g and GNN f. The output of an RBS-GNN defined as
RBS-GNN(()) g (EN(C))
It should be emphasized that, as mentioned in the end of Section 2, our RBS-GNN can be evaluated in constant time (i.e., only dependent on the hyperparameters) because the subsets returned by RandomBallSample has constant size regardless of the size of input graph G.

---

B
Step 1: Sample random roots
Step 2: Sample random neighbors
Step 3: Get induced subgraphs connected components
Figure 1: Random Balls Sampling Procedure (Algorithm 1). Our computational model is different from the existing general graph model at Step 2, where we sample neighbors randomly instead of taking all neighbors. In Step 3, the randomly sampled edges are shown with color, and the induced edges are black. The weakly connected components C₁ and C2 are inputs to the GNN.
Algorithm 1 Randomized Benjamini-SShrame GNN
1: procedure SAANDOMBALLSAMPLEEE
b,
2: layer [0] + II. ...... layer + [
3: Sample random vertex from V(G) and insert layer(0)
4: for ,,..., do
5: for in Layerfi 1] do
6:
Sample b random vertices (with replacement) from (ux and insert to layer[i] 7: return G[layer(0) U Ua. Uayeer[r]]
8: procedure RBS-GNN f. b, b,
9: BI...., Bg + Random@BlllSampleeG..bb b,
b Runs & times to get k balls.
CI,..., f- ValkyyComeedeeCoooonnnnnCCCCCC U...BB))
11: return g 9(2, (CC))
Relation to Existing GNN Models While RBS-GNN is motivated by the random neighborhood model, it has strong connection with existing message-passing GNNs and optimization techniques in graph learning. When we select f to be a simple message-passing GNN, RBS-GNN is a generalization of the mini-batch version of GraphSAGE (Algorithm 2 in [22]), and the multi- layers perceptron module acts as the global READOUT as in the GIN [70] architecture. Our analysis technique also applies for other mini-batch approaches of popular graph learning models [30, 64, 65]. This result provides a theoretical validation for the mini-batch approach in practice. Note that this is a positive result for continuous graph parameters, and make no claim for the non-continuous case. On the other hand, f can also be more expressive variant such as high-order WL [48], k-treewidth homomorphism density, universal approximator [27, 51].
Main Result
In this section, we conduct theoretical analyses of RBS-GNN for the graph classification problem. All the proofs are in Appendix A. To simplify the analysis, we assume the hyperparameters k; b, and r have the same value, and by slight abuse of notation, we denote these values by r. Note that this setting would not alter the notion of estimability. We further simplify the discussion by assuming the graphs have no vertex features. Similar results hold when the vertices have unite-dimensional vertex features; see Appendix B. Additionally, mentioned in Section 1, obtained complementary results for the vertex classification problem in Appendix C.
5.1 Universality of RBS-GNN
We first characterize the expressive power of RBS-GNN. The following shows the universality of RBS-GNN with a universal GNN component f. in the space of the estimable functions.
Theorem (Universality of RBS-GNN). If a graph parameter p p: G + is estimable (in the random neighborhood model), then it is estimable by an RBS-GNN with universal GNN f.
5

---

[0]
Zz(G)
[0.
Algorithm 1
isomorphism classes
indicator vectors
Expectation
(LG)=B(Z(GG)) [0.5.0.5)
single root, radius
Distribution over Isomorphism classes
(8)
Zg [1,0]
Figure 2: An illustrating example for the r-profile with = 1, = 2, and a simple graph G.
The proof of this theorem is an adaptation of the proof techniques by Czumaj et al. [8]. We first introduce a canonical estimator, which is an algorithm the random neighborhood model defined by the following procedure. (1) Sample random balls ......, B, using FandomBallSample(G r, r); (2) Return number according to the isomorphism class of the subgraph G[B] U... U B,] induced by the balls. Since the number of random balls, the branching factor, and the radius are constant, we can see that the size of G U... U B,] is bounded by r*+2, Therefore, we can list all isomorphism classes of all graphs having at most r.* vertices and assign unique number to each of them. Also, since the induced subgraph bounded, is possible to construct a universal approximator GNN [27, 51J. Therefore, we obtained the following.
Lemma 5. If a graph parameter p is estimable, then it is estimable by canonical estimator.
Since a canonical estimator assigns number according to the isomorphism class of the input, we see that RBS-GNN BNS- can approximate the canonical estimator by letting f be a universal approximator for bounded graphs. See the proof in Appendix A. for more detail.
Relation to Universality Results Existing universal GNNs assumed that the number of vertices of the input graphs are bounded. Theorem 4 shows that these universal GNNs for bounded graphs can be extended to general graphs by approximating the general graphs using the random balls sampling procedure. As a drawback, the theorem is only applicable to the continuous functions in the randomized Benjamini Schramm topology introduced below. We emphasize that this drawback shows the limitation of the partial-observation (random neighborhoods) setting.
5.2 Topology of Graph Space: Estimability is Uniform Continuity
The previous section defined the estimability by the existence of an estimation algorithm. Such definition suitable for algorithmic analysis; however, it not suitable for further analysis, such as deriving the generalization error bounds. This section rephrases our estimability by the continuity in a new topology induced by a distance between two graphs
We start with a simple example in Figure The figure shows an input graph G consisting of two isolated vertices and one edge. For simplicity, Algorithm I only samples single ball (k = 1) with radius two (r = 2). This configuration let us obtain two isomorphism classes with equal probability: single vertex and single edge. Hence, the event which each isomorphism class is obtained from Algorithm can be represented by a two-dimensional vector. We denote this vector Z2()), which takes value [0, 1] when the single vertex is sampled and value [1, 0] when the single edge sampled. Clearly, this is a random vector whose expectation defines a distribution over the isomorphism classes with respect to the configuration of Algorithm 1. More generally, we can define the r-profile (G) and the corresponding isomorphism class distribution (G) for positive integer values of radius r.
For an integer r, an r-profile Z, of graph G is random variable of the (k-rooted)) isomorphism class G U ... B,), where each B, is obtained from RandomBallSampleeG. r, r). As r) produces graph of size at most r", we can identify (G) random inite-dimensional vector. Let (G) = (G) be the probability distribution over the isomorphism classes in terms of the k--rooted graph isoorphism, where the expectation is taken SampleVertex and SampleNeighbor. The sampling distance of two graphs is defined by
RandommallSamplleCC:
d
2' drr 2r (H)),
(2)
For simplicity, we let le

---

where drv is the total variation distance of two probability distributions given by drv (p.(p.9) q) = (1/2)]lp all1. It should be emphasized that the sampling distance allows us compare any two graphs even though they have a different number of vertices. We call the topology on the set of all graphs 9 induced by this sampling distance randomized Benjamini-Schrane topology. A graph parameter is defined to be uniformly continuous in the randomized Benjamini-Schramm topology by the followings.
Definition 6 (Uniform Continuity in the RBS Topology). A graph parameter p 9 - R (resp.
randomized algorithm A) is uniformly continuous if for any > 0 there exists 5 > 0 such that for any G and H, d(GG, H) 5 implies (p(G)- p(H) c (resp. [A(G) A(H) S with probability at least - c).
This topology connects the estimability in terms of the continuity follows.
Theorem 7. A graph parameter is estimable in the random neighhorhood model if and only if is uniformly continuous in the randomized Benjamini-Schramii topology.
The "if" direction of this theorem is given by the triangle inequality and the (optimal) coupling theorem [7]; the "only-if" is proved using the fact that the graph space is totally bounded follows. Lemma 8 (Totally Boundedness of Graph Space). For any e > O, there exists a set of graphs such that mingett.....oy d(G, Hj) S for all G.
{Hi...., Hc} with C < 220 O/1e 1/6)
Theorem 7 allows functions. We present such applications in Section 6.
apply existing "functional analysis techniques" analyze the estimable
Intuition of the Sampling Distance and Relation to Senjamini-Schramon Topology The intu- ition behind our definition of the sampling distance reflects the idea that two graphs are similar when random samples from these graphs look similar, where the similarities on small samples are more important to the similarities on large samples. This definition generalizes the Senjamini-Schramm topology for the space GD of all graphs of degree bounded by D, which uses a different definition of the "r-profile:" Let us define the r-profile by the union of r balls of radius whose centers are sampled randomly. Then, the sampling distance defined using this r-profile induces topology called the Senjamini-Schramn topology. This topology was first studied by Benjamini and Schramm [4] to analyze the planar packing problem, and now it widely used analyze the limit of bounded degree graphs, where the limit object is identified as the graphing; see [38]. A practical issue of the Benjamini-Schramm topology is that is only applicable to bounded degree graphs, where many real-world extremely large graphs are complex networks having power-law degree distributions (i.e.. unbounded degree). We addressed this issue by introducing the randomized Benjamini-Schrane Schramm topology, which is applicable to all graphs
6 Theoretical Applications
6.1 Robustness Against Perturbation
The continuity immediately implics the robustness against the structural perturbation, i.c., for any >> 0 there exists 8 > 0 such that the output of RBS-GNN does not change more than if the graph is perturbed at most in the sampling distance. As the perturbation in sampling distance may not be intuitive in practice, we here provide a bound regarding the additive perturbation edges.
Proposition 9. Let G be a graph and let G' be the graph obtained from G by adding (VV edges completely randomly where 0
1. Then d(G, G') = (o)/)))))/)
This result indicates that to change the output of RBS-GNN, one needs to add linearly many random edges; it is impractical in extremely large graphs. Note that the "adversarial" perturbation can change the distance more easily, especially there is a "hub" in the graph; see Appendix A.3 for details.
6.2 Rademacher Complexity
Thus far, we only discussed the expressibility of the functions regardless of the learnability. Here, we derive the Rademacher complexity for the class of Lipschitz functions the random Benjamini- Schramm topology. This gives an algoribmm-independent bound of the learnability of the functions.
7

---

Theorem 10. Let n. be the number of training instances. The Rademacher complexity Rr of the set of O(1/ log log log log x), is o(1 log log log n))
1 L-iipschitz functionn that maps to [0. 1] is (log lo (
This result implies that, by minimizing the empirical error of n instances, we can achieve the generalization gap of o(1/ log log log n. with high probability. To the extent of our knowledge, this is the first Rademacher bound for the general graph space, which guarantees the asymptotic convergence on any graph learning problem without assuming any graph structure.
Comparison with Existing Results The significant difference between existing studies [11, 15, 36, 39, 61, 66] and our bound (Theorem 10) is that ours is independent of any structural property, such as the maximum number of vertices, the maximum degree, and the spectrum of the graphs. Thus, ours can be applied to any graph distribution. Simply put, this is consequence of the totally boundedness of the graph space (Lemma 8): For any e > O, the space of all graphs is approximated by finitely many graphs; hence any graph parameter is bounded by the values among them, which is constant depending on e. The drawback of this generality is its poor dependency on the number of instances n, which leaves significant room for quantitative improvement. One possible way improve the bound is by assuming some properties of the graph distribution because the above derivation is distribution-agnostii;;; concrete strategy for improvement is left for future works.
6.3 Size-Generalizability
One interesting topic of GNNs is size- tete-gennrulizatinn, which is property that a model trained on small graphs should perform well on larger graphs. lize-generalizztion is observed in several tasks [29]; however, it has also been proved that some classes of GNNs do not naturally generalize [72]. Hence, we want to know about the conditions for GNNs to generalize.
We need to distinguish the "approximation -hhooretit""""""" size- size-generalle size-ennrralizabliity and the "learning-thooretie" lizzggeneralizabiity. The former is the possibility of size-generalization, which is proved by showing the existence of sezeegeneralizing models. This, however, does not mean that a size-generalizable model is obtained by training: thus, need to introduce the latter. The latter is the degree of size- generalizability when we train model using a dataset (or a distribution); it is proved by bounding the generalization error.
6.3.1 Approximation Theoretic Sieeaaannrllizabbliiyy
We say that function p is size-generalizatee in approximation- -theoreticc sense if for any >> O, there exists N > such that we can construct an algorithm using dataset (p(GGe)) G<N): [V(GgN)] < N} such that Ip()) A(G)) S c with probability at least 1 - c for all G E g. This gives one mathematical formulation of the size-generalizabiiity as it requires to fit algorithm A to all graphs using the dataset of bounded graphs. In this definition, we have the following theorem.
Theorem 11. Estimable functions size-genenn generalezrlleee in the
cittimmmattiot-hoetttt sense.
This theorem is proved by constructing a size- -eeereenealli algorithm. We first pick the continuity constant 5 for e using Theorem 7. Then, we construct a 6-net using Lemma 8. By storing all the values P(,,) for the graphs in the 8-net, obtain size-ennerllizalle algorithm, where N is the maximum number of the vertices in the 6-net.
6.3.2 Learning-Theorres Size-Generalizability
From the learning theoretic viewpoint, size- lizzegeneralizztionn is domain adaptation from the distribution of smaller graphs to the distribution of larger graphs [72]. Thus, it is natural to utilize the domain adaptation theory [55]. Especially since we have introduced the sampling distance defined on all pairs of graphs irrelevant to their sizes, we here employ the Wasserstein iittance-based approach [62].
We start from a general situation. Let D, and D2 be joint distributions of graphs and their labels, and Gi and G2 be the corresponding marginal distributions of graphs. We abbreviate E, and Eg for the expectations on D, and D2, respectively. The Wasserstein distance between G1 and Go is given by
((9,, G2) inf E(G. dGi,, G2),
(3)
8

---

where d is the sampling distance of the graphs, and т runs over the couplings between these distributions. Let X = inf, [E, h(G)) + y h(G)] be the optimal combined error, where inf, runs over all 1-Lipschitz functions. We have the following lemma.
Lemma 12. For any 1 1-I.isschitz functions h and hi' we have the following.
Eiyy f(G)) - Ealy f(G) + 2W 92) + X,
(4)
Combining this result with the Rademacher complexity (Theorem 10), we obtain the following generalization bound.
Theorem 13. Let c > O. Let (y21, G2n),.... (y2n: G2n) be independently drawn from D2. If
A = (e) and n 2 22000/0 then, for any
h, we have
1 B(G llur h1(
U2a h(G2x)) + 2W D2) (c)
(5)
72 1=1
with probability at least 1-
The condition A= O(e) requires the existence of "consistent rule" among both Dj and D2. For example, this condition holds when the labels are generated by y = [(G) + (0, 1) for some 1-Lipschitz function J. where (N 1) is the standard normal distribution. We can obtain the size- generalization bound by applying the above theorem for the distribution of large graphs G1 and of small graphs G2. Thus, we only need to evaluate their Wasserstein distance. The Wasserstein distance can be large in the worst-case; thus, we here consider concrete examples of graph distributions.
First, consider the case that undirected graphs drawn from the configuration model of d-regular graphs. In this model, a graph is constructed by the following procedure: (1) It creates N vertices with d half-edges; (2) Then, it pairs the half-edges and connects them obtain edges. We that learning problem on this distribution is size- nnee-gnneralizbbe.
Proposition 14, Let G be a distribution of random d- d-regular graphs generated by the configuration model, and GEN be the distribution conditioned on only graphs of size bounded by N. If N (log 1/e) 101g 1/c) then W(G,g<D) = O(e).
This result can be generalized to general distribution of graphs with large girth. Next, we consider
the case where undirected graphs are drawn from a graphon. A graphon W is a function W: [0, 1] x [0, 1] [0, 1]. A graph G is drawn from W if we first draw N random numbers T1, .i......1 EN E [0. 1] uniformly randomly. Then, for each pairs (Ii, xz)) we put an edge with probability W(r,, This model extends Erdos-Reny' random graph and stochastic block model; see [37] for more detail.
Proposition 15. Let W be graphon. Let N₁ and N₂ be integers with Ni N2. Let GN, be distribution of graphs of N; vertices drawn from W. If N1 2 2011/2) then W W(N,, GN.)) S.e
Finally, we consider the case that V is obtained from D by the metric projection. Let II be the projection onto the space of graphs of size at most N, i.e IIG)) = wrgningw:/vicww
G
Proposition 16. Let 9 be any graph distribution and let G&N = TT() be the projected distribution of graphs of size at most N. For any > 0, there exists N such that (GN) S
drawback of this result is that an explicit bound of N is not known, even for its deterministic variant in the bounded degree graphs (See Proposition 19.10 in [37]). The only known bound is for the bounded degree graphs with large girth [13].
Comparison with Existing Results Size-generalization of GNNs reported on several tasks, but its theoretical analysis is limited. Yehudai et al. [72] studied the teeegeealllizbbllity using the concept of d d-pattern, which is information obtained from d-ball; is similar to our r-profile. Their results are approximation- -etorortttteorticcccco as they showed the (non-) jexistenete of size- size-generalizable models but did not show how such models can be obtained by training on data. Xu et al. [71] proved the size-generalization of the max-degree function under several conditions on the training data and GNNs. Their result is essentially an approximation-theoreee spans certain space that is sufficient to identify the max-degree function.
as it assumes the dataset lies and

---

6.4 Partially-Universal RBS-GNNs
Thus far, we assumed the universal GNNs are plugged into the RBS-GNNG for theoretical analysis. This assumption achieves the maximum expressive power in this framework; however, in practice, we often use expressive but more efficient GNNs such as GCN [30]. GIN [70], or GAT [64]. Here, we discuss what will be changed if we made this modification.
Let be equivalence relation graphs. We assume that is consistent with the weakly connected component decomposition, i.e., if G1 = H1 and G2 = H2 then G1 + G2 = H₃ + H2, where the "+" symbol denotes the disjoint union of two graphs. We say that a function h (resp. randomized algorithm A) is E-indistinguishable if (G) = h(G') (resp. A(G) = A(G') given the random sample) for all G G'. A GNN is E-universal if it can learn any =-indistinguisaabl functions. For example, it is known that GIN is universal with respect to the WL indistinguishable functions [70]. Let RBS-BBGGN [ be a class of BES-GNNs that uses an uuuiverssl GNN f in Equation (1). The following shows the partial universality of this architecture.
Theorem 17. If f is estimable and iniiisiinguiihabeee then is estimable by an RBS-GNN/S
One application of this theorem is extending the expressivity of GraphS to the partial observation setting. GraphSAGE can represent the local clustering coefficient if we have the complete observation of the graph [22, Theorem IJ. We can prove the local clustering coefficient is estimable (Proposition 24
in Appendix D). By applying Theorem 17 to the equivalence relation G1 G2 defined by f(Gr) f f(G2) for all function f representable by GraphSAGE, we obtain the following.
Proposition 18. The mini- -btch version of the GraphSAGE (Algorithm [22]) can estimate the local clustering coefficient.
Comparison with Existing Studies Equivalence relations associated with GNNs are mainly studied in the context of the "limitation" of GNNs: If a GNN is -indistinguushable then it cannot learn any function h that is non E-indistinguishable. Morris et al. [46] proved message-passing type GNN cannot distinguish two graphs having the same d- d-patterns. Garg et al. [15] identified indistinguishable graphs of several GNNs, including GCN [30], GIN [70], GPNGNN [58], and DimeNet [32].
On the other hand, we should use non- non-universal GNNs in practice because more expressive GNNs have higher computational costs (e.g., universal GNNs [27] is more costly than the graph isomorphism test). We here considered RBS- [BS--NN[=]] because =uuiiversal GNNs are theoretically tractable classes of non-universal GNNs. With similar motivation, [51] proposed GNNs parameterized by information aggregation pattern and proved the =-universality, where = is induced by the aggregation patterns.
Conclusion
We answered the question "What graph functions are representable by GNNs when we can only observe random neighborhoods?" by proving the functions representable by RBS-GNNs coincides with the estimable functions in the random neighborhood model, which is equivalent to the uniformly continuous functions in the randomized Senjamini-Schrane
topology. The word "(Some)" in our title was meant to emphasize the restriction to continuous graph functions. The result holds without any assumption
the input graphs, such as the boundedness. This result gives a "functional analysis view" of graph learning problems and leads to several new learning-theol theoretic results. The weakness of our result is the poor dependency trade-off for generality. We believe addressing this issue will be an interesting future direction. Another future direction links to the asymptotic behaviors of RBS-GNNs Motivating example includes the motif counting problem, in which Bhattacharya et al. [5] proved the Horvitz- -hhoitz- estimator is consistent and asymptotically normal. A corresponding result for the RBS-GNN will allow us to obtain a confidence interval of an estimation and to perform statistical testing.
the number of training instances, which is the
Potential Impact Our work contributes an understanding of general graph learning models whose inputs are random samples of arbitrarily large graphs. Due to the theoretical nature of our results, we believe there will not be a direct nor indirect negative societal impact.
Acknowledgement We would like to thank the anonymous reviewers and the area chairs for their thoughtful comments which help us improve our manuscript. HN is partially supported by the Japanese Government MEXT SGU Scholarship No. 205144.
10

---

References
[1] Sergi Abadal, Akshay Jain, Robert Guirado, Jorge López-Alonso, and Eduard Alarcón. Com- puting Graph Neural Networks: Survey from Algorithms to Accelerators. ArXiv preprint, abs/2010.00130, 2020. URL http:////aawvvoo///aaae/
00130.
[2] Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The Logical Expressiveness of Graph Neural Networks. In 8th International Confer- Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[3] Peter W. Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and Koray Kavukcuoglu. Interaction Networks for Learning about Objects, Relations and Physics. In Advances in Neurul Information Processing Systems 29: Annual Conference on Neural Infor- mation Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 4502-4510, 2016.
[4] Itai Benjamini and Oded Schramm. Recurrence of Distributional Limits of Finite Planar Graphs. In Selected Works of Oded Schramm, pages 533-545. Springer, 2011.
[5] Bhaswar B Bhattacharya, Sayan Das, and Sumit Mukherjee. Motif Estimation via Subgraph Sampling: The Fourth Moment Phenomenon. The Annals of Statistics, To Appear, 2021.
[6] Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein Function Prediction via Graph Kernels. Bioinformatics, 21: 47-56, 2005.
[7] Juan A Cuestaalbertos, Ruschendorf, and Araceli Tuerodiaz. Optimal Coupling of Multivariate Distributions and Stochastic Processes. Journal of Multivariate Analysis, (662)):35-361, 1993.
[8] Artur Czumaj, Hendrik Fichtenberger, Pan Peng, and Christian Sohler. Testable Properties in General Graphs and Random Order Streaming, ArXiv preprint, abs/1905.01644 2019, URL https://arxil:
org/ aa//ab//1999 /905. 01644.
[9] Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Peructure-Activvie Relationship of Mutagenic Aromatic and Heteroaromatic Nitro Compounds: Correlation with Molecular Orbital Energies and Hydrophobicity. Journal of Medicinal Chemistry, (4(2):786-797 1991.
[10] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, NeurIPS 2016, December 5-10, 2016, Barcelona, Spuin, pages 3837-3845, 2016.
[11] Simon S. Du, Kangcheng Hou, Ruslan Salakhutdinov, Barnabás Póczos, Ruosong Wang, and Keyulu Xu. Graph Neural Tangent Kemel: Fusing Graph Neural Networks with Graph Kernels. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 5724-5734, 2019.
[12] Matthis Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. SplineCNN: Fast Geometric Deep Learning With Continuous B-Spline Kernels. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pages 869-877. IEEE Computer Society, 2018
[13] Hendrík Fichtenberger, Pan Peng, and Christian Sohler. On Constant-Sinn Graphs That Preserve the Local Structure of High-Girth Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, volume 40 of L.Ples, pages 786-799. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2015.
[14] Ove Frank. Estimation of Graph Totals, Scandinavian Journal of Statistics, pages 81-89, 1977.

---

[15] Vikas K. Garg, Stefanie Jegelka, and Tommi S. Jaakkola. Generalization and Representational Limits of Graph Neural Networks. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 1430-333. PMLR, 2020.
[16] Thomas Gärtner. A Survey of Kernels for Structured Data. ACM SIGKDD Explorations Newsletter, 5(1):49-58) 2003.
[17] Justin Gilmer, Samuel S. Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, August 6-11, 1, 2017, volume 70 of Proceedings of Machine Learning Research, pages 1263-1277 PMLR, 2017.
[18] Oded Goldreich. Introduction to Testing Graph Properties. In Property Testing, pages 105-141. Springer, 2010.
[19] Oded Goldreich and Dana Ron. Property Testing in Bounded Degree Graphs. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, pages 406-415, 1997.
[20] Oded Goldreich, Shari Goldwasser, and Dana Ron. Property Testing and Its Connection to Learning and Approximation. Journal of ACM, 45(4):653-750, 1998.
[21] Leo A Goodman. On the Estimation of the Number of Classes in a Population. The Annals of Mathematical Statistics, 20(4):572-579, 1949.
[22] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA. pages 1034, 2017.
[23] Zhihao Jia, Sina Lin, Mingyu Gao, Matei Zaharia, and Alex Aiken, Improving the Accuracy, Scalability, and Performance of Graph Neural Networks with ROC. In Proceedings of Machine Learning and Systems 2020, MLSys 2020, Austin, TX, USA, March 2-4, 2020. MLSys.org, 2020.
[24] Michael Kampffmmeyer Yinbo Chen, Xiaodan Liang, Hao Wang, Yujia Zhang, and Eric P. Xing. Rethinking Knowledge Graph Propagation for Zero-Shot Learning. In 2019 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, IEEE Computer Society, 2019.
2019, pages 11487-11496
[25] Tali Kaufman, Michael Krivelevich, and Dana Ron. Tight Bounds for Testing Bipartiteness in General Graphs. SIAM Journal on Computing, 33(6):1441-144) 2004.
[26] Tatsuro Kawamoto, Masashi Tsubaki, and Tomoyuki Obuchi. Mean-Field Theory of Graph Neural Networks in Graph Partitioning. In Advances in Neural Information Processing Sys- tems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 4366-4376, 2018.
[27] Nicolas Keriven and Gabriel Peyré. Universal Invariant and Equivariant Graph Neural Networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 7090-7099, 2019.
[28] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and Stability of Graph Convo- lutional Networks on Large Random Graphs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, Virtual, 2020.
[29] Elias B. Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning Combinatorial Optimization Algorithms over Graphs. In Advances in Neural Information Processing Syx- tems 30: Annual Conference on Neural Information Processing Systems 2017, NeurIPS 2017, December 4-9, 2017, Long Beach, CA, USA, pages
2017.
12

---

[30] Thomas N. Kipf and Max Welling. Semi- Sami-Supervised Classification with Graph Convolutional Networks. In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017. OpenReview.net, 2017.
[31] Thomas N. Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard S. Zemel. Neural Relational Inference for Interacting Systems. In Proceedings of the 35th International Conference on Machine Learning, ICMI. 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 2693-2702. PMLR, 2018.
[32] Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional Message Passing for Molecular Graphs. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[33] Jason M Klusowski and Yihong Wu. Estimating the Number of Connected Components in Graph via Subgraph Sampling. Bernoulli, 26(3):1335-1664, 2020.
[34] Eric D Kolaczyk and Gábor Csárdi. Statistical Analysis of Network Data with R, volume 65. Springer, 2014.
[35] Itai Lang, Asaf Manor, and Shai Avidan. SampleNet: Differentiable Point Cloud Sampling. In 2020 IEEE Conference Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 7575-7585. IEEE Computer Society, 2020.
[36] Renjie Liao, Raquel Urtasun, and Richard Zemel. A PAC-Bayesian Approach to General- ization Bounds for Graph Neural Networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual, April 25-29, 2021. OpenReview.net, 2021.
[37] László Lovász. Large Networks and Graph Limits. American Mathematical Society, 2012.
[38] László Lovász and Balázs Szegedy. Limits of Dense Graph Sequences. Journal of Combinatorial Theory, Series B, 96(6)6933-99)) 000339977722 2006.
[39] Shaogao Lv. Generalization Bounds for Graph Convolutional Neural Networks via Rademacher Complexity. ArXiv preprint, abs/2102.10234, 2021. URL 10234.
[40] Takanori Machara and Hoang NT. A Simple Proof of the Universality of Invarian//Equivariant Graph Neural Networks. ArXiv preprint, abs/1910.03802, 2019. URL https://arxiv org/ abs/1910. 198000000.000.....
[41] Pierre Mahé and lean-Philippe Vert. Graph Kernels Based on Tree Patterns for Molecules. Machine Learning, 75()):3335, 2009.
[42] Stéphane Mallat. Group Invariant Scattering, Communications on Pure and Applied Mathemat- ics, 65(10): 1331-1193311999 2012.
[43] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2153-2164, 2019.
[44] Haggai Maron, Heli Ben-Hamin Nadav Shamir, and Yaron Lipman. Invariant and Equivariant Graph Networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[45] Andreas Mayr, Günter Klambauer, Thomas Unterthiner, and Sepp Hochreiter. DeepTox: Toxicity Prediction using Deep Learning. Frontiers in Environmental Science, 3:80, 2016.
[46] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, January 27 February 1, 2019, pages
AAAI Press, 2019.
13

---

[47] Christopher Morris, Nils M. Kriege. Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A Collection of Benchmark Datasets for Learning With Graphs. In ICMI. 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
URI. www. www.ggraaaaaanngg... io.
[48] Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and Leman Go Sparse: To- wards Scalable Higher-order Graph embeddings. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, Virtual, 2020.
[49] Huy N. Nguyen and Krzysztof Onak. Constant-Time Approximation Algorithms via Local Improvements. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 327-336. IEEE Computer Society, 2008.
[50] Hoang NT and Takanori Maehara. Revisiting Graph Neural Networks: All We Have is Low-pass Filters, ArXiv preprint, abs/ has//995.09555 0095000 2019. URL httpp::///atttite org/ //tp///////// 20aa//990 1905. 09550.
[51] Hoang NT and Takanori Maehara. Graph Homomorphism Convolution. In Proceedings of the 37th International Conferencee on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7306-7316 316. PMLR, 2020.
[52] Michal Parnas and Dana Ron. Testing the Diameter of Graphs. Random Structures & Algorithms, 2052)11 2002.
[53] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. DeepWalk: Online Learning of Social Representations. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014, New York, NY, USA, August 24-27, 2014, pages 701-710. ACM, 2014.
[54] Tobias Pfaff, Meire Fortunato, Alvaro Sanchez-Gonzalez, and Peter W Battaglia. Learning Mesh-Based Simulation with Graph Networks. ArXiv preprint, abs/2010.03409, 2020. URL https://arxiv org/ abs/2010 03409.
[55] levgen Redko, Emilie Morvant, Amaury Habrard, Marc Sebban, and Younes Bennani. Advances in Domain Adaptation Theory. Elsevier, 2019.
[56) Ronitt Rubinfeld and Asaf Shapira. Sublinear Time Algorithms. SIAM Journal on Discrete Mathematics,
2011.
[57] Ryoma Sato. A Survey on the Expressive Power of Graph Neural Networks. ArXiv preprint, abs/2003.04077 04078, 2020. URL https: //arxiv...vv/////////i org/abs abo//003. 22200000078.... 04078.
[58] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation Ratios Graph Neural Networks for Combinatorial Problems. In Advances in Neural Information Processing Syy- tems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 4083 4092, 2019.
[59] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Constant Time Graph Neural Networks. ArXiv preprint, abs/1901 1077668..888, 2019. URL https: h/tp://aaavvvvo/// org/ abss/1911.. 00tp/99.00788..
[60] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Neiworks, 20(1):61-80, 2008.
[61] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The Chenin-Cherrssseniis Dimension of Graph and Recursive Neural Networks. Neural Networks, 108:248-228 259, 2018.
[62] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein Distance Guided Representation Learning for Domain Adaptation. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, AAAI 2018, New Orleans, LA, USA, February 2-7, 2018, pages 4058- 4065, AAAI Press, 2018
14

---

[63] Diego Valsesia, Giulia Fracastoro, and Enrico Magli. Learning Localized Generative Models for 3D Point Clouds via Graph Convolution. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[64] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Attention Networks, In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018. OpenReview.net, 2018.
[65] Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep Graph Infomax. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[66] 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 and Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 1539-
1548. ACM, 2019.
[67] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic Graph CNN for Learning on Point Clouds, ACM Transaction on Graphics, 38(5), 2019.
[68] Boris Weisfeiler and Andrei Leman. The Reduction of a Graph to Canonical Form and the Algebra which Appears Therein. NTI, Series, 2(9):12-16, 1968.
[69] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
[70] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[71] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual, April 25-29, 2021. OpenReview.net, 2021.
[72] Gilad Ychudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From Local Structures to Size Generalization in Graph Neural Networks. ArXiv preprint, abs/2010.08853. 2020. URL https: //arxiv...i/////// .rgg abs /0000. 088533.
[73] 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 and Data Mining, KDD 2018. London, UK. August 19-23, 2018, pages 974-983 ACM, 2018.
[74] Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. An Improved Constant-Tima Approximation Algorithm for Maximum Matchings. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, page 225-234 New York, NY, USA, 2009. ACM.
[75] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander Smola. Deep Sets. Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, NeurlPS 2017, December 4-9, 2017, Long Beach, CA, USA, pages 3391-3401, 2017.
(76) Dalong Zhang, Xin Huang, Ziqi Liu, Zhiyang Hu, Xianzheng Song, Zhibang Ge, Zhiqiang Zhang, Lin Wang, Jun Zhou, Yang Shuang, et al. AGL: A Scalable System for Industrial- purpose Graph Machine Learning. ArXiv preprint, 0bs/2003.024554 2020. URL. https: //arxiv. org/ abs/ 2203. 02454.
15

---

[77] Da Zheng, Chao Ma, Minjie Wang. Jinjing Zhou, Qidong Su, Xiang Song. Quan Gan, Zheng Zhang, and George Karypis. DistDGL: Distributed Graph Neural Network Training for Billion- Scale Graphs. ArXiv preprint, abs/2010.053377, 2020. URL https: http://axxvvv.rooe wwwp.ii.rrg/bb///110. 05337.
[78] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang. Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph Neural Networks: A Review of Methods and Applications. Al Open, 1:57-81, 2020.
16


Reviews:
[{"review_id": "VyYqn0av6tf", "reviewer": "Reviewer_VmDC", "summary": "The paper proposes to use randomly sampled subgraphs from a large graph to estimate the function value computed from the entire graph. The paper has done extensive theoretical analysis using the \"randomized Benjamini–Schramm topology\". The model also has analyzed learnability issues when estimating these functions. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n+The main problem addressed in this paper is the estimation of graph functions through sampling neighborhoods on the graph. This paper seems to be the first theoretical analysis of this problem. This problem is related to two problems. The first one is the estimation of a value of a large graph (e.g. the average degree) through sampling, which is a traditional problem. The second problem is the analysis of GNNs generalizing to different sizes of graphs. \n\n+Using the \"randomized Benjamini–Schramm topology\" brings a new technique to the area is another contribution of the submission. \n\nWeaknesses\n\n-The problem studied in this paper is unrealistic. The introduction says the motivation is the learning problem where the input is a huge graph and the output is a single value. At least I don't know such a problem exists: we don't have thousands of social networks and need to classify them. The experiment in the appendix does not use any data supporting the motivation. Actually, the experiment samples tiny graphs, all of which does not have computation or memory issues. \n\n\n-The function to be estimated is unknown, so we are not sure whether it is estimable. Particularly, the learned model as a function is not necessarily estimable. For example, we can use the learning model to estimate the maximum degree. Therefore, it is unknown where the analysis is applicable. \n\n-By reading this submission, I have a feeling that it overly claims the contribution. For example, the title put parenthesis over \"some\". Do you mean \"some\" can be removed? Also, line 270:  \"... guarantees the asymptotic convergence on any graph learning problem without assuming any graph structure.\" I believe \"any graph learning problem\" is not true: it is limited to the estimable functions. There are also other cases. \n\n-There should be a more thorough introduction of the literature. There is plenty of work on randomized testing graph properties or computing graph parameters. Not all of them are based on \"randomized Benjamini–Schramm topology\" -- why this topology is advantageous? \n\nNevertheless, I still think the research carries value, but the authors may want to find the scenario for the analysis. For example, are there any learning problems that have prior knowledge that the unknown function is estimable?  \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential negative societal impact is known. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns were detected. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "MERRkPSnaYw", "reviewer": "Reviewer_2yke", "summary": "To take the words of the authors directly, this paper answers the question \"What graph functions are representable by GNNs when we can only observe random neighborhoods?\" In answering this question, the authors consider a notion of an estimable function in a random neighborhood model, which they then show is equivalent to uniform continuity in a metric topology, which they dub the randomized Benjamini-Schramm topology. With this perspective in hand, they show that sufficiently powerful graph neural networks coupled with universal approximators are capable of estimating uniformly continuous functions in this topology. They then discuss implications of this in terms of robustness, sampling complexity, and generalization.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I will begin by discussing the strengths of this paper, then move on to the weaknesses, followed by some brief comments.\n\n**Strengths**\n\n1. This paper is very well-presented. Although its contents are technically demanding, the results are presented in such a way that lends to easy understanding. Despite this paper being somewhat outside of my main research area, I found it to be not too difficult to digest. The authors should be applauded for refraining from using extremely fancy machinery to convey their results, which is all-too-tempting in papers like this. Because of this, I think this paper is of broad interest to the graph learning community.\n\n2. The approach taken by this work is quite general. As the authors point out, it makes essentially no assumption on the graph structure itself, only demanding that the function to be estimated is estimable under their sampling model. Related to this is the simplicity of their approach: although they study estimation under a specific random ball sampling algorithm, the RBS-GNN is not particularly exotic. That is to say, the results presented are apparently applicable in many contexts, as discussed in Section 6.4, where weaker classes of GNNs are considered.\n\n3. The problem studied is quite relevant: there is great interest in applying graph neural networks approaches to huge graphs, with many approaches dedicated to ways to split graphs up or sample them in clever ways to avoid storing a humongous data structure. This paper offers a nice set of results for this particular problem, which will be useful to practitioners in understanding what constitutes an \"estimable\" parameter and what sampling strategies should work.\n\n4. The proposed random Benjamini-Schramm topology seems to be novel.\n\n**Weaknesses**\n\n1. Although the authors admit this, the generality of their approach leads to some issues with bounds having poor dependance on the graph size and estimation accuracy. This is addressed briefly in a few places, but it would have been nice to see some more concrete examples regarding this. For the benefit of the research community, this addition would ground this work in practice better.\n\n3. The main paper does not show any empirical validation of the ideas in the paper. I do understand that this is primarily a theoretical paper, but the fact that a specific sampling method was studied motivates the inclusion of some empirical results. I did see that there are some in the supplementary material, which is appreciated, but these were somewhat weak in my opinion. The RBS-GNN clearly underperformed relative to competing approaches, which is understandable given the limited observation scheme. However, I would have liked to see a comparison with other neural approaches that sample subgraphs for the purpose of embedding.\n\n4. Despite my aforementioned appreciation of the presentation of this work, there are a few things that could use a bit more explanation. I list these below.\n\ni. Section 5.2. When defining the sampling distance, a few things stick out to me. First, the explanation of an $r$-profile is unclear: I am not sure what this distribution is meant to look like. I see that there is some randomness that comes up due to the random ball sampling, but how this translates to a random vector is not explained very well. Given that the metric topology of this sampling distance is the core contribution of this paper, this warrants more effort in explanation. I would have suggested moving part of Section 6 to the supplementary material in order to make room for this.\n\nii. Again in Section 5.2, eq (2). It isn't too surprising that this is a reasonable distance to choose, casting aside my previous doubts about $r$-profiles. However, this could use a bit more explanation. Reading it, the weighting by $2^{-r}$ treats smaller sampling radii as more important, while downweighting larger sampling radii: and of course, this kind of weighted sum of a difference of sequences is a common example of a distance between sequences in functional analysis. In this context, this could be interpreted as saying that the distance is small for graphs that exhibit similar motif structures, but perhaps with differing global structure. Could you please explain this in more detail? Is the sampling distance the only appropriate distance for defining this topology, or is it one in some class of appropriate metrics for this task?\n\n**Comments**\n\n1. Overall thoughts: I found this paper to be quite enjoyable and informative. The presentation is quite good, and the results are novel, providing an interesting perspective on randomized approaches to graph parameter estimation. I appreciated how the authors tied the notion of an estimable graph parameter to a novel metric topology, which allowd them to approach this problem from a functional analysis perspective. Overall, despite the issues I pointed out on practicality and some didactic concerns, I think this is a fine paper, and should be accepted.\n\n**Editorial** (No impact on decision)\n\n1. Line 228: \"Benjamini-Schram\" is misspelled.\n\n2. Line 303: \"numbere\" is misspelled.\n\n3. Some of the citations do not look very good. Please take another pass on these, **with a particular focus on capitalization.** Some problematic citations I noticed were [20],[31],[34],[40],[42],[43],[56],[58],[61],[63/64],[71],[72]. There are also inconsistencies on venue citation, for instance between [13/15] and [11/21]. I would suggest using the `@string` macro in BibTeX to ensure consistent venue naming, e.g.,\n\n```\n@string{iclr={International Conference on Learning Representations}}\n\n@article{\ntitle={Absurdly Deep Convolutional Neural Networks},\nauthor={John Smith},\njournal=iclr,\n}\n```\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are addressed in body of the paper, societal impact is not an issue for this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "IXljYIrxjc", "reviewer": "Reviewer_TQV6", "summary": "This paper studies a theoretical framework to address learning problems over graphs under partial observation constraints. In this context, a Random Balls Sampling GNN architecture based on random neighborhood model is introduced and its expressibility and learnability are characterized theoretically. Applications of the proposed architecture to settings with perturbations and size-generalizability are also discussed.   ", "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": "1. The notion of estimability of a graph parameter is central to the theoretical claims in the paper. Therefore, I recommend that the authors elaborate more on this aspect in Section 3.2. Moving Definition 18 and some of the discussions in Appendix D.1 to the main paper will greatly improve the readability of this section of the paper. \n\n2. Similarly, the notion of 'uniformly continuous' graph parameter must be explicitly defined in Section 5.2.\n\n3. What is the intuition behind the factor $2^{-r}$ in equation (2)?\n\n4. In Section 6.3.1, what does the notation $G_{\\leq N}$ signify? Also, shouldn't you have $|p(G) - {\\cal A}(G_{\\leq N})|\\leq \\epsilon$ in the definition of a size generalizable parameter $p$ for the algorithm ${\\cal A}$ that operates on the given dataset?\n\n5. The main paper lacks experimental evaluations and limited experiments are relegated to the Appendix. It would be useful to have an experimental setup in the main paper to illustrate the applicability of various theoretical claims in the paper. \n\nThe theory in this paper is tangential to my expertise and therefore, I am not fully familiar with other theoretical works in this context. However, the notions of learning from partially observed graphs and size generalizability are interesting and would be of interest to a wider audience. The readability of the paper could be improved by some reorganization of the content between the main paper and Appendices and including formally defining the notions of estimability, uniform continuity, size generalizability etc. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "37EaHK-yaBY", "reviewer": "Reviewer_eHqG", "summary": "The paper uses sublinear algorithms to estimate certain graph functions.\n\nThe paper is essentially a property testing (sublinear algorithms) paper posing as a GNN paper. This is not necessarily a bad thing if the connection is strong enough; however, this connection does not become very clear to me.\n\nThe main relation to GNN is very vague as core concepts such as universality are not well-defined. I presume the universal approximation theorem is meant here, but I cannot be sure.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In section 5.1 an important restriction is mentioned that somehow does not become clear in Theorem 3.\n(the theorem is only applicable to the continuous functions in  the randomized Benjamini–Schramm topology)\n\nThere are some applications mentioned, but they are not very illuminating. Could you perhaps state some concrete examples of functions that can be estimated?\n\nNot clear what this means:\nA rooted graph (G, v) is a graph G augmented with a vertex v in V (G) \n\nWeaklyConnectedComponents quadratic query complexity? Needs to check all possible adjacency matrix entries? What if the degrees are super-constant? Does that mean that the sampling is also super-constant?\n\nThe proof idea of Theorem 3 feels unfinished. Why is good to be able to list all isomorphism classes of all graphs on x vertices?\n\nShouldn't Theorem 3 mention sampling complexity in some way or another? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Fine", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers estimation of a real number associated to a large graph. Some examples of quantities that one might wish to estimate are the density of triangles (or relatedly the clustering coefficient). Rather than observing the entire graph, it is assumed that algorithms have access to a specific random sampling procedure whereby random nodes are selected and then their neighborhoods are randomly explored. A variation on the Benjamini-Schramm topology is introduced and the set of estimable graph properties is characterized in terms of continuity in this topology. A number of other results are presented regarding generalization across multiple graph sizes, etc.

The proposed sampling/observation model is reasonable and placed within context of related observation models. While the work is entirely theoretical, its results clearly demarcate what is possible or impossible with regards to the specific sampling model. Thus, there are natural implications for what can be learned by graph neural networks. The work seems likely to spur further investigation with other sampling models and to make tighter connections to finite size graph neural networks. 
Decision: Accept (Poster)