Fundamental Limits in Formal Verification of Message-Passing Neural Networks
Authors: Marco Sälzer
Martin Lange
Venue: ICLR 2023 poster (2023)
Keywords: formal verification
graph neural networks

Abstract: Output reachability and adversarial robustness are among the most relevant safety properties of neural networks. 
We show that in the context of Message Passing Neural Networks (MPNN), a common Graph Neural Network (GNN) model, 
formal verification is impossible. In particular, we show that output reachability of graph-classifier MPNN, 
working over graphs of unbounded size, non-trivial degree and sufficiently expressive node labels, cannot be verified formally: there
is no algorithm that answers correctly (with yes or no), given an MPNN, whether there exists some valid input to 
the MPNN such that the corresponding output satisfies a given specification. However, we also show that 
output reachability and adversarial robustness of node-classifier MPNN can be verified formally when a limit on
the degree of input graphs is given a priori. We discuss the implications of these results, for the purpose of
obtaining a complete picture of the principle possibility to formally verify GNN, depending on 
the expressiveness of the involved GNN models and input-output specifications.

Published as a conference paper at ICLR 2023
FUNDAMENTAL LIMITS IN FORMAL VERIFICATION OF HESSAGE-PASSING NEURAL NETWORKS
Marco Sälzer
Martin Lange
School Electr. Eng. and Computer Science University of Kassel, Germany
School Electr. Eng. and Computer Science University of Kassel, Germany ma martin. partin.langeen lange@uni -ksssel .de
ma rco. sael zer@un -assell..... .de
ABSTRACT
Ouiput reachability and adversarial robustness are among the most relevant safety properties of neural networks. We show that in the context of Message Passing Neural Networks (MPNN), common Graph Neural Network (GNN) model, for- mal verification is impossible. In particular, we show that output reachability graph-classifier MPNN, working over graphs of unbounded, but finite size, non- trivial degree and sufficiently expressive node labels, cannot be verified formally: there is algorithm that answers correctly (with yes no), given graph- classifier MPNN, whether there exists some valid input to the MPNN such that the corresponding output satisfies given specification. However, we also show that output reachability and adversarial robustness of node-classifier MPNN can be verified formally when limit on the degree of input graphs given a priori. We discuss the implications of these results, for the purpose of obtaining com- plete picture of the principle possibility to formally verify GNN, depending on the expressiveness of the involved GNN models and input-output specifications.
INTRODUCTION
The Graph Neural Network (GNN) framework, i.e. models that compute functions over graphs. has become a goto technique for learning tasks over structured data. This is not surprising since GNN application possibilities are enormous, ranging from natural sciences (Kipf et al. (2018): Fout et al. (2077) over recommender systems (Fan et al. 2 to general knowledge graph applications which itself includes a broad range of applications (Zhou et al. (2020)). Naturally, the high interest in GNN and their broad range of applications including safety-critical ones, for instance traffic situations, impose two necessities: first, solid foundational theory of GNN is needed that describes possibilities and limits of GNN models. Second, methods for assessing the safety of GNN are needed, in the best case giving guarantees for certain safety properties.
Compared to the amount of work on performance improvement for GNN or the development of new model variants, the amount of work studying basic theoretical results about GNN is rather limited. Some general results have been obtained as follows: independently, Xu et al. (019)) and Morris al. (2019) showed that GNN belonging the model of Message Passing Neural Net- works (MPNN) (Gilmer et al. (017)) are non-universal in the sense that they cannot be trained distinguish specilic graph structures. Furthermore, both relate the expressiveness of MPNN to the Weisfeiler- graph isomorphism test. This characterisation is thoroughly described and extended by Grohe (202T). [oukas (2020) showed that MPNN can be Turing universal under cer- tain conditions and gave impossibility results of MPNN with restricted depth and width for solving certain graph problems.
Similarly, there is a lack of work regarding safety guarantees for GNN, or in other words work on formal verification of GNN. Research in this direction is almost exclusively concerned with certifying adversarial robustness properties (ARP) of node-classifying GNN (see Sect. [.] for details). There, usually considered ARP specify a set of valid inputs by giving a center graph and bounded budget of allowed modifications and are satisfied by some GNN if all valid inputs classified to the same, correct class. However, due to the nature of allowed modifications, these properties cover only local parts of the input space, namely neighbourhoods around a center graph.

---

Published as a conference paper at ICLR 2023
This local notion of adversarial robustness is also common in formal verification of classical neural networks (NN). However, in NN verification, the absence of misbehaviour of a more global kind is adressed using so called output reachability properties (ORP) (Huang et al. (2020)). A common choice of ORP specifies a convex set of valid input vectors and a convex set of valid output vectors and is satisfied by some NN if there is valid input that leads valid output. Thus, falsifying ORP, specifiying unwanted behaviour as valid outputs, guarantees the absence of respective misbehaviour regarding the set of valid inputs. To the best of our knowledge there currently is no research directly concerned with ORP of GNN.
This work adresses both of the above mentioned gaps: we present fundamental results regarding the (im-) mio-iiiiiiillity of formal verification of GNN. We prove that in direct contrast to formal verifi- cation of NN there are non-trivial classes of ORP and ARP used for MPNN graph classification, that cannot be verified formally. Namely, as soon as the chosen kind of input specifications allows for graphs of unbounded, but finite size, non-trivial degree and sufficiently expressive labels, formal verification is no longer automatically possible in the following sense: there is algorithm that, given an MPNN and specifications of valid inputs and outputs, answers correctly (yes/no) whether some valid input is mapped to some (in-)valid output. Additionally, we show that ORP and ARP of MPNN used for node classification are formally verifiable as soon as the degree of valid input graphs is bounded. In the ARP case, this extends the previously known bounds.
The remaining part of this work is structured as follows: we give necessary definitions in Sect. 2 and a comprehensive overview of results in Sectß] In Sect. 4 and Sect. [5] cover formal arguments, with purely technical parts outsourced to App. A and B Finally, we discuss and evaluate our possibility and impossibility results in 6
1.1 RELATED WORK
This paper adresses fundamental questions regarding formal verification of adversarial robustness and output reachability of MPNN and GNN in general.
Günnemann (2022) presents survey on recent developments in research on adversarial attack, de- fense and robustness of GNN. We recapitulate some categorizations made in the survey and rank the corresponding works in our results. First, according to Günnemann (2022) most work consid- ers GNN used for node-classification (for example, Zügner et al. (2018); Dai et al. (2018); Wang let al. (2020;; Wu et al. (2019) and among such most common adversarial modifications are edge modifications of a fixed input graph (Zügner et al. (2018); Zügner & Günnemann (201)); Ma et al.
(020 ) but also node injections or deletions are considered (Sun et. (2020); Geisler et al. (222 ) In all cases, the amount of such discrete modifications is bounded, which means that the set of input graphs under consideration is finite and, thus, the maximal degree is bounded. Any argument for the possibility of formal verification derivable from these works is subsumed by Theorem here.
Additionally, there is work considering label modifications İüügner et 20188 Wu et al. (2019): Takahashi 2019)), ), but only in discrete settings or where allowed modifications are bounded by box constraints. Again, this is covered by Theorem 2 There is also work on adversarial robustness of graph-c craph-classifier GNN (Jin et al. (2020): CCen et al. (2020); [Bojcheskki et al. (2020)). In all cases, the considered set of input graphs is given by a bounded amount of structural pertubations to some center graph. Therefore, this is no contradiction to the result of Corollary I the size of considered graphs is always bounded.
As stated above, to the best of our knowledge, there currently is no work directly concerned with output reachability of MPNN or GNN general.
PRELIMINARIES
Undirected, labeled graphs and trees. A graph G is a triple (V, D, L) where V is a finite set of nodes, DD C V2 symmetric set of edges and L V + R" is a labeling function, assigning a vector to each node. We define the neighbourhood Neigh(v) of a node u as the set {e' (v, E D). The degree of G is the minimal d N s.t. for all V we have [Neigh(v)] S d. If the degree of G is d then G is also called a d-graph. A tree B is a graph with specified node up, called the root, denoted by (V, ID, I,, vo) and the following properties: V Vo U V, U... VA where Vo (vo). all V,
2

---

Published as a conference paper at ICLR 2023
pairwise disjoint, and whenever (v, r') E D and E V, then e' E V4+1 or vice- vice-versa, and for each node v E V, 2 there is exactly one o' E Vi-1 such that (u', E D. We call & the depth of graph B. A d-tree is d-graph that is a tree.
Neural networks. We only consider classical forward neural networks using ReLU activa- tions given by re(x) = max(0. x) across all layers and simply refer to these as neural networks (NN). We use relatively small NN building blocks to describe the structure of more complex ones. We call these small NN gadgets and typically define a gadget by specifying its computed function. This way of defining a gadget is ambiguous there could be several, even infinitely many NN computing the same function. An obvious candidate will usually be clear from context. Let N be a NN. We call N positive if for all inputs æ we have N(x) O. We call N upwards bounded if there is á with á E IR such that N I ât for all inputs T.
Message passing neural networks. A Message Passing Neural Network (MPNN) Gilmer et al. (017) consists of layers 1,...,,2 followed by a readout layer fread, which gives the overall output of the MPNN. Each regular layer I computes (x. M) comb,(x, agg, (M)) where M is a multiset, a usual set but with duplicates, agg, an aggregation function, mapping a multiset of vectors onto a single vector, comb; a combination function, mapping two vectors of same dimension to a single one. In combination, layers I,....du lx map each node v E V of a graph G = (V, D. L) to a vector x in the following, recursive way: a!. = [(v)) and a. = (1x Mi-+) where Mr-I is the multiset of vectors x 1-- of all neighbours o' Neigh(v). We distinguish two kinds of MPNN, based on the form of lead: the readout layer fread of node-classifier MPNN computes feaad (v,, MI²) raad) where v is some designated node, M is the multiset of all vectors xy and read maps a single vector onto a single vector. The readout layer of graph-classifie MPNN computes fraad (MT*) read ). We denote the application of a node-classifier MPNN N to 9 and v by N(G, and the application of a graph-classifier N to G by (g). In this paper, we make common choices (ef. Gilmer et al. 2017);; [arceló et al. (2020); Wu et al. (2021)) for the form of the aggregation, combination and readout parts: agg, (M) ZeEM œ. comb,(x, MD) = [x,, agg, (M)) where N; a NN and read = N, 2) respectively read(x) = (x) where, again, N, is NN.
Input and output specifications. An input specification over graphs (resp. pairs of graphs and nodes) ip is some formula, set of constraints, listing etc. that defines a set of graphs (resp. pairs of graphs and nodes) S.g. If graph G (resp. pair (G, v)) is included in S. we say that is valid regard- ing &p or that it satisfies 42, written G F 99, resp. (G, v) } yp Analogously, an output specification over vectors &i defines a set of valid or satisfying vectors of equal dimensions. Typically, we denote a set of input specifications by & and set of output specifications by V.
Formal verification of adversarial robustness and output reachability properties. An adver- sarial robustness property (ARP) P is a triple p = (N, p, v)) where N is a GNN, ip some input specification and & some output specification. We say that P holds iff for all inputs }= yp we have [(I)
} vb. We denote the set of all ARP with y E T &/ E T and graph-classifie or node-classifier by ARP ARRgraph ( 1 respectively ARP node AR..ndee ) We simply write ARP( V) when make no distinction between graph- or node-classifiers. Analogously, an output reachability property (ORP) i a triple Q = (N,4p, s0, v, which holds iff there is input / F oP such that N (()) } vb, and we define ORP graph ( @b )) ORP node ( 1 and ORP( v accordingly. Let P be set of safety properties like ARP graph (1, v or ORPPode ( )) We say that P is formally verifiable IT if there is an algo- (completeness)
rithm A satisfying two properties for all P P: first, if P holds then A(P) and, second, if A(P) = T then P holds (soundness).
3 OVERVIEW OF RESULTS
This work presents fundamental (im-)possibilitt results about formal verification of ARP and ORP of MPNN. Obviously, such results depend on the considered sets of specifications. All specification sets used in this work are described in detail in Appendix A
In other words, the problem of determining, given an MPNN N and descriptions of valid inputs and outputs, whether the corresponding property holds, is decidable.
3

---

Published as a conference paper at ICLR 2023
First, establish connection between ORP and ARP. For set of output specifications v define V/ = g x/2 w/ where v/ defines exactly the set of vectors which do not satisfy s/. We have that V = V
Lemma 1. ORP(O, V) formally verifiable if and only if AR, V) is formally verifiable.
Proof. Note that the ARP (N, sp, v)) holds iff the ORP (N, 15) does not hold. Hence, any al- gorithm for either of these can be transformed into an algorithm for the other problem by first complementing the output specification and flipping the yes/no answer in the end.
This connection between ARP and ORP, while usually not given fomally, is folklore. For example, see the survey by Huang et al. 22020) describing the left-to-right direction of Lemma !
Our first core contribution that, in contrast to verification of ORP of classical NN, there are natural sets of graph-classifier ORP, which cannot be verified formally. Let Punb be a set of graph specifica- tions, allowing for unbounded, but finite size, non-trivial degree and sufficiently expressive labels, and let V eq be set of vector specifications able to check if certain dimension of a vector is equal some fixed integer.
Theorem (Section
ORP graph (uub, Vog) is not formally verifiable.
Let leg be set of vector specifications, satisfied by vectors where for each dimension there is another dimension which is greater equal. Now, celaass == Ve is set of vector specifications, defining vectors where a certain dimension is greater than all others or, in other words, outputs which
can be interpreted an exact class assignment. We can easily alter the proof of Theorem I to argue
that ORP graph (Pum unb V leq) is also not formally verifiable (see Section Then, Lemma implies g the following result for ARP
MPNN.
Corollary 1. ARP graph (uunb Velass) is not formally verifiable.
Thus, as soon consider ORP ARP of graph-classifier MPNN over parts of the input space, including graphs of unbounded, but finite size, with sufficient degree and expressive labels, it is no longer guaranteed that they are formally verifiable.
To better understand the impact of our second core contribution, we make a short note on classical NN verification. There, a common choice of specifications over vectors are conjunctions of linear inequalities Σ C;;; S where G, are rational constants and x; are dimensions specifications define convex sets and, thus, we call the of all such specifications Vi Vonnv Let Pouund be a set of graph-node specifications, bounding the degree of valid graphs and using constraints on labels in a bounded distance the center node which can be expressed by vector specifications as described above 2 Now, it turns out that as soon as we bound the degree of input graphs, ORP of node-classifier MPNN with label constraints and output specifications from v Vconv can be verified formally.
vector. Such
Theorem 2 (Section 5). ORPnode node (bbuund, & conv) is formally verifiable.
Again, Lemma 1
implies a similar result for ARP of node-classifier MPNN. Obviously, we have C T conv-
V class
Corollary 2. ARP node (bbunnd, Mllass) is formally verifiable.
This byproduct of Theorem considerably extends the set of input specifications for which ARP of node-classifier MPNN is known be formally verifiable. particular, the literature (see Sec- tion 1.1b gives indirect evidence that ARP node (Pnnigh, Vlasss can be verified formally where & &nnigh a set of specifications defined by center graph and a bounded budget of allowed structural modi- fications well as label alternations restricted using box constraints, which can be expressed using vector specifications of the form given above. Thus, Pneigh C Pbound-
The results above, in addition to some immediate implications, reveal major parts of the landscape of MPNN formal verification, depicted in Figure The horizontal, resp. vertical axis represents sets
We assume that model checking of specifications from @ouund is decidable. Otherwise, verification of corresponding ORP becomes undecidable due trivial reasons.
4

---

Published as a conference paper at ICLR 2023
oupal spec.
verifable
veriiable
verifable (lieerture)
(Th22)
V conv
OR.
hode
(Cor2)
(Cel.)
V
class
ARP
node
graph
(1h.1)
Veg
ORP
graph
s neigh
bound
Pubb
imput spec.
Figure 1: Overview of core results.
of input, resp. output specifications, loosely ordered by expressiveness. The three most important impressions to take from this visualisation are: first, the smaller the classes of specifications, the stronger an impossibility result becomes. Note that Theorem [ and Corollary [ naturally extend to more expressive classes of specifications (indicated by the red, squiggly arrows and to the right). Second, results about the possibility do formal verification grow in strength with the expressive power of the involved specification formalisms; Theorem 2 and Corollary 2 extend naturally to smaller classes (indicated by the green, squiggly arrows down and the left). Third, the results presented here are not ultimately tight in the sense that there is part of the landscape, between Pbound and a unb. for which the status of decidability of formal verification remains unknown.
Remark An interesting observation that formal verification of ORP of node-classifier MPNN is impossible soon as we allow for input specifications that can express properties like Butv'' Err, v²), stating that valid graph must contain "master node" that is connected all other nodes. Then the same reduction idea seen in Section 4 can be used to show that formal verification is no longer possible.
4 THE IMPOSSIBILITY OF FORMALLY VERIFTYING ORP AND ARP OF GRAPH-CLASSIFEER MPNN OVER UNBOUNDED GRAPH CLASSES
The ultimate goal of this section is to show that ORP graph Punb, Veg) is not formally verifiable. Note that we use weak form of Pubb here. See Appendix A for details. To do so, we relate the formal verification of ORP graph unb Vea) to the following decision problem: given a graph-classifier N with a single output dimension, the question is whether there is graph G such that NGG) = 0. We call this problem graph-classifee classifier problem (GCP).
Lemma 2. If GCP is undecidable then ORP graph (uub, Vog) is not formally verifiable.
Proof. By contraposition. Suppose ORP graph ( Veg) was formally verifiable. Then there is an algorithm A such that for each (N, true, y 0) ORP graph ( unb. Feg) we have: A returns T and only if (N, true, 0) holds. But then A can be used to decide GCP.
Using this lemma, in order to prove Theorem I it suffices to show that GCP undecidable, which we will do in the remaining part of this section. The proof works as follows: first, we define satisfi- ability problem for a logic of graphs labeled with vectors, which we call Graph Linear Programming (GLP) as it could be seen as extension of ordinary linear programming on graph structures. We then prove that GLP is undecidable by a reduction from Post (1946)'s Correspondence Problem (PCP). From the form of the reduction we infer that the graph linear programs in its image are of a particular shape which can be used to define a therefore also undecidable fragment, called Discrete Graph Linear Programming (DGLP). We then show how this fragment be reduced to GCP, thus establishing its undecidability in a way that separates the structural from the arithmetical parts in reduction from PCP GCP. As side-effect, with GLP obtain relatively natural

---

Published as a conference paper at ICLR 2023
b b a
a
b
Figure A solution for the PCP instance Po-
undecidable problem on graphs and linear real arithmetic which may possibly serve to show further undecidability results similar graph neural network verification problems.
4.1 FROM PCP TO GLP
We begin by defining the Graph Linear Programming problem GLP. Let X = {xI...., Xn) be set of variables. node condition vp a formula given by the syntax
6 E 0;x; + (xx;) c c p
where aj, bj.b E Q Intuitively, the x, are variables for a vector of real values, constituting graph's node label, and the operator @ describes access to the node's neighbourhood, resp. their labels.
We write sub(y) for the set of subformulas of &p and Var(y) for the of variables occurring inside sp. We use the abbreviation t = e for t A -t S -c.
Let G -V, Di L) be graph with L V - R". A node condition yp induces set of nodes of g, written [ and is defined inductively follows.
v E E
1 a; + by (@x,) S c]9
iff
Σ acI(v); + by b:(EEENN. I(,'))) se
iff
e E 11 n 1
e 1 1p2ll
iff
12 1
E | then we say that satisfies so. A graph condition vp is a formula given by the syntax a;x; S & A v. where ai, E Q. The semantics of tb, written [v]. the subclass of graphs (V, with L: V:V- + R² fsuch that
IE axx S cl
iff iff
se.
[w A mb2]
ge [
Again, ifg
[ then say that & satisfies vb.
The problem GLP is defined as follows: given a graph condition ai and a node condition over the same set of variables X {x,,.... X,,) decide whether there is graph G (V, D, L) with V Rn such that 9 satisfies v and all nodes in G satisfy ş. Such an L = (w), sp) called graph linear program, which also abbreviate GLP. It will also be clear from the context whether GLP denotes a particular program or the entire decision problem.
As stated above, show that GLP is undecidable via reduction from Post's Correspondence Problem (PCP); given P = {a) B1), (a2, .2),..., (ak, Bx)} S E* x Σ" for some alphabet Σ, decide whether there is non-empty sequence of indices i1, i2 ..., i from {1....,A k} such that Oú OiS Q2 Br,Br, ... B The a; 3r are also called tiles. PCP is known to be undecidable when Σ 2 2, i.e. we can always assume
(a, b). For example, consider the solvable instance Po {aab,, au), (b, abb), (bu, b6)]. It is not hard to see that / 1, 1, 2 is solution for Po- Furthermore, the corresponding sequence of tiles can be visualised as shown Figure The upper word is produced by the a, parts of the tiles and the lower one by the B,. The end of one and beginning the next tile are visualised by the vertical part of the step lines.
Theorem 3. GL.P undecidable.
Proof sketch. We sketch the proof here and give full version in Appendix B.I B.I by establishing a reduction from PCP. The overall idea is to translate each PCP instance P a GLP Lp with the property that P solvable if and only if Lp is satisfiable. Thus, the translation
The proof is done

---

Published as a conference paper at ICLR 2023
yellow
green
blue
Figure 3: Encoded solution I of PCP instance Po-
must be such that Lp is only satisfiable by graphs that encode a valid solution of P. The encoding depicted for the solution of Po shown in Figure 2 in form of solid lines and nodes in Figure The word W/ = 0r is represented by the chain of yellow nodes from left to right in such way that there node for each symbol w; of wn- If w; a then Xa 1 and X 0 of the corresponding node and vice-versa if w, = b. Analogously, 31 13 is represented by the blue chain. The borders between two tiles are represented as edges between the yellow and blue nodes corresponding to the starting positions of tile. The encoding as graph uses additional auxiliary nodes, edges and label dimensions, in order to ensure that the labels along the yellow and blue nodes indeed constitute a valid PCP solution, i.e. the sequences of their letter labels are the same, and they are built from corresponding tiles in the same order. In Figure 3 indicated by the dashed parts.
these auxiliary nodes and edges are
GLP seems to be too expressive in all generality for a reduction to GCP, at least it does not seem (easily) possible mimic arbitrary disjunctions in an MPNN. However, the node conditions ip resulting from the reduction from PCP to GLP are always of a very specific form:
s A Paiser where Pdiser = Ases V Mee Lt m with M C N enforces dimensions x; to be discrete and y has the following property. Let X be the set of dimensions not discretized by Paiser. For each PP P2 E sub(y') ) the case that Var (ar( n disjunction in sp' at most one disjunct contains non-discretised dimensions. We call this fragment of GL. Discrete Graph Linear Programming (DGL.P). The observation that the reduction function from PCP constructs graph linear programs which fall into DGLP (see Appendix B.1 for details) immediately gives us the following result.
Var(pp) nx = 0. In other words, in each
Corollary 3. DGLP is undecidable.
4.2 FROM DGLP TO GCP
Theorem 4. GCP is undecidable.
Proof. By reduction from DGLP. Given a DGLP (p, we construct an MPNN N: that gives a specific output, namely 0, if and only if its input graph 9 satisfies L and therefore is a witness for L E GLP. Let m, n R with m S and MI (11, f2,, ix} C N such that i < i for all jE {l...., -1).
1}. We use the auxiliary gadget (x E [m; = re(re(x - n) re(x (n + 1))
re(m- x) +r(mm - x)) to define the gadgets
(x S m) = re m) re(x (m + 1))) and
(x M) r- E [+): プド= re (4 ((--1-6) (re(x- (,46++1) ro( t x))))
Each of the gadgets above fulfils specific properties which can be inferred from their functional forms without much effort: let R. Then. (r S m) 0 if and only if < m, and (r E M)) 0 and only r E M. Furthermore, both gadgets are positive and (x S m) is upwards bounded for all m by with the property that Ir ml > implies (r m) 1. We give formal proof in
Appendix B. We use (x m) as an abbreviation for (-x < m)) + (x S m).
The input size of Ne equals the amount of variables occurring in & and v. Nc has one layer with two output dimensions ydiser and ylnd and the readout layer has single output dimension y". The subformula &diser Ave V /mm.. X; m is represented by ydiser Eier (x, M.) and then checked using (yd 0) in the readout layer.
The remaining part of o is represented in output dimension yoon in the following way. Obviously, an atomic <-formula is represented using (x m) gadget. A conjunction ş 422 represented
7

---

Published as a conference paper at ICLR 2023
Figure 4: Tree-model property of two-layered MPNN.
by sum of two gadgets fi + f2 where fi represents Pi. For this to work, we need the properties that all used gadgets are positive and that their output is when satisfied.
To represent disjunction ş0i Vy22 where Si and f2 are the gadgets representing yo resp. s22, we need the fact that a DGLP. W.l.o.g. suppose that yp1 only contains discrete variables and that yriser satisfied. Then we get: if (o is not satisfied then the output of fi must be greater equal to 1. The reason for this is the following. If the property of some (x S mm)ggeeet not satisfied its output must be 1, still under the assumption that its input includes discrete variables only. Furthermore, as (x S m) is positive and upwards bounded, the value of f2 must be bounded by some value & E R>00 Therefore,
can represent the disjunction using re(f2 k re(1 fi)). Note that this advanced gadget is also positive and upwards bounded. Again, the value of yoond is checked in the readout layer using (Yaond = 0)- The graph condition y is represented using a sum of (x S m) gadgets.
Thus, effectively translate DGLP L into MPNN Ne such that there is graph with Nc(9) = 0 if and only g satisfies C, i.e. L E DGLP. This transfers the undecidability from DGLP to GCP.
Proof of Theorem The statement is an immediate consequence of the results of Theorem and
Lemma 2
The proof for Corollary follows the exact same line arguments, but we consider the following decision problem: given a graph-classifier N with two output dimension, the question is whether there is graph 9 such that (N) S 2)) (N(G), S NG)22). We call this GCP Obviously, the statement of Lemma 2 also holds for GCP and ORP graph (boundd Vl ). Proving that GCP is undecidable is also done via reduction from DGLP with only minimal modifications of MPNN Ne constructed in the proof of Theorem 4 add second output dimension to N2 which constantly outputs O. The correctness of the reduction follows immediately.
THE POSSIBILITY OF FORMALLY VERIFTYING ORP AND ARP OF NODE-CLASSIFIER MPNN OVER DEGREE BOUNDED GRAPH CLASSES
we argue that there is naive algorithm verifying ORP node (ounnd V Vconv) formally. Consider a node-classifier N with layers and consider some graph G with specified node e such that (G,,t) v) y. The crucial insight is that there is tree B of finite depth lo and with root to such that N(B, vo) = y. The intuitive reason for this that N update the label of node using information from neighbours of of distance most k. For example, assume that h = 2 and G, v are given as shown on the left side of Figure 4 where the information of a node, given by its label, is depicted using different colours y (yellow), b (blue), (red), (green) and (pink). As N only includes two layers, information from the unfilled (white) nodes are not relevant for the computation of N(G, v) as their distance is greater than Take the tree B on the right side of Figure 4 We get that (GG, v) = N(B, un).
In order prove Theorem
Proof of Theorem 2 First, we observe the tree-model property for node-classifier MPNN over graphs of bounded degree: let (N, yp, v) E ORP node (ooundd, V Pconw) where N has kv' layers and yp bounds valid graphs to degree d N and constraints nodes in the k ---neigbbouroood of the center node. We have that (N, sp e) holds if and only if there is d-tree of depth = max(k' (''''''''' k²) with
root Up such that (B, vp) F oo and N N(B, vn) } vb. We prove this property in Appendix B.3
8

---

Published as a conference paper at ICLR 2023
We fix the ORP (N, sp, (b) as specified above and assume that comb, well the readout function read of N are given by the NN ,,....,,NN NN,,, where N1 has input dimension 2 m and output dimension n. Furthermore, assume that yp bounds valid graphs to degree d E N. For each unlabeled tree B = (V, ID, vo) with V = {vo..... 12) of degree at most d and depth k: of which there are only finitely many, the verification algorithm A works follows.
By definition, the MPNN N applied to B computes N1 EVEN, Egy) as the new label for each v E V after layer 4, However, as the structure of B is fixed this point we know the neighbourhood for each node v. Therefore, A constructs NN Ni with input dimension 1 m and output dimension I nı given by (Nd( )dd(( id(E (Xe' ))..... N1 (id(x.,, ). id(E EN., (x))))), representing the whole computation of layer 11, where id(x) == re(re(æ)) -r((-z) is simple gadget computing the identity.
the same way A transforms the computation of layer 4, i 2 2. into a network N; using the output of Ni as inputs. Then, A combines Mi and Nr, by connecting the output dimensions of Ni corresponding to node vo to the input dimensions of N,. creating an NN N representing the computation of N over graphs of structure B for arbitrary labeling functions L.
This construction reduces the question of whether (NV 4, v) holds to the following question: are there labels for Uo..... ,,,, the input of N, satisfying the constraints given by & such that the output of N satisfies vb As the label constraints of ip and the specification d are defined by conjunctions of linear inequalities this is in fact instance of the output reachability problem for NN, which is known to be decidable, as shown by Katz et al. (0117) or Sälzer & Lange (202T). Therefore, A incorporates a verification procedure for ORP of NN and returns T if the instance is positive and otherwise considers the next unlabeled d-tree of depth k. If none has been found then it returns 1.
The soundness and completeness of AA follows from the tree-model property. the exhaustive loop over all candidate trees and use of the verification procedure for output reachability of NN.
SUMMARY AND APPLICABILITY OF RESULTS
This work presents two major results: we proved that formal verification of ORP and ARP of graph- classifier MPNN is not possible as soon of unbounded, but finite size, non-trivial degree and sufficiently expressive labels. We also showed that formal verification of ORP and ARP of node-classifier MPNN is possible, as soon as the degree of the considered input graphs is bounded. These results can serve as a basis for further research on formal verification of GNN but their extendability depends on several parameters.
consider parts of the input space, containing graphs
Dependency on the GNN model. We restricted our investigations to GNN from the MPNN model, which is blueprint for spatial-based GNN (Wu all (2021)). However, the MPNN model does not directly specify how the aggregation, combination and readout functions are represented. Motivated by common choices, we restricted our considerations to MPNN where the aggregation functions compute a simple sum of their inputs and the combination and readout functions are rep- resented by NN with ReLU activation only. Theorem and Corollary only extend GNN models that are at least as expressive as the ones considered here. For some minor changes to our setting, like considering NN with other piecewise-linear activation functions, it is easily argued that both results still hold. However, soon as we leave the MPNN or spatial-based model the question of formal verifiability opens anew. Bridging results about the expressiveness of GNN from differ- ent models, for example spatial- vs. spectral-based, is ongoing research like done by Balcilar et al.) (222)) and remains to be seen which future findings on expressiveness can be used to directly transfer the negative results about the impossibility of formal verification obtained here. Analo- gously, Theorem 2 and Corollary 2 only extend to GNN that are at most as expressive as the ones considered here. It is not possible, for example, to directly translate these results to models like DropGNN (Papp et al. (202T), which are shown to be more expressive than MPNN. Hence, this also remains to be investigated in the future.
Dependency on the specifications. Obviously, the results presented here are highly dependent on the choice of input as well output specifications (see Appendix A for details). We refer to future work for establishing further (im- posssibiiyy results for formal verification of ORP and ARP of GNN, with the ultimate goal of finding tight bounds.

---

Published as a conference paper at ICLR 2023
REFERENCES
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In International Conference on Learning Representations, 2021. URL htttps:///openevvlee
net/Fozum?ic qh0M9XW*nV
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 Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL htt.hhttps::/ppenneeeeee
net dtt.//oooommdddr1222222..
Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Efficient robustness cer- tificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Re- search, pp. 1003-1013. PMLR, 2020. URL http::/pproceednnn// bojchevski20a. 2htmmml
Jinyin Chen, Huiling Xu, Jinhuan Wang, Qi Xuan, and Xuhong Zhang, Adversarial detection on graph structured data. In Benyu Zhang, Raluca Ada Popa, Matei Zaharia, Guofei Gu, and Shouling Ji (eds.), PPMLPP'0: Proceedings of the 2020 Workshop on Privacy-Preserving Ma- chine Learning Pructice, Virtual Event, USA, November, 2020, pp. 37-41. ACM, 2020. doi: 10. 54114444.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang. Jun Zhu, and Le Song. Adversarial attack on graph structured data. Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th Inter- national Conference on Machine Learning, ICML 2018, Stockholmsmässann Stockholm, Sweden, July 10-15, 2018 volume 80 of Proceedings of Machine Learning Research, pp. 1123-1132. PMLR, 2018. URL. http:::::pppceeeeeeeeeeeeee
ngs m press / / da 18b htm
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Yihong Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neu- ral networks for social recommendation. In Ling Liu, Ryen W. White, Amin Mantrach, Fabrizio Silvestri, Julian J. McAuley, Ricardo Baeza- and Leila Zia (eds.), The World Wide Web Con- ference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, pp. 417-426. ACM, 2019, doi: 10.1145/3308558.3311 13488. ARLAttps:: doi www.oo/g//.o. 1145/1308553388 331088555833333333 3313488
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction us- ing graph convolutional networks. In Isabelle Guyon, Ulrike von Luxburg. Samy Ben- gio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan. and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA. USA, pp. 2017. URL /ttpttsss/ppopceedasssssscc neurips.............p........... wtw.aaaaiiieeet----saaaaaat Abst html
htpppappr//2111 221///2177hhhh///// h/aash/
Simon Geisler, Tobias Schmidt, Hakan Sirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. In Mare' Aurelio Ran- zato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. wttpccppppp//////eeeeepo
7637-7649, 2021. https: http::::/ppccceeddeeooo U nwwrpps........p................ wbt.eaaaaaaaaaeeeaaaaaaaaaeeeeee
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, ICMI. 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272. PMLR, 2017. URL
mir prwssppspps.e..... /ea00/ggilmmerre gil.erlla...mm.m
Martin Grohe. The logic of graph neural networks. In 36th Annual ACM/IEEE Symposium Logic in Computer Science, LICS 2021, Rome, Italy, June 29 July 2, 2021, pp. 1-17. IEEE, 2021. doi: 00.10091LCS322242221..9990
URL CRLaatps:: /ci. ortg/0..1/111
L. LICS52264 2021 9470677
10

---

Published as a conference paper at ICLR 2023
Stephan Günnemann. Graph neural networks: Adversarial robustness.. In Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao (eds.), Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 149-176. Springer Singapore, Singapore, 2022.
Xiaowei Huang, Daniel Kroening, Wenjie Ruan, James Sharp, Youcheng Sun, Emese Thamo, Min Wu, and Xinping Yi. A survey of safery and trustworthiness of deep neural networks: Ver- ification, testing, adversarial attack and defence, and interpretability. Comput. Sci. Rev. 37: 100270, 2020. doi:
URL htttpp://acc.or/110.000
5. coseevv. 2020 100270
Hongwei Jin, Zhan Shi, Venkata Jaya Shankar Ashish Peruri, and Xinhua Zhang. Certi- fied robustness of graph convolution networks for graph classification under topological at- tacks. In Hugo Larochelle. Marc' Aurelio Ranzato, Raia Hadsell, Maria-Floon Florina Balcan, and Hsuan-Ticn Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. UtL http::pp:s//prrceeeeeddd neurieeuiip. act/papprr/222/hhast 609a199881ccmmmm (tw.19888.cbbaacc58822332332 Absseesssccccccc---aaattttt .bstract. html
Guy Katz, Clark W. Barrett, David L. Dill. Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In Rupak Majumdar and Viktor Kuncak (eds.), Computer Aided Verification 29th International Conference, CAV 2017, Hei- delberg, Germany, July 24-28, 2017, Proceedings, Part I, volume 10426 of Lecture Notes in Computer Science, pp. 97-117. Springer, 2017. doi: 10. 10.10077978-3331--633887 https:: hopp::/ddi.. orgg 10. 111.111..10000000 1007/970 3 319 63387-9311 9_5
URL
Thomas N. Kipf, Ethan Fetaya, Kuan-Chiel Wang, Max Welling, and Richard S. Zemel. Neural re- lational inference for interacting systems. In Jennifer G. Dy and Andreas Krause (eds.), Proceed- ings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässon, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Re- search, pp. 2693-2702. PMLR, 2018. URL http://proceedingg mi..ppress/vB. kipfl8a. html
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL /tattts://opereeeeee
Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks on graph neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 4756-4766. Curran Asso- ciates, Inc., 2020. URL |nttps::/pproccedingss neurips..................r....im cc wttphip....ppppppppeeepemm /cc/ppppr/222///1lee Paper.pp
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, The Thirty-Firsi Inno- vative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu. Hawaii, USA, January AAAI Press, 2019. doi: 10.
27 February 1, 2019, pp. URL httpttss:: /oii www.do.......oo 10. 609 aaai 1. v33101 33014602
Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, 21997-22009, Curran Asso- ciates, Inc., 2021. URL http:::/ neur ips. /c/ppaper/22///ile/// pdf
b8b292 2wt.:/dd222443355522222 13222226666444055555000062333330
Emil L. Post. A variant of recursively unsolvable problem. Bulletin of the American Mathematical Society, 52(4):264-28 1946. doi: 111000000000--9944-196---------0
Marco Sälzer and Martin Lange. Reachability is np-complete even for the simplest neural net- works. In Paul C. Bell, Patrick Totzke, and Igor Potapov (eds.), Reachability Problems 15th

---

Published as a conference paper at ICLR 2023
International Conference, RP 2021, Liverpool, UK, October 25-27. 2021. Proceedings, volume 13035 Lecture Notes in Computer Science, pp. 149-164 Springer. 2021. doi: 10.1007/ 978-3-030-89716-1 10. URL https:/
i0
Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung-Yu Yu Hsieh, and Vasant G. Honavar. Adversarial attacks on graph neural networks via node injections: hierarchical reinforcement learning ap- proach. In Yennun Huang, Irwin King, Tie- Yan Liu, and Maarten van Steen (eds.), WWW '20; The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, pp. 673-683. ACM IW3C2, 2020. doi: 10.1145/3366423333814999
Tsubasa Takahashi. Indirect adversarial attacks via poisoning neighbors for graph convolutional networks. In Chaitanya K. Baru, Jun Huan, Latifur Khan, Xiaohua Hu, Ronay Ak. Yuanyuan Tian, Roger S. Barga, Carlo Zaniolo, Kisung Lee, and Yanfang Fanny (eds.), 2019 IEEE International Conference Big Data (IEEE BigData), Los Angeles, CA. USA, December 9-12, 2019, pp. 1395-1480 IEEE, 2019. doi: 10.1 D0.11009BBDDttt4770000000099 90090000049
Jihong Wang, Minnan Luo, Fnu Suya, Jundong Li, Zijiang Yang, and Qinghua Zheng. Scalable attack on graph data by injecting vicious nodes. Data Min. Knowl. Discov., 34(5):1363-1389, 2020. doi: 10. 10.1007/s 0017//100111-10 001116600000066666
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Ad- versarial examples for graph data: Deep insights into attack and defense. In Sarit Kraus (ed.), Proceedings of the Twenty-Eighth International Joint Conference on Artificial Inteli- gence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 4816 4823, ijcai.org, 2019, doi: 9/669
10.24963/jjcai.219999 http://caa..011///66 URL.tttss://dan org. 1ttttp///ooo..orr/00.20266666610
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn. Syst., 32 (1):4 24, 2021. doi: 10.1 (O09/NNNLS.222002977951 URL https: //ccci///cc/////// 1. oot..o.oo....0000000000
TNNLS 2020 29 78366
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Or- leans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL http:peeneeiieeee///
Dorum?id=ryGsiiln
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations, 2019. URL https://
openreview net http://ooorrimddylllsaa
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: review of methods and ap- plications. Al Open, 1:57-81, 2020. doi: 10.
URL https:
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Yike Guo and Faisal Farooq (eds.), Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 2847-2856. ACM, 2018. doi: 10.145//221981993220077
A DETAILS ON IMPORTANT SETS OF SPECIFICATIONS
To prove the results stated in the main part of the paper, we need to work with a formally defined syntax for each kind of specification considered here. However, it should be clear that the results presented in Section 3 do not depend on the exact syntactic form, but on the expressibility of the considered kind of specifications.
12

---

B PROOF DETAILS Published as a conference paper at ICLR 2023
Vector Specifications cconv- Motivated by common choices in formal verification of classical NN, we often use the following form: a vector specification for a given set of variables X is defined by the grammar
6 == A 1 p
c==
where b, E Q and x E
X a variable. A vector specification with occurring variables (ro,...:
No,..., Xn-1 x satisfied by arithmetic with each x; set to r;- We denote the set of all such specifications by conn- A vector specification that also includes and < operators is called extended. Extended vector specifications
R. if each inequality in yp is satisfied in real
are not included in V conv-
Graph specifications from Punb- In the arguments Section Fnnd Appendix B. we refer to any set of graph specifications which contains specification satisfialle by finite graphs of arbitrary size and degree as well as arbitrary labels, as Lunb. for instance a specification like yp = true. However, as indicated in Section 3 this weak form of Pubb is not necessary. The arguments for Theorem [ given in Section 4 and Appendix B.T are also valid if Punb contains at least one specification (,, satisfiable by graphs of arbitrary size, degree 4 (indicated by Figure (3) and labels expressive enough to represent those used in PCP-structures (Appendix B.I), mainly labels using positive integer values. For example, (g)) deg(G) S A Ve E V V.brep(r)) (r). where r'rep is an extended vector specification, checking if the label of node is valid for PCP-structure. However, the exact conditions are highly dependent on the construction used in the reduction from PCP to GLP and can easily be optimised. But the aim of this work is to show that there are fundamental limits in formal verification of ORP (and ARP), and optimising the undecidability results presented in Section 4 in this way would only obscure the understanding of such limits. Thus, we use the above described weaker Punb in the formal parts, leading to uncluttered arguments and proofs.
Graph-node specifications from Pbound- First, we define for each d, k E N set bound of graph- node specifications.
d.
T bound the set graph-node specifications y bounding the degree of satisfying graphs to d and constraining only nodes in the k-neighbourhood of the center node using vector specifications, for instance (pGG v) deg(g)= S 4AVv' E Neigh, (b). where Neigh, includes all nodes of distance up to l of u and ub is a vector specification. Then, P = UdAEEN d. bound
Graph or graph-node specifications from neigh. We consider + neigh as set of graph specifica- tions or set of graph-node specifications. & Peiggh consists of graph graph-node specifications ip, given by some fully-defined center graph G (or pair (G, v)) and a finite modification- finite modification budget specifies bounded number of structural modifications, namely inserting or deleting nodes and edges, as well as allowed label modifications of nodes in G, bounded by vec- tor specifications, for instance &p (G, B) or & ((G, v), B). Then, a graph graph-node pair satisfies if it can be generated from G respectively (9, v) respecting the bounded budget B.
B. A
Vector specifications Veq- The set Veg consists of vector specifications of the form x; = b, thus, vector specifications expressing that single dimension is equal to some fixed, rational value.
Extended vector specifications Vlog Velasse The Vieq consists of extended vector specifications of the form Aver Veen X, Xj- Analogously, V Velass consists of extended vector specifications of the form Viet (jen, X; > Xy. Note that for the argument of Corollary sufficient that (x1 A x2) A (x2 & X1) is included in Vleg-
B. PROVING THAT GLP AND DGLP ARE UNDECIDABLE
We use the following abbreviations for GLP. For set C of colours we define cCl Ax(x, 0) (x, = 1) and exactly _one(Conn___n_ = Ag(c + (Nato -d)) A ( Va c') where c := (x,
1), - = (x. 0), + sp (x. 0) V xp and -c + & == (x. 1) V s. We use - as having a weaker precedence than all other GLP operators. To keep the notation clear we denote unambiguous some variable x; in node and graph conditions by its index i.
13

---

Published as a conference paper at ICLR 2023
Let G (V, L) be graph. For some node set V C V and node we define Neigh, (V*) Neigh(u) V. We call a subset of nodes V = -fl...... uk) } C V. 2 2, a chain if Neigh.,, (V" {u2}, Neigh,, (V') {u;-1, 0(+1 } for 2 H Kisk k - and Neigh,,, (V')
{2k-1). We call in start, U middle node and Vk end of V and assume throughout the following arguments that index denotes the start and the maximal index k denotes the end of a chain. Let V1 = {ur..... Us and V2 fu....., ux} be subsets of V and both be chains. We say that VLUV is a ladder if for all es, us we have Noigh,, (V1 22) = Neigh (V1) U {ue} and Neigh,, (Vig (VUV) = Neigh,,, (V2) U (vi).
First, show that DGLP can recognise graphs G that consist of exactly one ladder and one additional chain. If this is the case we call G a chain-ladder. Let C3 = {e1, C3), T {(c, 8), (c, m), ec | e C3) he sets of of symbols we call colours. Let (pc1,WCL) be the following DGLP over variables VaraL= = fxe I c E C3 UT) U (Xcid, Xo, c Cz):
(PCL Poond A colour(C3 A (ME exactly (M)(M
(Pound := -= - -c, t) A (c,, id) = A
= 0) A (4: + 0q = V Cc = 2)
A ((c; 8) + Oc; = 1 A (c, id) = 1 O(, 2 e,
A ((c;, m) + Oc; = 2 2(c, id) = (d
A ((cs, e) + Oq = 1 A (c,id) < (d) 1A (c, = id)
A (ci + O02 = A (c).id) = (c2 id) A (c2 + oa = 1A (c2, id) = o(a id))
VCL == Acs (c,, = A
= (c.e,id) id)
Lemma 3. g = (V, D, L) satisfies (PCCL toe)) then G is a chain-ladder and if g' = (V', IT') is an unlabeled chain-ladder then there is L' such that G = (V' D', II) satisfies (fCL. Pea.).
Proof. Assume that 9 satisfies (PPCL v.c.). By definition, it follows that all nodes v E V satisfy PCL and G satisfies VCLL.
Let U E be a node. Due to (M,
(M))))))) A colour(Cs TT) we have that e has exactly one colour C1. C2 or cs and exactly one from T. Furthermore, the subformula Ac, (-q + -... implies that there is E {1, 2, 3) such that v is of colour o; and (ci, t) for some t. t) -c,
We divide V into three sets VI, V2 and Va such that E V. if and only if v is of colour e; and argue that each V, is a chain. Note that the V, are disjunct sets. Let V E V. The subformula (c: - Gc 1 V Gc; = 2) implies that v has 1 or two neighbours from Wz. From the argument above, we know that must be of exactly one colour (ci,s) (cz, m) or (c,,e) e). The -> subformulas in &Pond regarding these three colours imply: if is of colour (Gi, 8) or (c. e) it must have exactly one neighbour from V, and if is of colour (c,, m) it must have exactly two neighours from V. The graph condition t'C implies that there is exactly one node with colour (ct, and one with colour (cs, e). In combination, we have that there is start Us and end ve in V, both having one neighbour in V; and all middle nodes Um having two.
Next, consider the (c, and (cs, e, i,) label dimensions. We call (c,,id the id of node with = 0 A (q, e, id) = 0) A...) implics that if a node is not of colour 6; then the corresponding dimensions must be 0 and ((c, 8) -.... (Cz, e, id 0)) and ((c,, m) + .... A (c, e, id = 0)) imply that if it is not an end node then (cs, e, id) is O as well. Next, we see in the subformula ((c,,) + ...-A A (G, id) 1 (c,,
colour q, The subformula (-q -...A A..AA (c,ii)=
2 A-..) that vs has id and its neighbour has id 2. This implies that the only neighbour of C, is not itself. The same holds for u. due to the subformula ((ca, e) + ....A (c,,id S (c,, id) - 1). Furthermore, the subformula ((cs, e) ..... A (ca, id) = (c,, id)) implies that the id of Ue is stored in (c,, e. id). This is used in the graph condition subformula e, = (c, e, id) to ensure that the amount of nodes in V, is equal to the id of ve. We make case distinction: if v. is the neighbour of u, then the id of v. is 2 and, thus, chain. If Ue is not the neighbour of Us then must be some
Vi = -V,, which obviously Um. The subformula ((c.)) m) + ^ 2(c, id) = @(c,, id) A A...) implies that Um is not its own neighbour and that the other neighbour v' must have id 3. Now, if v/n = Ue then we can make the same argument as in the other case. If not then we get that e/n must have neighbour v% # tnm The node "M must have id 4 and, thus, it did not occur earlier on the chain. As V, is finite, this sequence must eventually reach U. and we get that V, must be chain.
So far, we argued that V = V, UV2 UV3 with V. disjunct and chains. It is left to argue that V, UV2 forms ladder. From our previous arguments we know that the nodes of V. have incrementing
14

---

Published as a conference paper at ICLR 2023
ids from Us to ve starting with 1. Therefore, the ladder property is ensured by the subformulas (ci + Oo2 = A (c1, id) = O(22,dd) and (c2 + Tc1 = 1 A (c2, id) = @(1r,d))
The other statement of the lemma, namely that there is labeling function L' for G' such that (PCCL VCL. is satisfied, is a straightforward construction of L' following the arguments above. E
Let 9 be a chain-ladder with ladder V1 U V2 for .e....... J U fui..... ... Ue and chain V3 (wi...., w We call G PCP-structure if for all w, we have Neigh (V1 U V2 U Va) = Neigh w. (Va) U (Th, (B, for some h4, Ji E (I,...,k) ,k) such that for all S S - we have that h4-1 < h4 < h441 and Ji-1 < j: < Je41- Intuitively, this property ensures that connections from chain V3 to 1 or V2 do not intersect.
We show that there is a DGLP that recognizes PCP-structures. Let L, M, R be colours, called R, R++ 1= L and direction - symmetrically. Let C3 be as above and FF = {(c, d) c C3 d E M,, RJ). The DGLP (yps,, vPs) over the variables Varps = Varai U fxx | c F] U (xd.c.id d [L,M, R), ca E ((i,c2)) is defined as follows:
directions. We define L+ == M, M,M+L6
M,
PPs Poond colour(1)) A exactly_onee one(()) A PCL FFomd == (Nc, T6 + -
M) A AAc, ((c,, - (c, M) 1)
((G. - Vg(c, d) A Nazy (cs, d') = =1
A (A(on.o)) Co 0c3 1) A (c3 6c 1 A AA02 1)
Ap(-(c3, d) Ma (d. c, 0) ^ ((c, Ata (q,, (d, c;
A Ap > Alcner) old id) s s(d, id) ^ (d, c. id) s old + 1, id)
hps :
Lemma 4. 1 = (V,D, satisfies (yps, Ves) then G is a PCP-structure and if g' (V.D') is unlabelled PCP-structure then there is labelling function L' such that (V' D' L') satisfies (Pps, thps).
Proof. Assume that 9 satisfies (pps, Des). As PCL occurs as a conjunct in yes and t'e in thes Lemma 3 jimplies that G is a chain-ladder. Let V, V. be the ladder and V, the chain.
The subformula exactly_onc(()) onc(F) and colour(F) in combination with (Ac, TC - Ax (c, d)) im- ply that a node is of colour o, and only if of exactly one color (c,, d). From the arguments of Lemma 3 we know that each node has exactly one colour o; and, thus, also has a corre- sponding direction d (L, M, R.). The subformulas ((c,,) - (c,, L) A O(c; M) = 1) and ([c, m) Vz(G,, d) A Na (c,, d²)= 1) imply that start node of chain V, has direction L. and its neighbour M and that the neighbours of each middle node of direction d, characterised by colour (cs, m), must have directions d and + 1. In combination, this implies that each chain V,, 1. V/ and V3 is coloured from start to end with the pattern (L, M, R)).
The subformulas (A C + Gc3 < 1) and (c3 + Geg A = 1) imply that nodes from ladder V1 U V2 have at most one neighbour from V, and each node from chain V3 has ex- actly one neighbour from V1 and one from V2. Consider the dimensions (d, c, id). First, the subformula (-(cs. d) + ( (d, c,, id) = 0) and the conditions of (CL imply that dimen- sion (d, c. id) of node are nonzero only if is from V3 and of direction d. The subformula ([c3, d) + ((o,.s) O(c, id) = (d,c,,id) leads to the case that each node e E V/3 of direction d has stored the id of its one neighbour from V, in (c), d, id) and the id of its one neighbour from V2 in (c2, id). Now, the subformulas ((c3, d) + Afar O(d 1, i,, S (d, c2, id) and ((d, c,idd id) < Odd+ + 1, 1, id)) imply the main property a PCP-structure, namely that the connec- tions between V, and V1 well V2 not intersecting. Note that < is sufficient as each node from V1 and Va can have at most 1 neighbour from Va.
Finally, we are set to prove that DGLP is undecidable. Let P {(a BI)..., ..., (ak, Bx)} be a PCP instance over alphabet = fa.b] and let mn = max(U; ((ci, d, j) (cr, b, a E (d), (T,, M, R).j E (0. (0, 1}) and S =
- flaul. B11).. Let =
15

---

Published as a conference paper at ICLR 2023
(o..... (...... ...)) colours. Addi- tionally, we define 8 = =8 1 f(c, (q, (q,d, L.j) E S), 8) ((c, d. p. 0) (c,, d. p. E s}
p. & (2,,2) (L, (e.....,ee
and Bd' [(a d. 0) 0) E Bj. We define the following DGLP (prr, pp) over the variables Varps U (xe cEB.
Pp :oood A (A G + AME(BO.S)) 30 exactly.one(MI)) A yes A colour US)
PPoond := -= + ABuS (c,, p,j))
d)(c,. 7 ABjjem d. p.j
A Ap(c,,) 7 N (c, p.j p.j + 1) Ol 1.p.))
A Marres (ci, + A (G, p).) A Ve(ci,dee,)
A (eLio)) (c, AF (q, e,
AST Do (0. d) oz 1 (A 0. - (.,,,,,,)))) (c,, A VØ= (9
A AST poto (02, d)p,0) O0 1 1
v1 (cg
((..)))(GG.d)) (c, ((nd) = 0 d, d, = 0,c,,, b,))
A + (A AOEELLM. Oc,, d. 0 A Vs d..1), =
bp :01ss
Proof of Theorem 3 We prove this via reduction from PCP. Let P = (1a,,8))... ................................ (ax. 3x)} and (pp,, 1p) be like above. Assume that (yp,, is satisfied by g.
From the describtion above, we can see that yos and sps are conjunctive subformulas of pp re- spectively ppp Therefore, Lemma 4 implies that G is a PCP-structure. Let V1 U2 be the ladder and V3 the additional chain in G. In addition to the colours resulting from (pps. the subformulas colour(IB U S) and (A(e),e2) G + (B"_(("" exactly_one(MM) (M)) ensure that IB and 8 are colours and that each ladder node has exactly one colour from E c B and S c S. The idea of these colours is the following: a colour (c, p.j) E IB with p E {a, and j E {O..... m 1} represents the symbol (a or b) of node in distance j of a node coloured with (c,, d). Similarly, colour (c,, d. p. m) represents that a node in distance j of a node coloured 2.p I. In case of the node in distance j is the end node of chain V, and 1 is a placeholder for nodes which are neither a start of some tilepart nor the end node. The case j 0 is interpreted as its own symbol or start of a tile part.
with E [1....,k:, I. c) and j E
with (c,, d) is the start of tilepart On if 1,p F 1, and B, if
We argue how spp ensures the above mentioned properties of colours (c.ddp..)) E U.S. The subformula (-(ci,d) + Azus -(c, d, p.j)) ensures that a node of some colour (G, d, P.j) must also be of colour (c,, d). Especially, this implies that nodes from chain V3 do not have any colour (ca, d, d.p.j). The subformulas ((c,, d) + AB d.P.j + 1) = O d + 1. ())) and @(c, d + I,), ensure that node with colour (c, d)
((c,, d) + As.iem (c,, p,j.j j..j+ + 1) stores the information p.j its (c,, d neighbour in form of its own colour (c,, d.p.j.j..... Note that, each chain is labeled wird L, M, Rt L.... from start to end and, thus, the d+1 neighbour is the right neighbour in the sense that its nearer the end node Ue. To understand how this leads the case that each node on chain V, stores the information of its m right neighbours, we argue beginning from end Ue of chain V, Subformula ((c,,)) e) + ABLE, ~(c;, d, p.j) Vz(c,, d, 0)) ensures that ve only has colour (c,, d, e, 0). That d matches its colour (c, d) is ensured by -(c,, d) + Therefore, its only and left neighbour & must have colour (c, d e, 1) plus its own additional colours with j = O. Now, the left neighbour s' of u must have colours (c1, d - 2, e, 2). the colours equivalent to with = 1 and its own colours with a colour from $ is m. tilepart start, end or 1 colours are stored in nodes up to distance m to the left of the original node. The same holds for colours from B with distance m 1.
0 and so As the maximum j in case of
16

---

Published as a conference paper at ICLR 2023
We are set to argue that & encodes a solution I of P. The subformula (AST MTTTpee(0a p,
(Aj=0 " (ci, apli):.) (eI, d, 1,J)) V d, y', lapl) V (ai, e, lapl)) ensures that for each node from V1 that is tilepart start for some Op that Op is written the right with- 1 (cI, d, aplil.j) A A(c1, (,))) and that after ap is fin- ished that either the next tile part starts or the chain ends ( (apl) v (ci, nn,d,e e, (ap))) Analogous conditions are ensured for nodes from V2 by the subformula (As pteeee d,p, + A (N (N)20 (c2, d, (pb)).1) A (c2, d, 1,5) A V ( d, 1.pp1111)))))) V (e2, d, (3p1)) (s,))),))))) Now, the subformula (2 (c, spond to tilepart start. In combination with the previous conditions, this ensures that chains V1 and V2 are coloured with words Wa and wa corresponding to sequences Cii Oii and 83 B..
out a next tilepart starting ((A)=0
VgT (c,, d. p. 0)) ensures that the start nodes of 11 and V2 corre-
It is left argue that wa wa and that in...in by ((c1,d) d) + (C1, d, 0, = O(ez, d, a, 0) A (c,, d, b, 0) = O(e,, d, d,), and the fact that U ladder. The second equality is ensured by (c3 + (Ago A O(11, d. p. (c22, pp, 0)) A Vet O(c,, d, p.O) 0) 1), ((e), 0. + Deg = A ...) and ((e2, d, p, + Ocg = 1A...) and the fact that G is PCP-structure which means that connections between V and V1 respectively V2 are not intersecting. Therefore, the sequence iz .n = j1 ... ft is a solution for P which implies that P is solvable.
ji ......
ji. The first equality is ensured
The vice-versa direction, namely that if P is solvable then (40r, 3/r) is satisfiable, is argued easily: If P is solvable then there is solution J. Figure 3 indicates how to encode 7 PCP-structure G. Note that in contrast to the visualisation, the encoding characterized by yPs demands that the end nodes of chain V and V2 are not part of solution 1. Lemma 4 states that for each unlabeled PCP-structure there is labeling function L' such that G satisfies (Grs, Wrs). Therefore, if we take a matching structree 9 without labels, label with L' and then extend L' with the colours (ca, (.)) according to I and the arguments above we get that G satisfies (ppp, vP))
We can see from the definitions of (CL, (pp and pp and corresponding graph conditions that they belong to the DGLP fragment of GLP. This proves the statement of Corollary
B.2 PROVING THAT DGLP REDUCIBLE TO GCP
In the proof of Theorem 4 we claimed the following properties of (x m) and (x E M) gadgets.
Lemma 5. Let R and (ri....,, rrk. RR for some k. It holds that (r S m) = 0 if and only if r & m and (r E M) = if and only if r E M. Furthermore, gadgets (x S m) and (x E My are positive and (x < m) is upwards bounded.
Proof. The properties of (x S m²) are straightforward implications of its functional form.
Next, we prove that (r E [m: nl) = 0 if and only if E [m;; rt). Assume that r E [m;; n). It follows that the output of each inner ReLU node is O and therefore (r [m,; nz) = O. Next, assume
m.
follows that re(m- - x) > 0 and as the value of all other inner ReLU nodes must be greater or equal to 0 it follows that (r [m;
0. The case r > n. is argued analogously as re(x n) > 0.
Consider the (x E M)) gadget and assume that r E M. It clearly holds that r E [(i; in] and therefore that re((x E (1)
0. Furthermore, w.l.o.g. let (b+1-11)) < re(r- 4, rr + - r) 2
in for some 1 1 kt Then, it follows
that (4141-4) = re(r f+++1++1) ) re( 4+
2 - and 2
for A f and, thus, the inner sum is equal to as well. Now, assume that r & M. Ifr < il or in
2
it follows that re((x E (();;x])) > 0. If E [ir; it must be the case that r E (1z) (54) for some
i < j k and therefore that re( (i .n) (re(x- (+tie+1) re( 1e x))) > 0. That the gadget (x E M) is positive is obvious as the outermost function is ReLU.
B.3 PROVING THE TREE-MODER PROPERTY OF CODE-CLASSIFIER MPNN OVER BOUNDED GRAPHS
In the proof of Theorem 2 we claim that node-classifier MPNN have the tree-model property. We formally prove this statement in the following.
17

---

Published as a conference paper at ICLR 2023
Let g (V.D, L) be graph and E V. The set of straight i-paths P of is defined as P {u) P. = (vv' | (u. o') E D} and Ii+1 = 1....01 11-11110 Up ................................ 44-1% E P. (v, 0(+1) E D, D-1 # 1.+1). }. For some path p U0
define Pe for S as the prefix uo U;- Furthermore, let P. ((vo, (o), PI)... (vt, -p= v0 .. p.j and let ()) = {(v). Pj)
(Uo.Po) ... (y), Py) ... (s), E PP: J. Let N be a node-classifier MPNN. We denote the value of after the application of layer with (9, v) for 2 Furthermore, let (9, v) = L(w) for each node v.
dd."" Lemma 6. Let (N, P. v)) E ORP ( (Poundd, ccnnv) where N has K' layers and E bound The ORP (N, p,, 4) holds if and only if there is d-tree B of depth max(k', k") with root up such that (B, vb) F & and (BB, vo) - v.
Proof. Assume that (N, q, 1)) is as stated above. The direction from right to left is straightforward. Therefore, assume that (N, f2, 2)) holds. By defintion, there exists d-graph G = (V, W, L) with
node w such that (g, w) F 4p and N(g, w) F th. Let B = (Vg, Dg, LB, (w, w)} be the tree with node set VB= = U PP (t). The set of edges DDx is given in the obvious way by {((u,)), pu')) (u,p), p), (v', pu') E V&} } and closed under symmetrie. Note that from the definition of IP follows that B is well-defined d-tree of depth k. The labeling function LB is defined such that Ls((v,2 p)) L(v) for all (v.p) VB. From its construction follows that (B, (w, w)) } g..
We show that it holds that N* (B, (w, w)) = N* (G: w) which directly implies that (B, (w. w)) = NGG, w). We do this by showing the following stronger statement for all ..... k'' via induction:
for all (v. E FK (k' - i) with k' 2 2 j holds that 2V (B, (u, p)) (g, v). The case j 0 is
obvious as Lg is defined equivalent to L. Therefore assume that the statement holds for j S k'
and all (v. p) E PpK (K' - i) with k 2 i 2 j.j. Consider the case j + 1 and let (v.p) E Pk (K' i) 2 j. We argue that for each (V', E Neigh( (1,gh(((,,0) p)) it follows that o' E Neigh(v)
for some k'
such that (B, (u', ,P))) = NG, v') and vice-versa. Let (v', p')) E Neigh((u,
By definition
of Ds. i 2 and the fact that all p E Pk' are straight follows that p' pr' or p p'v but not both. Therefore, either (v', (') E D& (k' -i 1)) (v',p")
PK' (K' - (i + 1)) and, thus, (v',v) E or (U,0") 1') E which in both cases means e' = Neigh(v). The induction hypothesis implies that (B, (U',p)) (9 v'). As these arguments hold for all (u',p') Neigh((e, p)) we get that (orp))(( (B, (()) S E Neigh(u)) (9 v'). The vice-versa direction is argued analogously which then implies that E [eiigh((e.)) (B, (v' ,/)) Eveigh(s) N² v'). From the induction hypothesis we get that (B, (v. ())))) = (G, v). Then, the definition of a MPNN layer implies that NB+ (v. p)) N v). Therefore, the overall statement holds for all j < k' and by taking j = = we get the desired result.
18


Reviews:
[{"review_id": "qwcodnsrZK", "reviewer": "Reviewer_LFLB", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This problem considers the question of whether or not it is possible to verify robustness and output reachability properties of message passing neural network (MPNN), e.g. graph neural networks. The paper proves via a succinct reduction to Post's Correspondence Problem that verification of such properties on large classes on MPNNs is undecidable. Furthermore, the illustrate that limiting the class of input graphs, e.g., limiting the degree of the nodes, is sufficient to make the problem decidable. This generalizes the feasibility established by explicit algorithms appearing in the literature.", "summary_of_the_review": "Overall, I think this i an excellent contribution to the theoretical understanding of message passing and the limits on verification.\n\nThe main take aways are that:\n\n1. arbitrary graphs are too expressive.\n2. reasonable restrictions on node degree is sufficient.", "strength_and_weaknesses": "# Strengths\n\n1. The topic of verification is a very important problem, particularly as such systems get deployed in more safety critical systems. Knowing the limitations of verification is critical to carving out tractable subsets of the problem space. Theoretical treatment of such topics typically lags behind the development of the models, and so this is welcomed progress.\n\n2. The provided reduction is succinct and fairly easy to follow, although I must admit to needing a refresher on PCP.\n\n# Weaknesses\n\n1. The paper focuses on a fairly small (but as far as I know practically used) subset of MPNNs. There is a discussion that the specifics could be relaxed, but many alternative formulations exist, e.g., a different aggregation function. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "YAFIzyeT4mh", "reviewer": "Reviewer_5S64", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper provides theoretical results on the formal verifiability of message passing neural networks (MPNNs), a popular class of graph neural network models, for graph and node classification tasks. \nIn particular, it proves that, without assuming a bound on the degree of the graph, the formal verification of output reachability and adversarial robustness is undecidable for graph classification problems. At the same time, the paper provides positive results by showing that bounding the degree makes the verification of node classifiers decidable.\n\n", "summary_of_the_review": "The paper contributes with some key theoretical results on the problem of verifying MPNNs, as well as providing useful groundwork for future efforts in the area. I think that the problem considered in this paper is very relevant. The overall methodology seems correct and, to the best of my knowledge, novel. However, I couldn't verify the correctness of the proofs in the appendix. The presentation could be improved in some parts, but overall I think that the authors did a good job in clearly presenting the key concepts and intuitions.", "strength_and_weaknesses": "Strengths:\n- The paper contributes to a fundamental problem in the context of safe/verifiable AI for a popular class of ML models\n- The theoretical groundwork provided in the paper, such as the connection between formal verification of GNNs and the newly introduced Graph Linear Programming (GLP), could benefit future efforts in this area.\n\nWeaknesses:\n- The presentation could be improved in some parts\n- It is not clear to me how realistic are the setting and assumptions made by the authors", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ReY-V20A_v", "reviewer": "Reviewer_8dRF", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents theoretical results about the decidability of verification problems of Message Passing Neural Networks, which are a type of graph neural network.\nGraph neural network are a flexible deep learning architecture that operate on graph data, which can be of variable sizes.\n\nThe first main result of the paper is in Theorem 1, proving that if the input specification is permissive enough (allowing unbounded size of input graphs and without imposing restrictions on node degrees and labels), then it is not possible to perform reachability verification (answer the question \"is there a graph such that a certain output will be produced by the MPNN when evaluated over this graph?\").\nThe proof is performed by reducing a known undecidable problem (Post's correspondence Problem) to a graph satisfiability problem based on linear constraints ( in section 4.1) and then, reducing that graph satisfiability problem to a MPNN verification problem (in section 4.2).\n\nThe other main result  is Theorem 2 which shows that if the input graph have bounded degrees, then the verification problem become decidable. The proof rely on the fact that due to the way MPNN work (each node can only process information that is most $\\texttt{GNN depth}$ nodes away, then if a graph satisfy a feasibility problem, there must a tree that satisfy it as well. Due to the assumption of bounded degrees, only a finite amount of those trees can exist, so it's possible to enumerate them, and to perform verification independently on each tree using traditional verification technique.", "summary_of_the_review": "This is a completely theoretical paper that proves results on the limitations of verifiability of graph neural network. \nThis is useful as it tells us that there is no point in researching verification algorithms that would be applicable to the most general settings, as these problems are not going to be decidable. The whole paper is self contained and clearly written, so I recommend acceptance, even if this does not inform real applications (where we could always consider that the graph considered would be bounded).", "strength_and_weaknesses": "The paper is very clearly written, with the authors having made a clear effort to be rigorous and provide definitions for all the constructions that they use. There is a clear structure to the paper, with the results being announced first, the strategy of the proof being presented and then executed, with the detailed version being present in the appendix. \nThe proofs are decomposed into logical parts, making it possible to get relatively quickly an intuition for the reduction being operated.\n\nIn addition, the paper is quite clear in Section 6 to delineate the settings in which their results are applicable and the ones in which they are not.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Iui2A_LL4K", "reviewer": "Reviewer_UR4T", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper studies the formal output reachability verification of message passing neural networks (MPNN). The paper claims that the verification is impossible if for general graphs (unbounded size, nontrivial degree and node labels). But the verification is possible if there is a bound on the degree of the graph. \n\n", "summary_of_the_review": "This work has theoretical merits on showing the impossibility of general GNN verification. But the problem is minor. The “fundamental limit” is not a critical limit in practice and is not the critical factor hindering the development of formal verifiers, for two reasons: 1) computational complexity plays a more important role given the NP-hardness of NN verification; 2) constraints can be added on graphs in practice, which makes the verification possible. The second point corresponds to Theorem 2 in the paper, but the paper does not provide a concrete and computationally feasible algorithm while only proving the possibility of verification, and thus the contribution is not significant. \n\nUpdates: \n\nI am recommending a rejection because I think the contributions in this paper are insufficient, not because this is purely a theory paper. As I have said, NP-hardness in verification is known and is already fundamentally limiting the verification [1, 2]. Especially on verification for graphs with unbounded degree/size, NP-hardness is a stronger limit that can hinder exact verification in practice for unbounded cases. That’s also partly why I said verification for the unbounded case is not important as we have already known NP-hardness on verification so I would not pursue generalizing verification to the unbounded case in practice. Therefore, for now, the limit revealed by Theorem 1 (decidability) is not an important limit compared to NP-hardness done by previous works and the contribution is minor. However, it could potentially become more significant if the paper can prove that the verification is not NP-hard in the special case for MPNN considered in this paper, to eliminate the limit revealed in previous works so that decidability could really be interesting and important. Theorem 2 only showing the possibility without a computationally feasible method is not making a sufficient contribution either.\n\nActually the failure to support that decidability is \"worse than NP-hard\" ([unconvincingly claimed by the authors](https://openreview.net/forum?id=WlbG820mRH-&noteId=LXeVO_iFIJ)) poses a significant weakness of this paper. This paper provides no evidence to support such a claim. Without it, given the existing works on NP-hardness [1 2], showing the undecidability is insufficient to support the significance of this work. See [my previous thread](https://openreview.net/forum?id=WlbG820mRH-&noteId=u3TrgCTLzp) on why I disagree decidability is worse than NP-hard.\n\nThe authors refuse to compare with existing works on regular NN, by saying this paper works on GNN but not regular NN. GNN is an extension of regular NN. There are works about NP-hardness of verification on regular NN and this paper needs to show that why their results don't apply to this paper in a formal way, e.g., by proving that the verification in their case is not NP-hard, which is missing in this paper and I am not sure if it is actually possible to prove that. The authors are responsible for ensuring their claims are sufficiently supported. \n\nOverall, there is a significant lack of evidence supporting the significance of the work. I believe this paper is not ready for publication at ICLR.\n\n[1] Katz, G., Barrett, C., Dill, D. L., Julian, K., & Kochenderfer, M. J. (2021). Reluplex: a calculus for reasoning about deep neural networks. Formal Methods in System Design, 1-30.\n\n[2] Sälzer, Marco, and Martin Lange. \"Reachability is NP-Complete Even for the Simplest Neural Networks.\" International Conference on Reachability Problems. Springer, Cham, 2021.\n\nMy latest discussion [post1](https://openreview.net/forum?id=WlbG820mRH-&noteId=u3TrgCTLzp) and [post2](https://openreview.net/forum?id=WlbG820mRH-&noteId=sbBDJ-bL3L).\n", "strength_and_weaknesses": "Strengths:\n- This paper has theoretical results showing the impossibility of generally verifying MPNN, and a theoretical construction showing the possibility of verifying MPNN when the degree of the graph is bounded. \n\nWeaknesses:\n- The problem considered in this paper has little importance and the results are not useful in practice. For verification in practice, we not only want decidability, but also computationally feasibility. NP-hardness of verifying NN is known. Therefore, considering the decidability of verification for graphs with unbounded size and degrees is not important, as computational complexity would play a more important role for larger graphs, which limits complete verification. Decidability is minor here, which is not the major factor hindering formal verification. \n- In practice, it is reasonable and acceptable for verification to only support specifications with some constraints, such as the size and degree of the graphs. While Theorem 1 says the impossibility of general verification, it would not fundamentally limit verification in practice. \n- The contribution of Theorem 2 is not significant. It only proves the possibility of verification when the degree is bounded, without proposing a computationally feasible algorithm (the construction seems to have an exponential complexity and thus it does not automatically imply a computationally feasible algorithm). On regular NNs, there already exist many concrete algorithms for formal verification. Then the contribution here is relatively insignificant. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster