Learning Discrete Structures for Graph Neural Networks

By Luca Franceschi, Mathias Niepert, Massimiliano Pontil, Xiaojuan He. International Conference on Machine Learning, 2019

522 citations recorded by the source corpus.

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.

View Paper: https://www.semanticscholar.org/paper/1e059de3858c90445f8dce8a48cdb16ce3fc2af0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Jinghao Zhang
2. Xiao Wang
3. Zezhi Shao
4. Xin Zhou
5. Qiang Liu
6. Yanqiao Zhu
7. Chuan Shi
8. Qitian Wu

Citations in the corpus

• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification (2023, methodology): “heterophily [53], over-squashing [2], long-range dependencies [8], and graph incompleteness [11], etc.”
• Node Similarity Preserving Graph Convolutional Networks (2020, methodology): “ion by a Gaussian random field model. Note that LP does not exploit node features. •GCN [15]: GCN is one of the most popular graph convolutional models and our proposed model is based on it. •�NN-GCN [8]: It is a variant of GCN which takes the �-nearest neighbor graph created from the node features ”
• Robust Graph Representation Learning via Neural Sparsification (2020, methodology): “(3) We also incorporate LDS (Franceschi et al., 2019), which works under a transductive setting and learns Bernoulli variables associated with individual edges.”
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings (2020, methodology): “More recently, [14] proposed the LDS model for jointly learning the graph and the parameters of GNNs by leveraging the bilevel optimization technique.”
• Discrete Graph Structure Learning for Forecasting Multiple Time Series (2021, methodology): “For LDS, we follow Franceschi et al. (2019).”
• A Tale of Two Graphs: Freezing and Denoising Graph Structures for Multimodal Recommendation (2022, background): “Other studies [24, 25] place a parameterized distribution or function on edges of the graph and learn the parameters in a supervised manner.”
• Heterogeneous Graph Structure Learning for Graph Neural Networks (2021, methodology): “…graph embedding methods, i.e., MP2Vec (Dong, Chawla, and Swami 2017), HAN (Wang et al. 2019b), HeGAN (Hu, Fang, and Shi 2019), and GTN (Yun et al. 2019), and three graph structure learning related methods, i.e. LDS (Franceschi et al. 2019), Pro-GNN (Jin et al. 2020), and Geom-GCN (Pei et al. 2020).”
• How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision (2022, methodology): “…constrained graph attention network (CGAT1) (Wang et al., 2019a), graph learning-convolutional network (GLCN) (Jiang et al., 2019), learning discrete structure (LDS) (Franceschi et al., 2019), graph agreement model (GAM) (Stretcu et al., 2019), and NeuralSparse (NS in short) (Zheng et al., 2020).”
• Pre-training Enhanced Spatial-temporal Graph Neural Network for Multivariate Time Series Forecasting (2022, methodology): “More recently, an increasing number of works [10, 17, 29] have focused on joint learning of graph structures and graph neural networks to model the dependencies between nodes.”
• Mining Latent Structures for Multimedia Recommendation (2021, methodology): “Although GNNs have shown great power on analyzing graphstructured data, most GNN methods are highly sensitive to the quality of graph structures and usually require a perfect graph structure that are hard to construct in real-world applications [7].”