Undirected graphs : is the shift-enabled condition trivial or necessary?

Chen, Liyan and Cheng, Samuel and He, Kanghang and Stankovic, Vladimir and Stankovic, Lina (2021) Undirected graphs : is the shift-enabled condition trivial or necessary? IEEE Access, 9. pp. 75082-75089. ISSN 2169-3536 (https://doi.org/10.1109/ACCESS.2021.3079349)

[thumbnail of Chen-etal-IEEE-Access-2021-Undirected-graphs-is-the-shift-enabled-condition-trivial]
Preview
 Text. Filename: Chen_etal_IEEE_Access_2021_Undirected_graphs_is_the_shift_enabled_condition_trivial.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (4MB)| Preview

Abstract

With the growing application of undirected graphs for signal/image processing on graphs and distributed machine learning, we demonstrate that the shift-enabled condition is as necessary for undirected graphs as it is for directed graphs. It has recently been shown that, contrary to the widespread belief that a shift-enabled condition (necessary for any shift-invariant filter to be representable by a graph shift matrix) can be ignored because any non-shift-enabled matrix can be converted to a shift-enabled matrix, such a conversion in general may not hold for a directed graph with non-symmetric shift matrix. This paper extends this prior work, focusing on undirected graphs where the shift matrix is generally symmetric. We show that while, in this case, the shift matrix can be converted to satisfy the original shift-enabled condition, the converted matrix is not associated with the original graph, that is, it does not capture anymore the structure of the graph signal. We show via examples, that a non-shift-enabled matrix cannot be converted to a shift-enabled one and still maintain the topological structure of the underlying graph, which is necessary to facilitate localized signal processing.

ORCID iDs

Chen, Liyan, Cheng, Samuel, He, Kanghang ORCID logoORCID: https://orcid.org/0000-0001-8251-7991, Stankovic, Vladimir ORCID logoORCID: https://orcid.org/0000-0002-1075-2420 and Stankovic, Lina ORCID logoORCID: https://orcid.org/0000-0002-8112-1976;
CORE (COnnecting REpositories)