Report
Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters
| العنوان: | Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters |
|---|---|
| المؤلفون: | Maehara, Takanori, NT, Hoang |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Statistics |
| مصطلحات موضوعية: | Computer Science - Machine Learning, Statistics - Machine Learning |
| الوصف: | 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. Comment: The manuscript is accepted as a poster presentation at NeurIPS 2021. This ArXiv version includes the Appendix |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2111.03317 |
| رقم الانضمام: | edsarx.2111.03317 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |