Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Abstract

In this work, we are interested in generalizing convolutional neural networks (CNNs) from low-dimensional regular grids, where image, video and speech are represented, to high-dimensional irregular domains, such as social networks, brain connectomes or words' embedding, represented by graphs. We present a formulation of CNNs in the context of spectral graph theory, which provides the necessary mathematical background and efficient numerical schemes to design fast localized convolutional filters on graphs. Importantly, the proposed technique offers the same linear computational complexity and constant learning complexity as classical CNNs, while being universal to any graph structure. Experiments on MNIST and 20NEWS demonstrate the ability of this novel deep learning system to learn local, stationary, and compositional features on graphs.

NIPS 2016 final revision

References in corpus (5)

• Adam: A Method for Stochastic Optimization
• Deep Convolutional Networks on Graph-Structured Data
• Emergence of Complex-Like Cells in a Temporal Product Network with Local Receptive Fields
• Accelerated filtering on graphs using Lanczos method
• Toward An Uncertainty Principle For Weighted Graphs

Cited by in corpus (137)

• Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Graph Neural Network for Traffic Forecasting: A Survey
• Adversarial Attacks on Neural Networks for Graph Data
• MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding
• MeshCNN: A Network with an Edge
• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Towards Deeper Graph Neural Networks
• Session-based Social Recommendation via Dynamic Graph Attention Networks
• Dynamic Graph Convolutional Networks
• Scaling Graph Neural Networks with Approximate PageRank
• Deep learning for determining a near-optimal topological design without any iteration
• PhyCRNet: Physics-informed Convolutional-Recurrent Network for Solving Spatiotemporal PDEs
• Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future
• Deep Vessel Segmentation By Learning Graphical Connectivity
• Residual Gated Graph ConvNets
• Relation-Aware Entity Alignment for Heterogeneous Knowledge Graphs
• Transferring Robustness for Graph Neural Network Against Poisoning Attacks
• DeepSphere: Efficient spherical Convolutional Neural Network with HEALPix sampling for cosmological applications
• HDMI: High-order Deep Multiplex Infomax
• Learning representations of irregular particle-detector geometry with distance-weighted graph networks
• A Deep-Learning Approach For Direct Whole-Heart Mesh Reconstruction
• Graph Convolutional Networks for Graphs Containing Missing Features
• MR-GNN: Multi-Resolution and Dual Graph Neural Network for Predicting Structured Entity Interactions
• Hybrid Spatio-Temporal Graph Convolutional Network: Improving Traffic Prediction with Navigation Data
• Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics
• Joint predictions of multi-modal ride-hailing demands: a deep multi-task multigraph learning-based approach
• Learning to Generate Questions by Learning What not to Generate
• Graph Kernels: A Survey
• RGCNN: Regularized Graph CNN for Point Cloud Segmentation
• Relation Modeling with Graph Convolutional Networks for Facial Action Unit Detection
• Revisiting Spatial-Temporal Similarity: A Deep Learning Framework for Traffic Prediction
• Deep Graph Convolutional Reinforcement Learning for Financial Portfolio Management -- DeepPocket
• Deeply learning molecular structure-property relationships using attention- and gate-augmented graph convolutional network
• N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification
• SPLATNet: Sparse Lattice Networks for Point Cloud Processing
• Three-Dimensionally Embedded Graph Convolutional Network (3DGCN) for Molecule Interpretation
• Promises and pitfalls of deep neural networks in neuroimaging-based psychiatric research
• DropMessage: Unifying Random Dropping for Graph Neural Networks
• Is Homophily a Necessity for Graph Neural Networks?
• AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filter
• Context-Dependent Diffusion Network for Visual Relationship Detection
• Forecast Network-Wide Traffic States for Multiple Steps Ahead: A Deep Learning Approach Considering Dynamic Non-Local Spatial Correlation and Non-Stationary Temporal Dependency
• Tensor Programs II: Neural Tangent Kernel for Any Architecture
• Learning Scheduling Algorithms for Data Processing Clusters
• On the use of graph neural networks and shape-function-based gradient computation in the deep energy method
• Self-Supervised Hyperboloid Representations from Logical Queries over Knowledge Graphs
• Learning physical properties of anomalous random walks using graph neural networks
• Graph Convolutional Neural Networks with Node Transition Probability-based Message Passing and DropNode Regularization
• How does spatial structure affect psychological restoration? A method based on Graph Neural Networks and Street View Imagery
• Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Architecture are Gaussian Processes
• SyncSpecCNN: Synchronized Spectral CNN for 3D Shape Segmentation
• Zero-shot Node Classification with Decomposed Graph Prototype Network
• Multiresolution Graph Attention Networks for Relevance Matching
• DeepCas: an End-to-end Predictor of Information Cascades
• Learning Graph Neural Networks with Positive and Unlabeled Nodes
• Joint embedding of structure and features via graph convolutional networks
• Inductive Matrix Completion Based on Graph Neural Networks
• paper2repo: GitHub Repository Recommendation for Academic Papers
• Clique pooling for graph classification
• DeepBundle: Fiber Bundle Parcellation with Graph Convolution Neural Networks
• Mean-field theory of graph neural networks in graph partitioning
• Implementing graph neural networks with TensorFlow-Keras
• Independent SE(3)-Equivariant Models for End-to-End Rigid Protein Docking
• Embedding-based Silhouette Community Detection
• A Review of Graph Neural Networks and Their Applications in Power Systems
• A literature survey of matrix methods for data science
• ZerNet: Convolutional Neural Networks on Arbitrary Surfaces via Zernike Local Tangent Space Estimation
• Hierarchical stochastic graphlet embedding for graph-based pattern recognition
• Gophormer: Ego-Graph Transformer for Node Classification
• GraphPAS: Parallel Architecture Search for Graph Neural Networks
• Action Sequence Augmentation for Early Graph-based Anomaly Detection
• Beyond Graph Convolutional Network: An Interpretable Regularizer-centered Optimization Framework
• Improving Graph Neural Networks with Simple Architecture Design
• Bayesian Semi-supervised Learning with Graph Gaussian Processes
• Heterogeneous Edge-Enhanced Graph Attention Network For Multi-Agent Trajectory Prediction
• Graph-Based Classification of Omnidirectional Images
• GraFormer: Graph Convolution Transformer for 3D Pose Estimation
• Simultaneous imputation and disease classification in incomplete medical datasets using Multigraph Geometric Matrix Completion (MGMC)
• RigNet: Neural Rigging for Articulated Characters
• Distantly Supervised Relation Extraction via Recursive Hierarchy-Interactive Attention and Entity-Order Perception
• Surrogate Representation Learning with Isometric Mapping for Gray-box Graph Adversarial Attacks
• Intraoperative Liver Surface Completion with Graph Convolutional VAE
• Attacking Graph-based Classification via Manipulating the Graph Structure
• Graph Clustering with Dynamic Embedding
• edGNN: a Simple and Powerful GNN for Directed Labeled Graphs
• Online Planner Selection with Graph Neural Networks and Adaptive Scheduling
• Graph Normalized-LMP Algorithm for Signal Estimation Under Impulsive Noise
• Superpixels and Graph Convolutional Neural Networks for Efficient Detection of Nutrient Deficiency Stress from Aerial Imagery
• General Partial Label Learning via Dual Bipartite Graph Autoencoder
• SCE: Scalable Network Embedding from Sparsest Cut
• Short-Term Electricity Price Forecasting based on Graph Convolution Network and Attention Mechanism
• Integrating LSTMs and GNNs for COVID-19 Forecasting
• Popularity Prediction on Social Platforms with Coupled Graph Neural Networks
• Artificial Intelligence in Drug Discovery: Applications and Techniques
• GKD: Semi-supervised Graph Knowledge Distillation for Graph-Independent Inference
• Information Obfuscation of Graph Neural Networks
• Grouping-matrix based Graph Pooling with Adaptive Number of Clusters
• I Know You'll Be Back: Interpretable New User Clustering and Churn Prediction on a Mobile Social Application
• Simplifying Clustering with Graph Neural Networks
• MutualGraphNet: A novel model for motor imagery classification
• A Survey of Spatio-Temporal EEG data Analysis: from Models to Applications
• Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes
• Understanding Concepts in Graph Signal Processing for Neurophysiological Signal Analysis
• Message-Passing Monte Carlo: Generating low-discrepancy point sets via Graph Neural Networks
• SketchGNN: Semantic Sketch Segmentation with Graph Neural Networks
• Fully Convolutional Graph Neural Networks for Parametric Virtual Try-On
• LookHops: light multi-order convolution and pooling for graph classification
• Modularity Optimization as a Training Criterion for Graph Neural Networks
• Train on Small, Play the Large: Scaling Up Board Games with AlphaZero and GNN
• Exploiting Spiking Dynamics with Spatial-temporal Feature Normalization in Graph Learning
• HTML-LSTM: Information Extraction from HTML Tables in Web Pages using Tree-Structured LSTM
• Beyond Homophily with Graph Echo State Networks
• HighwayGraph: Modelling Long-distance Node Relations for Improving General Graph Neural Network
• Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement Learning
• Deep Spectral Meshes: Multi-Frequency Facial Mesh Processing with Graph Neural Networks
• What Should I Learn First: Introducing LectureBank for NLP Education and Prerequisite Chain Learning
• Contextualized Knowledge-aware Attentive Neural Network: Enhancing Answer Selection with Knowledge
• Isometric Transformation Invariant Graph-based Deep Neural Network
• Hybrid graph convolutional neural networks for landmark-based anatomical segmentation
• LEReg: Empower Graph Neural Networks with Local Energy Regularization
• Graph Partitioning and Graph Neural Network based Hierarchical Graph Matching for Graph Similarity Computation
• On Local Aggregation in Heterophilic Graphs
• Heterogeneous Graph based Deep Learning for Biomedical Network Link Prediction
• Sparse hierarchical representation learning on molecular graphs
• Network representation learning: A macro and micro view
• Virus-MNIST: Machine Learning Baseline Calculations for Image Classification
• An Experimental Study of the Transferability of Spectral Graph Networks
• Placement Optimization with Deep Reinforcement Learning
• Learning flexible representations of stochastic processes on graphs
• Neural Network Approximation of Graph Fourier Transforms for Sparse Sampling of Networked Flow Dynamics
• Interferometric Graph Transform for Community Labeling
• Fractional order graph neural network
• Mitigating Performance Saturation in Neural Marked Point Processes: Architectures and Loss Functions
• Learn to Learn Metric Space for Few-Shot Segmentation of 3D Shapes
• STR-GODEs: Spatial-Temporal-Ridership Graph ODEs for Metro Ridership Prediction
• The Power of Communication in a Distributed Multi-Agent System