PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning heat diffusion graphs

Dorina Thanou, Xiaowen Dong, Daniel Kressner, Pascal Frossard

arXiv:1611.01456v1cs.LGcs.SIstat.ML

TL;DR

The paper tackles graph learning when data has localized rather than globally smooth structure, modeling observations as sparse combinations of heat-diffusion processes on an unknown graph. It jointly learns the graph, sparse sources, and diffusion scales with a PALM-based nonconvex optimization method. Experiments on synthetic and real diffusion data show that the approach recovers meaningful graph topologies and reveals application-specific structure.

  • Problem

    Existing graph models may be too globally smooth to capture localized data, while the underlying graph is often unavailable in applications such as social and biomedical networks.

  • Method

    LearnHeat jointly estimates a graph Laplacian, sparse latent sources, and heat-diffusion parameters using PALM for the resulting nonconvex problem.

  • Results

    Experiments on synthetic and real diffusion processes confirm recovery of meaningful graph topologies and improved data understanding and inference.

  • Takeaways & Limitations

    Heat-diffusion structure supports inferring graph geometry from observations across atmospheric tracer and urban mobility data.

Abstract

from arXiv · show

Effective information analysis generally boils down to properly identifying the structure or geometry of the data, which is often represented by a graph. In some applications, this structure may be partly determined by design constraints or pre-determined sensing arrangements, like in road transportation networks for example. In general though, the data structure is not readily available and becomes pretty difficult to define. In particular, the global smoothness assumptions, that most of the existing works adopt, are often too general and unable to properly capture localized properties of data. In this paper, we go beyond this classical data model and rather propose to represent information as a sparse combination of localized functions that live on a data structure represented by a graph. Based on this model, we focus on the problem of inferring the connectivity that best explains the data samples at different vertices of a graph that is a priori unknown. We concentrate on the case where the observed data is actually the sum of heat diffusion processes, which is a quite common model for data on networks or other irregular structures. We cast a new graph learning problem and solve it with an efficient nonconvex optimization algorithm. Experiments on both synthetic and real world data finally illustrate the benefits of the proposed graph learning framework and confirm that the data structure can be efficiently learned from data observations only. We believe that our algorithm will help solving key questions in diverse application domains such as social and biological network analysis where it is crucial to unveil proper geometry for data understanding and inference.

I. INTRODUCTION

The paper addresses the difficulty of defining graphs that capture localized data properties, replacing globally smooth assumptions with sparse combinations of localized graph patterns. It learns graph structure from observations modeled through heat-diffusion components.

  • Graph structure carries critical information, yet defining a graph that captures specific data properties remains difficult and limits structured-data processing.
  • The proposed model represents data as sparse combinations of overlapping localized patterns on an unknown graph, including events such as traffic bottlenecks or rumor sources.
  • The graph-learning problem estimates a graph and sparse heat-diffusion components that best explain observed graph signals.
  • Experiments use synthetic data and real datasets involving atmospheric tracer diffusion and Uber mobility patterns.

B. Diffusion signals on graphs

The signal model treats observations as combinations of heat-diffusion processes on a graph. Diffusion scale controls whether each component remains localized or captures broader graph structure.

  • Heat diffusion models processes evolving near a starting seed node, with the graph Laplacian governing heat flow across the graph.
  • The dictionary contains heat-diffusion operators e^(-τ_sL), so each signal is a linear combination of diffusion processes at different scales.
  • Small τ produces atoms localized near their center node, whereas larger τ captures information over a broader graph region.

IV. LEARNING GRAPH TOPOLOGIES UNDER SPARSE SIGNAL PRIOR

The paper jointly learns the unknown graph Laplacian, sparse latent sources, and diffusion parameters from heat-diffusion signal observations. The resulting optimization is nonconvex and requires constraints and regularization to produce valid, interpretable graphs.

  • Given signal observations, the objective jointly infers the graph Laplacian, latent source variables, and diffusion parameters.
  • The formulation constrains L to be a valid Laplacian and uses trace normalization plus a Frobenius penalty to control learned edge weights.
  • The number of diffusion blocks S is chosen from detectable training-signal scales, typically using 1 to 3 localized scales.
  • The joint problem is nonconvex because the fitting term contains the product of L, H, and τ through the matrix exponential.

B. Graph learning algorithm

The algorithm solves the joint nonconvex problem with PALM, alternating updates of sparse codes, the graph Laplacian, and diffusion parameters. Its graph update uses constrained quadratic optimization, while diffusion updates have closed-form solutions.

  • PALM alternates updates of H, L, and τ while linearizing the nonconvex fitting term, and guarantees convergence of iterates to a critical point under mild assumptions.
  • Each iteration updates sparse representations H, the graph Laplacian L, and diffusion parameters τ in sequence.
  • The L update is a quadratic program over valid-Laplacian constraints and can be solved with ADMM-based convex-cone optimization.
  • The diffusion-parameter update follows the same proximal reasoning and has a closed-form solution.

C. Discussion on the computational complexity

The main computational bottleneck is evaluating heat diffusion processes and their gradients, with costs that can become prohibitive for very large graphs. Polynomial kernel approximations can reduce both diffusion application and related computation, especially for sparse graphs.

  • Computing the heat diffusion matrix exponential and its gradient requires O(N^3) operations, creating a bottleneck for very large graphs.The exponential can be computed through spectral decomposition or scaling and squaring.
  • A degree-K polynomial approximation reduces heat diffusion application to O(|E|K), typically with small K when diffusion remains localized.The approximation is particularly efficient for sparse graph Laplacians.
  • The sparse-coding update requires O(N^2S) operations, while computing its Lipschitz constant requires a D^T D product of order O(S^2N^3).Polynomial kernel approximations can substantially reduce the latter cost.
  • The spectral norm of L for updating τ can be estimated in O(|E|) operations using a few power or Lanczos iterations.This supports efficient updates for large-scale systems.

V. EXPERIMENTS

Experiments evaluate LearnHeat on synthetic graph models using clean and noisy heat-diffusion signals, comparing it with two graph-learning methods. The proposed method recovers graph topology accurately and remains robust to noise, while global smoothness performs worst for localized diffusion patterns.

  • Experiments use 20-vertex RBF, Barabási-Albert, and Erdős-Rényi graphs, with graph recovery assessed from 100 signal observations across ten random instances.Evaluation reports Precision, Recall, F-measure, NMI, and Frobenius edge-weight error.
  • Synthetic signals are generated from heat-diffusion dictionaries D = [e^−τ1L e^−τ2L], with diffusion times chosen to produce distinct localized and more diffuse patterns.The dictionaries use two diffusion components with graph-model-specific τ values.
  • For clean RBF training signals, LearnHeat and [14] are visually consistent with the groundtruth, achieving F-measures of 0.9784 and 0.9927 respectively.The comparison is illustrated in the first row of Fig. 2.
  • The globally smooth model reaches an F-measure of 0.9173 on clean signals, performing worse because small diffusion times produce localized, piecewise-smooth components.As diffusion time increases toward steady state, the proposed method is expected to behave more like the smooth-signal model.
  • With noise at approximately 13 dB SNR, LearnHeat reaches F-measure 0.9552 and Frobenius edge-weight error 0.2642, outperforming [14] with 0.8451 and 0.3546.The noisy results appear in the second row of Fig. 2; also deteriorates, but less significantly than [14].
  • Across the reported graph models, the results confirm topology recovery close to groundtruth and robustness to noise, while is generally worst for localized heat-diffusion signals.The experiments use ADMM with a splitting conic solver and a maximum of 1000 iterations.

3) Algorithm analysis:

The algorithm learns graph connectivity and sparse diffusion sources jointly, with performance shaped by training-set size, regularization, and diffusion localization. Experiments show stronger recovery in limited-data settings and improved source localization when diffusion remains localized.

  • Training-set size: With very small training sets, LearnHeat outperforms Diffusion Filters and Smooth priors in F-measure recovery.Diffusion Filters depend on estimating spectral templates, which becomes difficult with limited or noisy training data.
  • Parameter effects: The sparsity parameter α primarily determines learned-edge count and F-measure, while β influences the graph’s sparsity pattern.For fixed α, increasing β decreases learned edges; increasing α generally decreases edges and can improve similarity to the ground-truth graph.
  • Parameter effects: A suitable range of α yields a learned graph with an edge count close to the true graph and a peak F-measure.When α is large, the sparse coding step produces a sparser source matrix H, encouraging the model to explain dense observations through diffusion.
  • Diffusion model: The learned graph models observations as heat diffusion from sparse initial sources, with connectivity enabling diffusion across the graph.The heat kernel is expressed through powers of the Laplacian, whose localization is tied to graph-hop neighborhoods.
  • Source localization: Source recovery is strongest at low diffusion parameter τ because diffusion remains localized near the initial sources.As τ increases, signals become smoother and recovering source activations becomes more difficult.
  • Source localization: At low τ, the largest-magnitude recovered sparse coefficients identify the initial source locations more consistently.The evaluation retains the s largest-magnitude coefficients, where s equals the number of initial sources.

B. Graph learning in real-world datasets

On ETEX and Uber data, the learned heat-diffusion graphs recover meaningful movement patterns and improve sparse signal representation relative to a geographically constructed graph.

  • ETEX dataset: The ETEX experiment models stations as graph nodes and tracer concentrations as graph signals from 30 observations over 72 hours.A single diffusion process is used because the observations contain many zero entries.
  • ETEX dataset: The learned ETEX graph indicates tracer movement directions, including strong connections between stations in France and Germany and between Sweden and Hungary.These directions are influenced by meteorological conditions and wind direction.
  • ETEX dataset: The learned graph yields significantly smaller approximation error than the geographical graph across different sparsity levels.The comparison uses diffusion dictionaries and sparse approximation of the ETEX signals.
  • Uber dataset: For Uber data, the city is divided into 29 taxi zones, with hourly pickup counts used as graph signals across five daily time slots.Separate heat-diffusion dictionaries are learned for the time intervals.
  • Uber dataset: The learned Uber graphs reveal airport travel in early mornings, commuting toward Manhattan during rush hours, and concentrated Manhattan connections at night.The daytime graph shows no clear pattern, while the authors caution that detailed mobility analysis requires additional urban and demographic factors.
  • Conclusion: Overall, experiments on synthetic and real-world diffusion processes support recovering meaningful graph topologies for improved data understanding and inference.The framework learns graph Laplacians from observations assumed to arise from heat diffusion starting at a few graph nodes.

APPENDIX A COMPUTATION OF THE GRADIENT

The appendix derives gradients needed by the graph-learning algorithm, including the Laplacian gradient through spectral decomposition and matrix-exponential derivatives.

  • Gradient computation: Algorithm 1 requires gradients of the fitting term with respect to H, L, and τ.The appendix computes these gradients separately.
  • Gradient with respect to H: The gradient with respect to each column of H depends only on its corresponding observation and is independent of the other columns.This follows the separable structure of the fitting term across observations.
  • Gradient with respect to L: For a symmetric Laplacian L with spectral decomposition L = χΛχT, the Laplacian gradient is obtained using the matrix exponential derivative and a Hadamard product.The resulting expression is ∇L tr(AeL) = χ(χT AT χ ◦B)χT.
  • Gradient with respect to L: The derivation uses orthonormal eigenvectors and the Fréchet derivative of the matrix exponential at the diagonal matrix Λ.These steps establish the gradient formula for the trace of a matrix exponential.
  • Gradient with respect to τ: The gradient with respect to τ is formed by collecting the gradients with respect to each element of τ.It is applied to the fitting term involving the diffusion dictionary.

C. Gradient with respect to τ

The τ-gradient is obtained by combining Taylor-expansion identities for the matrix exponential with the componentwise derivatives of the fitting term.

  • Gradient with respect to τ: Taylor expansion of the matrix exponential provides the identity used to derive the τ-dependent gradient.The derivation combines equations (21) and (22).
  • Gradient with respect to τ: The gradient with respect to τ is a vector whose elements are the derivatives with respect to each component of τ.It differentiates the fitting term ∥X − DH∥2 with respect to the diffusion-scale parameters.

APPENDIX B COMPUTATION OF THE LIPSCHITZ CONSTANTS

The appendix establishes Lipschitz constants for PALM updates, using a closed-form constant for H and backtracking to estimate the constant associated with the matrix exponential.

  • Lipschitz constants: PALM convergence requires a global Lipschitz constant or approximation satisfying the descent lemma at every iteration.The constants are considered for updates of L, H, and τ.
  • Lipschitz constant for H: The gradient with respect to H is globally Lipschitz with constant C1(L, τ) = ∥2DT D∥F.The bound follows by comparing gradients at two coefficient matrices H1 and H2.
  • Backtracking for H and τ: The Lipschitz constant C2(H, τ) for the matrix-exponential update is estimated by backtracking line search.The estimate is increased multiplicatively until the descent condition holds.
  • Convergence condition: The backtracking choice ensures that the objective function decreases over the iterations.The guarantee follows from setting the step-related quantity at least as large as C2(H, τ).

C. Variable τ

For variable τ, the paper derives a global Lipschitz constant from the Hessian of the convex, twice-differentiable objective. Positive semidefiniteness reduces this task to bounding the Hessian’s largest eigenvalue, using its largest absolute row sum and the positive-semidefinite Laplacian bound.

  • The objective is convex and twice differentiable with respect to τ, so its Lipschitz constant is estimated through the Hessian.
  • The Hessian entries form an S × S matrix obtained using the preceding equation.
  • Because the Hessian is positive semidefinite, its 2-norm equals its largest eigenvalue.
  • The largest absolute row sum provides an upper bound on the largest eigenvalue and therefore a global Lipschitz constant.
  • The derivation uses ∥L2e−τsL∥2 ≤ ∥L2∥2 for every τs ≥ 0, relying on the positive semidefiniteness of L.
Loading 1611.01456v1…