Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters

2021/11/05 by Takanori Maehara, Maehara, Takanori, Hoang Nt +2
Computer Science · Mathematics · #Advanced Graph Neural Networks #Algorithm #Bayesian Modeling and Causal Inference #Complexity and Algorithms in Graphs #Computer science #FOS: Computer and information sciences #Generalizability theory #Generalization #Graph #Line graph #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Mathematics #Random graph #Scalability #Theoretical computer science #Topological graph theory #Voltage graph #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2111.03317

The manuscript is accepted as a poster presentation at NeurIPS 2021. This ArXiv version includes the Appendix

arxiv created 2021/11/05 · openalex publication_date 2021/11/05 · arxiv updated 2021/11/08 · openalex created_date 2022/05/05 · openalex updated_date 2026/08/04

Abstract

Theoretical analyses for graph learning methods often assume a complete observation of the input graph. Such an assumption might not be useful for handling any-size graphs due to the scalability issues in practice. In this work, we develop a theoretical framework for graph classification problems in the partial observation setting (i.e., subgraph samplings). Equipped with insights from graph limit theory, we propose a new graph classification model that works on a randomly sampled subgraph and a novel topology to characterize the representability of the model. Our theoretical framework contributes a theoretical validation of mini-batch learning on graphs and leads to new learning-theoretic results on generalization bounds as well as size-generalizability without assumptions on the input.

Citations

• DeepTox: Toxicity Prediction using Deep Learning
• Interaction Networks for Learning about Objects, Relations and Physics
• Neural Message Passing for Quantum Chemistry
• Learning Combinatorial Optimization Algorithms over Graphs
• Inductive Representation Learning on Large Graphs
• Invariant and Equivariant Graph Networks
• Revisiting Graph Neural Networks: All We Have is Low-Pass Filters
• Wasserstein Distance Guided Representation Learning for Domain Adaptation
• Detecting Functionality-Specific Vulnerabilities via Retrieving Individual Functionality-Equivalent APIs in Open-Source Repositories
• Dynamic Graph CNN for Learning on Point Clouds
• TUDataset: A collection of benchmark datasets for learning with graphs
• DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs
• Generalization bounds for graph convolutional neural networks via Rademacher complexity
• Graph neural networks: A review of methods and applications
• A Comprehensive Survey on Graph Neural Networks

Related

• A Probabilistic Interpretation of Sampling Theory of Graph Signals
• Learning from one graph: transductive learning guarantees via the geometry of small random worlds
• A Local Graph Limits Perspective on Sampling-Based GNNs
• Active Semi-Supervised Learning Using Sampling Theory for Graph Signals
• Estimating the Number of Connected Components in a Graph via Subgraph Sampling