Convergent Graph Solvers
Authors: Junyoung Park
Jinhyun Choo
Jinkyoo Park
Venue: ICLR 2022 Poster (2022)
Keywords: Graph
Graph Neural Network
Fixed point
Implicit model
Implicit function theorem
Convergent

Abstract: We propose the convergent graph solver (CGS), a deep learning method that learns iterative mappings to predict the properties of a graph system at its stationary state (fixed point) with guaranteed convergence. The forward propagation of CGS proceeds in three steps: (1) constructing the input-dependent linear contracting iterative maps, (2) computing the fixed points of the iterative maps, and (3) decoding the fixed points to estimate the properties. The contractivity of the constructed linear maps guarantees the existence and uniqueness of the fixed points following the Banach fixed point theorem. To train CGS efficiently, we also derive a tractable analytical expression for its gradient by leveraging the implicit function theorem. We evaluate the performance of CGS by applying it to various network-analytic and graph benchmark problems. The results indicate that CGS has competitive capabilities for predicting the stationary properties of graph systems,  irrespective of whether the target systems are linear or non-linear. CGS also shows high performance for graph classification problems where the existence or the meaning of a fixed point is hard to be clearly defined, which highlights the potential of CGS as a general graph neural network architecture.

Published as a conference paper at ICLR 2022
CONVERGENT GRAPH SOLVERS
Junyoung Park, Jinhyun Choo & JJikyyo Park KAIST, Daejeon, South Korea juuyoungpark, jinhyun.choo,
ABSTRACT
We propose the convergent graph solver (CGS)', a deep learning method that learns iterative mappings to predict the properties of a graph system at its stationary state (fixed point) with guaranteed convergence. The forward propagation of CGS proceeds in three steps: (1) constructing the input-dependent linear contracting iterative maps, (2) computing the fixed points of the iterative maps, and (3) decoding the fixed points to estimate the properties. The contractivity of the constructed linear maps guarantees the existence and uniqueness of the fixed points following the Banach fixed point theorem. To train CGS efficiently, we also derive tractable analytical expression for its gradient by leveraging the implicit function thcorem. We evaluate the performance of CGS by applying it to various network-analyltn and graph benchmark problems. The results indicate that CGS has competitive capabilities for predicting the stationary properties of graph systems, irrespective whether the target systems are linear or non-linear. CGS also shows high performance for graph classification problems where the existence or the meaning of a fixed point is hard to be clearly defined, which highlights the potential of CGS as a general graph neural network architecture.
INTRODUCTION
Our world is replete with networked systems, where their overall properties emerge from complex interactions among the system entities. Such networked systems attain their unique properties from their stationary states; hence, finding these stationary properties is a common goal for many problems that arise in the science and engincering field. Examples of such problems include the minimization of the molecule's potential energy that finds the stationary positions of the atoms to compute the potential energy of the molecule (Moloi & Ali, 2005), the PageRank algorithm that finds the stationary importance of online web pages to compute recommendation scores (Brin Page, 1998), and the network analysis of fluid flow in porous media that finds the stationary pressures in pore networks to compute the macroscopic properties of the media (Gostick et al., 2016). these network-anallyicc problems, the network is often represented as a graph, and the stationary states are often computed through a wroblem-speciff iterative method derived analytically from the prior knowledge of the target system. By applying the iterative map repeatedly, these methods compute the stationary states (i.e., fixed points) and the associated properties of the target system. However, analytically deriving such iterative maps for highly complex systems typically requires tremendous efforts and time.
Instead of deriving/designing the problem-specific iterative methods, researchers employ deep learn- ing approaches learn the iterative methods (Dai al., 2018; Gu al., 2020; Hsich al., 2019; Huang et al., 2020). These approaches learn an iterative map directly without using domain-specific knowledge, but using only the input and output data. By applying the learned iterative map. these approaches (approximately) compute the fixed points and predict the properties of a target system. Graph Neural Networks (GNNs) have been widely used to construct iterative maps (Dai et al., 2018; Gu et al., 2020; Scarselli et al., 2008; Alet et al., 2019). However, when applying this approach, the existence of the fixed points is seldom guaranteed. As result, the number of iterative steps is often required to be specified, as a hyperparameter, to ensure the termination of the iterations. This may cause premature termination or inefficient backward propagation the number of iterations is inadequately small or too large.
'The code is available at hutps///ghhhhcccom//mmogggggggg

---

Published as a conference paper at ICLR 2022
In this study, we propose convergent graph solver (CGS), deep learning method that can predict the solution of a target graph analytical problem using only the input and output data, and without requiring the prior knowledge of existing solvers intermediate solutions. The forward propagation of CGS is designed to proceed in the following three steps:
Constructing the input-dependent inntr-contg iterative maps. CGS uses the input graph, which dictates the specification of the target network- analytic problem, to construct set of linear contracting maps. This procedure formulates/set up the internal problem be solved by considering the problem conditions and contexts (i.e., boundary conditions or initial conditions in PDE domains the physical network problems). Furthermore, the input-dependent linear map can produce any size of transition map flexibly depending on the input size graph; thus helping the trained model to generalize over unseen problems with different sizes (size transferabilityy)
Computing the fixed points via iterative methods. CGS constructs a set of linear contracting maps, each of which is guaranteed have unique fixed point that embeds the important features for conducting various end tasks. Thus, CGS computes the unique solutions of the constructed linear maps via iterative methods (or direct inversion) with convergence guarantee.
Decoding the fixed points to estimate the properties. By using separate decoder architecture, we compute the fixed points in the latent space while expecting them to be an effective representa- tion that can improve the predictive performance of the model. This enables CGS to be used not only for finding the real fixed points (or its transportation) if they exist, but also for computing the "virtual fixed point" as a representation learning method in general prediction tasks.
The parameters of CGS are optimized with the gradient computed based on the implicit function theo- rem, which requires (1) memory usage when computing the gradient along with the iterative steps. CGS is different from the other studies that solve the constrained optimization (with convergence guarantee) (Gu et al., 2020; Scarselli et al., 2008; Tiezzi et al., 2020) in that it does not impose any restriction when optimizing the parameters. Instead, CGS is inherently structured to have the unique fixed points owing to the uses of the linear map. Note that the structural restriction is only in the form of an iterative map: we can flexibly generate the coefficients of the linear map using any network (i.e., GNN) and utilize multiple linear maps to boost the representability.
We evaluate the performance of CGS using two types of paradigmatic network-an network-analytic problems: physical diffusion in networks and the Markov decision process, where the true labels indeed exist and can be computed analytically using linear and non-linear iterative methods, respectively. We also employ CGS to solve various graph classification benehmark tasks to show that CGS can serve as general (implicit) layer like other GNN networks when conducting typical graph classification tasks. In these experiments, we seek to compute a virtual fixed point that can serve as the best hidden representation of the input when predicting the output. The results show that CGS can be (I) an effective solver for graph network problems or (2) an effective general computational layer for processing graph-structun data.
2 RELATED WORK
Convergent neural models. Previous studies that have attempted to achieve the convergence property of neural network embedding (e.g., hidden vectors of MLP and hidden states of recurrent neural networks) can be grouped into two categories: soft and hard approaches. Soft approaches typically attain the desired convergence properties by augmenting the loss functions (Erichson et al., 2019; Miyato et al., 2018). Although the soft approaches are network- archittccch agnostic, these methods cannot guarantee the convergence of the learned mappings. On the other hand, hard approaches seek to guarantee the convergence of the iterative maps by restricting their parameters in certain ranges (Gu et al., 2020; Tiezzi et al., 2020; Miller & Hardt, 2018; Kolter Manek, 2019). This is achieved by projecting the parameters of the models into stable regions. However, such projection may lead to non-optimal performances since it is performed after the gradient update, i.c. the projection is disentangled from training objective.
Implicit deep models. The forward propagation of CGS, which solves fixed point iterations, is closely related to deep implicit models. Instead of defining the computational procedures (e.g., the depth of layer in neural network) explicitly, these models use implicit layers, which accept input- dependent equations and compute the solutions of the input equations, for the forward propagation.
2

---

Published as a conference paper at ICLR 2022
For instance, neural ordinary differential equations (NODE) (Chen et al., 2018; Massaroli al., 2020) solve ODE until the solver tolerance is satisfied or the integration domain is covered, the optimization layers (Gould et al., 2016; Amos & Kolter, 2017) solve the optimization problem until the duality gap converges, and the fixed point models (Bai et al., 2019; Winston & Kolter, 2020) solve the network--gnnerated fixed point iterations until some numerical solver satisfy the convergence condition. Implicit models use these (intermediate) solutions to conduct various end tasks (e.g., regressions, or classifications). In this way, implicit models can impose desired behavioral characteristics into layers as inductive bias and hence, often show superior parameter/memory efficiency and predictability.
Fixed points of graph convolution. Methods that find the fixed points of graph convolutions have been suggested in various contexts of graph-related tasks. Several works have utilized GNN along with RNN-like connections to (approximately) find the fixed points of graph convolutions (Liao et al., 2018; Dai et al., 2018; Li et al., 2015; Scarselli al., 2008). Some have suggested to constrain the parameter space of GNN that the trained GNN becomes a non-expansive map, thus producing the fixed point (Gu et al., 2020; Tiezzi et al., 2020). Others have proposed to apply an additional GNN layer the embedded graph and penalize the difference between the output of the additional GNN layer and the embedded graph to guide the GNN to find the fixed points (Scarselli et al., 2008; Yang al., 2021). It has been shown that regularizing GNN find its fixed points improves the predictive performance (Tiezzi et al., 2020; Yang et al., 2021).
Comparison between CGS and existing approaches. Combining the ideas of (1) computing/using the fixed points of the graph convolution (as a representation learning) and (2) utilizing the implicit differentiation of the model (as training method) has been proposed by numerous studies (Scarselli et al.. 2008; Liao et al., 2018; Johnson et al., 2020; Dai et al., 2018; Bai et al., 2019; Gallicchio & Micheli, 2020: Bai et al., 2019; Tiezzi et al.. 2020; Gu et al., 2020). Majority of those studies assume that the convolution operators (iterative map) induce a convergent sequence of the (hidden) representation; however, this assumption typically does not hold unless certain conditions hold for the convolution operator (iterative map). When neither the convergence nor uniqueness holds, it can possibly introduce biases in the gradient computed by implicit differentiation (Liao et al., 2018; Blondel et al., 2021). Hence, to impose convergence, some methods restrict the learned convolutions to be strictly contractive (i.e., the hidden solutions are convergent) by projecting the learned parameters into certain region and solving the constraint training problems, respectively (Gu et al., 2020; Tiezzi et al., 2020). Unlike these methods restricting the parameters of the graph convolutions directly, CGS guarantees the convergence and the uniqueness of the fixed point by imposing the structural inductive bias on the iterative map, i.e., using the contractive linear map that has unique fixed point, thus alleviating the need solve the constrained parameter optimization (Tiezzi et al., 2020).
PROBLEM DESCRIPTION
The objective of many network--nalytic problems can be described as:
Find a solution vector Y from a graph G that represents the target network system.
In this section, we briefly explain a general iterative scheme to compute Y from G. The problem specification G = (V, E) is a directed graph that composed of set of nodes V and a set of edges E. We define the h node as o; and the edge from to Biy as Cij- The general scheme of the iterative methods is given as follows:
H 0 [(9),
in) [n] = T( [ ();
71 = 1,2, ....
(2)
Y [n] (H!!))))
0, 1,...
where f(-) is the problem-specift initialization scheme that transforms into the initial hidden embedding 1110 T is the problem-specific iterative map that updates the hidden embedding |'l from the previous embedding Hin-1], and g(-) is the problem-specific decoding function that predicts the intermediate solution Yln
3

---

Published as a conference paper at ICLR 2022
-.) of (p Gangenn))
Fieed Pootirr SOS.SSA 
9 EV
(V,E)
Constructing iteraiive maps
Computing points
Decoding points
Figure Overview of forward propagation of CGS. Given an input graph 9, the parameter- generating network fa constructs contracting linear transition maps To. The fixed points H of To are then computed via matrix inversion. The fixed points are aggregated into H', and then the decoder de decodes H to produce Y
T is designed such that the fixed point iteration (equation 2) converges to the unique fixed point H*:
lim
H - H" H s.t. H = T(H",
(4)
The solution Y is then obtained by decoding H" i.e., g( Y
In many real-world network-analyti problems, we can obtain 9 and its corresponding solution Y*. but not T, Hb* and (()), Therefore, aim to learn mapping T from Y without using T, Hin) and Y
3.1 EXAMPLE: GRAPH VALUE ITERATION
Let us consider a finite Markov decision process (MDP), whose goal is to find the state values through the iterative applications of the Bellman optimality backup operator (Bellman, 1954). We assume that the state transition deterministic.
We define G (V, E). where V and E are the set of states and transitions of MDP respectively. v; the state transition from state i j.
corresponds to the 7th state of MDP, and ejj corresponds eg exists only if the state transition from state i to j is allowed in the MDP. The features of ei are the corresponding state transition rewards. The objective is to find the state values V*, In this setting, the Bellman optimal backup operator T is defined as follows:
v!ni T(v(n-1);
max (rij + aV/n-111
(5)
JEN(()
where y-lx] is the state value of 2 estimated at n-th iteration, .iii is the set of states that can be reached from the 4h state via one step transition, Fiy is the immediate reward related to Cij, and a is the discount rate of the MDP.
In this graph value iteration (GVT) problem, the initial values y are set as zeros (i.e., f(-) = 0). then T is applied until Vin) converges, and Vin) is decoded with the identity mapping (i.e., g(-) is identity and // & vlal), We will show how CGS constructs the transition map T from the input graph and predicts the converged state values V without using equation 5 in the following sections.
CONVERGENT GRAPH SOLVERS
We propose CGS that predicts the solution Y from the given input graph in three steps: (1) constructing linear iterative maps Ta from 9, (2) computing the unique fixed points H T, via iterative methods, and (3) decoding H' to produce Y* shown in Figure
4

---

Published as a conference paper at ICLR 2022
4.1 CONSTRUCTING LINEAR ITERATIVE MAPS
CGS first constructs an input-dependent contracting linear map To(-99) such that the repeated application of (=;9)) always produces the unique fixed point H (i.e. lim H H ) that embeds the essential characteristies of the input graph & for conducting end tasks. In other words, CGS learns to construct iterative maps that are tailored to each input graph G. from which the unique fixed points of the target system are guaranteed to be computed and used for conducting end tasks.
To impose the contraction property on the linear map, CGS utilizes the following iterative map:
TH A AA( + Bo(g)
where is the contraction factor, (g) E Rexp is the input-dependent transition parameter, Bo( E IP is the input-dependent bias parameter, and p is the number of nodes in graph.
To construct an input-dependent iterative map that preserves the structural constraints, which is required to guarantee the existence and uniqueness of fixed point, employ GNN-based parameter- generating network fo(-). The parameter generation procedure for To starts by encoding g E):
V,E'= = (V
(7)
where V' and are the set of updated node embeddings of R9 and edge embeddings e'g E R respectively, CGS then constructs Ag( by computing the (i, element of Ag(g) as follows:
a(ey)) d(
if eij exists,
(A)())
O
otherwise.
where (ar) is a differentiable bounded function that projects into the range [0, 1] (e.g., Sigmoid function), and d(i) is the outward degree of e; (i.c.., the number of outward edges of v.). Be is simply constructed by vectorizing the updated node embeddings as [Bo(g)),, = v/.
Theorem The existence and uniqueness of H" induced by To [H()) The proposed scheme for
constructing A9) along with the bounded contraction factor O < 7 < 1, is sufficient for (H( 9) to be "-contructing and, as a result, To has unique fixed point H Refer to Appendix A.1 for the proof.
Multi-head extension. Ta can be considered as a graph convolution layer defined in equation Thus, CGS can be easily extended to multiple convolutions in order to model more complex iterative map. To achieve such multi-head extension with M graph convolutions, one can design fo to produce set of transition parameters [A] ...,... Am,... ..., Aai and set of bias parameters [B..... Bm: ..., B for Ti H 9) Am H + Bm for m = 1, 1,..,M.. M.
4.2 COMPUTING FIXED POINTS
The fixed point H of the constructed iterative map Tm (H A AA, H B,n satisfies H = 7 Am H + Bm for m 1,..,, M. Due to the linearity, we can compute the fixed point of Tm via matrix inversion:
H =1- (1- Bm
where E RPXP is the identity matrix. The existence of (I (I-7Am)~1) is assured from the fact that Tm is contracting (see Appendix A.2). The matrix inversions can be found by applying various automatic differentiation tools while maintaining its differentiability. However, the computational complexity of the matrix inversion scales Op²)). which can limit this approach from being scaled to large scale problems favorably.
To scale CGS larger graph inputs, we compute the fixed point of Tm by repeatedly applying the iterative map Tm starting from an arbitrary initial hidden state H 0) E I& until the hidden embedding converges, i.e., lim,-+20 Hrll H
One can choose a way to compute the fixed point between inversion and iterative methods depending on the size of the transition matrix Am and its sparsity because these factors result in different computational speed and accuracy. In general, for small-sized problems, inversion methods can be favorable; while for large-sized problems, iterative methods are more efficient. (See Appendix D.6)
5

---

Published as a conference paper at ICLR 2022
4.3 DECODING FIXED POINTS
The final step of CGS is to aggregate the fixed points of multiple iterative maps and decode the aggregated fixed points produce Y*. The entire decoding step given follows:
H H ... HM
(10)
Y = (=
(11)
where H' is the aggregated fixed points, M is the number of heads, and g is the decoder which analogous the decoding function of the network network-analytie analytic problems (equation 3).
5 TRAINING CGS
To train CGS with gradient descent, we need to calculate the partial derivatives of the scalar-valued loss with respect to the parameters of Ta. To do so, we express the partial derivatives using chain rule taking H as the intermediate variable
ac a(.)
OC 8H
(12)
0H 8())
Oc readily computable via an where (+) denotes the parameters of Ao(g) (g) Here, øH
automatic differentiation package. However, computing 0H is less straightforward since H and 8
(.) are implicitly related via equation 6. One possible option compute the partial derivatives is to backpropagate through the iteration steps.
Although this approach be easily employed using most automatic differentiation tools, it entails extensive memory usage. Instead, exploiting the stationarity of H" we can derive an analytical expression for the partial derivative using the implicit function theorem follows:
OH a(.)
H ( A. OH-
Og Og(H', (HH,A,, A.
(13)
0(-)
where
H (YAH B). Here, we omit the unput-dependency of A and B for notational brevity. We compute the inverse terms via an iterative method. This option allows one to train CGS with constant memory consumption over the iterative steps. The derivation of the partial derivatives and the software implementation of equation 13 are provided in Appendix A.3 and B respectively.
EXPERIMENTS
We first evaluate the performance of CGS for two types of network-analyde problems: (1) the stationary state of physical diffusion in networks where the true solutions can be computed from linear iterative maps, and (2) the state values via GVI where the true solutions can be calculated from non-linear iterative maps. We then assess the capabilities of CGS as a general GNN layer by applying CGS to solve several graph property prediction benchmarks problems.
6.1 PHYSICAL DIFFUSION IN NETWORKS
Diffusion of fluid, heat, and other physical quantities are omnipresent in the science and engineering applications. Mathematically, physical diffusion in networks (c.g. pipe/pore networks) is often described by graph. The stationary state of the graph can be expressed as
Σ
kislpt p3) = 0, Ves E (V))(V)
(14)
JEN(O
P: = P. Ve, E O(V),
(15)
where p: and Pj are the potentials at v, and vy respectively, kay the conductance of the edge the connects the two nodes, and p the prescribed potentials at the boundary nodes that belong to the set O(V). Equation 14 specializes to particular diffusion problem according to how is prescribed (e.g. pressure fluid flow, and temperature for heat transfer).

---

Published as a conference paper at ICLR 2022
COGAMI
CANGO
CANGZE
Gole CO04E
0600991 KOWN
2.000
01:077
LX00
0.,023
0000
0.000
E200
0.050
200
300
600
500
600
100
602
14:022
Numbere of Pores
Figure 2: Diffusion experiment results. The and y- axis are the number of pores and the average MSE of the test graphs. The error bars indicates the standard error of predictions (measured from 500 instances per each size).
Number of GNN layers
Figure 3: Number of GNN layers vs. MSE (n. = =800).
As an example of physical diffusion, consider fluid flow in porous media particularly, finding the fluid pressures of pore network that is in equilibrium state (the solutions of equations 14 and 15). We model the pore network as 3D graph whose nodes and edges correspond to pore chambers and throats respectively as shown in figure We assume linear diffusion such that p (i.e., Y*) can be computed using a linear iterative map (Gostick et al., 2016).
Aa. 96
0.0
5.6c-06
09
08
0.0005
0.0015
06
0.0003
0.6
05
0.0012
04
4A
0.6
05
33645
We employ CGS to predict the equilibrium pressures Y inside pore networks G. The node fcatures are the Cartesian coordinates, volume, diameter, and bound- ary indicator its corresponding pore. The boundary pressure also as a node feature if the node corre- sponds to a boundary pore. The edge features are the cylinder volume, diameter, and length of its corre- sponding throat. We sample training graphs such that the graphs fit into 0.1 m cubes. The training graphs, which have 50-200 nodes. are then randomly generated (See Appendix C.I). We train CGS such that it minimizes the mean-squared error (MSE) between the predicted ones and Y*.
03
02
04
.12
0
00015
0,03
0.6
00006
0.011
Figure 4: Pore network graph
To investigate the effectiveness of the multi-head extension, we train CGS (4), CGS and CGS (16), where CGS (m) denotes CGS with m heads. For the baseline models, we use implicit GNNs, IGNN, (Gu et al., 2020), SSE (Dai et al., 2018), and n-layer GNN models GNN(n). IGNN and SSE find the fixed points in the forward propagation step. We utilize the same GNN architecture as the encoders for all baselines except for SSE. Please refer to Appendix C.1 for the details about the data generation, network architectures, and training schemes.
All CGS models show better generalization capabilities than the baselines in predicting Y as shown in Figure 2, even though all models show similar prediction errors during training (See Appendix C.1.2). CGSs with higher m show superior prediction results for the test cases. This difference evinces that the use of multi-head extension (i.e., multiple linear iterative maps) is advantageous due the increased expressivity. Also, when comparing CGS (8) and GNN (1), which utilize the same encoder architecture and thus has the same number of GNN layers shown in Figure 3, CGS (8) shows better prediction performance. This is because the 1-hop aggregation cannot provide enough information to compute the equilibrium pressure. This result indicates that CGS successfully accommodates the long-range patterns in graphs without adopting additional graph convolution layers.
6.2 GRAPH VALUE ITERATION
We investigate the performance of CGS on graph value iteration (GVI) problems, where the iterative map (equation 5) is non-linear explained in section 1. The goal of the experiments is show that CGS can estimate the state values that are computed from the nonlinear iterative map accurately, when using the set of learned linear iterative maps, shown in figure 5.
7

---

Published as a conference paper at ICLR 2022
Nor D HAVE
Bar
Iax. 10 Merc
Iter. 15 Zo1l
Box 20
Figure 5: Solutions of GVI with CGS. The balls represent the states of MDP and the ball colors show the prediction results and their corresponding targets. More details are described in the main text.
Table 1: Graph Value Iteration results. We report the average MAPE and policy prediction accuracies (in %) of different n2 and n& combinations with 500 repeats per combination. All metrics are measured per graph.
20
50
75
100
perans
10
10
10
15
10
15
S8E
4. 96
7.40 4.54
0072
5.98
0.12%)
3,30
10:00 0.08
6:00
& 2.74
(0.1 0.12
91.52 0.11
(0.99 a: 0.6 %
6,52 = 2.89
(0,7
91.51 # 0,06
0.06
[0.8 0.06 96)
86662 2:21
00.87 = 0.06
57.50 0.05
43.521
10HI
0.12%)
(0.63
28.18 1.79
0.13%)
28.33 1.40
(0.62
2044
(0.00
28:11
0.0%))
(0.60
29.00
28.00
(0.60
268,006
(03(16)
2:33
093(32)
0.00
2.67
00.83
1,90
(0.77:0:0000
2,16
(081
1.24 1:244-0..4
0.00
1.72
00:00:0000
00.76
0005
263.669
085(64)
10.85 0.00 (3)
3.00
(0.86 0.09 98)
1:1.88
(6.83 = 0.07
1.78
(0.85 2::0::00:0000 9) (083 = %)
2,36
(0.53 à 0.03 ()
1.7,6
[0,82 0:05 (6)
1.59
(0.82 = 0.05
0.67
700,059
We train three CGS models, CGS (16), CGS (32), and CGS (64), and two baseline models, SSE and IGNN, randomly generated MDP graphs. Each MDP graph has n, nodes and each node has na edges (i.e. the MDP has n, distinct states and na possible actions from each state). We sample and n. from the discrete uniform distributions with lower and upper bounds of (20, 50) and (5, 10), respectively. We evaluate the predictive performance of the trained CGS on randomly generated GVI problems verify the generalization capability of CGS for different ng and nu. We refer to Appendix C.2 for the details of the model architectures and training schemes.
Table summarizes the evaluation results of CGS and the baseline models. We report the mean- Absolute-perccenage error (MAPE) between the predicted state values and their true values, and the accuracy between the derived and optimal policies (in %), following Deac et al. (2020).
All the CGS models show reliable value and policy predictions for the in- in-training cases (n, = 20) as well as for the out-of-training cases. In general, CGS with many heads shows better prediction results than the model with smaller number of heads. The two baseline models shows significant performance drops as n, and, especially, na increase. (i.c. the number of incoming edges per node becomes larger). The results show that CGS solve the unseen problems well (i.c., generalization). From the results, we can conclude constructing the transition map adaptively by utilizing the input graph information is crucial factor for achieving better generalization and higher prediction accuracy of CGS, as compared to other baseline models (SSE and IGNN) that uses fixed transition maps
A Ablation studies. We conduct various ablation studies and confirm the following:
Appendix D.I: the flexibility of fe(-) design is beneficial to attain higher predictive performances,
Appendix D.2: the input-dependency of both (g and (g) is essential for generalization,
Appendix D.3: the contraction factor 7 balances the predictability and computational time,
Appendix D.4: the linear T-(.) has sufficient expressivity, compared to the nonlinear extension, while being robust to the hyperparameters.
Appendix D.5: a relatively small of training samples (2 512) is enough to attain higher predictive performances, compared to IGNN.
Appendix D.6: the iterative fixed point computation scales better than the direct method in terms of memory usage.
From the results, we confirmed the proposed design of (-) is effective and robust to the hyperpa- rameters in solving GVI, and the proposed training scheme iterative fixed point computation and
8

---

Published as a conference paper at ICLR 2022
Table Graph classification results (aceuracy in %). All benchmark results are reproduced from the original papers except IGNN.
IMDB-B
IMDB-M
MUTAG
PROT:
PTC
NCII
graphs
1500
classes
2
2
Avg # nodes
19.8
13.0
17.9
39.1
25.5
29.8
PATHOHY-SAX (Niepert et al., 2016)
45.2-4
92.6
2.8 75.5
4.8 58.6
1.9 74,4
DOONN (Zhang et al., 2018)
70.0
47.8
85.8
AWL (Ivanov & Burnee,, 2018)
74.5 5.9
51.5 3.6
87.9 9.8
(Xu et al., 2018)
75.1 5.1
52.3 = 2.8
89.4 + 5.6
76.2 + 2.8
64.6 7.0
82.7 = 1.7
GraphNorm (Cai et al., 2020)
76.0 76.0 3.7
91.6 +: 6.5
77.4 +: 4.9
64.9 + 7.5
81.4 +: 2.4
LP-GEN (Tiezzi et al.. 2020)
71.2=
46.6 3.7
90.5 7.0
17.1 4.3
61.4 5.9
08,
IGMN (ours)
2020)
78.1 11.8
76.5 4.3
60.8 10.3
72.8 1.9
(CS
72.3 # 3.4
49.6 + 3.6
85.9 6.8
74.1 + 4.1
60.2 =: 7.8
76.9 + 1.4
(G5
73.0 1.9
51.0
$8.4
76.3 6.3
64.7=6.4 6.4
76.3
2.0
CGS(8)
73.0
51.1
86.5
76.3 4.9
5.2
77.6
2.2
CaS CCS (16)
72.8 = 2.5
50.4
88.7 6.1
76.3 4.9
62.9
77.6
2.0
CBS (32)
73.
3.3
50.3 - 1.7
89.4 5.6
76.0 3.2
63.1 4.2
77.2
2.0
computing the gradient via the implicit function theorem is practically suitable in terms of memory usage. Due to the page limit, we refer to D for the details and results of the ablation studies.
6.3 GRAPH CLASSIFICATION
We show that CGS can also perform general graph classification tasks accurately, where the existence the meaning of fixed point hard be clearly defined, although originally designed to predict quantities related to the fixed points.
We assess the graph classification performance of CGS six graph classification benchmarks: two social-network datasets (IMDB-Binary. IMDB-Multe and four bioinformaties datasets (MUTAG, PROTEINS, PTC, NCII). Since the social generated based on the node degrees following Xu et al. (2018). Also, the edge features are initialized with one vectors for all datasets. To conduct the graph classification tasks, we perform the sum readout over the outputs of CGS (i.e., summing all fixed points), and then utilize additional MLP to predict the graph labels from the readout value. We perform 10-fold cross validation and report the average and standard deviation of its accuracy for each validation fold, following the evaluation scheme of Niepert et al. (2016). We refer to Appendix C.3.1 for the details the network architecture, training. and hyperparamter searchings.
datasets do not have node features, they are
The results in Table show that the classification performance CGS is comparable to those of other methods using fixed point iteration (LP-GNN and IGNN). Note that reproduced the results of IGNN as the original paper used a different performance metric (IGNN (ours)). We provide the additional benchmark results in Appendix C.3.2 compare with IGNN following their test metric. In general, CGS shows better performance than LP-GNN and IGNN, which also find the fixed points of graph convolutions on the -etwork datasets where the node features are not given. From the results, CGS can be interpreted as that CGS finds "virtual fixed points" that contain the most relevant information classify the graph labels. These results indicate that CGS has potential as an general graph convolution layer.
7 CONCLUSION
We propose the convergent graph solver (CGS) as new learning- iterative method to compute the stationary properties of network-analyten problems. CGS generates contracting input-dependent linear iterative maps, finds the fixed points of the maps, and finally decodes the fixed points to predict the solution of the network-analytic problems. Through various network-analytti problems, show that CGS has competitive capabilities in predicting the outputs (properties) of complex target networked systems in comparison with the other GNNs. We also show that CGS can solve general graph benchmark problems effectively, showing the potential that CGS can be used as a general graph implicit layer for processing graph structured data.

---

Published as a conference paper at ICLR 2022
8 ETHIC STATEMENTS AND REPRODUCIBILITY
Ethics statement We propose deep learning method that learns iterative mappings of the target problems. As we discussed in section I, various types of engineering, science, and societal problems are formulated in the form of fixed point-fin fint-finding problems. On the bright side, we expect the proposed method to expedite scientificeengnnering discoveries by serving as fast simulation. On the other hand, our method rooted in the idea of finding fixed points, it can be used to analyze networks and finding an adversarial or weak point a network that can change the results many network-analyyti algorithms that ranging from everyday usages, such recommendation engines of commercial services, and maybe life-critical usages.
Reproducibility As machine learning researchers, we consider the reproducibility of numerical results as one of the top priorities. Thus, we put significant amount of effort into pursuing the reproducibility of our experimental results. such, we set and tracked the random seed used for our experiments and confirmed the experiments were reproducible.
REFERENCES
Ferran Alet, Adarsh Keshav Jeewajee, Maria Bauza Villalonga, Alberto Rodriguez, Tomas Lozano- Perez, and Leslie Kaelbling. Graph element networks: adaptive, structured computation and memory. In International Conference on Machine Learning, pp. 212-222. PMLR, 2019.
Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks.
In International Conference on Machine Learning, pp. 145-145. PMLR, 2017.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems, pp. 690-701, 2019.
Stefan Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. 1922.
Peter Battaglia, Jessica B Hamrick, Victor Bapst. Alvaro Sanzhez-Gonzalez, Vinicius Zambaldi. Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 0888000261 2018.
Richard Bellman. The theory of dynamic programming. Technical report, Rand corp santa monica ca, 1954.
Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares-Lóópez, Fabian Pedregosa, and Jean-Phne Phillpil Vert. Efficient and modular implicit differentiation. arXiv preprint arXiv:2105.15183, 2021.
Sergey Brin and Lawrence Page.
The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1-7):107-117, 1998.
Tianle Cai, Shengjie Luo, Keyulu Xu, Di Hc. Tie-yan Liu, and Liwei Wang. Graphnorm: A principled approach to accelerating graph neural network training. arXiv preprint arXiv:2009.03294, 2020.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential equations. In Advances in neural information processing systems, pp. 6571-6588 2018.
Hanjun Dai, Zornitsa Kozareva, Bo Dai, Alex Smola, and Le Song. Learning steady-states of iterative algorithms over graphs. International conference on machine learning, pp. 1106-1114, 2018.
Andreea Deac, Pierre-Lue Bacon, and Jian Tang. Graph neural induction of value iteration. arXiv preprint arXiv:2009. 2020.
N Benjamin Erichson, Michael Muchlebach, and Michael W Mahoney. Physics-informed autoen- coders for syapueov-stable fluid flow prediction. arXiv preprint arXiv: /905. 10866, 2019.
10

---

Published as a conference paper at ICLR 2022
Claudio Gallicchio and Alessio Micheli. Fast and deep graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp.
2020.
Jeff Gostick, Mahmoudreza Aghighi, James Hinebaugh, Tom Tranter, Michael A Hoeh, Harold Day, Brennan Spellacy, Mostafa H Sharqawy, Aimy Bazylak, Alan Burns, et al. Openpnm: a pore network modeling package. Computing in Science & Engineering. 18(4);60-7,, 2016.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application bi-level optimization. arXiv preprint urXiv:160.00544,, 2016.
Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui Implicit graph neural networks. arXiv preprint arXiv:2009.062111 2020.
Jun-Tine Ting Hsich, Shengjia Zhao, Stephan Eismann, Lucia Mirabella, and Stefano Ermon. Learning neural pde solvers with convergence guarantees. arXiv preprint arXiv: /906. 006600200000 200, 2019.
Jianguo Huang, Haoqin Wang. and Haizhao Yang. Int-deep: A deep learning initialized iterative method for nonlinear problems. Journal of Computational Physics, 419:109675, 2020.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. arXiv preprini 11XX:::805..1122 2018.
Daniel Johnson, Hugo Larochelle, and Daniel Tarlow. Learning graph structure with a finite- state automaton layer. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 3082-3093. Curran Associates, Inc., 2020.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 2014.
J Zico Kolter and Gaurav Manek. Learning stable deep dynamics models. In Advances in Neural Information Processing Systems, pp. 11128-11 1136, 2019.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1571.0599. 2015.
Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urtasun, and Richard Zemel. Reviving and improving recurrent pac-prropagttion In International Conference on Machine Learning, pp. 3082-3091. PMLR, 2018.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608. 1308.0388, 2016.
Stefano Massaroli, Michael Poli, Jinkyoo Park, Atsushi Yamashita, and Hajime Asama. Dissecting neural odes. In NeurlPS, 2020.
John Miller and Moritz Hardt. Stable recurrent models. arXiv preprint arXiv:1805.10366) 2018.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv: 1802.05577 2018.
NP Moloi and MM Ali. An iterative global optimization algorithm for potential energy minimization. Computational Optimization and Applications, 30(2):119-132 2005.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pp. 2014 2-22002,3 2016.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
11

---

Published as a conference paper at ICLR 2022
Prajit Ramachandran, Barret Zoph, and Quoc V Le. Searching for activation functions. arXiv preprint arXiv:1710.05941, 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-199 2014.
Mattco Ticzzi, Giuseppe Marra, Stefano Melacci, Marco Maggini, and Marco Gori. A lagrangian approach information propagation in graph neural networks. arXiv preprint arXiv:200..06684 2020.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland. Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, -722, 2020. doi: 10.1038/44159220199
Minjie Wang. Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv:1909.01333 2019.
Ezra Winston and J Zico Kolter. Monotone operator equilibrium networks. arXiv preprint arXiv:2006.08591 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.008226 2018
Han Yang, Kaili Ma, and James Cheng. Rethinking graph regularization for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 4573-4581, 2021.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
12

---

Published as a conference paper at ICLR 2022
Convergent Graph Solvers Supplementary Material
Table of Contents
Proofs and derivations
A.1 Existence of converged embedding
14
A.2 Existence of inverse matrix
14
A.3 The complete derivation of the partial derivatives
14
B Software Implementation
16
Details on experiments
Physical diffusion
pe..............................
C.2 Graph value iteration
19
C.3 Graph classification experiments
19
D Ablation studies
21
D.1 Effect of fo(-) architecture
21
D.2 Design of the deppuddeeendent transition ................................
21
Effect of contraction parameter 7
................................
21
D.4 Comparisons the non-linear iterative maps
................................
22
D.5 Sample efficiency of CGS
................................
22
D.6 Runtime comparisons of direct inversion and iterative methods
23
13

---

Published as a conference paper at ICLR 2022
A PROOFS AND DERIVATIONS
In this section, we prove the existence of the converged hidden embedding H' and (7 - 7A0) and give the complement derivation of the partial derivatives that is used to train CGS.
A.1 EXISTENCE CONVERGED EMBEDDING
The proposed transition map is defined as follows:
To ( ml :g) = ( + Be(g)
(A.1)
where 0.0 7 1.0, Ag(g) e REXP with [9)x S 1.0, and Bg(g) 12x0
We first show that the proposed transition map is contracting, Then, the existence of unique fixed point can be directly obtained by applying the Banach fixed point theorem (Banach, 1922).
Lemma 1. (H |m) 9) -ycontractionn mapping.
Proof.
The proof is trivial. Consider the following equations:
(T To H |nl 9)ll = A9) (|) + Bo A00())) Bo(g))
=>|| (H) [H [++1 H|mi)|
S As()) x [|
[++1]] H|))
> (+ H H||)]
The inequality holds by the property of the spectral norm. Therefore, (HH y-contracting.
A.2 EXISTENCE OF INVERSE MATRIX
CGS can find the fixed point H" by pre-multiplying the inverse matrix of (T-7Ag) to Bg, which is given follows:
H- (I- BB
(A.2)
The following lemma shows the existence of the inverse matrix. Lemma 2. With matrix Ag, which constructed using equation and 0.0 < 1.0, (I 7Ap) is invertible.
Proof. According to the invertible matrix theorem, (I - Ao) being invertible is equivalent to - (T-AAg)== 0 only having the trivial solution æ 0. By rewriting the equation A and defining the 7-contraction map F(x) = Agær we can get the following result:
lim F (z) 0, for any
(A.3)
From the Banach fixed point theorem, we can conclude that the unique solution x 0. Therefore, (I Ay) is invertible.
A.3 THE COMPLETE DERIVATION OF THE PARTIAL DERIVATIVES
The following equality shows the relationship of the gradient of the scalar-valued loss L, the fixed point H", and the parameters of the fixed point equation Ag Bg(g):
ac
OL 0H
(A.4)
ac-)
9H a(-)
where (.) denotes Ag( or (g) Here, 9H are readily computable via automatic differentiation packages. However, computing 8H" is less straightforward since H" and (-) are implicitly related via equation 6.
14

---

Published as a conference paper at ICLR 2022
We reformulate the transition map (equation 6) in root-finding form Q, = = - (yAH B). Here, we omit the input-dependency of and for the brevity of the notations. For the fixed point H the following equality holds: (A, A.B
(A.5)
0A
We can expand the derivative by using chain rule as follows:
dgl H (A, B), A) Og(H", B)
0g(H A, B) OH B)
=0
(A.6)
0A
0A
0H
A
By rearranging the terms, we can get closed-form expression of 2H DA
as follows:
-1
ÖH (O(HHA,,
(A.7)
04
OH
0A
Here, can compute Ho(H',A.E .. easily by using either automatic differentiation tool manual 0H
8A
gradient calculation. However, in practice, directly computing [g [g(H"".AB ) can be problematic
since involves the inversion of Jacobian matrix. Instead, we can (1) construct linear system whose solution is Ogi .A.B) )-1 and solve the system via some matrix decomposition or (2) solve another 0H
( H .A.B) >-1 We provide the pseudocode that shows how öH-
fixed point iteration which converges to
to compute the inverse Jacobian with the second option in section B.
The partial derivative with respect to can be computed through the similar procedure and it is given follows:
HH
O0((H', A, B)
Og(H',A. A)
(A.8)
0B
0H*
0B
15

---

Published as a conference paper at ICLR 2022
B SOFTWARE IMPLEMENTATION
In this section, we provide Pytorch style pseudocode of CGS which computes the derivatives via the backward fixed point iteration.
import torch
import torch. nn as mn
class Module)
=**
Convergent Graph Propagation
def init_ (self, gamma: float, activation: str,
11
12
tol: float = 1e-6,
max_iter: int 50)
15
16
(CGP self)._inie init(()) ()
17
self.gamna gamna gamma self.tol tol
self.maxjited max_ iter
30
self.act getattr (nn, activation) ()
21
self. frd itr = None & forward iteration steps
24
def fsrward A, b):
25
**"
26
:param A: A matrix [e.heads x F, edges x 4. edges]
:param b: matrix [# heads f. nodes x 1] :return: Fixed points [#. heads 4. nodes] .*"
29
30
31
2,
= scl..cllveffpeee (A, b,
self ganma, self.act, sel f. fff.xxiter, self.tol)
33
34
35
37
re-engage autograd and add the gradient hock z self,act (semm.gamma torch, bmm (A, z) + b)
3M
39
40
if 2. requires_gradd:
y0 self.gamna torch.bam (A, y0 detdch requires__rrdd_ z_next
42
43
(y0) .um
44
dphi - y0.grad
self. gamma (dphi A) transpoose (2, 1)
47
48
deš modify ggaad))
49
bir_itr self scle.sccle_fp_eee (J,
grad,
51
1.0,
52
nn. nn. Im.Identity (),
53
self.max_itee
self.tol)
56
return y
57
58
2. r.rgister_hhooe hook (modify soddifyygraddl
7. squezze (dim=-1) $ drop dummy di mimension
16

---

Published as a conference paper at ICLR 2022
62
@staticmethed
63
storch.ne_gradde D, gamma: float, nn.ule, max_itr: int, tol: float):
64
def sclve_fp_oq
65
67
68
69
Find the fixed point act (gamma b) =*"
71
72
73
x torch. zeros_like (b, prrice-b.device.
itr = 0
while itr max itr:
76
next act (gamma terch. bmm (A, x) b)
77
g = x x_next
78
if torch.norm (g) < tol: break
x_next itr +- return X, itr
81
82
Listing 1: CGS pseudocode
17

---

Published as a conference paper at ICLR 2022
C DETAILS ON EXPERIMENTS
In this section, we provide the details of experiments including generation schemes and hyperparate- mers of models. We run all experiments on single desktop equipped with NVIDIA Titan X GPU and AMD Threadripper 2990WX CPU.
C.1 PHYSICAL DIFFUSION EXPERIMENTS
C.I.1 DATA GENERATION
In this section, we provide the details of porous network problems.
Diffusion Equation
For fluid flow in porous media described by Darcy's law, equation 14 is specific
(p. p.) 0, Vo, V V ((V),
(A.9)
8p lig
(EN(()
where is the dynamic viscosity of the fluid, and rij and 4y are the radius and length of the cylindrical throat between the i-th and j-th pore chambers respectively.
Data generation We generate random pore networks inside cubic domain of width 0.1 m using Voronoi tessellation. We sample the pore diameters from the uniform distribution of U999 10- m. 10.1x10-3 m) and assume that the fluid is water with μr = 10-3 Nsm -2 under the temperature of 298 K(25 *C). The boundary conditions are the atmospheric pressure ,101,320 Pa) on the front surface of the cube, zero pressure on the back surface, and no-flux conditions on all other surfaces. We simulate the flow using OpenPNM (Gostick et al., 2016). We normalize the pressure values (targets) by dividing the pressure by the maximum pressures of the pores. Note that this normalization is always viable because the maximum pressure is the prescribed boundary pressure the front surface due to the physical nature the diffusion problem.
C.1.2 DETAILS OF CGS AND BASELINES
In this section, we provide the details of CGS and the baseline models. For brevity, we refer an MLP with hidden neurons ni, n22, ... ny for each hidden layer as MLP(n,, 722, un n1).
Network architectures
CGS CGS (m): fo is single layer attention variant of graph network (GN) (Battaglia et al., 2018) whose edge, attention, and node function are MLP(64). The output dimensions of the edge and node function are determined by the number of heads m. p(-) is the summation. is MLP(64, 32). All hidden activations are Lea. We set 7 as 0.5.
IGNN: fe. 9u is the same the one of (8)(
SSE: We modify the original SSE implementation (Dai al., 2018) so that the model can take the edge feature as an additional input. As 9o, we use the same architecture to the one of CGS (m).
(n): It is the plain GNN architecture having the stacks of n different GNN layers as fe. For each GNN layer, we utilize the same GN layer architecture the one of CGS(m)) (m). go is the same the one of CGS (m).
Training details We train all models with the Adam optimizer (Kingma & Ba, 2014), whose learning rate is initialized 0.001 and scheduled by the cosine annealing method (Loshchilov & Hutter, 2016). The loss function is the mean squured error (MSE) between the model predictions and the ground truth pressures. The training graphs were generated on-fly as specified in the data generation paragraph. We used 32 training graphs per gradient update. On every 32 gradient update, we sample the new training graph. We train 1000 gradient steps for all models.
Training curves
The training curves of the CGS models and baselines provided in figure 6.
18

---

Published as a conference paper at ICLR 2022
CGSB
CGS16
KGNN
0.100
SSE
Train MSE
GNN1
GNN2
0.010
200
400
600
800
1000
Steps
Figure 6: Training curves of the CGS models and the baselines. We repeat the training 5 times per each model. The solid lines show the average training MSE over the training steps. The shadow areas visualize the + 1.0 standard deviation over the runs.
C.2 GRAPH VALUE ITERATION EXPERIMENTS
In this section, we provide the details of data generation, the CGS models and baseline architecture and their training schemes.
C.2.1 DETAILS OF GVT DATA GENERATION
Data generation We generate the MDP graph by randomly sampling nh out-warding edges for all nodes. The discount factor of MDP is 0.9. Rewards sampled from the uniform distribution whose upper and lower bounds are 1.0 and -1.0 respectively. The true state-values (labels) are computed by iteratively employing the exact analytical Bellman operator (equation 5) until the state-values converge (i.e., value iteration). The convergence tolerance is 0.001.
C.2.2 DETAILS OF CGS AND BASELINES
Network architectures
CGS (m)): fa is a three layer attention GN network as whose edge, attention, and node function are MLP(128). The output dimensions of the edge and node function are determined by the number of heads m. p(.) the summation. 9e MLP(64, 32). All hidden activations are LeakyRel.U. We set Y 0.5.
IGNN: for 9o is the same the one of CGS (32).
SSE: We modify the original SSE implementation (Dai et al., 2018) so that the model can take the edge feature as an additional input. As ge. we use the same architecture the one of CGS (m).
Training details We train all models with the Adam optimizer whose learning rate is initialized as 0.001 and scheduled by the cosine annealing method. The loss function MSE between the model predictions and the ground truth state-values. The training graphs are generated on-fly as specified in the data generation paragraph. We use 64 training graphs per gradient update. On every 32 gradient graphs, sample the training graph. We train 5000 gradient steps for all models.
C.3 GRAPH CLASSIFICATION EXPERIMENTS
C.3.1 EXPERIMENT DETAILS AND HYPERPARAMETERS
In this section, we explain the network architecture and training details of the six graph benchmark problems. Across all the benchmark dataset, we use the dataset implementation et al., 2019) and cross- cross-vlidatiin indices generated with Scipy (Virtanen et al., 2020). We set the contraction factor 7 as 0.5. We train all models with the Adam optimizer whose learning rate is initialized 0.001 and scheduled by the cosine annealing method for 500 (100 for NCT1 dataset
DGL (Wang
19

---

Published as a conference paper at ICLR 2022
Table Graph classification results (accuracy in %).
IMDB-B
IMDB-M
MUTAG
PROT.
PTC
NCTI
# graphs
1500
1113
344
41T0
# classes
3
2
Avg # nodes
19.8
13.0
17.9
39.1
25.5
29.8
IGNN (Gu al., 2020)
89.3
77.7
3.4
70.1
+.6
80.5 + 1.9
CG8 (4)
76.0 2.0
62.3 0.5
7.7
81.3 + 4.5
75.3
6.3
77.86
1.8
CGS (8)
76.0 1: 2.3
62.7.10.5 0.5
0.22..52
$1014.
74.0
14.0.50 5.5
78.9 1 2.0
CGS (16)
76.4 2.0
63.4 0.4
04.64..3 4.3
80.2 4.4
7.0
79.1 + 1.6
CGS (32)
76.4 3.0
59.4 1.0
95.7 4.2
80.1 4.4
6.00
79.1 2.1
due the large datset size) epochs with 128 mini-batch size. We the random seed of Scipy, Pytorch Paszke et al. (2019), and DGL as O.
Hyperparameter tuning Due to our limited computational resources, we search at most 10 different pairs of hyperparameters for each dataset. To find the initial hyperparemters, we first tune CGS (4) on MUTAG, which is the smallest dataset. For each benchmark dataset, we start hyperparmeter tunings from the hyperparameters that are used for MUTAG-CGS (4) and tune the activation functions of Sa and ge. the number of GN layers in fa. the number of layers of go. and the dropout rate of gø-
Network architectures
IMDB-Binary: fo is two layer attention GN network as whose edge, attention, and node function are MLP(128). The output dimensions of the edge and node function are determined by the number of heads m. The hidden dimensions of edge, and node are 64. p(-) is the summation, go MLP(64, 32). All hidden activations are Swish Ramachandran et al. (2017).
IMBD-Multi: The same as IMDB-Binare
MUTAG: The
IMDB-Binary All hidden activations LeakyReLU,
PROTEINS: The same as the MUTAG. Apply dropout Srivastava et al. (2014) with probability 0.2 after the activation functions of go-
NCI1: The same as IMDB-Binary.
C.3.2 EXTENDED BENCHMARK RESULTS
We provide the benchmark results of CGS with the test metric that is used from (Gu al., 2020). The test metric is to calculate the average maximal test accuracies over the test folds. CGS shows better predictive accuracies compared to IGNN.
20

---

Published as a conference paper at ICLR 2022
Table 4: Graph Value Iteration results over the different fo(-) architecture. We report the average MAPE and policy prediction accuracies (in %) of different n, and na combinations. All metrics are measured per graph. + shows the standard deviation of the metrics.
30
50
75
(00
10
10
10
10
15
1-003(16)
0072 =
1.35 = 4,29
10.75
3.38
0.11
2000
10.2
321 =
6.35
3
10.22 0.00
3.25
(0.20 0nS
2.00
(171
3,15
00.71 =:00=
2,56 2: 1.10
10,756
CRS(16)
(08)
0.000
2.78
10.79
0..8..00.00.)
(0.78
0.2
10.76:20008
53
(0.77 0.05
6.12-
2:21+
(0.70
00.00
6-003(16)
00.88
L
2.99
0.00
10.86
1:00::097
(0333 1005
2.77
(0.82
1,19
258.699
D ABLATION STUDIES
In this section, we provide the results of the ablation studies in GVI. The ablation studies were done to understand
the effect of fo()) architecture,
the effect of transition map design,
the effect of contraction factor 7
the effect of employing the non-linear transition maps,
the sample efficiency CGS.
We also provide the runtime comparisons of direct inversion and iterative methods to find the fixed points hidden embedding.
D.1 EFFECT OF fo(.) ARCHITECTURE
As the Ag) and (g) generation schemes of CGS allow the employment the arbitrary archi- tecture of GNN as fo(+), CGS has different predictive performances depending on the architectural selection of f-(-).
Here, we investigate the effect of the number of GN layers in fe(-) to the predictive performance of CGS for the GVI problems. The number of the independent GN layers controls the range of information when CGS constructs the transition maps. That is, larger number of GN layers allows the information be gathered from far neighborhoods while constructing (g) and (g)
Table 4 shows the predictive performances of CGS models with the different number of GN layers in fa(.). The model with n GN layers referred as n-CGS (16). general, the model with larger number of GN layers performs better. These results highlight that allowing the flexibility in fe(:) can be practically beneficial when we derive the model with guaranteed convergence.
D.2 DESIGN OF THE INPUT-DEPENDENT TRANSITION MAPS
The transition map T-(-) of CGS given follows:
To H ml () (A, Bo(G)
(A.10)
By restricting Ag( and (g) to input independent, we can consider simpler variants of CGS. We can consider three variants which has (1) input-independent A and B; (2) input-independent A and input- depetdeeeeddnttt B: (3) cannot differentiate different G and (2) is similar to Gu et al. (2020). Therefore, we provide the GVI results of (3) Fixed B CGS in here. From Table 5, we can confirm that having input-dependent A
A and indepenndd B. Out of three variants, (1)
and B in T-)-) shows best performances.
D.3 EFFECT OF CONTRACTION PARAMETER 7
The contraction parameter y, as hyperparameter, changes the fixed point (because it changes the linear map) and controls the rate of convergent speed as well. We investigate the effect of ? to the
21

---

Published as a conference paper at ICLR 2022
Table 5: Transition map ablation. We report the average MAPE and policy prediction accuracies (in %) of different n, and nu combinations with 500 repeats per combination. All metrics are measured per graph. = shows the standard deviation of the metrics.
27
75
100
1. perami
10
10
15
16
15
10
15
IQIM
28,38
0.13%)
20
27.17
265,006
Fioel B (26)
(0.0 3 (1.2.%)
10.33 6,87
(0.7
5.90 2.07
(212/))
(0.66 : 018 9)
6.60 a 2.71
(0.88
2.81
1:01
6066 a 000 30
6.34 : 2.58
(666 a
1081
0.00 %
1.7
3006 1 005 4)
687 a 2,21
00.85
10.96
0.00 (0)
1,6
258,485
Food B co3182)
(070
9:52 = 6.45
00.66
6.12 2:35
(313/9)
(0.5 0.08
4,38 2.96
(0.77
9000 2.00-1.7
(065 0.5
4.73 2.79
(063
12.59
())
0.0 1085
4.99 2.36
(0.53
13.10
1.70
265,70L
Fros (64)
(0.70:1 0.122:0:12:)
(0.64 0.000000
(0.53
cCB(16)
0.61::.0.100
2.50
00.84 3: 0.10 (.
1.53 = 1.22
(U81 1000000000 9)
133
(0.54: a 0.0 %)
165 = 1,66
(060 0.0 6)
0.76
(0.80
1.57 0.56
0:00::00:0 %)
10.00 1 005 4)
0
(0/79 2: 0.05 %
1,45 0.37
255,469
(0.8 0:00
4.39 2,66
(0.83
2.00 1.18
(0.81
1990 00001100 1.07
(0.7
2.16= 1.11
(051 0.03
1.73 0
(0.76
1.24 =244=0.00
10.80
1.72
(0.76
1.19-040 0:41
265.068
(0.55
0.05
Table 6: ablations. We report the average MAPE and policy prediction accuracies (in %) of different n, and n, combinations with 500 repeats per combination. All metrics are measured per graph. + shows the standard deviation of the metrics. All metrics are measured per graph.
0%
100
parmms
15
1.41
0.,2:1:0000
1.17
(0.80
250,009
(0.85 0.00
4.55 2.60
(0.86 %)
1 1.18
(0:83
1.02
(0:55 1,009
2
00.0
1668
(0.85 %)
1,23
(0:22 0,05
1.13
280,069
3.68 1 2,00
0,08
1.68 1.08
0.08 %)
(0.85 15)
(0.54 0:000
10.66:00000
1.48 0.75
0:00 %))
1.174.0..4
(0.4
1.46 0.56
15)
(0.82
1,19
280,069
predictive performance of CGS. We test three 0.3, 0.5, 0.7 and the experimental results are given in Table 6. The CGS model with smaller " tends to have higher prediction errors compared to the larger y. However, using larger enlargers the number of iterative steps. In this regard, we use 7 = 0.5 to balance the computational speed and the predictive performance of CGS.
D.4 COMPARISONS TO THE NON-LINEAR ITERATIVE MAPS
A natural question to the linear iterative map of CGS is "can we achieve performance gain if we employ non-linear contracting iterative maps?" To answer the question, we provide the extended experiment results.
The analysis of the existence and uniqueness of fixed points still holds when CGS employs component- wise con-expansive (CONE) activation (c.g., ReLU, Leaky Tanh, Swish, Mish) to the outputs of T.)) given as follows:
To (HIm)))) (()) + BB(
(A.11)
where o(-) is CONE activation. The gradient of loss w.r.t Ag( and Bg( can be computed similarly to the non-linear activation cases as described in Appendix B.
We compare the GVI results of linear CGS to the non-lineat CGS utilizing LeakyReLU as ((-). Table 7 shows the GVI experiment results. The linear CGS, CGS (m), and non-linear CGS, nl m1-CGS (mn) shows similar predictive performance on GVI experiments general. From these experiments, we can observe that the non-linear extension of CGS does not give significant performance gain.
Furthermore, the training of non-linear CGSs can be challenging as (1) they exhibit higher variance in loss while training, and (2) the choice of non-linearity can severely change the performance of the entire model. For instance, the rectifying units such as ReLU and LeakyReLU can result in the premature termination of the iterative schemes of CGS when Bg) has large negative values. Bounded activation such as Tanh limits the range of hidden embeddings to a certain range.
D.5 SAMPLE EFFICIENCY OF CGS
We assumed the training graph and corresponding labels are easily sampled while solving physical diffusion problem and GVI. For some practical cases, this assumptions cannot be made. Hence, we investigate the sample efficiency of CGS and our closest baseline IGNN(Gu et al., 2020).
22

---

Published as a conference paper at ICLR 2022
Table 7: Graph Value Iteration results over the non-linear and linear transition maps. We report the average MAPE and policy prediction accuracies (in %) of different n, and combinations. All metries are measured per graph. + shows the standard deviation of the metrics.
75
100
10
10
15
10
15
10
a1-009(8)
4.73
34T 1.4
3.5 1887
00.33
1.54
4 115--1112
3.21
4.1
2543099
1.0
0.88
0.55
1.5
4.33
4 0.97
00.55
0:09
0.1111
000
0.00
x1-008004)
(0.22 0.10
4.99 3.30
10:84 0,0999
2,00 1.11
(x) 4
193
00:4 99
1600
(08)
a a
0.7
0081 2:000:000
1:6 0.66
(03) 1us
1,0 0.8
0:01 90
113:2
280/590
099
(0,8
3.81 2.76
(0:8 0.08
2.22 1:51
0028 006
2:23 1.40
00:44 0:000000000
333 1.39
(084
2.03 1.20
003
(0:00 1.0000000
200
00:4
1.3 1,05
00.30 0:000:00000
254
C00(16)
4
2:000:0000
426.
25%
(0.55
(0.78:00111
0.066
10.76:00:00
0OS(04)
(0.84
4.94 3,80
(0.55 0.09%)
1.9
(0.8 0.6
1.8 0.99
(0.55
2
0.0 %)
(0.85 0.:5:-00.5500
(0.32 0.05
1.51 0.64
(0:52 93
1112
250JMM
CGS(64)
IGNN
Test MAPE
250
500
750
1000
1250
1500
1750
2000
# train graphs
Figure 7: Sample efficiency
We prepare 2048 training and 2048 test graphs and their labels. We then train CGS and IGNN by using the first 128, 256, 512, 1024, and 2048 training graphs. As shown in figure 7, confirm that the trade-off between the sample efficiency and expressivities. IGNN only utilizes the input-dependent bias terms in the transition maps; thus, such structural assumptions when the training samples are limited. However, IGNN shows more minor improvements along with the number of training samples. On the other hand, CGS performs worse than IGNN when the training graphs are limited, but it starts to outperform IGNN as more training samples are used. Finally, when the number of training samples increases (2 512 graphs), CGS outperforms IGNN significantly.
effective regularizer
D.6 RUNTIME COMPARISONS OF DIRECT INVERSION AND ITERATIVE METHODS
In this paragraph, provide the experimental results that shows the runtime of CGS models which solve the fixed point equation via direct inversion and iterative methods. For all size GVI graphs, test the models 100 times with n, 5. As shown in figure 8, for small graphs n, 4000. solving the fixed point equation with the direct inversion is faster than solving with the iterative scheme. However, the direct inversion scales worse than iterative method.
23

---

Published as a conference paper at ICLR 2022
CPU Runtimes
GPU Runtimes
0.3
CGS/2)-Direct
2
time (sec)
CGS(2)-y= 0.3
time (sec)
0.2
0.1
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
0g
ng
Figure 8: Runtimes of CGS models. For GPU experiments, the memory usage of the direct method
with n, 2 4000 exceeds 24GB VRAM.
24


Reviews:
[{"review_id": "xZhJyCsbA4_", "reviewer": "Reviewer_G7SD", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The key idea from the observation that the diffusion on a graph often converges to a fixed point. Thus the authors proposed a linear map that is used to mimic this procedure. I did not check all the derivations and proofs of the paper, but I believe the correctness of Theorem 1 is quite obvious. \n\nCurrently overall the paper is ok but there are three problem. \n\n(1) The result of Theorem 1 can be further improved. In the paper the authors only consider linear maps, but the Banach fixed point theorem is strong enough to handle nonlinear maps. I guess we can easily add non-linear functions such as ReLU, sigmoid or tanh to (6) to get a nonlinear convergent map.\n\n(2) In linear case, it might not be a good way to compute the fixed point by matrix inverse. The inverse of matrix might be expensive. Meanwhile, by using fast matrix multiplication we can use O(log n) matrix  multiplication to get an approximate fixed point very fast. \n\n(3) In graph value iteration, the authors only considered deterministic transition case, while in practice the transition are often with uncertainty. The authors may consider to extend this part to probabilistic cases.", "summary_of_the_paper": "The paper constructed a linear map on graph that is guaranteed to converge to a fixed point, by embeding such linear map into a graph neural network, it can be used to solve nonlinear problems on graphs. Experiments show that the proposed methods have good performance in various methods. ", "summary_of_the_review": "The motivation and the theory of the paper is clear and correct. But there are some space for the authors to further improve the quality of the paper, also the value iteration part of the paper is to restrictive and it need to be extended.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jv7Di9EMKmM", "reviewer": "Reviewer_R2aV", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "**Strong points:**\n\nThe paper is well-written and motivates the choice of the linear transition map from theoretical prospective. The fact that the transition map should depend on the input graph is Interesting and has not been explored by the previous works.\n\nThe paper also provides extensive ablation studies on their modelling choices as well as the snippet of the code for the model.\n\n**Weak points:**\n\nIt is a bit odd to compare the CGS across the number of heads, while GNN results are provided for a different number of message-passing layers. This particularly makes the figure 3 to be misleading. CGS and GNN will have a similar number of parameters if they have the same number of layers and output heads, if I understand correctly. I see that CGS results for different layers are provided in the supplement, but it will be handy to put them into the same table and compare CGS and GNN across the same parameters.\n\nThe similar issue is with SSE and IGNN models, especially since the architecture is slightly different across experiments. It would be handy to mark which CGS(m) is the most direct comparison to SSE and IGNN in terms of number of layers and heads.\n\n**Additional questions:**\n\nIt is intriguing that implicit GNN models can handle long-range interactions without increasing the depth of the GNN. Do you have a hypothesis why?\n\nIt is odd that more output heads result in better performance. The Implicit Layers tutorial by Zico Kolter (http://implicit-layers-tutorial.org/deep_equilibrium_models/, section “One (implicit) layer is all you need”) demonstrates that a single equilibrium layer is equivalent to modelling a “stack” of several equilibrium layers (or multiple GNN heads). Can it be that the increased performance is simply due to higher output dimensionality?\n\nMinor: I would be interested to see the runtime comparison between the GNN models and CGS, as CGS requires up to 50 iterations to converge (according to the code snippet).\n\n", "summary_of_the_paper": "The paper introduces the equilibrium GNN-based model with a linear transition map. The transition map is made contracting to ensure that the fixed point exists and is unique. The paper provides the extensive comparisons and ablation studies for the proposed model.\n", "summary_of_the_review": "The paper uses fixed-point iteration to find the equilibrium point of the graph network and constructs the transition map to be contracting and input-dependent to ensure a unique fixed point. The paper provides extensive comparisons with other equilibrium models and on different types of graphs. It is a clear accept for me.", "strength_and_weaknesses": "", "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": "c3uA5GcL9tJ", "reviewer": "Reviewer_i9Je", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "STRONG POINTS: There is a principled theory regarding contractive linear maps as well as the existence of inverses. Experiments are well explained (sometimes is interesting to explain again what is the readout for the classification). Supplementary material is often used by this reviewer just to better understand the statements and experiments, but they are very well structured and provide the necessary evidence. \n\nWEAK POINTS: I get the point of using SSE or IGNN for computing global descriptors of the graphs instead of node embedding, which is not scalable for real-world graphs (large number of nodes). However, the approach presented here is limited exactly for the same reason. Consider for instance the problem of learning many linear mappings for a very large graph. Gradient descent is difficult to compute (need either matrix inversion or solving a linear system) and this is not practical. This is why most of the experiments are done with small graphs. \n\nRECOMMENDATION and ARGUMENTS: My recommendation is weak acceptance. Since the WEAK POINT is evident, the theoretical contribution is very interesting and inspires additional tasks (widely applicable). \n\nQUESTIONS AND ADDITIONAL EVIDENCE. Please clarify the following paragraph: \"From the results, we can conclude that learning to generate transition matrices A(G) from the data is more effective than using the fixed transition matrix, as in SSE and IGNN, to achieve a model with better generalizability\" and contextualize with respect to the mechanism used by SSE. It there any trade-off between less mappings to learn and better generalization? ", "summary_of_the_paper": "This paper proposes a method for learning how to predict the properties of graphs. These properties are fixed points (e.g. the PageRank vector or Equilibrium Values of a Diffusion Process).Wrt existing methods (SSE and IGNN), CGS learn multiple transition matrices instead of using a unique one. The underlying idea is to: (a) learn several linear operators whose iterations lead to a fixed point, (b) aggregate/combine the fixed points and (c) make the final prediction. With these elements to hand it is possible to find fixed points for several tasks. The proposed approach is tested in PHYSICAL DIFFUSION, GRAPH VALUE ITERATION and GRAPH CLASSIFICATION. The results show that CGSs are competitive with the state of the art and sometimes generalize better. ", "summary_of_the_review": "The paper is theoretically interesting but the results are limited to small graphs. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EvU1UFVzRBi", "reviewer": "Reviewer_A3tH", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The proposed approach is technically sound and empirically evaluated on a range of experiments. The paper is generally well-written, easy to follow, and contains enough technical details to understand the underlying principles. I found that I had to look at the appendix a couple of times for important details. This includes for example the experimental details or the discussion on the runtime comparison of direct inversion and iterative methods. I think that it would have been beneficial to briefly summarize those details in the main paper.\n\nThe paper proposes a three-step procedure that is guaranteed to converge by construction. This approach is well motivated and seems promising. At first, one might wonder whether the constructed maps are expressive enough. Various experiments suggest that this is often the case. The ablation studies in the appendix corroborate the claim regarding computational complexity and suggest that the proposed method performs particularly well for problems with a large number of samples.", "summary_of_the_paper": "This paper proposes a graph neural network termed \"Convergent Graph Solvers\" that computes the stationary distribution of stochastic matrices. This is achieved by an implicit definition of a linear system and by computing the fixed point of that system. The paper shows on a range of problems that the proposed approach works well and that it is particularly fast for smaller graphs.", "summary_of_the_review": "The paper is well written, clearly explains the underlying assumptions and limitations, and shows promising results on a range of experiments. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper got four accepts (after the reviewers changed their scores), all with high confidences. The theories are complete and the experiments are solid. The AC found no reason to overturn reviewers' recommendations. However, the AC deemed that all the pieces are just routine, thus only recommended poster.
Decision: Accept (Poster)