Sampling Signals on Graphs: From Theory to Applications

• URL: http://arxiv.org/abs/2003.03957v4
• Date: Tue, 11 Aug 2020 23:12:53 GMT
• Title: Sampling Signals on Graphs: From Theory to Applications
• Authors: Yuichi Tanaka, Yonina C. Eldar, Antonio Ortega, and Gene Cheung
• Abstract summary: We review current progress on sampling over graphs focusing on theory and potential applications. Although most methodologies used in graph signal sampling are designed to parallel those used in sampling for standard signals, sampling theory for graph signals significantly differs from the theory of Shannon--Nyquist and shift-invariant sampling.
• Score: 119.19108613761915
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The study of sampling signals on graphs, with the goal of building an analog of sampling for standard signals in the time and spatial domains, has attracted considerable attention recently. Beyond adding to the growing theory on graph signal processing (GSP), sampling on graphs has various promising applications. In this article, we review current progress on sampling over graphs focusing on theory and potential applications. Although most methodologies used in graph signal sampling are designed to parallel those used in sampling for standard signals, sampling theory for graph signals significantly differs from the theory of Shannon--Nyquist and shift-invariant sampling. This is due in part to the fact that the definitions of several important properties, such as shift invariance and bandlimitedness, are different in GSP systems. Throughout this review, we discuss similarities and differences between standard and graph signal sampling and highlight open problems and challenges.

Related papers

• Sampling and Uniqueness Sets in Graphon Signal Processing [136.68956350251418]
  We study the properties of sampling sets on families of large graphs by leveraging the theory of graphons and graph limits. 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)
• A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs [34.99659089854587]
  We introduce a signal sampling theory for a type of graph limit -- the graphon. We show that unique sampling sets on a convergent graph sequence converge to unique sampling sets on the graphon. We then propose a related graphon signal sampling algorithm for large graphs, and demonstrate its good empirical performance on graph machine learning tasks.
  arXiv  Detail & Related papers  (2023-11-17T16:04:31Z)
• A Geometric Perspective on Diffusion Models [57.27857591493788]
  We inspect the ODE-based sampling of a popular variance-exploding SDE. We establish a theoretical relationship between the optimal ODE-based sampling and the classic mean-shift (mode-seeking) algorithm.
  arXiv  Detail & Related papers  (2023-05-31T15:33:16Z)
• Distributional Signals for Node Classification in Graph Neural Networks [36.30743671968087]
  In graph neural networks (GNNs) both node features and labels are examples of graph signals, a key notion in graph signal processing (GSP) In our framework, we work with the distributions of node labels instead of their values and propose notions of smoothness and non-uniformity of such distributional graph signals. We then propose a general regularization method for GNNs that allows us to encode distributional smoothness and non-uniformity of the model output in semi-supervised node classification tasks.
  arXiv  Detail & Related papers  (2023-04-07T06:54:42Z)
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
  We consider graphs as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius. In a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius. We develop methods to estimate the unknown sampling density in a self-supervised fashion.
  arXiv  Detail & Related papers  (2022-10-15T08:01:08Z)
• Stratified Graph Spectra [0.0]
  This paper seeks a generalized transformation decoding the magnitudes of eigencomponents from vector-valued signals. Several attempts are explored, and it is found that performing the transformation at hierarchical levels of adjacency help profile the spectral characteristics of signals more insightfully.
  arXiv  Detail & Related papers  (2022-01-10T23:35:13Z)
• On the Importance of Sampling in Learning Graph Convolutional Networks [13.713485304798368]
  Graph Convolutional Networks (GCNs) have achieved impressive empirical advancement across a wide variety of graph-related applications. Despite their success, training GCNs on large graphs suffers from computational and memory issues. We describe and analyze a general textbftextitdoubly variance reduction schema that can accelerate any sampling method under the memory budget.
  arXiv  Detail & Related papers  (2021-03-03T21:31:23Z)
• FiGLearn: Filter and Graph Learning using Optimal Transport [49.428169585114496]
  We introduce a novel graph signal processing framework for learning the graph and its generating filter from signal observations. We show how this framework can be used to infer missing values if only very little information is available.
  arXiv  Detail & Related papers  (2020-10-29T10:00:42Z)
• A Hierarchical Graph Signal Processing Approach to Inference from Spatiotemporal Signals [14.416786768268233]
  Motivated by the emerging area of graph signal processing (GSP), we introduce a novel method to draw inference from signals. In this paper we leverage techniques to develop a hierarchical feature extraction approach. We test our approach on the intracranial EEG (iEEG) data set of the K aggle seizure detection contest.
  arXiv  Detail & Related papers  (2020-10-25T17:08:13Z)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  We propose an offline method that relies on the concept of graph signal stationarity. Our detector comes with a proof of a non-asymptotic inequality oracle.
  arXiv  Detail & Related papers  (2020-06-18T15:51:38Z)

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.