Learning Graph Neural Networks with Approximate Gradient Descent

02/02/2021

Learning Graph Neural Networks with Approximate Gradient Descent

Qunwei Li, Shaofeng Zou, Wenliang Zhong

Keywords:

Abstract Paper Similar Papers

Abstract: The first provably efficient algorithm for learning graph neural networks (GNNs) with one hidden layer for node information convolution is provided in this paper. Two types of GNNs are investigated, depending on whether labels are attached to nodes or graphs. A comprehensive framework for designing and analyzing convergence of GNN training algorithms is developed. The algorithm proposed is applicable to a wide range of activation functions including ReLU, Leaky ReLU, Sigmod, Softplus and Swish. It is shown that the proposed algorithm guarantees a linear convergence rate to the underlying true parameters of GNNs. For both types of GNNs, sample complexity in terms of the number of nodes or the number of graphs is characterized. The impact of feature dimension and GNN structure on the convergence rate is also theoretically characterized. Numerical experiments are further provided to validate our theoretical analysis.

The video of this talk cannot be embedded. You can watch it here:

https://slideslive.com/38949066

(Link will open in new window)

0

0

0

0

Share

This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment

no comments yet

Similar Papers

12/07/2020

Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case

shuai zhang, Meng Wang, Sijia Liu and
Pin-Yu Chen, Jinjun Xiong

Keywords Paper

Learning Theory

0

0

0

0

15:06

06/12/2020

Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks

Kenta Oono, Taiji Suzuki

Keywords Paper

0

0

0

0

3:22

06/12/2020

Implicit Graph Neural Networks

Fangda Gu, Heng Chang, Wenwu Zhu and
Somayeh Sojoudi, Laurent El Ghaoui

Keywords Paper

Applications -> Computer Vision; Applications -> Denoising; Deep Learning -> Deep Autoencoders; Deep Learning -> Predictive Mod, Deep Learning

0

0

0

0

3:17

12/07/2020

Bayesian Graph Neural Networks with Adaptive Connection Sampling

Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki and
Nick Duffield, Mingyuan Zhou, Krishna Narayanan, Xiaoning Qian

Keywords Paper

Applications - Other

0

0

0

0

15:26

06/12/2021

A Convergence Analysis of Gradient Descent on Graph Neural Networks

Pranjal Awasthi, Abhimanyu Das, Sreenivas Gollapudi

Keywords Paper

theory, deep learning, optimization, graph learning

0

0

0

0

7:46

03/05/2021

Discrete Graph Structure Learning for Forecasting Multiple Time Series

Chao Shang, Jie Chen, Jinbo Bi

Keywords Paper

graph structure learning, graph neural network, Time series forecasting

0

0

0

0

5:06

03/05/2021

Expressive Power of Invariant and Equivariant Graph Neural Networks

Waïss Azizian, marc lelarge

Keywords Paper

Approximation, Universality, Graph Neural Network

0

0

0

0

9:54

02/02/2021

Sample-Efficient L0-L2 Constrained Structure Learning of Sparse Ising Models

Antoine Dedieu, Miguel Lázaro-Gredilla, Dileep George

Keywords Paper

0

0

0

0

19:09

18/07/2021

On Explainability of Graph Neural Networks via Subgraph Explorations

Hao Yuan, Haiyang Yu, Jie Wang and
Kang Li, Shuiwang Ji

Keywords Paper

Deep Learning

0

0

0

0

5:15

26/04/2020

Neural Execution of Graph Algorithms

Petar Veličković, Rex Ying, Matilde Padovano and
Raia Hadsell, Charles Blundell

Keywords Paper

Graph Neural Networks, Graph Algorithms, Learning to Execute, Program Synthesis, Message Passing Neural Networks, Deep Learning

0

0

0

0

5:03

08/12/2020

Exploiting Node Content for Multiview Graph Convolutional Network and Adversarial Regularization

Qiuhao Lu, Nisansa de Silva, Dejing Dou and
Thien Huu Nguyen, Prithviraj Sen, Berthold Reinwald, Yunyao Li

Keywords Paper

0

0

0

0

12:11

06/12/2021

Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning

Robin Winter, Frank Noe, Djork-Arné Clevert

Keywords Paper

deep learning, machine learning, self-supervised learning, graph learning, clustering, representation learning

0

0

0

0

11:16

18/07/2021

Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth

Keyulu Xu, Mozhi Zhang, Stefanie Jegelka, Kenji Kawaguchi

Keywords Paper

Algorithms, Networks and Relational Learning

0

0

0

0

5:29

06/12/2020

A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems

Jiawei Zhang, Peijun Xiao, Ruoyu Sun, Zhiquan Luo

Keywords Paper

0

0

0

0

3:12

03/05/2021

Combining Label Propagation and Simple Models out-performs Graph Neural Networks

Qian Huang, Horace He, Abhay Singh and
Ser-Nam Lim, Austin Benson

Keywords Paper

graph neural networks, graphs, residual, simple, label propagation

0

0

0

0

5:15

06/12/2020

Certified Robustness of Graph Convolution Networks for Graph Classification under Topological Attacks

Hongwei Jin, Zhan Shi, Ashish Peruri, Xinhua Zhang

Keywords Paper

0

0

0

0

3:20

18/07/2021

GRAND: Graph Neural Diffusion

Ben Chamberlain, James Rowbottom, Maria Gorinova and
Michael Bronstein, Stefan Webb, Emanuele Rossi

Keywords Paper

Deep Learning, Embedding and Representation learning

0

0

0

0

5:25

06/12/2021

Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction

Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, Jian Tang

Keywords Paper

deep learning, graph learning, representation learning

0

0

0

0

14:25

14/06/2020

Determinant Regularization for Gradient-Efficient Graph Matching

Tianshu Yu, Junchi Yan, Baoxin Li

Keywords Paper

graph matching, numerical continuation, gradient effectiveness

0

0

0

0

1:00

18/07/2021

Elastic Graph Neural Networks

Xiaorui Liu, Wei Jin, Yao Ma and
Yaxin Li, Hua Liu, Yiqi Wang, Ming Yan, Jiliang Tang

Keywords Paper

Algorithms

0

0

0

0

16:23

06/12/2021

BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation

Mingguo He, Zhewei Wei, zengfeng Huang, Hongteng Xu

Keywords Paper

deep learning, graph learning

0

0

0

0

12:54

06/12/2021

Learning to Learn Graph Topologies

Xingyue Pu, Tianyue Cao, Xiaoyun Zhang and
Xiaowen Dong, Siheng Chen

Keywords Paper

deep learning, machine learning, graph learning

0

0

0

0

13:18

12/07/2020

Quantized Decentralized Stochastic Learning over Directed Graphs

Hossein Taheri, Aryan Mokhtari, Hamed Hassani, Ramtin Pedarsani

Keywords Paper

Optimization - Large Scale, Parallel and Distributed

0

0

0

0

13:03

06/12/2021

Implicit SVD for Graph Representation Learning

Sami A Abu-El-Haija, Hesham Mostafa, Marcel Nassar and
Valentino Crespi, Greg Ver Steeg, Aram Galstyan

Keywords Paper

machine learning, graph learning, representation learning

0

0

0

0

11:07

06/12/2020

On the Role of Sparsity and DAG Constraints for Learning Linear DAGs

Ignavier Ng, AmirEmad Ghassami, Kun Zhang

Keywords Paper

0

0

0

0

3:23

26/04/2020

Deep Graph Matching Consensus

Matthias Fey, Jan E. Lenssen, Christopher Morris and
Jonathan Masci, Nils M. Kriege

Keywords Paper

graph matching, graph neural networks, neighborhood consensus, deep learning

0

0

0

0

4:55

03/05/2021

Learning Parametrised Graph Shift Operators

George Dasoulas, Johannes Lutzeyer, Michalis Vazirgiannis

Keywords Paper

graph neural networks, graph representation learning, graph classification, graph shift operators, node classification

0

0

0

0

5:08

18/07/2021

Stochastic Iterative Graph Matching

Linfeng Liu, Michael Hughes, Soha Hassoun, Liping Liu

Keywords Paper

Optimization, Combinatorial Optimization

0

0

0

1

5:15

26/08/2020

Permutation Invariant Graph Generation via Score-Based Generative Modeling

Chenhao Niu, Yang Song, Jiaming Song and
Shengjia Zhao, Aditya Grover, Stefano Ermon

Keywords Paper

0

0

0

0

12:14

26/04/2020

Pruned Graph Scattering Transforms

Vassilis N. Ioannidis, Siheng Chen, Georgios B. Giannakis

Keywords Paper

Graph scattering transforms, pruning, graph convolutional networks, stability, deep learning

0

0

0

0

5:02

06/12/2021

Metropolis-Hastings Data Augmentation for Graph Neural Networks

Hyeonjin Park, Seunghun Lee, Sihyeon Kim and
Jinyoung Park, Jisu Jeong, Kyung-Min Kim, Jung-Woo Ha (NAVER AI Lab), Hyunwoo J Kim

Keywords Paper

deep learning, graph learning, semi-supervised learning

0

0

0

0

14:18

02/02/2021

Proxy Graph Matching with Proximal Matching Networks

Hao-Ru Tan, Chuang Wang, Si-Tong Wu and
Tie-Qiang Wang, Xu-Yao Zhang, Cheng-Lin Liu

Keywords Paper

0

0

0

0

15:26

13/04/2021

Alternating direction method of multipliers for quantization

Tianjian Huang, Prajwal Singhania, Maziar Sanjabi and
Pabitra Mitra, Meisam Razaviyayn

Keywords Paper

1

0

0

0

2:43

26/04/2020

What Can Neural Networks Reason About?

Keyulu Xu, Jingling Li, Mozhi Zhang and
Simon S. Du, Ken-ichi Kawarabayashi, Stefanie Jegelka

Keywords Paper

reasoning, deep learning theory, algorithmic alignment, graph neural networks

0

0

0

0

6:00

06/12/2021

Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization

Qi Zhu, Carl Yang, Yidan Xu and
Haonan Wang, Chao Zhang, Jiawei Han

Keywords Paper

deep learning, graph learning, domain adaptation, transfer learning

0

0

0

0

14:49

06/12/2021

Disentangled Contrastive Learning on Graphs

Haoyang Li, Xin Wang, Ziwei Zhang and
Zehuan Yuan, Hang Li, Wenwu Zhu

Keywords Paper

deep learning, self-supervised learning, graph learning, contrastive learning, representation learning

0

0

0

0

7:06

23/08/2020

Neural subgraph isomorphism counting

Xin Liu, Haojie Pan, Mutian He and
Yangqiu Song, Xin Jiang, Lifeng Shang

Keywords Paper

neural network, dynamic memory, subgraph isomorphism

0

0

0

0

13:43

03/05/2021

Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms

Arda Sahiner, Tolga Ergen, John M Pauly, Mert Pilanci

Keywords Paper

convolutional neural networks, convex duality, copositive programming, nonnegative PCA, semi-nonnegative matrix factorization, computational complexity, global optima, semi-infinite duality, theory, convex optimization, neural networks

0

0

0

0

6:08

06/12/2021

Efficient Bayesian network structure learning via local Markov boundary search

Ming Gao, Bryon Aragam

Keywords Paper

theory, generative model, graph learning

0

1

0

0

3:31

06/12/2021

Efficient Learning of Discrete-Continuous Computation Graphs

David Friede, Mathias Niepert

Keywords Paper

deep learning, reinforcement learning and planning, graph learning

0

0

0

0

12:31