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
Node-Asynchronous 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 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
- Award ID(s):
- 1712633
- NSF-PAR ID:
- 10275654
- Date Published:
- Journal Name:
- Proc. Asil. Conf. Sig., Sys., and Comp
- Page Range / eLocation ID:
- 460 to 464
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Graph Neural Networks have recently become a prevailing paradigm for various high-impact graph analytical problems. Existing efforts can be mainly categorized as spectral-based and spatial-based 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 fixed low-pass filters to perform information denoising. Thus their learning capability is rather limited and may over-smooth node representations at deeper layers. To tackle these problems, we develop a novel graph neural network framework AdaGNN with a well-designed adaptive frequency response filter. At its core, AdaGNN leverages a simple but elegant trainable filter that spans across multiple layers to capture the varying importance of different frequency components for node representation learning. The inherent differences among different feature channels are also well captured by the filter. As such, it empowers AdaGNN with stronger expressiveness and naturally alleviates the over-smoothing problem. We empirically validate the effectiveness of the proposed framework on various benchmark datasets. Theoretical analysis is also provided to show the superiority of the proposed AdaGNN. The open-source implementation of AdaGNN can be found here: https://github.com/yushundong/AdaGNN.more » « less
-
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
-
more » « less
Abstract Motivation The de Bruijn graph is fundamental to the analysis of next generation sequencing data and so, as datasets of DNA reads grow rapidly, it becomes more important to represent de Bruijn graphs compactly while still supporting fast assembly. Previous implementations of compact de Bruijn graphs have not supported node or edge deletion, however, which is important for pruning spurious elements from the graph.
Results Belazzougui et al. (2016b) recently proposed a compact and fully dynamic representation, which supports exact membership queries and insertions and deletions of both nodes and edges. In this paper, we give a practical implementation of their data structure, supporting exact membership queries and fully dynamic edge operations, as well as limited support for dynamic node operations. We demonstrate experimentally that its performance is comparable to that of state-of-the-art implementations based on Bloom filters.
Availability and implementation Our source-code is publicly available at https://github.com/csirac/dynamicDBG under an open-source license.
-
Towards the challenging problem of semi-supervised 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 few-shot learning (GFL) algorithm that incorporates prior knowledge learned from auxiliary graphs to improve classification accuracy on the target graph. Specifically, a transferable metric space characterized by a node embedding and a graph-specific prototype embedding function is shared between auxiliary graphs and the target, facilitating the transfer of structural knowledge. Extensive experiments and ablation studies on four real-world graph datasets demonstrate the effectiveness of our proposed model and the contribution of each component.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/IEEECONF51394.2020.9443349
