This paper considers a nodeasynchronous 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 nondiagonalizable 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 1hop localized on the graph irrespective of the order of the filter. The method is shown to converge in the meansquared sensemore »
NodeAsynchronous Implementation of Filter Banks on Graphs
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 nodeasynchronous implementation of graph
filters, this study proposes an asynchronous implementation of
filter banks on graphs. In the proposed algorithm nodes follow a
randomized collectcomputebroadcast 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 meansquared sense under mild stability conditions. The
convergence is verified also with numerical experiments.
 Award ID(s):
 1712633
 Publication Date:
 NSFPAR ID:
 10275654
 Journal Name:
 Proc. Asil. Conf. Sig., Sys., and Comp
 Page Range or eLocationID:
 460 to 464
 Sponsoring Org:
 National Science Foundation
More Like this


Graph Neural Networks have recently become a prevailing paradigm for various highimpact graph analytical problems. Existing efforts can be mainly categorized as spectralbased and spatialbased methods. The major challenge for the former is to find an appropriate graph filter to distill discriminative information from input signals for learning. Recently, myriads of explorations are made to achieve better graph filters, e.g., Graph Convolutional Network (GCN), which leverages Chebyshev polynomial truncation to seek an approximation of graph filters and bridge these two families of methods. Nevertheless, it has been shown in recent studies that GCN and its variants are essentially employing fixedmore »

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 ifmore »

Towards the challenging problem of semisupervised node classification, there have been extensive studies. As a frontier, Graph Neural Networks (GNNs) have aroused great interest recently, which update the representation of each node by aggregating information of its neighbors. However, most GNNs have shallow layers with a limited receptive field and may not achieve satisfactory performance especially when the number of labeled nodes is quite small. To address this challenge, we innovatively propose a graph fewshot learning (GFL) algorithm that incorporates prior knowledge learned from auxiliary graphs to improve classification accuracy on the target graph. Specifically, a transferable metric space characterizedmore »

We consider the adhoc networks consisting of n wireless nodes that are located on the plane. Any two given nodes are called neighbors if they are located within a certain distance (communication range) from one another. A given node can be directly connected to any one of its neighbors, and picks its connections according to a unique topology control algorithm that is available at every node. Given that each node knows only the indices (unique identification numbers) of its one and twohop neighbors, we identify an algorithm that preserves connectivity and can operate without the need of any synchronization amongmore »