More Like this

1. AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filter

   https://doi.org/10.1145/3459637.3482226  

   Dong, Yushun ; Ding, Kaize ; Jalaian, Brian ; Ji, Shuiwang ; Li, Jundong ( October 2021 , Proceedings of the 30th ACM International Conference on Information & Knowledge Management)

   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
2. Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data

   https://doi.org/10.1109/ISIT45174.2021.9518248  

   Data, Deepesh ; Diggavi, Suhas ( July 2021 , IEEE International Symposium on Information Theory (ISIT))

   We study distributed stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. We consider the heterogeneous data model, where different workers may have different local datasets, and we do not make any probabilistic assumptions on data generation. At the core of our algorithm, we use the polynomial-time outlier-filtering procedure for robust mean estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt gradients. In order to be able to apply their filtering procedure in our heterogeneous data setting where workers compute stochastic gradients, we derive a new matrix concentration result, which may be of independent interest. We provide convergence analyses for smooth strongly-convex and non-convex objectives and show that our convergence rates match that of vanilla SGD in the Byzantine-free setting. In order to bound the heterogeneity, we assume that the gradients at different workers have bounded deviation from each other, and we also provide concrete bounds on this deviation in the statistical heterogeneous data model. 

   more » « less
3. Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data

   Data, Deepesh ; Diggavi, Suhas N. ( July 2021 , IEEE International Symposium on Information Theory (ISIT))

   We study distributed stochastic gradient descent (SGD) in the master-worker architecture under Byzantine at- tacks. We consider the heterogeneous data model, where different workers may have different local datasets, and we do not make any probabilistic assumptions on data generation. At the core of our algorithm, we use the polynomial-time outlier-filtering procedure for robust mean estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt gradients. In order to be able to apply their filtering procedure in our heterogeneous data setting where workers compute stochastic gradients, we derive a new matrix concentration result, which may be of independent interest. We provide convergence analyses for smooth strongly- convex and non-convex objectives and show that our convergence rates match that of vanilla SGD in the Byzantine-free setting. In order to bound the heterogeneity, we assume that the gradients at different workers have bounded deviation from each other, and we also provide concrete bounds on this deviation in the statistical heterogeneous data model. 

   more » « less
4. Multi-view spectral graph convolution with consistent edge attention for molecular modeling

   https://doi.org/https://doi.org/10.1016/j.neucom.2021.02.025  

   Shang, C ; Liu, Q ; Tong, Q ; Sun, J ; Song, M ; Bi, J ( July 2021 , Neurocomputing)

   null (Ed.)

   Although graph convolutional networks (GCNs) that extend the convolution operation from images to graphs have led to competitive performance, the existing GCNs are still difficult to handle a variety of applications, especially cheminformatics problems. Recently multiple GCNs are applied to chemical compound structures which are represented by the hydrogen-depleted molecular graphs of different size. GCNs built for a binary adjacency matrix that reflects the connectivity among nodes in a graph do not account for the edge consistency in multiple molecular graphs, that is, chemical bonds (edges) in different molecular graphs can be similar due to the similar enthalpy and interatomic distance. In this paper, we propose a variant of GCN where a molecular graph is first decomposed into multiple views of the graph, each comprising a specific type of edges. In each view, an edge consistency constraint is enforced so that similar edges in different graphs can receive similar attention weights when passing information. Similarly to prior work, we prove that in each layer, our method corresponds to a spectral filter derived by the first order Chebyshev approximation of graph Laplacian. Extensive experiments demonstrate the substantial advantages of the proposed technique in quantitative structure-activity relationship prediction. 

   more » « less
5. Identifying Undirected Network Structure via Semidefinite Relaxation

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

   Shafipour, Rasoul ; Segarra, Santiago ; Marques, Antonio G. ; Mateos, Gonzalo ( April 2018 , 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   We address the problem of inferring an undirected graph from nodal observations, which are modeled as non-stationary graph signals generated by local diffusion dynamics on the unknown network. We propose a two-step approach where we first estimate the unknown diffusion (graph) filter, from which we recover the eigenvectors of the so-called graph-shift operator (a matrix representation of the graph). We then estimate the eigenvalues by imposing desirable properties on the graph to be recovered. To carry out the initial system identification step, we assume that second-order statistics of the inputs are available. While such quadratic filter identification problem boils down to a non-convex fourth order polynomial minimization, we propose a semidefinite relaxation with provable performance guarantees. Finally, numerical tests illustrate the use of the proposed algorithm to unveil urban mobility patterns. 

   more » « less