Learning Discrete Structures for Graph Neural Networks

Abstract

Graph neural networks (GNNs) are a popular class of machine learning models whose major advantage is their ability to incorporate a sparse and discrete dependency structure between data points. Unfortunately, GNNs can only be used when such a graph-structure is available. In practice, however, real-world graphs are often noisy and incomplete or might not be available at all. With this work, we propose to jointly learn the graph structure and the parameters of graph convolutional networks (GCNs) by approximately solving a bilevel program that learns a discrete probability distribution on the edges of the graph. This allows one to apply GCNs not only in scenarios where the given graph is incomplete or corrupted but also in those where a graph is not available. We conduct a series of experiments that analyze the behavior of the proposed method and demonstrate that it outperforms related methods by a significant margin.

arXiv commentICML 2019, code at https://github.com/lucfra/LDS - Revision of Sec. 3

References in corpus (20)

• Scikit-learn: Machine Learning in Python
• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Categorical Reparameterization with Gumbel-Softmax
• Link Prediction in Complex Networks: A Survey
• Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
• A Review of Relational Machine Learning for Knowledge Graphs
• The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables
• Kronecker Graphs: An Approach to Modeling Networks
• MolGAN: An implicit generative model for small molecular graphs
• Learning Deep Generative Models of Graphs
• Gradient-based Hyperparameter Optimization through Reversible Learning
• Link Prediction Based on Graph Neural Networks
• Neural Relational Inference for Interacting Systems
• Gradient Estimation Using Stochastic Computation Graphs
• REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models
• Monte Carlo Gradient Estimation in Machine Learning
• Unbiasing Truncated Backpropagation Through Time
• Graphite: Iterative Generative Modeling of Graphs

Cited by in corpus (50)

• Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters
• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Mining Latent Structures for Multimedia Recommendation
• Pre-training Enhanced Spatial-temporal Graph Neural Network for Multivariate Time Series Forecasting
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings
• Differentiable Graph Module (DGM) for Graph Convolutional Networks
• Graph Neural Networks for Natural Language Processing: A Survey
• Latent-Graph Learning for Disease Prediction
• SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization
• Learning Strong Graph Neural Networks with Weak Information
• Deep Iterative and Adaptive Learning for Graph Neural Networks
• Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies
• Homophily-oriented Heterogeneous Graph Rewiring
• Graph neural network-based fault diagnosis: a review
• From Machine Learning to Robotics: Challenges and Opportunities for Embodied Intelligence
• Analyzing Unaligned Multimodal Sequence via Graph Convolution and Graph Pooling Fusion
• SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks
• Graph Convolutional Networks based on Manifold Learning for Semi-Supervised Image Classification
• Learning Sparse Interaction Graphs of Partially Detected Pedestrians for Trajectory Prediction
• Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint
• Graph Condensation for Graph Neural Networks
• Pointer Graph Networks
• GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks
• Model Extraction Attacks on Graph Neural Networks: Taxonomy and Realization
• Rank Flow Embedding for Unsupervised and Semi-Supervised Manifold Learning
• Graph Signal Processing for Geometric Data and Beyond: Theory and Applications
• Revisiting 2D Convolutional Neural Networks for Graph-based Applications
• Private Graph Extraction via Feature Explanations
• Relation Matters in Sampling: A Scalable Multi-Relational Graph Neural Network for Drug-Drug Interaction Prediction
• Graph-Revised Convolutional Network
• Recognizing Predictive Substructures with Subgraph Information Bottleneck
• Self-supervised edge features for improved Graph Neural Network training
• Simultaneously Reconciled Quantile Forecasting of Hierarchically Related Time Series
• Interpretable Neuron Structuring with Graph Spectral Regularization
• Learning Contextualized Knowledge Structures for Commonsense Reasoning
• Learning Graph Structure With A Finite-State Automaton Layer
• Graph Information Bottleneck for Subgraph Recognition
• HighwayGraph: Modelling Long-distance Node Relations for Improving General Graph Neural Network
• Edgeless-GNN: Unsupervised Representation Learning for Edgeless Nodes
• Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks
• Random projection tree similarity metric for SpectralNet
• Livewired Neural Networks: Making Neurons That Fire Together Wire Together
• Bounding the expected run-time of nonconvex optimization with early stopping
• Mutual Information Maximization in Graph Neural Networks
• Relax and penalize: a new bilevel approach to mixed-binary hyperparameter optimization
• Gradient scarcity with Bilevel Optimization for Graph Learning
• Co-embedding of Nodes and Edges with Graph Neural Networks
• A Gradient Method for Multilevel Optimization
• Relate and Predict: Structure-Aware Prediction with Jointly Optimized Neural DAG
• Understanding Human Innate Immune System Dependencies using Graph Neural Networks