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:
- Erdős–Rényi (ER): Purely random connections.
- Watts–Strogatz (WS): Small-world networks characterized by high clustering.
- 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.
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.
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