Estimating Centrality Blindly From Low-Pass Filtered Graph Signals

Yiran He, Hoi-To WaiICASSP 2020 · OpenReview

TL;DR

This paper tackles the challenge of identifying influential nodes (centrality) in a network when the underlying network structure and how signals propagate through it are unknown. They propose a robust method that outperforms traditional PCA-based approaches, especially when signal propagation is complex, and demonstrate its effectiveness on synthetic and real-world stock market data.

What Problem Does This Paper Address?

In many real-world systems, like social networks or financial markets, understanding which nodes are most important (central) is crucial. Traditionally, this is done by analyzing the network's structure (e.g., who is connected to whom). However, in many scenarios, the true network structure is unknown, and we only observe signals at each node that have been "filtered" by the network's dynamics. This paper addresses the problem of estimating node centrality blindly, meaning without prior knowledge of the network's adjacency matrix or the specific characteristics of the signal filtering process. The authors highlight that common heuristics, like using Principal Component Analysis (PCA) on the observed signal covariances, can fail when the signal filtering is not "low-pass" enough, meaning signals can spread in complex ways. They aim to develop a more robust method for centrality estimation in these challenging blind scenarios.

Methods

The core of the paper lies in modeling the observed graph signals. They assume a graph signal $y$ is generated by an unknown low-pass graph filter $H(A)$ applied to an input signal $x$, where $A$ is the unknown adjacency matrix. Crucially, the input signal $x$ is modeled as a sparse influence process, meaning it's driven by a few external stimuli that affect only a subset of nodes ($x = Bz$, where $B$ is a sparse matrix and $z$ represents the stimuli).

Their proposed method builds upon this model:

  1. PCA-based Estimation (and its limitations): They first analyze why traditional PCA on the covariance of the observed signals ($C_y$) can be inaccurate. They show theoretically that if the graph filter $H(A)$ is not sufficiently low-pass, the top eigenvector of $C_y$ might not correspond to the true node centrality.
  2. Robust Estimation via Boosted Graph Filter: To overcome the limitations of PCA, they introduce a "boosted" graph filter $H_\rho(A) = H(A) - \rho I$. This modification aims to make the filter more reliably low-pass, even if the original filter wasn't.
  3. Low-Rank + Sparse Decomposition: They then leverage the observed filtered signals ($Y$) and estimated latent parameters ($Z$) to form a product $HB \approx Y Z^T$. This product is then decomposed into a low-rank component ($L$) and a sparse component ($S$). The key insight is that the true centrality is related to the low-rank component $L$.
  4. Convex Optimization: The decomposition of $HB$ into $L+S$ is achieved using a convex optimization problem that balances finding a low-rank $L$ and a sparse $S$.
  5. Centrality Estimation: The centrality vector is then estimated from the top singular vector of the recovered low-rank component $L$. They also propose a quantization step for the sparse component $S$ to further improve robustness.

Datasets

  • Synthetic Data: The authors generated synthetic graph signals using a stochastic block model for the graph structure. They experimented with different sparsity patterns for the influence matrix $B$ and used a specific infinite impulse response (IIR) graph filter.
  • Real Data: They used daily stock return data from S&P100 stocks (May 2018 - Aug 2019). The latent stimuli $z$ were approximated using Google Trends data for five keywords ('trade war', 'sales tax', 'Iran', 'oil crisis', 'election').

Key Insights and Ideas

  • PCA's Achilles' Heel: The paper clearly demonstrates that the intuitive approach of using PCA on signal covariances for centrality estimation is fundamentally flawed when the underlying graph filter is not strongly low-pass. This is a crucial insight for practitioners relying on such heuristics.
  • The Power of "Boosting" Filters: By introducing a simple modification to the graph filter (boosting), they can significantly improve the robustness of centrality estimation, making it less sensitive to the exact characteristics of the unknown filter.
  • Low-Rank + Sparse Decomposition as a Tool: The problem of estimating the centrality from filtered signals can be framed as a low-rank + sparse decomposition problem. This is a powerful paradigm that allows for robust estimation even with noisy or complex underlying processes.
  • Stock Market as a Graph Signal System: The application to stock market data provides a compelling real-world example where graph signal processing concepts can be applied to understand inter-stock influences and the impact of external events.

Key Results

  • Synthetic Data: The proposed robust estimation methods (both with and without quantization) consistently outperformed the PCA-based method in terms of error rate across various sparsity settings of the influence matrix $B$. The error rate generally decreased as the dimension of the latent factors ($k$) increased, especially with the quantization step.
  • Real Data (Stock Market):
    • The robust methods identified a more diverse set of top central stocks, including companies from food, technology, and energy sectors.
  • In contrast, the PCA method tended to return mostly technology firms.
  • The inferred influence matrix $B$ provided interpretable insights into how different keywords (e.g., 'trade war', 'oil crisis') affected specific industries and stocks.

Limitations and Future Work

  • Limitations:
    • The current method requires knowledge of the latent parameters $z$ (or at least their statistical properties). The paper acknowledges that a fully blind setting where $z$ is also unknown is a more challenging problem.
  • The performance of the convex optimization problem (21) can be sensitive to the choice of regularization parameters ($\lambda_S, \lambda_L$) and the dimension of the latent factors ($k$).
  • Future Work:
    • Developing efficient algorithms for the fully blind setting where latent parameters $z$ are unknown.
  • Further exploring the trade-offs in choosing regularization parameters for the convex optimization problem.
  • Investigating the application of these methods to other domains beyond finance.

Summary updated

Abstract

This paper considers blind methods for centrality estimation from graph signals. We model graph signals as the outcome of an unknown low-pass graph filter excited with influences governed by a sparse sub-graph. This model is compatible with a number of data generation process on graphs, including stock data and opinion dynamics. Based on the said graph signal model, we first prove that the folklore heuristics based on PCA of data covariance matrix may fail when the graph filter is not sufficiently low-pass. To remedy, we propose a robust blind centrality estimation method which substantially improves the centrality estimation performance. Numerical results on synthetic and real data support our findings.
BibTeX
@inproceedings{he2020estimating,
  author = {Yiran He and Hoi-To Wai},
  title = {{Estimating Centrality Blindly From Low-Pass Filtered Graph Signals}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=_1skvjWcKrj},
}
Figure