Fast path localization on graphs via multiscale Viterbi decoding

Yaoqing Yang, Siheng Chen, Mohammad Ali Maddah-Ali, Pulkit Grover, Soummya Kar, Jelena KovacevicICASSP 2017 · OpenReview

TL;DR

This paper introduces a novel "multiscale Viterbi decoding" algorithm for efficiently tracking the movement of an agent on a graph, even with noisy observations. By combining graph partitioning with dynamic programming, it significantly speeds up localization while maintaining comparable accuracy to existing methods, making it practical for large-scale networks.

What Problem Does This Paper Address?

The paper tackles the challenge of "path localization" on graphs. Imagine an agent moving along a network (like a road map or a social network) and we're trying to track its exact location over time based on imperfect sensor readings. This is crucial for applications like urban mobility monitoring, surveillance, or even understanding brain signal propagation. Traditional methods, like dynamic programming (specifically, Viterbi decoding), are effective but become computationally prohibitive on large, complex graphs. The core problem is to develop a method that can accurately track this "path-signal" on massive graphs without requiring an unreasonable amount of computational resources.

Methods

The authors propose a "multiscale Viterbi decoding" approach. The core idea is to first simplify the large graph by partitioning it into smaller clusters and then representing each cluster as a single "super-node." This creates a smaller "super-graph." They then apply a Viterbi decoding algorithm on this super-graph, which drastically reduces the number of states to consider, thus speeding up computation.

Here's a breakdown of the key techniques:

  • Graph Partitioning: The original graph is divided into non-overlapping clusters. This is a standard technique, but the paper explores how different partitioning strategies (like "Slashburn") impact performance.
  • Super-Graph Construction: Each cluster is shrunk into a single "super-node." Connections between super-nodes are established if there are connections between nodes in the corresponding original clusters.
  • Coarsened Signal: The noisy observations are "coarsened" to match the super-graph structure. The authors specifically use a "max" statistic for this coarsening, arguing it's more robust to noise than a simple average.
  • Dynamic Programming (Viterbi Decoding): The standard Viterbi algorithm is applied to the super-graph and the coarsened signal. This finds an approximate path on the simplified graph.
  • Refined Search: After finding an approximate path on the super-graph, a second step refines this path back onto the original graph. This involves selecting the most likely node within each cluster for the agent's location.

The paper also introduces theoretical bounds on the localization error (both Hamming distance and destination distance) to analyze the performance of their proposed algorithm.

Datasets

The paper uses two types of datasets for evaluation:

  • Synthesized Random Geometric Graphs: These are generated graphs that mimic sensor networks, allowing for controlled experiments and validation of theoretical bounds.
  • Real Graph Data (AS-Oregon): This is a real-world graph representing Autonomous Systems (AS) peering information from the internet. This dataset is used to demonstrate the practical performance of the algorithm and compare it with other graph partitioning methods.

Key Insights and Ideas

  • Graph Partitioning as a Scalability Tool: The most significant insight is that graph partitioning can be effectively used to make computationally intensive graph signal processing tasks, like path localization, scalable to massive networks.
  • Multiscale Approach: The "multiscale" aspect is key. By first operating on a coarser representation of the graph and then refining, the algorithm achieves a dramatic speedup.
  • "Max" Statistic for Coarsening: The choice of using the maximum signal within a cluster (rather than the average) is a crucial detail that improves robustness to noise in the coarsened signal.
  • Tradeoff Between Granularity and Speed: The paper highlights a clear tradeoff: more clusters (finer partitioning) lead to better localization accuracy but increase computational complexity, and vice-versa. This allows for tuning the algorithm to specific application needs.
  • Slashburn for Sparse Super-Graphs: The authors find that the "Slashburn" graph partitioning method is particularly effective because it tends to create sparse super-graphs, which is beneficial for the multiscale Viterbi approach.

Key Results

  • Significant Speedup: The multiscale Viterbi decoding algorithm achieved a speedup of over 100x compared to the direct Viterbi decoding method on the AS-Oregon graph.
  • Comparable Localization Error: Despite the speedup, the localization error (measured by Hamming distance) was only about 4x worse than the direct method.
  • Theoretical Bounds: The paper provides analytical bounds on the localization error, which are shown to be computable in polynomial time and validated through simulations.
  • Performance on Random Graphs: Simulations on random geometric graphs show that increasing the number of clusters generally improves localization accuracy (lower SNR required) but increases computation time.

Limitations and Future Work

  • Degradation with Multiple Paths: The paper acknowledges that the performance of the multiscale Viterbi algorithm degrades as the number of overlapping paths increases. This is because subtracting one path's signal can disconnect other overlapping paths.
  • Sequential Path Localization: The current extension for multiple paths is sequential, meaning paths are localized one after another. This can lead to accumulated errors.
  • Future Work: The authors suggest further research into improving the multi-path localization, particularly for scenarios with significant path overlap. They also note the potential for applying this multiscale approach to other message-passing techniques. The analysis of the "max" statistic for coarsening is also highlighted as a direction for further theoretical exploration.

Summary updated

BibTeX
@inproceedings{yang2017fast,
  author = {Yaoqing Yang and Siheng Chen and Mohammad Ali Maddah-Ali and Pulkit Grover and Soummya Kar and Jelena Kovacevic},
  title = {{Fast path localization on graphs via multiscale Viterbi decoding}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2017},
  url = {https://openreview.net/forum?id=cA2vUUY2yP},
}
Figure