Generalization Bounds for Graph Embedding Using Negative Sampling: Linear vs Hyperbolic
Authors: Atsushi Suzuki, Atsushi Nitanda, jing wang, Linchuan Xu, Kenji Yamanishi, Marc Cavazza
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we provide a generalization error bound applicable for graph embedding both in linear and hyperbolic spaces under various negative sampling settings that appear in graph embedding. Our bound states that error is polynomial and exponential with respect to the embedding space s radius in linear and hyperbolic spaces, respectively, which implies that hyperbolic space s exponential growth property worsens the error. Using our bound, we clarify the data size condition on which graph embedding in hyperbolic space can represent a tree better than in Euclidean space by discussing the bias-variance trade-off. |
| Researcher Affiliation | Academia | Atsushi Suzuki University of Greenwich London, United Kingdom atsushi.suzuki.rd@gmail.com Atsushi Nitanda Kyushu Institute of Technology Fukuoka, Japan nitanda@ai.kyutech.ac.jp Jing Wang University of Greenwich London, United Kingdom jing.wang@greenwich.ac.uk Linchuan Xu The Hong Kong Polytechnic University Hong Kong SAR, China linch.xu@polyu.edu.hk Kenji Yamanishi The University of Tokyo Tokyo, Japan yamanishi@g.ecc.u-tokyo.ac.jp Marc Cavazza National Institute of Informatics Tokyo, Japan marc.cavazza@gmail.com |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper describes theoretical data distributions (Example 1) for analysis but does not use or provide access information for a publicly available or open dataset for empirical training. |
| Dataset Splits | No | The paper does not provide specific dataset split information (exact percentages, sample counts, citations to predefined splits, or detailed splitting methodology) for training, validation, or testing. |
| Hardware Specification | No | The paper does not provide specific hardware details (exact GPU/CPU models, processor types with speeds, memory amounts, or detailed computer specifications) used for running experiments, as it is a theoretical paper. |
| Software Dependencies | No | The paper does not provide specific ancillary software details (e.g., library or solver names with version numbers) needed to replicate experiments, as it is a theoretical paper. |
| Experiment Setup | No | The paper does not contain specific experimental setup details (concrete hyperparameter values, training configurations, or system-level settings), as it is a theoretical paper. |