# Learning Discrete Structures for Graph Neural Networks

arXiv: https://arxiv.org/abs/1903.11960 · HTML: https://mlsanity.com/paper/1903.11960/

## Key facts

- Cited by 231 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2019.

## Built on by (most cited first, 30 of 231)

- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Discrete Graph Structure Learning for Forecasting Multiple Time Series](https://mlsanity.com/paper/2101.06861/) (2021)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Pre-training Enhanced Spatial-temporal Graph Neural Network for Multivariate Time Series Forecasting](https://mlsanity.com/paper/2206.09113/) (2022)
- [Towards Unsupervised Deep Graph Structure Learning](https://mlsanity.com/paper/2201.06367/) (2022)
- [GraphText: Graph Reasoning in Text Space](https://mlsanity.com/paper/2310.01089/) (2023)
- [SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2102.05034/) (2021)
- [How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision](https://mlsanity.com/paper/2204.04879/) (2022)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion](https://mlsanity.com/paper/2301.09474/) (2023)
- [Beltrami Flow and Neural Diffusion on Graphs](https://mlsanity.com/paper/2110.09443/) (2021)
- [Graph Structure Learning with Variational Information Bottleneck](https://mlsanity.com/paper/2112.08903/) (2021)
- [Mining Latent Structures for Multimedia Recommendation](https://mlsanity.com/paper/2104.09036/) (2021)
- [A Comprehensive Survey on Deep Graph Representation Learning](https://mlsanity.com/paper/2304.05055/) (2023)
- [A Survey on Graph Structure Learning: Progress and Opportunities](https://mlsanity.com/paper/2103.03036/) (2021)
- [FBNETGEN: Task-aware GNN-based fMRI Analysis via Functional Brain Network Generation](https://mlsanity.com/paper/2205.12465/) (2022)
- [Empowering Graph Representation Learning with Test-Time Graph Transformation](https://mlsanity.com/paper/2210.03561/) (2022)
- [Graph Data Augmentation for Graph Machine Learning: A Survey](https://mlsanity.com/paper/2202.08871/) (2022)
- [GSLB: The Graph Structure Learning Benchmark](https://mlsanity.com/paper/2310.05174/) (2023)
- [Does Graph Distillation See Like Vision Dataset Counterpart?](https://mlsanity.com/paper/2310.09192/) (2023)
- [Hypformer: Exploring Efficient Transformer Fully in Hyperbolic Space](https://mlsanity.com/paper/2407.01290/) (2024)
- [A Comprehensive Survey on Data Augmentation](https://mlsanity.com/paper/2405.09591/) (2024)
- [RAIN: Reinforced Hybrid Attention Inference Network for Motion Forecasting](https://mlsanity.com/paper/2108.01316/) (2021)
- [From Machine Learning to Robotics: Challenges and Opportunities for Embodied Intelligence](https://mlsanity.com/paper/2110.15245/) (2021)
- [SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization](https://mlsanity.com/paper/2303.09778/) (2023)
- [Multi-modal Graph Learning for Disease Prediction](https://mlsanity.com/paper/2203.05880/) (2022)
- [GraphEdit: Large Language Models for Graph Structure Learning](https://mlsanity.com/paper/2402.15183/) (2024)
- [Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing](https://mlsanity.com/paper/2208.08302/) (2022)

## Abstract (arXiv)

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.