Time-Varying Graph Learning for Data With Heavy-Tailed Distribution

Amirhossein Javaheri, Jiaxi Ying, Daniel P. Palomar, Farokh Marvasti

Introduction

In many real-world domains, such as finance or social networks, the relationships between entities are dynamic rather than static. Uncovering these evolving structures—known as time-varying graph learning—is crucial for tasks like clustering and anomaly detection. However, traditional methods often fail when faced with "heavy-tailed" data distributions (where extreme events are common) or "dirty" data containing noise and missing values. Most existing frameworks rely on a Gaussian assumption, which makes them fragile to outliers.

Conceptual overview of time-varying graph learning from signals.

This paper introduces a robust probabilistic framework designed to track evolving network structures in non-Gaussian environments. By combining a non-negative vector auto-regressive (VAR) model for graph dynamics with a Student-t signal distribution, the proposed method enables accurate tracking and superior data clustering even under significant noise.

Methodology

The authors propose a semi-online (mini-batch) approach based on Maximum A Posteriori (MAP) estimation. The framework is distinguished by several key innovations that address the limitations of prior work:

  1. Student-t Signal Model: Unlike standard Gaussian models, the Student-t distribution includes a "degrees of freedom" parameter ($\nu$) that naturally down-weights outliers. This makes the model inherently robust to the heavy tails typical of financial returns.
  2. Non-negative VAR Dynamics: To capture how edge weights evolve, the model uses a vector auto-regressive approach ($w_n \approx a \odot w_{n-1}$). This multiplicative dynamic is more flexible than simple subtractive smoothing, allowing the graph to scale relationships up or down more effectively.
  3. Spectral Constraints: To ensure the learned graph is useful for clustering, the authors impose a rank constraint on the Laplacian matrix. Specifically, a rank of $p-k$ ensures the graph has exactly $k$ connected components, making it "clustering-ready" without post-processing.
Comparison of the proposed framework with existing graph learning methods.

The resulting optimization problem is non-convex. The authors solve it using the Alternating Direction Method of Multipliers (ADMM) combined with Majorization-Minimization (MM) to derive efficient, closed-form updates.

Experimental Results

The model was rigorously tested against synthetic and real-world datasets to validate its robustness and accuracy:

  • Synthetic Performance: In tests involving signals generated from a time-varying Stochastic Block Model (SBM) with noise and missing data, the proposed method achieved an F-score of 0.60. This significantly outperformed benchmarks like Kalofolias et al. (0.40) and TV-GGM (0.28).
  • Financial Clustering: Using log-returns of 100 S&P 500 stocks, the model achieved a clustering accuracy of 0.69 and an Adjusted Rand Index (ARI) of 0.58, successfully identifying GICS sectors more accurately than state-of-the-art alternatives.
  • Portfolio Optimization: A portfolio strategy based on the learned graphs (MTVGRP) achieved a Sharpe ratio of 1.31, outperforming a standard Maximum Sharpe Ratio Portfolio (1.00).

Conclusion

The proposed framework offers a significant advancement in robust graph learning. By statistically accounting for heavy tails and enforcing structural constraints, it provides a powerful tool for analyzing complex, evolving systems. While the $O(p^3)$ computational complexity remains a challenge for massive-scale graphs, the method's ability to handle "dirty" data and provide clustering-ready outputs makes it highly valuable for financial and sensor-based applications. Future work will focus on scaling the algorithm and exploring higher-order temporal dynamics.

Summary updated

BibTeX
@article{javaheri2025time,
  author = {Amirhossein Javaheri and Jiaxi Ying and Daniel P. Palomar and Farokh Marvasti},
  title = {{Time-Varying Graph Learning for Data With Heavy-Tailed Distribution}},
  journal = {IEEE Trans. Signal Process.},
  year = {2025},
  doi = {10.1109/tsp.2025.3588173},
}
Figure