Taxonomy of reduction matrices for Graph Coarsening

• URL: http://arxiv.org/abs/2506.11743v1
• Date: Fri, 13 Jun 2025 12:55:03 GMT
• Title: Taxonomy of reduction matrices for Graph Coarsening
• Abstract summary: Graph coarsening aims to diminish the size of a graph to lighten its memory footprint.<n>Most coarsening frameworks impose a fixed relationship between the reduction and lifting matrix.<n>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.
• Score: 14.662574002430794
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Cramer-Rao Bounds for Laplacian Matrix Estimation [56.1214184671173]
  We derive closed-form matrix expressions for the Cramer-Rao Bound (CRB) specifically tailored to Laplacian matrix estimation.<n>We demonstrate the use of CRBs in three representative applications: (i) topology identification in power systems, (ii) graph filter identification in diffused models, and (iii) precision matrix estimation in Gaussian Markov random fields under Laplacian constraints.
  arXiv  Detail & Related papers  (2025-04-06T18:28:31Z)
• Beyond symmetrization: effective adjacency matrices and renormalization for (un)singed directed graphs [0.0]
  We define the concept of effective adjacency matrices that arise from the definition of deformed Laplacian operators. These effective matrices allow mapping generic graphs to a family of unsigned, undirected graphs. We show how the Hodge-Helmholtz decomposition can assist us in navigating this complexity.
  arXiv  Detail & Related papers  (2024-06-03T16:48:25Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• A Unified Framework for Optimization-Based Graph Coarsening [5.720402020129441]
  Given a large graph, graph coarsening aims to learn a smaller-tractable graph while preserving the properties of the originally given graph. The proposed framework lies in the unification of graph learning and dimensionality reduction. It is established that the learned coarsened graph is $epsin(0,1)$ similar to the original graph.
  arXiv  Detail & Related papers  (2022-10-02T06:31:42Z)
• Graph Polynomial Convolution Models for Node Classification of Non-Homophilous Graphs [52.52570805621925]
  We investigate efficient learning from higher-order graph convolution and learning directly from adjacency matrix for node classification. We show that the resulting model lead to new graphs and residual scaling parameter. We demonstrate that the proposed methods obtain improved accuracy for node-classification of non-homophilous parameters.
  arXiv  Detail & Related papers  (2022-09-12T04:46:55Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Matrix Decomposition on Graphs: A Functional View [36.85782408336389]
  We propose a functional view of matrix decomposition problems on graphs. Our framework is based on the key idea that using a reduced basis to represent functions on the product space is sufficient to recover a low rank matrix approximation.
  arXiv  Detail & Related papers  (2021-02-05T15:28:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.