Graph Coarsening with Message-Passing Guarantees
Authors: Antonin Joly
Nicolas Keriven
Venue: NeurIPS 2024 poster (2024)
Keywords: graph coarsening
message passing
graph neural network
Primary area: graph_neural_networks
TL;DR: We propose a new message-passing paradigm specific to coarsened graphs, with theoretical guarantees from the original graph.

Abstract: Graph coarsening aims to reduce the size of a large graph while preserving some of its key properties, which has been used in many applications to reduce computational load and memory footprint. For instance, in graph machine learning, training Graph Neural Networks (GNNs) on coarsened graphs leads to drastic savings in time and memory. However, GNNs rely on the Message-Passing (MP) paradigm, and classical spectral preservation guarantees for graph coarsening do not directly lead to theoretical guarantees when performing naive message-passing on the coarsened graph.

In this work, we propose a new message-passing operation specific to coarsened graphs, which exhibit theoretical guarantees on the preservation of the propagated signal. Interestingly, and in a sharp departure from previous proposals, this operation on coarsened graphs is oriented, even when the original graph is undirected. We conduct node classification tasks on synthetic and real data and observe improved results compared to performing naive message-passing on the coarsened graph.

Graph Coarsening with Message-Passing Guarantees
Antonin Joly IRISA, Rennes, France intonin.joly@imee
Nicolas Keriven CNRS, IRISA, Rennes, France nicolas. keriven@cnss.ff
Abstract
Graph coarsening aims to reduce the size of large graph while preserving some its key properties, which has been used in many applications to reduce com- putational load and memory footprint. For instance, in graph machine learning, training Graph Neural Networks (GNNs) on coarsened graphs leads to drastic savings in time and memory. However, GNNs rely on the Message- Passaaggg (MP) paradigm, and classical spectral preservation guarantees for graph coarsening do not directly lead to theoretical guarantees when performing naive message-passing on the coarsened graph.
In this work, we propose a new passage-passingg operation specific to coarsened graphs, which exhibit theoretical guarantees on the preservation of the propagated signal. Interestingly, and in sharp departure from previous proposals, this op- eration on coarsened graphs often oriented, even when the original graph undirected. We conduct node classification tasks on synthetic and real data and observe improved results compared to performing naive pesssag--passig on the coarsened graph.
Introduction
In recent years, several applications in data science and machine learning have produced large-scale graph data 22 5. For instance, online social networks [3] recommender systems [40] routinely produce graphs with millions of nodes or more. To handle such massive graphs, researchers have developed general-purpose purpose graph reduction methods 44, such graph coarsening [32 77. It consists in producing a small graph from large graph while retaining some its key properties, and starts play increasingly prominent role in machine learning applications
Graph Neural Networks. Networks (GNNs)
Machine Learning on graphs is now largely done by Graph Neural 5) GNNs are deep architectures on graph that rely on the Message- Passing paradigm 16: : at each layer, the representation H E Rdl of each node < i S N, is
37
27
updated by aggregating and transforming the representations of its neighbours the previous layer {H) })))(()) where (i) is the neighborhood of i. In most examples, this aggregation can be represented as a muliipliaation of the node representation matrix Hi-1 e Nx by propagation matrix S XNNN related to the graph structure, followed by fully connected transformation. That is, starting with initial node features H the GNN & outputs after layers:
H' = 1SH (
(1)
where a is an activation function applied element-wise (often ReLU), 0, E Rdd-1xdd are learned parameters and 0 = ( 0x). J. We emphasize here the dependency of the GNN the propagation matrix Classical choices include mean aggregation S D- ' or the normalized adjacency S Dー AD- 2, with the adjacency matrix of the graph and D the diagonal matrix of degrees. When adding self-loops A, the latter corresponds for instance to the classical GCNconv layer [27].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

An interesting example is the Simplified Graph Convolution (SGC) model [2], which consists in removing all the non- non-linearity shown that SGC reaches quite good performances when compared to non-linear architectures and due to its simplicity, SGC has been extensively employed in theoretical analyses of GNNs [46 26
id the identity function). Surprisingly. the authors of 42 have
Graph coarsening and GNNs. In this paper, we consider graph coarsening as preprocessing step to downstream tasks [1]: indeed, applying GNNs on coarsened graphs leads to drastic savings in time and memory, both during training and inference. Additionally, large graphs may be too big to fit on GPUs, and mini- batching graph nodes is known to be a difficult graph sampling problem [14], which may no longer be required on coarsened graph. A primary question is then the following: is training a GNN on a coarsened graph provably close to training it on the original graph? To examine this, one must study the interaction between graph coarsening and paassagg-.ssing......
There are many ways of measuring the quality of graph coarsening algorithms, following different criteria 100 32 7 A classical objective is the preservation of spectral properties of the graph Laplacian, which gave birth to different algorithms [32 8 4 24 33 Loukas [32] materializes this by the so-called Restricted Spectral Approximation (RSA, see Sec. 2 property: it roughly states that the frequency content of a certain subspace of graph signals is approximately preserved by the coarsening, or intuitively, that the coarsening is well-aligned with the low-frequencies of the Laplacian. Surprisingly, the RSA does not generally lead to guarantees on the message passsing process at the the
core of GNNs, even for very simple signals. That is, simply performing pessage-passingg coarsened graph using S.,. the naive propagation matrix corresponding to S on the coarsened graph (e.g. normalized adjacency of the coarsened graph when S is the normalized adjacency of the original one) does not guarantee that the outputs of the GNN on the coarsened graph and the original graph will be close, even with high-quality RSA.
Contribution. In this paper, we address this problem by defining a new propagation matrix SMP specific coarsened graphs, which translate the RSA bound mnessge--passngg guarantees: we show in Sec. 3.3 that training GNN on the coarsened graph using S is provably close to training it on the original graph. The proposed matrix SMP can be computed for any given coarsening and is not specific to the coarsening algorithm used to produce i{] as long as it produces coarsenings with RSA guarantees. Interestingly, our proposed matrix SMP not symmetric in general even when S is, meaning that our guarantees are obtained by performing oriented message-passingg on the coarsened graph, even when the original graph undirected. To our knowledge, the only previous work to propose a new propagation matrix for coarsened graphs is (21]. where the authors obtain guarantees for a specific GNN model (APPNP (2)) which is quite different from generic message-passing
Related Work. Graph Coarsening originates from the multigrid-literature (36], and is part of family of methods commonly referred to as graph reduction, which includes graph sampling [9]. which consists in sampling nodes to extract subgraph; graph sparsification [38 31], that focuses on eliminating edges; or more recently graph distillation [22 (3). which extends some of these principles by authorizing additional informations inspired by dataset distillation [4T).
Some of the first coarsening algorithms were linked to the graph clustering community, e.g. which used recursively the Graclus algorithm [00 algorithm itself built on Metis (25. Linear algebra technies such as the Kron reduction were also employed [32] 12]. In (32), the author presents greedy algorithm that recursively merge nodes by optimizing some cost, with the purpose of preserving spectral properties of the coarsened Laplacian. This is the approach we use in our experiments (Sec. 4 It was followed by several similar methods with the same spectral criterion 8 4 24| 33 J. Since modern graph often includes node features, other approaches proposed to take
them into account in the coarsening process, often by learning the coarsening with specific regularized loss 22 3d Closer to this work, [1] proposes an optimization process to explicitely preserve the propagated features, however with theoretical guarantees and only one step of message-passing While these works often seek to preserve a fixed number of node features as in e.g. (29).. the RSA guarantees [32 leveraged in this paper are uniform over a whole subspace: this stronger property is required to provide guarantees for GNNs with several layers.
Note however that SMP must be computed during the coarsening process and included as an output of the coarsening algorithm, before eventually discarding the original graph.

---

Graph coarsening has been intertwined with GNNs in different ways. It can serve as graph pooling within the GNN itself, with the aim of mimicking the pooling process in deep convolutional models on images. In the recent literature, the terms "coarsening" and "pooling" tend to be bit exchangeable. For instance, some procedures that were initially introduced as pooling could also be used as pre-processing step, such as Graclus [10], introduced by [9] as pooling scheme, see also Graph pooling is often data-driven and fully differentiable, such as Diffpool [44), SAGPool 30 and DMoN [39]. Theoretical work their ability to distinguish non homomorphic graphs after pooling have been conducted [. In return, GNNs can also be trained to produce data-driven coarsenings. e.g. GOREN [6] which proposes to learn edge weights with GNN. As mentioned before, in the framework we consider here, graph coarsening is a preprocessing step with the aim of saving time and memory during training and inference (2I]. Here few works derive theoretical guarantees for GNNs and message-passinng beyond the APPNP architecture examined in (11) To knowledge, the proposed S.PP is the first yield such guarantees.
44
17..
Outline. We start with some preliminary material on graph coarsening and spectral preservation in Sec. [ We then present our main contribution in Sec. 3 a new propagation matrix on coarsened graphs that leads to guarantees for passage-passing
As is often the case in GNN theoretical analysis, our results mostly hold for the linear SGC model, however we still outline sufficient assumptions that would be required to apply our results to general GNNs, which represent major path for future work. In Sec. 4 we test the proposed propagation matrix on real and synthetic data, and show how it leads to improved results compared to previous works. The code is available graph- wereeggrraahhhaeeaeeee coarsening, and proofs are
inria. fr htr/anjolymmpguureeeeeeeerereeee httmm/pgggaaaatteeeeeee
deterred to App.A
Notations. For a matrix Q R its pseudo-inverse Q E R-Nxn is obtained by replacing its nonzero singular values by their inverse and transposing. For symmetric positive semi- (p.s.d.) matrix L E RNVN we define L by replacing its eigenvalues by their square roots, and T = (L++ For R. we denote by || Vx La the Mahalanobis semi-norm associated to T.. For a matrix P E RRNN we denote by |||| = max]|=]== || Pxx|| the operator norm of P, and ||P||
| PL- I. For subspace R, we say that matrix P is R-preserving if x R implies Px E R. Finally, for matrix X E R Nxd, we denote its columns by Xi and define |X|| = Σ, Ll
2 Background on Graph Coarsening
We mostly adopt the framework of Loukas [32]. with some generalizations. A graph G with N nodes wax.
is described by its weighted adjacency matrix A E RMNN, We denote by L E NNN a notion of symmetric p.s.d. Laplacian of the graph: classical choices include the combinatorial Laplacian L = D - A with D = (AA) = diag( A1 the diagonal matrix of the degrees, or the symmetric normalized Laplacian L = IN D AD 3. We denote by Amaxi Amin respectively the largest and smallest zonz eigenvalue of L.
Coarsening matrix. A coarsening algorithm takes graph G with N nodes, and produces coarsened graph Ge with n < N nodes. Intuitively, nodes in are grouped in "super-nodee nodes" Ge (Fig. D with some weights outline their relative importance. This mapping can be represented via a coarsening matrix Q E RaxN
Qu > 0 if the i-th node of G' is mapped to the k-th super-node of Ge Qu+
Q
otherwise
The lifting matrix is the pscudo-inverse of the coarsening matrix Q+, and plays the role of inverse mapping from the coarsened graph to the original one. The coarsening ratio is defined r ==1- N- That is, the higher r is, the more coarsened the graph is.
A coarsening is said to be well-mapped if nodes in G are mapped to unique node in Ge, that is. Q has exactly one non-zero value per column. Moreover, it is surjective at least one node is mapped to each super node: Σ. Qui > 0 for all k. In this case, QQ is invertible diagonal and Q Q (QQT)= Moreover, such a coarsening is said to be uniform when mapping weights
3

---

are constant for each super-nodes and sum to one: Qu = 1/ng for all Qx > 0, where is the number of nodes mapped to the super-node k. In this case the lifting matrix is particularly simple:
Q E {0, 1|Nx** (Fig. ldb. For simplicity, following the majority of the literature [32,, in this paper we consider only well-mapped surjective coarsenings (but not necessarily uniform).
coarsenings may appear in the literature, e.g. when learning the matrix Q via a gradiens-bate based optimization algorithum such as Diffpool [44y. However, these methods often include regularization penalties to favor well-mapped coarsenings.
Remark 1. Non-well-mappe
Restricted Spectral Approximation. A large part of the graph coarsening literature measures the quality of coarsening by quantifying the modification of the spectral properties of the graph, often represented by the graph Laplacian L. In [32]. this is done by establishing a near-isometry property for graph signals with respect to the norm || Ilz. which can be interpreted
measure of the smoothness of signal across the graph edges. Given a signal x E R N over the nodes of G, we define the coarsened signal xe E Rh and the re-lifted signal ä R by
Zee = Qu,
i= = xe = 1lx
I
(2)
where II = Q+Q Loukas 32 then introduces the notion of Restricted Spectral Approximation close to the identity
(RSA) of a coarsening algorithm, which measures how much the projection for a class of signals. Since II is at most of rank n < N, this cannot be true for all signals, but only for a restricted subspace R C RRN With this in mind, the RSA constant is defined as follows.
Definition 1 (Restricted Spectral Approximation constant). Consider a subspace R C CRN, Laplacian L, a coarsening matrix Q and its corresponding projection operator II= =QQ The RSA constant Q,R is defined as
CLQ.R = sup
1 =ER,I==
11 |L
(3)
In other words, the RSA constant measures how much signals in R are preserved by the coarsening- lifting operation, with respect to the norm - Given some R. and Laplacian L,, the goal of coarsening algorithm then to produce a coarsening Q with the smallest RSA constant possible. While the "best" coarsening arg ming ÉL, is generally computationally unreachable, there are many possible heuristic algorithms, often based on greedy merging of nodes. In App. B.I] we give an example of such an algorithm, adapted from [32 In practice, R is often chosen as the subspace spanned by the first eigenvectors of ordered by increasing eigenvalue: intuitively, coarsening the graph and merging nodes is more likely preserve the fow-frequencies of the Laplacian.
While CLQ.R < 1 is required necessarily finite. Indeed, as || ||z. may only be a semi-norm, its unit ball is not necessarily compact. nevertheless finite in the following case.
obtain meaningful guarantees, we remark that CL,QRR is not
Proposition 1. When is ker( L) prrsservnng, it holds that EL, S /maxx/Aun
Hence, some examples where LL, is finite include:
For uniform coarsenings with = D - A and connected graph G. ker(L) is the constant vecto and TI is ker( -))-reserrving. This is the case examined by (32].
Example 1.
Example 2. For positive definite "Laplacians", ker(L) {0}. This is deceptively simple solution for which || l| is true norm. This can be obtained e.g. with L = 81N + L for any p.s.d. Laplacian i and small constant 8 > 0. This leaves its eigenvectors unchanged and add 5 to its eigenvalues, and therefore does not alter the fundamental structure of the coarsening problem.
Given the adjacency matrix A E RNN of G, there several possibilities to define an adjacency matrix Ag for the graph G. (1 29 A natural choice that we make in this paper is
A. = (Q-) AQ+
In the case of uniform coarsening, (Ae) equals the sum of edge weights for all edges in the original graph between all nodes mapped to the super-node and all nodes mapped to L. Moreover, we have the following property, derived from [32]
Note that this would also work with several connected components, if no nodes from different components mapped to the same soder-node.

---

123
1/2
213
2/3
(a)
(b)
(c)
1
0
07
0
0
0
0
0
0
1
Q*
0
Il I
Q=Q
040
0
0 1
(d)
Figure 1: Example of uniform coarsening, (a): original graph G; (b): coarsened adjacency matrix Agi (c) representation of the proposed SheP when = AA; (d): corresponding matrices Q, Q+ II.
Proposition 2. Assume that the coarsening Q is uniform and consider combinatorial Laplacians == ((A) A and Le (Aee) Ag. Then L. (Q+) LQ* and
E (1 - (1. S |r S (1 + =r.
(5)
This draws a link between the RSA and a notion of near-isometric embedding for vectors in R. Note that the proposition above uniform coarsenings. In the next section, we propose new propagation matrix on coarsened graphs and draw link between the RSA constant CL,QRR and cesssage-passingg guarantees.
necessarily true when considering normalized Laplacians, non
3 Message-Passing on coarsened graphs
In the previous section, we have seen that coarsenings algorithms generally aim at preserving the spectral properties of the graph Laplacian, leading to small RSA constants E.Q.R. However, this generally does not directly translate to guarantees on the Message-Passing process that is at the core of GNNs, which as mentioned in the introduction is materialized by the matrix S. In this section, we propose a new propagation matrix such that small RSA constants leads to preserved message-passing, which then leads to guarantees for training GNNs coarsened graphs.
3.1 A new propagation matrix on coarsened graph
Given graph G with propagation matrix S and coarsened graph G. with coarsening matrix Q. our goal is to define a propagation matrix SMP E _R=x" such that one round of message-passing on the coarsened signal x, followed by lifting close performing message-passing graph: Q SMP x. R Sx. Assuming that the propagation matrix S = (A) is the output of function fs of the graph's 's adjacency matrix, the most natural choice, often adopted in the literature [I]] is therefore to simply take S. fs(A)). where Ag is the adjacency matrix of the coarsened graph defined in 4. However, this does not generally leads to the desired guarantees: indeed, considering for instance S = A, we have in this case Q+ S.r. (++++)" AlTx, which involves the quite unnatural term (Q++) For other choices of normalized S, the situation is even less clear. Some authors propose different variant of S, adapted to specific cases [21 44) (see Sec. 4), but none offers generic message-passing guarantees. To address this, we propose a new propagation matrix:
the original
ciMP
QSQ+ gaxx
(6)
This expression is conceptually simple: it often amounts to some reweighting. For instance, when S A and in the case of uniform coarsening, have (P ) (Ac) / (Fig, Ic). Despite
5

---

this simplicity, we will see that under some mild hypotheses this choice indeed leads to preservation guarantees of message-passeen paatiingga for coarsenings with small RSA constants.
Orientation. An important remark is that, unlike all the examples in the literature, and unlike the adjacency matrix A, defined in 4 the proposed matrix S is generally asymmetric, even when S is symmetric. This means that our guarantees are obtained by performing directed message- passing on the coarsened graph, even when the original caassage-psssing procedure was undirected. Conceptually, this is an important departure from previous works. However S.MP becomes "more" symmetric when Q+ and Q" becomes more similar. This for instance the case when Q induces a balanced partition, where each supernodes has the same number of ancestors (which can be targeted by some pooling algorithms). On the contrary, the difference hetween Q and @+ more pronounced when supernodes are of very different sizes, which may happen for highly irregular graphs.
3.2 Message-Passing guarantees
In this section, we show how the proposed propagation matrix 66) allows to transfer the spectral approximation guarantees to message-passing passing guarantees, under some hypotheses. First, we must make some technical assumptions relating to the kernel of the Laplacian.
Assumption 1. Assume that II and S are both ker( L) ppreserving.
Moreover, since spectral approximation pertains subspace R, we must assume that this subspace is left unchanged by the application of S. Assumption 2. Assume that S is R-preserving.
As mentioned before, for Examples and 2 the projection 11 is ker(L))-peeerrvin) Moreover, R is often chosen to be the subspace spanned by the low-frequency eigenvectors of L and this case, all matrices of the form S = aIN + 3L for some constant a. B are both ker( [)) ())-preerrving and R-preserving. Hence, for instance, a primary example in practice is to choose GCNconv (27] with S = (A)- = ĀD( A) with À = A + IN. and to compute a coarsening with a good RSA constant for the "Laplacian" I. = (1 + 8) I 5 with small 5 0 and R spanned by eigenvectors of L. In this case, Assumptions and 2 are satistied. This is the implementation we choose in our experiments.
We now state the main result of this section.
Theorem 1. Define SMP as (6). Under Assumption 7 andd 2
for all x E R,
Srx - ++ SMP xellı. S <..l, (Cs + Cn))
where Cs = ||. and Cn = |IS
Sketch of proof. The Theorem is proved in App. A The proof is quite direct, and relies on the fact that, for this well-designed choice (6) of SMP, the lifted signal is precisely Q* SMP x ISSH.. Then, bounding the error incurred by II using the RSA, we show that this is indeed close to performing message-passing by S in the original graph.
This theorem shows that the RSA error CL..RR directly translates to an error bound between Sa and Q+ SMP Ze. As we will see in the next section, this leads to guarantees when training a GNN on the original graph and the coarsened graph. First, we discuss the two main multiplicative constant involved in Thm. [I]
Multiplicative constants. In full generality, for any matrix M we have |
<
V Amin- Moreover, when M and L commute, we have ||]] < [[M]]. As mentioned before, choosing S = aIN + 3L for some constants a, 3 is primary example to satisfy our assump- tions. In this case Cs || S ||S]]. Then, if S is properly normalized, e.g. for the GCNconv (27 example outlined above, we have ||S||| < 1. For combinatorial Laplacian I, = D however, we obtain ||||| < |a| N We observed in our experiments that the combinatorial Laplacian generally yields poor results for GNNs.
For Cn1 in full generality we only have Cn < Cs|lUlll < Cs / / since 11 is an orthogonal projector. However, in practice we generally observe that the exact value Cn ||SS|| is far better

---

than this ratio of eigenvalues (e.g. we observe a ratio of roughly On s (1/10) /maax/ Amin in our experiments). Future work may examine more precise bounds in different contexts.
3.3 GNN training coarsened graph
In this section, we instantiate our message-passing guarantees to GNN training on coarsened graph, with SGC as primary example. To fix ideas, we consider single large graph G, and node-level task such as node classification or regression. Given some node features X E R Nxd the goal is
to minimize loss function J : RV - R_ the output of a GNN &g [X, S) E RN (assumed unidimensional for simplicity) with respect to the parameter #:
min R(0) with R(O)= == J J(
(8)
where set of parameters that we assume bounded. For instance, can be the cross-entropy between the output of the GNN and some labels training nodes for classification, or the Mean Square Error for regression. The loss is generally minimized by first-order optimization methods on which requires multiple calls to the GNN on the graph G. Roughly, the computational complexity of this approach is O(T(N + D), where is the number of iterations of the optimization algorithm, D is the number of parameters in the GNN, and E is the number of nonzero elements in S. Instead, one may want to train on the coarsened graph Ge. which can be done by minimizing instead"
(o( == J(Q Do Sall))
where X = QX. That is, the GNN is applied on the coarsened graph, and the output is then lifted to compute the loss, which is then back peokappppe to compute the gradient of 9. The computational complexity then becomes ( + e) + TN), where S E is the number of nonzeros in SMP,, and the term TN is due to the lifting. As this decorrelates N and D, it is in general much less costly.
We make the following two assumptions to state our result. Since our bounds are expressed in terms of 1I,, we must handle it with the following assumption. Assumption 3. We assume that there is a constant CJ such that
(x)) - J(x')l S Cy || 1'11z
(10)
For most loss functions, is easy to show that [xx) [xx') S || - I'11, and when L is positive definite (Example 2 then || -=
I|.. Otherwise, one must handle the kernel of L, which may be done on case-by-cass basis of for an uppropriate choice of J.
The second assumption relates to the activation function. It is here mostly for technical completeness, as do not have examples where it is satisfied beyond the identity a id, which corresponds the SGC architecture [42) often used in theoretical analyses 46 26
Assumption 4. We assume that:
i) is R-preserving, that is. for all E R, we have (x) E R. We discuss this constraint below. i) [|(()) - al2 S Callæ - x'Ilz. Note that most activations are 1 1-Lipschitz w.r.t the Fuclidean norm, so this is satisfied when L is positive-definte with C. = =/>mmaxi Amiu-
ii a and Q+ commute: a(Q+v) y) = oy)). This is satisfied for all uniform coarsenings, or when o is l-positively homogeneous: (Az) = (z) for nonnegative X (e.g. ReLU).
Item i) above means that, when R is spanned by low-frequency eigenvectors of the Laplacian, does not induce high frequencies. In other words, we want a to preserve smooth signal. For now, the only example for which we can guarantee that Assumption 4 is satisfied is when linear, which corresponds to the SGC architecture [42]. As is the case with many such analyses of GNNs, non-linear activations are major path for future work. A possible study would be to consider random geometric graphs for which the eigenvectors of the Laplacian are close to explicit functions, e.g. spherical harmonies for dot-product graphs (2]. In this case, it may be possible explicitely prove that Assumption 4 holds, but this is of -fcoppe of this paper.
id and the GNN is
Our result on GNNs is the following.
NNoe that we apply the GNN on the coarsened graph, but still lift its output to compute the loss on the training nodes of the original graph. Another possibility would be to also coarsen the labels to directly compute the loss the coarsened graph [2]. but this is not considered here. See App. B.2 for more discussion.
7

---

Theorem 2. Under Assumptions
1 for all node features X E R such that X., E R. denoting
by Hr arg mingee R(0) and t arg mingge (0), we have
R(O.) R((0)= S &
(11)
with C 2 CCC,C Cn) Ei=1 Ch '''' where Cn == ||LSSTI|| and Ce is constant that depends on the parameter set 6
The proof of Thm. is given in App. A.3 In this proof, to apply the Theorem 1 we apply the RSA to each nodes features column. It relies on the assumption that each column of the nodes features x belongs to the preserved space R. This assumption seems reasonable for homophilic datasets (Cora, Citeseer) and large preserved space The Theorem states that training a GNN that uses the proposed St the coarsened graph by minimizing
( yields parameter 0g whose excess loss compared to the optimal 0" is bounded by the RSA constant. Hence, spectral approximation properties of the coarsening directly translates to guarantees GNN training. The multiplicative constants Cs, Cn have been discussed the previous section, and the same remarks apply to Cn.-
Experiments
Setup- We choose the propagation matrix from GCNconv (27 that is, S = fs(A) D(Ā) AA)) with Á = A+ Iv. As detailed in the previous section, we take L II+8)IN-S with = 0.001 and R as the first eigenvectors L (K = N/10 in our experiments), ensuring observed that the combinatorial Laplacian = A gives quite poor results, as it corresponds to unusual propagation matrices S = alN + 3LL and the constant Cs |ااا is very large. Hence our focus the normalized case.
that Assumptions and 2 are satisfied. In experiments,
On coarsened graphs, we compare five propagation matrices:
MP QSQ+, +, our proposed matrix
S. fs(Ac), the naive choice
Sding = 1/2 (Ac + +C)D'1/2 proposed in (21), where C is the diagonal matrix of the ng and D' the corresponding degrees. This yields theoretical guarantees for APPNP when S is GCNconv;
Sdiff = QSQT, which is roughly inspired by Diffpooo [4];
Stam = TS*+ which the lifting employed to compute A
Coarsening algorithm. Recall that the pro- posed SMPP can be computed for any coarsening. and that the corresponding theoretical guaran- tees depend on the RSA constant CL.QRR- In our experiments, we adapt the algorithm from [32] coarsen the graphs. It takes as input the graph G and the coarsening ratio desired r and output the propagation matrix SMP and the coarsening matrix Q used for lifting. It is greedy algorithm which successively merges edges by minimizing a certain cost. While orig- inally designed for the combinatorial Laplacian, we simply adapt the cost to any Laplacian I,, see App. B.I Note however that some mathemat- ical justifications for this approach in [32] are no longer valid for normalized Laplacian, but we find in practice that it produces good RSA
S
10
8611
8pam
S
Shha
CELQR
10
10
10.5.
10
10"
Figure 2: Message-Passing error for different prop- agation matrices.
constants.
A major limit of this algorithm is its computational cost, which is quite high since it involves large matrix inversion and SVD computation. Hence we limit ourselves to middle-scale graphs like Cora 35 and Citeseer [5] and one larger graph with Reddit [88 in the following experiments. The design of more scalable coarsening algorithms with RSA guarantees an important path for future work, but out-of-scope of this paper.

---

Message passing preservation guarantees To evaluate the effectiveness of the proposed prop- agation matrix, we first illustrate the theoretical message passing preservation guarantees (Thm. and on synthetic graphs, taken as random geometric graph, built by sampling 1000 nodes with coordinates in [0, 1]a and connecting them if their distance is under a given threshold (details in App. [33 For each choice of propagation matrix and different coarsening ratio, we compute numer- ically || c x - (S yxxllx for various signals x E R. We perform N = message-passiln steps to enhance the difference between propagation matrices. We evaluate and plot the upper bound defined by L1.QR + Σi= C (seen in the proof of Theorem 2 in App. A.3 in Fig. We observe that our propagation matrix incurs a significantly lower error compared to other choices, and that as expected, this error is correlated to EL, which is not the case for other choices. More experiments can be found in App. B.4
Node classification on real graphs. We then perform node classification experiments on real-world graphs, namely Cora (35] and Citeseer (15), using the public split from [43] For simplicity, restrict them to their largest connected componen since using a connected graph is far more convenient for coarsening algorithms (details in App. B.3) The training procedure follows that of Sec. 3.3] the network is applied to the coarsened graph and coarsened node features, its output is lifted to the original graph with Q+, and the label of the original training graph nodes are used compute the cross-entropy loss, which is then pack-propagater to optimize the parameters 9 (pseudocode in App. B.2 Despite the lifting procedure, this results in faster training than using the entire graph (e.g.. by approximately 30% for a coarsening ratio of r = 0.5 when parallelized on GPU). For downstream tasks we introduce a novel metric analyze a specific coarsening : "Max acc possible". It corresponds to the optimal prediction over the super-nodes of the coarsened graph (all the nodes coarsened super nodes has the same prediction. optimally the majority label of this cluster). It might be hard to achieve as the optimal assignment for the validation nodes or training nodes can be different. It allows comparing different coarsenings for classification task without training models on it. We test SGC 42 with Np = 6 and GCNconv (27] with N, 2 on four different coarsening ratio: r E {0.3, 0.5, 0.7] where Np is the number of propagation. Each classification results is averaged on 10 random training.
Results are reported in Table and Table We observe that the proposed propagation matrix SMP yields better results and is more stable, especially for high coarsening ratio. The benefits are more evident when applied to the SGC architecture 22) for which Assumption 4 of Thm. is actually satisfied, than for GCN, for which ReLU is unlikely to satisfy Assumption 4 It is also interesting to notice that training on coarsened graphs sometimes achieve better results than on the original graph. This may be explained by the fact that, for homophilic graphs (connected nodes are more likely to have the same label), nodes with similar labels are more likely to be merged together during the coarsening, and thus become easier to predict for the model. The detailed hyper- hyper-parameters parameters for each model and each dataset can be found in appendix B.S]
Table 1: Accuracy in % for node classification with SGC and different coarsening ratio
Cora
Citeseer
SGC
0.3
0.5
0.7
0.3
0.5
0.7
Stym
16.8+ 3.8
16.1
3.8
16.4
4.7
17.5 3.8
18.6 4.6
19.8 5.0
Silff
50.7 + 1.4
21.8
+ 2.2
13.6 2.8
50.5
0.2
30.5 + 0.2
23.1 + 0.0
Se
79.3 + 0.1
78.7
+ 0.0
74.6
0.1
72.8 - 0.1
72.5 0.1
Sdiag
79.9 + 0.1
78.7
+ 0.1
77.3
73.6
73.4 - 0.1
73.1 + 0.4
SMP (ours)
81.8 + 0.1
80.3
+ 0.1
78.5
0.0 88.9
7.19
74.6 + 0.1
74.2 + 0.1
Max acc possible
96.5
92.5
93.5
90.5
84.5
Full Graph
81.6 1.1 0.1
73.6 - 0.0
Scaling to larger Datasets We performed experiments on the Reddit Dataset 18], which is approximately 100 times bigger than Cora or Citeseer. The Ceessage-Passingg error for different coarsening propagation matrices is reported in Table 33 with the node prediction results on two coarsening ratio = 90% and r = 99% (their number of nodes,and edges can be found in App B.3). the details of the hyperparameters and coarsening procedure are in B.6 Our propagation matrix for
'hence the slight difference with other reported results these datasets

---

Table 2: Accuracy in % for node classification with GCNconv and different coarsening ratio
Cora
Citeseer
GCNconv
0.3
0.5
0.7
0.3
0.5
0.7
S
80.1 + 1.3
78.1
+ 1.3
30.8 + 2.5
71.0 + 1.4
62.5 + 11
52.7 + 3.6
Sulff
81.9 + 1.0
74.5
+ 0.9
62.6
7.1
72.7 + 0.4
71.2 = 1.7
37.6 1 0.9
Se
81.2 + 0.8
79.9
- 0.9
78.1
1 1.0
71.7 +
70.7 = 1.0
67.1 1.1
Sciag
81.4 + 0.8
80.4 + 0.8
78.6
+ 1.3
72.1
+ 0.6
70.2 - 0.8
69.3 - 1.9
Saa (ours)
+
79.8 1.5
78.2 0.9
72.8 0.8
72.0 0.8
70.0
Max acc possible
96.5
92.5
88.9
93.5
90.5
84.5
Full Graph
81.6 = 0.6
73.1 = 1.5
coarsened graphs achieved better Plessage-Passingg error, close to the RSA-constant computed in the coarsened graph. consistent with the fact the Message-Passing error is bounded by Theorem I with propagation matrix. Similarly, for the node prediction results, our propagation matrix SMP achieves good results with the SGC model, close to the maximum accuracy possible on the given coarsening. Our propagation matrix is still competitive with the GCNconv model and achieved better results on the biggest coarsening ratio. These experiments show the effectiveness our method on large graphs for which coarsening preprocessing step is crucial: indeed, most small-scale machines with single GPU, the Reddit dataset is too large to fit in memory and requires adapted strategies.
Table Accuracy in % for node classification Reddit Dataset and Message passing errors
SGC
GCNconv
MP
Reddit Dataset
0.90
0.99
0.90
0.99
0.90
0.99
Saym
37.1 + 6.6
3.7 + 5.5
48.1 + 8.9
34.8 + 4.0
4.73e16
2.07e27
Sdiff
18.3
14.9
71.3 1.0
18.7 1.7
0.92
1.00
S. Sdiag
87.5
88.0 0.1
2.4
2.46
1.75
87.6 0.1
0.0
88.1 0.2
55.5
2.45
1.74
SMP (ours)
90.2 0.0
64.1
84.4 0.3
6.9
0.22
0.88
Max Acc Possible
93.4
64.7
93.4
64.7
Not applicable
Full Graph
94.9
Non computable (OOM)
Not applicable
5
Conclusion
In this paper, we investigated the interactions between graph coarsening and dessage-Passsngg for GNNs. Surprisingly, we found out that even for high-quality coarsenings with strong spectral preservation guarantees, naive (but natural) choices for the propagation matrix on coarsened graphs does not lead to guarantees with respect to message-passinn a new message message-passing matrix specific to coarsened graphs, which naturally translates spectral preservation message-passing guarantees, for any coarsening. under some hypotheses relating to the structure of the Laplacian and the original propagation matrix. We then showed that such guarantees extend GNN, and in particular the SGC model, such that training the coarsened graph is provably close to training on the original one.
on the original graph. We thus proposed
There many outlooks to this work. Concerning the coarsening procedure itself, which not the focus of this paper, new coarsening algorithms could emerge from our theory, e.g. by instantiating optimization problem with diverse regularization terms stemming from our theoretical bounds. The scalability of such coarsening algorithms is also an important topic for future work. From a theoretical point of view, crucial point is the interaction between non-linear activation functions and the low-frequency vectors in graph (Assumption 4). We focused on the SGC model here, but a more in-depth study of particular graph models (e.g. random geometric graphs) could shed light this complex phenomenon, which we believe to be a major path for future work.
10

---

Acknowledgments and Disclosure of Funding
The authors acknowledge the fundings France 2030, PEPR IA, ANR-23-PEIA-000S and ANR GrandMa ANR-21-CE23-0006.
References
[1] Z. Allen-Zhu, Z. Liao, and L. Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 237-245, 2015.
[2] E. Araya and Y. de Castro. Latent distance estimation for random geometric graphs. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019. ISSN 10495258. URL betp://arxive org/ abs/ 190. 06841
[3] M. Bianchi and Lachi. The expressive power pooling in graph neural networks. Advances in neural information processing systems, 36, 2024.
[4] G. Bravo Hermsdorff and L. Gunderson. unifying framework for sparsification and coarsening. Advances in Neural Information Processing Systems, 32, 2019.
graph
[5] M. M. Bronstein, Bruna, T. Cohen, and P. Veličković. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv:2104.1347,, 2021. URL http::///a/atr.oorg 13478
[6] C. Cai, D. Wang, and Y. Wang. Graph coarsening with neural networks. In 9th International conference on Learning Representations, 2021.
[7] Chen, Y. Saad, and Z. Zhang. Graph coarsening: from scientific computing to machine learning, volume 79. Springer International Publishing, 2022. ISBN 4032402100282. doi: 00.1007/544322--02--0088
URL https:://///o ott.//.....gg/...
[8] Y. Chen, R. Yao, Y. Yang, and J. Chen. A gromov-wasserstenn geometric view of spectrum- preserving graph coarsening. International Conference on Machine Learning, pages 5257- 5281. PMLR, 2023.
[9] M. Defferrard, X. Bresson, and Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[10] I. S. Dhillon, Y. Guan, and B. Kulis. Weighted graph cuts without eigenvectors multilevel approach. IEEE transactions on pattern analysis and machine intelligence, 194117:1944-1957 2007.
[11] C. Dickens, E. Huang, A. Reganti, Zhu, K. Subbian, and D. Koutra. Graph coarsening via convolution matching for scalable graph neural network training. In Companion Proceedings of the ACM on Web Conference 2024, pages 1502-1510, 2024.
[12] Dorfler and F. Bullo. Kron reduction of graphs with applications electrical networks. IEEE Transactions on Circuits and Systems I: Regular Papers, 60(1):150-161 2012.
[13] D. Ediger, K. Jiang, Riedy, D. A. Bader, C. Corley, R. Farber, and W. N. Reynolds. Massive social network analysis: Mining twitter for social good. Proceedings of the International Conference on Parallel Processing, pages 583-593, 2010. ISSN 01903918, doi: 10.1109/ICPP. 2010.66.
[14] Gasteiger, C. Qian, and Günnemann. Influence-based mini-batching for graph neural networks. 12 2022. http:pttt://aaxt/ org/abs//2/0 09083
[15] C. Giles, D. Bollacker, and S. Lawrence, Citeseer: automatic citation indexing system, 1998. URL www neci. njj com

---

[16] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural Message Passing for Quantum Chemistry. In International Conference on Machine Learning (ICML), pages 1-14. 2017. ISBN 978-1-4577-0079--8 doi: 10. 10.1000//me URL httt:://arxiv.oor abs/ .12212
[17] D. Grattarola, D. 7ambon, F. M. Bianchi, and C. Alippi. Understanding pooling in graph neural networks. IEEE transactions on neural networks and learning systems, (5(2):2708-27)) 2022.
[18] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[19] P. Hu and W. C. Lau. A Survey and Taxonomy of Graph Sampling, pages 1-34, 2013. URL http:://a http///axvvv///////v//ee///aaal/ org 1308. 5865
[20] W. Hu, M. Fey, M. Zitnik, Y. Dong. H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. Neural Information Processing Systems (NeurIPS), (NeurIPS):1-34, 2020. URL httttttttp//iiii orgoorgg///.. abwaab/o..../////////////// 2005 006877
[21] Z. Huang, S. Zhang, C. Xi, T. Liu, and M. Zhou. Scaling up Graph Neural Networks Via Graph Coarseming, volume 1. Association for Computing Machinery, 2021, ISBN 9783450383325. doi: 74.114/3444544.34672225
[22] W. Jin, Zhao, S. Zhang, Y. Liu, J. Tang, and N. Shah. Graph condensation for graph neural networks. In International Conference on Learning Representations, 2021.
[23] W. Jin, X. Tang, H. Jiang, Z. Li, D. Zhang, J. Tang, and B. Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 720-730, 2022.
[24] Y. Jin, A. Loukas, and J. JaJa. Graph coarsening with preserved spectral properties. In International Conference on Artificial Intelligence and Statistics, pages 4452 4462. PMLR, 2020.
[25] G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal scientific Computing, (0(1):359-392, 1998.
[26] N. Keriven. Not too little, not too much: theoretical analysis of graph (over)smoothing. Advances in Neural Information Processing Systems (NeurIPS), 2022. URL WtRLhttp:/// httt:://axiii 12156
[27] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2016.
[28] J. Klicpera, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized PageRank. 7th International Conference on Learning Representations ICLR 2019, pages 1-15, 2019.
[29] M. Kumar, A. Sharma, S. Saxena, and S. Kumar. Featured graph coarsening with similarity guarantees. In International Conference on Machine Learning, pages 17953-17975. PMLR, 2023.
[30] J. Lee, I. Lee, and Kang. Self-attention graph pooling. In International conference on machine learning, pages 3734-3743. PMLR, 2019.
[31] Y. T. Lee and Sun. Constructing linear-sized spectral sparsification in almost-linear time. SIAM Journal on Computing, 47(6):231--2333 2018.
[32] A. Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 20(1 20(116): (11): 2019.
[33] A. Loukas and Vandergheynst. Spectrally approximating large graphs with smaller graphs. In International conference on machine learning, pages 3237-3246. PMLR, 2018.
12

---

[34] T. Ma and J. Chen. Unsupervised learning of graph hierarchical abstractions with differen- tiable coarsening and optimal transport. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 9856-8864, 2021.
[35] A. K. Mecallum, K. Nigam, J. Rennie, and K. Seymore. Automating the construction of internet portals with machine learning, 2000. URL www. campsearch. com
[36] J. W. Ruge and K. Stüben. Algebraic multigrid. In Multigrid methods, pages 73-130. SIAM, 1987.
[37] Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1);61-80, 2008.
[38] D. A. Spielman and S. S.H. Teng. Spectral sparsification of graphs. SIAM Journal on Computing. 40(4):981-1025 2011.
[39] A. Tsitsulin, J. Palowitch, B. Perozzi, and E. Müller. Graph clustering with graph neural networks. Journal of Machine Learning Research, 24(127):1-21, 2023.
[40] J. Wang, P. Huang. H. Zhao, Z. Zhang, B. Zhao, and D. L. Lee. Billion-scale commodity embedding for E-commerce recommendation alibaba. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 839-848, 2018. doi: 10.1 41444//399989932298888
[41] T. Wang. J.-Y. Zhu, A. Torralba, and A. A. Efros. Dataset distillation. arXiv preprint arXiv:1811.10995 2018.
[42] Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. PMLR, 2019.
[43] Z. Yang, W. Cohen, and R. Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[44] Z. Ying, J. You, C. Morris, X. Ren, W. Hamilton, and J. Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018
[45] X. Zheng, M. Zhang, Chen, Q. V. H. Nguyen, X. Zhu, and S. Pan. Structure-free graph condensation: From large-scale graphs condensed graph-free data. Advances in Neural Information Processing Systems, 36, 2024.
[46] J. Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra. Graph Neural Networks with Heterophily. 35th AAAI Conference on Artificial Intelligence, AAAI 2021, 12B: 11168-11176, 2021.
13

---

A Proofs
We start by small useful lemma.
Lemma 1. For all k preserving matrices M, we have || S ||
Proof. Take the orthogonal decomposition x = u + where u E ker(L) and v E ker(L) Then, since ||>|| = || L Liv = and || 0.
| l - Me | ML elll - ||M
A.1 Proof of Proposition 2
Proof. The fact that L
LQ+) in this particular case done by direct computation. results
that | = | Izx| and
||ا|| - |xella, $ [L LA L = 1| Ix & CL.Q.el
by definition of ÉL.Q.R.
A.2 Proof of Theorem
Proof. Since R and S is R- R-preserving, we have
|||+ S RL
where II IN II, and similarly for Sz. Moreover, under Assumption both II and ker( (..--..)eerveigg.... such that ||TSSx]] x. for all x. Then
|Sx - Q+ SMP
SaP xellı = |St IISIL=||
|S5 ITS. + TSS IISTTa
|| Sz 11111 ø|1
< ||l Sx1lz + +|UUS1+**11
x 61.Q. | |
+
< 61.2 Sx 62Q.R [TS ||ll Q. (Cs + Cn)
A.3 Proof of Theorem 2
Recall that the GNN is such that H = X, and
H' (SH E R Nxde, Lx(X, = H² e R
Similarly, for the GNN coarsened graph denote by H Xx and its layers
H = a(S (1--0,) E gaxde (x SMP) = H e R
For some set of parameters 0 of GNN, we define
Co.1 =
sup sup Σ 16ghh
Co. II Co.
n=1
We start with a small lemma.
Lemma 2. Define
B = Bi()) = Σ |
(12)
Then we have
Bi < Co 1
(13)
14

---

Proof. From assumption 4 we have ||o(x)) S Collæele. Then, since S is ker( L) preserring from Assumption D by Lemmal
Σ H all
Σ 1 S Co Σ ||SH 16,,
S (sup
Σ Σ i
|SH '1l 11e S CBB.i
Since Bo | we obtain the result
Proof. We start with classical risk bounding in machine learning
J J( (X, J( (x) (X, - J(Q + 08. (Xe, SePP) ))
+ +J to. (X,, SMPP) J(Q $ (Xe: SMPP)
+ J(Q 2g. (Xe, (X, )) - ( (X,
$ 2 sup J ( X, S)) - J(Q + Fo (Xe, Se ))
since 0, minimizes J(Qttb((@@t...t (X )) For all 0, by Assumption
we have
())o(XX))) - J(Q (X ) S C2 C, Q+ to SMPP
(14)
We will prove a recurrence bound on
Ej = Σ |1 - Q+ (Ht).oll
From Assumption
F Σ (0))) - (0))
(0)..)) MP 11 11'-1 (l)
S C. Σ |H (0)).. - Q+ MMP (0)),,l)
s C. Σ
Σ (0))sl) ||SH a+s (
We then write
||SH - Q S.MP (H (HL-)) ) < || - Q 5.a "n! +10+ S Qu!5= -Q S (H ).illz.
Then note that, since both S and a are R-preservvigg for all 7, we have that (H') E R. We can thus apply Theorem to the first term:
| Q+ QH lI. S <... + Cn)
The second term is 0 when = 1 since H = QHº Otherwise, using QQ = In, and since under Assumption both S and II are ppreseriies applying Lemma] [
l1Q MP Q Q+s ( l1@ Q(H Q+ )
)
= - (
< |MST]|ZIIA - Qt a= (H!-")).sle
At the end of the day, we obtain
E x CCCorllL...R(S + Cn) (nE
x ( + C. Co
15

---

Co (Cs C1)l We recognize recursion of the form Un I C in 1n which leads to un S 2p=2 ap lippt b; un I by which results in:
using Lemma 2 and E C.
E& S (. (Cs + Cn)
Σ
Ck- c
(15)
1=1
This concludes the proof with Ce = maxage Co.k-
B Coarsening algorithm and experimental details
B.1 Adaptation of Loukas Algorithm
You can find below the pseudo-code of Loukas algorithm. This algorithm works by greedy selection of contraction (see below) according some cost, merging the corresponding nodes, and iterate. The main modification is to replace the combinatorial Laplacian in the Loukas code by any Laplacian L - (A), and update the adjacency matrix according 4 each iteration and recompute L, instead of directly updating L as in the combinatorial Laplacian case. Note that we also remove the diagonal of A at each iteration, as we find that produces better results. The output of the algorithm is the resulting coarsening Q, as well as SMP = QSQ for our application.
Algorithm Loukas Algorithm
Require: Adjacency matrix A, Laplacian I. (A),,, propagation matrix S, coarsening ratio r, preserved space R, maximum number of nodes merged at coarsening step ne
1: Nobj + int(NV N r) the number of nodes wanted at the end of the algorithm.
2: compute cost matrix Bo + VVT with V an orthonormal basis of R
3: Q 2--x IN
4: while n 2 Robj do
5: Make coarsening STEP
6: Create candidate contraction sets.
7: For each contraction C, compute cost Bt-1, L-1)- |[T (B L-1B:-1)
2/2
[C-
8: Sort the list of contraction set by the lowest score
9: Select the lowest scores non overlapping contraction set while the number of nodes merged is inferior to min(n Robj, ne))
Compute Qt, Q uniform intermediary coarsening with contraction sets selected
11:
Bi < Qi
Q + QiQ
13:
A + T "
14:
L--1 = (AI1)
15:
min(n Robjj Re.)
16: end while
17: IF uniform coarsening THEN Q row-normalize((i(Q)
18: Compute SMP = QSQ+
19: return Q, SMP
The terms He and Le are some specific projection of the contraction set, their explicit definition can be find in Loukas work (32. We did not modify them here and leave their eventual adaptation for future work.
Enforcing the iterative/greedy aspect In our adaptation we also add parameter to limit the number of nodes contracted each coarsening step. one coarsening step, when a contraction set is selected, we merge |C] nodes. In practice Loukas proposed in its implementation to force ne = oo and coarsen the graph one single iteration. We observed empirically better results by diminishing ne and combining with enforcing the uniform coarsening (Appendix B.4).
16

---

Candidate contraction Set. Candidate contractions sets come in two main flavors: they can be each two nodes linked by edges, or the neighborhood of each nodes (so-called "variation edges" and "variation neighborhood" versions). In practice, as the neighborhood are quite big in our graphs, it is not very convenient for small coarsening ratio and give generally poor results. We will use mainly the edges set as candidate contraction sets and adjust the parameter to control the greedy aspect of this algorithm.
Uniform Coarsening At each coarsening step, in Loukas algorithm Qi is uniform by construction. Nonetheless the product of uniform coarsening is not necessarily an uniform coarsening. Then, we propose option to force the uniform distribution in the super-nodes in the Loukas algorithm by normalize the non zero values each line of the final coarsening matrix Q. We observe that uniform coarsening gives better results for C,Q and works better for message passing guarantees. See Appendix B.4.
B.2
Discussion on Training procedure
The pseudocode of our training procedure is detailed in Algo.
Algorithm 2 Training Procedure
Require: Adjacency A, node features X, desired propagation matrix S, preserved space R, Lapla-
cian L, coarsening ratio r
1: Q. SMP +-
algorithm(A,
2: Xg +X
3: Initialize model (SGC GCNconv)
4: for Nepochs iterations do
5: compute coarsened prediction ( (SMP Xx)
6: uplift the predictions Q+ &b ( (SMP Xx)
7: compute the cross entropy loss ( X.))
8: Backpropagate the gradient
9: Update /
10: end for
Note that it different from the procedure of 21 which computes labels for the super-nodes (using the majority label in the coarsening cluster) and do not use the uplifting matrix Q+. We find this procedure be less amenable to semi-supervised learning, as super-nodes may merge training and testing nodes, and prefer to uplift the output of the GNN in the original graph instead. Additionally, this preserves the theoretical guarantees of Sec. 3 Our procedure might be slightly lower but we find the uplifting operation to be of negligible cost compared to actual backpropagation.
B.3 Presentation of dataset
Synthetic Dataset Random geometric graph is built by sampling nodes with coordinates in [0, 1] and connecting them if their distance is under given threshold. For the experiment illustrating the message passing preservation guarantees, we sample 1000 nodes with a threshold of 0.05 (fig
Table Characteristics of Cora and CiteSeer Datasets
Dataset
# Nodes
# Edges
# Train Nodes
Val Nodes
Test Nodes
Cora
2,708
10,556
140
500
1,000
Cora PCC
2,485
10,138
122
459
915
Citeseer
3,327
9,104
120
500
1,000
Citeseer PCC
2,120
7,358
80
328
663
Real World datasets We restrict the well known Cora and Citeseer to their principal connected cPM) as it more compatible with coarsening preprocessing. Indeed, the loukas
17

---

Figure Example of a random Geometric graph
algorithm tend coarsen first the smallest connected components before going to the biggest which leads to poor results for small coarsening ratio. However working with this reduced graph make the comparison with other works more difficult is the same training and evaluating dataset.
For the Reddit dataset ( 1 PCC) its characteristics and of its coarsened version as well of the Reddit and Cora coarsened dataset can be find in the table
Table 5: Characteristics of Reddit, Cora, Citeseer and its coarsen version
Dataset
# Nodes
Edges
# Features
#classes
Reddit
232,965 23,298
114,615,892
602
41
Reddit90
8,642,864
602
41
Reddit99
2,331
10,838
602
41
Cora PCC
2,485
10,138
1,433
Cora70
746
3,716
1,433
Citeseer PCC
2,120
7,358
3,703
Citeseer70
636
2,122
3,703
B.4 Discussion of hyperparameters and additional experiments
In the following section, we will use two different view of the same plot, to focus on different parts. We use the log-log scale (fig 4ay to put the focus on low coarsening ratio and on the upper bound. We use the linear scale (fig (bb) to compare more precisely our propagation matrix with Çdlag and S, for higher coarsening ratio.
18

---

SMP
1.0
SMP
Symm
5611
10 Sang
10
0.0
(a) Log Log scale
(b) Linear Linear Scale
Figure 4: Uniform coarsening with n. = 5.//100 and Normalized Laplacian
Uniform coarsening We observe that foreing uniform coarsening gives better Q,, and thus better message passing guarantees It is shown in the figure 5 for The 5N/110 with N the number of Nodes of the graph (1000 here).
0.8
56611
0.4
0.0
0.0
0.0
0.1
0.2
0.3
0.5
0.6
0.7
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
(a) uniform coarseming
(b) Non uniform coarsening
Figure 5: Coarsening with ne 5N/100 and Normalized Laplacian
For high coarsening ratio, we observe limits of the variation edges defined as Loukas with nhe oo as it gives bigger ÉI,QRR and thus worse curve for our propagation matrix in the coarsened graph ().
Bounding nh.
B.5 Hapam-pasameters for Table Table
preserve K eigenvectors of the normalized Laplacian defined L [x(1 + 8) - S with å = 0.001 and K = 10%N where N is the number of nodes in the original graph. We apply our adapted version of Loukas coarsening algorithm with n,, 5%.N for SGC Cora, SGC Citeseer and GCN citeseer and n. - oo for GCN Cora (variation edges as defined by Loukas). For SGC cora and SGC Citeseer make 6 propagations as preprocessing for the features. For GCN Cora and Citeseer we use convolationnal layer with a hidden dimension of 16. For all experiments we use Adam Optimizer wit a learning rate of 0.05 and weight decay 0.01.
For all experiments,
B.6 Hyper-parameters for Table
For the experiment on Reddit Dataset, we preserve K eigenvectors of the normalized Laplacian defined as T, = (1 + 6) with 0.001 and 400 eigenvectors to be computationally efficient (10%.N being too big). We apply our adapted version of Loukas coarsening algorithm with
19

---

1.0
SMP
1.0
SMP
5611
0.0
0.0
(a) 5N/100
(b)
Figure Uniform coarsening for Normalized Laplacian
Yee 10%.N for SGC Reddit and GCN Reddit. We computed 6 propagations for Reddit SGC and 2 for Reddit GCN. We keep the same hidden dimension as for Cora and Citeseer. For the reddit experiments, an Adam Optimizer wit learning rate of 0.1 and weight decay of 0.0.
20

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: This is mostly theoretical paper. Theorems and their implications are described in abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
ii) Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: This is mostly theoretical paper. Hypotheses are illustrated by examples and limitations are discussed. For experiments, scalability is discussed.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiscless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., the approach was only tested on few datasets with a few runs. In general, empirical results often depend implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
iii) Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
21

---

Justification:
Proofs are provided in Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
iv) Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Code is included supplementary material, and can be any computer.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
If the contribution
Depending on the contribution, reproducibility can be accomplished in various ways. For example, the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), relcasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
i) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
ii) the contribution primarily new model architecture, the paper should describe the architecture clearly and fully.
iii) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
iv) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited some way (e.g., registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
v) Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: libraries.
Code included as supplementary material, and use only open-source Python
22

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc/pbb))
Teadde//ooeeuuen ssiooooliy for more details.
While we encourage the release code and data, we understand that this might not possible,
so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips. cc/ Btapl//guiides/ooeSSubaae wttpbbmmmssooooooiicy.oooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
vi) Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All details are described in Appendix, and the code in supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
vii) Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Standard deviations are reported in Table results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should clear whether the error bar the standard deviation or the standard error of the mean.
OK report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
23

---

If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
viii)
Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
Answer: [Yes]
Justification:
This is small-scale code: it can be run on any computer in reasonable time.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
ix) Code Of Ethics
Question:
Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
This is mostly theoretical paper. The code use only open-source Python libraries.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due laws or regulations in their jurisdiction).
x) Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts the work performed?
Answer: [NA]
Justification: This is a mostly theoretical paper. We do not anticipate significant societal impact direct result of our work. Future algorithmic work scalability of graph coarsening could include such discussion, but this is relatively out-of-topic for this paper.
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact or why the paper does not address socictal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
xi) Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
This paper does not include such model.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
xii) Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The original paper for Cora and Citeseer is cited. Details are given in Appendix.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information creators.
available online, the authors encouraged reach the asset's
xiii) New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
25

---

Researchers should communicate the details of the dataset/code/mooel as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL include an anonymized zip file.
xiv)
Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage the country of the data collector.
xv)
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
26


Reviews:
[{"review_id": "II0gn7PY2P", "reviewer": "Reviewer_5Vcn", "summary": "This paper proposes a novel message-passing guarantee for graph coarsening and a new message-passing operation with the message-passing guarantee. Experiments demonstrate that the prediction performance of the proposed method outperforms some baselines.", "questions": "See Weaknesses.", "limitations": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed message-passing guarantee is novel.\n2. The authors provide the theoretical analysis", "weaknesses": "1. How to select the hyperparameters in experiments (e.g. the number of the SGC layers)? The selected coarsening ratio is significantly larger than existing works.\n2. Do linear GNNs [3] satisfy Assumption 4?\n3. I am not sure whether the analysis under the linearity assumption is enough. Assume the processed features of SGC is $H=A^TX \\in \\mathbb{R}^{n \\times r}$, where the feature dimension $r$ is significantly smaller than the number of nodes $n$. By noticing that the rank of $H$ is lower than $r$, we can compress the node features into sizes $(r,r)$ without errors. So, what is the motivation for graph coarsening under the linearity assumption?\n4. The authors may want to compare the spectral guarantee and the proposed message-passing guarantee in details. Moreover, I suggest summarizing these theoretical properties of existing methods and the proposed method.\n5. The formulation of message passing is different from [5]. The message passing framework considers the graphs with edge features while Equation (1) does not consider them. Therefore, the concept of message passing guarantees may mislead readers. In my opinion, the proposed concept in this paper is close to convolution matching [6].\n6. How to effectively compute $Q^+$ in practice? The complexity analysis is missing.\n\n\n[1] Featured Graph Coarsening with Similarity Guarantees.\n\n[2] Graph Distillation with Eigenbasis Matching.\n\n[3] How Powerful are Spectral Graph Neural Networks?\n\n[4] Graph Reduction with Spectral and Cut Guarantees.\n\n[5] eural Message Passing for Quantum Chemistry. \n\n[6] Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback. We address each comment below.\n\n**Q 1)** *How to select the hyperparameters in experiments (e.g. the number of the SGC layers)? The selected coarsening ratio is significantly larger than existing works*\n\n\nWe chose classical values for the training of SGC models as the paper don't focus on that point but on the theoretical guarantees. We will add more range of parameters, including coarsening ratios, in the appendices of the final version.\n\n**Q 2)** *Do linear GNNs [3] satisfy Assumption 4?*\n\nA linear GNN is formulated in [3] as $Z = g(\\hat{L})XW$ where $Z \\in \\mathbb{R}^{N \\times d}$ is the prediction matrix, $g$ is a learnable real-valued polynomial and $W \\in \\mathbb{R}^{N \\times d}$ a learnable weight matrix. The polynom of $L$ is a message passing with a number of layers equal to the degrees; as it is linear with $\\sigma = id$, hence the linear GNNs satisfies assumption 4. We will add the reference.\n\n\n**Q 3)** *I am not sure whether the analysis under the linearity assumption is enough. Assume the processed features of SGC is $H = A^KX \\in \\mathbb{R}^{n\\times d}$, where the feature dimension is significantly smaller than the number of nodes . By noticing that the rank of is lower than $n$ , we can compress the node features into sizes without errors. So, what is the motivation for graph coarsening under the linearity assumption?*\n\nThank you for this very interesting remark. Compressing the propagated features into sizes of the nodes features ranks would indeed result in a very different but efficient compressing method, even if it somewhat blurs the link with vanilla semi-supervised learning as the loss couldn't be computed directly. We elected to keep a direct link with message-passing and GNNs in this work, but consider your suggestion as a promising avenue for a future work. \n\n\n**Q 4)** *The authors may want to compare the spectral guarantee and the proposed message-passing guarantee in details. Moreover, I suggest summarizing these theoretical properties of existing methods and the proposed method.*  \n\n\nWith our new propagation matrix  $ S^\\textup{MP}\\_{c}$ on the coarsened graph (contrarly to other choices), spectral guarantees *lead* to message passing guarantees through the RSA-constant : $\\epsilon\\_{Q,{L}, \\mathcal{R}}$. Hence they are one and the same. To our knowledge, no other method has guarantees of this type, hence our difficulty to ``compare'' the theoretical bounds.\n\n**Q 5)** *The formulation of message passing is different from [5]. The message passing framework considers the graphs with edge features while Equation (1) does not consider them. Therefore, the concept of message passing guarantees may mislead readers. In my opinion, the proposed concept in this paper is close to convolution matching [6].*\n\nThank you for this remark. We agree that incorporating edge features in coarsened graphs in an important path for future work (eg to handle GAT), however GNNs without edge features remain classical in a lot of fundamental models such as GCNconv or GIN, where the auhors effectively define the \"propagation matrix\" to describe the message-passing process.\n\n**Q 6)** *How to effectively compute $Q^+$ in practice*\n\nWe use Loukas coarsening algorithm, where the matrix $Q$ is \"well defined\", i.e each original node is mapped to an unique \"super node\" in the coarsened graph. That means that $Q$ has an unique non zero entries by column. \n\nFor such matrix $Q \\in \\mathbb{R}^{N,n}$, Loukas proposed an \"easy inversion\" property (Proposition 6) $ Q^{+} = Q^TD^{-2}$ with $D(r,r) = \\lVert Q(r,:) \\rVert\\_2 $.\n\nAs the matrix Q has $N$ non-zero entries and as it is needed to compute the sum of the rows of Q, the complexity to compute the pseudo inverse is linear with the number of nodes in the original graph $\\mathcal{O}(N)$\n\n[3] How Powerful are Spectral Graph Neural Networks?\n\n[5] Neural Message Passing for Quantum Chemistry. \n\n[6] Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training", "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": "DNw163SJBp", "reviewer": "Reviewer_GXdc", "summary": "The authors describe an alternative way to obtain the connectivity matrix of a coarsened graphs and provide some bounds on operations performed on such a matrix.", "questions": "I do not have questions besides the concerns above.", "limitations": "See what I wrote in weaknesses.", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Theoretical work on how to optimally compute the connectivity matrix of a coarsened graph is an interesting and potentially useful research direction.", "weaknesses": "- The main contribution is very small, as it simply consists in replacing the coarsened matrix QSQ^T, commonly used in graph pooling, with QSQ^+. This seems more of a detail in practice and it seems too much to have a whole paper on it. I seriously doubt it would make a significant difference in practice and the limited experimental evaluation (more on this later) does not help to address my concern.\n- I don't see the usefulness of Theorems 1 and 2, which is the second contribution of the paper. They provide bounds which I don't find useful, as they do not compare against other existing bounds and they are not computed for other coarsening schemes, such as the more common QSQ^T. For example, it would be useful to see that the proposed coarsened matrix yields narrower bounds than the latter.\n- I believe that there are too many simplifications and assumptions for the theoretical results to be relevant in practice. For example, the RSA constant is defined only for 1-D node features, which is something not commonly found in many graph data processed by graph neural networks. Similarly, it seems that Theorem 2 relies on the assumption that each column of the node features X belongs to R, which seems too strong and unrealistic as assumption. Finally, the whole paper assumes GNNs without nonlinearities. I believe that a GNN without nonlinearity is not a GNN and a paper completely centered around the analysis of such models should rather be published in a (graph) signal processing or linear algebra venue, not a machine learning one.\n- The experimental evaluation is too limited and not convincing. First of all, it only considers relatively small graphs, as the coarsening algorithm used does not scale well. This defies the whole premise of using coarsened graphs to handle large graphs that cannot be processed due to high computational complexity. \n- Only one coarsening algorithm is considered to obtain Q, while there is a large pletora of existing graph pooling algorithms that can be used to compute Q. To convince about the effectiveness of the proposed method, the author(s) should show that it works with different coarsening schemes. Remarkably, the coarsening algorithm used in the experimental evaluation does not even account for node features. This, again, set the work apart from the GNN and machine learning community.\n- Besides the synthetic data, the only two datasets considered are Cora and Citeseer. These datasets are rather similar (both of them are citation networks) and they have very homophilic node features\\labels, which might biases the experimental evaluation. In addition, the experiment considers only the largest connected component of these networks, which further simplify the task on datasets that are already simplicistic. The need for such an unusual experimental setting casts further doubts on the effectiveness of the proposed method.\n- The authors largely overlook relevant related work on graph pooling. See for example the CONNECT operation from the paper entitled \"Understanding Pooling in Graph Neural networks\". \n- (minor) Ker(L) is not defined I think.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback. We have addressed your comments individually below. Before answering the questions, we would like to precise that Graph Pooling and Graph coarsening are two methods that are linked, but with different purposes. Graph Pooling is generally incorporated into the GNN to upgrade the classification results by mimicking the \"pooling\" in CNNs. It is often supervised, and diferentiable, such as DiffPool, but in turns has generally no guarantees, being the result of a non-convex optimization problem. On the other hand, Graph coarsening is a preprocessing used to gain memory. It is often non-supervised, with the type of guarantees such as the RSA constant introduced by Loukas.\n\n**Q 1)** *The main contribution is very small, as it simply consists in replacing the coarsened matrix $QSQ^T$, commonly used in graph pooling, with $QSQ^+$.  [...]*\n\nWe agree that this new propagation matrix is indeed \"deceptively\" simple, even if it is quite original in the sense that it is not a Laplacian or any other form of graph representation matrix, as it may not even be symmetric. In effect, we show that our proposal is the \"right\" normalization to directly translate spectral guarantees (which are classical in graph coarsening and the objective of many coarsening algorithms), to MP guarantees. Other matrices simply do not have this mathematical property. Note that when $Q$ is orthogonal, the two coincide, but classical \"uniform\" coarsenings are not orthogonal.\n\nAlso note that we compared in the experiments our matrix with $S\\_c^{diff} =QSQ^{T}$ inspired by the pooling litterature, and in our experiments, $S_c^{diff}$ give accuracy results which are far less competitive.\n\n\n**Q 2)** *I don't see the usefulness of Theorems 1 and 2, [...] They provide bounds which I don't find useful, as they do not compare against other existing bounds and they are not computed for other coarsening schemes, such as the more common $QSQ^T$. [...]*\n\nThe crucial part of our theoretical bounds is to the dependency on the RSA-constant $\\epsilon_{Q, {L}, \\mathcal{R}}$, which tend to be small, as it is explicitely minimized by coarsening algorithms. Unfortunately, other propagation matrices (including $QSQ^T$) simply do *not* yield any mathematical guarantee in this spectral-based framework, hence the impossibility to ``compare'' with existing bounds. We will clarify this in the final version of the paper.\n\n**Q 3)** *I believe that there are too many simplifications[...]. For example, the RSA constant is defined only for 1-D node features[...]. Similarly, it seems that Theorem 2 relies on the assumption that each column of the node features X belongs to R [...] Finally, the whole paper assumes GNNs without nonlinearities*\n\nSee global comment (B) for multidimensional node features. Thm 2 relies on the assumption that each column of the nodes features $X_{:,i} \\in \\mathcal{R}$, that is, are close to low-frequency. This assumption seems reasonable for homophilic datasets (Cora, Citeseer) and large preserved space.\n\nWe agree that for now the assumption on non-linearities is strong. However SGC is indeed used in many theoretical works to analyse the inner workings of GNNs (see eg [1,2] and references therein), and we still believe that it opens a path for interesting future works on the interaction between low-frequencies and non-linearities.\n\n**Q 4)** *The experimental evaluation [...] only considers relatively small graphs, as the coarsening algorithm used does not scale well. This defies the whole premise of using coarsened graphs to handle large graphs [...].*\n\nSee global comment (A).\n\n**Q 5)** *Only one coarsening algorithm is considered to obtain Q, while there is a large pletora of existing graph pooling algorithms that can be used to compute Q. [...] Remarkably, the coarsening algorithm used in the experimental evaluation does not even account for node features.[...]*\n\nThe starting point of our work are indeed coarsening algorithm that present spectral-based theoretical bounds (see header comment on graph pooling vs graph coarsening). To our knowledge, the Loukas coarsening algorithm is one of the most classical algorithm with such theoretical spectral guarantees. We do agree that future works focusing on the nodes features and coarsening algorithms incorporating both spectral guarantees and nodes features are a promising avenue, but this paper did not focus on the coarsening algorithm itself, but rather how to translate classical spectral guarantees to GNNs.\n\n**Q 6)** *Besides the synthetic data, the only two datasets considered are Cora and Citeseer. These datasets are rather similar (both of them are citation networks) and they have very homophilic node features\\labels, which might biases the experimental evaluation. In addition, the experiment considers only the largest connected component of these networks [...]*\n\n We considered the main connected component of Cora and Citeseer as Loukas coarsening algorithm was designed for fully connected graph. It is true that spectral coarsening algorithms might be less efficient on heterophilic datasets, since the features are less likely to live in the low frequency of the graph. The design of new coarsening algorithms for these graphs is an important path for future work. We conducted additional experiments on the Reddit Dataset with good results, see global comment (A)\n\n**7)** *See for example the CONNECT operation from the paper entitled \"Understanding Pooling in Graph Neural networks\"*\n\nThank you for the suggestion, we will add this reference to the final version and discuss it. We will also clarify the relation between pooling and coarsening (see top).\n\n[1] Zhu et al. *Graph Neural Networks with Heterophily*. AAAI.\n\n[2] Keriven. *Not too little, not too much: a theoretical analysis of graph (over)smoothing*. NeurIPS.", "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": "CNudTL0kEf", "reviewer": "Reviewer_foGd", "summary": "This work presents a novel computation method for the message-passing matrix on coarsened graphs. This method does not require recalculating degree matrices and other information on the coarsened graph and has comprehensive theoretical guarantees. Overall, it addresses a significant problem in graph coarsening field.", "questions": "How effective is this work on datasets such as Arxiv and Products?", "limitations": "The authors adequately addressed the limitation and potential negative societal impact  of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The theoretical analysis is sufficient and reasonable.\n2. The proposed method is very simple.\n3. The model performs very well on Cora and Citeseer.", "weaknesses": "The experimental section is insufficient. Testing only on Cora and Citeseer is not enough to demonstrate the effectiveness of the method. More GNN models should also be tried. I believe this work is a valuable contribution to the field of graph coarsening, and if the authors further increase the experiments, I will raise my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback.\n\n**Q 1)** *How effective is this work on datasets such as Arxiv and Products*\n\nSee global comment (A): improving our spectral corsening algorithm, we have conducted experiments on a larger graph, Reddit. This graph has 1.5 times more nodes than ogb-arxiv. For the final version of this paper, experiments on ogbn-arxiv,  conducted if time allows, would be a valuable addition.", "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": "alul0vR2M1", "reviewer": "Reviewer_eigc", "summary": "This paper proposes a new message-passing matrix for a graph coarsening algorithm. The goal is to have some message-passing guarantees for the new message-passing matrix, which is not the case with the previous message-passing matrices based on this coarsening. They provide theoretical proofs for linear variants of GNNs (SGC). They examine their theoretical guarantees on synthetic datasets and do experiments on two real-world graphs for comparing different selections of the message-passing matrices. Their approach in most of the experiments varying in the coarsening ratio, works better than alternative approaches.", "questions": "1. The theory is based on signal processing on graphs that work on a single value for each node. Most datasets have a vector of initial features for each node, how this can be addressed in the theory?\n\n2. How much does the coarsening algorithm help with the memory? GNNs usually scale by the number of nodes + the number of edges, the coarsening ratio r talks about how much you can reduce the number of nodes, but edges seem to be a more important factor in the memory and time complexity. Is there any theoretical or experimental analysis on the edges or memory in general?", "limitations": "The theoretical analysis is limited to the linear networks and the experiments are limited to two small datasets.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Graph coarsening can be indeed very beneficial if it can be done efficiently. Pooling approaches in some domains such as computer vision have been very helpful, but they are not as prominent in the learning on graphs community. Having well-studied approaches for this end can be of great importance because of the memory limitations of the GNNs. Also, their work has a deep root in the theory and provides theoretical guarantees for their approach.", "weaknesses": "While the theoretical analysis is interesting it is limited to the linear networks. Extending this analysis to more complex GNNs might not be an easy task, however, this does not mean that they could not try their approach for other types of GNNs and see if it works in practice or not. Maybe they could try more common message-passing architecture such as Graph Attention Networks (GAT) or Graph Isomorphism Networks too. Also, the datasets used are fairly old and outdated in the current state of learning on graph works. I would suggest trying some recent datasets, maybe varying from homophilous datasets to heterophyllous ones.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback. \n\n**Datasets** See global comment (A): we have performed additional experiments on the Reddit Dataset which is significantly bigger than Cora and Citeseer. Concerning heterophilous datasets, we note that spectral-based coarsening itself is probably very inefficient, as it basically aims at preserving the low-frequencies. Dedicated, new coarsening methods is an interesting path for future work. We will add a remark in the paper. \n\n**Other models** Because of attention coefficients, GAT do not rely on a propagation scheme that can be expressed as the multiplication of the node representation $H$ by a fixed propagation matrix $S$. Thus, we can't adapt our method to compute a new propagation matrix for the coarsened graph with this model. However, message-passing on coarsened graphs with attention coefficients and/or edge features is an important path for future work. We will add a remark.\n\n\n**Q 1)** *The theory is based on signal processing on graphs that work on a single value for each node. Most datasets have a vector of initial features for each node, how this can be addressed in the theory?*\n\nSee global comment (B).\n\n**Q 2)** *How much does the coarsening algorithm help with the memory? GNNs usually scale by the number of nodes + the number of edges, the coarsening ratio r talks about how much you can reduce the number of nodes, but edges seem to be a more important factor in the memory and time complexity. Is there any theoretical or experimental analysis on the edges or memory in general?*\n\nThe memory used and number of edges in the coarsened graph depend on the coarsening algorithm itself: in general, two super nodes are connected if at least two nodes they represent in the original graph are connected. For the Loukas algorithm that we used, Loukas wrote that \"The sparsification step was not included in the numerical experiments since it often resulted in increased errors\"  which prevent us to perform an additional sparsification step. A new coarsening algorithm that better controls the sparsity of the resulting graphs while balancing with good RSA constant is an interesting path for future work, but out of scope of the present paper.\n\nThe number of edges for Reddit after coarsening and cora citeseer can be found in the table 1 (see pdf attached with tables).", "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": "cs75iTjObR", "reviewer": "Reviewer_7C68", "summary": "This paper studies the theoretical guarantees of graph coarsening for GNNs. The authors propose a new and directed message-passing operation specific to coarsened graphs, which makes many theoretical results possible.", "questions": "Q1: Can the authors give some intuitive explanation on $\\overline{C}_{\\Pi}$, e.g., what kind of coarsening method will make this term smaller?\n\nQ2: It would be nice to see more experiments on larger datasets, e.g., ogbn-arxiv.\n\nTypo: Line 212, $\\hat{A}=A+I$.", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "S1: The results are very useful for the field of graph coarsening. Theorem 2 shows the gap of loss between the coarsened graph and the original graph, which is applicable for many tasks.\n\nS2: The new message-passing looks natural and novel to me.\n\nS3: The literature review is comprehensive.", "weaknesses": "W1: The overall structure is somewhat loose.\n\nW2: It would be nice to see more intuitive explanation of $S^{MP}_c$, e.g., when $S$ is symmetrically normalized adjacency matrix from GCN.\n\nW3: The experiments are conducted only on small datasets, which I understand since the authors put more effort on the theoretical analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback. We will fix the typos and clarify the description of the proposed propagation matrix.\n\n**Q1)** *Can the authors give some intuitive explanation on $\\overline{C}_{\\Pi}$, e.g., what kind of coarsening method will make this term smaller?*\n\nFrom a theoretical point of view, in general we only have a harsh upper bound: $$C_{\\Pi} \\leq \\lVert S \\rVert_{{L}} \\sqrt{\\frac{\\lambda_{max}}{\\lambda_{min}}} $$   as $\\Pi$ is an orthogonal projector and where $\\lambda$ are the eigenvalues of the laplacian ${L}$.\n\nFor a propagation matrix $S = \\alpha i_n + \\beta {L}$ and normalized as it is the case in our experiments $ \\lVert S \\rVert_{{L}}  \\leq 1$. Thus $C_{\\Pi}  \\leq \\sqrt{\\frac{\\lambda_{max}}{\\lambda_{min}}} $.\n\nThe same goes with $\\overline{C_{\\Pi}}  = \\lVert \\Pi S \\Pi \\rVert_{{L}}  \\leq \\lVert \\Pi \\rVert_{{L}} C_{\\Pi} \\leq \\frac{\\lambda_{max}}{\\lambda_{min}} $\n\n\nExperimentally we can however remark that we generally observe a factor 10 between the upper bound and the actual value of the constants. Moreover, we obtain lower values for uniform coarsenings. Theoretical interpretation of uniform coarsenings are a promising avenue to use in a coarsening procedure.\n\n\n**Q 2)** *It would be nice to see more experiments on larger datasets, e.g., ogbn-arxiv.*\n\nWe have conducted experiments on a larger dataset, namely the Reddit one (see global comment A). As said in the global comment, the Reddit Dataset has 1.5 times more nodes than ogbn-arxiv. For the final version of this paper, experiments on ogbn-arxiv, conducted if time allows, would be a valuable addition.", "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:
We thank all the reviewers for their reviews and questions. In this global comment, we address two questions that were mentioned in multiple reviews. Namely, we introduce new experiments on a larger dataset (Reddit) and comment on the multidimensionality of node features.

**A)** ***Larger Dataset***


As mentioned in the paper, Loukas' coarsening algorithm is one of the only one that provides RSA guarantees, but in turns it is quite costly to run. Improving the computational cost of spectral-based coarsening algorthms is a major path for future work, but out of scope of this paper. Hence we evaluated our coarsened propagation matrix proposition on small-ish datasets for the first version of our paper. During the reviewing process, we upgraded our code to deal with larger graphs and have conducted experiments on the Reddit Dataset, which is 1.5 bigger than ogb-arxiv dataset and 100 times bigger than Cora or Citeseer.

We performed two coarsening ratio on the Reddit Dataset ( available in torch geometric) $ r = 90\%$ and $ r = 99\%$, their number of nodes, and edges can be found in the table 1 (see additional pdf with tables). For a final version paper, experiments will be conducted on ogbn-arxiv if time allows.

The coarsening is performed with the adaptation of Loukas coarsening variation edges and preserving the first 400 eigenvectors. As a reference point for such heavy coarsening ratios, we add the "max acc possible", which is inherent to the coarsening: it corresponds to the optimal prediction over the super-nodes of the coarsened graph (all the nodes coarsened in a super nodes has the same prediction, optimally the majority label of this cluster). For the node classification task, the corresponding learning rate and weight decay are 0.1 and 0.0.

The node prediction results on the Reddit Dataset are reported in table 2. Our propagation matrix  ${S^\textup{MP}_c}$ achieves very good results with the SGC model, very close to the maximum accuracy possible on the given coarsening. Our propagation matrix is still competitive with the GCNconv model and achieved better results on the biggest coarsening ratio. 

The Message-Passing error for different coarsening propagation matrices is reported in table 3. Our propagation matrix for coarsened graphs achieved a better Message-Passing error, close to the RSA-constant computed in the coarsen graph. It is consistent with the fact the Message-Passing error is bounded by theorem 1 with our propagation matrix, and we thus expect lower values.

Thus, these additional experiments show better the effectiveness of our method on large graph for which coarsening as a preprocessing is crucial to save memory.


**B)** ***Multiple dimension node features***

The spectral guarantees and the corresponding RSA-constant $\epsilon_{Q , {L}, \mathcal{R}}$ depend of a *whole vector space* $\mathcal{R} \subset \mathbb{R}^{N}$. It therefore applies to multidimensional features by treating each coordinates independently, as seen in Theorem 2. We will clarify this in the final version.

Meta-review: In the context of GNNs with pooling, the authors propose computing the coarse graph from the full graph $A$ using the pseudoinverse of the coarsening matrix instead of its transpose in the formula $Q^TAQ$. This construction comes with theoretical guarantees: training a GNN on the coarsened graph is provably close to training it on the original graph. While the practical advantage of replacing the coarse graph $Q^TAQ$ by $Q^+AQ$ may be marginal, the theoretical analysis done by the authors is novel and brings new insights into the graph coarsening/pooling community.

The authors are asked to incorporate the reviewer comments for the camera ready version.
Decision: Accept (poster)