# Matrices de réduction et de reconstruction pour la réduction de graphes

Antonin Joly, Nicolas Keriven, Aline Roumy

► To cite this version:

Antonin Joly, Nicolas Keriven, Aline Roumy. Matrices de réduction et de reconstruction pour la réduction de graphes. GRETSI 2025 - 30ème Colloque Francophone de Traitement du Signal et des Images, Aug 2025, Strasbourg, France. pp.1-4. hal-05248082

HAL Id: hal-05248082

https://hal.science/hal-05248082v1

Submitted on 10 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Matrices de réduction et de reconstruction pour la réduction de graphes

Antonin JOLY¹ Nicolas KERIVEN² Aline ROUMY²

Équipe COMPACT, INRIA-IRISA, Campus de Beaulieu, 263 Av. General Leclerc, 35042 Rennes, France

**Résumé** – La réduction de Graphe a pour objectif de diminuer la taille d'un graphe afin d'alléger son empreinte mémoire, à l'aide d'une matrice de réduction et d'une matrice de reconstruction. La plupart des algorithmes de réduction se concentrent sur la matrice de réduction et imposent une matrice de reconstruction fixée en fonction de celle-ci. Dans cet article, nous mettons en évidence le rôle central de la matrice de reconstruction, qui garantit que le résultat du processus a une structure de graphe. Ensuite, en fixant cette matrice, nous établissons une taxonomie des matrices de réduction admissibles, offrant ainsi un cadre plus flexible pour leur choix. Enfin, nous introduisons une nouvelle matrice de réduction qui obtient des garanties spectrales améliorées.

**Abstract** – Graph coarsening aims to diminish the size of the graph to lighten its memory footprint, using a coarsening matrix and a lifting matrix. Most coarsening algorithms focus on the coarsening matrix and impose a lifting matrix fixed according to it. In this paper, we highlight the crucial role of the lifting matrix, which ensures the graph structure of the process' result. Then, by fixing this matrix, we establish a taxonomy of admissible coarsening matrices, offering a more flexible framework for their choice. Finally, we introduce a new coarsening matrix that achieves improved spectral guarantees.

## 1 Introduction

Ces dernières années, de nombreuses applications en science des données et en apprentissage génèrent des graphes gigantesques [4, 1], par exemple dans les réseaux sociaux [3] ou les systèmes de recommandation [11]. Pour traiter ces graphes massifs, des méthodes de réduction de graphes ont été développées [8, 2, 7] ainsi que des méthodes d'apprentissage spécifique à ces graphes réduits [6, 5]. Ces techniques consistent à produire un graphe de taille réduite à partir d'un graphe original à l'aide d'une matrice de réduction et d'une matrice de reconstruction.

La plupart des algorithmes de réduction se concentrent sur définir la matrice de réduction en imposant une matrice de reconstruction fixée en fonction de celle-ci, le plus souvent choisissant l'inverse de Moore-Penrose. Nous verrons que la propriété assurant la structure de graphe de la réduction ne dépend que de certaines contraintes sur la matrice de reconstruction et non de la matrice de réduction. Pour une matrice de reconstruction vérifiant ces contraintes, nous nous demanderons quel est l'ensemble des matrices de réduction possible pour définir une opération de réduction-reconstruction souhaitable et si cet ensemble est caractérisable. Pour le critère spectral quantifiant la qualité de reconstruction et introduit par Loukas [8], nous montrons que les choix naïfs de matrice de réduction ne sont pas ceux produisant les meilleurs résultats. Les preuves peuvent être retrouvées à l'adresse suivante https://gitlab.inria.fr/team-compact/coarsening-and-lifting-matrix

## 2 Caractérisation du graphe réduit par la matrice de reconstruction

**Notations** Un graphe $G$ avec $N$ noeuds est décrit par sa matrice d'adjacence pondérée $A \in \mathbb{R}^{N \times N}$. On note $L \in \mathbb{R}^{N \times N}$ le laplacien combinatoire du graphe $L = D - A$ avec $D = D(A) := \text{diag}(A1_n)$ la matrice diagonale des degrés.

Une matrice $M$ est dite $\alpha$-valuée si tous ses coefficients sont 0 ou $\alpha \in \mathbb{R}$. Pour une matrice symétrique semi-définie positive (p.s.d) $L$, on note $\|x\|_L = \sqrt{x^\top L x}$ la (semi-)norme de Mahalanobis associée à $L$.

**Algorithme de réduction** Un algorithme de réduction de graphe prend comme argument un graphe $G$ de $N$ noeuds et retourne un graphe réduit $G_c$ avec $n < N$ noeuds. Le ratio de réduction est défini comme $r : r = 1 - \frac{n}{N}$. Plus la valeur de $r$ est élevée, plus le graphe est réduit. Le processus de réduction de graphe est représenté par deux matrices : une matrice de réduction $P \in \mathbb{R}^{n \times N}$ permettant de "passer" de $G$ à $G_c$, et une matrice de reconstruction $Q \in \mathbb{R}^{N \times n}$ pour l'inverse. Intuitivement, $P$ décrit le groupement des noeuds $i$ de $G$ aux "super-noeuds" $j$ de $G_c$ lorsque $P_{ji} \neq 0$, tandis que $Q$ décrit l'expansion des super-noeuds $i$ de $G_c$ aux noeuds $j$ de $G$ pour $Q_{ij} \neq 0$. Si classiquement, $P$ et $Q^\top$ ont le même support, de telle sorte qu'il existe une correspondance exacte entre groupes de noeuds et super-noeuds lors de la réduction et de l'expansion, dans ce papier ce ne sera pas forcément le cas. Nous allons voir qu'il est possible de relâcher certaines contraintes sur une de ces matrices (la matrice $P$) tout en préservant, et même améliorant, les propriétés de la réduction de graphes.

$Q$ contient les infos structurelles de $G_c$. Toutes les matrices de réduction et de reconstruction ne définissent pas un processus de réduction de graphe. Étonnamment c'est la matrice de reconstruction $Q$ et non la matrice de réduction $P$ qui assure cette propriété. En effet, seule la matrice $Q$ est classiquement utilisée dans la définition du graphe réduit par sa matrice d'adjacence ($A_c = Q^T A Q$) ou son Laplacien ($L_c = Q^T L Q$). Il est donc important de caractériser des matrices $Q$ qui définiront des graphes. Pour ce faire, nous considérons, comme Loukas [8], la classe des matrices de reconstruction **bien partitionnées** défini comme :

**Définition 1** (Matrice $Q$ bien partitionnée). On dit que $Q$ est
bien partitionnée si $Q_{ik} \neq 0 \Rightarrow \forall k' \neq k, Q_{ik'} = 0$.

L'expansion d'un super noeud de $G_c$ par $Q$ fournit un ensemble de noeuds de $G$. Dans le cas où $Q$ est bien partitionné, ces ensembles d'expansion forment une partition de l'ensemble des noeuds du graphe d'origine.

**Lemme 1 (Consistence [8]).** Soit $Q \in \mathbb{R}^{N \times n}$ une matrice de reconstruction bien partitionnée. Il y a équivalence entre les propriétés suivantes :

1. Pour tout Laplacien combinatoire $L$ de taille $N$, la matrice $L_c = Q^T L Q$ est un Laplacien combinatoire

2. $Q$ est une matrice $\alpha$-valuée pour un $\alpha \in \mathbb{R}$ arbitraire

Ainsi, cette caractérisation simple permet de s'assurer que l'on considère toujours effectivement un processus de réduction de graphes (par opposition à une réduction de dimension arbitraire). Dans ce papier, nous considérerons toujours des matrices $Q$ bien partitionnées et $\alpha$-valuées pour un certain $\alpha$ (typiquement 1). Si l'obtention de la structure de graphe après réduction dépend uniquement de la matrice $Q$, la qualité de cette réduction est en revanche évaluée à partir des deux matrices $P$ et $Q$. Dans la littérature, la relation entre ces deux matrices est généralement fixée (le plus souvent via la pseudo-inverse). Cependant, nous étudions ici des classes plus larges de matrices admissibles. Plus précisément, nous explorons dans ce papier la question suivante : étant donné $Q$ bien partitionnée et $\alpha$-valuée, quelles sont les matrices $P$ "valides" ? En existe-t-il certaines plus "optimales" ?

## 3 Taxonomie des matrices de réduction

Dans cette section, nous examinons la première des questions ci-dessus : considérant $Q$ bien partitionnée et $\alpha$-valuée, que peut-on considérer comme une matrice $P$ "valide" ?

En apprentissage et traitement de signal, l'objet important en réduction de graphe est en réalité l'opérateur de réduction-reconstruction $\Pi = QP$: en effet, étant donné un signal $x \in \mathbb{R}^N$ défini sur les nœuds de $G$, on cherchera à ce que le signal réduit $x_c = Px$ puis reconstruit $\tilde{x} = Qx_c = \Pi x$ perde le moins d"informations" possible par rapport au signal d'origine. Comme nous le verrons dans la prochaine section, cela s'exprime souvent sous la forme d'un problème d'optimisation cherchant à préserver les basses fréquences du Laplacien [8]. Cela nous donne une première piste pour caractériser les matrices $P$. En effet, une propriété cruciale de la réduction de graphe est qu'appliquer successivement des réductions-reconstructions ne dégrade pas à nouveau le signal, ou en d'autres termes, que $\Pi$ soit un projecteur $\Pi^2 = \Pi$.

**P tel que $\Pi$ projecteur.** Le choix classique, où $P$ est l'inverse de Moore-Penrose de $Q$, permet de satisfaire la propriété de projecteur. Cependant ce n'est qu'un exemple parmi une classe plus grande de matrice de réduction qui satisfont $\Pi$ projecteur. Afin de caractériser cette classe plus grande, nous rappelons tout d'abord la notion d'inverse généralisée.

**Définition 2 (Inverse Généralisée).** Soit $A \in \mathbb{K}^{m \times n}$. On considère une matrice $B \in \mathbb{K}^{n \times m}$ qui peut satisfaire les conditions suivantes :

$$ (i) \quad B \in A^g \text{ avec } A^g = \{M | AMA = A\} $$

$$ (ii) \quad A \in B^g \text{ i.e. } BAB = B $$

$$ (iii) \quad AB \text{ est Hermitienne: } (AB)^* = AB. $$

$$ (iv) \quad BA \text{ est Hermitienne: } (BA)^* = BA. $$

La matrice $B$ est dite :

* inverse généralisée de $A$ lorsqu'elle vérifie (i) ;

* inverse généralisée réflexive de $A$ si elle vérifie simultanément (i) et (ii) ;

* Moore Penrose inverse de $A$ si elle vérifie (i), (ii), (iii) et (iv).

**Remarque 1 (unicité).** l'inverse de Moore-Penrose est unique alors qu'il peut exister une infinité "d'inverse généralisée" [9].

Pour une matrice de reconstruction $Q$ bien partitionnée, on a alors le résultat suivant.

**Lemme 2 (Inverse généralisée et $\Pi$ projecteur).** Pour une matrice de reconstruction bien partitionnée $Q$ :

$$ \Pi^2 = \Pi \iff Q \in P^g $$

Ainsi, en supposant que $\Pi$ est projecteur pour une matrice $Q$ bien partitionnée, l'ensemble $\{P | Q \in P^g\}$ définit le plus grand ensemble de matrice $P$ admissible comme le montre la Fig. 1. Cependant, cet espace reste difficile à décrire, et il n'existe a priori pas d'expression analytique permettant de le parcourir facilement de manière algorithmique. Nous allons donc regarder certains de ses sous-ensemble particuliers.

**P inverse Généralisée de $Q$.** En premier lieu, il se trouve qu'il est facile de caractériser les inverses généralisées réflexives de $Q$ bien partitionnée.

**Lemme 3 (Inverse généralisée réflexive).** Pour une matrice de reconstruction $Q$ bien partitionnée et une matrice de réduction $P$ telle que $Q \in P^g$, on a l'équivalence suivante :

$$ \mathrm{rang}(P) = n \iff P \in Q^g $$

**Remarque 2.** Il est intéressant de remarquer que si on a une matrice $Q$ bien partitionnée, alors $P \in Q^g$ implique $Q \in P^g$ et $\mathrm{rang}(P) = n$ d'où l'inclusion de cet ensemble dans le précédent dans la Fig. 1. L'inclusion est néanmoins stricte car il existe en général des $P$ telles que $Q \in P^g$ mais $\mathrm{rang}(P) < n$.

Contrairement à la plupart des matrices, pour une matrice $Q$ bien partitionnée, ses inverses généralisées sont aussi réflexives. Les inverses généralisées réflexives de $Q$ peuvent être décrites avec le lemme suivant.

**Lemme 4 (Caractérisation des inverses généralisées réflexives de $Q$).** Soit $Q \in \mathbb{R}^{N \times n}$ une matrice de reconstruction bien partitionnée. Toutes les inverses généralisées réflexives de $Q$ peuvent être caractérisées comme :

$$ Q^g = \{Q^+ + M(I_N - QQ^+) | M \in \mathbb{R}^{n \times N}\} $$

avec $Q^+$ l'inverse de Moore-Penrose de $Q$.
<figure><img src="image_2.png" /><figcaption>Figure 1 – Schéma représentant l’espace de recherche des matrices de réduction P tel que Π soit un projecteur pour Q bien partitionnée, et qui est {P | Q ∈ P<sup>g</sup>} d’après Lem. 2. Q<sup>g</sup> est caractérisé par Lem. 4 et Q<sup>g</sup><sub>supp</sub> par Lem. 5</figcaption></figure>

Cette propriété nous permet, par exemple, d’envisager de
calculer un *P* “optimal” en définissant un critère de qualité ap-
proprié et en optimisant directement la matrice *M*, sous forme
close ou à l’aide d’algorithmes d’optimisation si le critère
considéré est différentiable. Il est surprenant de remarquer
que, contrairement à toutes les matrices considérées dans la
littérature, certaines matrices n’ayant pas le même support que
Q<sup>T</sup> sont acceptables. Intuitivement, Q définit la “vraie” corre-
spondance entre noeuds et super-noeuds car bien partitionnée,
tandis que P est “autorisée” à relâcher cette contrainte.

P inverse Généralisée de même support. Néanmoins, il
peut être intéressant de caractériser les P qui ont effectivement
le même support que Q$^{⊤}$. Celles-ci seront en général bien
plus creuses que les matrices précédentes, et leur manipulation
bien plus efficace en temps de calcul et mémoire.

**Lemme 5** (Inverse généralisée de même support). *Soit Q ∈ ℝ<sup>N×n</sup> une matrice de reconstruction α-valuée bien partitionnée. L'ensemble Q<sup>g</sup><sub>supp</sub> des inverses généralisées de Q ayant le même support que Q<sup>⊤</sup> sont toutes les matrices P telles que supp(P) = supp(Q<sup>T</sup>) et Σ<sup>N</sup><sub>k=1</sub> P<sub>ik</sub> = 1/α pour tout i.*

Il s'agit donc de toutes les matrices ayant le support de $Q^\top$
dont la somme des "poids" pour chaque super-noeud est égale
à $1/\alpha$. Les degrés de liberté deviennent donc les poids de
chaque noeud au sein de chaque super-noeud.

Les implications entre ces différents résultats sont résumées
dans la Fig. 1.

4 Comparaison de certaines matrices
de réduction

Maintenant que nous avons caractérisé différentes classes de
matrices *P* “admissibles”, examinons la deuxième question :
qu’est-ce qui constitue une **bonne** matrice de réduction ?

La qualité d'une réduction de graphe se mesure par sa capacité à préserver un certain sous-espace des signaux définis sur le graphe pour une opération de réduction-reconstruction Π. Plus précisément, Loukas [8] définit la notion d'Approximation Spectrale Restreinte (Restricted Spectral Approximation, RSA), qui mesure à quel point l'opérateur Π est proche de l'identité. Étant donné que Π est d'au plus rang *n* < *N*, cette propriété ne peut pas être vérifiée pour tous les signaux, mais

seulement pour un sous-espace restreint $\mathcal{R} \subset \mathbb{R}^N$. En tenant compte de cela, la constante RSA est définie comme suit.

**Définition 3** (Constante d’Approximation Spectrale Restreinte). *Soit un sous espace *R* ⊂ *R*<sup>*N*</sup>, un laplacien combinatoire *L*, une matrice de réduction *P* et une matrice de reconstruction *Q*. La constante RSA *ϵ*<sub>*L*,*Q*,*P*,*R*</sub> est définie comme

$$
\epsilon_{L,Q,P,R} = \sup_{x \in \mathcal{R}, \|x\|_L = 1} \|x - QPx\|_L \quad (1)
$$

où $\|\cdot\|_L$ est la semi-norme de Mahalanobis associé.

En pratique, $\mathcal{R}$ est souvent choisi pour être le sous espace
engendré par les vecteurs propres associés aux plus faibles
valeurs propres de $L$. Pour une matrice $Q$ fixée, classiquement
dans la littérature [8, 2, 7] le choix est de considérer la matrice
de réduction $P$ comme étant l'inverse de Moore-Penrose de $Q$
pour minimiser la RSA. Nous avons vu précédemment que la
classe des matrices possibles est plus grande, nous étudierons
danc quelques exemples bien choisis de $P$, que nous placerons
sur notre schéma Fig. 1.

**Réduction de Moore Penrose.** Dans la littérature [8, 2, 7],
le choix très majoritaire de *P* est tout simplement l’inverse de
Moore-Penrose de *Q*:

$$
P_{MP} = Q^{+} = (Q^{T}Q)^{-1}Q^{T}
$$

Pour Q bien partitionnée et α-valuée, il s’agit de la matrice
respectant les conditions du lemme 5, telle que tous les poids
au sein d’un super-noeud sont constant (égaux à 1/(αn_k) où n_k
est le nombre de coefficient non-nuls sur la ligne k). Q^T Q
étant diagonale, P_{MP} est donc de même support que Q^T et
P_{MP} ∈ Q_{supp}^g.

Vis-à-vis de la RSA, il se trouve que $P_{MP}$ est la solution
du problème d'optimisation suivant (pour $Q$ fixée) :

$$
\arg \min_{P} \sup_{x \in \mathbb{R}^N, \|x\|_2=1} \|x - QPx\|_2 \quad (2)
$$

où la minimisation porte sur *toutes* les matrices *P*. Ainsi,
ce critère est simplifié de deux manières, par rapport à la
minimisation de la constante RSA définie en (1) : 1) l'espace
$\mathcal{R}$ est remplacé par $\mathbb{R}^N$, et 2) les normes de Mahalanobis
sont remplacées par des normes euclidiennes ! Cette extrême
simplification suggère que, *même à* $Q$ *fixée*, *il est possible de*
*trouver* *P* produisant *une meilleure RSA*, ce que nous allons
faire dans la suite. Avant cela, nous examinons un autre choix
classique de la littérature.

**Réduction de Loukas** [8]. La plupart des algorithmes de réduction fonctionnent hiérarchiquement, en fusionnant itérativement des noeuds. Cela correspond à une matrice de reconstruction $Q = Q_1 \dots Q_l$. Le choix qui a été fait par Loukas [8] est de considérer la matrice de réduction qui est le produit des Moore Penrose inverses des matrices de reconstruction intermédiaires :

$P_L = Q_l^+ \dots Q_1^+$

Il est important de remarquer que cette matrice n’est pas nécessairement égale à l’inverse de Moore-Penrose de $Q$, mais qu’elle est tout de même inverse généralisée réflexive et de même support de $Q$.
**Réduction inspirée de Rao et Mitra.** Enfin, nous considérons le problème d'optimisation suivant:

$$ \arg\min_{P} \sup_{x \in \mathbb{R}^N, \|x\|_L=1} \|x - QPx\|_L \quad (3) $$

En d'autre termes, nous avons réintroduit les normes de Mahalanobis dans (2). Il se trouve que si $L$ et $L_c = Q^T L Q$ sont définies positives, alors ce problème admet une unique solution de norme minimale [10], qui est égale à $L_c^{-1} Q^T L$.

Bien que ce problème soit plus proche de la RSA comparé à (2), il subsiste tout de même deux différences : 1) il n'y a toujours pas l'espace $\mathcal{R}$, et 2) $L$ et $L_c$ ne sont techniquement pas inversibles. Néanmoins, inspiré par cette solution, nous proposons la matrice de réduction suivante :

$$ P_{rao} = L_c^+ Q^T L $$

On remarque que nous avons bien $Q \in P_{rao}^g$ comme requis par le Lemme 2, mais cependant $P_{rao} \notin Q^g$ car elle n'est pas de rang plein (voir Fig. 1). Contrairement à $P_{MP}$ et $P_L$, le support de $P_{rao}$ n'est pas le même que celui de $Q^T$ mais sa taille reste bornée par $((2|\mathcal{E}| + N) d_{max}^c)$ (avec $\mathcal{E}$ les arrêtes du graphe originel $G$, $N$ le nombre de noeuds de $G$ et $d_{max}^c$ le degré maximal des noeuds de $G_c$).

# 5 Expériences

**Remarque 3 (valeur de $\alpha$).** Toutes les propriétés de ce papier s'écrivent pour $Q \alpha$-valuée. On peut néanmoins remarquer que la valeur $\alpha = 1$ permet de conserver le volume du Graphe (la somme des poids des arrêtes du graphe). Cela justifie le choix $\alpha = 1$ dans les expériences.

**Courbe RSA.** Nous avons appliqué l'algorithme de réduction proposé par Loukas [8] à un graphe géométrique aléatoire de 1000 noeuds. Cet algorithme permet de définir une matrice de reconstruction $Q = Q_1 \dots Q_l$ de manière itérative en conservant un certain espace, ici les vecteurs propres associés aux 100 plus petites valeurs propres de $L$. A partir de cette matrice de reconstruction, nous évaluons la constante RSA associée aux trois matrices de réduction proposées : $P_L$, $P_{MP}$ et $P_{rao}$. Les résultats affichés dans la Fig. 2 montrent que la matrice de réduction de Rao obtient une meilleure constante RSA que les deux autres en particulier pour les grands ratios de réductions.

# 6 Conclusion

Dans ce papier, nous avons souligné l'intérêt de considérer des matrices de reconstruction $Q$ bien partitionnée et $\alpha$-valuée pour assurer la structure de graphe de $G_c$. Pour ces matrices $Q$, nous avons prouvé que les matrices de réduction $P$ dont $Q$ est une inverse généralisée définissent l'ensemble des matrices de réduction tel que l'opérateur de réduction-reconstruction $\Pi = QP$ soit un projecteur. Nous avons par la suite caractérisé deux-sous ensembles de ces inverses généralisées, les matrices généralisées réflexives et leur restriction au support de $Q$. Enfin, après avoir introduit la mesure de qualité spectrale de la réduction RSA, nous montrons empiriquement que les choix classiques de matrice de réduction pour une matrice de

<figure><img src="image_3.png" /><figcaption>Figure 2 – $\epsilon_{L,Q,P,\mathcal{R}}$ pour différentes matrices de réduction</figcaption></figure>

reconstruction fixée ont des moins bons scores qu'une matrice $P_{rao}$ motivée par des travaux sur le problème de moindre carré dans des espaces munis de normes de Mahalanobis. Cette observation motive l'exploration future des ensembles définis précédemment pour trouver des choix meilleurs que les heuristiques les plus communes.

# References

[1] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv:2104.13478, 2021.

[2] 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, 2024.

[3] David Ediger, Karl Jiang, Jason Riedy, David A. Bader, Courtney Corley, Rob Farber, and William N. Reynolds. Massive social network analysis: Mining twitter for social good. *Proceedings of the International Conference on Parallel Processing*, pages 583–593, 2010.

[4] 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. *Neural Information Processing Systems (NeurIPS)*, (NeurIPS):1–34, 2020.

[5] Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In *Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining*, pages 675–684, 2021.

[6] Antonin Joly and Nicolas Keriven. Graph coarsening with message-passing guarantees. *Advances in Neural Information Processing Systems*, 37:114902–114927, 2024.

[7] Manoj Kumar, Anurag Sharma, Shashwat Saxena, and Sandeep Kumar. Featured graph coarsening with similarity guarantees. In *International Conference on Machine Learning*, pages 17953–17975. PMLR, 2023.

[8] Andreas Loukas. Graph reduction with spectral and cut guarantees. *Journal of Machine Learning Research*, 20(116):1–42, 2019.

[9] Roger Penrose. A generalized inverse for matrices. In *Mathematical proceedings of the Cambridge philosophical society*, volume 51, pages 406–413. Cambridge University Press, 1955.

[10] C Radhakrishna Rao, Sujit Kumar Mitra, et al. Generalized inverse of a matrix and its applications. In *Proceedings of the sixth Berkeley symposium on mathematical statistics and probability*, volume 1, pages 601–620. University of California Press Oakland, CA, USA, 1972.

[11] Jizhe Wang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and 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.