Reconstruction for Powerful Graph Representations
Authors: Leonardo Cotta
Christopher Morris
Bruno Ribeiro
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph representation learning
invariances
deep learning
graph theory

Abstract: Graph neural networks (GNNs) have limited expressive power, failing to represent many graph classes correctly. While more expressive graph representation learning (GRL) alternatives can distinguish some of these classes, they are significantly harder to implement, may not scale well, and have not been shown to outperform well-tuned GNNs in real-world tasks. Thus, devising simple, scalable, and expressive GRL architectures that also achieve real-world improvements remains an open challenge. In this work, we show the extent to which graph reconstruction---reconstructing a graph from its subgraphs---can mitigate the theoretical and practical problems currently faced by GRL architectures. First, we leverage graph reconstruction to build two new classes of expressive graph representations. Secondly, we show how graph reconstruction boosts the expressive power of any GNN architecture while being a (provably) powerful inductive bias for invariances to vertex removals. Empirically,  we show how reconstruction can boost GNN's expressive power---while maintaining its invariance to permutations of the vertices---by solving seven graph property tasks not solvable by the original GNN. Further, we demonstrate how it boosts state-of-the-art GNN's performance across nine real-world benchmark datasets.

Reconstruction for Powerful Graph Representations
Leonardo Cotta Purdue University cotta@purdue edu
Christopher Morris
Mila Quebec AI Institute, McGill University
chriis@chrietoopeerrrrri..... info
Bruno Ribeiro
Purdue University
ribeiro@cs purdue. edu
Abstract
Graph neural networks (GNNs) have limited expressive power, failing to represent many graph classes correctly. While more expressive graph representation learning (GRL) alternatives distinguish some of these classes, they significantly harder to implement, may not scale well, and have not been shown to outperform well-tuned GNNs in real-world tasks. Thus, devising simple, scalable, and expressive GRL architectures that also achieve real-world improvements remains an open challenge. In this work, show the extent to which graph reconstruction reconstructing a graph from its subgraphs can mitigate the theoretical and practical problems currently faced by GRL architectures. First, we leverage graph reconstruction build two new classes of expressive graph representations. Secondly, we show how graph reconstruction boosts the expressive power of any GNN architecture while being (provably) powerful inductive bias for invariances to vertex removals. Empirically, we show how reconstruction can boost GNN's expressive power-while maintaining its invariance to permutations of the vertices-by by solving seven graph property tasks not solvable by the original GNN. Further, demonstrate how it boosts state-of-the-art GNN's performance across nine realdworld benchmark datasets.
Introduction
Supervised machine learning for graph-structured data, i.c., graph classification and regression, is ubiquitous across application domains ranging from chemistry and bioinformatics 94 image [89]. and social network analysis (33] Consequently, machine learning on graphs is an active research area notaaly with numerous proposed approaches- notably GNNs [2] 42 45) GRL methods.
being the most representative case of
Arguably, GRL's most interesting results arise from cross-over between graph theory and representation learning. For instance, the representational limits of GNNs are upper-bounded by simple heuristic for the graph isomorphism problem [78] 105). the 1-dimensional Weisfeiler-Lemad algorithm (1- WL) [4
[02], which might miss crucial structural information in the data (5). Further works show how GNNs cannot approximate graph properties such as diameter, radius, girth, and subgraph counts 25 38, inspiring architectures (6
66 77] 78) based on the more powerful x-dimensional Seiifeiler-Leman algorithm (K- WL) 44 On the other hand, despite the limited expressiveness of GNNs, they still can overfit the training data, offering limited generalization performance [T05]. Hence, devising GRL architectures that are simultaneously sufficiently expressive and avoid overfitting remains an open problem.
We opt for using instead of k i.e., WL instead of lc WL, not confuse the reader with the hyperparameter A: of our models.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

An under-explored connection between graph theory and GRL is graph reconstruction, which studies graphs and graph properties uniquely determined by their subgraphs. In this direction, both the pioneering work of Shawe-Taylor [88] and the more recent work of Bouritsas et al. [8]. show that assuming the reconstruction conjecture (see Conjecture[] [T) holds, their models are most-expressive representations (universal approximators) of graphs. Unfortunately, Shawe-TTylorr computational graph grows exponentially with the number of vertices, and [Bouritsas et al. full representation power requires performing multiple graph isomorphism tests potentially large graphs (with n I vertices). Moreover, these methods were not inspired by the more general subject of graph reconstruction; instead, they rely on the reconstruction conjecture to prove their architecture's expressive powers.
Contributions. In this work. we directly connect graph reconstruction to GRL. We first show how the k-reconstruction of graphs reconstuticnn from induced k-vertex subgraphs -inuucss a natural class of expressive GRL. architectures for supervised learning with graphs, denoted k: k-Reccostruction Neural Networks. We then show how several existing works have their expressive power limited by k-reconstruction. Further, we show how the reconstruction conjecture's insights lead to provably most expressive representation of graphs. Unlike Shawe-Taylo (88) and Bouritsas et al. [8] which, for graph tasks, require fixed-size unattributed graphs and multiple (large) graph isomorphism tests, respectively, our method represents bounded-size graphs with vertex attributes and does not rely on isomorphism tests.
To make our models scalable, we propose k- R-Reconstruction GNNs, a general tool for boosting the expressive power and performance of GNNs with graph reconstruction. Theoretically. we characterize their expressive power showing that k- d-Reeconttruction GNNs can distinguish graph classes that the 1-WL. and 2- WL. cannot, such as cycle graphs and strongly regular graphs, respectively. Further, to explain gains in real-world tasks, we show how reconstruction can act as a lower-variance risk estimator when the graph-generating distribution is invariant to vertex removals. Empirically, we show that reconstruction enhances GNNs expressive power, making them solve multiple synthetic graph property tasks in the literature not solvable by the original GNN, On real-workd datasets, we show that the increase in expressive power coupled with the oowervvariance risk estimator boosts GNNs' performance up to 25%. Our combined theoretical and empirical results make another important connection between graph theory and GRL.
1.1 Related work
We review related work from GNNs, their limitations, data augmentation, and the reconstruction conjecture in the following. See Appendix [or more detailed discussion.
GNNs.
Notable instances of this architecture include, e.g., 31 47 97,, and the spectral approaches
proposed in, e.g., [19 30 56 aal of which descend from early work in [10 57 69 70 71
87
[0]
Aligned with the field's recent rise in popularity, there exists a plethora of surveys on recent advances in
GNN methods. Some of the most recent ones include [1 [04 14]
Limits of GNNs. Recently, connections to Weisfeiler-Leman type algorithms have been shown [9]
27 39 40, 64, 66) (77) [78) [10]] Specifically, the authors of [78] 105
show how the 1-WL limits the introduce re-dimensional GNNs paassage-psssingg scheme between subgraphs of cardinality k. Later, this was refined in 6 (66] and in (76) by deriving models equivalent the more powerful x-dimensional Weisfeiler-Lemar algorithm. Chen et al. (27) connect the theory of universal approximation of functions and graph isomorphism testing, further introducing a variation of the
expressive power of any possible GNN architecture. Morris et al.
78
which rely on more expressive
permutation-invarian
WI., Recently, a large body of work propose enhancements to GNNs, e.g., see [3] [1] 18] 80 [98] [09], making them more powerful than the 1-WL; see (75] for a survey and see Appendix A for a in-depth discussion. For clarity, throughout this work, we will use the term GNNs to denote the class of message-passing architectures limited by the 1-WL algorithm, where the class of distinguishable graphs is well understood [5].
Data augmentation, generalization and subgraph- inductive biases. There exist few works proposing data augmentation for GNNs for graph classification. Kong et al. [59] introduces simple feature perturbation framework to achieve this, while Rong et al. 855. Feng et al. (34] focus on
vertex-level tasks. Garg et al. [8) study the generalization abilities of GNNs showing bounds on the
Rademacher complexity, while Liao et al. [62] offer a refined analysis within the PAC-Bayes framework.
Recently, Bouritsas et al. [18] proposed to use subgraph counts as vertex and edge features in GNNs.

---

(G-)(G)
Figure I: A graph G and its deck Dn-1 (G), faded out vertices are not part of each card in the deck.
Although the authors show an increase in expressiveness,, the extent, e.g., which graph classes their model can distinguish, is still mostly unclear. Moreover, Yehudai et al. [T07] investigate GNNs' ability to generalize to larger graphs. Concurrently. Bevilacqua et al. [1] show how subgraph densities can be used build size-invariant graph representations. However, the performance of such models in in-distribution tasks, their expressiveness, and scalability remain unclear. Finally, Yuan et al. [MI show how GNNs' decisions can be explained by (often large) subgraphs, further motivating our use of graph reconstruction as a powerful inductive bias for GRL.
Reconstruction conjecture. The reconstruction conjecture is longstanding open problem in graph theory, which has been solved in many particular settings. Such results come in two flavors. Either proving that graphs from specific class are reconstructible determining which graph functions reconstructible. Known results of the former are, for instance, that regular graphs, disconnected graphs, and trees are reconstructible 53). In particular, we highlight that outerplanar graphs, which account for most molecule graphs, are known to be reconstructible [41]. For comprehensive review of graph reconstruction results, see Bondy [T6]
2
Preliminaries
Here, we introduce notation and give an overview of the main results in graph reconstruction theory [16 including the reconstruction conjecture (96). which forms the basis of the models in this work.
43
Notation and definitions. As usual, let [n]] = (I,.... n C N for n 2 1, and let K.... B denote a multiset. In abuse of notation, for set X with in X, we denote by X
the set X \ {x]. We also assume elementary definitions from graph theory, such as graphs, directed graphs, vertices, edges, neighbors, trees, isomorphism, et cetera; see Appendix B The vertex and the edge set of a graph G are denoted by (() and E(G), respectively. The size of graph G is equal to its number of vertices. Unless indicated otherwise, we edges are annoted with attributes, i.e., vallev vectors.
= IV()). If not otherwise stated, we assume that vertices and
We denote the set of all finite and simple graphs by G. The subset of G without edge attributes (or edge directions) is denoted @ C G. We write G ~ H if the graphs G and are isomorphic. Further, we denote the isomorphism type, i.e., the equivalence class of the isomorphism relation, of a graph G as [GG). Let S C (G). then G[S] is the induced subgraph with edge set E(G)[S] = {S n E()). We will refer to induced subgraphs simply as subgraphs in this work.
Let R be family of graph representations, such that for d d-dimensional representation vector r(G) for graph G in G. We say R can distinguish graph G if there exists r in R that assigns unique representation to the isomorphism type of G, i.e., r(G) = r(H) if and only if G = H. Further, we say R distinguishes pair of non-isomorphic graphs G and H if there exists some r in R such that rG) a rH).. Moreover, we write R, < R2 if 9t distinguishes between all graphs H, does, and Ri Mi if both directions hold. The corresponding strict relation is denoted by <. Finally, we say R is a most-expressive representation of class of graphs it distinguishes all non-isomorphic graphs in that class.
r in R, r: 9 + Rd assigns a
Graph reconstruction. Intuitively, the reconstruction conjecture states that an undirected edge- unattributed graph can be fully recovered up to its isomorphism type given the multiset of its vertex- deleted subgraphs' isomorphism types. This multiset of subgraphs usually referred to as the deck of the graph, see Figure [ for an illustration. Formally, for graph G, we define its deck as (G) (ZGG o):: v E V(G) We often call an element in (G) card. We define the graph reconstruction problem as follows.
Definition 1. Let G and H be graphs, then H is a reconstruction G if H and G have the same deck, denoted H G. graph G reconstructible if every reconstruction of G is isomorphic to G, ie. H G implies H ~ G.
3

---

Similarly, we define function reconstruction, which relates functions that map two graphs to the same value if they have the same deck.
Definition 2. Let f: 9 3 be finction, then f is reconstructible if f(G) = f(H) for all graphs in ((H,G) G²: H ~ G}, i.e., G ~ H implies f(G) = f(H).
We now state the reconstruction conjecture, which in short says that every G in @ with [V] 2 is reconstructible.
Conjecture (Kelly [52] Ulam (6). Let H and G in 8 be two finite, undirected, simple graphs with at least three vertices. If H is reconstruction of G, then H and G are isomorphic.
We note here that the reconstruction conjecture does not hold for directed graphs, hypergraphs, and infinite graphs [16 92 93 In particular, edge directions can be seen as edge attributes. Thus, the reconstruction conjecture does not hold for the class G. contrast, the conjecture has been proved for practical-relevan graph classes, such as disconnected graphs, regular graphs, trees, and outerplanar graphs [66.. Further, computational searches show that graphs with up to eleven vertices are reconstructible [68]. Finally, many graph properties are known be reconstructible, such as every size subgraph count, degree sequence, number of edges, and the characteristic polynomial [16].
Graph k-rrccostrruction Kelly et al. 53 generalized graph reconstruction, considering the multiset of subgraphs of size k instead of n 1, which we denote DA (G) = HI(H): И E S (G)) where S(k) is the set of all (f) k-size subsets of V. We often call an element in Dx(G) a k-card. From the k-deck definition, is easy to extend the concept of graph and function reconstruction, cf. Definitions ! and to graph and function d-rrconstruction.
Definition 3. Let G and H be graphs. then H is k-reconstruction of G if H and G have the same k-deck, denoted H ~ug G. A graph G is k-reconstructible if every k-reconstruction of G is isomorphic to G, i.e., H ~* implies H = G.
Accordingly, define k-function reconstruction as follows.
Definition 4. Let f: G + + be a function, then f is k-reconstructible if f(G) = f(H) for all graphs in ()H g²: H ~u G), i.e. G ~y H implies ((G) - f(H).
Results for k-reconstruction usually state the least k as a function of n such that all graphs G in G (or some subset) are k-reconstrucctible [84] There exist extensive partial results in this direction, mostly describing k-reconstructibiiliy (as function of n.) for a particular family of graphs, such trees, disconnected graphs, complete multipartite graphs, and paths, see [84] 60). More concretely, Nydl 83 Spinoza and West [9T] showed graphs with 2k vertices that are not k-reconstructible. In practice, these results imply that for some fixed there will be graphs with not many more vertices than that are not k-reconstructible. Further, k-reconstructible graph functions such as degree sequence and connectedness have been studied in 65 91 depending on the size of In Appendix C we discuss further such results.
3 Reconstruction Neural Networks
Building on the previous section, we propose two neural architectures based on graph k-reconstruction and graph reconstruction. First, we look at k-Reconstruction Neural Networks, the most natural way to use graph k-reconstruction. Secondly, we look at Full Reconstruction Neural Networks, where we leverage the Reconstruction Conjecture to build most-expressive representation for the class of graphs of bounded size and unattributed edges.
k- R--eonnttructinn Neural Networks.
Intuitively, the key idea of k- R-Reonnstruction Neural Networks that of learning a joint representation based on subgraphs induced by & vertices. Formally, let fw: UPe 1 R -> Rd be a (row-wise) permutation-invariant function and GR = [G E G: VV(G)
k} be the set of graphs with exactly ht vertices. Further, let h (A): G. - Ixd be graph representation function such that two graphs G and H l vertices are mapped to the same vectorial representation
and only they are isomorphic, i.e., h (R) = h(()) (H) > G ~ H for all G and H in Gy. We define k- Reconstruction Neural Networks over G as function with parameters W in the form
(k) W (G) fw (CONCAT =
(G[S)): S 5()))))
where ((k) is the set of all k-size subsets of V(G) for some 3 < k S and CONCAT denotes row-wise concatenation of multi-set of vectors in some arbitrary order. Note that / might also be function

---

with learnable parameters. In that case, we require it to be eost-expressive for Gg. The following results characterize the expressive power of the above architecture.
Proposition Let Iw be universal upproximator of multisets 1112
700 79
Then, Tw can
(k)
approximate function if and only if the function is k-reconstructible
Moreover, can observe the following.
Observation 1 (Nydl [84), Kostochka and West 60
For any graph G in G, its k-deck Dz(G)
determines its (k 1) -deck (G).
From Observation we can derive a hierarchy in the expressive power of d-Reconstruction Neural (3) (4)
Networks with respect the subgraph size k. That is, rw 3 rw .... "W
(n-2) 3 rw
(n-1)
In Appendix D we show how many existing architectures have their expressive power limited by k-reconstruction. We also refer to Appendix for the proofs, a discussion on the model's 's computational complexity, approximation methods, and relation to existing work.
Full Reconstruction Neural Networks. Here, we propose a recursive scheme based on the recon- struction conjecture build a most-expressive representation for graphs. Intuitively, Full Reconstruction Neural Networks recursively compute subgraph representations based on smaller subgraph represen- tations. Formally, let 8 Sn- == {G E 6: V(G)) S n') be the class of undirected graphs with unattributed edges and maximum size n*. Further, let !W! U Rm - R$ be (row-wise) permutation invariant function and let h43st subgraph induced by vertices and j. We can now define the representation r(G[V(() of graph G in & Sn in a recursive fashion as
most-expressive representation of the two-vertex
fIISD (CONCAT((r(C[SS- - u)): v SB)), if < |S| S hs(G())),
r(GS)) =
if ||| = 2.
Again, CONCAT is row-wise concatenation in some arbitrary order. Note that in practice, it is easier to build the subgraph representations in a bottom-up fashion. First, use two-vertex subgraph representations to compute all threc-vertex subgraph representations. Then, perform this inductively until we arrive at a single whole-graph representation. In Appendix we prove the expressive power of Full Reconstruction Neural Networks, i.e., we show how if the reconstruction conjecture holds, it is a most-expressive representation of undirected edge-unan unattributed graphs. Finally, we show its quadratic number of parameters, exponential computational complexity, and relation to existing work.
4 Reconstruction Graph Neural Networks
Although Full Reconstruction Neural Networks provide a most-expressive representation for undi- rected, unattributed-edge graphs, they are impractical due to their computational cost. Similarly, d-Reconstruction Neural Networks are not scalable since increasing their expressive power requires computing most-expresssvv representations of larger k-size subgraphs. Hence, to circumvent the computational cost, we replace the most-expressive representations of subgraphs from k- R-Reconstruction Neural Networks with GNN representations, resulting in what we name k-RRecostrructio GNNs. This change allows for scaling the model to larger subgraph sizes, such
1, 2, ... cetera.
Since, in the general case, graph reconstruction assumes most-expressive representations of subgraphs, it cannot capture k- t-Reconstruction GNNs' expressive power directly. Hence, we provide theoretical characterization of the expressive power of &-Reconstruction GNNs by coupling graph reconstruction and the GNN expressive power characterization based on the 1-WL algorithm. Nevertheless, in Appendix F22 we devise conditions under which k-Reconstruction GNNs have the same power as k-Reconstruction Neural Networks. Finally, we show how graph reconstruction can act (provably) powerful inductive bias for invariances to vertex removals, which boosts the performance of GNNs even in tasks where all graphs already distinguishable by them (see Appendix G). We refer to Appendix | for a discussion on the model's relation to existing work.
Formally, let fw: U R + R be (row-wise) permutation invariant function and IGNN, G - I B a GNN representation. Then, for 3 < k < (V)G),, a k- Recoonsstruttion GNN takes the form (G) /w) (CONCAT( ( GNN (G[S)): s( B)).
(k.GNN) 7 W
5

---

with parameters W (W1, 1, W2), where S(A) is the set of all k-size subsets of V(G), and CONCAT row-wise concatenation in some arbitrary order.
Approximating 'w (k.GNN) By design, k-Reconstruction GNNs require computing GNN representations for all k-vertex subgraphs, which might not be feasible for large graphs or datasets. To address this, we discuss a direction to circumvent computing all subgraphs, i.e., approximating rw
(A.GNN) by sampling.
One possible choice for fw is Deep Sets [122,, which we use for the experiments in Sec- tion where the representation is sum decomposition taking the form "w (
(K,GNN) (G)
PWi Esegin @wz (NWN (C(ST)) where PW, and ow, are permutation sensitive functions, such as feed-forward networks. We can learn the k-Reconstruction GNN model over a training dataset D(u) {(G,, M/ j and loss function / by minimizing the empirical risk
N (k.GNN)
(D!h; W. 2. Wa)
N Σ (rw (G:).
(1)
(A,GNN) is sum over Equation is impractical for all but the smallest graphs, since rw (k,UNNN using a sam- all k-vertex induced subgraphs ((&) of G. Hence, we approximate rw
ple s(h) c (S(A) drawn uniformly at random at every gradient step, i.e., Tw G(A,GNN) | Esespy Φwz
(G) (G)
Pw. (1S()))))
(hw, ( (G[SI))) Due to non-lineassties in pw, and 1, plug-
((,GNN)) into Equation ( does not provide with unbiased estimate of Rs. However, ging TW
(lww (a). v) is convex in a, in expectation, we will be minimizing a proper upper bound of our loss, i... 1/N" Σ 1(TW (1Nl,GNN) v1) S L/N" Ei=
N" ((F (Gx), 31). In practice, many models rely on this approximation and provide scalable and reliable training procedures, cf. 48 79
112
4.1 Expressive power
Now, we analyze the expressive power of k-Reccostruutton GNNs. It clear that k-Reconstructton GNNs 3 k- t-Reconstruction Neural Networks, however the relationship between k- teeeoonttruction GNNs and GNNs not that straightforward. At first, one expects that there exists well-defined such as the one in k-Reccnstrructio Neural Networks (see Observation [ between GNNs, (n (.-11)-Rcconstruttoon GNNs, (n (em--22))cetttteee Reconstruuction GNNs, and so on. However, there is no such hierarchy, as we see next.
Are GNNs more expressive than C-Reconstruction GNNs? well-known that GNNs cannot distinguish regular graphs 78). By leveraging the fact that regular graphs are reconstructible [53), we show that cycles and circular skip link (CSL) graphs-two classes of regular graphs-can indeed be distinguished by k- R-Reconstructio GNNs, implying that k- Recconsttruttinn GNNs are not less expressive than GNNs. We start by showing that k- t-RReonstructioo GNNs can distinguish the class of cycle graphs
Theorem (k- (e-Reconstruction GNNs can distinguish cycles). Let G E 8 be a cycle graph with n vertices and ls := L. An (n Reconstsstrutio GNN assigns a unique representation G if 1/2 and ii) n 2 (E - log E + 1)(
i) (1+ o(1)
log n2 log log
c+te log logg+e+1 [e-1)log(-1
+ hold.
The following results shows that k- Reconstrucctio GNNs can distinguish the class of CSL graphs.
Theorem 2 (d-Recconttructinn GNNs can distinguish CSL graphs). Let G, H @ be two non- isomorphic circular skip link (CSL) graphs (a class of 4-reuulr graphs, Reconstruction GNNs can distinguish G and H.
graphs. of. [23 80)). Then, (n - 1)-
Hence, if the conditions in Theorem 1 hold, GNNs A (en-o))-econstruuttio GNNs. Figure 2 (cf. Appendix F) depicts how k- d-Reconstruction GNNs can distinguish a graph that GNNs cannot. The process essentially breaks the local symmetries that make GNNs struggle by removing one (or few) vertices from the graph. By doing so, we arrive at distinguishable subgraphs. Since we can reconstruct the original graph with its unique subgraph representations, we can identify it. See Appendix for the complete proofs of Theorems D and 2

---

Are GNNs less expressive than d-Reconstruction GNNs? We now show that GNNs can distinguish graphs that k- k-Reconstruction GNNs with small & cannot. We start with Proposition 2 Istaaing that there exist some graphs that GNNs can distinguish which k-Reconstruction GNNs with small k cannot.
Proposition 2. GNNs A k-Reconstruction GNNs for k S [n/2].
On the other hand, the amalysis is more interesting for larger subgraph sizes, e.g., n - 1, where there are known examples of (undirected, edge-unatrributed) non-reconstruutible graphs. There are graphs distinguishable by GNNs with at least one subgraph not distinguishable by them; see Appendix [F] However, the analysis is whether the multiset of all subgraphs' representations can distinguish the original graph. Since we could not find any counter-exanples, we conjecture that every graph distinguishable by GNN is also distinguishable by k-Reconstruction GNN with k = n 1 or possibly more generally with any k close enough to n. In Appendix F we state and discuss the conjecture, which we name WL reconstruction conjecture. If true, the conjecture implies GNNs < (n -)-onconstruuttoo GNNs. Moreover, if we use the original GNN representation together with k- t-Reconstruction GNNs, Theorems and imply that the resulting model is strictly more powerful than the original GNN.
Are k-Reconstruction GNNs less expressive than higher-order (K-WL)) GNNs?
Recently a line of work, e.g. 6 67 76), explored higher-order GNNs aligning with the s- WL hierarchy.
Such architectures have, in principle, the same power the x-WL algorithm in distinguishing non- isomorphic graphs. Hence, one might wonder how k-Reconstruction GNNs stack up to x- x-WL-based algorithms. The following result shows that pairs of non-isomorphic graphs exist that (n 2)- Reconstruction GNN can distinguish but the 2- WL cannot.
Proposition 3. Let 2-GNNs be neural architectures with the same expressiveness as the 2-WL algorithm. Then, (n 2) Re-oosttttuutionn GNN & 2-GNNs 2-WL.
As a result of Proposition 3 using (n 2) Re-construution GNN representation together with a 2-GNN increases the original 2- 2-GN''s expressive power.
4.2 Reconstruction as a powerful extra invariance for general graphs
An essential feature of modern machine learning models is capturing invariances of the problem of interest [63]. It reduces degrees of freedom while allowing for better generalization [I3 663. GRL is predicated on invariance to vertex permutations, i.c., assigning the same representation to isomorphic graphs. But are there other invariances that could improve the generalization error?
k-reconstruction is an extra invariance. Let P(G, Y) be the joint probability of observing a graph G' with label Y. Any k-reconstruction based model, such as d-Reconstruction Neural Networks and k- d-Reccostruution GNNs, by definition assumes P(G, Y)) to be invariant to the k-deck, i.c., P(G,Y) P(H, Y) if Dx(G) (H). Hence, neural architectures for k-Reconstructiin Neural Networks and k-Reconstruccion GNNs directly define this extra invariance beyond permutation invariance. How we do know is extra invariance and not consequence of permutation invariance? It does not hold on directed graphs [93, where permutation invariance still holds.
Hereditary property variance reduction. We now show that the invariance imposed by k- reconstruction helps in tasks based on hereditary properties [77. A graph property (G() is called hereditary if it is invariant to vertex removals, i.e. p(G) μ G - 21) for every VG) and GE E G. By induction the property is invariant to every size subgraph, i.c., ((G) = (GG[S) for every S E S(A), k [n] where S(k) is the set of all k-size subsets of (G). Here, the property is invariant to any given subgraph. For example, every subgraph of planar graph is also planar, every subgraph of an acyelic graph is also acyclic, any subgraph of a j-colorable graph is also j-colorable. A more practically interesting (weaker) invariance would be invariance to a few vertex removals. Next we define 5 herreditary properties (a special case of a --hereditary property). In short, a property is ō-hereditary it is a hereditary property for graphs with more than ă vertices.
Definition 5 (6-hereditary property). A graph property μ.: G + y is said to be 8-hereditary if (GG)= = ( - v)), Vu E VGG), (H E G > 8). That is, p is uniform in G and all subgraphs of G with more than 8 vertices.
Consider the task of predicting Y == (G)). Theorem 3 shows that k- Reoeconstruction GNNs is an invariance that reduces the variance of the empirical risk associated with d-hereditary property tasks. See Appendix FF for the proof.
7

---

Theorem 3 (k- Re-Reconstruction GNNs for variance reduction of 8-hereditary tasks), Let P P(G be a 8 8-hereditary distribution, i.e. Y := p(G) where is a 8-hereditary property. Further, let P(G,Y) for all G E 9 with [V(G)
2 5 + O. Then, for k-Reconstruuttio GNNs taking the form
pw, (1/(S(A) EsEsu Φw2 (C151)) )
if (fllW (a),y) is convex in a we have
Var[Ra] S Var[Ra
where R& is the empirical risk of k-Reconstruction GNNs with == n 12-66 l (cf. Equation ① and RONN is the empirical risk of GNNs.
5 Experimental Evaluation
In this section, we investigate the benefits of d-Reconstruction GNNs against GNN baselines on both synthetic and real-world tasks. Concretely, we address the following questions:
Q1. Does the increase in expressive power from reconstruction (cf. Section 4.1) make k- k-Reconstruction
GNNs solve graph property tasks not originally solvable by GNNs?
Q2 Can reconstruction boost the original GNNs performance on real-world tasks? If so, why?
Q3. What is the influence of the subgraph size in both graph property and real-world tasks?
Synthetic graph property datasets. For Q1 and Q3, we chose the synthetic graph property tasks in
T for which GNNs are provably incapable to solve due to their limited expressive power 38 The tasks are CSL (32], where we classify CSL graphs, the cycle detection tasks 4 CYCLES, 6 CYCLES and 8 CYCLES 98] and the multi-task regression from Corso et al. (28] where we want to determine whether graph is connected, its diameter, and its spectral radius. See Appendix
H for datasets statistics. Real-world datasets. To address Q2 and Q3, we evaluated E-Reconstruction GNNs on diverse set of large-scale, standard benchmark instances 49 74) Specifically, we used the ZINC (10K) [32, MOLEOO,, and
ALCHEMY (10K) (23], (GBG-MOLFRRESS
49 regression datasets. For the case of graph classification, we used OGBG-MOLHIV, OGBG-MOLPCBA, OGBG-TOX21, and DOBG-TTXCAAL [4]. See Appendix H for datasets statistics.
Neural architectures. We used the GIN (166), GCN (56). and the PNA 28 architectures as GNN baselines. We always replicated the exact architectures from the original paper, building on the respective PyTorch Geometric implementation [35]. For the OGBG regression datasets, we noticed how using jumping knowledge layer yields better validation and test results for GIN and GCN. Thus we made this small change. For each of these three architectures,
implemented k-Reconstruction GNNs for k in {n- 1, n 2, n 3. /2/2]] } using a Deep Sets function 112 over the exact same original GNN architecture. For more details,
Appendix G
Experimental setup. To establish fair comparisons, we retain all hyperparameters and training procedures from the original GNNs train the corresponding k-Reconstruction GNNs. Tables T and and Table 6jin Appendix present results with the same number of runs as previous work [28, 32 49 77
(88. i.e., five for all datasets exeept the OGBG datasets, where the number of subgraphs sampled for each k- t-Reconstruction GNN and each dataset, see Appendix G Non-GNN baselines. For the graph property tasks, original work used vertex identifiers or Laplacian embeddings to make GNNs solve them. This trick is effective for the tasks but violates an important premise of graph representations, invariance to vertex permutations. To illustrate this line of work, we compare against Positional GIN, which uses Laplacian embeddings [32) for the CSL task and vertex identifiers for the others [98] 28 To compare against other methods that like k-Reconstructton GNNs are invariant to vertex permutations and increase the expressive power of GNNs, we compare against Ring-GNNs (27 and (3-WL) PPGNs (66). For real-world tasks, Table 6 in Appendix [ shows the results from GRL alternatives that incorporate higher-order representations in different ways, LRP 27
ten runs. For more details, such as
GSN [8], 8-2-LGNNN (77,, and SMP 988.
All results are fully reproducible from the source and are available at https://gi /ttt:////tttbb.... com/ PurzuuetLInSSrrcoosttrcciii
Results and discussion.
A1 (Graph property tasks). Table I Theorem 2 where the increase in expressive power from reconstruction allows k-Reconstruution GNNs to distinguish CSL graphs, a task that GNNs cannot solve. Here, k- t--econstructton GNNs boost the accuracy of standard GNNs between 10x and x0x. Theorem only guarantees GNN expressiveness boosting for (n 1) Reeoosssttnction, but our empirical results also show benefits for k- R-Reconstruction with k < 222. Table D also confirms Theorem I where
8

---

Table I: Synthetic graph property tasks. We highlight in green R-Reconstruucton GNNs boosting the original GNN architecture. 1: Std. not reported in original work. +: Laplacian embeddings used as positional features. ": Vertex identifiers used as positional features.
Mulli-uik
CYCLES
CYCLES (Ausanay S)1
CONNECTIVITY
DIAMETER
SPECTRAL RADOUS Oog
Invartiaz in gemnatalion??
(Aucanary
(Ausanay
(Esg
longg
92.51
+-0300
1)
88.66
22.00
4.91
14299
333573
0.714
On 20
78.66
22.17
94.05 2 5.00
50 2 0.72
95.04 2,99
3,799
0.115
0.307
1 0.388
2,344
23.33
-3.770
[wy9]
40.06
4.9.0
75.13
61.78
61.55 6
-376
0.083
0.564
1:0005
-2.190
0.166
GUNiong
6,66 + 4,300
08.336 8 0.24
95.73 2.3
K7.16 +: 12.73
-3.761 4:0075
0.067
2 185
-2,204 : 0.343
(n- 1)
100000 10.00
99.00 1.0.0
W2.6 1.19
94.99
7.31
-,899
10100
-1.125
1.0.05
13.25 1.5.5
On 21
V7.82
(397)
41577
On 50
96.00 6.46
99.11 0.19
98.31 0.55
07.18
0.59
3,995
0.081
0.333
2.1117
33,05 0.2.5
49.53 7.442
75.19 9.19
66.04
63.66
-3693
11963
0,8518
1.0016
-1838 00851
(erig)
10,00
61 19
95.57
$4.81
-3,100
On-1) 1)
100.00 2.100
97.68 2.19
99.18
08.02 6272
11:01
1.03022
-3.64
(1-9)
98.83 7.7.7
99.12 0.78
10 0-047
99.12 0.77
-1.781
: 0.8
-0UN00 1:0115
-3447
1 0:070
95.53
89.36 0.00
13.92
-3710
0.000
0102
+0047
13.11
Tw/20
42.66
11.00
75.34
65.55
64.01
0.3.0
-2.77
1.445
2007
-1,073
Pesitional GEN
90.331
1:133
85.3
95.1
95.3!
-1661
-2.17
22.6
Ring GINN
10,00 + 0.00
99.9
100.0
71.4
PPGN
97.80
1001
99.87
87.11
76.51
Table 2: OGBG molecule graph classification and regression tasks. We highlight in green k- k-Reconstruction GNNs boosting the original GNN architecture.
OGRG-MOLTOOC] (ROC-ADCC 6)
CORG-MOUTOXCASTT (ROC-ADCS))
OGRG-MOI PREESOLV (RSMSF).
OGRI-MOLESOL (RSMSF) 1
OGRG-MOLLTIN TNP (RSMSF)
OGRG-MOI PCRA (AP%))
(ong.)
74.91 0..5L
63:41
2,411
1,111 0,08
0,754 0.010
21.16 :
Recunit
(u 3)
75.15 +: 1.40
63.95
0.53
2.283 0.279
LO26 0.033
0,716 = 0.020
23,60 0.02
(x=2)
76,84
65.36 0.49
2.117 0.181
0.000
0.736 0.025
23.25 0.00
(n- 5)
76.78 + 0.644
64.84 +:0.1
2.370 0.326
1055 + 0.001
0.738 0.018
23.33 0.09
[a/2]
0.75
62.29
1:51=00000
0.033
0.020
13.50
GCN (orig.)
75:29 0.00
63.54
2.412
1.106 0106
0.793 1 0,040
20.20
Ressnar.
(n- 1)
76.46 1 0.77
64.51 0.000
2.534 a 0.300
096 0,045
0.760 0.055
21,25
75.58 0:50
64.38 0.39
2,467
L086 0,04
0,766 0.025
20,10 2:
(n 3)
75,88 0.73
64,70 0.811
2,345 =: 0.261
1.114 0.047
0.754 0.021
19.04 0.03
[ny/
24.03 0.63
62:30 x 0.77
2,399 :: 0.361
1.372 e 0.085
0.835 1: 0.000
11.69 +: 1.41
PNA (orig))
74.28
=: 0.52
62.69 = 0.63
2,192 = 0.125
1.140 0.002
0,759 4: 0.017
25.45 2: 0.04
Rosanes
73:64
0.74
61.14 0.76
2.341 0.000
1,723
0,743 0.055
23.11 =
(n- 2)
74.89
4: 0.29
65:22 0.47
2.298 = 0.115
1,342 = 0.272
0.794 4: 0.055
22.10 :: 0.08
75.10
0.3
0.58
2,133 0.080
0.163
0.41
[8/2]
73.71 0.61
61.25 =
2.085 0.231
1.157 0.066
0.843 0.018
12.33
k-Reconstruction GNNs provide significant accuracy boosts on all cycle detection tasks (4 CYCLES, 6 CYCLES and 8 CYCLES). See Appendix J.I for a detailed discussion on results for CONNECTIVITY. DIAMETER, and SPECTRAL R RADIUS, which also show boostings.
A2 (Real-world tasks). Table 2 and Table in Appendix [ show that applying k-reconstruction to GNNs significantly boosts their performance across all eight real-world tasks. In particular, in Table 2, (n rreconsttructonn applied to GIN gives the best results in the OGBG tasks, with the exception of
we see a boost of up to 5 5% while achieving the best results in five out of six datasets. The
and OGBG-MOLPCEA where (n - 1) reconsttttuti performs better. The only settings where we did not get any boost were PNA for (GEG-MOLESOL and in Appendix I also shows consistent boost in GNNs' performance of up to 25% in other datasets. On ZINC, k-Reconstruction yields better results than the higher-order alternatives LRP and 8-2-LGNN. While GSN gives the best ZINC results, we note that GSN requires ieplication-specciie features. In OGBG-MOLHIV, k-reconstruction is able to boost both GIN and GCN. The results in Appendix G show that nearly 100% of the graphs in our real-world datasets are distinguishable by the 1-WL algorithm. thus can conclude that traditional GNNs are expressive enough for all our real-worke tasks. Hence, real-world boosts of reconstruction over GNNs can be attributed to the gains from invariances to vertex removals (cf. Section 4.2) rather than the boost in expressive power (cf. Section 4.1
MOLPCRA. Table 6
A3 (Subgraph sizes). Overall we observe that removing one vertex (k= is enough to improve the performance of GNNs in most experiments. At the other extreme end of vertex removals, k 2]. there is significant loss in expressiveness compared to the original GNN. In most real-world tasks, Table 2 and 6 in Appendix show variety of performance boosts also with & E (n- 2 -33) For GCN and PNA in AGBGG-MO.ESSO specifically, we only see k-Reconstruuttio boosts over smaller subgraphs such as n 3, which might be due to the task's need of more invariance to vertex removals (cf.
9

---

Section 4.2). In the graph property tasks [Table]] we see significant boosts also for & E nn-2, n-3) all models across most tasks, except PNA. However, as in real-world tasks the extreme case of small subgraphs k- [n/2] significantly harms the ability to solve tasks with k- k-Reconstruction GNNs.
Conclusions
Our work connected graph (k-) Ie-Jneconttrtctinn and modern GRI.. We first showed how such connection results in two natural expressive graph representation classes. To make our models practical, we combined insights from graph reconstruction and GNNs, resulting in k- d-Reconstruction GNNs. Our theory shows that reconstruction boosts the expressiveness of GNNs and has a lower-variance risk estimator in distributions invariant to vertex removals. Empirically, we showed how the theoretical gains of k- k-Reconstruction GNNs translate into practice, solving graph property tasks not originally solvable by GNNs and boosting their performance on real-world tasks.
Acknowledgements
This work was funded in part by the National Science Foundation (NSF) awards CAREER IIS- 1943364
and CCF-1918483 Any opinions, findings and conclusions recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors. Christopher Morris is funded by the German Academic Exchange Service (DAAD) through DAAD IFI postdoctoral scholarship (57515245). We want to thank our reviewers, who gave excellent suggestions to improve the paper.
References
[1] Abboud, R., Ccylan, i. i., Grohe, M., and Lukasicwicz. (2020). The surprising power of graph neural networks with random node initialization. CoRR, abs/2010.01179.
[2] Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Steeg, G. V. and Galstyan, A. (2019). Mixhop: Higher-order graph convolutional architectures via sparsified neighhorhood mixing. In International Conference on Machine Learning, pages 21-29.
[3] Albooyeh, M., Bertolini, D., and Ravanbakhsh, S. (2019). Incidence networks for geometrie deep learning. CoRR, abs/1905.1 1460.
[4] Anderson, B. M., Hy, T., and Kondor, R. (2019). Cormorant: Covariant molecular neural networks. In Advances in Neural Information Processing Systems, pages
[5] Arvind, V., Köbler, Rattan, G., and Verbitsky, O. (2015). On the power of color refinement. In International Symposium on Fundamentals of Computation Theory, pages 339-350.
[6] Azizian, W. and Lelarge, M. (2020). Characterizing the expressive power of invariant and equivariant graph neural networks. arXiv preprint arXiv:2006. 15646.
[7] Babai, L. (2016). Graph isomorphism in quasipolynomial time. In ACM SIGACT Symposium on Theory of Computing, pages 684-697.
[8] Barabasi, A.-L. and Oltvai, Z. N. (2004), Network biology: Understanding the cell's functional organization. Nature Reviews Genetics, 5(2):101-113.
[9] Barceló, P. Kostylev,
Monet, M., Pérez, J., Reutter, L., and Silva, J. P. (2020). The logical expressiveness of graph neural networks. In International Conference on Learning Representations.
[10] Baskin, I. Palyulin, V. A., and Zefirow, N. S. (1997). A neural device for searching direct correlations hetween structures and properties of chemical compounds. Journal of Chemical Information and Computer Sciences, 37(4)2715-721.
[11] Beaini, D., Passaro, S., Létourneau, V., Hamilton, W. L., Corso, G., and Liò, P. (2020). Directional graph networks. CoRR, abs/2010.02863.
[12] Bevilacqua, B., Zhou, Y., and Ribeiro, B. (2021). Size-invariant graph representations for graph classification extrapolations. arXiv preprint AXXi:2203300045
[13] Reddy, B. and Teh, W. (2020). Probabilistic symmetries and invariant neural networks. Journal of Machine Learning Research, (1
[14] Bodnar, C., Frasca, F., Wang. Y. G., Otter, N., Montúfar, G., Lio, P., and Bronstein, M. (2021). Weisfeiler and lehman go topological: Mcssage passing simplicial networks. arXiv preprint arXiv:2103.0322
[15] Bollobás, B. (1990). Almost every graph has reconstruction number three. Journal of Graph Theory. 14(1)1-4.
10

---

[16] Bondy, J. A. (1991). A graph reconstructor's manual. Surveys in combinatorics. 166:221-252.
[17] Borowiecki, M., Broere, I,, Frick, M., Mihok, P., and Semanišin, (1997). survey hereditary properties of graphs. Discussiones Mathematicae Graph Theory, 17(1):5-50. 50.
[18] Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. (2020), Improving graph neural network expressivity via subgraph isomorphism counting. CoRR, abs/2206.092522.
[19] Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y. (2014). Spectral networks and deep locally connected
networks on graphs. In International Conference on Learning Representation.
[20] Cangea, C., Velickovic, P., Javanovic, N., Kipf, T., and Liò, (2018). Towards sparse hierarchical graph classitiers. CoRR, abs/1811.01287.
[21] Chami, I., Abb-EEl-Haije S., Perozzi, B., Ré, C., and Murphy, K. (2020). Machine learning on graphs: model and comprehensive taxonomy. CoRR, abs/2005.036755
[22] Chami, I., Ying. Z., Ré, C., and Leskovee, J. (2019). Hyperbolic graph convolutional neural networks. In Advances in Neural Information Processing Systems, pages 4869-4880.
[23] Chen, G., Chen, P., Hsich, C., Lee, C., Liao, B., Liao, R., Liu, W., Qiu, J., Sun, Q. Tang, J., Zemel, R. S., and Zhang, S. (2019a). Alchemy: A quantum chemistry dataset for benchmarking Al models. CoRR,
abs/1906.094 09407.
(24] Chen, Dobriban, E., and Lec, J. H. (2019b). Invariance reduces variance: Understanding data augmentation in deep learning and beyond. arXiv preprint 1rXiv:1907.10990
[25] Chen, Z.. Chen, L., Villar, S., and Bruna. J. (2020a). Can graph neural networks count substructures? In Advances Neural Information Processing Systems.
[26] Chen, Z., Chen, L., Villar, S., and Bruna, J. (2020b). Can graph neural networks count substructures? CoRR, abs/2002.04025.
[27] Chen, Z., Villar, S., Chen, L.., and Bruna, J. (2019c). On the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances in Neural Information Processing Systems, pages 19968-18766.
[28] Corso, G., Cavalleri, L.,, Beaini, D., Lió, P., and Velickovic, (2020). Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Systems.
[29] Dasoulas, G., Santos, L. D., Scaman, K., and Virmaux, A. (2020). Coloring graph neural networks for node disambiguation. In International Joint Conference on Artificial Intelligence, pages 2126-2132.
[30] Defferrard, M., X., B.. and Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pages 3844-3852.
[31] Duvenaud, D. K., Maclaurin, D., Iparraguirre, J., Bombarell, R., Hirzel, T., Aspuru- Guzik, A., and Adams,
R. P. (2015). Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems, pages 22222222.
[32] Dwivedi, V. P., Joshi, C. K., Laurent, Bengio, Y., and Bresson, X. (2020). Benehmarking graph neural networks. CoRR, 000s//000000082..
[33] Easley, D. and Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning About Highly Connected World, Cambridge University Press.
[34] Feng, W., Zhang. J., Dong, Y., Han, Y., Luan, H., Xu, Q. Yang, Q. Kharlamov, E., and Tang. J. (2020). Graph random neural networks for semi sepi-supe learning on graphs. In Advances in Neural Information Processing Systems.
[35] Fey, M. and Lenssen, J. E. (2019). Fast graph representation learning with PyTorch Geometric. CoRR, abs/1903.02428.
[36] Flam-Shepherd, D., Wu, T., Friederich, P., and Aspuru-Guzik, A. (2020). Neural message passing on high order paths. CoRR, abs/2002.10413.
[37] Gao, H. and Ji, S. (2019). Graph U-Nets. In International Conference on Machine Learning, pages 2083-2092.
[38] Garg, V. K., Jegelka, S., and Jaakkola, T. (2020). Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pages 3419-3430,
[39] Geerts, F. (2020). The expressive power of kth-order invariant graph networks. CoRR, abs/2007. 12035.
[40] Geerts, F., Mazawiccki, F,, and Pérez, G. (2020). Let's agree to degree: Comparing graph convolutional networks in the message-passing framework. CoRR, 0bs/22004025922,
[41] Giles, W. B. (1974). The reconstruction of outerplanar graphs. Journal of Combinatorial Theory, Series 16(3):215 226.
[42] Gilmer, J.. Schoenholz, S. S., Riley, P. F., Vinyals. O., and Dahl, G. E. (2017). Neural message passing for quantum chemistry. In International Conference Machine Learning.
11

---

[43] Godsil, C. (1993). Algebraic combinatorics, volume 6. CRC Press.
[44] Grohe, M. (2017). Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic. Cambridge University Press.
[45] Grohe, M. (2020). Word2vec, Node2vec, Graph2vec, X2vec: Towards theory of vector embeddings of structured data. CoRR, abs/2003.
[46] Grohe, M. and Neuen, D. (2020). Recent advances on the graph isomorphism problem. CoRR, abs/201 1.01366.
[47] Hamilton, W. L., Ying, R., and Leskovee, (2017). Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages
[48] Hinton, G. E., Srivastava, N., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. R. (2012). Improving neural networks by preventing co-adaptation of feature detectors. CoRR, abs/1207.0568
[49] Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. (2020). Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems.
[50] Jin, Y. Song. G., and Shi, C. (2019). GraL.SP: Graph neural networks with local structural patterns. CoRR, abs/1911.07675.
[51] Junttila, T. and Kaski, P. (2007). Engineering an efficient canonical labeling tool for large and sparse graphs. In Workshop on Algorithm Engineering and Experiments, pages 135-149.
[52] Kelly, P. J. (1942). On isometric transformations. PhD thesis, University of Wisconsin Wisconsin-Madisonn
[53] Kelly, J. et al. (1957). A congruence theorem for trees. Pacific Journal of Mathematics, 7(1):961
[54] Keriven, N. and Peyré, G. (2019). Universal invariant and cquivariant graph neural networks. In Advances in Neural Information Processing Systems, pages 7090-7099.
[55] Kiefer, S., Schweitzer, P. and Selman, E. (2015). Graphs identified by logics with counting. In International Symposium on Mathematical Foundations of Computer Science, pages 319-330.
[56] Kipf, T. N. and Welling, M. (2017). Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representation.
[57] Kireev, D. B. (1995). Chemnet: A novel neural network based method for graph/property mapping. Journal of Chemical Information and Computer Sciences, 35(2):175-180.
[58] Klicpera, J.. GroB. J., and Günnemann, S. (2020). Directional message passing for molecular graphs. In International Conference on Learning Representations.
[59] Kong, K., Li. G., Ding, M.. Wu, Z., Zhu, C., Ghanem, B., Taylor. G., and Goldstein, (2020). FLAG: adversarial data augmentation for graph neural networks. CORR, abs/2010.09891.
[60] Kostochka, A. V. and West, D. B. (2020). On reconstruction of n-vertex graphs from the multiset of (n-E)-vertex induced subgraphs. IEEE Transactions on Information Theory, PP:1-1.
[61] Li, P., Wang, Y., Wang, H., and Leskovec, J. (2020). Distance encoding: Design provably more powerful neural networks for graph representation lcarning. Advances in Neural Information Processing Systems.
[62] Liao, R., Urtasun, R., and Zemel, R. S. (2020). A PAC-bayesian approach to generalization bounds for graph neural networks. CoRR, abs/2012.07690.
[63] Lyle, C., van der Wilk, M., Kwiatkowska, M., Gal, Y., and Bloem-Reddy, B. (2020). On the benefits of invariance in neural networks. arXiv preprint arXiv:2005.0012 00178.
[64] Machara. T. and NT. H. (2019). A simple proof of the universality of invariant/equivariant graph neural networks. CoRR, abs/1910.03802.
[65] Manvel, B. (1974). Some basic observations on kelly's conjecture for graphs. Discrete Mathematics, 8(2):181-185.
[66] Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman. (2019a). Provably powerful graph networks. In Advances in Neural Information Processing Systems, pages 2153-2164.
[67] Maron, H., Fetaya, E., Segol, N., and Lipman, Y. (2019b). On the universality of invariant networks. In International Conference on Machine Learning, volume 97, pages 4363-4371. PMLR.
[68] McKay, B. D. (1997). Small graphs are reconstructible. Australasian Journal of Combinatorics, 15:123-126.
[69] Merkwirth, C. and Lengauer, T. (2005). Automatic generation of complementary descriptors with molecular graph networks. Journal of Chemical Information and Modeling, 15(5):1159-11)
[70] Micheli, A. (2009). Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 2083):99-551.
[71] Micheli, A. and Sestito, A. S. (2005). A new neural network model for contextual processing of graphs. In Italian Workshop on Neural Nets Neural Nets and International Workshop on Natural and Artificial Immune Systems, volume 3931 of Lecture Notes in Computer Science, pages 10 11. Springer.
12

---

[72] Monti, F., Boscaini. D., Masci, J.. Rodolà, E., Svoboda, J.. and Bronstein, M. M. (2017), Geometric deep learning graphs and manifolds using mixture model CNNs. In IEEE Conference on Computer Vision and Pattern Recognition. pages 5425-5434.
[73] Morris, C. (2021). The power of the weisfeiler-leman algorithm for machine learning with graphs. In International Joint Conference on Artificial Intelligence, page TBD.
[74] Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. (2020a). TUDataset: A collection of benchmark datasets for learning with graphs. CoRR, abs/2007.08665
[75] Morris, C., L., Y., Maron, H., Rieck, B., Kriege, N. M., Grohe, M., Fey, M., and Borgwardt, K. (2021). Weisfeiler and leman learning: The story so far. CoRR, abs/21 12.09992.
[76] Morris, C. and Mutzel, P. (2019). Towards a practical k-dimensional Weisfeiler- algorithm. CoRR, 154/1994.1543.
[77] Morris, C., Rattan, G., and Mutzel, P. (2020b). Weisfeiler and leman go sparse: Towards higher-order graph embeddings. In Advances in Neural Information Processing Systems.
[78] Morris, C., Ritzert, M., Fey, M., Hamilton, W. I.,, Lenssen, E., Rattan, G., and Grohe, M. (2019). Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence, pages 4602-4609.
[79] Murphy, R. L., Srinivasan, B., Rao, V., and Ribeiro, B. (2019a). Janossy pooling: Learning deep permutation- invariant functions for variable-sie size inputs. International Conference on Learning Representations.
[80] Murphy, R. L.,, Srinivasan, B., Rao, V., and Riheiro, (2019b). Relational pooling for graph representations.
In International Conference on Machine Learning, pages 4663-4673.
[81] Murphy, R. L., Srinivasan, B., Rao, A. and Ribeiro, B. (2019c). Relational pooling for graph representations. In International Conference Machine Learning, pages 4663-4673.
[82] Niepert, M.. Ahmed, M., and Kutzkov, K. (2016). Learning convolutional neural networks for graphs. In International Conference Machine Learning, pages 2014-2023.
[83] Nýdl. V. (1981). Finite graphs and digraphs which are not reconstructible from their cardinality restricted subgraphs. Commentationes Mathematicue Universitatis Carolinae, 22(2):281-287.
[84] Nýdl, V. (2001). Graph reconstruction from subgraphs. Discrete Mathematics. 235(1-3):335 -411.
[85] Rong, Y., Huang. W., Xu, T., and Huang, (2020), DropEdge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations.
[86] Sato, R., Yamada, M., and Kashima, H. (2020). Random features strengthen graph neural networks. CoRR, abs/2002.03155.
[87] Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. (2009). The graph neural network model. IEEF Transactions on Neural Networks, 20(1):61-80.
[88] Shawe-Taylor, J. (1993). Symmetries and discriminability in feedforward network architectures. IEEE Transactions on Neural Networks, 4(5):816-226
[89] Simonovsky, M. and Komodakis, N. (2017). Dynamic edge-conditioned filters in convolutional ncural
networks on graphs. In IELE Conference on Computer Vision and Pattern Recognition, pages 29-38.
[90] Sperduti, A. and Starita, A. (1997). Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 8(2):714-3) -5.
191] Spinoza, H. and West, D. B. (2019). Reconstruction from the deck of-vertex induced subgraphs. Journal of Gruph Theory, 90(4):497-522.
[92] Stockmeyer, P. K. (1977). The falsity of the reconstruction conjecture for tournaments. Journal of Graph Theory, 1(1):19-25.
[93] Stockmeyer, P. K. (1981). A census of non-reconstrrutabll digraphs, Six related families. Journal of Combinatorial Theory, Series B, (1(2):232-339
194] Stokes, J., Yang, K., Swanson, K., Jin, W., Cubillos-Ruiz, A., Donghia, N., MacNair, C., French, S., Carfrae, I., BloommAAceermnn, 7., Tran, V., Chiappino-Pepe A., Badran, A., Andrews, I., Chory, E.,, Church, G., Brown, E., Jaakkola, T., Barzilay, R., and Collins, J. (2020). A deep learning approach to antibiotic discovery. Cell, 180:688-702.e13.
[95] Taylor, (1990). Reconstructing degree sequenees from delertex-deleted subgraphs. Discrete mathematics, 79(2):207-213.
[96] Ulam, S. M. (1960). A collection of mathematical problems, volume 8. Interscience Publishers. [97] Velickovic, P. Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. (2018). Graph attention networks. In International Conference on Learning Representations.
13

---

[98] Vignac, C.. Loukas, A., and Frossard, P. (2020). Building powerful and equivariant graph neural networks with structural message-passing. In Advances in Neural Information Processing Systems.
[99] Vinyals, O., Bengio, S., and Kudlur, M. (2015). Order matters: Sequence to sequence for sets, arXiv preprint arXiv:5511.06391
[100] Wagstaff, E., Fuchs, F., Engelcke. M., Posner, I,, and Osbome, A. (2019). the limitations of representing functions on sets. International Conference on Machine Learning, pages 6487-6494.
[101] Weisfeiler, B. (1976). On Construction and Identification of Graphs. Lecture Notes in Mathematics, Vol.
558. Springer.
[102] Weisfeiler, B. and Leman., A. (1968). The reduction of graph to canonical form and the algebra which appears therein. Nauchno Techeichcccc Informatsia. 2(9): 16. English translation G. Ryabov is available at
wiw...ii.i.. zeu. wwt.u........// wttp////////oa/ http://///////////////..1../ _aaperr____p________________ translation. ppf
[103] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P. S. (2019). A comprehensive survey graph neural networks. CoRR, 100519.
[104] Wu, Z., Ramsundar, B., Feinberg, E, N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., Pande, (2018). MoleculeNet: A benchmark for molecular machine learning. Chemical Science, 9:513-530.
[105] Xu, K., Hu, W., Leskovee, J., and Jegelka, S. (2019). How powerful are graph neural networks? In International Conference on Learning Representations.
[106] Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K., and Jegelka, S. (2018). Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 5453-5462.
[107] Yehudai, G., Fetaya, E., Meirom, E. A., Chechik, G., and Maron, H. (2020). On size generalization in graph neural networks. CoRR, abs/2010.08853.
[108] Ying, R., You, J., Morris, C., Ren, X., Hamilton, W. L., and Leskovec, (2018). Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, pages 4800-4810.
[109] You, Comes-Selman, J., Ying. R., and Leskovee, (2021), Identity-aware graph neural networks. arXiv preprint PrXii:2101.10322
[110] You, J., Ying. R., and Leskovec, (2019). Position-awand graph neural networks. In International Conference on Machine Learning, pages 7134-7143.
[1II] Yuan, H., Yu, H., Wang, J., Li, K., and Ji, S. (2021). On explainability of graph neural networks via subgraph explorations. arXiv preprint arXiv:2102.051552
[112] Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R., and Smola, J. (2017). Deep sets. In Advances in neural information processing systems, pages 3391-3401.
[113] Zhang, M., Cui, Z.,, Neumann, M., and Yixin, C. (2018). An end-to-end deep learning architccture for graph classification. In AAAI Conference on Artificial Intelligence, pages 4428-4434
[114] Zhou, J., Cui, G., Zhang, Z., Yang, C., Liu, Z. Wang, L., Li, C., and Sun, M. (2018). Graph neural networks: A review of methods and applications. CoRR, abs/181 812.08434.
14


Reviews:
[{"review_id": "oIJwLIkCp1M", "reviewer": "Reviewer_8wLo", "summary": "The paper uses principles of the reconstruction conjecture to devise powerful graph representations addressing the current challenges in graph representation learning. The authors first present a theoretical construction of reconstruction-neural-networks, which is impractical because a universal graph function is not learnable. They then construct an approximate k-reconstruction-GNNs, which replace the graph representation function with GNN layers. The authors also discuss the hierarchy of expressive power and the relation of k-reconstruction networks to GNNs expressive power. They show theoretical guarantees regarding the expressive power of the suggested model, observing that under some conditions, k-reconstruction networks can distinguish graphs that GNNs cannot and even 2-GNNs cannot. While under other conditions, the opposite is true. The authors conduct an extensive set of experiments showing the model’s ability to distinguish several types of structures GNNs cannot, and also conduct some experiments on real-world tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. **Originality**\n\n   The paper provides a novel combination of a classical conjecture from graph theory with graph representation learning. I find the ideas and theory presented in the paper interesting. \n\n2. **Experimental Evaluation**\n\n   - The authors provide a wide dissection of the different configurations of the suggested method illustrating a boost in performance when used with common GNN backbones. \n   - The results on real-life dataset are ok. But the graphs the method is applied to are relatively small, which leads to item (3) below stating my concerns.\n\n**Convergence and Generalization**\n\nIn the approximation of the k-reconstruction GNNs the authors resort to averaging over subsets of the k-decks due to the complexity reasons. My questions are:\n\n**(a)** When using subsets of the k-decks, although the authors provide a theoretical justification in line 242, how does the subset sampling effect the convergence of the training? \n\n**(b)** Could the proposed method generalize well to large graphs? \n\n\n\n---\nAfter reading the author's response and the other reviews, I still lean towards acceptance. Although empirical results are not exceptional, I believe the theoretical concepts and relations to reconstruction conjecture from graph theory are valuable and may lay ground for future advancements in GRL. I hereby keep my score unchanged. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal impacts discussed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "aGCjXUe2yuS", "reviewer": "Reviewer_TP2j", "summary": "This paper bridges ideas from graph theory and graph representation learning to propose a simple but theoretically backed-up strategy to increment the expressive power of Deep Graph Networks (DGNs).\nThe underlying idea should be that, by considering subset of a graph where some vertices are removed, it is possible to discriminate between graphs that would appear identical to the original DGN.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an example of a very good paper. It is well written and organised, the bibliography is wide and complete, and it guides the reader towards the main findings, giving a substantial contribution to the field of graph representation learning. Given the amount of work put in by the authors, most of which was relegated to the appendix, submission to a journal may have been more appropriate.\nThe synthetic experimental part seems solid, but the real-world experiments suffer from the fact that the hyper-parameters have been fixed in advance. Thus, the comparison is actually unfair; it might be possible that on those real-world datasets a proper model selection over GIN, GCN and PNA could have nullified the reported performance improvements of the proposed approach. While the same issue occurs on synthetic datasets, given the way they are created it is less likely that the main results would have changed. While it would be highly appreciable to see the authors fix this mistake, the overall contribution is still undoubtedly valuable. Below there are some requests of clarifications and potential suggestions (mainly regarding style and presentation) that may help improve the mauscript.\n\nline 11: \"any GNNs\" is too strong of a claim. Please consider changing the wording.\nline 24: claiming that the representational limit of DGNs are upper-bounded by the WL-test may not be appropriate, as WL does not consider vertex/edge attributes (see also line 48-50).\nline 37: it may be important to state from the beginning that the \"universal approximation\" property is related to graph isomorphism without attributes (unless I missed something).\nline 60: what do the authors mean by \"the combination of theoretical and empirical results is an additional connection\"? Is it not enough to have incorporated the theoretical insights into the experiments of Section 5?\n\nline 93-99: for someone that is not familiar with the reconstruction conjecture, this part may be vague. Please consider moving it a bit later, perhaps in a different form after the conjecture has been formulated.\nlines 108-109: the term \"edge directions\" becomes clear later on in the paper (line 139). The authors may consider removing this reference or explaining it.\nline 116: Question: if R can distinguish pairs of graphs G,H, is it implied that R distinguishes the individual graphs according to the previous definition? Some clarification may be in order here, perhaps using a more formal notation.\n\nline 143: so far, reconstructible graphs have been defined, wheres reconstructible graph properties have not. What is a reconstructible property (formally)? Is it related to the concept of hereditary property defined later? Please clarify this point.\nline 178: it seems the term $k$ is used both as an index taking different values as well as the exact size of the graphs under consideration. Please consider using a different index to help the reader.\nline 188: similarly, it would be helpful to explicitly state that r^3 is considered more expressive than r^4 and so on.\n\nline 239: what is the purpose of the ratio |S|\\|S_B| ?\n\nlines 251 and 269: it may be confusing that the use of the terms \"more expressive\" and \"less expressive\" is in contrasts with the results at lines 263 and 272, respectively. To be more clear, I was expecting a different kind of result after line 269, something of the kind k-Reconstruction \"<=\" GNN. Perhaps it is just me, but the titles of the paragraph sounded misleading.\n\nline 256: Question: are there any restrictions on the length of the cycle?\n\nline 280: Question: why is it GNN < n-1-reconstruction and not the opposite, given that the authors are conveying the message that n-1-reconstruction is more expressive?\nlines 308-309: the hereditary property definition does not necessarily imply that inductive reasoning holds in general. Please clarify this aspect.\n\nline 329: if there is no hierarchy between DGNs and k-reconstruction GNN, why talking about \"increased\" expressive power in general?\n\nline 397: Question: what is the authors intuition behind the drop in performance of n-3.. n/2 - reconstruction GNNs (which in theory should be more powerful)? Is it because of the sampling approach vs the exact implementation of n-1-reconstruction?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "G8o_205vu7w", "reviewer": "Reviewer_Dm2T", "summary": "This paper proposed several kinds of GNN models that integrate the representations of subgraphs to obtain graph representations.\n\nFirst, the k-reconstruction NN is defined using the representation of a subgraph of size k for the input graph G. Under the reconstruction conjecture, the k-reconstruction NN is proven to be most expressive. \n\nNext, this paper defined the k-reconstruction GNN, which is made by specializing k-reconstruction NN by obtaining representations using GNNs. The computational complexity of a k-reconstruction GNN is exponential with respect to k. Therefore, we proposed a method to approximate it by sampling subgraphs. The relationship between GNNs and k-reconstruction GNNs is discussed. Concretely, the k-reconstruction GNN is not less expressive than GNN if k is not too small. Also, k-reconstruction GNN is not more expressive than GNNs when k is small.\n\nFinally, the proposed k-reconstruction GNN was applied to synthetic and real datasets (OGB). This paper showed that the proposed model improved the accuracy of the proposed GNN compared to baseline GNNs.", "questions": "", "limitations": "", "rating": 5, "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": "### Strength\n\n- [S1] We can apply the k-reconstruction GNN to any GNN for graph prediction tasks (in the experiments, this paper used GCN, GIN, and PNA).\n- [S2] The proposed model is provably no worse than GNNs in terms of expressive power.\n\n### Weakness\n\n- [W1] I would say that there is room for improvement in the organization of the paper.\n- [W2] Also, I think there is room for improvement in the proof of mathematical statements.\n- [W3] Existing research employed the idea of reconstruction theory for the theoretical analysis of structured representation learning. Therefore, I think the novelty of the paper in this respect is limited.\n\n### Soundness (Do theorems and experiments answer research questions, assuming they are correct?)\n\n- [So1] The research question of this paper is to explore the relationship between graph theory and graph representation learning (GRL). More precisely, this paper tried to create a simple, scalable, and expressive GRL model using reconstruction theory. For the following reasons, I think that this paper is an answer to the research question from a theoretical perspective.\n  - [So1.1] The proposed k-Reconstruction GNN is not less expressive than the corresponding GNN (Theorem 1, 2).\n  - [So1.2] When the true distribution satisfies the hereditary property, the proposed architecture can reduce the variance of the empirical loss (Theorem 3). However, it requires strong convexity assumptions about the loss function and the architecture.\n- [So2] As for the experimental side, I have both positive and negative opinions.\n  - [So2.1] The proposed model is effective in the synthesis and real datasets of the graph classification task (Table 1, 2).\n  - [So2.2] Table 1 shows that vanilla GIN and GCN can recognize cycles to some extent and that the advantage of the reconstruction model is not large.\n  - [So2.3] As for GIN and GCN, the proposed model has improved the prediction accuracy on the OGB dataset, demonstrating the empirical effectiveness.\n\n### Correctness (Are derivation of theorems and experiments correct?)\n\n- [C1] I think the statement and proof of the theorem are written informally. Therefore, it was difficult for me to verify its correctness. I would like this paper to define concepts more mathematically rigorously write the statement more formally.\n  - [C1.1] For Proposition 1, I tried to give formal proof by myself, but I could not do so, and I could not verify its correctness. \n  - [C1.2] Definition 6, I did not understand what was meant by \"give a unique representation to a graph sampled with probability 1-ε\".\n  - [C1.3] In Definition 6, ε-universal is defined for a distribution D on the graph. On the other hand, (ε, k)-universal is defined for the induced subgraph. Is this correct that (ε, k)-universal is defined for the probability distribution on a graph of size k, obtained by sampling the graph from D and then uniformly randomly sampling more subgraphs of size k from it?\n\n\n**Novelty and Significance (Do the paper have novel points? If so, are they significant?)**\n\n- [N1] When we consider representation learning for graph structures, it is natural to compute representations for subgraphs and aggregate them. The idea of using subgraphs in a graph for GRL has been used in Graph Homomorphism Network (GHN) [Nguyen and Maehara, ICML2020], Graph Substructure Networks (GSN) [19], and Structural Message Passing (SMP) [Vignac et al., NeurIPS2020]. However, this paper has novel points because the proposed method of this paper is different from these works in how we extract subgraph information.\n- [N2] As pointed out by this paper, Shawe-Taylor [88] and Bouritsas et al. [19] used reconstruction theory to guarantee expressive power. Therefore, the novelty of the use of reconstruction theory for GRL is limited. On the other hand, this paper is novel because it pointed out the problems of these architectures from the viewpoint of computational complexity and proposes a model with reduced computational complexity.\n- [Nguyen & Maehara, ICML2020] http://proceedings.mlr.press/v119/nguyen20c.html\n- [Vignac et al., NeurIPS2020] https://proceedings.neurips.cc//paper_files/paper/2020/hash/a32d7eeaae19821fd9ce317f3ce952a7-Abstract.html\n\n**Clarity (Is the paper clearly written?)**\n\n- [Cl1] I would say that there is room for improvement in the clarity of the paper.\n- [Cl2] I think there is room for improvement in the proof of mathematical statements.\n- [Cl3] In addition, this paper introduced several similar concepts (k-Reconstruction NN, full Reconstruction NN, and Reconstruction GNN). It was difficult for me to grasp the relationship between them. So, I would like this paper to clarify the relationship between them more explicitly.\n\n**Other Comments**\n\n- [O1] In Theorem 1, with respect to which variable the order of $o(1)$ is written?\n- [O2] Some model definitions have $n$ (e.g. $(n-1)$-reconstruction GNN). Is it assumed that such models accept only graphs of size $n$ as input?\n- [O3] 2-WL is undefined. If it is to be used in mathematical statements, its definition should be clarified.\n- [O4] In l.156--164 and Appendix C, existing results on graph reconstruction are presented. It is interesting in itself, but I could not understand how it is related to the model proposed in this paper. For example, does it provide background ideas for the proposed model? Or can we analyze the expressive power of the proposed model by these existing studies? \n- [O5] It was difficult to grasp the meaning of l.215--223 when I read it for the first time. This paragraph have what is done in this section and what is done in the Appendix in an interleving manner. It might hindered my understanding.\n- [O6] Is it correct that Var in Theorem 3 is the variance with respect to both the probability distribution $P(G, Y)$ and the randomness coming from sampling a subgraph from $G$?\n- [O7] In l. 910, I think it is better to write something like $\\mu_k(G) = E_{H\\sim \\mathcal{G}_k(G)}[\\mu(H)]$. Also, I think it is better to state explicitly that H is uniformly sampled from $G_k(G$).\n- [O8] For Theorem 1, I want to discuss the condition of $\\ell$ (or equivalently $k$) in more detail because if I understand correctly, it just borrowed from conditions of the existing studies. Can we think that l should be sufficiently small (specifically, $O(\\log n/\\log \\log n)^{1/2})$)?\n\n\n### Post-rebuttal comments\n\nMy main concern in the initial review comments was about the accuracy of mathematical statements. I asked them to the authors and they answered my questions properly. Taking them into consideration, although I keep my rating (5), I do not object to accepting the paper, providing that the authors improve the mathematical descriptions in the camera-ready version.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- [L1] The authors discussed the problem of computational complexity of k-Reconstruction NN in l.208.\n- [L2] The authors showed the theoretical limitation k-Reconstruction GNN in terms of expressive power.\n", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "1m_YuhCMZ5Q", "reviewer": "Reviewer_UtnL", "summary": "This paper introduced graph reconstruction theory to GNN area and use it to improve the expressiveness of GNNs with some formal theoretical proof. The theoretical framework is not tractable but the author proposed using sampling based method and combine with GNN to  approximate k-reconstruction neural network. Some experiments over synthetic datasets and OGB graph datasets show some improvement over existing message passing based network. ", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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. Originality: although the idea is not presented before, the k-reconstruction idea that views graph as a set of k-subgraphs has some connection to k-WL or k-GNN. As we know that each node in k-WL is a k-size super node which corresponds to a k-subgraph. And the k-WL algorithm over these k-size super nodes are permutation invariant which can be looked as implementation of the f_w function used in the paper. I wish the author provide more formal analysis to connect these two type of models, figuring out their difference and similarity. Nevertheless, from my end the presented k-reconstruction GNN is too complicated and is more like a toy for theoretical analysis instead of real-world useable model. \n\n2. Quality: the author provides a great literature review for expressiveness of GNN. The author also introduced the graph reconstruction theory in section 2. For the definition of reconstructible function, I wish the author can provide more insight of why introducing these defnitions in section 2. A trivial example of reconstructible function is a function that always output a constant representation for all graphs. In section 4 the author use these reconstructible function to characterize the expressiveness of k-reconstruction neural network, but before this I don't see any value of introducing these definitions. I suggest the author rewrite the section 2 part with giving some insight of why introducing these definitions from graph reconstruction theory. For section 3, the presented model looks like theoretical toy model to me. This is very similar to the relational pooling paper but I don't get the value of this model . The contribution of relational pooling is more like the universal approximation ability on graphs but this has been studied extensively. For section 4, the author provided several theorems to characterize the expressiveness of the designed k-reconstruction networks, however these theoretical results are not \"tight\" at all, most of these theorems just tell us that the k-reconstruction is not worse than GNNs. No amazing theoretical result shows that the k-reconstruction network achieves the best expressiveness (higher than k-WL/k-FWL). Also, the improvement on real world datasets are not much noticeable although it does show some ability in synthetic dataset. \n\n3. Clarity: In general the written is ok, but need some improvement to provide more insight in the flow to help reader understand the paper much easier. \n\n4. Significance: my impression is that the paper is more for theoretical analysis instead of real-world usage. I would like to see some more practical model that can make use of the author's analysis. The author did lots of approximations and it's really hard to know how much expressiveness left after these approximations. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agreed that this work provides a valuable contribution to the GNN research by expanding on the known connections between graph reconstruction theory with graph representation learning. While sometimes falling behind more powerful architectures, the proposed method is shown to consistently improve upon vanilla GNN. 

The reviewers originally expressed some concerns about the rigorousness of the mathematical statements. However, these were addressed during the rebuttal phase. 

I thus recommend the (revised) paper for publication.
Decision: Accept (Poster)