Node-Asynchronous Spectral Clustering On Directed Graphs

In recent years the convergence behavior of random node asynchronous graph communications have been studied for the case of undirected graphs. This paper extends these results to the case of graphs having arbitrary directed edges possibly with a non-diagonalizable adjacency matrix. Assuming that the...

Full description

Saved in:
Bibliographic Details
Main Authors: Teke, Oguzhan, Vaidyanathan, P. P.
Format: Conference Proceeding
Language:English
Subjects:
autonomous clustering
Convergence
directed graphs
Eigenvalues and eigenfunctions
Filtering
Graph signal processing
node-asynchronous iterations
Numerical simulation
Signal processing
Speech processing
Sufficient conditions
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In recent years the convergence behavior of random node asynchronous graph communications have been studied for the case of undirected graphs. This paper extends these results to the case of graphs having arbitrary directed edges possibly with a non-diagonalizable adjacency matrix. Assuming that the graph operator has eigenvalue 1 and the input signal satisfies a certain condition (which ensures the existence of fixed points), this study presents the necessary and sufficient condition for the mean-squared convergence of the graph signal. The presented condition depends on the graph operator as well as the update probabilities, and the convergence of the randomized asynchronous updates may be achieved even when the underlying operator is not stable in the synchronous setting. As an application, the node-asynchronous updates are combined with polynomial filtering in order to obtain a spectral clustering for directed networks. The convergence is also verified with numerical simulations.
ISSN:2379-190X
DOI:10.1109/ICASSP40776.2020.9054241