An official website of the United States government
In classical signal processing spectral concentration is an important problem that was first formulated and analyzed by Slepian. The solution to this problem gives the optimal FIR filter that can confine the largest amount of energy in a specific bandwidth for a given filter order. The solution is also known as the prolate sequence. This study investigates the same problem for polynomial graph filters. The problem is formulated in both graph-free and graph-dependent fashions. The graph-free formulation assumes a continuous graph spectrum, in which case it becomes the polynomial concentration problem. This formulation has a universal approach that provides a theoretical reference point. However, in reality graphs have discrete spectrum. The graph-dependent formulation assumes that the eigenvalues of the graph are known and formulates the energy compaction problem accordingly. When the eigenvalues of the graph have a uniform distribution, the graph-dependent formulation is shown to be asymptotically equivalent to the graph-free formulation. However, in reality eigenvalues of a graph tend to have different densities across the spectrum. Thus, the optimal filter depends on the underlying graph operator, and a filter cannot be universally optimal for every graph.
more »
« less
Community Detection from Low Rank Excitations of a Graph Filter
This paper considers the problem of inferring the topology of a graph from noisy outputs of an unknown graph filter excited by low-rank signals. Limited by this low-rank structure, we focus on the community detection problem, whose aim is to partition the node set of the unknown graph into subsets with high edge densities. We propose to detect the communities by applying spectral clustering on the low-rank output covariance matrix. To analyze the performance, we show that the low-rank covariance yields a sketch of the eigenvectors of the unknown graph. Importantly, we provide theoretical bounds on the error introduced by this sketching procedure based on spectral features of the graph filter involved. Finally, our theoretical findings are validated via numerical experiments in both synthetic and real-world graphs.
more »
« less
- Award ID(s):
- 1714672
- PAR ID:
- 10064337
- Date Published:
- Journal Name:
- ICASSP 2018
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The manuscript considers multivariate functional data analysis with a known graphical model among the functional variables representing their conditional relationships (e.g., brain region-level fMRI data with a prespecified connectivity graph among brain regions). Functional Gaussian graphical models (GGM) used for analyzing multivariate functional data customarily estimate an unknown graphical model, and cannot preserve knowledge of a given graph. We propose a method for multivariate functional analysis that exactly conforms to a given inter-variable graph. We first show the equivalence between partially separable functional GGM and graphical Gaussian processes (GP), proposed recently for constructing optimal multivariate covariance functions that retain a given graphical model. The theoretical connection helps to design a new algorithm that leverages Dempster’s covariance selection for obtaining the maximum likelihood estimate of the covariance function for multivariate functional data under graphical constraints. We also show that the finite term truncation of functional GGM basis expansion used in practice is equivalent to a low-rank graphical GP, which is known to oversmooth marginal distributions. To remedy this, we extend our algorithm to better preserve marginal distributions while respecting the graph and retaining computational scalability. The benefits of the proposed algorithms are illustrated using empirical experiments and a neuroimaging application.more » « less
-
Graph Neural Networks have recently become a prevailing paradigm for various high-impact graph analytical problems. Existing efforts can be mainly categorized as spectral-based and spatial-based methods. The major challenge for the former is to find an appropriate graph filter to distill discriminative information from input signals for learning. Recently, myriads of explorations are made to achieve better graph filters, e.g., Graph Convolutional Network (GCN), which leverages Chebyshev polynomial truncation to seek an approximation of graph filters and bridge these two families of methods. Nevertheless, it has been shown in recent studies that GCN and its variants are essentially employing fixed low-pass filters to perform information denoising. Thus their learning capability is rather limited and may over-smooth node representations at deeper layers. To tackle these problems, we develop a novel graph neural network framework AdaGNN with a well-designed adaptive frequency response filter. At its core, AdaGNN leverages a simple but elegant trainable filter that spans across multiple layers to capture the varying importance of different frequency components for node representation learning. The inherent differences among different feature channels are also well captured by the filter. As such, it empowers AdaGNN with stronger expressiveness and naturally alleviates the over-smoothing problem. We empirically validate the effectiveness of the proposed framework on various benchmark datasets. Theoretical analysis is also provided to show the superiority of the proposed AdaGNN. The open-source implementation of AdaGNN can be found here: https://github.com/yushundong/AdaGNN.more » « less
-
We address the problem of inferring an undirected graph from nodal observations, which are modeled as non-stationary graph signals generated by local diffusion dynamics on the unknown network. We propose a two-step approach where we first estimate the unknown diffusion (graph) filter, from which we recover the eigenvectors of the so-called graph-shift operator (a matrix representation of the graph). We then estimate the eigenvalues by imposing desirable properties on the graph to be recovered. To carry out the initial system identification step, we assume that second-order statistics of the inputs are available. While such quadratic filter identification problem boils down to a non-convex fourth order polynomial minimization, we propose a semidefinite relaxation with provable performance guarantees. Finally, numerical tests illustrate the use of the proposed algorithm to unveil urban mobility patterns.more » « less
-
A novel reconstruction method for compressive spectral imaging is designed by assuming that the spectral image of interest is sufficiently smooth on a collection of graphs. Since the graphs are not known in advance, we propose to infer them from a panchromatic image using a state-of-the-art graph learning method. Our approach leads to solutions with closed-form that can be found efficiently by solving multiple sparse systems of linear equations in parallel. Extensive simulations and an experimental demonstration show the merits of our method in comparison with traditional methods based on sparsity and total variation and more recent methods based on low-rank minimization and deep-based plug-and-play priors. Our approach may be instrumental in designing efficient methods based on deep neural networks and covariance estimation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
