Assigning Stationary Distributions to Sparse Stochastic Matrices

Nicolas Gillis, Paul Van Dooren

TL;DR

This paper introduces an efficient way to "re-rank" nodes in a network by minimally perturbing its transition matrix. By framing the Target Stationary Distribution Problem (TSDP) as a sparse linear optimization, the authors can handle massive networks (up to $10^5$ nodes) in minutes, ensuring the resulting model remains sparse and physically meaningful.

What Problem Does This Paper Address?

In many systems—from PageRank on the web to traffic congestion on road networks—we model behavior using Markov chains. These are defined by a stochastic matrix $G$, where the "importance" or long-term behavior of the system is captured by its stationary distribution $\mu$.

The Target Stationary Distribution Problem (TSDP) asks the inverse question: If we have a desired distribution $\hat{\mu}$ (e.g., we want to reduce traffic on a specific road), how should we modify the network ($G + \Delta$) with the smallest possible change $\Delta$?

Previous approaches were often computationally heavy, produced "dense" solutions (adding links between every possible pair of nodes), or relied on the Metropolis-Hastings algorithm, which only works well if the network is symmetric. This paper tackles the TSDP under support constraints, meaning we can only modify existing links or a specific set of allowed connections, keeping the network sparse.

Methods

The authors propose two main ways to solve the TSDP:

  1. Closed-Form Diagonal Scaling: For the specific case where you can only modify existing links and the diagonal (self-loops), they provide an explicit formula. This is extremely fast but often results in larger perturbations than necessary.
  2. Sparse Linear Programming (LP): They formulate the problem using the component-wise $\ell_1$ norm. Because $\ell_1$ optimization naturally promotes sparsity, the resulting perturbation $\Delta$ adds or modifies as few links as possible.
  3. The Efficiency Trick: A naive LP would have $n^2$ variables. However, the authors show the problem only requires $2n$ equality constraints. They implement a column-generation approach: starting with a small set of allowed modifications and iteratively adding only the most "promising" variables (based on reduced costs in the dual problem). This allows them to solve problems that would otherwise crash a standard solver.

Datasets

The authors evaluated their algorithms on:

  • Synthetic Data: Randomly generated "queue-like" matrices where each node is connected to its $k$ nearest neighbors.
  • Real-World Networks (from the KONECT project):
    • email: A communication network of university employees ($n=1133$).
  • road: A network of major European cities ($n=1030$).
  • moreno: A directed social network of high school students ($n=2155$).

Key Insights and Ideas

  • Sparsity is a Feature, Not a Bug: By using the $\ell_1$ norm, the optimal solution often modifies fewer links than the original matrix had to begin with. This is crucial for practical applications like road networks, where you can't simply build a thousand new highways.
  • The Power of $2n$: The realization that the TSDP only has $2n$ linear equality constraints is the "aha moment" for scalability. It transforms a potentially $O(n^6)$ problem into something that scales closer to $O(n^2)$ or $O(n^3)$ in practice.
  • Coherent Ordering: The authors prove that if your target distribution $\hat{\mu}$ follows the same "ranking order" as the original distribution $\mu$, the required perturbation is significantly smaller.
  • Column Generation works: Even when the set of possible modifications is dense ($n^2$), the algorithm only needs to look at a tiny fraction of those possibilities to find the global optimum.

Key Results

  • Scalability: The column-generation algorithm solved sparse problems with 100,000 nodes in just a few minutes on a standard laptop.
  • Optimality: Compared to the Metropolis-Hastings (MH) baseline, the proposed LP approach found solutions with significantly lower error (often 5-10x lower objective values) because it isn't restricted by symmetry.
  • Sparsity: In experiments on the email network, the globally optimal solution only required modifying about 10-12% of the possible entries to reach the target distribution.

Limitations and Future Work

  • Initial Feasibility: The current algorithm requires an initial "guess" of which links to modify (usually the existing links plus self-loops). If the original network structure makes the target distribution impossible to reach, the algorithm needs a better way to pick which new links to add.
  • Eigenvalue Control: While the algorithm fixes the stationary distribution, it doesn't explicitly control the mixing time (how fast the system reaches that distribution). A perturbation might achieve the target but make the system converge very slowly. The authors suggest combining their norm minimization with constraints on the "subdominant eigenvalue" as a future research path.

Summary updated

Abstract

The target stationary distribution problem (TSDP) is the following: given an irreducible stochastic matrix $G$ and a target stationary distribution $\hat \mu$, construct a minimum norm perturbation, $\Delta$, such that $\hat G = G+\Delta$ is also stochastic and has the prescribed target stationary distribution, $\hat \mu$. In this paper, we revisit the TSDP under a constraint on the support of $\Delta$, that is, on the set of non-zero entries of $\Delta$. This is particularly meaningful in practice since one cannot typically modify all entries of $G$. We first show how to construct a feasible solution $\hat G$ that has essentially the same support as the matrix $G$. Then we show how to compute globally optimal and sparse solutions using the component-wise $\ell_1$ norm and linear optimization. We propose an efficient implementation that relies on a column-generation approach which allows us to solve sparse problems of size up to $10^5 \times 10^5$ in a few minutes. We illustrate the proposed algorithms with several numerical experiments.
BibTeX
@article{gillis2024assigning,
  author = {Nicolas Gillis and Paul Van Dooren},
  title = {{Assigning Stationary Distributions to Sparse Stochastic Matrices}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2024},
  doi = {10.1137/23m1627328},
}
Figure