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
- 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
-
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.
-
more » « less
Recently there is a growing focus on graph data, and multi-view graph clustering has become a popular area of research interest. Most of the existing methods are only applicable to homophilous graphs, yet the extensive real-world graph data can hardly fulfill the homophily assumption, where the connected nodes tend to belong to the same class. Several studies have pointed out that the poor performance on heterophilous graphs is actually due to the fact that conventional graph neural networks (GNNs), which are essentially low-pass filters, discard information other than the low-frequency information on the graph. Nevertheless, on certain graphs, particularly heterophilous ones, neglecting high-frequency information and focusing solely on low-frequency information impedes the learning of node representations. To break this limitation, our motivation is to perform graph filtering that is closely related to the homophily degree of the given graph, with the aim of fully leveraging both low-frequency and high-frequency signals to learn distinguishable node embedding. In this work, we propose Adaptive Hybrid Graph Filter for Multi-View Graph Clustering (AHGFC). Specifically, a graph joint process and graph joint aggregation matrix are first designed by using the intrinsic node features and adjacency relationship, which makes the low and high-frequency signals on the graph more distinguishable. Then we design an adaptive hybrid graph filter that is related to the homophily degree, which learns the node embedding based on the graph joint aggregation matrix. After that, the node embedding of each view is weighted and fused into a consensus embedding for the downstream task. Experimental results show that our proposed model performs well on six datasets containing homophilous and heterophilous graphs.
-
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
