PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning graphs from data: A signal representation perspective

Xiaowen Dong, Dorina Thanou, Michael Rabbat, Pascal Frossard

arXiv:1806.00848v3cs.LGcs.SIstat.ML

TL;DR

The paper addresses inferring graph structure from data and surveys classical statistical and physical viewpoints alongside newer graph signal processing approaches. It frames graph learning as selecting a graph whose properties support desired signal characteristics, while highlighting GSP's potential advantages and open challenges.

  • Problem

    Inferring a graph structure from data is necessary when the data do not provide a natural graph choice.

  • Method

    The tutorial reviews statistics- and physics-based solutions and surveys GSP approaches that learn a graph whose properties support desired signal characteristics.

  • Results

    Meaningful graph learning can significantly affect graph-based image representation, while graph-weight GFT coefficients concentrated at low frequencies indicate a highly compressible graph.

  • Takeaways & Limitations

    GSP provides a perspective for representing data as graph signals and may offer advantages under more accurate assumptions, while graph learning remains challenging for sensor observations.

Abstract

from arXiv · show

The construction of a meaningful graph topology plays a crucial role in the effective representation, processing, analysis and visualization of structured data. When a natural choice of the graph is not readily available from the data sets, it is thus desirable to infer or learn a graph topology from the data. In this tutorial overview, we survey solutions to the problem of graph learning, including classical viewpoints from statistics and physics, and more recent approaches that adopt a graph signal processing (GSP) perspective. We further emphasize the conceptual similarities and differences between classical and GSP-based graph inference methods, and highlight the potential advantage of the latter in a number of theoretical and practical scenarios. We conclude with several open issues and challenges that are keys to the design of future signal processing and machine learning algorithms for learning graphs from data.

I. INTRODUCTION

Graph learning infers a topology that captures relationships among structured-data entities when no natural graph is available. This tutorial reviews statistical, physics-based, and GSP-based approaches, emphasizing how signal representations can yield distinct graph-inference methods and advantages.

  • Problem formulation: Graph learning seeks a graph G relating N data entities from M observations X, so each observation becomes a graph signal generated through F(G).The inferred graph is intended to expose relationships underlying the observed data.
  • Motivation: Graphs can capture data geometry and relationships, supporting structured-data processing, visualization, connectivity analysis, and prediction of future data evolution.Examples include transportation, social, computer, brain, and gene-interaction networks.
  • Challenges: Inferring graph topologies is ill-posed because multiple topologies can be associated with the same observed samples.Observation-only similarity or correlation methods may be noise-sensitive and difficult to tune because they lack explicit priors or data models.
  • Classical approaches: Classical graph learning uses statistical models whose distributions or conditional independences are determined by G, or physical models in which F(G) describes diffusion or cascades.These perspectives connect graph inference to probabilistic graphical models and processes such as information flow or epidemic spread.
  • GSP perspective: GSP-based learning treats columns of X as signals on a weighted graph and learns G so signal properties such as smoothness or sparsity become explicit.Graph Fourier-like analysis links the representation to topology and can address complex behavior such as bandlimited graph signals.
  • Tutorial scope: The tutorial surveys classical and recent GSP approaches, presents applications, compares their conceptual similarities and differences, and identifies open challenges for future algorithms.Its stated scope includes applications across domains and unresolved issues in learning graphs from data.

II. LITERATURE REVIEW

The literature includes statistical and physically motivated approaches to learning graph structures, with statistical methods using graphical models to encode conditional independence. Gaussian and discrete Markov random fields provide several estimation strategies, including covariance inversion, neighborhood selection, and graphical Lasso.

  • Graph-learning research commonly follows statistical or physically motivated models, with this review focusing on statistical graphical-model approaches.
  • Markov random fields represent local neighborhoods through conditional independence, while Bayesian networks use directed edges and a more complicated independence structure.
  • Gaussian graphical models: In Gaussian Markov random fields, graph learning reduces to estimating a sparse precision matrix Θ whose off-diagonal structure encodes pairwise conditional independence.
  • Gaussian graphical models: Covariance-inversion methods are simple but fail when samples are fewer than variables because the sample covariance is not invertible.
  • Neighborhood selection: Neighborhood selection fits sparse regressions separately for each variable, then connects vertices when either directional coefficient is nonzero.
  • Graphical Lasso: Graphical Lasso estimates the precision matrix jointly by combining Gaussian log-likelihood with an entry-wise L1 sparsity penalty, yielding a convex but computationally demanding optimization.

B. Physically-motivated models

Physically motivated graph learning infers network structure from observations generated by communication, epidemic, or information-propagation processes. Cascade methods recover edges from infection times, using homogeneous or heterogeneous transmission models and optimization-based likelihood inference.

  • Network tomography: Network tomography infers network properties from indirect end-to-end measurements, including routes, link reliability, and internal topology.Probe traffic can be substantial when measurements are sent between all possible end-host pairs.
  • Information propagation: Propagation-based methods infer latent biological, social, or financial networks from epidemics, memes, or other signals diffusing over the network.These models comprise nodes, an infection process, and graph-based causality.
  • Cascade observations: Cascade inference recovers an edge structure from partial observations of which nodes became infected and when, without necessarily observing the infecting neighbor.Each cascade can be represented in an N-by-M matrix X = F(G).
  • Transmission models: Homogeneous models assume statistically identical propagation across edges, whereas heterogeneous models allow different transmission rates through edge-specific likelihoods.Homogeneous formulations may reduce to discrete edge selection, while heterogeneous likelihood models can retain continuous edge parameters.
  • Optimization and guarantees: For homogeneous models, greedy edge selection achieves the optimal likelihood up to a constant factor, while heterogeneous likelihood inference can be convex and decompose into per-node problems.Under additional conditions, heterogeneous estimates are consistent and their sample complexity quantifies error decay with observed cascades.
  • Limitations: Homogeneous methods’ main drawback is their strong assumption that cascades propagate identically across every network edge.Active sampling has been proposed to reduce the significant measurement traffic imposed by exhaustive probing.

III. GRAPH LEARNING: A SIGNAL REPRESENTATION PERSPECTIVE

Graph signal processing extends graph learning by treating observations as signals whose representation depends on an unknown graph. The perspective complements statistical and physics-based methods by using signal representations, including spectral structure, as inference ingredients and regularizers.

  • Graph signal representation: GSP represents signals on weighted graphs and uses graph operators such as Laplacian, adjacency, and shift matrices to generalize transforms and filtering.The Laplacian eigenvectors and eigenvalues define graph-frequency representations for undirected graphs, while adjacency-based definitions can also handle directed graphs.
  • Relation to prior viewpoints: This perspective addresses graph learning when topology is unavailable and complements classical statistical and physics viewpoints.Statistical methods may not directly produce non-negative edge weights or localized behavior, while physics-based methods focus mainly on conventional diffusion and cascade models.
  • Learning formulation: Graph learning in the synthesis view infers G from observed x by modeling the relationship between graph structure, representation function F, and coefficients c.Assumptions on c influence the characteristics of the resulting signal representation.
  • GSP perspective: GSP-based frameworks can enforce desirable signal representations by exploiting frequency-domain analysis and graph filtering operations.The tutorial reviews three graph signal representation models that lead to different topology-inference methodologies.
  • Open direction: Spectral representations provide an additional regularizer for inference problems involving observations that may not arise from a well-defined physical phenomenon.The paper identifies how such observations can be used to infer underlying data structure as an open question.

A. Models based on signal smoothness

Smoothness-based models learn graphs on which observed signals vary little across edges and concentrate primarily in low graph frequencies. Their formulations connect Laplacian quadratic minimization with Gaussian representations, while later models relax global smoothness constraints.

  • Smoothness criterion: Smoothness models learn a graph or Laplacian such that the observed signal has similar neighboring values and a low-frequency spectral representation.For the illustrated signal, the graph with Q(L) = 1 yields a smoother representation than the graph with Q(L) = 5.
  • Smoothness criterion: The Laplacian quadratic Q(L) measures signal smoothness by penalizing weighted squared differences between values at connected vertices.Smaller Q(L) indicates less variation along graph edges.
  • Probabilistic formulation: A synthesis model with F(G) = χ and Gaussian coefficients connects smooth graph signals to GMRF models whose precision matrix has Laplacian structure.Joint inference can estimate the graph Laplacian and latent coefficients, with noise and coefficient assumptions entering the formulation.
  • Optimization: Optimization formulations jointly fit observations and smooth reconstructed signals while constraining L to valid Laplacian matrices and regularizing edge-weight structure.Trace normalization fixes graph volume, while a Frobenius penalty controls the distribution of edge weights.
  • Variants and computation: Related methods differ in whether they learn adjacency matrices or Laplacians and in their optimization algorithms, including quadratic programming and sorting.Some formulations incorporate prior connectivity knowledge, which can improve graph inference performance when available.
  • Limitation and transition: Global smoothness can be limiting because it requires small variation across all graph edges, motivating models with more flexible spectral representations.The next model class relaxes this constraint rather than requiring globally smooth signals.

B. Models based on spectral filtering of graph signals

Spectral-filtering models represent graph signals as outputs of graph-dependent filters applied to latent inputs. By varying filters and coefficient assumptions, they can model frequency-selective and localized signals, including signals produced by diffusion processes.

  • General model: Spectral-filtering models go beyond global smoothness by representing signals through graph filters applied to latent input signals.The filter and input determine the generated signal’s frequency and localization characteristics.
  • Applications: Filtering can generate bandpass or locally smooth signals, making this family more appropriate than global smoothness for observations produced by graph diffusion.Applications include heat distribution, movement, and changing interests on social media.
  • Filter and coefficient choices: Graph filters may be polynomial functions of graph-related matrices or diffusion kernels such as the heat diffusion kernel.The synthesis coefficients can follow assumptions including zero-mean Gaussian distributions or sparsity.
  • Algorithm categories: These algorithms include stationary-process models that estimate graph operator eigenvectors from the sample covariance before estimating eigenvalues.A second category formulates graph learning as dictionary learning with a prior on coefficients.

1) Stationarity based learning frameworks:

Stationarity-based methods infer graph operators by exploiting relationships between graph-shift eigenvectors and signal covariance, then estimate compatible eigenvalues or graph structures. These approaches include covariance-based recovery, graph system identification, and iterative graph-filter estimation.

  • Covariance-based recovery: Stationarity-based methods estimate graph-operator eigenvectors from the empirical covariance of observed graph signals.This relies on the graph operator and covariance matrix sharing eigenvectors under the stationarity model.
  • Covariance-based recovery: After estimating eigenvectors, the graph-learning problem becomes estimating eigenvalues subject to constraints such as sparsity and valid edge weights.Convex objectives can impose properties including entry-wise L1 sparsity and non-negative edge weights.
  • Covariance-based recovery: A diffusion-matrix approach characterizes admissible operators as a polytope, so an additional sparsity or simplicity criterion is needed to select one graph.The observations generally correspond to a continuum of consistent graphs rather than a unique solution.
  • Limitations: These methods assume the sample covariance and graph operator have the same eigenvectors, making performance sensitive to covariance-eigenvector accuracy.This accuracy can be difficult to guarantee when the number of samples is small relative to the number of graph vertices.
  • Graph system identification: Graph system identification jointly learns a graph Laplacian and graph filter through a regularized maximum-likelihood procedure.An iterative algorithm pre-filters covariance, estimates a Laplacian, and updates filter parameters until convergence.
  • Graph system identification: The iterative system-identification procedure may produce a more accurate graph-Laplacian inference than approaches that use covariance eigenvectors directly.Its iterations pre-filter the covariance before estimating the Laplacian and updating the filter.

2) Graph dictionary based learning frameworks:

Graph-dictionary methods learn graph topology by representing signals as sparse combinations of graph-dependent atoms, especially diffusion kernels. Heat-diffusion dictionaries connect localization and scale to an unknown graph Laplacian that is estimated through structured dictionary learning.

  • Sparsity and scope: The model assumes diffusion processes begin at only a few nodes and times, which is encoded by imposing sparsity on the latent coefficients.Without locality assumptions and with a single diffusion kernel, the model reduces to global smoothness.
  • Dictionary-based representations: Graph dictionary learning represents signals as linear combinations of simple components or atoms, often using an overcomplete basis and sparse coefficients.This representation is intended to reveal important signal characteristics while enabling efficient approximation or processing.
  • Heat-diffusion dictionaries: Heat-diffusion methods model graph signals as combinations of processes that start from selected nodes and evolve over different diffusion times.The graph Laplacian models heat propagation, and concatenated diffusion operators form the graph dictionary.
  • Heat-diffusion dictionaries: Each heat-diffusion component e^-τsLcs represents a diffusion process at time τs, with τs controlling its spatial scale.Small τs yields atoms localized near a seed node, whereas larger τs spreads information over a larger neighborhood.
  • Learning the topology: Graph learning is formulated as structured dictionary learning in which the unknown graph Laplacian defines the dictionary and is estimated by optimization.The framework has also been extended from heat-diffusion dictionaries to more general polynomial graph kernels.
  • Applications and interpretation: These methods recover a graph Laplacian by assuming graph signals admit sparse representations using graph diffusion kernels.Localized kernels can represent observations from processes such as traffic bottlenecks or rumor sources spreading over time.

C. Models based on causal dependencies on graphs

Causal-dependency models represent graph signals through present and past observations, allowing graph learning to capture directed relationships. SVAR and SEM formulations use graph operators and coefficients to specify generative processes for temporal or component-wise dependencies.

  • Comparison and extensions: Methods based on these causal models can learn an asymmetric graph adjacency matrix, a potential advantage over methods built on undirected graph models.SEM extensions can also track dynamically evolving topologies and handle highly correlated data.
  • Motivation: Directed graph learning is useful when edge directions represent causal dependencies, such as effective connectivity between brain regions.Directed connectivity can provide information beyond undirected functional connectivity.
  • SVAR models: Sparse vector autoregressive models represent x[t] as a combination of observations from the previous T time steps and random noise.The polynomial Pj(W) captures graph-mediated temporal dependencies through powers of a possibly directed adjacency matrix.
  • SVAR models: SVAR estimation imposes entry-wise L1 sparsity on the adjacency matrix and polynomial coefficients, then solves the non-convex problem sequentially for Pj(W), W, and a.The resulting choices of F and c define a generative process for the observed signals on the learned graph.
  • Structural equation models: Structural equation models write the signal as endogenous variables from W, exogenous variables Ey[t], and observation noise n[t].The endogenous component uses current signal values and can again employ a directed graph.
  • General framework: Causal dependencies can be modeled by choosing F(G) as a polynomial of a directed adjacency matrix and c as present or past signal observations.This accommodates dependencies between signal components and across time.

D. Connections with the broader literature

GSP-based graph learning unifies topology inference with signal representation and generative processes on graphs. Compared with classical approaches, its flexible graph functions support broader signal statistics and processes beyond simple diffusion or cascade models.

  • Unifying perspective: GSP-based approaches can be unified as methods that learn graph topologies through the representation of graph signals.This viewpoint connects graph inference to how observed signals are modeled on the topology.
  • Connection to graphical models: Graphical Lasso can be interpreted as promoting global smoothness of signals on the learned topology when its precision matrix is chosen as a graph Laplacian.Its trace term corresponds to a Laplacian quadratic-form interpretation.
  • Generative interpretation: Spectral-filtering and causal-dependency models define generative processes for observed signals, including explicit or implicit diffusion processes.These models share a physical-process interpretation with approaches motivated by diffusion and cascading phenomena.
  • Connections to classical views: Some models admit statistical, GSP, and physical interpretations simultaneously, as illustrated by global smoothness and the square-lattice Ising model.This creates conceptual connections between traditional statistical modeling, signal processing, and physics.
  • Advantages of GSP-based methods: GSP-based graph learning allows signal statistics beyond Gaussian distributions through flexible choices of F(G).The same flexibility supports models that go beyond simple diffusion or cascade processes.
  • Advantages of GSP-based methods: Choosing sparse coefficients can model multiple diffusion processes originating at different graph locations and times.SVAR and SEM choices of F(G) and c likewise represent different generative processes based on static structure or temporal dynamics.
  • Applications: GSP-based graph learning is increasingly applied where data contain hidden structure, including image coding, compression, and brain signal analysis.The emphasis on signal representation within learning contributes to its use across diverse application areas.

A. Image coding and compression

GSP-based graph learning supports image representation and coding by adapting graph transforms to image signals. Learned topologies can improve coefficient compressibility, but graph and transform design remains a major challenge.

  • Graph-based transforms can be better adapted to actual image signals than fixed transforms such as the DCT.
  • Image coding methods learn graphs from pixel similarities or signal smoothness, sometimes jointly accounting for signal coding and graph-transmission costs.
  • The learned graph in Fig. 10 produces GFT coefficients whose log-magnitude decays much faster than coefficients on a regular grid graph.
  • Graph weights can be represented as a signal on a dual graph, with low-frequency concentration indicating a highly compressible graph.
  • A constrained maximum-likelihood graph-learning approach yields a fast non-separable transform for intra-predictive residual blocks in video compression.
  • Existing efforts show significant impact in graph-based image compression, while coding performance and graph-transform design remain open areas for improvement.

C. Other application domains

GSP-based graph learning has been applied across biomedical, environmental, meteorological, and social domains to infer hidden relationships from observed signals. The survey also identifies open challenges involving partial observations, changing graphs, directed structures, and application-specific graph properties.

  • Environmental and meteorological applications: Weather-network models can use signal smoothness to capture altitude-related relationships or heat diffusion to model temperature evolution on a geographical graph.
  • Environmental and meteorological applications: Environmental and meteorological methods learn relationships among regions or weather stations from ozone, evapotranspiration, or temperature observations.
  • Other applications: Applications also include traffic flows, news propagation, political relationships, animal similarity, and concept ontologies, demonstrating broad potential for uncovering hidden relationships.
  • Open challenges: Future work must address incomplete observations, online data, dynamic topologies, directed graphs, and graph properties beyond sparsity.

C. Signal models

The survey argues that graph learning should be guided by signal models matched to the data, task, and graph dynamics. It highlights theoretical guarantees, application-specific objectives, and integration with downstream analysis as important future directions.

  • Signal models: Current methods predominantly use globally or locally smooth signals, while bandlimited and filtering-based models offer broader alternatives for graph inference.
  • Signal models: For partial observations, the signal model may need to target the observed region rather than the entire graph.
  • Dynamic graphs: Dynamic graph learning requires signal models consistent with the temporal smoothness criteria used to infer graph sequences.
  • Theory and scalability: Graph recovery remains difficult because it has generally O(N^2) unknown variables and relatively few observations, necessitating assumptions or priors.
  • Theory and scalability: Open theoretical issues include recovery guarantees, downstream-task impact, alternating-minimization convergence, and computational complexity for large graphs.
Loading 1806.00848v3…