Research map / Graph learning / Knowledge and temporal graphs
PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives the first transductive PAC-Bayesian generalization bounds for knowledge graph representation learning by unifying GNN encoders and shallow KG embedding decoders in a generic ReED framework, and validates the bound's critical factors empirically on three KGs.
Problem
Generalization bounds for knowledge graph representation learning (KGRL) methods for knowledge graph completion via triplet classification have rarely been studied, and existing GNN bounds assume single-relation graphs and graph classification.
Approach
A generic ReED framework (relation-aware message-passing encoder plus translational-distance or semantic-matching triplet decoder) subsumes at least 15 KGRL models; a transductive PAC-Bayesian bound for deterministic classifiers, obtained by adding Gaussian weight perturbations, is instantiated for ReED with factors such as the graph diffusion norm, parameter count, weight norms, and depth.
Key results
- Across all three datasets, the mean aggregator yields lower generalization errors than the sum aggregator.
- Generalization errors increase as the weight-norm bound s and the number of layers L increase, matching the theoretical corollary.
- Generalization error increases with maximum dimension d on FB15K237 when using BERT-derived features reduced to 32 dimensions by PCA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use a mean aggregator instead of a sum aggregator | ReED · three real-world knowledge graphs | generalization error | Helped |
| increase the Frobenius norm of learnable matrices s | ReED · three real-world knowledge graphs | generalization error | Hurt |
| increase the number of RAMP encoder layers L | ReED · three real-world knowledge graphs | generalization error | Hurt |
| increase maximum representation dimension d | ReED · FB15K-237 | generalization error | Hurt |
Limitations
- Graph attention networks cannot be expressed in the current ReED form.
- Bounds are loose upper limits; the empirical analysis checks trends rather than tightness.
- Analysis restricted to transductive setting with a finite full triplet set and KL-divergence PAC-Bayes.
Experimental setup
Datasets: FB15K237 CoDEx UMLS
Benchmarks: FB15K237 CoDEx UMLS
Metrics: generalization error expected loss empirical margin loss
Baselines: R-GCN WGCN CompGCN TransR RotatE DistMult ANALOGY
Builds on: PAC-Bayesian bounds for GNNs R-GCN CompGCN transductive PAC-Bayes (Corollary 7)
Closest papers by meaning
- Toward a Unified Statistical Theory of Unsupervised Pretraining and Supervised Neural Knowledge Graph Learning (NeurIPS 2026 · similarity 0.87)
- Towards Global-Topology Relation Graph for Inductive Knowledge Graph Completion (AAAI 2025 · similarity 0.86)
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.85)
- Towards Foundation Models for Knowledge Graph Reasoning (ICLR 2024 · similarity 0.85)
- UniGTE: Unified Graph–Text Encoding for Zero-Shot Generalization across Graph Tasks and Domains (NeurIPS 2025 · similarity 0.85)
- Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.