Signal Recovery on Graphs: Variation Minimization

Siheng Chen; Aliaksei Sandryhaila; José M. F. Moura; Jelena Kovačević

Source-linked AI summary

Signal Recovery on Graphs: Variation Minimization

Siheng Chen, Aliaksei Sandryhaila, José M. F. Moura, Jelena Kovačević

arXiv:1411.7414v3Nov 26, 2014cs.SIcs.LGstat.ML

TL;DR

The paper addresses recovery of smooth graph signals from noisy, corrupted, or incomplete measurements on complex graph structures. It formulates a unified optimization problem, solves it generally with ADMM, and develops specialized methods for inpainting, matrix completion, robust recovery, and anomaly detection. The methods are validated across real-world recovery problems spanning classification, estimation, recommendation, and expert-opinion combination.

Problem
Existing signal recovery methods mainly address regular structures, whereas graph signal recovery must handle smooth signals with arbitrary graph structure and noisy, missing, or corrupted measurements.
Method
The paper models graph signal recovery as an optimization problem and uses ADMM, with nuclear- and ℓ1-norm relaxations supporting low-rank and sparse components.
Results
The proposed methods are validated on real-world problems including online blog classification, bridge condition identification, temperature estimation, recommender systems, and expert-opinion combination.
Takeaways & Limitations
Graph signal recovery provides a common formulation connecting signal inpainting, matrix completion, robust principal component analysis, and anomaly detection.

Abstract

from arXiv · show

We consider the problem of signal recovery on graphs as graphs model data with complex structure as signals on a graph. Graph signal recovery implies recovery of one or multiple smooth graph signals from noisy, corrupted, or incomplete measurements. We propose a graph signal model and formulate signal recovery as a corresponding optimization problem. We provide a general solution by using the alternating direction methods of multipliers. We next show how signal inpainting, matrix completion, robust principal component analysis, and anomaly detection all relate to graph signal recovery, and provide corresponding specific solutions and theoretical analysis. Finally, we validate the proposed methods on real-world recovery problems, including online blog classification, bridge condition identification, temperature estimation, recommender system, and expert opinion combination of online blog classification.

I. INTRODUCTION

The paper extends signal recovery to smooth signals on arbitrary graph structures, formulating a unified optimization problem and developing recovery methods for several classical tasks. It combines graph structure, low-rank signal relationships, and sparse corruption modeling, with ADMM providing a general solution.

Problem: Graph signal recovery targets smooth graph signals from noisy, missing, or corrupted measurements, including signals on directed and undirected graphs.Smoothness means neighboring vertices have similar signal samples.
General formulation: The proposed graph signal model casts recovery as an optimization problem solved generally with the alternating direction method of multipliers.ADMM updates variables sequentially while exploiting decomposition and convergence properties.
Unified recovery framework: The framework relates signal inpainting, matrix completion, and robust principal component analysis to graph signal recovery.These connections unify completion and denoising problems under graph-based assumptions.
Contributions: The paper introduces graph signal inpainting, matrix completion, anomaly detection, and robust graph signal inpainting algorithms with theoretical analysis.The contributions include estimation-error and detection-accuracy analyses for corresponding recovery problems.
Graph signal model: DSPG represents arbitrary irregular domains with graph shifts, extending classical discrete signal processing to applications including denoising, classification, semi-supervised learning, and data recovery.The graph shift is a weighted adjacency matrix representing directed or undirected connections.
Optimization formulation: The practical convex GSR formulation replaces rank with the nuclear norm and the ℓ0-norm with the ℓ1-norm to promote low rank and sparsity.This produces a feasible convex problem that is easier to solve.

IV. GRAPH SIGNAL INPAINTING

Graph signal inpainting recovers missing graph-signal entries from incomplete and noisy measurements by imposing smoothness on the corresponding graph. It is a special case of the general graph signal recovery problem and can sometimes be solved in closed form.

Formulation: Graph signal inpainting recovers missing entries from incomplete and noisy measurements while assuming smoothness with respect to the corresponding graph.The graph formulation replaces the usual consecutive-sample similarity assumption with graph-based smoothness.
Relation to GSR: Graph signal inpainting is a special case of graph signal recovery with L = 1 and β = γ = 0.These parameter choices reduce the general formulation to a single-signal inpainting problem.
Solutions: Algorithm 1 provides a general iterative solution for graph signal inpainting, while special cases admit closed-form solutions.A noiseless measurement setting is considered for deriving one such special case.

1) Noiseless inpainting:

The noiseless graph signal inpainting problem is formulated as a constrained optimization problem, with a closed-form solution obtained after block-structuring the graph operator.

The noiseless inpainting formulation imposes the observed-value constraint xM = tM.
Problem (26) is called graph signal inpainting via total variation minimization (GTVM).
Reordering nodes permits the matrix eA = (I − A)∗(I − A) to be written in block form for solving the inpainting problem.
Setting the derivative of the objective to zero yields a closed-form solution.
When eAUU is not invertible, the solution requires a pseudoinverse.

2) Unconstrained inpainting:

Unconstrained inpainting merges the observed-value condition into a regularized objective, producing GTVR and an error bound that depends on graph and measurement conditions.

GTVR merges the observed-value condition with the objective and introduces tuning parameter α to balance its two terms.GTVR is a convex quadratic problem with a closed-form solution.
Graph signal inpainting can tackle semi-supervised learning when data points are nodes, similarities are edges, and node labels form the graph signal.
The proposed inpainting solution has an upper bound on its error under the condition q < 2.
For symmetric A, q ≤ ∥I + A∥2 ≤ 2 because ∥A∥2 = 1, although q < 2 may fail for some matrices.
The error bound tightens with more measurements and depends on the smoothness of the true graph signal and the noise level of accessible measurements.Less noise in the accessible part leads to a smaller estimation error.
The analysis requires the true signal to be smooth; otherwise, the upper bound can become large and useless.

V. GRAPH SIGNAL MATRIX COMPLETION

Graph signal matrix completion extends matrix completion by treating matrix columns as smooth graph signals and develops constrained optimization and iterative projected-gradient solutions.

The graph signal matrix completion problem recovers missing entries while assuming the matrix has low rank and its columns are smooth graph signals.
The formulation is a special case of the general graph signal recovery model with α = 1 and γ = 0.
In the noise-free case, the measurement matrix contains no noise, so the formulation uses W = 0 and ǫ = 0.
The constrained method, GMCM, enforces XM = TM and solves a convex problem using projected generalized gradient descent.Each iteration solves a proximity function and projects the result onto the feasible set.
The projection preserves measured entries Tn,m for (n,m) ∈ M while retaining Xn,m for unmeasured entries (n,m) ∈ U.
The main computational cost of the iterative method is the singular value decomposition used when updating X.This cost is also present in standard matrix completion.

2) Regularization:

Regularized graph signal matrix completion replaces projection with an unconstrained convex optimization method and links nuclear-norm minimization to graph smoothness through singular vectors.

2) Regularization:: GMCR is an unconstrained convex problem solved by generalized gradient descent without projecting after each iteration.
2) Regularization:: The regularized objective combines measurement fidelity, graph total variation, and nuclear-norm minimization.The differentiable component includes ∥XM − TM∥2_F + α S2(X), while the nondifferentiable component is β ∥X∥∗.
2) Regularization:: Each generalized-gradient iteration solves a proximity function, with step size t selected by backtracking line search.
2) Regularization:: The regularized algorithm’s main computational cost is the singular value decomposition used to update X.
2) Regularization:: Lower rank naturally leads to smaller graph total variation.
2) Regularization:: Theoretical analysis relates graph total variation to the nuclear norm of X and the graph total variation of X’s left singular vectors.
2) Regularization:: When the graph shift is built from insufficient information, increasing β forces a smaller nuclear norm and consequently a smaller graph total variation.
2) Regularization:: A graph signal is smooth when it belongs to a subspace spanned by smooth left singular vectors.

VI. ANOMALY DETECTION

Anomaly detection models measurements as a smooth graph signal plus sparse, large-magnitude outliers, then separates them through ℓ1-regularized optimization. Under appropriate sparsity and smoothness conditions, the proposed formulations can detect outliers perfectly.

Anomaly detection seeks sparse, large-magnitude outliers e in measurements t = x + e, where x is a smooth graph signal.
The ideal formulation minimizes outlier sparsity while constraining the recovered graph signal's variation.
The unconstrained formulation, anomaly detection via ℓ1 regularization, combines graph-signal variation with an ℓ1 penalty on outliers and is solved by generalized gradient descent.
Theoretical analysis represents the true signal spectrally and the outliers as impulses supported on an outlier index set.
Perfect outlier detection requires sufficiently sparse outliers and a smooth graph signal that is not sparse.
Robust graph total variation regularization combines outlier detection with inpainting: it cleans accessible measurements before recovering inaccessible values.

VII. EXPERIMENTAL RESULTS

The proposed methods are evaluated on real-world recovery problems spanning blog classification and bridge monitoring, with robust graph total variation regularization implemented as Algorithm 5.

Experiments evaluate graph signal recovery methods on online blog classification, bridge condition identification, temperature estimation, and expert opinion combination.
Algorithm 5 takes a graph signal as input and returns an outlier graph signal and an output graph signal.
Online blog classification represents 1,224 political blogs as nodes in a directed hyperlink graph with normalized outgoing-edge weights.

1) Online blogs:

Bridge condition identification is evaluated using a lab-scale bridge–vehicle dynamic system with accelerometer measurements under simulated bridge conditions.

The bridge condition study builds a lab-scale bridge–vehicle dynamic system to validate indirect structural health monitoring.
Vehicle-mounted accelerometers collect acceleration signals while masses of various weights simulate different bridge-condition severities.
The experiment collects acceleration measurements from the instrumented vehicle as it travels across the bridge.

2) Acceleration signals:

The paper evaluates graph signal recovery across acceleration, weather, recommender, and classification data using graph-based inpainting and matrix completion. Results compare graph methods with baselines under varying labeling or measurement availability.

Acceleration signals: Acceleration recordings are represented by an 8-nearest-neighbor graph connecting each recording to its eight most similar recordings.The graph signal is the mass level over each acceleration signal.
Acceleration signals: The graph shift is normalized from a symmetric similarity matrix, producing an asymmetric directed graph that empirically performs better than an undirected graph.The feature vector for each recording represents its measured features.
Temperature estimation: Temperature experiments use 150 weather stations with 365 daily recordings, connected through an 8-nearest-neighbor graph based on geodesic distance.Each graph signal contains the temperatures recorded at the weather stations.
Recommender systems: The Jester dataset contains 4.1 × 10^6 ratings from 73,421 users, whose similarity graph connects each user to eight similar users.Each user’s graph signal consists of that user’s joke ratings, and normalization produces a directed graph.
Graph signal inpainting: For online blog classification and bridge condition identification, GTVR outperforms LapR at low labeling ratios, while blog-classification accuracy saturates around 95%.For bridge condition identification, GTVR yields significantly smaller MSEs than LapR at low labeling ratios; tuning parameters are selected by cross-validation.
Graph signal inpainting: Acceleration-signal recovery performance saturates at 3 in terms of MSE, potentially because PCA-derived features from complex, noisy laboratory data omit useful information.This limitation can restrict performance even when more samples are available.

1) Temperature estimation:

The paper evaluates graph signal matrix completion on temperature and rating recovery, then tests graph-based denoising and robust inpainting for expert opinions, mislabeled blogs, and signals.

Temperature estimation: GMCR outperforms all matrix completion algorithms on both RMSE and MAE for temperature estimation.The method combines graph-structure prior information with a low-rank assumption.
Rating completion for recommender system: GMCR achieves the best RMSE on Jester rating completion, while GWNMF achieves the best MAE.Both graph-based methods exploit internal information among users.
Combining expert opinions: GMCR provides the best results for combining opinions from 100 experts labeling 1224 blogs.GTVR improves accuracy by promoting smoothness in each opinion-vector column, while GMCR uses a twofold learning scheme.
Robust graph signal inpainting: RGTVR provides the most accurate classification when 1%, 2%, or 5% of blogs are labeled and 16.66% or 33.33% of those labels are wrong.The experiment evaluates robustness to mislabeled labels in semi-supervised online blog classification.
Robust graph signal inpainting: RGTVR produces the smallest MSE under the same labeling and mislabeling ratios for acceleration-signal regression.This experiment tests robustness to outliers in semi-supervised regression.

X. APPENDIX

The appendix describes an augmented-Lagrangian formulation that separates graph total variation, nuclear norm, sparse error, and accessibility constraints for alternating optimization.

Appendix: An auxiliary matrix Z duplicates X so the graph total variation and nuclear norm terms can be decomposed.A residual matrix C captures error associated with the inaccessible part of T.
Appendix: The formulation imposes T = X + W + E + C and X = Z as constraints.These constraints separate the recovered signal, low-rank component, sparse error, and inaccessible entries.
Appendix: The indicator operator assigns zero when X_n,m = 0 and +∞ otherwise.Putting the indicator in the objective is equivalent to enforcing the corresponding constraint.
Appendix: The augmented Lagrangian combines graph variation, nuclear norm, sparse-error penalty, the indicator, and two multiplier terms.The variables are minimized individually in an alternating procedure.
Appendix: Updates use matrix-soft thresholding, standard soft thresholding, closed-form solutions, and multiplier updates.The final implementation is given as Algorithm 1.