Taxonomy of reduction matrices for Graph Coarsening
Authors: Antonin Joly
Nicolas Keriven
Aline Roumy
Venue: NeurIPS 2025 poster ()
Keywords: graph coarsening
graph machine learning
Primary area: theory

Abstract: Graph coarsening aims to diminish the size of a graph to lighten its memory footprint, and has numerous applications in graph signal processing and machine learning. It is usually defined using a reduction matrix and a lifting matrix, which, respectively, allows to project a graph signal from the original graph to the coarsened one and back. This results in a loss of information measured by the so-called Restricted Spectral Approximation (RSA). Most coarsening frameworks impose a fixed relationship between the reduction and lifting matrices, generally as pseudo-inverses of each other, and seek to define a coarsening that minimizes the RSA.

In this paper, we remark that the roles of these two matrices are not entirely symmetric: indeed, putting constraints on the *lifting matrix alone* ensures the existence of important objects such as the coarsened graph's adjacency matrix or Laplacian.
In light of this, in this paper, we introduce a more general notion of reduction matrix, that is *not* necessarily the pseudo-inverse of the lifting matrix. 
We establish a taxonomy of ``admissible'' families of reduction matrices, discuss the different properties that they must satisfy and whether they admit a closed-form description or not. We show that, for a *fixed* coarsening represented by a fixed lifting matrix, the RSA can be *further* reduced simply by modifying the reduction matrix. We explore different examples, including some based on a constrained optimization process of the RSA. Since this criterion has also been linked to the performance of Graph Neural Networks, we also illustrate the impact of this choices on different node classification tasks on coarsened graphs.

Taxonomy of reduction matrices for Graph Coarsening
Antonin Joly
Nicolas Keriven CNRS, IRISA, Rennes, FRANCE nicolas kew.eenenrr............... fr
CNRS, IRISA, Rennes, FRANCE jotonin..ooydirisa.
Aline Roumy INRIA, Rennes, FRANCE al inee wwwunooinnia........ fr
Abstract
Graph coarsening aims to diminish the size of a graph to lighten its memory footprint, and has numerous applications in graph signal processing and machine learning. It is usually defined using reduction matrix and lifting matrix, which, respectively, allows to project a graph signal from the original graph to the coars- ened one and back. This results in a loss of information measured by the so-called Restricted Spectral Approximation (RSA). Most coarsening frameworks impose a fixed relationship between the reduction and lifting matrices, generally as pseudo- inverses of each other, and seek to define a coarsening that minimizes the RSA.
In this paper, we remark that the roles of these two matrices are not entirely symmetric: indeed, putting constraints existence of important objects such as the coarsened graph's ' adjacency matrix or Laplacian. In light of this, in this paper, we introduce a more general notion of reduction matrix, that is not necessarily the pseudo-inverse of the lifting matrix. We establish a taxonomy of "admissible" families of reduction matrices, discuss the different properties that they must satisfy and whether they admit a closed-fon description or not. We show that, for fixed coarsening represented by fixed lifting matrix, the RSA can be further reduced simply by modifying the reduction matrix. We explore different examples, including some based on a constrained optimization process of the RSA. Since this criterion has also been linked to the performance of Graph Neural Networks, we also illustrate the impact of this choices on different node classification tasks coarsened graphs.
the lifting matrix alone ensures the
Introduction
In recent years, several applications in data science and machine learning have produced large-scale graph data [18] 5) For instance, online social networks [13] or recommender systems (36) routinely produce graphs with millions of nodes more. To handle such massive graphs, researchers have developed general-purposs. graph reduction methods [4], such as graph coarsening [27] 7 as well
as specific learning techniques on these coarsened graphs 24 [9]. Graph coarsening starts to play an
increasingly prominent role in machine learning applications 77.
Graph Coarsening and Spectral guarantees Graph coarsening consists in producing small graph from a large graph while retaining some of its key propertics. There are many ways to evaluate the quality of a coarsening, following different criteria [10 27 77. The majority of these approaches aims to preserve spectral properties of the graph and its Laplacian, and have given rise to different coarsening algorithms 27
22 28 The most widely used spectral guarantee is the so-called Restricted Spectral Approximation (RSA, see Sec. 2), introduced by Loukas (27]. In broad terms,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the RSA states that the frequeney content of a certain subspace of graph signals is approximately preserved when projected on the coarsened graph and then re-lifted in the original one, or intuitively. that the coarsening is well-aligned with the low-frequencies of the Laplacian. The RSA is a general-
purpose criterion with many applications, from clustering to signal reconstruction 27 23 Recently, RSA guarantees were also used to guarantee the performances of Graph Neural Networks on the coarsened graph [23].
Projection and lifting. The projection and re-lifting operations are generally described by two matrices: the reduction matrix allows to transform graph signals from the original graph to the coarsened one, while the lifting matrix does the opposite. In virtually all works on graph coarsening, these two matrices are simply pseudo-inverse of cach other. and both can represent the "graph coarsening" indifferently. However, in this paper we make the following remark: their roles are not entirely symmetric. Mathematically, as we will see, the lifting matrix alone has to be quite constrained for the graph coarsening to be "well-defined", with a consistent adjacency matrix and Laplacian. The reduction matrix, on the other hand, does not seem to play role in the definition of graph coarsening. However, it does play a role in computing the RSA. Therefore, in this paper, we examine the following questions: for fixed lifting matrix, 1) What are the admissible degrees of freedom for the reduction matrix? and 2) Can we improve the RSA by simple modification of the reduction matrix alone?
Contribution. In this paper, we thus define and then explore the admissible sets of reduction matrices over which to optimize the RSA. We introduce several interesting examples, from closed- form ones motivated by notions of optimality and memory footprint to optimization-base ones over well-defined sets with various properties. We compare these different choices, both in terms of RSA and performance when used within GNNs trained on coarsened graphs.
Related work Graph coarsening is derived from the multigrid-literatuee 33 and belongs to a broader class of methods commonly referred to as graph reduction. The latter includes graph sampling
[17] graph sparsification 34 I 26]. or more recently graph distillation [21 41 20), inspired by
dataset distillation [37]. Some of the first coarsening algorithms were linked to the graph clustering community, c.g. [9] which used recursively the Graclus algorithm [T0] algorithm. Linear algebra technics such as the Kron reduction were also employed [27
In 277, the author introduces the RSA, and presents greedy algorithm that recursively merge nodes by optimizing some cost, which in turns leads to RSA guarantees. This the approach we use our experiments (Sec. (5).
It was followed by several similar methods with the same spectral criterion [8] 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 255 29 [1].
22
28 Since
On the contrary, the RSA guarantees 27 leveraged this paper are uniform over a whole subspace to ensure the spectral preservation of the coarsened graph.
Closer to us, some works aim to optimize various quantities after the coarsening has been computed. For instance, GOREN (6] optimizes in a data-driven manner the edges' weights in the coarsened graph, which quite different from focusing on reduction/lifting matrices as proposed here. Moreover, we consider the RSA, a general-purpont criterion not necessarily related to downstream tasks. The literature also includes different choices of reduction/lifting matrices, or propagation matrices in GNNs on coarsened graphs (23), but to our knowledge this paper is the first to put forth the idea of decorrelating reduction and lifting matrices up to a certain point, with precise mathematical definitions of the consequences.
Finally, we mention graph pooling, which designed to mimick the pooling process in deep convolutional models on images and is somewhat related to graph coarsening in terms of vocabulary, One difference is that graph pooling tends to focus only on the reduction phase while graph coarsening focuses on repeated reduce-then-life then-lift operations between the coarsened and original graphs. Although some pooling method can be computed as preprocessing such GRACLUS [IO], the most well-known pooling methods are data-driven and fully differentiable (Diffpool 40), top-K K pooling (14), DMoN 35).. These methods use interchangeably the reduction and the lifting matrix by choosing one as the Iransposed of the other. Usually in graph pooling, this matrix is unconstrained and is either defined heuristically or learned, while graph coarsening proposes mathematical links between the reduction and the lifting matrix. In this paper, we explore these mathematical links.
2

---

Outline. We start by background material on graph coarsening in Sec. highlighting the roles of the lifting and reduction matrices. We emphasize the asymmetricity of their roles, along with the strong constraints put on the lifting matrix alone. Then in Sec. we study sets of admissible reduction matrices, focusing on various notions of "generalized inverses". Some will be very generic, while others will admit parametrizations that are convenient for optimization. In Sec. 4 we then study several motivated examples of reduction matrices, classical or entirely novel, with an analytical closed-form expression or based optimization procedures. We relate them to the properties defined in the section before. Finally, we compare their performance in terms of RSA or GNN performance in Sec. [5] The code is available at https: // h/t///gtabbb..//.///.. inrii. frarioll./////yy//// anjoly/ mete-mattiicsse and proofs are deferred to App. B
Characterizing graph coarsening with the lifting matrix
Notations A graph G with N nodes is deseribed by its weighted adjacency matrix A E NNN The combinatorial Laplacian is defined as L = [(A) := D A, where D = D(A) := diag A1x) is the diagonal matrix of the degrees. A matrix is said to be binary if all its coefficients are either 0 or 1. For a symmetric positive semi-definite (p.s.d) matrix M, we denote ||æ]|as Vx Mr the Mahalanobis semi-norm associated with M.
Coarsening The goal of coarsening is to reduce the size of a graph G with N nodes a coarsened graph G. with n < N nodes. The proportion of reduction achieved is measured by the coarsening ratio r = 1 N. The mapping from G to G. is obtained by grouping set of nodes in G to form supernodes in G.. This mapping can be represented by a matrix Q E R R xx, where Qik > means that node i from G has been mapped onto the supernode A of G... To represent a true mapping from the original nodes to the supernodes, the matrix Q needs to be well-partitioned.
Definition 1 (Well-partitioned Q matrix). Q is said to be well-partitioned if has exactly one non-zero coefficient per row.
One natural way 27 to define the adjacency matrix of the coarsened graph is then to take
A 2 AQ
In addition to be well-partitioned, is also natural to impose that Q is binary, as shown by 27 Prop.7] in the following Lemma.
Lemma 1 (27)). Let Q be well partiiiood matrix. The two following properties are equivalent: (i) Q proportional to a binary matrix; (ûi for all A, we have L. := [((a)= = Q L(A)
In other words, the Laplacian of the coarsened graph can be defined by the same equation as ① In light of this, matrices Q in this paper will always be well- cell-partitioned and binary. This results in a particularly interpretable A weighted edge between two supernodes has value equal to the sum of the weights of all the edges between the two groups of original nodes.
Lifting, Reduction, and spectral quality measure for Graph Coarsening The quality of coarsening can be assessed from signal processing point of view (27. Indeed, one way to interpret Q is that it can be used to "lift" a signal y E R from the coarsened graph to the original one, as ==
Qy, and is thus called the lifting matrix the literature. Its counterpart is a reduction matrix P RaxN that reduces signal from G to Go. More formally, let RN be signal over the nodes of G. The coarsened signal Fe E R_ and the re-lifted signal ã E R-- are defined by
Ze Px,
i Qr. IIx
(2)
where 11 QP. To measure the quality of the coarsening, a popular criterion introduced by Loukas [27, is then the Restricted Spectral Approximation (RSA), which measures the loss of information from x to å. Since II is at most of rank n < N, only a subspace R of N may be preserved. This leads to the definition of the RSA constant below.
Definition 2 (Restricted Spectral Approximation constant). Consider a subspace R. C RNN, Laplacian C, a lifting matrix Q, a reduction matrix P. The RSA constant C.R. is defined as
CC.OPP.R = sup
|| Qxxle
(3)
=ER_||=||==1
3

---

Classically, the preserved subspace R is spanned by the eigenvectors of the first eigenvalues of C. In this case, the RSA constant can be used to bound the deviation between the spectrums of L and Le. When R. is an eigen-subspace of L, the RSA has an explicit expression
2 C.R = where V is orthogonal basis of R and |1-1l2 is the spectral norm. (1 PQ) Note that this expression is convex in P. which will be useful for optimization. This definition slightly differs from (27]. as it disentangles the roles of the lifting matrix Q and the reduction matrix P. while in (27]. Q was fixed as the Moore Penrose inverse of P.
Q is more constrained than P One might have noticed that P and Q do not exactly play symmetric roles. Indeed, and this is the first key message of the paper: as shown by (T) and Lem. [ the matrix Q alone fully characterizes the graph coarsening, and the matrix Q alone must respect strong constraints (it must be well-partion pertitaait and binary). Technically, the reduction matrix P does not play any role in the definition of A. or Le.
However, P still plays role in the computation of the RSA constant. As mentioned in the introduction, in virtually every formulations of graph coarsening. P is taken as the Moore-Penrose pseudo-inverse P Q For a pell-paatitioned, binary 2, this matrix has the same support as Q with rows that contain only coefficients 1/nx where nę is the size of the ktth supernode. In this paper, we challenge this choice and argue that there is no real reason for it. As we will see, there of freedom in designing P. and this is our second main message: for a fixed Q. the matrix P' can be optimized to improve the RSA constant. Of course, this optimization may still satisfy important constraints in terms of interpretability. feasibility, memory footprint, or just simplicity. and this forms the main questions mentioned in the introduction: given a well well-partitioned and binary lifting matrix, what are the "valid" reduction matrices? Is there more "optimal" choice to minimize the RSA?
relative degree
Normalized Laplacian matrices Before moving the next section, we adapt the previous discussion to a broader notion of "normalized" Laplacian, that we call A-Laplacian, defined as
== ALA
where L(A) is the combinatorial Laplacian, and A = A(A) E NNN a strictly positive diagonal matrix that depends on the adjacency matrix. This A-Laplacian thus encompasses the combinatorial Laplacian when A IN. or the classical normalized Laplacian when A = D D-1/2 Another interesting example is the self-loop normalized Laplacian A (D + IN) IN) 1w)_-//, which is such that L = IN - S where S is the propagation matrix of the classical Graph convolution network defined by Kipf 244
To extend the definition of the RSA constant (3) to the case of the generalized A-Laplacian, is first necessary to ensure that the norms used in the original and coarsened graphs, G and Ge, are comparable (27] Corollary 12]. This requires establishing the consistency of the A-Laplacian matrices of G and Ge- This is shown with the following lemma, provided that, starting from any binary well-paatitioned lifting matrix Q E TR Nxn a generalized lifting matrix is constructed as
(5) where A. = A(A.) with A. defined in []. Note that Q is also well-partitioned when Q is well- partitioned, however it is generally not binary. Instead, the constraint still lies on Q, as shown below.
Q Q(A, Q) = A QA-...
Lemma 2 (Consistency, adaptation 27 Let Q be well-partitioned lifting matrix. The two following properties are equivalent:
a) Q is proportional to binary matrix.
b) For all adjacency matrices A. we have that L is defined in (4) and Q in (5)
= Q(4, L(A)QAA Q), where we recall
Hence, the normalized Laplacian of the coarsened graph can again be directly deduced from the normalized Laplacian of the original graph when adopting the generalized lifting matrix Q = Q(4, Q) with well- eertiiaatt and binary Q. This consistency then enables the definition of a generalized
RSA constant
sup ELI...RR IER.
| QP
(6)
where, again, we emphasize that L is defined in (4) and Q in (5). The main question that we will examine the rest of the paper remains: for a fixed Q that parlipaatiiioned and binary, what are the "valid" reduction matrices P, and is there more "optimal" choice to minimize P.RQ

---

Expanding the space of reduction matrices
In this section, examine the first of the above questions: what are the "valid" reduction matrices P? One might be tempted to simply minimize the RSA equation (6) over all P matrices, however this discards important properties of graph coarsening that want to preserve. To address this, introduce several ensembles of admissible P matrices and derive key properties that will enable us, in Sec. 4 optimize P and compare several examples.
In the beginning of this section, Q will indicate any well-partitioned matrix. We note that, unlike all the matrices considered in the literature. some matrices P with support different from Q" will be acceptable. Intuitively, Q defines the "true" mapping between the nodes and the supernodes by enforcing the well- cell-partitioned aspect, while P will be allowed to relax this constraint. We begin by examining the largest such ensemble, denoted Ej.
E1: P such that II is a projection. A first minimal property in graph coarsening is that applying successively coarsen and lift procedures does not degrade further the signal, or in other words, the coarsen and lift operator II QP is projection II2 II.
The classical choice, where P is the Moore Penrose inverse of Q, satisfies the projection property II is even an orthogonal projector in this case. However it is only an example among a bigger set of reduction matrices which satisfies _1 II. To characterize this larger set, we first recall the notion of generalized inverse.
Definition 3 (Generalized Inverse). Let A E Kmxn We consider a matrix B R which can satisfy the following conditions:
(i) B E A
with A == {M AMA =
(ii) A E B
i.c BAB = B
(iii) AB is Hermitian: (AB)" = AB.
(iv) BA is Hermitian: (BA)* BA.
The matrix B is said to be:
generalized inverse of A when it satisfies
(i)
generalized reflexive inverse of A if satisfies simultaneously and (ii)
Moore Penrose inverse of A if it satisfies (i)
(ii)
and
(iv)
Remark 1 (uniqueness). The Moore Penrose inverse is unique while there may exist infinitely many "generalized inverses"
(3).
(PIQ cP] Pd]
We now propose an alternative characterization of the E, ensemble.
Eg = Q"
X Papt
Lemma 3 (Generalized Inverse and Il projection).
Es Qaupp
For well-partitioned lifting matrix Q:
X
X
=1
Q QE p9
Pioukas
PMP
The proof can be found in App. B.4 Lem. means that, assuming that Q is well-partitioned, E, {P II projection] the hypothesis on Q is important here: this lemma not true general, and only valid because Q particularly simple.
Ensembles of admissible reduction ma- trices. Ej includes all P satisfying only the pro- jection constraint for PQ 1l. En contains all generalized inverses Q. subset of Es in Lem. 4 Eg restricts Es to ma- trices sharing the same support as Q".
Figure 1:
{P Q E P9}. Note that
shown to
In general, the E₁ does not admit further descrip- tion, and it seems difficult to optimize over with algorithms such as projected gradient descent. We see next that a relatively minor additional constraints considerably simplifies the situation.
Eg: P generalized inverse of Q. We now consider an ensemble characterized in reverse manner of Ei. The rationale is that this admits closed form characterization, which allows for an easy implementation of optimization algorithms over it.
Lemma 4 (Generalized reflexive inverse). For well- pelt-partitioneed lifting matrix Q and reduction matrix P such that Q E P9, we have the following equivalence:
rank(P) = n - E Q"
Conversely, P Q" implies Q E 88 and rank(P) such that Q" C Ev-
5

---

Again, this proof relates specifically to well perlitartti matrices Q. We thus define E2 := Q and the lemma shows that E2 E, (Fig. DT. The inclusion often strict, as there generally exists such that Q E pe but such that rank P) < The proof of this lemma can be found in App. B.5
Remark 2 (Generalized inverse = reflexive), In Lem. 4 we show that, for well well-partitioned Q, generalized inverses of Q are automatically reflexive generalized inverses. Of course, this not true in general, here this is again due to the fact that Q is well rell-partitioned.
As hinted above, the set Ez far easier to describe than Eg-
Lemma 5 (Characterization of generalized reflexive inverses of Q). Let Q RNxx be well- partitioned lifting matrix. All the reftexive generalized inverses of Q can be characterized as:
E Q" 1Qt + M (IN QQ*) J E ER
with Q+ the Moore Penrose inverse of Q.
These two lemmas are important because they provide a way to optimize P. Indeed, by the converse of Lem. 4 it is shown that Egg (being subset of E1) contains admissible matrices. Moreover, Lem. (proven in App. B.6 offers a convenient characterization of Eg through the matrix M.
Eg: P generalized reflexive inverse with same support Up until now, matrices in E₁ and Eg have no reason to have the same support as Q+, unlike for instance the Peooree inverse. Worse, matrices in Fe may be very dense, which might hinder computation time and increase memory usage. Therefore, we consider sparser P, and add the constraint that has the same support as Q while still being a reflexive inverse. By construction, E3 E2, shown in Fig. Moreover, E5 is empty, as it contains at least the Moore-Penrose inverse (see next section).
Lemma (Generalized reflexive inverse with same support). Let Q = Q(A, E Nxn be generalized lifting matrix with Q well- partitioned and binary. The set of reflexive generalized inverse of Q with the same support as Q is defined as
{ supp P) supp(QT) E
E3 = P RONN
k= A(R) 2. Vi [1.
Pik
Note that, while Lem. and were valid for any well-partitioned matrix Q, here we specifically examine Q = QAA, 2) with Q well-partitioned and binary. Moreover, all matrices with non-zero coefficients on the support of Q" that are also in E1 are in Eg and Ez, as their rank is equal to n. To provide better intuition about Lem. consider the of the combinatorial Laplacian (A In)
where Q Q: this lemma reduces to k= Pa 1, which appears to be natural condition already
used in 3
The lemma is proved in App. B.7 Note that optimizing over Es is particularly light compared the previous dense examples, as it requires optimizing only over the N non-zero coefficients located on the support of QT. Projected gradient descent can be implemented with simple renormalization of the rows at each iteration.
4 From classical to novel reduction matrices: a comparative study
Now that we have proposed a taxonomy of the valid reduction matrices P, we investigate the second question raised in Sec. 2 what are good examples of reduction matrices? In all this section,
consider Q = Q(A, Q) with Q well-partitiones and binary. As outlined in Sec. 2 Le = Q LQ is then the A-Laplacian of the coarsened graph. We will start with three examples with closed-form analytic expression, then outline a possible optimization framework, emphasizing that is only one choice among many possible. It is worth noting that the transposed matrix P Q commonly used in graph pooling, does not belong to E,, and is therefore not considered in our analysis.
Moore-Penrose Reduction. The most common choice for P in the literature the Moore Penrose inverse of Q (the derivation is in App. B.2
27
25
is simply
PMP Q (Q (QQ)Q=Q Q0

---

By Def. 3. PMPP E E2 and has the same support as Q" since QTQ is diagonal when Q is well- partitioned. Thus, Pasp E Ez.
Interestingly, PMP is the solution of the following optimization problem, which we note is formulated over all matrices P RRxN without any constraint:
arg min FERM 2
sup
|| QP
(8)
This problem looks suspiciously similar to the RSA 6). but differs in several key aspects. Namely, the signals lives in R. not in R, the Mahalanobis norm || || in (6) is replaced by the Euclidean l2 norm. This suggests that PMP is still "optimal" from a certain point of view, but for a different (much simpler) problem than the RSA. Below, will formulate an optimal matrix for a problem closer to the RSA, but first examine another potential choice in Eg.
Loukas Reduction (27, aka iterative coarsening. Many coarsening algorithms construct the lifting matrix iteratively, product of individual coarsening Q Q1 Qe- In [27]. Loukas implements such an algorithm, and chooses the reduction matrix as the product of the Moore-Penrose inverses of each lifting matrix
Loouaas = = .....QT QF
Note that this is not equal to the Moore-Penrose inverse of Q in general. However, and as shown in App. B.3 this results matrix PLoukas E Eg, (see Fig. [.
Rao and Mitra inspired reduction As we have seen above, the Moore- Penrose inverse can be interpreted as the solution of an optimization problem (8), that differs from the RSA (6) in two key aspects: the subspace R and the Mahalanobis norm. We now consider the following problem, where we reintroduce the latter:
arg min TERR -|=l||==1
sup
>| QP
(10)
Rao and Mitra show that (10 admits a unique solution under some hypotheses. In our case, several simplification over their original result happen, and obtain the following: if L and Le are positive definite, then the optimal solution is P = L L. This solution does not technically apply when L and L. are A A-aplaccians since they not invertible, but inspired by this, we propose the following reduction matrix:
Q
Pope= = L
(11)
Note that, even though (0) is again an optimization problem with no constraints on P, it easy to check that Popt E Ei. However Popt & E2 as it is not full rank (see Fig. [b. Hopefully, Popt should lead to better RSA constant than PASp, even though R still absent from (TOp. However, its main drawback is that it is dense in general.
Optimization based Reduction We now turn to the true RSA minimization of (6). To our knowl- edge, does not have a simple solution such as PMP for (8) or Pope for (TO), so that we need to implement iterative optimization algorithm. As discussed in the previous section, it is particularly convenient to minimize over the set Eg, thanks to the characterisation of E2 with Lem. S The minimization can then be written
P (M())) with M arg min
sup HER, 1a
I Q4Q(M)allz
(12)
MER
with (M) = Q+ + M (IN- - QQ+). Again, solutions P are usually dense. A potential remedy add a sparsity constraint on P. which leads to the following problem:
Po = (M()
with Mi. = arg min M
sup =
|| QF)((M))ll + (l) (13)
As mentioned before, when R a subspace of L, the RSA has a close form expression that is convex in P. This results in optimization problem that are convex in M in these cases. In our experiments, we treat the I penalty simply with gradient descent combined with final thresholding operation (for simplicity we leave aside more complex optimization procedures with e.g. proximal operators).
7

---

Finally, we also mentioned that optimization over E3 was also particularly simple: a simple renor- malization sufficient for projected gradient descent. has the advantage of being always sparse, as it respects the support of Q' (of size N). This leads to the following problem:
P arg min PE 2ER,1==|
sup
a - QPrlI
(14)
This is again convex in P. as the constraint P E E3 is linear.
5 Experiments
In Sec. [4] we have proposed several examples of reduction matrices P that aimed to minimize the RSA with various constraints. In this section, we evaluate numerically the performance of these examples, both in terms of RSA constant and used within GNNs.
Setup: (i) Graph. We consider the two classical medium-scale graphs Cora 30 and Citeseer [15], and use the public split from [39] for training the GNNs. We restrict ourselves to medium-scale graphs because handling larger graphs presents challenges. Indeed, in the optimizations we propose. the RSA requires computing the square root of the original Laplacian, which is not sparse in general and, for graphs like Reddit [6]. cannot be stored on modern GPUs Furthermore, we only consider the largest connected component since connected graphs are better suited for coarsening (see details in App. C. This may induce some slight difference with other reported results on these datasets.
(ii) Laplacian and preserved space. We choose two different Laplacians: the combinatorial Laplacian L and the self-loop normalized Laplacian I, = ALA with A = (diag((A + 1) 1)-1/2, The motivation for this Laplacian comes from the fact that it is related to the propagation matrix For the RSA, the
S = DN)D-1/2 (via L IN S) commonly used in GNNs [24 23). preserved space R is chosen as the K = 100 first eigenvectors of L and L.
(iii) Lifting matrix Q. The method that has introduced the notion of RSA 27 is particularly relevant for computing Q, as we share the same objective of reducing the RSA constant. However, requires adaptation because this method minimizes the RSA constant for the combinatorial Laplacian, and yields a binary well-partitionss the RSA constant for A-Laplacian, resulting in lifting matrix Q. is worth noting that some of the assumptions made in 27 no longer hold in the A A-Laplacian setting. Nevertheless, we observe that this generalized construction still achieves good RSA constants. The details of the generalized algorithm are provided in App.
matrix lifting matrix Q. We generalize this method to minimize
RSA minimization. The RSA constants achieved by the reduction matrices introduced in Sec. are shown in Fig. far the combinatorial Laplacian L and in Fig. 2b for the self-loop normalized Laplacian L. The coarsening ratios range from 0.05 to 0.85. As expected, the two proposed methods Pope and P achieve better RSA constants than the usual РMP and PLoukas- Moreover, the performance gap increases with higher reduction ratios. Another interesting observation that the optimization methods Py,,, and por that incorporate sparsity constraints also perform very well. At low reduction ratios, their performance is nearly indistinguishable from their unconstrained counterparts Pr. This is particularly surprising given that the reduction in the number of non- zero coefficients is around 99.8%. regardless of the coarsening ratios (see App. G.2 for a detailed analysis on the sparsity of the P matrices and App. E for their computational hyperparameters) We also observe that the two approaches g.l, and P strong regularization parameter used in the sparsity penalty in Pg.1, a different setting could yield a more balanced trade-off for Pa, g.11 between the performance of P; and QT-
QT yield similar performance. This may be due to the
GNN application Inspired by the paper 223 which link the training of Graph Neural Networks
(GNN) and the RSA- : we have trained for three different coarsening ratio ( r {0.3, 0.5. 0.7]) convolutional GNN 24] and a Simplified convolution network (SGC (38) on Cora 30 and Citeseer
15) Each training is averaged on random split, using the same experimental setting as (23 and the hyperparameters are provided in App. G.T For the training on coarsened graphs, we used the propagation matrix SMP PSQ from the paper (33, where S - and the self-
normalized Laplacian. This matrix depends on both the reduction matrix P and the lifting matrix Q
8

---

Paosta
Par
POr
52-
Fo
2 3.6
24
BA
9.8
5.44
3.2
03
02
05
24
25
0'a
da
0.2
0.4
0.6
24
(a) Cora graph, combinatorial Laplacian
(b) Cora graph, self-loop normalized Laplacian L
Figure 2: RSA for different reduction matrices
The results reported Tab. show slightly better performances on Cora for high coarsening ratio and RSA-optimized reduction matrices such P.. P2.,, and Par- The results CiteSeer less pronounced, which may be due to its higher level of heterophily compared to Cora: indeed, since spectral coarsening designed to preserved the low frequencies the Laplacian and 23 the RSA is more relevant when homophily is high. Lastly, note that Popt has the best RSA but poor GNN performance. We might explain this by its density which implies propagation with SMP that is similar to complete graph. The sparsity of each matrix can be found in App. G.2 Therefore, the RSA only relatively translates to better GNN accuracy, mitigating the theoretical results of 23
Table 1: Accuracy % for node classification with SGC and GCNconv on different coarsening ratio
Cora
Citeseer
SGC
0.3
0.5
0.7
0.3
0.5
0.7
Loukas
80.5
0.0
79.7 1 0.0
76.8 1 0.0
72.6 1 0.3
71.7 1 0.1
69.7
0.7
PMP
80.5
0.0
80.1
0.0
0.5
72.7
0.0
69.5 0.3
Popt
77.1 #.6
7.1
0.3
70.9
0.1
67.3 0.4
PoT
80.3 + 0.0
80.0
7.0
7.37
0.5
67.6 0.2
Po
80.7 0.0
8.0
0.0
7.2
72.7
68.6
Pa
8.0
79.2
78.3
7..0
71.2 0.1
69.2 0.4
Full Graph
81.0 0.1
71.6 1.6000
Cora
Citeseer
GCN
0.3
0.5
0.7
0.3
0.5
0.7
PLoukas
80.6 + 0.8
80.5 + 1.0
78.1 + 1.4
71.0 + 1.6
72.2 - 0.6
70.4
0.8
PæP
80.4 + 1.0
80.7
78.6
70.8
72.1
- 1.0
71.0 1.0
Popt
73.7 1.5
63.3
1..11
64.6.1.
50.4 1 1.6
42.6 4..6044.0
P
80.5 0.9
80.9
78.0
71.1
72.3
0.7
70.0
p
80.6 166+10
0.6
7.9
7.71
72.1
- 1.2
69.6 1.0
p
80.4 0.9
80.0
7.72
70.2
66.8
1 1.1
66.7
Full Graph
8.83
70.9 1 1.4
Conclusion
In this paper, highlighted the crucial role the lifting matrix Q in graph coarsening. Surprisingly, we found that we can take advantage of the degree of freedom over the reduction matrix to obtain better spectral guarantees, without changing the coarsening itself the lifting matrix. We have defined various sets of "admissible" reduction matrices with different properties, from the very generic property of simply obtaining projection II, convenient parametrization with reflexive generalized inverses, and support constraints. We then showed that the classical choices of reduction matrices can outperformed, both by well-motivated novel examples with analytic expressions, or by matrices resulting from various optimization processes with sparsity or support constraints. Even if previous works linked the performances of GNNs trained on coarsened graph with the RSA, empirically showed that the benefits of improving the RSA were somewhat marginal, although

---

visible for high coarsening ratio and homophilous graphs. This suggests that other factors, such the sparsity of the reduction matrix, could also play in GNNs training.
In this work, we have selected the RSA as a general-purpose score to optimize, however our theoretical characterization of the admissible sets of reduction matrices does particularly rely it. We thus believe that considering more complex scoring function to take into account graphs heterophily or node features while being scalable to larger graphs is major path for future works. Notably, our optimization framework is agnostic to the specific choice of scoring function and coarsening algorithm and directly applies to these extensions.
Acknowledgments and Disclosure of Funding
The authors acknowledge the fundings of France 2030, PEPR IA, ANR-23, 1ER-23-PEIA-OO2 FEIA-0008 and European Union ERC-2024-STG--011663 MALAGA.
References
[1] Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification regret minimization beyond matrix multiplicative updates. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 237-245, 2015.
[2] Adi Ben- Ben-Isracl and Thomas NE Greville. Generalized inverses: theory and applications. Springer, 2003.
[3] Filippo Maria Bianchi and Veronica Lachi. The expressive power of pooling in graph neural networks. Advances in neural information processing systems, 36:7 16671603-7 2023.
Gecia Bravo Hermsdorff and Lee Gunderson. A unifying framework for ppectrum-preservvvv graph sparsification and coarsening. Advances in Neural Information Processing Systems, 32, 2019.
[5] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric Deep Learning: Grids. Groups, Graphs, Geodesics, and Gauges. arXiv:2104.13476 2021. URL http:p/////axiiv.. http://axxxii..r//////o abaaabs//111 /204 13478
[6] Chen Cai, Dingkang Wang, and Yusu Wang. Graph coarsening with neural networks. In 9th International conference Learning Representations, 2021.
[7] Jie Chen, Yousef Saad, and Zechen Zhang. Graph coarsening: from scientific computing machine learning. SeMA Journal, 79(1):187-22 2022.
[8] Yifan Chen, Rentian Yao, Yun Yang, Jie Chen. Kromov-Wassersie geometric view of spectrum- preserving graph coarsening. In International Conference on Machine Learning, pages 5257-5281. PMLR, 2023.
[9] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[10] Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph without eigenvectors multilevel approach. JEEE transactions on pattern analysis and machine intelligence, 29(11): -957, 2007.
[11] Charles Dickens, Edward Huang, Aishwarya Reganti, Jiong Zhu, Karthik Subbian, and Danai Koutra. Graph coarsening via convolution matching for scalable graph neural network training. In Companion Proceedings of the ACM on Web Conference, pages 1502-1510 1510, 2024.
[12] Florian Dorfler and Francesco Bullo. Kron reduction of graphs with applications to electrical networks. IEEE Transactions Circuits and Systems I: Regular Papers, 60(1):150-14) 163, 2012.
[13] David Ediger, Karl Jiang, Jason Riedy. David A. Bader, Courtney Corley, Rob Farber, and William N. Reynolds. Massive social network analysis: Mining twitter social good. Proceedings of the International Conference on Parallel Processing, pages 583-593, 2010. ISSN 01903918. doi: 10.1 109/CCPP.2000.66
[14] Hongyang Gao and Shuiwang Ji. Graph uenets. In international conference on machine learning, pages PMLR, 2019.
[15] C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pages 89-98, 1998.
10

---

[16] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[17] Pili Hu and Wing Cheong Lau. A Survey and Taxonomy of Graph Sampling. pages 1-34, 2013. URL http://arxiv www.arwwwww....aaa..o..ooooeeeee http///bs11300... 5865
[18] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 13:22118-22111
2020.
[19] Zengfeng Huang. Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 675-684, 2021.
[20] Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang, Jiliang Tang, and Bing Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 720 030-730,220 2022.
[21] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph Condensation for Graph Neural Networks. In International Conference on Learning Representations, 2022.
[22] Yu Jin, Andreas Loukas, and Joseph JaJa. Graph coarsening with preserved spectral properties. In International Conference on Artificial Intelligence and Statistics, pages 1452-4462. PMLR, 2020.
[23] Antonin Joly and Nicolas Keriven. Graph Coarsening with Message- Passing Guarantees. Advances in Neural Information Processing Systems, 37:1 14902-1149927 2024.
[24] Thomas N Kipf and Max Welling. Semi Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Leurning Representations, 2017.
[25] Manoj Kumar, Anurag Sharma, Shashwat Saxena, and Sandeep Kumar. Featured graph coarsening with similarity guarantees. In International Conference on Machine Learning, pages I 17953-17975. PMLR, 2023.
[26] Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear time. SIAM Journal on Computing, 47(6):2315-2336, 2018.
[27] Andreas Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 20(116):1-42, 2019.
[28] Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In International conference on machine learning, pages 3237-3246. PMLR, 2018
[29] Tengfei Ma and Jie Chen. Unsupervised learning of graph hicrarchical abstractions with differentiable coarsening and optimal transport. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 8856-8864, 2021.
[30] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construc- tion internet portals with machine learning. Information Retrieval, 3(2):177-13. 2000.
[31] Roger Penrose. A generalized inverse for matrices. Mathematical proceedings of the Cambridge philosophical society, volume 51, pages 406-413. Cambridge University Press, 1955.
[32] Calyampudi Radhakrishna Rao and Sujit Kumar Mitra. Generalized inverse of a matrix and applications. In Proceedings of the sixth Berkeley symposium on mathematical statistics and probability, volume 1, pages 601 -000. University of Califoria Press Oakland, CA, USA, 1972.
[33] John W Ruge and Klaus Stüben. Algebraic multigrid. In Multigrid methods, pages 73-130. SIAM, 1987.
[34] Daniel Spielman and Shang-Hua Teng. Spectral sparsification graphs. SIAM Journal on Computing, 40(4);981- -002,, 2011.
[35] Anton Tsitsulin. John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. Journal of Machine Learning Research, 24( 14(127)11-11, 2023.
[36] Jizhe Wang. Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, Dik Lun Lee. Billion-scale commodity embedding for E-commerce recommendation in alibaba. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 839 848, 2018. doi: 10. 1145/
3219819.321989.

---

[37] Tongzhou Wang, Jun Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint 2018.
[38] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger, Simplifying graph convolutional networks. In International conference machine learning. pages 6861-6871. PMIR, 2019.
[39] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference machine learning, pages 40-48. PMLR, 2016.
[40] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
[41] Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure-fiee free graph condensation: From large-scale graphs to condensed graph-free data, Advances in Neural Information Processing Systems, 56:6026-6044 2023.
A Useful property and definitions
Definition 4 (Left inverse). If the matrix A has dimensions m x n and rank(A) = n, then there exists an n X m matrix A7." called the left inverse of A, such that:
A7 A In
where I, is the X identity matrix. Definition 5 (Right inverse). If the matrix has dimensions x n and rank(A) m, then there exists an matrix AR called the right inverse of A, such that:
AA Im
where Im is the m x m identity matrix.
Lemma 7 (rank of well-partitioned matrices), For well-partitioned lifting matrix Q E Nxn,
rank(Q)
(15)
Proof. For a well-partitioned lifting matrix Q E R RNxx, there is only one non zero value per row: Consequently all the columns are independent and the rank of the rank of this matrix is equal to
n.
Remark 3. Similarly a reduction matrix P E REXN, which has the same support as Q with Q well-partitioned lifting matrix is also of rank n.
Lemma (QQT is diagonal). Let Q be well- pallitartdto lifting matrix. For all matrix P g B with the same support as Q,, PQ diagonal.
Proof. Let a reduction matrix with the same support as Q Let's show that (Q (QTQ is diagonal).
For i,j E .....N3 and + j:
N
(QTQ)
Σ Qu
k=1
Indeed if one term is different from 0, it means that two nodes and j of Ge have been expanded to same node l: of G which contradicts the rell-partitioned definition.
Thus TTQ is diagonal and by equality of the support PQ is also diagonal.
Lemma (PQ I,). Let Q well- cell-partitioned lifting matrix. have the following equivalence
PQ = -
Proof. Let's show the two sides of the equivalence.
12

---

= If PQ = In we have directly IIa = II and thus with Lem. 3 have rank(P) r and using Lem. as pa have P Q
Q E PS. Then as PQ = In, we
if E Q2 then QPQ = Q. by multiplying by the Moore Penrose inverse Q to the left, we have Q*QPQ= QF Q thus PQ I,- The Moore Penrose inverse being left inverse of Q seen in App. B.2
B
Proofs
B.1 Consistency Lem.
This property is an extension of Loukas work [27] on the consistency of the combinatorial Laplacian. We will use the Lem. I proven in [7 for proof.
Let Q be a well-partitioned lifting matrix. (A)) and QAA Q) (AA) = A 11120..
For all adjacency matrix A, consider L(A)
When Q is binary matrix. By using Lem.
[ [(A,) Q C(A)Q. Thus,
= ((4)))
=A.0TA-AACAAA
((AA)
=A(AAC(AA)AAA)
= L((A)
Le
When L. = Q LQ LQ then
Le = LQ
= A.C.A. = A.Q - - 'QA.
A.C.A. A.Q T LOA.
L. e cb
Q is binary
The last line using Lem.
B.2 Proof of Lemma Moore Penrose inverse
Proof. Let's show that Q = (QTQQ (0
For given well-partitioned lifting matrix Q E R we have rank(Q) proposed in Lem.
We can compute one left inverse as Q = (QTQ) QQ.
It verifies the four properties of Moore Penrose inverse
1. QQ7 Q Q(QTT))-QTT====
2. Q7 QQ (QT0)=QQT QQQ -Q=)=-00-- =0- Q7
3. (QQ,") =(QTQ)-1QT) Q
= =Q0
4. (Q7, QT --
Thus is the unique Moore Penrose inverse of the lifting matrix Q.
Please note that for the third condition used that (QTQ) diagonal (see Lem. 8 and QQ1
symmetric.
It is thus by definition generalized reflexive inverse of Q with the same support QT.
13

---

B.3 Proof Pookas generalized reflexive inverse
For a multilevel coarsening scheme we have intermediary coarsening with intermediary well- partitioned Qi. We remark that Q = Q1 ....... Qe is also a well-partitioned lifting matrix.
Let's examine PLoukas Q ... Q First it is of same support QT. Secondly, Loouas Q wT..QQQ, Q .....QQ Qı .... Qe I, Moore Penrose inverse are left inverse. Using Lem. 9 have P E Q" Thus Poouas is generalized reflexive inverse of Q and has the same support as Q".
B.4 Proof of Coarsen-lift operator projection Lem.
Proof. Let's show the two side of the equivalence:
II projection implies Q P8
We have II2 then QPQP = QP.
As Q is well-partitioned, we have that rank(Q) = n (using Lem. 7p. Thus we have the existence of
left inverse ( (nne example the Moore Penrose inverse) such that Q Q In-
We multiply our expression at the left by Q7 then QT'Q = Qi QP thus PQP P. Consequently Q is a generalized inverse of P.
= E Ps implies = QP projection
M| QPQP = QP = II. Thus II is a projection using directly the generalized inverse property on Q. (condition (i)
B.5 Proof of Reflexive generalized inverse Lem. 4
Proof. For a well-partitioned lifting matrix Q and a reduction matrix P such that Q E P9. Let's show the two sides of the equivalence:
- rank P) = n implies P E Q"
With this "full rank" reduction matrix, using Lem. 7 there is the existence of right pseudo inverse PR such that PPR In.
As we have Q P9 that implies II2 = II, using the Lem. 3 We thus have QPQP= =QP using the existence of P we multiply this equality by P
QPQP= QPQP=QP== = QPQPP = QPPF
QPQ=Q
Thus P E Q?.
E Q9 implies rank(P)
QPQ Q by assumption. As we know that rank (Q) n, we can compute one left inverse Q and multiply at left for both side of this equation. Thus we have PQ = I,-
This is only possible if rank P) 2 otherwise the kernel of PQ would not be null. Thus bounded by the dimension of the matrix rank(P) P) n.
Second implication of the theorem Now for the second part of the theorem: have P E Qº. Thus PQPQ = PQ and 2 II.
Using the Lem. 3 have Q ps, this justifies the inclusion of Es C Ei
B.6 Proof of Generalized inverse Characterization Lem. 5
Proof. We will use the following theorem presented as theorem 2.1 in but presented as Corollary of [3] in 2
14

---

Theorem 1 (Generalized inverse characterization). Let A E Rmxx Then A exists. The entire classe of generalized inverses generated from any given inverse A by the formula
A + U - AU
(16)
where U IRax is arbitrury.
We apply this characterization to the well-partitioned lifting matrix Q E RR-Vx using a well known generalized inverse of Q, namely the Moore-Penrose pseudo inverse" Q
that has been characterized
in App. B.2
Thus Q + M 2- QUQMQQQT for M |R*X arbitrary, generates all the generalized inverse of the lifting matrix Q.
But this formula has some simplifications. Indeed Q Q = I,, as we have proved in App. B.2 Thus the characterization can be rewritten as Q+ + (In - QQ+) for an arbitrary M E R=xx
Reflexive Let's show that these generalized inverse are also reflexive:
We have QPQ Q P E Q". Thus IT2 QPQP = QP II. Using the equivalence of Lem. we have that Q E P9. This is a characterization of reflexive generalized inverse.
B.7 Proof' of Generalized reflexive inverse of same support Lem. 6
Proof. Let's show the two side of the equivalence:
Q with same support implies Σ A(R)
2e(i)
For well pellipartitioned, degree-wised wiied valued matrix Q and a matrix E Q9 with same support as Q using Lem. 9 we have PQ = IN. Thus each diagonal term must be equal to one
N
ii, (PQ),
Pu
N
Ac(i)
Vi,
Pu
k=
Pik 1
Vi
A(k)
(1
is the normalization condition have.
Pa (. and with same support as Q implies P E Q5
E
For reduction matrix with the same support as QT, PQ is thus a diagonal matrix (Lem.
Moreover Σ k=
(. we have
(PQ)iz
Psn
(i AKk)
Σ
Pi
M/Qus Qm:
10 when +
wheni
15

---

Thus PQ = In, using Lem. we have P E Q9.
C Presentation of datasets
We restrict the well known Cora and Citeseer to their principal connected component(PCC) as it more compatible with coarsening as a preprocessing step. Indeed, the loukas algorithm tend coarsen first the smallest connected components before going to the biggest which leads to poor results for coarsening with 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. The characteristics of these datasets and their principal connected component are reported Tab.
Table 2: Characteristics of Cora and CiteSeer Datasets
Dataset
# Nodes
# Edges
Train Nodes
Val Nodes
Test Nodes
Cora
2,708 2,485
10,556
140
500
1,000
Cora PCC
10,138
122
459
915
Citeseer
3,327
9,104
120
500
1,000
Citeseer PCC
2,120
7,358
80
328
663
D Random Geometric graphs
random geometric graph is built by sampling nodes with coordinates [0, 1]2 and connecting them if their distance is under given threshold. For this additional experiment on minimizing the RSA, we sample 1000 nodes with threshold of 0.05 (Fig. 3).
The results presented in Fig. confirms the observation made for the same experiment on Cora, Popt being the best option minimize the RSA.
188
Pauliu
12
Part
Pg
266
Pan
02
60
25
d
(a) L
(b)
Figure 4: RSA minimization on a Random Geometric Graph
E
Convergence of optimization algorithm
For the optimization hyperparameters, we compared different optimizer, different learning rate, different initialization. The results for the three different problems can be find below.
E.1 Parameters for Pr
We present here the chosen parameters for the optimization problem defined in Eq.
As initialization matrix M for our optimization procedure, we choose the Moore Penrose inverse matrix PMP compared to Popt and PLoukas Indeed shown in Fig. 5 the Popt initialization is too
16

---

Figure Example of a random Geometric graph
close to the minima and thus the matrix doesn't 't change and is too similar to Popt. PMP is better initialization for combinatorial Laplacian as PLoukas Furthermore PMP is more generic as PLoukas which can only be computed in multi-level coarsening algorithm. The random initialization does not converge fast enough and show the relevance to consider more "classic" reduction matrix as initialization.
We choose the stochastic gradient optimizer (SGD) is more stable than the Adam optimizer. For the Learning rate we choose (r 0.01 for an improved stability.
Fig. 5 is computed for coarsening Cora with 0.5.
S6D
Fao
(a) Initialization
(b) Random Init
(c) Optimizer
(d) Learning rate
Figure 5: Parameters for p
E.2 Parameters for Pt
We present here the chosen parameters for the optimization problem defined in Eq.
To enforce the sparsity we apply after the optimization procedure a threshold of 0.001 to erase the small coefficients.
We choose as initialization matrix M the Popt matrix. Parp and PLoukas provide a better combined loss as shown in Fig. 6 but due to the sparsity constraint they do not leave their support and the
17

---

sparsity remains unchanged (as shown in Tab. 3). It then becomes an optimization on the same support and the RSA is less improved. Oppositely when we initialize with P,a0 which very dense, we obtain a number of non zero coefficients close to the support of PMP with an additional 500 coefficients.
We choose an À coefficients which control the / penalty equals to À = 0.01 to enforce the sparsity.
As the previous experiment, we choose the SGD optimizer and learning rate Ir 0.01 for an improved stability.
Fig. 6 and Tab. 3 are computed for coarsening on Cora with r = 0.5.
lambde
02
(a) Initialization
(b) À Sparsity
(c) Optimizer
(d) Learning rate
Figure 6: Parameters for P
Table 3: Influence of Sparsity coefficient for Pg (ex with r = 0.5 and threshold = 0.001)
Initialization
A
#Non zero coefficients of Initialization
# Non zero Coefficients
LLakas
0.01
2,485
2,479
PMP
0.01
2,485
2,509
Popt
0.01
3,080,144
3,007
Popt
0.001
3,080,144 144
29,585
Popt
0.1
3,080,144
654,080
E.3 Parameters for P7
We present here the chosen parameters for the optimization problem defined in Eq. 14
As initialization vector for optimization procedure, we choose the zero coefficients of the Moore Penrose inverse matrix РAT compared to the non zero coefficient of PLoukas- a random initialization and the uniform vector which has all same values for each node in the same super node. Indeed as shown in Fig. the РMP vector initialization the only stable method.
The SGD optimizer is still more stable than the Adam optimizer which motivate its choice. For the Learning rate we choose Ir 0.05 for fast convergence and an improved stability. The results are reported in Fig. 7
Uniform init
SGD
MP Init
Adam
6.m
Loukas Init
6.10
1r-0.05
Ir-0.2
(a) Initialization
(b) Optimizer
(c) Learning rate
Figure Parameters for QT
18

---

Fig. 7 is computed for coarsening on Cora with r = 0.5.
Adaptation of Loukas Algorithm
You can find below the pseudo-code of Loukas algorithm Alg. | This algorithm works by greedy selection of contraction sets (see below) according some cost, merging the corresponding nodes, and iterate. The main modification to replace the combinatorial Laplacian in the Loukas code by any Laplacian L ACA. Note that we also remove the diagonal of A, each iteration, Loukas given its lower value of RSA. The output of the algorithm is the resulting lifting matrix Q = Q1 Qe. the coarsened adjacency A. and the the Loukas and Moore Penrose reduction matrices Lookas and PMr.
Algorithm Loukas Algorithm
Require: Adjacency matrix A, Laplacian L - ACA, coarsening ratio y, preserved space R, percentage number of nodes merged one coarsening step The
1: Nobj t intt N r) the number of nodes wanted at the end of the algorithm.
2: compute cost matrix Bo + IVTI,-1/2 with V an orthonormal basis of R
3: Q 2< IN
4: while n 2 Robj do
5: Make one coarsening STEP
6:
Create candidate contraction sets.
7: For each contraction C, compute cost(C, Bt-1, L1-1) |[ll BB. (1-1BI-1)-M 1/2
|C|-1
8: Sort the list of contraction set by the lowest score
9:
Select the lowest scores overlapping contraction while the number of nodes merged is inferior to min(n - Tobij ni.)
10:
Compute the binary 0-1 matrix Qi intermediary lifting matrix with contraction selected
11:
Qi-QQ: < A
PLoakas f- PLonkas
PMP rruniform(()) PMPP
14:
B Q+Bi-1
15:
Art 2 A diag ((ΩT A(-11)1)),,
16: L L
17: n min(n Mobyj ne)
18:
end while
PMP QQT
20: return Ac, Q, PLoukas: PMP
The terms IL and Le denote specific projection of the contraction set. Their precise definitions provided in Loukas work (27). We kept them unchanged in our experiments and defer any potential adjustments to future work.
In our adaptation we also add a parameter n. to limit the number nodes contracted at each coarsening step. In one coarsening step, when contraction set C is selected, merge (C] nodes. In practice Loukas proposed in implementation to force n, oo and coarsen graph one single iteration. We observed empirically that decreasing ne leads to improved results.
Candidate contraction Set. Candidate contractions sets can take two main forms: either pairs of nodes connected by an edge (referred to as the variation edges version), or the full neighborhood of each nodes (the variation neighborhood version). In practice, since neighborhoods tend to large in our graph, this second option proves impractical for small coarsening ratios and typically leads to suboptimal results. We therefore rely on edge-based candidate sets, and adjust the parameter n,, to control the greedy behaviour of the algorithm.
19

---

G Experiments hyperparameters
For all the experiments, we preserve K eigenvectors of the normalized self looped Laplacian 7 ACA with A (diag(AIx) + 1)-1/2 with K 100. We apply our adapted version of Loukas variation edges coarsening algorithm with n, = 10%...
For the optimization hyperparameters as discussed previously in the appendix, choose - is initialized with the non zero coefficients Parp. We use a SGD optimizer with momentum of 0.9, learning rate Ir 0.05 and 200 epochs.
P is initialized with the non zero coefficients of PMr.. We use SGD optimizer with momentum of 0.9, learning rate [r 0.01 and 200 epochs.
Pg is initialized with the non zero coefficients of Popt and X = 0.01 and a threshold of 0.001 enforce the sparsity. We use SGD optimizer with momentum of 0.9, learning rate ir = 0.01 and 200 epochs.
penalty coefficient
G.1 Hyperparameters for Tab.
For the GCN, for both Cora and CiteSeeer we have 3 convolutional layers with the hidden dimensions [256, 128]. We use an Adam Optimizer with a learning rate = 0.01 and weight decay wed 0.001.
For the SGC model on Cora and Citeseer we make propagations as preprocessing for the features. We use an Adam Optimizer with a learning rate Ir 0.1 and weight decay wd 0.001.
G.2 Sparsity of the reduction matrices for Tab.
Table 4: Number of non zero elements for the different reduction matrices of Tab.
Cora
Citescer
#Non coefficients
0.3
0.5
0..7
0.3
0.5
0.7
Lankas
2,485
2,485
2,485
2,120
2,120
2,120
PAP
2,485
2,485
2,485
2,120
2,120
2,120
Popt
4,315,200
3,080,144 144
1,846.584
3,136,320
2,235.527
1,341,714
P
2,485
2,485
2,485
2,120
2,120
2,120
Pg
2,261,446
2,202,595
1,596.687
1,505.412
1,533,820
1,131,521
P
2,822
3,003
2,881
2,629
3,505
3,278
Popt (coeff 0.001)
583,431
766,439
580,971
537,353
594,807
421,027
Pr (coeff 0.001)
5,735
46,080
99,288
18,601
24,874
79,609
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes]
Justification: This paper is mainly theoretical. The abstract and introduction present the theorems and their consequences.
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 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 other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors? Answer:
[Yes]
Justification: The limitations of the experiments, in particular the scalability the method, are discussed in the main body of the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors 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, 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect 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 speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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 faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The proofs are provided in the 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.
21

---

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 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.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The code is included as supplementary material, it can be executed 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 dataset and/or model, the authors should describe the steps taken 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, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g.. with an open-source dataset instructions for how to construct the dataset).
(d) 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. the case of closed-source models, may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The datasets are available through Yorch-Geemmtric, and the code included supplementary material. It only uses open-source Python libraries. 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/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not
22

---

reproducible, they including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
httpsccccpbbccccccccc pwwplic/guuuuioo guwdes//e//e///ee http://guudeeeeeeeubbbimiaaaa CodeSuomissss wwwaaabmmissiiioi ssionoiiccy 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 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 much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All these details are mentioned in the setup paragraph of the experiments (Sec. [5] and in the Appendix.
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, as supplemental material.
7. 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: The results in Tab. Tare averaged over ten runs and reported with standard deviations.
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, confi- dence 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, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 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 out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
23

---

Justification:
This is small-scale code, reproducible without specific computational re-
sources,
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or 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 experimental runs as well as 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 or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We confirm that our paper complies with the NeurIPS Code of Ethics. This is mainly theoretical paper, and the code uses only open-source Python libraries. Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction). 10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Given the theoretical nature of our work, we do not expect any direct societal impact. Future work on the scalability of graph coarsening algorithm may raise these questions, but this is beyond the scope of 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 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 unintentional) misuse of the technology.
If there are negative socictal 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).
11. 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, or scraped datasets)? Answer: [NA]
Justification: This paper does not present such models.

---

Guidelines:
The answer NA means that the paper poses no 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 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 best faith effort.
12. Licenses for existing assets
Question: Are the creators 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 papers for Cora and Citeseer are cited. Further details on these datasets are provided in the 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.
assets are released, the license, copyright information, and terms use in thcode. com datasets package should be provided. For popular datasets, thcode
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's 's creators.
13. 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.
Researchers should communicate the details the dataset/code/moodel as part 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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, if 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.
25

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: 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 equivalent approval/teview based on the requirements of your country institution) were obtained?
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 NeurlPS 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.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components. Please refer to our LLM policy httppppe//eeerrrp.ccc//////eeee/ for what should should be described.
26


Reviews:
[{"review_id": "PsGFWn7ZiG", "reviewer": "Reviewer_bTnS", "summary": "This paper focuses on two detailed issues in graph coarsening: 1) What are the admissible degrees of freedom for the reduction matrix? and 2) Can we improve the RSA by simply modifying the reduction matrix alone? Overall, this paper conducts an in-depth and detailed theoretical study of graph coarsening operations and achieves valuable conclusions. I appreciate the work done in this paper.", "questions": "1. Please provide corresponding experiments to support the theoretical analysis. The specific experimental issues have already been mentioned in the weaknesses section.", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.This paper is well-written and explains the background and context of the problem in detail.\n\n2.The issues addressed in this paper are highly valuable for the field.\n\n3.The theoretical analysis is solid.\n\n Weaknesses:\n\n1.However, the experiments in this paper are still insufficient. Although this is a theoretical paper, I still hope the authors can provide more experimental results to support the theoretical conclusions. If the authors further expand the experiments, I will consider increasing my score. Specifically, I would like to see results on at least five datasets, including larger-scale datasets like Arxiv, which current graph coarsening algorithms are capable of handling.", "was_revised": true, "final_justification": "After reviewing the other reviews, I have decided to raise the score to 5.", "rebuttal": "Thank you for your review and for engaging with our work. We are glad to hear you found the paper valuable for the field. Please find our response to your comment below.\n\n**Q 1)** *Please provide corresponding experiments to support the theoretical analysis*\n\nWe acknowledge the concern regarding the number of datasets evaluated. In addition to the main experiments, we would like to point out that we already included results on random geometric graphs in the appendix for the RSA minimization. \n\nIn this paper, we choose to focus our methodology on the RSA, a standard spectral objective in graph coarsening, since it allows for many interesting characterizations and intuitions pertaining to graph coarsening, as well as serves as inspiration for new reduction matrices. However, this comes with certain limitations, foremost among them the computational cost of this criterion. In particular, in our setting, we implement the RSA in a differentiable manner, which is more costly than the non-differentiable implementations that typically leverage sparse representations. This limits scalability to large graphs like OGB-Arxiv or Reddit. However, our optimization procedure is compatible with any scoring function, and designing scalable differentiable alternatives is a key direction for future work. This point will be clarified in the final version of the paper."}, {"review_id": "j0cfTcobAl", "reviewer": "Reviewer_DYWE", "summary": "This paper introduces a taxonomy of admissible families of reduction matrices for graph coarsening. The authors first extends the graph coarsening metric Restricted Spectral Approximation (RSA) by Loukas, in order to disentangle the lifting matrix and the reduction matrix. By observing the additional flexibility in defining reduction matrices, the authors proposes three nested sets of reduction matrices to optimize RSA. The authors provide concrete examples of these reduction matrix characterizations via pointers to the existing literature, and propose new choices of reduction matrices. These reduction matrices are compared empirically on the RSA metric and predictive performance of GNN trained on the obtained coarsened graphs.", "questions": "1. For the sparse reduction matrices in set $E_3$, the proposed $P^*_{Q^{\\top}}$ empirically perform quite similar (within standard error bars) to the existing baselines $P_{Loukas}, P_{MP}$. Can the authors discuss their relationship in more details, either conceptually or empirically?\n\n2. The authors discuss in the introduction that \"$P$ is taken as the Moore-Penrose pseudo-inverse...In this paper, we challenge this choice and argue that there is no real reason for it.\". But the characterization of $E_3$ clearly shows the advantages of $P$ being Moree-Penrose pseudo-inverse: (1) it is sparse (share the same support as $Q$); (2) it admits a close-form given $Q$, so no further optimization is needed. From the RSA evaluation, the pseudo-inverse $P$ choice underperforms $P^*_{Q^{\\top}}$ requiring optimization. Do the authors agree? If so, I would suggest reword this discussion.\n\n3. Although the characterization of $E_1, E_2$ reduction matrices is interesting, they introduce heavy computational overhead (Appendix G.2) and seem to bring very little advantage to GNN performance (Table 1). Can the authors discuss possible sparser characterizations or more efficient implementations? \n\nMinor:\na) Definition 2 is the extended version of RSA, which differs from the one proposed by Loukas in disentangling the role of the lifting matrix and the reduction matrix. I would suggest adding the remark before/after this to remind the reader.\n\nb) The notation $\\Delta$ in Lemma 6: does it refer to the $\\Delta$-Laplacian? I didn't find it defining anywhere close to Lemma 6 nor its proof.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The proposal of a taxonomy of reduction matrices for graph coarsening is interesting and of great interest to the graph learning community.\n\n2. The paper is well written overall, with a clear exposition of the motivation and chosen sets of reduction matrices.\n\nWeakness:\n1. Graph coarsening aims to reduce computation complexity (while maintaining performance). However, for the proposed sets of reduction matrices $E_1, E_2$, they both consist of dense matrices $\\mathbb R^{n \\times N}$. This introduces a heavy memory and time complexity overhead, as shown in Appendix G.2 (e.g., these reduction matrices consists of millions of parameters to be optimized for a medium size graph Cora or Citeseer). The authors do not provide any analysis on complexity and discussion on runtime.\n\n2. The empirical validation is only carried out on two Cora and Citeseer benchmark graphs (with additional synthetic geometric random graphs). The paper can be further strengthened by a more thorough evaluation on more benchmark graphs including both homophilous ones and heterophilous ones (e.g., from [1] or [2], or even random graphs say a two-block stochastic block model where across-block connection probability is higher than within-block probability). \n\nReferences\n[1] Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova, L. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. ICLR 2023\n[2] Pei, H., Wei, B., Chang, K. C. C., Lei, Y., & Yang, B. Geom-GCN: Geometric Graph Convolutional Networks. ICLR 2020", "was_revised": true, "final_justification": "The authors have addressed my main concern on complexity and applicability of the method (e.g., scalability, heterophilous graphs), and I have raised my score from 3 to 4. The complexity/scalability aspect is also brought up in other reviews (e.g., QiV5, btns), and the authors responded by highlighting the bottleneck $O(N^3)$ in the Laplacian computation for optimizing the chosen metric RSA. The authors acknowledged that considering other more computationally efficient metric is an interesting future direction but out of the scope of the current work. Considering this limitation, I thus recommend a weak acceptance of the paper.", "rebuttal": "Thank you for your review and feedback. We are encouraged that you found the work of interest to the graph learning community. Please find our responses to your comments below.\n\n**W1)** *This introduces a heavy memory and time complexity overhead, as shown in Appendix G.2 (e.g., these reduction matrices consists of millions of parameters to be optimized for a medium size graph Cora or Citeseer). The authors do not provide any analysis on complexity and discussion on runtime.*\n\nAs $E_1$ does not admit a closed-form expression, we focus our response on $E_2$ and $E_3$. Note that part of the discussion below is already present in the paper, we will complete it in the final version.\n\nIn $E_2$, at each optimization step we update the full matrix $P$ of size $n\\times N$. In $E_3$, we impose the support and thus we optimize the $N$ non-zero values of the matrix $P$. This affects the memory complexity: $E_2$ is only manageable for medium size graphs, while $E_3$ scales linearly in $N$. In terms of time complexity, $E_2$ is highly parallelizable and the total runtime for the 200 iterations on a modern GPU last 5 seconds for Cora and Citeseer. $E_3$ is more memory efficient, but the renormalization tricks make it slightly slower. Even on CPU, for Cora and Citeseer, the two optimization processes remain manageable and take less than 3 minutes, which is reasonable for a preprocessing done only once.\n\nDespite this, the main bottleneck that prevents scalability for now is in fact in the computation of the chosen scoring function: the differentiable RSA. It requires the square root of the original Laplacian which is in $\\mathcal{O}(N^3)$. While we limit this paper to the RSA because it is a classical criterion in graph coarsening that allows for interpretability as well as serves as inspiration for new reduction matrices, designing new, more scalable scoring function is a major path for future work.\n\n**W2)** *The paper can be further strengthened by a more thorough evaluation on more benchmark graphs including both homophilous ones and heterophilous ones (e.g., from [1] or [2], or even random graphs say a two-block stochastic block model).*\n\nSimilarly to the previous response, these limitations are mostly due to our choice to focus on the RSA, noting however that our optimization procedure is compatible with any scoring function, allowing future extensions to alternative objectives.\n\nIndeed, larger graphs such as OGB-Arxiv and Reddit were not included due to the high computational cost of optimizing a differentiable version of RSA in $\\mathcal{O}(N^3)$.\n\nSimilarly, heterophilous datasets are not really suitable for evaluating the RSA score, which is specifically designed to promote the preservation of low-frequency signals, by definition not compatible with heterophily. Indeed, an important direction for future work is to design scalable, heterophily-aware scoring functions. Exploring this idea in synthetic settings, such as a two-block stochastic block model, could serve as a natural first step.\n\nThis point will be further emphasized in the discussion and limitations section of the final version.\n\n**Q1)** *For the sparse reduction matrices in set $E_3$, the proposed $P ^\\ast_{Q^\\top}$\nempirically perform quite similar (within standard error bars) to the existing baselines $P_{MP}$, $P_{Loukas}$ . Can the authors discuss their relationship in more details, either conceptually or empirically ?*\n\nAs expected, the proposed $P ^\\ast_{Q^\\top}$ outperforms the naive baselines $P_{MP}$ and $P_{Loukas}$ *in minimizing the RSA score*. However, the connection between RSA and GNN performance proved in [22] is sometimes imperfect on real data, which is not really surprising as it is only an upper-bound and other criteria probably comes into play (sparsity of the message-passing, etc.). This suggests that future work should explore alternative scoring functions, or even consider directly optimizing the reduction matrix in a supervised manner, which we avoided here to keep the spirit of an unsupervised, general-purpose method not linked to any particular task. This discussion will be added in the final version.\n\n**Q2)** *But the characterization of $E_3$ clearly shows the advantages of being Moree-Penrose pseudo-inverse [...]*\n\nAs the reviewer highlights, the Moore Penrose inverse is indeed a good choice in practice as it is sparse and has a close form given $Q$. But as shown in figure 2, $P ^\\ast_{Q^\\top}$ has a lower RSA. For the GNN application, since again the link between GNN performance and RSA is not perfect, the performance between these different choices can vary. This could change with another scoring function, as the proposed optimization process could work for any criterion. \n\n**Q3)** *Can the authors discuss possible sparser characterizations or more efficient implementations?*\n\nSee our response to Weakness 1. Designing new scoring functions that scale to large graphs, by better leveraging the sparsity or allowing intermediate support sizes is a promising direction for future work, but remains out of scope for this paper.\n\n**Q4)** (minors): *Definition RSA and $\\Delta$ notation*\n\nThank you for the suggestion on the RSA definition. We agree that this addition will improve clarity, and we will make sure to include it in the final version of the paper.\n\nFor the second point, $\\Delta$ is indeed the diagonal matrix that it used for the normalization of the considered $\\Delta$-Laplacian. We will make it clearer by adding an example for the combinatorial Laplacian in Lemma 6."}, {"review_id": "50ysqUUCG5", "reviewer": "Reviewer_QiV5", "summary": "This paper studies the admission space of reduction matrices and its optimization towards preserving Restricted Spectral Approximation (RSA) in graph coarsening. Specifically, the authors observe that the coarsening can be solely defined by the lifting matrix and then decouple the relation between the lifting and reduction matrix, which is typically chosen as pseudo-inverse of each other. With this, they reveal three admission spaces of the reduction matrix, from projection to generalized reflexive inverse and to generalized reflexive inverse of the same support. They then study optimizing the reduction matrix for the RSA objective and discuss six reduction matrices under different admission spaces and sparsity constraints. Experiments have been conducted on two small datasets to demonstrate the RSA preservation for different reduction matrices and their impacts on the accuracy of the GNN application.", "questions": "Comments:\n\nThe lifting and reduction matrices are often considered to be pseudo-inverse of each other with the intuition that the two processes are inverse. This paper defines the adjacency matrix of the coarsened graph as (1) and optimizes P. Would it be possible to use P to define the coarsened graph and then optimize Q for the RSA target instead? \n\nThe well-partitioned property may not be always true in real-life coarsening tasks with possibly overlapping clusters/supernodes. What are known results for the overlapping setting?\n\nThe computation overhead for getting different reduction matrices should be provided to offer guidance in the selection.\n\nI’m quite curious on the empirical performance of GNN on the RSA approximation and data-driven graph pooling methods [39,13,34]. RSA may have better generalization on different downstream tasks while data-drive methods are optimized for specific task and data.\n\nTypo: Line 135: a eigen-subspace.\n\nLine 43: “In virtually all works on graph coarsening, these two matrices are simply pseudo-inverse of each other, and both can represent the “graph coarsening” indifferently.” and Line 85: “These methods use interchangeably the reduction and the lifting matrix by choosing one as the transposed of the other.” Graph coarsening and pooling seem to be similar, if not the same. Why does one set the two matrices to be pseudo-inverse of each other and the other set them to be transposed of each other? Please clarify.", "limitations": "I did not see the discussion but this work may not have clear negative societal impacts that have to be explained. Should add limitation discussions though.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper establishes a good understanding between the relations between the lifting and reduction matrices and pointed out the lifting matrix defines the coarsening while the reduction matrix can affect the RSA preservation and thus can be optimized towards a better preservation. It is a solid paper that builds on top of the RSA objective and can be of great reference for similar research in graph coarsening.\n\nAnalyze the three levels of admission spaces for the reduction matrix and formulate the optimization over the admission spaces. Discuss the optimization and special properties of each reduction matrix, ranging from typical Moore-Penrose inverse to RSA optimization with a sparsity constraint. Although I did not review the proof in Appendix, the conclusions look natural and should be correct.\n\nWhile the main contribution is in theory, the authors have performed experiments to study the empirical performance on the RSA optimization and the impacts on downstream GNN application.\n\nWeaknesses:\n\nThe spectral guarantee using RSA proposed in 2019 is only one type of key properties graph coarsening approximates. It is not clear how the developed optimization and coarsening framework have significant impacts on other types of graph coarsening objective.\n\nThe experiments were conducted on small-scale graphs, while this is a common problem for spectral methods. The empirical computation costs for different optimizations are missing and should be reported.", "was_revised": true, "final_justification": "The authors answered well in the rebuttal and I am keeping my score.", "rebuttal": "Thank you for your review and feedback. We appreciate your positive assessment and have addressed your comments below.\n\n**W1)** *It is not clear how the developed optimization and coarsening framework have significant impacts on other types of graph coarsening objective.*\n\nAlthough we focus on optimizing the RSA score in this work, as it is a standard and interpretable objective in graph coarsening, the proposed framework is general and can be applied to other scoring functions, including other graph coarsening objectives. This flexibility enables broader applicability beyond RSA.\n\n**W2)** *The experiments were conducted on small-scale graphs, while this is a common problem for spectral methods. The empirical computation costs for different optimizations are missing and should be reported.*\n\nA discussion on the size of the optimized matrices and on large-scale graphs is already in the main paper to some extent, but we acknowledge that it could be extended. We briefly do so below. This discussion will be included in the final version of the paper.\n\nIn $E_2$ at each optimization step we update the full matrix $P$ of size $n\\times N$. This affects the memory complexity: $E_2$ is somewhat manageable for medium size graphs only. This is why we introduce $E_3$ with a support constraint, which is manageable for large graphs. \nEmpirically, $E_2$ is highly parallelizable and the total runtime for the 200 iterations on a modern GPU last 5 seconds for Cora and Citeseer. $E_3$ is more memory efficient, but the renormalization tricks slightly slower it. Even on CPU, for Cora and Citeseer, the two optimization processes remain manageable and take less than 3 minutes.\n\nHowever, the main bottleneck of computational complexity lies in the computation of the scoring function : the differentiable RSA. Its computation requires the square root of the original Laplacian which is in $\\mathcal{O}(N^3)$ and not feasible for large graphs such Reddit or OGB-Arxiv. While we limit this paper to the RSA because it is a classical criterion in graph coarsening that allows for interpretability as well as serves as inspiration for new reduction matrices, designing new, more scalable scoring function is a major path for future work.\n\n**Q1)** *Would it be possible to use P to define the coarsened graph and then optimize Q for the RSA target instead?*\n\nThe asymmetry between $P$ and $Q$ is indeed the key point of the paper. In the classical definition of graph coarsening, it is $Q$ that is used to define the coarsened adjacency matrix $A_c$ and the coarsened Laplacian $L_c$ (which preserve the isometry with respect to $\\lVert \\cdot \\rVert_{L_c}$), and thus $Q$ contains the structural information of the coarsening. In this framework, it therefore could not be easily optimized for the RSA target instead of $P$. Of course, one could imagine an entirely different framework for graph \"coarsening\" (since it is a vague problem at best) where constraints would lie elsewhere, however the framework that we use is the one largely admitted and employed in the literature. This will be clarified in the final version of this work.\n\n**Q2)** *The well-partitioned property may not be always true in real-life coarsening tasks with possibly overlapping clusters/supernodes. What are known results for the overlapping setting?*\n\nWe appreciate the reviewer’s insightful suggestion. In the overlapping setting, it may be possible to relax the well-partitioned assumption by considering *a minima* a full-rank $Q$ matrix (i.e., $\\operatorname{rank}(Q)= n $). In this case, the first two mathematical characterizations of $E_1$ and $E_2$ would still hold. However, computing the Moore–Penrose inverse becomes less convenient, as $Q^TQ$ is no longer diagonal and thus harder to invert. This nuance will be clarified in the final version of the paper. Future work could explore more intuitive ways to relax the well-partitioned assumption on the $Q$ matrix, beyond a simple rank-based argument: to remain interpretable and still represent a \"coarsening\", as opposed to a general reduction, the \"overlapping\" part should be quantified and limited. This represents an interesting mathematical challenge. We will add this discussion as outlooks.\n\n**Q3)** *The computation overhead for getting different reduction matrices should be provided to offer guidance in the selection.*\n\nPlease refer to Weakness 2 answer.\n\n**Q4)** *I’m quite curious on the empirical performance of GNN on the RSA approximation and data-driven graph pooling methods [39,13,34].*\n\nWe thank the reviewer for this interesting question. A possible future work indeed would be to consider this optimization process as part of the downstream task training. The GNN would be trained simultaneously with the reduction matrix $P$ and both the coarsened features $X_c = PX$ and the propagation scheme would be recomputed at each epoch $S_c = QSP$ with considering only one differentiable scoring function : the loss. This would slower the GNN training on the coarsened graph, and it could be hard to train as the number of hyperparameter would be important, but this idea seems promising for future works. We will include this remark in the outlook of the final paper.\n\n**Q5)** *Graph coarsening and pooling seem to be similar, if not the same. Why does one set the two matrices to be pseudo-inverse of each other and the other set them to be transposed of each other? Please clarify.*\n\nGraph coarsening and graph pooling are often likened in graph machine learning. Although similar, pooling is usually differentiable and used end-to-end to optimize GNN performance, but pays less attention to the lifting step (e.g. from a spectral point of view) and often uses transposes for computational efficiency. In contrast, coarsening is a *preprocessing* step designed to reduce memory and computation time for large graphs, and designed to promote information-preservation, often in an unsupervised manner. In the literature, it typically relies on pseudo-inverses for both lifting and reduction. It is worth noting that some pooling approaches also employ pseudo-inverses. So the two approaches may employ very similar tools, but often have slightly different objectives and methods. In our paper, we focus on unsupervised, spectral methods, which is closer to coarsening."}, {"review_id": "HfwrIB2x0Z", "reviewer": "Reviewer_mmpw", "summary": "Graph coarsening is an important algorithmic primitive for many pipelines involving graphs in ML, such as graph/geometric deep learning, but also computational methods working on or with graphs beyond ML. There are celebrated results on spectral approximations of large graphs by sparser ones (see the work of Spielman for instance) but fewer strong theoretical results on reducing/coarsening large graphs to smaller ones with mathematical guarantees. \n\nIn ML, it is of particular importance to preserve features defined over the graph and that can represent external signals or graph structure. This paper builds on and extends previous work by Lukas, widening the coarsening and lifting operations that lead to preserved spectral properties (defined via a stable embedding condition). A systematic exploration of the \"design space\" of these operations allow the authors to propose several new operations and recover older ones. \n\nExperimental validation suggest that these techniques are particularly suited for homophilic/smooth signals, but less so when this restriction is lifted.", "questions": "- Please clarify the role of graph structure (beyond the example of the random geometric graph) and graph signal models (is the method suited for non-smooth graph signals at all)\n- Given the importance of Kron reduction in many fields (it has been used in graph signal processing/ML), and its well-studied spectral properties, I think it deserves a more elaborate discussion: can you compare both approaches, what would be the advantages/disadvantages of both. Kron reduction can also be (at least partially) inverted using its spectral approximation properties, is there any link to what is being proposed in this paper ?", "limitations": "Yes, except maybe on the practical limitations of the methods. I do not consider this critical though.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- very clearly written, the paper is easy to follow with crystal motivations\n- strong mathematical results, even if limited by the spectral objectives (which one must say are the norm in this field)\n\nWeaknesses:\n- how important is the structure of the graph ?\n- it is hard to tell whether the theoretical motivation results in practical gains \n- practical results are limited to rather small graphs where one could question the usefulness of the whole endeavour", "was_revised": true, "final_justification": "Having interacted with the authors and read their rebutal, I think the paper has gained in intelligibility and impact. I have therefore updated ymy score accordingly", "rebuttal": "Thank you for your review and positive comment on the clarity of the motivation. We address your remarks below.\n\n**W1, Q1)** *Please clarify the role of graph structure (beyond the example of the random geometric graph) and graph signal models (is the method suited for non-smooth graph signals at all)*\n\nWe chose to focus on the RSA score as it is a standard spectral objective in graph coarsening. However, our optimization procedure is compatible with any scoring function, allowing future extensions to alternative objectives.\nThe role of the graph structure in our approach relies heavily on the Laplacian and its low-frequency components, as shown in the first lemma. The RSA is designed to estimate the reconstruction of smooth (low-frequency) signals within a preserved subspace $\\mathcal{R}$. Exploring alternatives scoring functions designed for different types of signals, including non-smooth ones is a promising direction but remains out of scope for this paper.\n\n**W2)** *it is hard to tell whether the theoretical motivation results in practical gains*\n\nThis works effectively shows that the RSA could be optimized through the reduction matrices in different subsets. However, the connection between RSA and GNN performance, proved in a prior work [22] (with a theoretical upper bound that may be quite loose), is sometimes not perfectly reflected in our results, as other phenomena probably comes into play. This suggests that future work should explore alternative scoring functions, or even consider directly optimizing the coarsening in a supervised manner. This point will be added to the discussion on future work in the final version.\n\n**W3)** *practical results are limited to rather small graphs where one could question the usefulness of the whole endeavour*\n\nIn our setting, RSA is made differentiable, which is more costly than the non-differentiable objectives typically used with sparse methods. This limits scalability to large graphs like OGB-Arxiv or Reddit. Designing scalable differentiable scoring functions is a key direction for future work. This point will be clarified in the final version of the paper. \n\n**Q2)** *Given the importance of Kron reduction in many fields (it has been used in graph signal processing/ML), and its well-studied spectral properties, I think it deserves a more elaborate discussion: can you compare both approaches, what would be the advantages/disadvantages of both. Kron reduction can also be (at least partially) inverted using its spectral approximation properties, is there any link to what is being proposed in this paper?*\n\nKron reduction plays a central role in many areas of graph machine learning. In the context of graph coarsening, it can be seen as an alternative to Loukas' coarsening algorithm. Since this algorithm was specifically designed to minimize the RSA, we focus our experiments on it. However, our optimization scheme is compatible with any scoring function or coarsening method. The coarsening algorithm is only used to define the contraction sets and thus the lifting matrix $Q$, before optimizing the reduction matrix $P$. We will clarify in the final version that the proposed optimization method applies to any coarsening algorithm."}]

Author rebuttal:

Meta-review: This paper introduces a taxonomy of admissible families of reduction matrices for graph coarsening. The authors first extend the graph coarsening metric Restricted Spectral Approximation (RSA) by Loukas, in order to disentangle the lifting matrix and the reduction matrix. By observing the additional flexibility in defining reduction matrices, the authors propose three nested sets of reduction matrices to optimize RSA. The authors provide concrete examples of these reduction matrix characterizations via pointers to the existing literature, and propose new choices of reduction matrices. These reduction matrices are compared empirically on the RSA metric and predictive performance of GNN trained on the obtained coarsened graphs.

The reviewers were positive about this paper, specifically stating that the topic is of interest to the general GNN community, and that the paper is clear and well written.
As indicated by the reviewers, scalability is a main limitation of the approach studied in this paper, as the procedure is cubic in the number of vertices.
Decision: Accept (poster)