A basic premise in graph signal processing (GSP) is that a graph encoding pairwise (anti-)correlations of the targeted signal as edge weights is leveraged for graph filtering. Existing fast graph sampling schemes are designed and tested only for positive graphs describing positive correlations. However, there are many real-world datasets exhibiting strong anti-correlations, and thus a suitable model is a signed graph, containing both positive and negative edge weights. In this paper, we propose the first linear-time method for sampling signed graphs, centered on the concept of balanced signed graphs. Specifically, given an empirical covariance data matrix , we first learn a sparse inverse matrix , interpreted as a graph Laplacian corresponding to a signed graph . We approximate with a balanced signed graph via fast edge weight augmentation in linear time, where the eigenpairs of Laplacian for are graph frequencies. Next, we select a node subset for sampling to minimize the error of the signal interpolated from samples in two steps. We first align all Gershgorin disc left-ends of Laplacian at the smallest eigenvalue via similarity transform , leveraging a recent linear algebra theorem called Gershgorin disc perfect alignment (GDPA). We then perform sampling on using a previous fast Gershgorin disc alignment sampling (GDAS) scheme. Experiments show that our signed graph sampling method outperformed fast sampling schemes designed for positive graphs on various datasets with anti-correlations.

A basic premise in graph signal processing (GSP) is the existence of an underlying graph capturing pairwise similarities/correlations between nodes, using which graph filtering tasks such as denoising and interpolation are performed. In practice, node-to-node similarities often evolve over time, and thus, ideally, the graph structure should adapt accordingly. In this paper, we model the temporal changes in the adjacency matrix between two consecutive time instants as a low-rank matrix. Specifically, given an initial graph structure, we jointly interpolate a partial signal and estimate a graph at later times using graph signal smoothness priors and a low-rank prior for the adjacency difference matrix. We alternate optimization steps: given a fixed graph, the signal is computed as a solution to a linear system using conjugate gradient (CG), and given a fixed signal, the adjacency matrix is optimized via a new variant of proximal gradient descent (PGD). Experiments show that our joint optimization produces better interpolation results than existing graph learning schemes.

In agronomics, predicting crop yield at a per field / county granularity is important for farmers to minimize uncertainty and plan seeding for the next crop cycle. While state-of-the-art prediction techniques employ graph convolutional nets (GCN) to predict future crop yields given relevant features and crop yields of previous years, a dense underlying graph kernel requires long training and execution time. In this paper, we propose a graph sparsification method based on the Fiedler number to remove edges from a complete graph kernel, in order to lower the complexity of GCN training / execution. Specifically, we first show that greedily removing an edge at a time that induces the minimal change in the second eigenvalue leads to a sparse graph with good GCN performance. We then propose a fast method to choose an edge for removal per iteration based on an eigenvalue perturbation theorem. Experiments show that our Fiedler-based method produces a sparse graph with good GCN performance compared to other graph sparsification schemes in crop yield prediction.

In graph signal processing (GSP), an appropriate underlying graph encodes pairwise (anti-)correlations of targeted discrete signals as edge weights. However, existing fast graph sampling schemes are designed and tested for positive graphs describing only positive correlations. In this paper, we show that for datasets with inherent strong anti-correlations, a suitable graph structure is instead a signed graph with both positive and negative edge weights, and in response, we propose a linear-time signed graph sampling method. Specifically, given an empirical covariance data matrix ${\mathbf{\bar C}}$, we first employ graphical lasso to learn a sparse inverse matrix $\mathcal{L}$, interpreted as a generalized graph Laplacian for signed graph $\mathcal{G}$. We then propose a fast signed graph sampling scheme containing three steps: i) augment $\mathcal{G}$ to a balanced graph ${\mathcal{G}_B}$, ii) align all Gershgorin disc left-ends of corresponding Laplacian ${\mathcal{L}_B}$ at smallest eigenvalue ${\lambda _{\min }}\left( {{\mathcal{L}_B}} \right)$ via similarity transform ${\mathcal{L}_p} = {\mathbf{S}}{\mathcal{L}_B}{{\mathbf{S}}^{ - 1}}$, leveraging a recent linear algebra theorem called Gershgorin disc perfect alignment (GDPA), and iii) perform sampling on ${\mathcal{L}_p}$ using a previous fast Gershgorin disc alignment sampling scheme (GDAS). Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on two political voting datasets.

Transform coding to sparsify signal representations remains crucial in an image compression pipeline. While the Karhunen-Loève transform (KLT) computed from an empirical covariance matrix ${\mathbf{\bar C}}$ is theoretically optimal for a stationary process, in practice, collecting sufficient statistics from a non-stationary image to reliably estimate ${\mathbf{\bar C}}$ can be difficult. In this paper, to encode an intra-prediction residual block, we pursue a hybrid model-based / data-driven approach: the first K eigenvectors of a transform matrix are derived from a statistical model, e.g., the asymmetric discrete sine transform (ADST), for stability, while the remaining N −K are computed from ${\mathbf{\bar C}}$ for data adaptivity. The transform computation is posed as a graph learning problem, where we seek a graph Laplacian matrix minimizing a graphical lasso objective inside a convex cone sharing the first K eigenvectors in a Hilbert space of real symmetric matrices. We efficiently solve the problem via augmented Lagrangian relaxation and proximal gradient (PG). Using open-source WebP as a baseline image codec, experimental results show that our hybrid graph transform achieved better coding performance than discrete cosine transform (DCT), ADST and KLT, and better stability than KLT.

Learning a suitable graph is an important precursor to many graph signal processing (GSP) pipelines, such as graph signal compression and denoising. Previous graph learning algorithms either i) make assumptions on graph connectivity (e.g., graph sparsity), or ii) make edge weight assumptions such as positive edges only. In this paper, given an empirical covariance matrix ${\mathbf{\bar C}}$ computed from data as input, we consider an eigen-structural assumption on the graph Laplacian matrix L: the first K eigenvectors of L are pre-selected, e.g., based on domain-specific criteria, and the remaining eigenvectors are then learned from data. One example use case is image coding, where the first eigenvector is pre-chosen to be constant, regardless of available observed data. We first prove that the subspace $\mathcal{H}_{\mathbf{u}}^ + $ of symmetric positive semi-definite (PSD) matrices with the first K eigenvectors being {uk} in a defined Hilbert space is a convex cone. We then construct an operator to project a given positive definite (PD) matrix L to $\mathcal{H}_{\mathbf{u}}^ + $, inspired by the Gram-Schmidt procedure. Finally, we design an efficient hybrid graphical lasso / projection algorithm to compute the most suitable graph Laplacian matrix ${{\mathbf{L}}^ * } \in \mathcal{H}_{\mathbf{u}}^ + $ given ${\mathbf{\bar C}}$. Experimental results show that given the first K eigenvectors as a prior, our algorithm outperforms competing graph learning schemes using a variety of graph comparison metrics.