Bespoke multiresolution analysis of graph signals

• URL: http://arxiv.org/abs/2507.19181v1
• Date: Fri, 25 Jul 2025 11:43:19 GMT
• Title: Bespoke multiresolution analysis of graph signals
• Authors: Giacomo Elefante, Gianluca Giacchi, Michael Multerer, Jacopo Quizi,
• Abstract summary: We present a novel framework for discrete multiresolution analysis of graph signals.<n>The main analytical tool is the samplet transform, originally defined in the Euclidean framework as a discrete wavelet-like construction.<n>For efficient numerical implementation, we combine heavy edge clustering, to partition the graph into meaningful patches.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel framework for discrete multiresolution analysis of graph signals. The main analytical tool is the samplet transform, originally defined in the Euclidean framework as a discrete wavelet-like construction, tailored to the analysis of scattered data. The first contribution of this work is defining samplets on graphs. To this end, we subdivide the graph into a fixed number of patches, embed each patch into a Euclidean space, where we construct samplets, and eventually pull the construction back to the graph. This ensures orthogonality, locality, and the vanishing moments property with respect to properly defined polynomial spaces on graphs. Compared to classical Haar wavelets, this framework broadens the class of graph signals that can efficiently be compressed and analyzed. Along this line, we provide a definition of a class of signals that can be compressed using our construction. We support our findings with different examples of signals defined on graphs whose vertices lie on smooth manifolds. For efficient numerical implementation, we combine heavy edge clustering, to partition the graph into meaningful patches, with landmark \texttt{Isomap}, which provides low-dimensional embeddings for each patch. Our results demonstrate the method's robustness, scalability, and ability to yield sparse representations with controllable approximation error, significantly outperforming traditional Haar wavelet approaches in terms of compression efficiency and multiresolution fidelity.

Related papers

• Graph-Dictionary Signal Model for Sparse Representations of Multivariate Data [49.77103348208835]
  We define a novel Graph-Dictionary signal model, where a finite set of graphs characterizes relationships in data distribution through a weighted sum of their Laplacians. We propose a framework to infer the graph dictionary representation from observed data, along with a bilinear generalization of the primal-dual splitting algorithm to solve the learning problem. We exploit graph-dictionary representations in a motor imagery decoding task on brain activity data, where we classify imagined motion better than standard methods.
  arXiv  Detail & Related papers  (2024-11-08T17:40:43Z)
• Sampling and Uniqueness Sets in Graphon Signal Processing [125.12453307797]
  We study the properties of sampling sets on families of large graphs by leveraging the theory of graphons and graph limits.<n>We exploit the convergence results to provide an algorithm that obtains approximately close to optimal sampling sets.
  arXiv  Detail & Related papers  (2024-01-11T22:31:48Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• Template based Graph Neural Network with Optimal Transport Distances [11.56532171513328]
  Current Graph Neural Networks (GNN) architectures rely on two important components: node features embedding through message passing, and aggregation with a specialized form of pooling. We propose in this work a novel point of view, which places distances to some learnable graph templates at the core of the graph representation. This distance embedding is constructed thanks to an optimal transport distance: the Fused Gromov-Wasserstein (FGW) distance.
  arXiv  Detail & Related papers  (2022-05-31T12:24:01Z)
• 3D Shape Registration Using Spectral Graph Embedding and Probabilistic Matching [24.41451985857662]
  We address the problem of 3D shape registration and we propose a novel technique based on spectral graph theory and probabilistic matching. The main contribution of this chapter is to extend the spectral graph matching methods to very large graphs by combining spectral graph matching with Laplacian embedding.
  arXiv  Detail & Related papers  (2021-06-21T15:02:31Z)
• Joint Inference of Multiple Graphs from Matrix Polynomials [34.98220454543502]
  Inferring graph structure from observations on the nodes is an important and popular network science task. We study the problem of jointly inferring multiple graphs from the observation of signals at their nodes. We propose a convex optimization method along with sufficient conditions that guarantee the recovery of the true graphs.
  arXiv  Detail & Related papers  (2020-10-16T02:45:15Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• Homology-Preserving Multi-Scale Graph Skeletonization Using Mapper on Graphs [5.86893539706548]
  We propose to apply the mapper construction -- a popular tool in topological data analysis -- to graph visualization. We develop a variation of the mapper construction targeting weighted, undirected graphs, called mog, which generates homology-preserving skeletons of graphs. We provide a software tool that enables interactive explorations of such skeletons and demonstrate the effectiveness of our method for synthetic and real-world data.
  arXiv  Detail & Related papers  (2018-04-03T19:18:36Z)

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.