An official website of the United States government
Abstract A graph is said to be ‐free if it does not contain any subdivision of as an induced subgraph. Lévêque, Maffray and Trotignon conjectured that every ‐free graph is 4‐colorable. In this paper, we show that this conjecture is true for the class of {, diamond, bowtie}‐free graphs, where a diamond is the graph obtained from by removing one edge and a bowtie is the graph consisting of two triangles with one vertex identified.
more »
« less
A Windowed Digraph Fourier Transform
We propose a methodology to carry out vertex-frequency analyses of graph signals, with the goal of unveiling the signal’s frequency occupancy over a localized region in the network. To this end, we first introduce localized graph signals in the vertex domain, by defining windows that are localized around each node by construction. Recent directed graph Fourier transform (DGFT) advances facilitate the frequency analysis of said localized signals, to reveal the signal’s energy distribution in a way akin to a spectrogram in the vertex-frequency plane. We then learn a set of windows by applying gradient descent method to an optimization problem governed by penalty parameters in the spectral domain. We also argue about the tradeoff between the resolution in the vertex and frequency domains based on the said parameters. We evaluate the performance of the proposed windowed GFT approach through numerical experiments on synthetic and real-world graphs.
more »
« less
- PAR ID:
- 10092281
- Date Published:
- Journal Name:
- 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
- Page Range / eLocation ID:
- 7525-7529
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract Contemporary data is often supported by an irregular structure, which can be conveniently captured by a graph. Accounting for this graph support is crucial to analyze the data, leading to an area known as graph signal processing (GSP). The two most important tools in GSP are the graph shift operator (GSO), which is a sparse matrix accounting for the topology of the graph, and the graph Fourier transform (GFT), which maps graph signals into a frequency domain spanned by a number of graph-related Fourier-like basis vectors. This alternative representation of a graph signal is denominated the graph frequency signal. Several attempts have been undertaken in order to interpret the support of this graph frequency signal, but they all resulted in a one-dimensional interpretation. However, if the support of the original signal is captured by a graph, why would the graph frequency signal have a simple one-dimensional support? Departing from existing work, we propose an irregular support for the graph frequency signal, which we coin dual graph. A dual GSO leads to a better interpretation of the graph frequency signal and its domain, helps to understand how the different graph frequencies are related and clustered, enables the development of better graph filters and filter banks, and facilitates the generalization of classical SP results to the graph domain.more » « less
-
We address the problem of learning a sparsifying graph Fourier transform (GFT) for compressible signals on directed graphs (digraphs). Blending the merits of Fourier and dictionary learning representations, the goal is to obtain an orthonormal basis that captures spread modes of signal variation with respect to the underlying network topology, and yields parsimonious representations of bandlimited signals. Accordingly, we learn a data-adapted dictionary by minimizing a spectral dispersion criterion over the achievable frequency range, along with a sparsity-promoting regularization term on the GFT coefficients of training signals. An iterative algorithm is developed which alternates between minimizing a smooth objective over the Stiefel manifold, and soft-thresholding the graph-spectral domain representations of the signals in the training set. A frequency analysis of temperature measurements recorded across the contiguous United States illustrates the merits of the novel GFT design.more » « less
-
Graph neural networks (GNNs) have emerged as a powerful tool for tasks such as node classification and graph classification. However, much less work has been done on signal classification, where the data consists of many functions (referred to as signals) defined on the vertices of a single graph. These tasks require networks designed differently from those designed for traditional GNN tasks. Indeed, traditional GNNs rely on localized low-pass filters, and signals of interest may have intricate multi-frequency behavior and exhibit long range interactions. This motivates us to introduce the BLIS-Net (Bi-Lipschitz Scattering Net), a novel GNN that builds on the previously introduced geometric scattering transform. Our network is able to capture both local and global signal structure and is able to capture both low-frequency and high-frequency information. We make several crucial changes to the original geometric scattering architecture which we prove increase the ability of our network to capture information about the input signal and show that BLIS-Net achieves superior performance on both synthetic and real-world data sets based on traffic flow and fMRI data.more » « less
-
Here we consider the problem of denoising features associated to complex data, modeled as signals on a graph, via a smoothness prior. This is motivated in part by settings such as single-cell RNA where the data is very high-dimensional, but its structure can be captured via an affinity graph. This allows us to utilize ideas from graph signal processing. In particular, we present algorithms for the cases where the signal is perturbed by Gaussian noise, dropout, and uniformly distributed noise. The signals are assumed to follow a prior distribution defined in the frequency domain which favors signals which are smooth across the edges of the graph. By pairing this prior distribution with our three models of noise generation, we propose Maximum A Posteriori (M.A.P.) estimates of the true signal in the presence of noisy data and provide algorithms for computing the M.A.P. Finally, we demonstrate the algorithms’ ability to effectively restore signals from white noise on image data and from severe dropout in single-cell RNA sequence data.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ICASSP.2019.8683852
