How likely is a random graph shift-enabled?

Liyan Chen, Samuel Cheng, Vladimir Stankovic, Lina StankovicarXiv 2021 · arXiv

Abstract

In Graph Signal Processing (GSP), the "shift-enabled" property is a critical mathematical requirement for designing distributed filters. A graph is shift-enabled if its minimal polynomial equals its characteristic polynomial, which for undirected graphs implies that all eigenvalues of the shift operator must be distinct. This paper investigates the probability of common random graph models—Erdős–Rényi (ER), Watts–Strogatz (WS), and Barabási–Albert (BA)—possessing this property. The authors demonstrate that while unweighted graphs are shift-enabled only within a specific range of edge densities, the introduction of random weights or signs makes them almost universally shift-enabled once connectivity is established.

Introduction

Distributed implementation of filters in large-scale networks requires that filters be representable as polynomials of a graph shift operator (typically the Adjacency or Laplacian matrix). This representability is guaranteed if and only if the graph is shift-enabled. Despite its necessity for practical GSP applications, the shift-enabled condition is often assumed without verification. This study seeks to quantify how likely this assumption is to hold across standard random graph topologies.

Methodology

The research utilizes theoretical proofs and extensive numerical simulations (averaging $10^5$ runs) to analyze the probability $p$ of a graph being shift-enabled. Three primary models are evaluated:

  1. Erdős–Rényi (ER): Purely random connections.
  2. Watts–Strogatz (WS): Small-world networks characterized by high clustering.
  3. Barabási–Albert (BA): Scale-free networks with preferential attachment.

The study examines unweighted, weighted (Gaussian and Exponential), and signed configurations. While the Laplacian matrix is the primary focus, results are shown to generalize to other shift operators like the adjacency matrix.

Key Insights: The Unweighted "Sweet Spot" and Symmetry

For unweighted ER graphs, the probability of being shift-enabled follows a non-monotonic trajectory. It is zero for very sparse (unconnected) graphs, peaks near 1.0 at moderate densities, and collapses back to zero as the graph approaches full connectivity.

Figure 3: Probability of an unweighted Erdős–Rényi graph being shift-enabled for N=50 nodes. The "sweet spot" occurs at moderate edge densities, while the probability collapses for very sparse or very dense graphs.

This behavior is linked to the Symmetry of Complements (Theorem 4), which states that a graph and its complement share the same shift-enabled probability. Just as an empty graph has repeated zero eigenvalues, a complete graph has repeated eigenvalues due to its high symmetry, making both unsuitable for shift-enabling.

The Regularity Trap in Small-World Models

The Watts–Strogatz model begins with a regular ring lattice. These highly symmetric structures are never shift-enabled because they inherently possess repeated eigenvalues. As the rewiring probability $\beta$ increases, introducing randomness breaks this symmetry.

Figure 5: Shift-enabled probability for Watts–Strogatz graphs (N=50) across different rewiring probabilities ($\beta$). Note that for $\beta=0$ (regular lattice), the probability remains zero.

Weights and Signs as Symmetry Breakers

The study finds that adding random weights to edges acts as a powerful "cure" for repeated eigenvalues. In weighted graphs, the probability of being shift-enabled remains near 1.0 once the graph is connected ($M \geq N-1$), regardless of density. Similarly, "unbalanced" signed graphs behave like weighted graphs, maintaining shift-enabling at high densities, whereas "balanced" signed graphs mirror the behavior of unweighted graphs.

Conclusion

The shift-enabled property is not a given in unweighted or highly symmetric networks. For practical GSP filter design, researchers should be aware of the "sweet spot" in edge density or consider employing weighted/signed graphs to ensure distributed implementability. Future work may explore directed graph models and the potential for decomposing non-shift-enabled graphs into shift-enabled subgraphs.

Summary updated

BibTeX
@misc{chen2021how,
  author = {Liyan Chen and Samuel Cheng and Vladimir Stankovic and Lina Stankovic},
  title = {{How likely is a random graph shift-enabled?}},
  year = {2021},
  eprint = {2109.00339},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.00339},
}
Figure