Graph Coarsening with Message-Passing Guarantees

Authors: antonin  joly
nicolas  keriven
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:18:45

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.

Main paper: 
 introduction: 
 In recent years, several applications in data science and machine learning have produced large-scale graph data [20, 5] . For instance, online social networks [13] or recommender systems [40] routinely produce graphs with millions of nodes or more. To handle such massive graphs, researchers have developed general-purpose graph reduction methods [4] , such as graph coarsening [32, 7] . It consists in producing a small graph from a large graph while retaining some of its key properties, and starts to play an increasingly prominent role in machine learning applications [7] .Graph Neural Networks. Machine Learning on graphs is now largely done by Graph Neural Networks (GNNs) [37, 27, 5] . GNNs are deep architectures on graph that rely on the Message-Passing paradigm [16] : at each layer, the representation H l i ∈ R d l of each node 1 ≤ i ≤ N , is updated by aggregating and transforming the representations of its neighbours at the previous layer {H l-1 j } j∈N (i) , where N (i) is the neighborhood of i. In most examples, this aggregation can be represented as a multiplication of the node representation matrix H l-1 ∈ R N ×d l-1 by a propagation matrix S ∈ R N ×N related to the graph structure, followed by a fully connected transformation. That is, starting with initial node features H 0 , the GNN Φ θ outputs after k layers:An interesting example is the Simplified Graph Convolution (SGC) model [42] , which consists in removing all the non-linearity (σ = id the identity function). Surprisingly, the authors of [42] have 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] .Graph coarsening and GNNs. In this paper, we consider graph coarsening as a preprocessing step to downstream tasks [11, 21] : 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 a 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 message-passing.There are many ways of measuring the quality of graph coarsening algorithms, following different criteria [10, 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-passing process at the core of GNNs, even for very simple signals. That is, simply performing message-passing on the coarsened graph using S c , 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 S MP c specific to coarsened graphs, which translate the RSA bound to message-passing guarantees: we show in Sec. 3.3 that training a GNN on the coarsened graph using S MP c is provably close to training it on the original graph. The proposed matrix S MP c can be computed for any given coarsening and is not specific to the coarsening algorithm used to produce it 1 , as long as it produces coarsenings with RSA guarantees. Interestingly, our proposed matrix S MP c is not symmetric in general even when S is, meaning that our guarantees are obtained by performing oriented message-passing on the coarsened graph, even when the original graph is 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 [28] ), which is quite different from generic message-passing.Related Work. Graph Coarsening originates from the multigrid-literature [36] , and is part of a family of methods commonly referred to as graph reduction, which includes graph sampling [19] , which consists in sampling nodes to extract a subgraph; graph sparsification [38, 1, 31] , that focuses on eliminating edges; or more recently graph distillation [22, 45, 23] , which extends some of these principles by authorizing additional informations inspired by dataset distillation [41] . Some of the first coarsening algorithms were linked to the graph clustering community, e.g. [9] which used recursively the Graclus algorithm [10] algorithm itself built on Metis [25] . Linear algebra technics such as the Kron reduction were also employed [32] [12] . In [32] , the author presents a 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] . 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 [29, 34] . Closer to this work, [11] proposes an optimization process to explicitely preserve the propagated features, however with no 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.Graph coarsening has been intertwined with GNNs in different ways. It can serve as graph pooling [44] 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 a 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 a pooling scheme, see also [17] . Graph pooling is often data-driven and fully differentiable, such as Diffpool [44] , SAGPool [30] , and DMoN [39] . Theoretical work on their ability to distinguish non homomorphic graphs after pooling have been conducted [3] . In return, GNNs can also be trained to produce data-driven coarsenings, e.g. GOREN [6] which proposes to learn new edge weights with a 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 [21] . Here few works derive theoretical guarantees for GNNs and message-passing, beyond the APPNP architecture examined in [21] . To our knowledge, the proposed S MP c is the first to yield such guarantees.Outline. We start with some preliminary material on graph coarsening and spectral preservation in Sec. 2. We then present our main contribution in Sec. 3: a new propagation matrix on coarsened graphs that leads to guarantees for message-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 a 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 at https://gitlab.inria.fr/anjoly/mp-guarantees-graph-coarsening, and proofs are deferred to App. A.Notations. For a matrix Q ∈ R n×N , its pseudo-inverse Q + ∈ R N ×n is obtained by replacing its nonzero singular values by their inverse and transposing. For a symmetric positive semi-definite (p.s.d.) matrix L ∈ R N ×N , we define L 1 2 by replacing its eigenvalues by their square roots, andL -1 2 = (L + ) 1 2 . For x ∈ R N we denote by ∥x∥ L = √x ⊤ Lx the Mahalanobis semi-norm associated to L. For a matrix P ∈ R N ×N , we denote by ∥P ∥ = max ∥x∥=1 ∥P x∥ the operator norm of P , and ∥P ∥ L = ∥L 1 2 P L -1 2 ∥. For a subspace R, we say that a matrix P is R-preserving if x ∈ R implies P x ∈ R. Finally, for a matrix X ∈ R N ×d , we denote its columns by X :,i , and define ∥X∥ :,L = i ∥X :,i ∥ L . 
background on graph coarsening: 
 We mostly adopt the framework of Loukas [32] , with some generalizations. A graph G with N nodes is described by its weighted adjacency matrix A ∈ R N ×N . We denote by L ∈ R N ×N a notion of symmetric p.s.d. Laplacian of the graph: classical choices include the combinatorial Laplacian L = D -A with D = D(A) := diag(A1 n ) the diagonal matrix of the degrees, or the symmetric normalized Laplacian L = I N -D -1 2 AD -1 2 . We denote by λ max , λ min respectively the largest and smallest non-zero eigenvalue of L.Coarsening matrix. A coarsening algorithm takes a graph G with N nodes, and produces a coarsened graph G c with n < N nodes. Intuitively, nodes in G are grouped in "super-nodes" in G c (Fig. 1 ), with some weights to outline their relative importance. This mapping can be represented viaa coarsening matrix Q ∈ R n×N : Q = Q ki > 0 if the i-th node of G is mapped to the k-th super-node of G c Q ki = 0 otherwiseThe lifting matrix is the pseudo-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 as r : r = 1 -n 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 a unique node in G c , that is, if Q has exactly one non-zero value per column. Moreover, it is surjective if at least one node is mapped to each super node: i Q ki > 0 for all k. In this case, QQ ⊤ is invertible diagonal andQ + = Q ⊤ (QQ ⊤ ) -1. Moreover, such a coarsening is said to be uniform when mapping weights are constant for each super-nodes and sum to one: Q ki = 1/n k for all Q ki > 0, where n k is the number of nodes mapped to the super-node k. In this case the lifting matrix is particularly simple: Q + ∈ {0, 1} N ×n (Fig. 1d ). For simplicity, following the majority of the literature [32] , in this paper we consider only well-mapped surjective coarsenings (but not necessarily uniform). Remark 1. Non-well-mapped coarsenings may appear in the literature, e.g. when learning the matrix Q via a gradient-based optimization algorithm such as Diffpool [44] . However, these methods often include regularization penalties to favor well-mapped coarsenings.Restricted Spectral Approximation. A large part of the graph coarsening literature measures the quality of a 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 ∥ • ∥ L , which can be interpreted as a measure of the smoothness of a signal across the graph edges. Given a signal x ∈ R N over the nodes of G, we define the coarsened signal x c ∈ R n and the re-lifted signal x ∈ R N byEQUATIONwhere Π = Q + Q. Loukas [32] then introduces the notion of Restricted Spectral Approximation (RSA) of a coarsening algorithm, which measures how much the projection Π is close to the identity for a class of signals. Since Π is at most of rank n < N , this cannot be true for all signals, but only for a restricted subspace R ⊂ R N . With this in mind, the RSA constant is defined as follows.Definition 1 (Restricted Spectral Approximation constant). Consider a subspace R ⊂ R N , a Laplacian L, a coarsening matrix Q and its corresponding projection operatorEQUATIONIn other words, the RSA constant measures how much signals in R are preserved by the coarseninglifting operation, with respect to the norm ∥ • ∥ L . Given some R and Laplacian L, the goal of a coarsening algorithm is then to produce a coarsening Q with the smallest RSA constant possible.While the "best" coarsening arg min Q ϵ L,Q,R is generally computationally unreachable, there are many possible heuristic algorithms, often based on greedy merging of nodes. In App. B.1, 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 L ordered by increasing eigenvalue: intuitively, coarsening the graph and merging nodes is more likely to preserve the low-frequencies of the Laplacian.While ϵ L,Q,R ≪ 1 is required to obtain meaningful guarantees, we remark that ϵ L,Q,R is not necessarily finite. Indeed, as ∥ • ∥ L may only be a semi-norm, its unit ball is not necessarily compact.It is nevertheless finite in the following case.Proposition 1. When Π is ker(L)-preserving, it holds that ϵ L,Q,R ≤ λ max /λ min .Hence, some examples where ϵ L,Q,R is finite include: Example 1. For uniform coarsenings with L = D -A and connected graph G, ker(L) is the constant vector2 , and Π is ker(L)-preserving. This is the case examined by [32] . Example 2. For positive definite "Laplacians", ker(L) = {0}. This is a deceptively simple solution for which ∥ • ∥ L is a true norm. This can be obtained e.g. with L = δI N + L for any p.s.d. Laplacian L and small constant δ > 0. This leaves its eigenvectors unchanged and add δ to its eigenvalues, and therefore does not alter the fundamental structure of the coarsening problem.Given the adjacency matrix A ∈ R N ×N of G, there are several possibilities to define an adjacency matrix A c for the graph G c [21, 29] . A natural choice that we make in this paper isEQUATIONIn the case of a uniform coarsening, (A c ) kℓ equals the sum of edge weights for all edges in the original graph between all nodes mapped to the super-node k and all nodes mapped to ℓ. Moreover, we have the following property, derived from [32] . Proposition 2. Assume that the coarsening Q is uniform and consider combinatorial Laplacians1 2 1 1 2 1/2 1/3 2/3 2 1/2 1 1/2 2/3 (a) (b) (c) Q =   1 2 1 2 0 0 0 0 0 0 1 3 1 3 1 3 0 0 0 0 0 0 1   , Q + =        1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1        , Π = Q + Q =        1 2 1 2 0 0 0 0 1 2 1 2 0 0 0 0 0 0 1 3 1 3 1 3 0 0 0 1 3 1 3 1 3 0 0 0 1 3 1 3 1 3 0 0 0 0 0 0 1        (d)EQUATIONThis draws a link between the RSA and a notion of near-isometric embedding for vectors in R. Note that the proposition above is not necessarily true when considering normalized Laplacians, or non uniform coarsenings. In the next section, we propose a new propagation matrix on coarsened graphs and draw a link between the RSA constant ϵ L,Q,R and message-passing guarantees.3 Message-Passing on coarsened graphsIn 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 ϵ L,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 on coarsened graphs. 
a new propagation matrix on coarsened graph: 
 Given a graph G with a propagation matrix S and a coarsened graph G c with a coarsening matrix Q, our goal is to define a propagation matrix S MP c ∈ R n×n such that one round of message-passing on the coarsened signal x c followed by lifting is close to performing message-passing in the original graph:Q + S MP c x c ≈ Sx.Assuming that the propagation matrix S = f S (A) is the output of a function f S of the graph's adjacency matrix, the most natural choice, often adopted in the literature [11] , is therefore to simply take S c = f S (A c ), where A c 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 caseQ + S c x c = Q + (Q + ) ⊤ AΠx, which involves the quite unnatural term Q + (Q + ) ⊤ .For other choices of normalized S, the situation is even less clear. Some authors propose different variant of S c 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:EQUATION)This expression is conceptually simple: it often amounts to some reweighting. For instance, when S = A and in the case of uniform coarsening, we have (S MP c ) kℓ = (A c ) kℓ /n k (Fig. 1c ). Despite this simplicity, we will see that under some mild hypotheses this choice indeed leads to preservation guarantees of message-passing 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 c defined in (4), the proposed matrix S MP c is generally asymmetric, even when S is symmetric. This means that our guarantees are obtained by performing directed messagepassing on the coarsened graph, even when the original message-passing procedure was undirected. Conceptually, this is an important departure from previous works. However S MP c becomes "more" symmetric when Q + and Q T becomes more similar. This is 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 between Q and Q + is more pronounced when supernodes are of very different sizes,which may happen for highly irregular graphs.In this section, we show how the proposed propagation matrix (6) allows to transfer the spectral approximation guarantees to message-passing guarantees, under some hypotheses. First, we must make some technical assumptions relating to the kernel of the Laplacian. Assumption 1. Assume that Π and S are both ker(L)-preserving.Moreover, since spectral approximation pertains to a 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 1 and 2, the projection Π is ker(L)-preserving. Moreover, R is often chosen to be the subspace spanned by the low-frequency eigenvectors of L and in this case, all matrices of the form S = αI N + βL for some constant α, β are both ker(L)-preserving and R-preserving. Hence, for instance, a primary example in practice is to choose GCNconv [27] withS = D( Â) -1 2 ÂD( Â) -1 2 with Â = A + I N ,and to compute a coarsening with a good RSA constant for the "Laplacian" L = (1 + δ)I N -S with small δ > 0 and R spanned by eigenvectors of L. In this case, Assumptions 1 and 2 are satisfied. This is the implementation we choose in our experiments.We now state the main result of this section. Theorem 1. Define S MP c as (6) . Under Assumption 1 and 2, for all x ∈ R, ∥Sx -EQUATIONwhere C S := ∥S∥ L and C Π := ∥ΠS∥ L .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 S MP c , the lifted signal is precisely Q + S MP c x c = ΠSΠx. Then, bounding the error incurred by Π 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 ϵ L,Q,R directly translates to an error bound between Sx and Q + S MP c x c . 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. 1.Multiplicative constants. In full generality, for any matrix M we have ∥M ∥ L ≤ ∥M ∥ λ max /λ min . Moreover, when M and L commute, we have ∥M ∥ L ≤ ∥M ∥. As mentioned before, choosing S = αI N + βL for some constants α, β is a primary example to satisfy our assumptions. In this case C S = ∥S∥ L ≤ ∥S∥. Then, if S is properly normalized, e.g. for the GCNconv [27] example outlined above, we have ∥S∥ ≤ 1. For combinatorial Laplacian L = D -A however, we obtain ∥S∥ ≤ |α| + |β|N . We observed in our experiments that the combinatorial Laplacian generally yields poor results for GNNs.For C Π , in full generality we only have C Π ≤ C S ∥Π∥ L ≤ C S λmax λmin , since Π is an orthogonal projector. However, in practice we generally observe that the exact value C Π = ∥ΠS∥ L is far better than this ratio of eigenvalues (e.g. we observe a ratio of roughly C Π ≈ (1/10) • λ max /λ min in our experiments). Future work may examine more precise bounds in different contexts.In this section, we instantiate our message-passing guarantees to GNN training on coarsened graph, with SGC as a primary example. To fix ideas, we consider a single large graph G, and a node-level task such as node classification or regression. Given some node features X ∈ R N ×d , the goal is to minimize a loss function J : R N → R + on the output of a GNN Φ θ (X, S) ∈ R N (assumed unidimensional for simplicity) with respect to the parameter θ:EQUATION)where Θ is a set of parameters that we assume bounded. For instance, J can be the cross-entropy between the output of the GNN and some labels on 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 + E)D), where T 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 G c , which can be done by minimizing instead 3 :EQUATIONwhere X c = 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-propagated to compute the gradient of θ. The computational complexity then becomes O(T (n + e)D + T N ), where e ≤ E is the number of nonzeros in S MP c , and the term T N 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 ∥ • ∥ L , we must handle it with the following assumption. Assumption 3. We assume that there is a constantEQUATIONFor most loss functions, it is easy to show that |J(x) -J(x ′ )| ≲ ∥x -x ′ ∥, and whenL is positive definite (Example 2) then ∥ • ∥ ≤ 1 √ λmin ∥ • ∥ L .Otherwise, one must handle the kernel of L, which may be done on a case-by-case basis of for an appropriate choice of J.The second assumption relates to the activation function. It is here mostly for technical completeness, as we do not have examples where it is satisfied beyond the identity σ = id, which corresponds to the SGC architecture [42] often used in theoretical analyses [46, 26] . Assumption 4. We assume that: i) σ is R-preserving, that is, for all x ∈ R, we have σ(x) ∈ R. We discuss this constraint below.ii) ∥σ(x) -σ(x ′ )∥ L ≤ C σ ∥x -x ′ ∥ L . Note that most activations are 1-Lipschitz w.r.t. the Euclidean norm, so this is satisfied when L is positive-definite with C σ = λ max /λ min .iii) σ andQ + commute: σ(Q + y) = Q + σ(y). This is satisfied for all uniform coarsenings, or when σ is 1-positively homogeneous: σ(λx) = λσ(x) for nonnegative λ (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 σ to preserve smooth signal. For now, the only example for which we can guarantee that Assumption 4 is satisfied is when σ = id and the GNN is linear, which corresponds to the SGC architecture [42] . As is the case with many such analyses of GNNs, non-linear activations are a 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 harmonics for dot-product graphs [2] . In this case, it may be possible to explicitely prove that Assumption 4 holds, but this is out-of-scope of this paper.Our result on GNNs is the following.Theorem 2. Under Assumptions 1-4: for all node features X ∈ R N ×d such that X :,i ∈ R, denoting by θ ⋆ = arg min θ∈Θ R(θ) and θ c = arg min θ∈Θ R c (θ), we haveEQUATIONwithC = 2C J C k σ C Θ (C S + C Π ) k l=1 Ck-l Π C l-1 Swhere CΠ := ∥ΠSΠ∥ L and C Θ is a constant that depends on the parameter set Θ.The proof of Thm. 2 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 :,i 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 S MP c on the coarsened graph by minimizing (9) yields a parameter θ c whose excess loss compared to the optimal θ ⋆ is bounded by the RSA constant. Hence, spectral approximation properties of the coarsening directly translates to guarantees on GNN training. The multiplicative constants C S , C Π have been discussed in the previous section, and the same remarks apply to CΠ . 
experiments: 
 Setup. We choose the propagation matrix from GCNconv [27] , that is,S = f S (A) = D( Â) -1 2 ÂD( Â) -1 2 with Â = A+I N .As detailed in the previous section, we take L = (1+δ)I N -S with δ = 0.001 and R as the K first eigenvectors of L (K = N/10 in our experiments), ensuring that Assumptions 1 and 2 are satisfied. In our experiments, we observed that the combinatorial Laplacian L = D -A gives quite poor results, as it corresponds to unusual propagation matrices S = αI N + βL, and the constant C S = ∥S∥ L is very large. Hence our focus on the normalized case.On coarsened graphs, we compare five propagation matrices: [21] , where C is the diagonal matrix of the n k and D′ the corresponding degrees. This yields theoretical guarantees for APPNP when S is GCNconv;• S MP c = QSQ + , our proposed matrix • S c = f S (A c ), the naive choice • S diag c = D′ -1/2 (A c + C) D′ -1/2 , proposed in• S dif f c = QSQ ⊤ ,which is roughly inspired by Diffpool [44] ;• S sym c = (Q + ) ⊤ SQ + ,which is the lifting employed to compute A c (4). Coarsening algorithm. Recall that the proposed S MP c can be computed for any coarsening, and that the corresponding theoretical guarantees depend on the RSA constant ϵ L,Q,R . In our experiments, we adapt the algorithm from [32] to coarsen the graphs. It takes as input the graph G and the coarsening ratio desired r and output the propagation matrix S MP c and the coarsening matrix Q used for lifting. It is a greedy algorithm which successively merges edges by minimizing a certain cost. While originally designed for the combinatorial Laplacian, we simply adapt the cost to any Laplacian L, see App. B.1. Note however that some mathematical justifications for this approach in [32] are no longer valid for normalized Laplacian, but we find in practice that it produces good RSA constants.S M P c S dif f c S sym c S c S diag c C L,Q,RA 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 [15] and one larger graph with Reddit [18] in the following experiments. The design of more scalable coarsening algorithms with RSA guarantees is an important path for future work, but out-of-scope of this paper.To evaluate the effectiveness of the proposed propagation matrix, we first illustrate the theoretical message passing preservation guarantees (Thm. 1 and 2) on synthetic graphs, taken as random geometric graph, built by sampling 1000 nodes with coordinates in [0, 1] 2 and connecting them if their distance is under a given threshold (details in App. B.3). For each choice of propagation matrix and different coarsening ratio, we compute numerically ∥S k x -Q + (S MP c ) k x c ∥ L for various signals x ∈ R. We perform N p = 6 message-passing steps to enhance the difference between propagation matrices. We evaluate and plot the upper bound defined by ϵL,Q,R (C S + C Π ) k l=1 Ck-l Π C l-1 S(seen in the proof of Theorem 2 in App. A.3) in Fig. 2 . We observe that our propagation matrix incurs a significantly lower error compared to other choices, and that as expected, this error is correlated to ϵ L,Q,R , 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, we restrict them to their largest connected component 4 , 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 to compute the cross-entropy loss, which is then back-propagated to optimize the parameters θ (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 to 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 in a 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 N p = 6 and GCNconv [27] with N p = 2 on four different coarsening ratio: r ∈ {0.3, 0.5, 0.7} where N p is the number of propagation. Each classification results is averaged on 10 random training.Results are reported in Table 1 and Table 2 . We observe that the proposed propagation matrix S MP c yields better results and is more stable, especially for high coarsening ratio. The benefits are more evident when applied to the SGC architecture [42] , for which Assumption 4 of Thm. 2 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-parameters for each model and each dataset can be found in appendix B.5. We performed experiments on the Reddit Dataset [18] , which is approximately 100 times bigger than Cora or Citeseer. The Message-Passing error for different coarsening propagation matrices is reported in Table 3 with the node prediction results on two coarsening ratio r = 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 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 of our method on large graphs for which coarsening as a preprocessing step is crucial: indeed, on most small-scale machines with single GPU, the Reddit dataset is too large to fit in memory and requires adapted strategies.  
conclusion: 
 In this paper, we investigated the interactions between graph coarsening and Message-Passing 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-passing on the original graph. We thus proposed a new message-passing matrix specific to coarsened graphs, which naturally translates spectral preservation to 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 to GNN, and in particular to the SGC model, such that training on the coarsened graph is provably close to training on the original one.There are many outlooks to this work. Concerning the coarsening procedure itself, which was not the focus of this paper, new coarsening algorithms could emerge from our theory, e.g. by instantiating an 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, a crucial point is the interaction between non-linear activation functions and the low-frequency vectors in a 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 on this complex phenomenon, which we believe to be a major path for future work. 
 
 Appendix: We start by a small useful lemma. Lemma 1. For all ker(L)-preserving matrices M , we have ∥M x∥ L ≤ ∥M ∥ L ∥x∥ L .Proof. Take the orthogonal decomposition x = u + v where u ∈ ker(L) and v ∈ ker(L) ⊥ . Then, since ∥x∥L = ∥v∥ L , L -1 2 L 1 2 v = v and ∥M u∥ L = 0, ∥M x∥ L ≤ ∥M v∥ L = ∥L 1 2 M L -1 2 L 1 2 v∥ ≤ ∥M ∥ L ∥v∥ L A.1 Proof of Proposition 2Proof. The fact that L c = (Q + + in this particular case is done by direct computation. It results that ∥x c ∥ Lc = ∥L 1 2 Πx∥ and| ∥x∥ L -∥x c ∥ Lc | ≤ ∥L 1 2 x -L 1 2 Πx∥ = ∥x -Πx∥ L ≤ ϵ L,Q,R ∥x∥ L by definition of ϵ L,Q,R .Proof. Since x ∈ R and S is R-preserving, we have∥Π ⊥ x∥ L ≤ ϵ L,Q,R ∥x∥ Lwhere Π ⊥ = I N -Π, and similarly for Sx. Moreover, under Assumption 1, both Π and S are ker(L)-preserving, such that ∥ΠSx∥ L ≤ ∥ΠS∥ L ∥x∥ L for all x. Then∥Sx -Q + S MP c x c ∥ L = ∥Sx -ΠSΠx∥ L = ∥Sx -ΠSx + ΠSx -ΠSΠx∥ L = ∥Π ⊥ Sx + ΠSΠ ⊥ x∥ L ≤ ∥Π ⊥ Sx∥ L + ∥ΠSΠ ⊥ x∥ L ≤ ϵ L,Q,R ∥Sx∥ L + ∥ΠS∥ L ∥Π ⊥ x∥ L ≤ ϵ L,Q,R ∥Sx∥ L + ϵ L,Q,R ∥ΠS∥ L ∥x∥ L = ϵ L,Q,R ∥x∥ L (C S + C Π ) A.3 Proof of Theorem 2Recall that the GNN is such that H 0 = X, andH l = σ(SH l-1 θ l ) ∈ R N ×d ℓ , Φ θ (X, S) = H k ∈ R NSimilarly, for the GNN on coarsened graph we denote by H 0 c = X c and its layersH l c = σ(S MP c H l-1 c θ l ) ∈ R n×d ℓ , Φ θ (X c , S MP c ) = H k c ∈ R NFor some set of parameters θ of a GNN, we defineC θ,l = sup i j |θ l ij |, Cθ,l = l p=1 C θ,pWe start with a small lemma. Lemma 2. DefineEQUATIONThen we haveEQUATIONProof.From assumption 4 we have ∥σ(x)∥ L ≤ C σ ∥x∥ L . Then, since S is ker(L)-preserving from Assumption 1, by Lemma1 i ∥H l :,i ∥ L = i ∥σ(SH l-1 θ l :,i )∥ L ≤ C σ i ∥SH l-1 θ l :,i ∥ L ≤ C σ (sup j i |θ l ji |) j ∥SH l-1 :,j ∥ L ≤ C σ C θ,l C S B l-1Since B 0 = ∥X∥ :,L , we obtain the result Proof. We start with classical risk bounding in machine learningJ(Φ θc (X, S)) -J(Φ θ ⋆ (X, S)) = J(Φ θc (X, S)) -J(Q + Φ θc (X c , S MP c )) + J(Q + Φ θc (X c , S MP c )) -J(Q + Φ θ ⋆ (X c , S MP c )) + J(Q + Φ θ ⋆ (X c , S MP c )) -J(Φ θ ⋆ (X, S)) ≤ 2 sup θ∈Θ |J(Φ θ (X, S)) -J(Q + Φ θ (X c , S MP c ))| since θ c minimizes J(Q + Φ θ (X c , S MP c )). For all θ, by Assumption 3, we haveEQUATIONWe will prove a recurrence bound onE l := i ∥H l :,i -Q + (H l c ) :,i ∥ L From Assumption 4, E l = i ∥σ(SH l-1 (θ l ) :,i ) -Q + σ(S MP c H l-1 c (θ l ) :,i )∥ L = i ∥σ(SH l-1 (θ l ) :,i ) -σ(Q + S MP c H l-1 c (θ l ) :,i )∥ L ≤ C σ i ∥SH l-1 (θ l ) :,i -Q + S MP c H l-1 c (θ l ) :,i ∥ L ≤ C σ j i |(θ l ) ji | ∥SH l-1 :,j -Q + S MP c (H l-1 c ) :,j ∥ LWe then write∥SH l-1 :,j -Q + S MP c (H l-1 c ) :,j ∥ L ≤ ∥SH l-1 :,j -Q + S MP c QH l-1 :,j ∥ L + ∥Q + S MP c QH l-1 :,j -Q + S MP c (H l-1 c ) :,j ∥ LThen note that, since both S and σ are R-preserving, for all l, i we have that (H l ) :,i ∈ R. We can thus apply Theorem 1 to the first term:∥SH l-1 :,j -Q + S MP c QH l-1 :,j ∥ L ≤ ϵ L,Q,R (C S + C Π )∥H l-1 :,j ∥ LThe second term is 0 when l = 1 since H 0 c = QH 0 . Otherwise, using QQ + = I n , and since under Assumption 1 both S and Π are ker(L)-preserving, applying Lemma 1:∥Q + S MP c QH l-1 :,j -Q + S MP c (H l-1 c ) :,j ∥ L = ∥Q + S MP c Q(H l-1 :,j -Q + (H l-1 c ) :,j )∥ L = ∥ΠSΠ(H l-1 :,j -Q + (H l-1 c ) :,j )∥ L ≤ ∥ΠSΠ∥ L ∥H l-1 :,j -Q + (H l-1 c ) :,j ∥ LAt the end of the day, we obtainE l ≤ C σ C θ,l (ϵ L,Q,R (C S + C Π )B l-1 + CΠ E l-1 ) ≤ C l σ Cθ,l C l-1 S (C S + C Π )ϵ L,Q,R ∥X∥ :,L + C σ C θ,l CΠ E l-1using Lemma 2, andE 1 ≤ ϵ L,Q,R C σ C θ,1 (C S + C Π )∥X∥ :,L .We recognize a recursion of the formEQUATION)This concludes the proof with C Θ = max θ∈Θ Cθ,k .You can find below the pseudo-code of Loukas algorithm. This algorithm works by greedy selection of contraction sets (see below) according to 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 = f L (A), and to update the adjacency matrix according to (4) at 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 c at each iteration, as we find that it produces better results. The output of the algorithm is the resulting coarsening Q, as well as S MP c = QSQ + for our application.Require: Adjacency matrix A, Laplacian L = f L (A), propagation matrix S, a coarsening ratio r , preserved space R, maximum number of nodes merged at one coarsening step : n e 1: n obj ← int(N -N × r) the number of nodes wanted at the end of the algorithm.2: compute cost matrix B 0 ← V V T L -1/2 with V an orthonormal basis of R 3: Q ← I N 4: while n ≥ n obj do 5:Make one coarsening STEP l 6:Create candidate contraction sets.For each contraction C, compute cost(C, B l-1 , L l-1 ) =∥Π C B l-1 (B T l-1 L l-1 B l-1 ) -1/2 ∥ L C |C|-1 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 -n obj , n e ) 10:Compute Q l , Q + l , uniform intermediary coarsening with contraction sets selected 11:B l ← Q l B l-1 12: Q ← Q l Q 13: A l ← (Q + l ) ⊤ A l-1 Q + l -diag((Q + l ) ⊤ A l-1 Q + l )1 n ) 14: L l-1 = f L (A l-1 ) 15:n ← min(n -n obj , n e ) 16: end while17: IF uniform coarsening THEN Q ← row-normalize(Q l Q) 18: Compute S MP c = QSQ + 19: return Q, S MP cThe terms Π C and L C 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 a parameter n e to limit the number of nodes contracted at each coarsening step. In one coarsening step, when a contraction set C is selected, we merge |C| nodes. In practice Loukas proposed in its implementation to force n e = ∞ and coarsen the graph in one single iteration. We observed empirically better results by diminishing n e and combining it with enforcing the uniform coarsening (Appendix B.4).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 n e to control the greedy aspect of this algorithm.Uniform Coarsening At each coarsening step, in Loukas algorithm Q l is uniform by construction. Nonetheless the product of uniform coarsening is not necessarily an uniform coarsening. Then, we propose an option to force the uniform distribution in the super-nodes in the Loukas algorithm by normalize the non zero values of each line of the final coarsening matrix Q. We observe that uniform coarsening gives better results for ϵ L,Q,R , and works better for our message passing guarantees. See Appendix B.4.The pseudocode of our training procedure is detailed in Algo. 2.Require: Adjacency A, node features X, desired propagation matrix S, preserved space R, Laplacian L, a coarsening ratio r1: Q, S MP c ← Coarsening-algorithm(A, L, S, r, R) 2: X c ← QX 3: Initialize model (SGC or GCNconv) 4: for N epochs iterations do 5: compute coarsened prediction Φ θ (S MP c , X c ) 6:uplift the predictions :Q + Φ θ (S MP c , X c ) 7:compute the cross entropy lossJ(Q + Φ θ (S MP c , X c )) 8:Backpropagate the gradient 9:Update θ 10: end for Note that it is 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 to 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.Synthetic Dataset Random geometric graph is built by sampling nodes with coordinates in [0, 1] 2 and connecting them if their distance is under a given threshold. For the experiment on illustrating the message passing preservation guarantees, we sample 1000 nodes with a threshold of 0.05 (fig 3 ). Real World datasets We restrict the well known Cora and Citeseer to their principal connected component(PCC) as it more compatible with coarsening as preprocessing. Indeed, the loukas Figure 3 : Example of a random Geometric graph algorithm tend to 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 as it is not 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 5 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 4a ) to put the focus on low coarsening ratio and on the upper bound. We use the linear scale (fig 4b ) to compare more precisely our propagation matrix with S diag c and S c for higher coarsening ratio. Uniform coarsening We observe that forcing uniform coarsening gives better ϵ L,Q,R and thus better message passing guarantees . It is shown in the figure 5 for n e = 5N/100 with N the number of Nodes of the graph (1000 here). Bounding n e . For high coarsening ratio, we observe limits of the variation edges defined as Loukas with n e → ∞ as it gives bigger ϵ L,Q,R and thus worse curve for our propagation matrix in the coarsened graph (fig 6 ).For all experiments, we preserve K eigenvectors of the normalized Laplacian defined as L = I N (1 + δ) -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 e = 5%N for SGC Cora, SGC Citeseer and GCN citeseer and n e → ∞ for GCN Cora (variation edges as defined by Loukas).For SGC cora and SGC Citeseer we make 6 propagations as preprocessing for the features. For GCN Cora and Citeseer we use 2 convolationnal layer with a hidden dimension of 16. For all experiments we use an Adam Optimizer wit a learning rate of 0.05 and a weight decay of 0.01.For the experiment on Reddit Dataset, we preserve K eigenvectors of the normalized Laplacian defined as L = I N (1 + δ) -S with δ = 0.001 and K = 400 eigenvectors to be computationally efficient (10%N being too big). We apply our adapted version of Loukas coarsening algorithm with Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: This is a 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 contributions made in the paper and important assumptions and limitations. A No or 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.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: This is a 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 are not discussed in the paper. • The authors are encouraged to create a 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, noiseless 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., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a 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 to 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] 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 or 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 a 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 as supplementary material, and can be run on any computer. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a 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 a large language model), releasing of a 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 a new algorithm, the paper should make it clear how to reproduce that algorithm. ii) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. iii) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or 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 in some way (e.g., to registered users), but it should be possible for other researchers to 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: [ 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).x) Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a mostly theoretical paper. We do not anticipate significant societal impact as a direct result of our work. Future algorithmic work on 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 no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 to particular applications, let alone deployments. However, if there is a 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, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).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, or scraped datasets)?Answer: [NA] Justification: This paper does not include such model.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to usage guidelines or restrictions to 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.Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are 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 a 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 are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 is not available online, the authors are encouraged to reach out to the asset's creators.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.• Researchers should communicate the details of the dataset/code/model as part of their submissions 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. • We recognize that the procedures for this may vary significantly between institutions and locations, and we 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 applicable), such as the institution conducting the review.Note however that S MP c must be computed during the coarsening process and included as an output of the coarsening algorithm, before eventually discarding the original graph.Note that this would also work with several connected components, if no nodes from different components are mapped to the same super-node.Note 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 on the coarsened graph[21], but this is not considered here. See App. B.2 for more discussion.hence the slight difference with other reported results on these datasets 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. Do linear GNNs [3] satisfy Assumption 4?
3. 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?
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.
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].
6. How to effectively compute $Q^+$ in practice? The complexity analysis is missing.


[1] Featured Graph Coarsening with Similarity Guarantees.

[2] Graph Distillation with Eigenbasis Matching.

[3] How Powerful are Spectral Graph Neural Networks?

[4] Graph Reduction with Spectral and Cut Guarantees.

[5] eural Message Passing for Quantum Chemistry. 

[6] Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training
questions: questions: See Weaknesses.
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- 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.
- 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. 
- 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.
- 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.
- 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". 
- (minor) Ker(L) is not defined I think.
questions: questions: I do not have questions besides the concerns above.
limitations: limitations: See what I wrote in weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: How effective is this work on datasets such as Arxiv and Products?
limitations: limitations: The authors adequately addressed the limitation and potential negative societal impact  of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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?

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?
limitations: limitations: The theoretical analysis is limited to the linear networks and the experiments are limited to two small datasets.
paper_summary: paper_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.
strength_weakness: strength_weakness: W1: The overall structure is somewhat loose.

W2: It would be nice to see more intuitive explanation of $S^{MP}_c$, e.g., when $S$ is symmetrically normalized adjacency matrix from GCN.

W3: The experiments are conducted only on small datasets, which I understand since the authors put more effort on the theoretical analysis.
questions: 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?

Q2: It would be nice to see more experiments on larger datasets, e.g., ogbn-arxiv.

Typo: Line 212, $\hat{A}=A+I$.
limitations: limitations: N/A

Comments: comment: I further improved my score, trusting the authors to implement all the modifications they promised to me and the other reviewers.
Thank you for your answer. Indeed, your are correct in pointing out that the *coarsening* process in itself is still an active area of research and that classical spectral-based coarsening must be improved for certain datasets. Our work, however, studies message-passing on coarsened graphs, which is downstream from the coarsening process. But we hope that it might serve as pointers to improve the coarsening itself in future work.
Thank you for your answer. We are confident at this point that it will be possible for us to extend the experimental section with other large datasets beyond Reddit.
Thank you for the pointers and reference, that is indeed an important point that we will emphasize in the final version.
The point you made in your answer about the propagation matrix, i.e., that $Q^{+}$ and $Q^\top$ become more similar as $Q$ induces a balanced partition makes sense but it is something I missed when reviewing the paper. Indeed, I strongly encourage the authors to stress this point. 

There is a class of graph pooling methods that encourage the size of the supernodes to be balanced (see for example the dense pooling methods from this recent survey paper [1]). In this case, it would make less sense to use $Q^{+}$. Again, this seems an important point worth commenting on.

[1] Wang, Pengyun, et al. "A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and Generalizability." arXiv preprint arXiv:2406.09031 (2024).
Thanks for the detailed response and most of my concerns have been addressed. Therefore, I raise my score to support the acceptance of this paper.
Thank you for your careful review and for raising your score.

A few comments on the points you mention.

**On pooling**: we agree that the vocabulary in the community might overlap a bit at this point. We'll try to clarify as much as we can our meaning in the final version (that is, our focus on spectral-based unsupervised coarsening), and add the references you mention. Thank you for providing them.

**On propagation matrix**: it is true that the ``more orthogonal'' $Q$ is, the less the difference between $Q^+$ and $Q^T$. More generally, the difference between the two is more pronounced when supernodes are of very different sizes, which may happen for highly irregular graphs (eg, for uniform coarsenings, when all the supernodes are exactly of the same size, there is only a multiplicative constant between $Q^+$ and $Q^T$). We will explain this better in the final version, as well as outline the datasets where this happens more frequently.
Thank you for your answer. We attempt to answer your remaining questions below.

1. *Why is the selected coarsening ratio significantly larger than existing works? How to select the coarsening ratio in experiments?*

We select three coarsening ratios that are used in Loukas work [1] to illustrate our theoretical results. Following your suggestion, the final version of the paper will include more coarsening ratios (please note that in the Dickens [4] work mentioned earlier in your questions, the coarsening ratio is defined as $1-r$ compared to Loukas and ours). In practice, selecting the ratio really depends on the use-case, whether the aim of the user is to save storage memory, train a GNN, and so on. For instance, compared to smaller datasets, we had to select a very high coarsening ratio for Reddit in order to train a GNN for it on a laptop. Of course, the higher the ratio, the ``worse'' the results compared to the original graph.

2. *What is the motivation for graph coarsening under the linearity assumption?*

We 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 [2,3] 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, in order to treat more general GNNs on coarsened graphs.

3. *The answer for Concern 4 is confusing. If spectral guarantees lead to message-passing guarantees, then what is the contribution of this paper? A method with spectral guarantees is enough in practice, as the method also ensures message-passing guarantees.*

Spectral guarantees and message-passing are of different nature, and concern different objects. Spectral guarantees are inherent to a graph coarsening, and refer to the fact that low-frequencies of the graphs are preserved by coarsening (aka a low $\epsilon$ constant). Most algorithms, such as Loukas' that we employ in the experiments, aim at producing such spectral guarantees. Message-passing guarantees concerns the choice of a *propagation matrix*. Our work consist in showing that, even assuming that the coarsening exhibit spectral guarantees, message-passing guarantees are *not* automatic, and generally not satisfied for naive choices of propagation matrices. We then propose a new propagation matrix that yields such message-passing guarantees, when the coarsening has spectral guarantees (that is, we bound the message-passing error of this propagation matrix by $\epsilon$, hence the fact that spectral guarantees ``lead to'' message-passing guarantees *for this new propagation matrix only*). We will clarify this in the final version.

4. *The concept of message-passing guarantees is still confusing. Given your answer, convolution guarantees may be more accurate than message-passing guarantees, as the convolution operation usually does not consider the edge features.*

Thank you for your suggestion. We will not change the title at this point, but will make this point of vocabulary clear in the final version.

[1] Graph Reduction with Spectral and Cut Guarantees, Andreas Loukas, JMLR 2019

[2] Zhu et al. Graph Neural Networks with Heterophily. AAAI.

[3] Keriven. Not too little, not too much: a theoretical analysis of graph (over)smoothing. NeurIPS.

[4] Dickens et al. Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training
Thanks for your rebuttal. The rebuttal has addressed Concerns 2 and 6. Unfortunately, my concerns about Concerns 1,3,4,5 remain unaddressed. The suggestions and questions are as follows.

1. **Why is the selected coarsening ratio significantly larger than existing works?** How to select the coarsening ratio in experiments?
2. **What is the motivation** for graph coarsening under the linearity assumption?
3. The answer for Concern 4 is confusing. If spectral guarantees lead to message-passing guarantees, then what is the contribution of this paper? A method with spectral guarantees is enough in practice, as the method also ensures message-passing guarantees.
4. The concept of message-passing guarantees is still confusing. Given your answer, convolution guarantees may be more accurate than message-passing guarantees, as the convolution operation usually does not consider the edge features.
Thanks for the response. I believe that the volume of experiments in this paper still has not reached my expectations. However, considering that the paper addresses a very important issue in graph coarsening, I have raised the score to 7 and encourage the authors to continue adding more experiments.
Thank you for the detailed answers.

I do not completely agree with the distinction proposed by the authors between graph pooling and graph coarsening. Graph pooling can also be a pre-processing step that reduces the size of the graph and, thus, the memory consumption. See for example Graclus [1], originally introduced by [2] as a pooling scheme, and other non-trainable pooling operators described in [3]. In addition, there are some recent work that showed some guarantees of pooling operators in terms of their capability of keeping two non-homomorphic graphs distinguishable after pooling [4]. I suggest the authors to clarify this connection... or to find a stronger argument for why pooling and coarsening should be different things.

I still believe that the practical contribution seems a rather small detail that would arguably make a small difference using $QSQ^+$ rather than $QSQ^T$ in most practical settings. At least, that's the experience I had myself when I replaced $S^T$ with a pseudo-inverse on some problems I am currently working with. Nevertheless, I see that the value of this work is to be a starting point for a theoretical study on pooling/coarsening in GNNs that will hopefully be developed further in the future.

Even if most of my concerns still remain after the rebuttal, I do appreciate the effort of the authors in answering in detail to every author and adding additional experiments. Therefore, I'll raise my scores conditional on the fact that the authors will modify the paper as asked.

[1] I. S. Dhillon, Y. Guan, and B. Kulis. Weighted graph cuts without eigenvectors a multilevel
approach. IEEE transactions on pattern analysis and machine intelligence, 29(11):1944–1957,
2007.

[2] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs
with fast localized spectral filtering. In Advances in Neural Information Processing Systems,
pages 3844–3852, 2016.

[3] Grattarola, D., Zambon, D., Bianchi, F. M., & Alippi, C. (2022). Understanding pooling in graph neural networks. IEEE transactions on neural networks and learning systems, 35(2), 2708-2718.

[4] Bianchi, F. M., & Lachi, V. (2024). The expressive power of pooling in graph neural networks. Advances in neural information processing systems, 36.
I thank the authors for their rebuttal and new experiments.

In general, I think the practical applicability of this work is limited at present. The computational cost seems to be expensive and this class of graph coarsening idea seems to be mostly applicable to homogeneous datasets (usually less challenging datasets), and as nodes inside a supernode can only be assigned to the same class, the performance would be poor on more heterogeneous datasets.

However, I also think that we need more theory to understand the coarsening and pooling algorithms. I am not an expert in this area and cannot evaluate the significance of the theoretical results provided in this work or their applicability to other works or for future theoretical analysis. Relying on Reviewer 7C68's review, I would like to increase my score to 5; however, I want to decrease my confidence level in my assessment to 1, since I am making a decision in an area where my knowledge is very limited.
Thanks for the response. All my concerns are addressed.