More Like this

1. Node-asynchronous Implementation of Rational Filters on Graphs

   https://doi.org/10.1109/ICASSP.2019.8682946  

   Teke, Oguzhan; Vaidyanathan, P. P. (May 2019, IEEE Int. Conf. Acoust. Speech, and Signal Processing)

   This paper considers a node-asynchronous implementation of rational (“IIR”) filters on graphs, in which the nodes are assumed to wake up randomly and independently from each other, and communicate only with their immediate neighbors. The underlying graph is allowed to be directed, possibly with a non-diagonalizable adjacency matrix. Since the nodes are allowed to act independently, the proposed implementation is practical for very large or autonomous networks where synchronization is difficult to achieve. Furthermore, the proposed algorithm is 1-hop localized on the graph irrespective of the order of the filter. The method is shown to converge in the mean-squared sense under a boundedness assumption on the filter as well as the graph operator. The result follows from the convergence of a more general randomized asynchronous state recursion, which is also presented in this paper. The algorithm is simulated on a random geometric graph, which numerically verifies the convergence. 

   more » « less
2. Asynchronous Nonlinear Updates on Graphs

   https://doi.org/10.1109/ACSSC.2018.8645351  

   Teke, Oguzhan; Vaidyanathan, P. P. (October 2018, Asilomar Conf. Sig., Sys., and Computers)

   The notion of graph shift, introduced recently in graph signal processing, extends many classical signal processing techniques to graphs. Its practical importance follows from its localization: a single graph shift requires nodes to communicate only with their neighbors. However, communications should happen simultaneously, which requires a synchronization over the graph. In order to overcome this restriction, recent studies consider a random asynchronous variant of the graph shift, which is also suitable for autonomous networks. A graph signal under this randomized scheme is shown to converge (under mild conditions) to an eigenvector of the eigenvalue 1 of the operator even if the operator has other eigenvalues with magnitudes larger than unity. If the eigenvalue 1 does not exist, the operator can be easily normalized in theory. However, in practice, the normalization requires one to know the (dominant) eigenvalues, which may not be possible to obtain in large autonomous networks. To eliminate this limitation, this study considers the use of a nonlinearity in the updates making the scheme similar in spirit to the Hopfield neural network model. Our simulation results show that a graph signal still approaches the eigenvector of the dominant eigenvalue although the convergence is not exact. Nevertheless, approximation is sufficient to accomplish certain tasks including autonomous clustering. 

   more » « less
3. Node-Asynchronous Implementation of Filter Banks on Graphs

   https://doi.org/10.1109/IEEECONF51394.2020.9443349  

   Teke, Oguzhan; Vaidyanathan, P. P. (November 2020, Proc. Asil. Conf. Sig., Sys., and Comp)

   null (Ed.)

   Filter banks on graphs are shown to be useful for analyzing data defined over networks, as they decompose a graph signal into components with low variation and high variation. Based on recent node-asynchronous implementation of graph filters, this study proposes an asynchronous implementation of filter banks on graphs. In the proposed algorithm nodes follow a randomized collect-compute-broadcast scheme: if a node is in the passive stage it collects the data sent by its incoming neighbors and stores only the most recent data. When a node gets into the active stage at a random time instance, it does the necessary filtering computations locally, and broadcasts a state vector to its outgoing neighbors. When the underlying filters (of the filter bank) are rational functions with the same denominator, the proposed filter bank implementation does not require additional communication between the neighboring nodes. However, computations done by a node increase linearly with the number of filters in the bank. It is also proven that the proposed asynchronous implementation converges to the desired output of the filter bank in the mean-squared sense under mild stability conditions. The convergence is verified also with numerical experiments. 

   more » « less
4. Tracking the Adjacency Spectral Embedding for Streaming Graphs

   https://doi.org/10.1109/IEEECONF56349.2022.10051861  

   Larroca, Federico; Bermolen, Paola; Fiori, Marcelo; Marenco, Bernardo; Mateos, Gonzalo (October 2022, 2022 56th Asilomar Conference on Signals, Systems, and Computers)

   The popular Random Dot Product Graph (RDPG) generative model postulates that each node has an associated (latent) vector, and the probability of existence of an edge between two nodes is their inner-product (with variants to consider directed and weighted graphs). In any case, the latent vectors may be estimated through a spectral decomposition of the adjacency matrix, the so-called Adjacency Spectral Embedding (ASE). Assume we are monitoring a stream of graphs and the objective is to track the latent vectors. Examples include recommender systems or monitoring of a wireless network. It is clear that performing the ASE of each graph separately may result in a prohibitive computation load. Furthermore, the invariance to rotations of the inner product complicates comparing the latent vectors at different time-steps. By considering the minimization problem underlying ASE, we develop an iterative algorithm that updates the latent vectors' estimation as new graphs from the stream arrive. Differently to other proposals, our method does not accumulate errors and thus does not requires periodically re-computing the spectral decomposition. Furthermore, the pragmatic setting where nodes leave or join the graph (e.g. a new product in the recommender system) can be accommodated as well. Our code is available at https://github.com/marfiori/efficient-ASE 

   more » « less
5. A novel scheme for support identification and iterative sampling of bandlimited graph signals

   https://doi.org/10.1109/GlobalSIP.2018.8646488  

   Hashemi, Abolfazl; Shafipour, Rasoul; Vikalo, Haris; Mateos, Gonzalo (February 2019, 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP))

   We study the problem of sampling and reconstruction of bandlimited graph signals where the objective is to select a node subset of prescribed cardinality that ensures interpolation of the original signal with the lowest reconstruction error. We propose an efficient iterative selection sampling approach and show that in the noiseless case the original signal is exactly recovered from the set of selected nodes. In the case of noisy measurements, a bound on the reconstruction error of the proposed algorithm is established. We further address the support identification of the bandlimited signal with unknown support and show that under a pragmatic sufficient condition, the proposed framework requires minimal number of samples to perfectly identify the support. The efficacy of the proposed methods is illustrated through numerical simulations on synthetic and real-world graphs. 

   more » « less