PaperlayerView exact revision on arXiv

Source-linked AI summary

Network Topology Inference from Spectral Templates

Santiago Segarra, Antonio G. Marques, Gonzalo Mateos, Alejandro Ribeiro

arXiv:1608.03008v1cs.SIphysics.soc-ph

TL;DR

The paper asks how to recover direct graph relationships from diffusion-generated signals when only spectral information is available. It estimates or receives graph eigenvectors, then optimizes compatible eigenvalues and structural properties using convex relaxations. The methods provide exact or robust recovery conditions and demonstrate effective recovery on social, brain, and amino-acid networks.

  • Problem

    The paper addresses recovering direct graph relationships from indirect dependencies observed in signals generated by diffusion on an unknown graph.

  • Method

    It estimates spectral templates from graph-signal realizations or uses available eigenvectors, then finds a compatible graph shift with desired properties such as sparsity.

  • Results

    The framework develops efficient convex-relaxation algorithms and theoretical exact and robust recovery conditions for adjacency and normalized-Laplacian shifts.

  • Takeaways & Limitations

    Experiments demonstrate recovery effectiveness on social, brain, and amino-acid networks, including improvements over comparison methods in reported evaluations.

Abstract

from arXiv · show

We address the problem of identifying a graph structure from the observation of signals defined on its nodes. Fundamentally, the unknown graph encodes direct relationships between signal elements, which we aim to recover from observable indirect relationships generated by a diffusion process on the graph. The fresh look advocated here permeates benefits from convex optimization and stationarity of graph signals, in order to identify the graph shift operator (a matrix representation of the graph) given only its eigenvectors. These spectral templates can be obtained, e.g., from the sample covariance of independent graph signals diffused on the sought network. The novel idea is to find a graph shift that, while being consistent with the provided spectral information, endows the network with certain desired properties such as sparsity. To that end we develop efficient inference algorithms stemming from provably-tight convex relaxations of natural nonconvex criteria, particularizing the results for two shifts: the adjacency matrix and the normalized Laplacian. Algorithms and theoretical recovery conditions are developed not only when the templates are perfectly known, but also when the eigenvectors are noisy or when only a subset of them are given. Numerical tests showcase the effectiveness of the proposed algorithms in recovering social, brain, and amino-acid networks.

I. INTRODUCTION

The paper infers graph shift operators from spectral templates derived from graph signals, recovering direct network relationships underlying diffusion-generated indirect dependencies. It combines graph-signal stationarity with structural objectives such as sparsity and develops convex, robust recovery methods.

  • Spectral templates: Graph-signal stationarity implies that the shift and signal covariance share eigenvectors, motivating recovery of the shift eigenbasis followed by its eigenvalues.The eigenbasis can be estimated from independent signal realizations or covariance structure.
  • Structural objectives: The framework searches among shifts consistent with spectral templates for networks satisfying desired properties, including sparsity, minimum edge-weight energy, or low maximum edge weights.The optimization can also promote fast mixing when the shift is a Laplacian.
  • Algorithms: Adjacency and normalized-Laplacian recovery use convex feasible sets and convex relaxations of nonconvex sparsity objectives to obtain efficient algorithms.The paper also develops conditions for exact recovery and handles imperfect or incomplete eigenvector information.
  • Problem: Graph topology inference seeks direct relationships encoded by a graph shift from indirect relationships produced by diffusion on observed graph signals.The observed signals are modeled as diffusions of white inputs through a graph shift.

A. A priori knowledge about the GSO

Prior structural knowledge about the graph shift is encoded through separate feasible sets for adjacency matrices and normalized Laplacians. These constraints impose graph-specific sign, symmetry, diagonal, scale, and spectral conditions.

  • Adjacency matrix: The adjacency feasible set represents undirected graphs with nonnegative weights, no self-loops, and a scale fixed by the first node’s weighted degree.The constraints respectively impose nonnegativity, symmetry, zero diagonal, and exclusion of the trivial zero shift.
  • Normalized Laplacian: The normalized-Laplacian feasible set imposes symmetry, positive semidefiniteness, unit diagonal entries, and nonpositive off-diagonal entries.It also incorporates the degree-related eigenvector associated with eigenvalue zero.
  • Normalized Laplacian: For normalized Laplacians, the degree-related eigenvector can be identified as the only spectral template whose entries have the same sign.The zero-eigenvalue constraint excludes the uninformative identity shift.
  • Extensions: The framework can accommodate other graph shift operators, including the combinatorial and random-walk Laplacians, with minor modifications to the feasible set.The paper focuses concretely on adjacency and normalized-Laplacian matrices.

B. Additional sources for the spectral templates

The inference framework accepts eigenvectors or eigenvector estimates from sources beyond observed graph-signal covariances. Thus, topology recovery remains applicable whenever suitable spectral templates are available.

  • Spectral-template sources: Topology inference problems remain applicable when eigenvectors or eigenvector estimates are available, including sources other than sampled graph-signal realizations.The paper introduces four practical settings for obtaining or using such templates.

GSO associated with orthogonal transformations.

Given an orthogonal transform or another operator’s eigenvectors, the framework constructs graph shifts sharing that eigenbasis while optimizing graph structure. It analyzes feasibility, uniqueness, and efficient sparsity recovery under these spectral constraints.

  • Orthogonal transformations: Setting the graph eigenvector matrix equal to a prescribed orthogonal transform makes the graph Fourier transform equal to that transform.The resulting shift is S = UΛU^T, with eigenvalues selected through the recovery problem.
  • Distributed operators: A prescribed distributed linear operator can be implemented through graph filtering when the graph shift shares its eigenvectors, enabling search for a sparse compatible shift.The operator’s eigenvectors provide the spectral templates for the recovery formulation.
  • Graph sparsification: Graph sparsification obtains a shift with the same eigenvectors as a given shift while optimizing structural properties such as sparsity.The given shift need not be a covariance matrix in this setting.
  • Network deconvolution: Network deconvolution is generalized by allowing the observed adjacency to be an unspecified polynomial of the sought shift rather than assuming a single-pole-single-zero filter.This yields the spectral-template formulations with eigenvectors supplied by the observed matrix.
  • Feasibility and optimization: When the feasible set has full rank conditions that make it a singleton, the objective is inconsequential; otherwise, sparsity recovery uses provably tight convex relaxations.The adjacency and normalized-Laplacian cases admit computationally efficient treatment under the stated conditions.

B. Relaxation for the sparse formulation

The paper relaxes sparse graph-shift recovery from an ℓ0 objective to convex and iteratively re-weighted ℓ1 formulations, with exact-recovery guarantees under structural conditions. The guarantees apply to adjacency and normalized-Laplacian shifts and clarify when re-weighting can recover sparsest solutions.

  • Sparse graph-shift inference replaces the nonconvex ℓ0 objective with iteratively re-weighted ℓ1-norm minimization.Small entries receive larger subsequent penalties, promoting further shrinkage toward zero.
  • Weight selection: Optimal weights can make convex recovery reproduce the sparsest solution, but those weights depend on the unknown sparsest graph and need not be reached by re-weighting.This motivates studying theoretically justified weights that can be selected a priori.
  • Adjacency matrices: For adjacency matrices, Theorem 1 guarantees coincidence between the relaxed and sparsest solutions under feasibility, rank, and dual-certificate conditions.The rank condition ensures uniqueness, while the second condition supports a dual certificate establishing minimum ℓ0 norm.
  • Recovery conditions: The adjacency recovery bound ψR < 1 is reported as tight, and sparser graphs are expected to yield smaller ψR values.Recovery can fail when ψR = 1; characterization of random graph ensembles satisfying the bound is left for future research.
  • Normalized Laplacians: The same recovery framework extends to normalized Laplacians through analogous rank and certificate conditions.Theorem 2 states the corresponding equivalence result for S = SL.

IV. IMPERFECT SPECTRAL TEMPLATES

The paper extends network topology inference to imperfect spectral templates, addressing both noisy eigenvector estimates and cases where only a subset of the templates is available.

  • Imperfect-template inference covers approximate spectral templates obtained from limited or noisy observations and incomplete template sets.The approximate templates may come from eigenvectors of a sample covariance matrix, while incomplete templates arise when signals are bandlimited.

A. Noisy spectral templates

For noisy spectral templates, the formulation permits a sparse shift whose eigenvectors remain close to the observed templates. Recovery error is bounded by the template tolerance, and consistency follows as covariance-based eigenvector estimates improve.

  • The noisy-template formulation treats the true eigenvectors as decision variables constrained to remain within prescribed distances of their observed estimates.The tolerances ϵk should reflect prior information about covariance-estimation or observation-noise imperfections.
  • The direct noisy-template formulation is non-convex because eigenvalues and eigenvectors are optimized jointly.A convex matrix-distance alternative instead searches for a feasible sparse shift close to an auxiliary shift S′.
  • Convex alternative: Matrix-distance choices determine whether closeness emphasizes shift entries or spectral similarity, with additional conic constraints available for selected eigenvectors.The Frobenius norm focuses on entrywise similarity, whereas the spectral norm focuses on the spectrum.
  • Sparse recovery: For sparse shifts, an ℓ1 relaxation of the noisy formulation can be used, with iteratively re-weighted schemes also possible.Further uncertainty, including adjacency-shift scale ambiguity, can be incorporated into the feasible set or distance definition.
  • Recovery behavior: The recovered shift is bounded in distance from the desired shift by the template tolerance multiplied by a constant depending on the noisy recovery matrix and support.As the number of observed signals increases, the sample covariance and its eigenvectors converge under the stated distinct-eigenvalue condition; zero tolerance then yields perfect recovery under the noiseless theorem conditions.

B. Incomplete spectral templates

The incomplete-template formulation uses known eigenvectors to constrain the graph shift while optimizing for sparse structure, with recovery guarantees for adjacency and normalized Laplacian shifts.

  • Problem setting: Only K of N eigenvectors may be available because of bandlimited signals or rotation ambiguity from repeated covariance eigenvalues.Ambiguous eigenspaces are handled by adding rotation constraints to the optimization problem.
  • Formulation: The optimization partially diagonalizes the shift using known templates and constrains the unknown component to the orthogonal complement of their span.The unknown component has rank at most N − K.
  • Adjacency recovery: For adjacency recovery, the rank condition requires columns of P^T indexed by the support and template-related coordinates to be full column rank.This condition is derived from the kernel intersection criterion used in the sparse recovery proof.
  • Adjacency recovery: Theorem 3 gives sufficient conditions for the relaxed adjacency problem to recover the sparsest graph from incomplete eigenvector information.The conditions involve a rank requirement and an additional certificate condition.
  • Recovery conditions: Fewer known templates generally increase ηP and make recovery less favorable, matching the empirical incomplete-template results.The normalized Laplacian case has an analogous theorem under the assumption that the zero-eigenvalue eigenvector is known.
  • Imperfect templates: Noisy and incomplete templates can be combined by introducing a separate shift variable and constraining its distance from the target shift by ε.This extends the incomplete-template formulation to imperfect spectral information.

V. NUMERICAL EXPERIMENTS

The numerical evaluation covers adjacency and normalized-Laplacian recovery, theoretical findings, imperfect templates, comparisons with existing methods, and sparsity promotion.

  • Experimental scope: Experiments evaluate both graph shifts across synthetic and real-world networks while testing theory, imperfect information, baselines, and sparsity promotion.The study includes topology recovery, theoretical corroboration, robustness assessment, state-of-the-art comparisons, and graph sparsification.

A. Topology inference from noiseless templates

Noiseless-template experiments relate recovery to problem uniqueness and matrix rank, and empirically validate the sufficient condition ψR < 1 for perfect adjacency recovery.

  • Uniqueness: ER experiments vary graph size and density, measuring singleton feasibility for adjacency and normalized-Laplacian recovery.Multiple feasible solutions occur more often when the expected number of neighbors is smaller.
  • Rank and recovery: Recovery rates are linked to the ranks of WD for adjacency and U for normalized Laplacian problems.When rank(U) degrades, uniqueness may fail even though iterative reweighting can still recover the true graph.
  • Rank and recovery: 0.92 recovery rate was obtained for N = 10 and p = 0.2, with only 8 failures among cases where rank(U) < 9.More than half of the instances had rank(U) = 9 and were uniquely and successfully recovered.
  • Theoretical validation: Whenever ψR < 1, relaxation (11) achieved perfect recovery across 1000 ER realizations.Recoveries frequently failed when ψR was equal to or just above 1, supporting tightness of the bound.

B. Topology inference from noisy and incomplete templates

Experiments show that recovery improves with more observed signals or known eigenvectors, while SpecTemp outperforms graphical lasso and correlation-based recovery for general filters.

  • Noisy templates: Brain-graph recovery error decreased monotonically as more signals were used to estimate noisy spectral templates.Increasing observations from 10^4 to 10^5 approximately divided average error by seven across patients.
  • Noisy templates: Social-network recovery error also decreased monotonically with the number of observed signals.The experiment used four unweighted, symmetric networks on 32 common nodes.
  • Baseline comparison: For general filters, SpecTemp outperformed graphical lasso and correlation-based recovery.The comparison used F-measure, which evaluates edge-support precision and recall while ignoring recovered weights.
  • Incomplete templates: Perfect recovery occurred for all four social networks when 24 eigenvectors were known, after errors above 0.85 for three networks at 17 templates.Performance improved sharply as the number of available spectral templates increased.
  • Robustness differences: Network 4 was easier to identify under imperfect templates, with error 0.224 at 19 templates versus 0.584 averaged across the other networks.The authors leave formal analysis of this robustness difference for future work.

C. Performance comparison

SpecTemp is evaluated against statistical and graph-signal-processing baselines across synthetic graph settings, signal models, and observation counts. Its advantage depends on the filter and sample regime: it is strongest for general filters and larger sample sizes, while graphical lasso excels when the precision matrix directly matches the target shift.

  • Experimental setup: SpecTemp is compared with correlation, graphical lasso, Kalofolias, and Dong et al. [8] using edge recovery, F-measure, and error metrics.The experiments cover Erdős–Rényi and Barabási–Albert graphs, multiple signal-generation models, and varying numbers of observations.
  • Adjacency recovery: For general filters H1 with 10^5 signals, SpecTemp reaches average F-measure 0.81 versus 0.29 for correlation and 0.25 for graphical lasso.SpecTemp is also the only method reported to achieve perfect recovery consistently as the number of observations increases.
  • Adjacency recovery: For filters H2 whose precision matrix coincides with the target graph-shift operator, graphical lasso outperforms SpecTemp and correlation.At larger observation counts, SpecTemp nevertheless achieves perfect recovery without assuming a specific filter model.
  • Overall comparison: In all but one testing case, SpecTemp achieves the largest F-measures and smallest errors across the considered graphs and signal types.
  • Laplacian recovery: With few observations, Kalofolias outperforms SpecTemp, whereas SpecTemp performs better as the number of observed signals increases.The comparison uses ℓ2 edge recovery error for ER graphs and inverse-Laplacian signals.

D. Network sparsification

The sparsification experiment uses mutual-information graphs to recover protein contact structures. SpecTemp produces sparser graphs that more closely follow the desired structure and recovers more true contacts than network deconvolution in the reported examples.

  • Experimental objective: The protein experiment recovers structural contact graphs from mutual-information graphs of amino-acid co-variation.Contacts along the first four sub-diagonals are removed to test detection of distant amino-acid relationships.
  • Qualitative comparison: SpecTemp produces a sparser inferred contact graph that more closely resembles the desired protein structure than network deconvolution.The comparison is illustrated for protein BPT1 BOVIN, with a counterpart analysis for YES HUMAN.
  • Quantitative comparison: For the top 200 edges, mutual information recovers 36% of desired contacts, network deconvolution 43%, and SpecTemp with ϵ=1 recovers 53%.Larger ϵ permits more flexibility in the inferred eigenvectors; setting ϵ=0 instead recovers the original mutual-information adjacency matrix.
  • Methodological takeaway: The conclusion identifies a two-step pipeline that first estimates the graph-shift eigenvectors and then uses them to recover eigenvalues through sparse optimization.The paper reports convex-relaxation algorithms and recovery conditions for adjacency and normalized-Laplacian shifts.
Loading 1608.03008v1…