More Like this

1. 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
2. Iterative Chebyshev Polynomial Algorithm for Signal Denoising on Graphs

   Cheng, Cheng; Jiang, Junzheng; Emirov, Nazar; Sun, Qiyu (July 2019, Proceeding of SampTA 2019)

   In this paper, we consider the inverse graph filtering process when the original filter is a polynomial of some graph shift on a simple connected graph. The Chebyshev polynomial approximation of high order has been widely used to approximate the inverse filter. In this paper, we propose an iterative Chebyshev polynomial approximation (ICPA) algorithm to implement the inverse filtering procedure, which is feasible to eliminate the restoration error even using Chebyshev polynomial approximation of lower order. We also provide a detailed convergence analysis for the ICPA algorithm and a distributed implementation of the ICPA algorithm on a spatially distributed network. Numerical results are included to demonstrate the satisfactory performance of the ICPA algorithm in graph signal denoising. 

   more » « less
3. An Asynchronous Multi-Agent Actor-Critic Algorithm for Distributed Reinforcement Learning

   Lin, Yixuan; Luo, Yuehan; Zhang, Kaiqing; Yang, Zhuoran; Wang, Zhaoran; Basar, Tamer; Sandhu, Romeil; Liu, Ji (January 2019, NeurIPS Optimization Foundations for Reinforcement Learning Workshop)

   This paper studies a distributed reinforcement learning problem in which a network of multiple agents aim to cooperatively maximize the globally averaged return through communication with only local neighbors. An asynchronous multi-agent actor-critic algorithm is proposed for possibly unidirectional communication relationships depicted by a directed graph. Each agent independently updates its variables at “event times” determined by its own clock. It is not assumed that the agents’ clocks are synchronized or that the event times are evenly spaced. It is shown that the algorithm can solve the problem for any strongly connected graph in the presence of communication and computation delays. 

   more » « less
4. Node-Asynchronous Spectral Clustering On Directed Graphs

   https://doi.org/10.1109/ICASSP40776.2020.9054241  

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

   null (Ed.)

   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 nondiagonalizable 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. 

   more » « less
5. A Massively Parallel Distributed N-body Application Implemented with HPX

   https://doi.org/10.1109/ScalA.2016.012  

   Khatami, Zahra; Kaiser, Hartmut; Grubel, Patricia; Serio, Adrian; Ramanujam, J. (November 2016, 7th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA16))

   One of the major challenges in parallelization is the difficulty of improving application scalability with conventional techniques. HPX provides efficient scalable parallelism by significantly reducing node starvation and effective latencies while controlling the overheads. In this paper, we present a new highly scalable parallel distributed N-Body application using a future-based algorithm, which is implemented with HPX. The main difference between this algorithm and prior art is that a future-based request buffer is used between different nodes and along each spatial direction to send/receive data to/from the remote nodes, which helps removing synchronization barriers. HPX provides an asynchronous programming model which results in improving the parallel performance. The results of using HPX for parallelizing Octree construction on one node and the force computation on the distributed nodes show the scalability improvement on an average by about 45% compared to an equivalent OpenMP implementation and 28% compared to a hybrid implementation (MPI+OpenMP) [1] respectively for one billion particles running on up to 128 nodes with 20 cores per each. 

   more » « less