Training One-Dimensional Graph Neural Networks is NP-Hard
Authors: Robert Ganian
Mathis Rocton
Simon Wietheger
Venue: ICLR 2025 Poster (2025)
Keywords: Computational Complexity
Graph Neural Networks
Training
ReLU
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We initiate the study of the computational complexity of training Graph Neural Networks (GNNs) and prove NP-hardness even in the one-dimensional case.

Abstract: We initiate the study of the computational complexity of training graph neural networks (GNNs). We consider the classical node classification setting; there, the intractability of training multidimensonal GNNs immediately follows from known lower bounds for training classical neural networks (and holds even for trivial GNNs). However, one-dimensional GNNs form a crucial case of interest: the computational complexity of training such networks depends on both the graphical structure of the network and the properties of the involved activation and aggregation functions. As our main result, we establish the NP-hardness of training ReLU-activated one-dimensional GNNs via a highly non-trivial reduction. We complement this result with algorithmic upper bounds for the training problem in the ReLU-activated and linearly-activated settings.

Published as a conference paper at ICLR 2025
TRAINING ONE-DIMENSIONAL GRAPH NEURAL NETWORKS IS NP-HARD
Robert Ganian, Mathis Rocton & Simon Wietheger Algorithms and Complexity Group, TU Wien, Vienna, Austria rgan i annigman@gm 1. .com, (mrocton,, swi et twwien ac
ABSTRACT
We initiate the study of the computational complexity of training graph neural networks (GNNs). We consider the classical node classification setting; there, the intractability of training multidimensonal GNNs immediately follows from known lower bounds for training classical neural networks (and holds even for trivial GNNs). However, one-dimensional GNNs form a crucial case of inter- est: the computational complexity of training such networks depends on both the graphical structure of the network and the properties of the involved activation and aggregation functions. As main result, establish the NP-hardness of train- ing -activvvee one-dimensional GNNs via a highly non non-trivial reduction. We complement this result with algorithmic upper bounds for the training problem in the Rea.ivactd and linearl--activtted settings.
INTRODUCTION
Graph neural networks (GNNs) are, without a doubt, among the best studied and most successful contemporary learning models. Today, GNNs are widely used in a variety of settings, including recommender systems (Wang et al. 2018: Ying et al. 2018), pharmaceutics (Fout et al. 2017 Do eet al. 2019 Ghorbani et al. 2022) and fraud detection (Dou et al. 2020). And yet, in spite of sig- nificant efforts and interest in the research community, our current understanding of the theoretical foundations of graph neural networks is still in its infancy.
In this article, we concentrate on the crucial task of training a GNN, i.c., determining the weights and biases which best match provided training data. We note that the computational complexity of the corresponding AL NETWORK TRAINING problem (NNT) has been extensively studied from the complexity-theorfe intractability even in highly restrictive settings (Goel et al., 2021 Froese et al., 2022, Froese & Hertrich 2023 [ertschinger al., (023) and exact algorithms targeting the problem (Arora al.) 2018| et al. [022]] Brand et al. 2023). And yet, until now no analogous insights have been available for GNNs. The aim of this article to change this not only by laying down the foundations for the study of the GNN TRAINING problem, but primarily by presenting highly non-trivial reduction which establishes the NP-hardness of the problem even for 1 1-dimensional GNNs.
point of view: there numerous recent results proving computational
MODEL AND FORMALIZATION. While highly successful line of peppricalll-driveen research has led to the introduction of hundreds of different variants and adaptations of GNNs to spe- cific settings (Zhou et al. 2020: Kanatsoulis & Ribeiro, 2024 Zhao & Zhang, (024), for our complexity-theoretic study we will focus on the standard formalization for the (semi-supervised) node-classification model as used, e.g., in the pioneering paper of Kipf & Welling (2017) and the survey of Wu et al. | We provide an intuitive and high-level description of such GNNs below, while formal definitions are deferred to Section 2
A graph neural network can be viewed as graph g = (V, E)) which performs certain computations over a specified sequence of consecutively processed layers. At each layer é, each vertex E V computes a vector H!! over reals called its feature vector; the vector's dimensionality depends on
'The model we use here is sometimes called Graph Convolutional Neural Networks and is arguably the most prominent GNN model date.

---

Published as a conference paper at ICLR 2025
the layer, and say that the GNN is a-dimensional if a is the maximum feature vector dimension- ality over all of the network's layers. While the initial feature vectors H are provided, at each other layer & 2 1 the network needs to compute H! from the feature vectors at layer & e- 1. In the standard model considered here, this will be done via the application of an aggregation function (which aggregates the feature vectors of and all of its neighbors in layer { - into a single vector K() and an activation Sunction (which transforms the aggregated vector K into H!!"). After the final layer is processed, the GNN reads the feature vectors at certain specified vertices; these are typically then passed on for further processing, e.g., to a multi-layer perceptron.
A range of aggregation functions have been considered throughout the literature, with notable ex- amples including SUM, MEAN and SPECTRAL S (Kipf & Welling/ 2017). The activation functions used for GNNs are typically the same as those used for neural networks, and in this work we focus primarily on the most widely used ReLU activation function. In line with the literature and previous
studies on neural network training (Abrahamsen et al. 202 Brand et al. 2023). we assume that the type of aggregation and activation function is fixed and uniform throughout all layers. However, the parameters of the activation function speecnicalllilil........ the weight and the will differ from layer to layer, and the task in GNN TRAINING is to compute the weights and biases of each layer which minimize the error on the output feature vectors (i.e., their deviation from the provided training data). While the error may be computed using a variety of error functions, for our main lower-bound result it will be sufficient use the simple Lo error function, which merely counts the number of mislabeled vertices.
RESULTS AND TECHNICAL CONTRIBUTION. It is rather straightforward show that GNN consisting of isolated vertices behaves just like a classical fully-connected neural network with the same activation function, where the number of nodes at each layer is precisely equal to the GNN's dimensionality at that layer (see Proposition 2 Hence, existing lower bounds for NEURAL NET- WORK TRAINING on fully-connected networks can be immediately transferred to GNN TRAINING on edgeless graphs; however, such results are only known for networks of high dimensionality (see Section 3 and stem purely from the intractability of training nigher-dimensiona ReLU functions without requiring any insights into the structure of the GNN or its aggregation function whatsoever.
On the other side of the spectrum lie 1-dimensional GNNs. For these, one in fact cannot hope to transfer lower bounds from NEURAL NETWORK TRAINING, the corresponding "purely 1- dimensional" ReL.Uacttivaed neural networks can be trained in polynomial time (see Proposition 7 later). Essentially, the 1-dimensional case is the crucial one for ReLt-activated GNN TRAINING (ReLU-GNNT): here both the aggregation and activation functions are easy to deal with in isolation, and the challenge stems from how these interact with each other via the graph structure. As our main result, we prove:
Theorem 1. 1-dimensional ReLU-GNNT is NP-hard for any Ly error function with p E [0, 1). and any of the following aggregation functions: SUM, MEAN and SPECTRAL.
The proof of Theorem I relies on an intricate reduction from POSITIVE-I-IN-3-SAM first developed for the SUM aggregation function and then adapted to the remaining two. On a high level, the difficulty of the reduction stems from the fact that while the weights and biases have a high degree of freedom at each layer, we need to achieve a correspondence between the training outcome and a solution to our initial SAT instance (where each variable is assigned to be either true or false). We note that it seems difffiull- perihaps even impossible-to reuse previously developed gadgets and insights targeting NEURAL NETWORK TRAINING, as there each weight and bias is associated with a single edge of the network while here the weights and biases at layer are applied globally to every vertex in the GNN on that layer.
which is
Essentially, our reduction allows us to associate each variable x; in the SAT instance with a pair of consecutive layers, and uses special gadgets to ensure that there are precisely two viable choices for weights and biases at these two layers: one corresponding to z; being true, and the other false. The truth value of x; is then stored in the form of feature vectors on vertices along dedicated pikh subgraphs. As the feature vectors on these subgraphs are subject to the same weights and biases that are used to encode the truth values of other variables, special care is taken to preserve
being
A variant of 3-SAT where each literal is positive, but each clause requires precisely one true literal to be satisfied; see also the proof of Theorem
2

---

Published as a conference paper at ICLR 2025
Rank
W
W
W W
S
W
P
2j
2n 2n++1
Variable
Variable
Variable Gadgets In.
Clause Gadget Clause Gadget
Gadgets 21
Gadgets 34
11 V
2z V Iy
Iy V Biy V In
ReLU-GNNT The vertices of the graph are partitioned into 2n + 1 ranks (visualized horizontal lines). For each variable Ti, we construct several identical path-like subgraphs spanning all of the ranks (depicted as multicolored columns): two for the variable itself and additional copy for each literal of x; in a clause. The path-like subgraphs for 2; contain a special Selection gadger at ranks 2i - 1 and 2i (depicted in blue), where the weights and biases determine whether the feature vector for æy all ranks above 2i encodes that x; is set to true, or false. On all other ranks up to 2n, the path- like subgraphs of x2 consist of specialized Waiting and Preservation gadgets (illustrated in gray and orange, respectively) which prevent the selection procedure for other variables from interfering with the feature vectors encoding the truth value of z₁. On the final rank, we use Clause gadgets to ensure that each clause is satisfied by their literals and Variable gadgets to ensure that each variable has been correctly set to true or false (depicted in purple).
Figure I: High-level construction for the reduction from POSITIVE- 1-----V--------SAA
the truth value of Iy during the whole course of the computation. In particular, our construction partitions the vertices of the instance into ranks and ensures that the only "relevant" feature values at layer are precisely the values of vertices belonging to rank l. In this sense, the GNN proceeds with the computation, the information can be seen as being "transmitted" along the aforementioned path-like subgraphs.
Once we have forced the GNN to make a choice for each of the variables, we use special gadgets in the final layer to verify that all of the clauses are satisfied by the truth assignment-this is done by ensuring that not satisfying a clause would lead to specified error threshold being exceeded. A high-level illustration of the reduction is provided in Fig. While the intuition of the reduction is easier to grasp when considering the SUM aggregation function, in our construction we ensure that the obtained graph is uniform-ae in particular, the degree of each vertex is precisely 6 6-wchch allows the proof to work analogously for the other two considered aggregation functions.
Finally, we complement main theorem with three complexity complexity-theoretie theoretic upper bounds.
Supplementary Result 1.
We obtain the first algorithmic upper bound for ReL U-activvie GNN TRAINING. In particular, we show that the training problem on a mixx-diimnsional GNN with n vertices and dl layers can be solved in time at most (101)0((ddd)) (ndA max) j(dd) where L the bit encoding size of the data.
Supplementary Result 2. Recall that ReL.tvattivted GNN TRAINING is computationally in- tractable even on edgeless graphs (as argued in the beginning of this paragraph), even for 1-dimensional networks (as shown in Theorem D This raises the question: what happens if we combine both of these restrictions? We show that at least under these severe restrictions and in the exact training setting
GNN TRAINING can be solved in polynomial time.
Supplementary Result We establish that exact GNN TRAINING under the same aggregation and dimensionality conditions as in Theorem T[-bbecmeee polynomial- -tim solvable when one uses linear activation functions instead of ReLU. While these are far less common than ReLU, we believe this algorithmic result to still be of interest as it follows up on previous cumplexity-theoree for linearly activated neural networks (Panigrahi et al.) 2020 Abrahamsen et al. [202 Brand et al. activated setting.
results
2023) and rules out analogue of Theorem in the exact innarrl-activvate
In exact training, the task is achieve an exact fit for the training data.
3

---

Published as a conference paper at ICLR 2025
2 PRELIMINARIES
Our notation follows prior works on graph neural networks (Kipf & Welling 2017 Wu et al. 2021 as well as the terminology established for the setting of training neural networks (Froese et al, 2022 Brand et al., 2023). A GNN for oniissuprr node classification with depth d is tuple (9, A, y), where = (V,8) is a graph with adjacency matrix A. The vector E N4+1 gives the dimensionality of each layer. If ma..ee Åe, we call the GNN a-dimensional. The GNN processes set of features of every vertex (the data), which is given by X E R| Further, VCV denotes a set of labeled nodes, and in the training setting we also have a function Y: Y RA which determines their target labels.
))
Given that our work focuses on ReLU- and linearly GNNs, we assume that trained GNN further comes with weights w(( E Rác-iXA, and biases B(0) E &A for each layer é E [d], where [d] (I....,d}, d3. The activations (features) the nodes in the hh layer are denoted by H())) E IR M In particular, write H X for the initial features and H for the final features. Features propagate over the layers. In general, propagation rule is of the form
H f(A, ((-1), (,,,
Graph Convolutional Networks (GCNs), which are the common type of GNNs that are considered in this article, are characterized by a certain form of propagation. There, one first aggregates the features of the node's neighborhood by given aggregation function (such as SUM, MEAN, or MAX) and then applies given activation function (such as ReLU linear activation) that involves the weights and biases. As common, we will assume a fixed aggregation function and a fixed activation function across all vertices and layers and call the GNN ReLU- or linearly-activant respectively. Formally, the feature of a node u V in layer & Z is defined as
H (v) activation (W()) aggregation (1 + B(O).
where N/e] denotes the closed neighborhood of in G.
For SUM aggregation and ReLU activation, the 7th dimension in the feature of a node v E V Vin layer é > 1 is computed
A (H = Σ (w
Σ (H ()) + B!!)) E!T) NEN(2)
where (z)+ max(0, z). The two other types of aggregation functions considered here MEAN aggregation, where factor W added before the inner sum, and SPECTRAL ag- gregation (Kipf Welling 2017). which adds factor of / As for the activation functions, in the final part of our article we will also consider linear activation, where (-)+ is replaced by (.)-
inside the innermost sum.
The error of a trained GNN is determined by an error function over the predicted and true labels of all labeled data points, where in real-life network the read-out data points the final layer would first undergo further processing through perceptron. For our results, we focus on the special case where the perceptron is trivial (i.e., merely outputs the identity). For p Q, the Lep error function considered here assumes we are given predictions Ú1,..., Ök and labels ..,.... and is equal to EieR l| 7 I. where || Il denotes the Euclidean norm. Of particular importance will be the case of p O, which simply counts the number of mislabeled vertices. In particular, we show that the training problem is Na-hard even in this particular setting.
We are now ready formally state the ReLU-activated GNN training problem considered here.
for Aggregation Function o and Error Function r
Input:
Graph G = (V, E), (d 1) -idiennsio vector A of positive integers, data X, set y of vertices labeled with Y, and an error bound I.
Question:
Are there weights W(1) ,..., Wid) and biases ((1) (()),..., B(d) such that the result-
ing error the ReLtvvattveeedd GNN using aggregation is most t?
4

---

Published as a conference paper at ICLR 2025
We define the training problem Lin-GNNT GNNs with linear activation analogously. Finally, assume that the bit encoding of the data X is provided on the input and that basic number operations can be carried out in constant time.
RELATION TO NEURAL NETWORK TRAINING
Before proceeding towards our main result, we first discuss some connections between ReLU- GNNT (Lin-GNNT) and the corresponding training problems classical neural networks. For classical neural network training. we follow the standard terminology and definitions used in the lit-
erature (Arora al. 2018 Boob al. 2022 Froese et al. 2022, Brand al. 2023) and denote the corresponding training problems as ReLU-NNT and Lin- NNT, respectively. Below, we formalize an equivalence between training edgeless GNNs and training fully connected neural networks.
Proposition 2. There a linear-time computable bijection I between (1) the set of ReLU-GNNT (or Lin-GNNT) instances with SUM, MEAN, or SPECTRAT aggregation where the graph is ()',0) 0) and (2) the set of ReLU-NNT (or Lin-NNT) instances where each pair of consec- utive layers is fully connected, such that the following holds. For all such GNN-training instances (G, A, X.Y.Y, ,Yt:))
I is yes-instance if and only if (I) is a yes-instance;
I and f(I) have the same depth, error function, and error bound t;
each layer & of the classical neural network architecture in (II consists of Ae nodes
As an immediate corollary of the previous proposition, we can transfer known lower bounds where the dimensionality is not bounded by fixed constant from ReLU-NNT to ReLU-GNNT. In par- ticular, the following observation builds on the hardness result from Froese et al. (202)).
Observation 3. ReLU-GNNT with SUM, MEAN, or SPECTRAL aggregation for any error error function Lpp p Q2o is NP-hard, even if the depth is d = 1, A = and the graph
(V, 0) consists of isolated vertices. Further, the corresponding problems cannot be solved time fAa)) (Ao))) for any computable function f unless the Exponential Time Hypothesis fails.
The above reduction works for any fully connected neural network with ReI.U-activated nodes, and may hence likely also allow one transfer other lower bounds from neural network training (Goel et al., 2022]; Bertschinger et al. 2023) to the GNNT setting; however, Observation 3 fully suffices for our aim of arguing the intractability of training nigher-dimension.. graph neural networks.
4 TRAINING ONE-DIMENSIONE GNNS IS NP-HARD
We note that the GNNs obtained in Observation 3 have a dimensionality of in the last layer, but the dimensionality of the first layer not bounded by any fixed constant. In fact, is impossible to leverage Proposition 2 to obtain lower bounds for training 1-dimensional GNNs, as the corre- sponding case in (see, e.g., Proposition 7 later). Hence, our lower bound for ReLU-GNNT in the base 1-dimensional setting must exploit both the structure of the network and the properties of the activation function.
neural networks boils down to training very simple architectures
For our hardness reduction we require the following observation, which allows to shift the ab- solute values of weights to the first layer. This lemma inspired by a similar result on classical neural networks (Brand et al. (003);; curiously, in the classical neural network setting this was used to obtain algorithmic results, while here it facilitates our construction of an NP-hardness reduction. For the remainder of this work, whenever consider features of dimensionality 1, we simplify the notation by w(() == (W(()), and b(C B as well as H = (H!*),
Lemma 4. Consider any 1-dimensional ReLU-activated GNN with SUM, MEAN, or SPECTRAL aggregation and depth d. For all weights and biases W, B Rd. there are weights W. B E Rd
Forr convenience, consider the 0 layer of an classical neural network to describe its input nodes, that is, the input dimensionality of the neural network equals Ap.
5

---

SAT problem Schaefer (1978): given a set of n variables Ti,..., In and m clauses of the form < I n), determine whether there exists assignment of the Published as a conference paper at ICLR 2025
such that for all but the first weight in W we have T produces the same feature at each vertex after layers as when using and B.
w "
{-1,1} and using W and B
.....
With Lemma 4in hand, we proceed directly to the proof of our main result.
Theorem 1. 1-dimensional ReLU-GNNT is NP-hard for any Lo error function with p [0,1). 1), and any of the following aggregation functions: SUM, MEAN and SPECTRAL.
Proof. We first show the statement for SUM aggregation and Lo-error, that is, each mislabeled vertex contributes exactly to the total error. We reduce from the NP-hard POSITIVE 1-IN-3-
(z; V 22 V 24 (for S variables to (TRUE, FALSE) such that each clause satisfied by precisely one literal.
We now construct equivalent I-dimensional ReLU-GNNT instance of depth d = 2n When describing the construction of the graph G. we will assign each vertex to a "rank"-ap an integer be- tween 0 and 2n 1. One basic building block used in our reduction is decision gadget, which is the subgraph depicted in Fig. that will intuitively be used to set a variable r; to be either TRUE or FALSE.
2
2(1 2)
2(1 - 1)
21
2(1 + 1)
2n
2n -
2n
Figure 2:
Decision gadget for variable T; Each column represents a rank. The blue color marks where the selection happens and the orange part preserves the selected value to the last rank and layer. Gray edges and gray dummy vertices are used to give every vertex except the ones in rank 2n (which will be connected rank 2 1) degree 2 or 4, which will later help us to turn the graph into one where every vertex has the same degree, namely 6, and allow for more convenient analysis.
We use the above building block in the construction of G as follows. For each clause I, x V Zg. we create a copy of each of the three corresponding decision gadgets (i.e., one for I;, one for x and one for z&) and connect these together via clause gadget consisting of clause check vertex and dummy vertex, as depicted in Fig. left). Assign the clause check vertex the label 2.
2n 2n + 1
2n
2n
+ 1
2n 2n + 2n
.
Tj
T.
T.k
Figure 3: Clause gadget (left), variable gadget (center), and integrity gadget (right). The black vertices are the clause check, variable check, and integrity check vertices, respectively, and are only labeled vertices in the graph. Gray edges and gray dummy vertices are used to give every vertex degree 2, 4, 6. Dots indicate that individual copies of the respective decision gadget are included, even if only the ultimate rank is depicted.
We want to ensure that all vertices x; representing a variable have one of two values in the penul- timate layer, which corresponds to the variable being TRUE FALSE. Thus, for each variable add two variable gadgets, each with a variable check vertex and a copy of the respective decision gadget, see Fig. 3 (center). Give one of the variable check vertices label and the other label 2. Last, pick an arbitrary clause y1 V 3/2 V y/ and add an integrity gadget that connects two decision gadgets for each of its variables (6 in total), Fig. (right). Give the connecting integrity check

---

Published as a conference paper at ICLR 2025
vertex label 3. We now define the rank of each vertex. The two left most vertices of each decision gadget are assigned rank and the rank of each other vertex equals its distance to any vertex of rank 0. Note that all labeled vertices (clause, variable, and integrity check vertices) have rank d = 2m + 1.
While this completes the main part of our construction, we further add a set of dummy vertices whose sole purpose is to make the constructed graph 6-regular (a property which will be useful when dealing with the MEAN and SPECTRAL aggregation functions). Note that all vertices have degree 2, 4, or 6. For each vertex o with degree at most 4, add copy of the clique K7. If has degree 4, delete an arbitrary edge from the K7 and add edges from v to the endpoints of e. If e has degree 2. delete two disjoint edges from the K7 and add edges from v to the 4 endpoints of these edges. This ensures that v and all added dummy vertices have degree 6.
For the data X, let X 1 for each vertex v in rank 0 and X,, 0 for every other vertex u. Observe that the constructed GNN training problem can be computed in time polynomial in the size of the 1-IN-3-SAT instance. high-level illustration of the construction for the most important elements is provided in Fig. [ and the complete graph constructed for exemplary, simple 1- IN-3-SAT instance visualized in Fig. 4 in Appendix B It remains to show that the constructed ReLU-GNNT instance has a solution with error at most if and only if the 1-IN-3-SAN instance has a solution.
Suppose there is solution (i.c., satisfying assignment) to the 1 1-IN-3-S 3-AT instance and consider the following weights w(S) and biases b(0), E [d]. Let (t) = 1 for all & E [d]. For all i E [m], if a; is TRUE in the solution, let 6(2i-1) -1 1 and (2x) = O. Otherwise, let 1(2 0 and ((2r) = -1. Let 1(2n+1) 1. Crucially, this leads to the following observations: As all biases except for the last one are non-positive and only vertices in rank 0 have positive feature in X, in layer E all vertices
with rank have H!! O. With this and as the only labeled vertices are in rank d 2n + 1, note that by our construction
the first time a vertex in rank r may take positive value layer = r,
this value is only determined by its neighbors in rank r- 1 in layer r- 1 (all other neighbors have feature in layer 1), and
whichever value a vertex in rank r takes in layers > r does not matter as this information does not propagate to the labeled vertices in rank d = 2n + 1 within the remaining layers.
In particular, this implies that the gray dummy edges and vertices in the gadgets do not impact the final features at the labeled vertices. With these observations, note that the two topmost (black) vertices e in rank 2j.j E [n]. in all decision gadgets have (( = 1, no matter which of the choices are made for the biases ((2i-1) and ((26) for all i I j: We prove this by induction over j. Clearly, it holds for j = 0. Assume for some arbitrary but fixed we have H! = 1 for each black vertex e in rank 2j. If ((2)+1) = -1 and ((2)+2) = 0, then for the black vertex v' in each gadget in rank 2j 1 we have H.
o' (2)+1) = 1 and for each black vertex v" in rank 2(j + 1) we have Hq" H2((++1) 1.
Otherwise, b(2j+1)= = 0 and 6(2)+2) = 11, so we have 11 (2j+1) = 2 and H p (2(++1)) 1.
Consider the decision gadgets of any variable x;, Note that in layer 2i 1 the two bottommost (blue) vertices have exactly one neighbor with feature 1 and all other neighbors have value 0 by the above observations. Thus, if ((22) = and 1/2i+1) = -1 then for the gadget's is hottom-most, blue vertex v in rank 2i + 2 we have H (2++2) 1 and if (224) -1 and 1(2i+1) 0 then H! (2 0. Next, observe that in the bottom (orange) conservation part, the value is conserved as in every odd layer the feature is increased by 1. This excess is subtracted either in this the next layer depending on the chosen biases. Thus, each vertex v with even rank r in the bottom path of variable x; will have H 1 if x; is TRUE and H 0 otherwise. This is in particular true for the vertices I; with rank 2n. Now consider the last layer d = 2n + 1. As we chose a variable assignment satisfying the 1-IN-3-SAY instance, each clause check vertex is connected to exactly one vertex
with dd = 1; all other neighbors v' have value (dd-1) = 0. Hence, for each clause check vertex 2. we have
H(d) (0(4) (1 + +0.6) 6)+ bb()) + (d) 2,
7

---

Published as a conference paper at ICLR 2025
incurring error. The integrity check vertex vy. does not incur any there
( = w (1 2 + 0 5) + ((d) = 2 + 6(d) = 3.
Further, exactly half of the variable check vertices mislabeled, giving total error of desired.
For the other direction, suppose there are weights and biases giving a total error of at most n. Note that for all & E [d], if two vertices v, v' have isomorphic ddistannee-eiighorrooddd with respect to the initial features X, then H! = H In particular, this applies to the final feature of the two variable check vertices for each variable. Hence, most one of these can be labeled correctly. As there are n such pairs of variable check vertices, we get that exactly one vertex in each pair is labeled correctly and all clause check vertices and the integrity vertex are labeled correctly.
Further, observe that every vertex in the graph has the same degree and (except for the ones in rank 0) the same initial value. Hence, for all r E [d]. all vertices in rank r and their adjacent dummy vertices have the same, uniform feature in all layers f < as by construction the non-uniform values from rank 0 only propagate by one rank each layer. For layer d 1, let be the uniform feature of all labeled vertices in rank d and their adjacent dummy vertices. This further implies that two vertices rank r with isomorphic (r-
in ranks r' S r have the same feature value in layer In particular, the orange vertex H; (or y:) in rank 2n has the same feature value in layer 2n d across all copies of the decision gadget for variable F₁. We hence refer to the feature value of any of these vertices in layer & by H (dd-1) With this, we can narrow down the weight and bias in the ultimate layer. By Lemma 4 we can assume w(d) E {-1,1]. First, consider the case (d)) = 1. Both the integrity check vertex and the corresponding clause check vertex (i.e. the one for the clause over the same variables as used in the integrity gadget) are labeled correctly, so
2(H 1) (d-1) + H(d-1)) + + b(d) = and
H(d-1) + H(d-1) H(d-1) 4a + ((4) 2.
in
Combining the equations gives ! H (d-1)
H (d-1) 3a + Applying this back Eq.
yields ((d) = 7a + 1. If w(d) = -1 we obtain H (d 9/
+ 1110 (d-1)
1) + H (d-1) 3a - 1 and b(d)
yn
Ta + 1. Next, consider any variable and assume (d) = 1. Exactly one of the corresponding
variable check vertices is labeled correctly, so exactly one of the following two equations is true:
((d-1) + 6a + b(d) = 2, that is,
H(d-1) =a or
(d-1) + 6a + b(d) 1, that ((d-1)= =
We let be TRUE in the first case and FALSE otherwise. Similar to Eq. 1 for each clause T; V xy V Ie the corresponding clause check vertex enforces
+ 4a + ((d) 2, that is, !dd-1) (d-1) H(d-1) 3a + 1. # (d-1) H( + -1
This holds if and only if exactly one of the variables wi, Ttj Ty.. TRUE giving a yes-instance of 1-IN-3-SAT. The case (d)) 1 works analogously. For all E [n]] we have that either
2; (dd-1) 1) 6a + (d) = 2, that is,
Hdd a-1 or that is, H(d-1)
H((d-1) 6a + b(d)
We let x; be TRUE in the first case and FALSE otherwise. For each clause V Iÿ V the corresponding clause check vertex enforces
-H(d-1) -10--)-H---10
1) 4a + = 2, that is, H(d-1) + H(d-1) ((d-1)
H2y 22 = 3a 1,
which holds if and only if exactly one of the variables x,, Ky, TR is TRUE.
The only purpose of the I. error function is to ensure that the error incurred by the variable check vertices is minimal if exactly one of the labels is met exactly (and not if the final feature is somewhere in between the labels and 2). Thus, the same construction with an correspondingly updated error bound can be used with any L, error function for which p E [0, 1).
Further, on 6-regular graphs, such as the constructed one, the aggregation variants in the statement can be translated to each other by multiplying or dividing all weights by 6. Hence, solving ReLU- GNNT on this instance with SUM aggregation trivially reduces to solving the same instance with MEAN SPECTRAL aggregation, yielding hardness for these settings as well.
8

---

Published as a conference paper at ICLR 2025
5 ALGORITHMIC UPPER BOUNDS AND TRACTABLE CLASSES
In this section, we obtain three results which can be seen as counterparts to Theorem T
SUPPLEMENTARY RESULT 1. We begin by establishing general algorithmic upper bound for solving ReLU-GNNE
Theorem S. dimensiimss ReLU-GNNT with SUM, MEAN, or SPECTRAL aggregation and any Lp error function for non-negative integer p. depth d and graph of n. vertices can be solved in time L ((nddAun) (ndA max) (dds) where the bit encoding size for the data X.
Proof. We begin by exhaustively branching determine the following information: for each vertex dimension i and layer é, whether the ReLU function will flatten the feature of v at dimension i and layer é, i.e., whether (H)( ); O. This requires overall branching factor of most 2ndAmax and allows us to concentrate on the case where we assume to have this information available.
For each branch, we construct set of (in)equalities (i.e., constraints) whose variables represent the set of weights W and biases B in the GNN. In particular, we use a variable for each scalar in every weight and bias, that is, for all & [4]
[ and [A+-1], we have the variables (W!(), ) and B For convenience, we define for each & E (O....,d d}, every vertex and dimension i [Ac] placeholder a!4 which represents a term capturing the value of (H())) ); these will be used state our constraints more concisely. The definition of these placeholders is as follows:
For all [Ao] and each vertex v, we define v; o (X,);. We define of 0 for all places where we branched that (H),)) = 0. The remaining placeholders are defined recursively by
B(O
Σ WEN
where we let C = 1 for SUM, C = [N[u] for MEAN, and C VIN Nul for SPECTRAL. aggregation. For each (( which our current branch assumes be flattened, we add a constraint
requiring B Σデ= (W! requiring
(e) EvENY )u) s while for all others we add a constraint
(1) 2 0.
Let be the error bound. To complete the construction, we distinguish two subcases. If = 0 (i.e., if the error function merely counts the number of mislabeled vertices), we perform an additional round branching to determine a set of [)]] vertices which will be labeled correctly, and in
each such branch add constraint of the form 2i (d) Yo)) for each selected labeled vertex and dimension
[Aa] This yields another branching factor of (?²)) S 2". On the other hand, p > add one constraint / Evey ||0 (P).
Having constructed the set inequalities described above, we invoke Renegar's 's Theorem (Renegar) 1992a blc) to solve the corresponding instance of the formula in the Existential Theory of the Reals.
Observe that in both cases, weights and biases that label the data as desired yield a solution to the system of (in)equalities and, vice versa, a solution the system yields such weights and biases. Thus, deciding whether the system has any solution decides the ReLU-GNNT problem. In both cases we have (ddA) variables and O(ndAmax) constraints. Note that each constraint has total degree (d). Such an instance of the Existential Theory of the Reals can be decided in time in
(1) (ndA max) ) ((d4 (Renegar 1992a blc. Combining this factor with the number of branches yields the stated runtime bounds.
We note that the same approach can be used to solve Lin-GNNT. There, the algorithm skips the branching step and drops all constraints except for those of the form Di (d)
=Y(v);
Corollary 6. -ime-eiimnso Lin-GNNT with SUM, MEAN, or SPECTRAL aggregation, error bound I, and any Inp error function for non-negative integer p. depth d and graph of vertices

---

Published as a conference paper at ICLR 2025
can be solved in time LO()) (ndd (iddSann) if 0 and in time L 12(1(2))) (nd ((dsmn))) if p = O, where L is the bit encoding size for the data X.
Next, we proceed with establishing the polynomial-ting solvability of exact training for GNNs which are both 1-dimensional and edgeless. Towards this aim, we first tackle the neural network training problem in the corresponding setting.
SUPPLEMENTARY RESULT? 2.
Proposition 7. For any hones error function, ReLU-NNT with 0 and precisely one node per layer can be solved in polynomial time.
Propositions and yield tractability for 1-dimensional ReLU-GNNT on edgeless graphs. Theorem 8. 1-dimensional ReLU-GNNT with t = O on edgeless graphs with SUM, MEAN, or SPECTRAL aggregation and any honest ervor function can be solved in polynomial time.
SUPPLEMENTARY RESULT 3. Finally, for the simpler linear activation function, we are able to improve the result of Theorem 5 in the setting of exact training and uniform dimensionality polynomial time algorithm. First, we provide a weight shifting argument that reduces the number of non-trivial weights. For the following. let Ia denote the identity matrix with dimension a E N.
Lemma 9. Consider any linearly-attvvteed GNN with SUM, MEAN or SPECTRAL aggregation and depth d such that Dn =
Aa. For all weights and biases W E pdx &o A B E IR So, there are weights W. B such that all for all l E {2....,d d} we have W(f) = Iao and using W and B computes the same feature function at each vertex in the final layer as when using W and B.
We are now able to give a polynomial time algorithm for Lin- GNNT instances where all layers have the same wwwprsiionnnityinllddiiin use Lemma to assume without loss of generality that all but the first weight matrix in the solution the identity matrix, we can provide system of linear equations equivalent our problem and solve it in polynomial time.
1-dimensional networks special case. Intuitively, once
Theorem 10. Lin-GNNT with SUM, MEAN or SPECTRAL aggregation, = O, and depth d such that Ag ... Da with any honest error function can be solved in polynomial time.
CONCLUDING REMARKS
Our main NP-hardness result can be interpreted as showing that the intractability of GNN training does not stem solely from the inherent difficulty of multidimensional classical neural networks train- ing, and hence one cannot hope to make progress by designing heuristics targeting solely this aspect. Still, we view it as merely the first-albeit critical-step towards understanding the complexity of training GNNs, one which opens us multiple follow-up questions. For instance, can one identify natural classes of network architectures which allow for efficient (i.e., polynomial-tima training in the 1-dimensional (or, more generally, d-dimensional for constant d) setting? Our Theorem [ ex- cludes efficient training for planar networks as the instances arising from the reduction are in fact planar, but leaves open the question of whether one can efficiently train networks which are, e.g., acyclic. Another question that remains open whether ReLU-GNNT for 1-dimensional networks is also in NP, or lies higher in the polynomial hierarchy; here, one can note that the training problem on ReLU-activated classical neural networks was recently shown to be complete for the complexity class 3R, which lies between NP and PSPACE (Bertschinger et al. (023).
Another important branch of follow-up question asks for the complexity of training variants of graph neural networks that differ from the one discussed here. These includes varying the GNN's objec- tive (e.g., graph classification instead of node classification), the propagation paradigm (by going beyond message passing), the employed activation and/or loss functions (e.g., by considering Leaky ReLU or Sigmoid activation, the Lp loss function for p 2 2, or the cross-entropy loss af- important base case in the
ter some perceptron post-processing). We believe work acts exploration of these areas.
An error function is honest if it returns value of 0 precisely when the network perfectly fits the data Hertschinger al. 2023).
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors acknowledge support by the FWF Science Fund (FWF projects 10.55776YY329 and 10.55776/COF12). Mathis Rocton additionally acknowledges support by the European Union's Horizon 2020 research and innovation COFUND programme (LogiCS@ Begics@@UWieen, grant agreement No 101034440).
REFERENCES
Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Training neural networks is ER-complete. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems (NeurIPS 2021), volume 34, 2021.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In 6th International Conference on Learning Representations (ICLR 2018), 2018.
Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. Training fully connected neural networks 3r-complete. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems (NeurIPS 2023), volume 36, 2023.
Digvijay Boob, Santanu S. Dey, and Guanghui Lan. Complexity of training relu neural network. Discrete Optimization, 44(Part): 006200, 2022.
Comelius Brand, Robert Ganian, and Mathis Rocton. New complexity-theorede frontiers of tractability for neural network training. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems (NeurIPS 2023), volume 36, 2023.
Kien Do, Truyen Tran, and Svetha Venkatesh. Graph transformation policy network for chemical reaction prediction. Ankur Teredesai, Vipin Kumar, Ying Li, Rómer Rosales, Evimaria Terzi, and George Karypis (eds.), Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2019), 2019.
Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng. Hao Peng, and Philip S. Yu. Enhancing graph neural network- based fraud detectors against camouflaged fraudsters. Mathieu d' Aquin, Stefan Dietze, Claudia Hauff, Edward Curry, and Philippe Cudré Mauroux (eds.), 29th ACM Interna- tional Conference on Information and Knowledge Management (CIKM 2020). 2020.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wal- lach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Infor- mation Processing Systems (NeurIPS 2017), volume 30, 2017.
Vincent Froese and Christoph Hertrich. Training neural networks is np-hard in fixed dimension. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems (NeurIPS 2023), volume 36, 2023.
Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of relu network training parameterized by data dimensionality. Journal of Artificial Intelligence Re- search, 74:1775-1790, 2022.
Mahsa Ghorbani, Anees Kazi, Mahdieh Soleymani Baghshah, Hamid R. Rabiee, and Nassir Navab. RA-GCN: graph convolutional network for disease prediction problems with imbalanced data. Medical Image Analysis, 75:102272, 2022.
Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, and Daniel Reichman. Tight hardness results for training 2 relu networks. In 12th Innovations in Theoretical Computer Science Conference (ITCS 202]), volume 185 Leibniz International Proceedings in Informatics (LIPlcs), pp. 22:1- 22:14, 2021.
11

---

Published as a conference paper at ICLR 2025
Charilaos Kanatsoulis and Alejandro Ribeiro. Counting graph substructures with graph neural net- works. In The 12th International Conference on Learning Representations (ICLR 2024), 2024.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In 5th International Conference on Learning Representations (ICLR 2017). 2017.
Abhishek Panigrahi, Abhishek Shetty, and Navin Goyal. Effect of activation functions on the train- ing of overparametrized neural nets. In 8th International Conference on Learning Representations (ICLR 2020)., 2020.
James Renegar. On the computational complexity and geometry of the first-order theory of the reals, part I: introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of Symbolic Computation, 13(3):255-300, 1992a.
James Renegar. On the computational complexity and geometry of the first-order theory of the reals, part II: the general decision problem. preliminaries for quantifier elimination. Journal of Symbolic Computation, 13(3):301-328, 1992b.
James Renegar. On the computational complexity and geometry of the first-order theory of the reals, part quantifier elimination. Journal of Symbolic Computation, 13(3):329-352, 1992c.
Thomas J. Schaefer. The complexity of satisfiability problems. In Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho (eds.), Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978), 1978.
Jizhe Wang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. Billion- scale commodity embedding for e-commerce recommendation in alibaba. In Yike Guo and Faisal Farooq (eds.). Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2018), 2018
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 32(1):4 3:444000 24, 2021.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Yike Guo and Faisal Farooq (eds.), Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2018), 2018
Kesen Zhao and Liang Zhang. Causality-inspired spatial-temporal explanations for dynamic graph neural networks. In 12th International Conference Learning Representations (ICLR 2024),
2024.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changeheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020.
12

---

Published as a conference paper at ICLR 2025
A APPENDIX: FULL PROOFS
PROOF OF PROPOSITION
Proof. For every depth d ReLU-GNNT (or Lin-GNNT) instance I = (9, X,,, ,t) we struct a ReLU-NNT (or Lin-NNT) instance f(I) as follows. Let N be fully connected neural network architecture of depth (that is, NN' yields consecutive propagation steps). Let each layer l E (O....,d) d in N consist of A ReLU-activated nodes. Let D contain data point (X.. Y()) for every labeled vertex v E V. Keep the same error bound and enror function. Note that this construction describes a bijection between the two sets of instances and ʃ as well as its inversion f are computable linear time.
It remains to argue that f preserves yes- and no no-instances, which we prove by showing that each set of weights W ..... W(d) and biases (()) ..... B(d) incurs the same error on I as on f(Z). Fix
any such of weights and biases. Recalling Section 2 let (H be the value of the 7th dimension in layer l at vertex u, when processing the GNN in Z with these weights and biases, Analogously, for each data point (ar, v) E D, each layer l {0, {O....,d], dd, and all [Ar], let (fr(e) (2:1)) denote the value of the th node in layer in the neural network W of fI) when processing data point (æ, y)
with the fixed weights and biases. Let g be the bijection that associates each vertex v I with its associated data point g(v) in fZ)) We prove by induction over the layers that (H = (A s( );
for all choices of u, l, and i. By construction, we have (H."); (H s(e))i. Further, the propagation rules in classical neural networks and GNNs respectively yield that
(1 s(o));
Σ (w (1 B,00 9(0)
and
(HF))) = Σ (w())) (HI + B(0)
is edgeless and hence [lu] {o}. By the induction hypothesis have (Fr((--)) (I! and thus (ir()) (X,, (v)). the error on both instances is the same. The same reasoning holds for linear activation
9(v)
(H!"),. As this holds particular for = and as g(v)
when all (+)+ are replaced by (-).
PROOF OF OBSERVATION
Proof. We reduce from ReI.U-NT with depth 1, n input nodes, and 1 ReL.U-activated output node. This problem is NP-hard and cannot be solved in time f() D o(Do) for any computable function f unless the Exponential Time Hypothesis fails (Froese et al. 2022]. We note that strictly speaking, Froese al. (2022) show hardness on depth 2 neural network where the hidden layer consists of I ReLU-activated node and the output layer consists node that is activated by mul- tiplying the value at the hidden node by weight
11, Nevertheless, their construction immediately also yields the lower bound for the case where the output layer is omitted and the train- ing occurs directly the ReLU-activated neuron. The WP-hardness for depth ReLU-GNNT then follows by Proposition
PROOF OF LEMMA
Proof. We start with the weights W and biases B and iteratively update them have weights in
(-1,1) while preserving the computed features. Let é be the last layer with w(() & {1,,1). If
f = 1 there is nothing to prove. Otherwise, update the weights and biases by setting
(4) := sgn (w (w)
()--1) = |1o()) (e-1)) and p(e-1) = (((e11)
where sgn(x) if x 2 and sgn(x) = 11 otherwise. Then replace the respective weights and biases accordingly. The updated weights and biases produce the same features as before: Consider
13

---

Published as a conference paper at ICLR 2025
any vertex with closed neighborhood No... With the original set of weights and biases we have
H = (wil)
Σ MEN/ol
1 C
( H( + b(c-1)) + tb(0)),
where C- for SUM, C
[N[u]] for MEAN, and C v M N for SPECTRAL aggrega-
tion. For the updated weights and biases we have
H = ())(((())
Σ MEN
(w0
(((0)(()1))) + +b(0))
+
C
If (1) = 0 we have H¹: = _ = (blo))t. Otherwise observe that for all u E NNll we have
(o(t-1) H + b(e-1) S 0 if and only if
Hl(-1) + |w(0)b((-11 < 0. Hence, for all
u W N[u].
w 1) 11 (e(11)
+ ((=-1))+ sgn(w (1w) 1) + 11100(1111)
and thus H H! This procedure can be repeated until é 1.
PROOF OF PROPOSITION
Proof. We prove the statement by showing that every 1-dimensional ReLU-NNT instance of depth > 3 can be reduced to an equivalent 1 d-dimensional instance of depth at most 3. We start by proving by induction over the layers that the function computed by N on D in layer E can be expressed by
(x) w min(k, max(j. +
for some j, vi, d E IR with j S k. In the input layer = O, the claim holds by letting u = 1, d = 0,j = mi,(r,,))) Ti, k (a Ty.. Now assume the claim holds in any fixed layer é. Let the weight and bias for layer é + 1 be w(++1) and 6(++1), Then, by the inductive hypothesis, the function computed in layer E + 1 is
(x+ = (f+ min(k, max(j, x)) + wo (0+11) +b(0-1))
If (e+1)) = O. the claim holds for layer & + 1 by letting w/ = 0 and 8' = max(0, b(01)). If u = 0, the claim holds with w = 0 and 8' max(0, 1) + b((+1)). Otherwise, let
T T (e+ G ú' (e(+t)) + b(e+1), Teur (6 b((++) ((c+1)/w((11)))) (eo
Consider function g(x) (wr + b)+ for any w, x E E and let Tew -b w. Note that we have g(x) = w max TTurs x + b if w > 0 and g(x) = w min(Temt x) + if w < O. Thus, we get for all in D that
b/ww.
f (++ 1) min(k', max(j', x)) + (e+ + b(++1) = w min(k', max(j', xx)) + U/ where we let j' = max(j, Fem)) and k' = max(k, Zem) if (e+ 0 and j' min(j, Fcm) as well as k'' = -min(k Fcc)), otherwise.
Let w. j.j. and l be as for fd in the last layer of N. We now construct a Rel.tivativ 1 1-dimensional trained neural network A' with depth d' S that computes fd on D. If / 0, let d' 1, (1) 0, and ((2) = b. Otherwise, we require depth d = 3. If T > let
(1) w. (()) wjj m2 -1, 6 w(k j), (3 11 b = 5 wk.
Then, " computes the function
s(xx) = (- (-(wr wj)+ + ul: (k - 1)) + + i + úik
= --- (- ((mmmx((j))) wi) + o(k j)) + b + wk +
14

---

Published as a conference paper at ICLR 2025
where we expand the innermost (+)* using the observation g(z). We further get
(x) = i max(j.)) + uk)+ + b -ikk
(- (--mmin(ff mix + tbk) + b uik
= ü min(k; max(jj=) x)) + +6)
If w < 0, let
(() = |لت (0) = - w (2) 1, ((2) (k - j), w 1, 6(3) = + wk.
We can reuse the above steps except the last one get that here the computed function is the same:
(()x) = ((-būi) ((-())
min(k, max(j,))) + |=](k) + d wk) = (i6 min(k, max(j, + +b)
As M is ReLU-activated and is described by fd+ (xx) = w min(k, max(i, xt) ) + on D, we know that fat1 (x;) 2 for all x; in D. Hence, for all x, in D, we have f'(x) (
N\ can express the same set of functions on D as N, solving the training problem for / reduces to solving the training problem on N' when using the same data set D. error function, and error bound. The latter, with depth at most 3 and just one node per layer, can be decided in polynomial time, for example by the algorithm Brand et al. (2023). We note that while their result stated for the L2 error function, it also holds for every other honest error function as one honest error function yields error 0 and only if all other honest error functions do the same.
PROOF OF LEMMA
Proof. We start with the weights W and biases B and iteratively update them to obtain identity matrices for the weights while preserving the computed features. Let & be the last layer with W o Ioo I = I there is nothing to prove. Otherwise, update the weights and biases by setting
(0 = Jsu, Wr(t-1) = (((((( and B(c-1) = w(O) B(C-1)
Then replace the respective weights and biases accordingly. The updated weights and biases produce the same features as before: Let n denote the number of vertices in the graph G, let Á A + I, be its adjacency matrix with forced self-loops, and let D be its degree matrix that has the vertex degrees along the diagonal and Os everywhere else. The forced self-loops increase the degree of every vertex
by 1. Let C C' = In for SUM, = D-1 and C = I, for MEAN, and C = C' = D 1/2 for SPECTRAL aggregation. With the original set of weights and biases we have
H w(O (w ((t + B(t-1) B(O)
while for the updated weights and biases we have
II. ((W ( + w(t-1()))) + B(0) = -1
This procedure can be repeated until 1
PROOF OF THEOREM LO
Proof. For every such Lin-GNNT instance, if there is a solution at all, then there are weights and biases such that all but the first weight matrix the identity matrix (Lemma 99. Finding these weights and biases corresponds to finding a solution for the following set of linear equations. Let there be variable (w:")), for all i,j [Ao] and a variable eiS)) for all e e [d] and e [Ao]. For convenience, we state the equations using a placeholder v! for every E (0...., d). every vertex v, and dimension i [Ao]. For all i [Ao] and each vertex v, we define v.()) (X,); and
Da Σ O
of D B("
Σ
d.
1=1
WEN(U)
15

---

Published as a conference paper at ICLR 2025
where C' = 1 for SUM, C |Mub]] for MEAN, and = v tion. The remaining placeholders are defined recursively by
[N
[uu] for SPECTRAL aggrega-
(2)
1 B
Σ
Σ aEN(2]
4 )
For every labeled vertex E y and E [Ao]. add the equation Y(u) o/ This is a linear
equation as, even though the o are defined recursively, in none of the expressions two variables are multiplied with each other. As there are (A + d) variables, the system of linear equations can be solved in polynomial time (c.g., by Gaussian elimination).
16

---

Published as a conference paper at ICLR 2025
B APPENDIX: ADDITIONAL FIGURE
Decision Cadget dt
Docision Gadger
Variablee Gudget xy
Decision Godget ds
Decision Gadges
Clanse Gudipet Ty Jg Vag
Varioble Gudlee
Decision Godget ia
Decision Godges X3
Varialle Garlyot
Docision Godgee Pz
Viriabble Gadget
Decision Gadget its
Docision Gadges 20
Variable Garlyot
Decision
Decision Gadges 23
Variable Gadget
Decision Codget
Decision Godget
Lategricy Gadget 2y Wr Va
3
Docision Codget
Decision Gadget
Figure 4: The graph constructed in the reduction for Theorem 1 for 1-IN-3-SAT instance with variables 31, F2, I3 and a single clause 21 I2 F3- The initial label (data) for each vertex is O, except for the leftmost vertices, where it is (marked with 1 in square). Target labels are marked with a circle. The error bound is 3, i.e., the number of variables in the I-IN-3-SAT instance. An exemplary solution that corresponds to setting only to be TRUE is setting
for all i e (1....,7) 7} and bj = b, = bg = 0 and by = by = by = - and by = 1. This way, the rightmost orange vertex of each decision gadget for 21 has value in the penultimate layer. The rightmost orange vertex in decision gadget for 22 and the rightmost blue vertex in the decision gadget for æa well all labeled vertices and their dummy-neighhors have value 0 in that layer. Hence, in the ultimate layer, with the added bias of 1, the labeled clause gadget vertex has value 2 and the labeled integrity gadget vertex has label 3. The solution mislabels only the labeled vertices in the first variable gadget for ii and the second variable gadgets for xy and Øz, respectively.
17


Reviews:
[{"review_id": "DwfoycgTet", "reviewer": "Reviewer_tj5Z", "summary": "The paper studies the computational complexity of graph neural networks, with a focus on one-dimensional GNNs. The primary result is the NP-hardness of training ReLU-activated one-dimensional GNNs. In addition, the paper provides algorithmic upper bounds for the training problem in the ReLU-activated setting, and shows that the one-dimensional, edgeless setting can be solved in polynomial time, as can the linear-activation case.", "questions": "Q1. The paper presents an interesting result and the proof is innovative. On the other hand, as raised in W1, it is challenging to see how this extends our understanding of GNNs in an important way. Could the authors provide an explanation of how they expect the provided results to impact further theoretical work that studies GNNs in the more interesting multi-dimensional setting? Or to the settings that go beyond message-passing (which has known limitations in its expressiveness)? Is there a way to build on the presented proof techniques and use similar concepts for other problems?  \n\nQ2. Can the results be extended to the graph classification setting? (Or if it is potentially challenging, can you see paths towards this? Or would it require a totally different approach?) \n\nQ3. Can the authors comment on any connections with their work and the line of research that investigates logical expressiveness (e.g., [R1,R2])? Perhaps there is not an obvious connection, but it would seem that characterization of the types of logical expressions that GNNs are capable of describing has connections to a complexity proof that relies on a linkage to a logic problem. Related to Q1, this branch of work usually assumes a vector at each node, and this is key to expanding the expressive capabilities.\n\n[R1] M. Grohe, \"The Descriptive Complexity of Graph Neural Networks,\" 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Boston, MA, USA, 2023.\n\n[R2] Barcelo et al., “The Logical Expressiveness of Graph Neural Networks,” in Proc. ICLR, 2020.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "S1. The paper studies an interesting problem that has received little attention in the graph learning community and provides an intriguing result. \n\nS2. The proof technique is innovative, with an elegant reduction based on a non-intuitive connection between a graph learning task and a logic problem. \n\nS3. The paper is well-written. In particular, the results are presented very clearly and proofs are logically structured and readily followed.", "weaknesses": "W1. It is challenging to see how the main result extends our understanding of GNNs in an important way. From the perspective of intellectual curiosity, I can appreciate the work as a welcome answer to a question. The proof technique is innovative and elegant. But in most cases, both practical and theoretical (in terms of quantifying the expressive capabilities of a GNN), we are interested in the multi-dimensional setting. Aside from this, the theoretical work focused on pushing the bounds of expressivity has veered away from the simple message-passing approach. The authors don’t provide a clear explanation in the introduction or the conclusion concerning how the presented work is expected to provide further impact. \n\nFor many problems, if we want to understand the multi-dimensional setting, then it makes a great deal of sense to first understand the one-dimensional setting. That doesn’t seem to be so clearly the case here, since we already know that the multi-dimensional setting is NP-hard. So how do we gain from deriving special-case results for the one-dimensional setting that can’t be extended to the practically interesting case? \n\nW2. The paper focuses on the (semi-supervised) node classification setting of graph neural networks. While this is clear from Section 2 onwards, it is not mentioned in the abstract or introduction. Graph classification is a very common use case of GNNs, and many of the theoretical results concerning expressivity focus on a GNN’s ability to differentiate between two graphs. The abstract, introduction and limitations section should make the limitations of the derived results much clearer.", "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": "", "extra_scores": {}}, {"review_id": "o5UFzUHk2A", "reviewer": "Reviewer_Z1QF", "summary": "The paper investigated the computational complexity of training GNNs, with a particular focus on the NP-hardness of one-dimensional GNNs, and authors demonstrated that training ReLU-activated GNNs is NP-hard under specific aggregation functions, such as SUM, MEAN, and SPECTRAL Additionally, the paper established upper bounds on algorithmic efficiency and examines how different network architectures affect training efficiency.", "questions": "Refer to wekenesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. In section 4, the paper clearly constructed a graph that intuitively represents the structure of GNNs, effectively describing the nodes, edges, and the logical relationships associated with Boolean variables, and it also designs several gadgets to ensure the resolution of the SAT problem, providing an excellent insight into the complexity of GNN training.\n\n2.  The paper presented a rigorous theoretical derivation and, in Section 5, established a general algorithmic upper bound for solving ReLU-GNNT, providing an important theoretical framework regarding the complexity and feasibility of training ReLU-GNNT.\n\n3. The paper proved the NP-hardness of training graph neural networks, which provides an important conclusion for exploring the complexity of training GNNs.", "weaknesses": "1. In line 308, when constructing the graph in Section 4, the author explained that gray edges and gray dummy vertices are introduced to ensure the nodes have degrees of 2, 4, or 6. What is the rationale behind it? Is it only applicable when the node degree is even, rather than simply being constrained to the specific values of 2, 4, or 6? The author could enhance clarity by providing further explanation on this matter to improve the readability of the paper.\n\n2. The paper researched the NP-Hardness of training ReLU-activated one-dimensional GNNs. The conclusion is primarily correct for the ReLU activation function. If the GNNs' activation function is changed, such as to Sigmoid or Leaky ReLU, the conclusion may be affected. It would be helpful if the authors could provide more theoretical analyses regarding this issue to make the paper more persuasive.", "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": "", "extra_scores": {}}, {"review_id": "vGIVkwQAZ6", "reviewer": "Reviewer_onPv", "summary": "The main result is showing NP-hardness for training a 1-dimensional GNN (i.e. the input dimension and width are 1). The proof uses a reduction from the positive-1-in-3-SAT problem. Several other results are given such as exponential time algorithm for training 1-d GNN, polynomial time algorithm for training GNN on edgeless graphs, and polynomial time algorithm for training a linear GNN.", "questions": "- How does this work compare to previous works? Specifically, are there any previous works on the hardness of learning GNNs? \n\n- Can the hardness result from Froese and Hertrich 2023 on 2-d networks be transferred to GNNs?\n\n- The depth of the GNN in Theorem 1 isn’t mentioned. Does it work for any depth?\n\nI am willing to reconsider my score based on the author’s response.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The main result (Np-hardness of 1-d GNNs) is interesting and uses a non-trivial reduction.\n\n- The supplementary results, provide further insights into the problem.", "weaknesses": "- There is no related works section, so it is difficult to position this paper w.r.t previous works. For me, it is difficult for me to determine how novel the result is since I don’t know previous works on the hardness of learning GNNs. It would be helpful to provide a thorough literature survey and more in-depth comparisons to previous works.\n\n- Froese and Hertrich 2023 show that training neural networks is NP-hard even for input dimension 2. Can’t this result be used on GNNs for edgeless graphs using Proposition 2? If so, the contribution of this paper seems incremental as it improves the hardness result from input dimension 2 to input dimension 1.\n\n- The hardness works only for node classification tasks. There should be a discussion about graph-level tasks, which are widely used in practice (perhaps even more than node-level). As a remark, it is OK to focus on node-level tasks, but still, graph-level tasks should be at least discussed on some level.\n\nOn the presentation level, the introduction is a bit long and convoluted (almost 3 pages long), which makes it difficult to understand the main message of the paper.", "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": "", "extra_scores": {}}, {"review_id": "asfb3hCUEd", "reviewer": "Reviewer_bLnv", "summary": "The paper shows that 1-dimensional GNN training is hard. In precise wording, for a $L_p$ norm error, finding the optimal weights and biases that decreases the error between the predicted label and the ground truth label lower than a threshold (decision problem) reduces to 1-in-3 SAT problem (same as SAT but each clause has to be satisfied with only one variable). \n\nThe paper is novel in sense that other hardness results for neural networks can be used for applied to multi-dimensional GNNs, but here the authors show the same for 1-dimensional which in NNs there is a polynomial time search for it.\n\nThe authors follow by introducing algorithmic upperbounds for special cases of NN training and GNN training.", "questions": "I believe the core part of the paper is Theorem 1, and with the theoretical nature of the work the qualification of the paper mostly boils down to checking the proofs. However the proof, and the theorem statements are unclear. I think answering following questions can help me to understand it more, and also placing these answers in the paper enhances its readability:\n\n1. What does the ranks encode. Why there are 2 ranks per node. How a node is assigned to a rank? The authors just introduced the terminology while leaving out the intuition behind using it. Specifically what does this sentence mean?\n> In particular, our construction partitions the vertices of the instance into ranks and ensures that the only “relevant” feature values at layer l are precisely the values of vertices belonging to rank l.\n\n2. In theorem 1, and in general please specify what is the range of the labels. It can be that the labels assumed in theorem 1, range differently compared to the more general setup.  \n\n3. Please specify the correct labels of the graph in general. Which nodes should be labeled? which nodes are left without labels? \n\n4. Please specify a simple case of 1-in-3 SAT (e.g. with one or two clauses) alongside the corresponding instance of GNN training so it becomes clear what each gadget is introducing to the problem. \n\n5. Number of the layers are not fixed at the beginning of the problem. From lemma 4 it is understood that a 1, or 2 layer GNN is representative of the overall problem. Is that so? If yes please specify that without loss of generality we can assume 2, layers. \n\n6. (Similar to 5) Why there is no relation between the number of layers and any other element in the corresponding graph. The graph seems to be only a function of the 3-in-1 SAT problem. In that case what is the difference between 2 and any n-layer GNN?\n\n7. Why the rank in integrity gadget is 2n, 2n+1 and then again 2n? How many times a clause is repeated as gadgets? Why in the integrity gadget the grey center node is not connected to the black one? \n\n8. What is the configuration of labels w.r.t. clauses in the SAT problem? Please provide an example SAT and show the graph and model labels alongside the prediction of the model.\n\n9. What is the loss in the decision problem corresponding to a given SAT instance?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The approach to the problem was really non-trivial. The target reduction problem was unexpected to me and like any other algorithmic lower bound, the reduction requires novel approaches in problem design.", "weaknesses": "I assume Observation 3. is just a rephrasing of Theorem 1. If so, why it is repeated?\n\nAlthough the problem is really interesting, and the work has a lot of novel ideas for tackling the problem, still I am not sure (1) if the paper is presented in a correct subject (e.g. if there is any theoretical study of NNs or some similar categories it belongs to that category where reviewers have better background on complexity study) and (2) I am still unclear about the impact of the work in application. Surely it is a theoretical study and we should not expect direct real-life applications but the study is in a corner case (1-d GNNs) where for more dimensions the results are already showing NP-hardness. It would be better if the authors could discuss the potential implications of this work for GNN training in general.\n\n**Theorem 1.** The reduction is nice, however the intuition behind this reduction is still unclear. Although polynomial reductions are essentially not easily understandable, and are mostly innovative, there are intuitive descriptions that can make the reduction understandable. I still am not sure if the proof is completely correct since most of the parts in the proof are still not understood by me..\n\nA list of questions are provided in \"questions\" section. I recommend writing the proof (or sections before it) again considering the questions, so an abstract image of this reduction becomes clear. \n\nHowever the gadgets and a high-level shape of the problem is illustrated, still the designed graph is not clear. It would elevate the paper's quality if the reader could imagine a sample graph for even a very small 1-in-3 SAT problem. The number of layers is also not determined. In case (from lemma 4) the 2-layer GNN is representative of any other GNN, the authors could mention that and for a sample SAT instance, show the weights of the optimal network, and the graph.", "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": "", "extra_scores": {}}, {"review_id": "4YySJ1tby1", "reviewer": "Reviewer_U9xM", "summary": "The paper investigate the computational complexity of training GNNs.  While it is straightfoward that training a high-dimensional GNN with a single node is NP-hard, the paper focuses on the less explored case of training multi-node, one-dimensional GNNs. The authors prove that training 1-dimensional GNNs is NP-hard when (i) the loss function is $L_p$ for some $p\\in[0,1)$; (ii) the aggregation functions is SUM, MEAN, or SPECTRAL; and (iii) the activation function is ReLU. The proof is an reduction from the NP-hard POSITIVE-1-IN-3-SAT problems.", "questions": "Refer to \"Weaknesses\"", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The results are solid and contribute to our understanding of the computational hardness of training GNNs.", "weaknesses": "1. The paper should provide a definition of the POSITIVE-1-IN-3-SAT problem when introducing the proof idea in the Introduction.\n2. It would be helpful to expand the discussion on the assumptions of the main theorem. For instance, is the problem still NP-hard for more commonly used loss functions, such as cross-entropy or $L_2$?\n3. The paper could benefit from a more explicit discussion on how these theoretical results might influence the design of GNN architectures or training algorithms in practical applications.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)