Research map / Graph learning / Knowledge and temporal graphs
Knowledge Graphs Can be Learned with Just Intersection Features
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.
Proposes randomized MinHash/HyperLogLog estimation of k-hop intersection features for KG triples, then trains a simple fully-connected network on them for link prediction, matching or beating KG embedding and GNN baselines.
Problem
Knowledge graph completion via link prediction needs structural information about a triple, but exact k-hop neighborhood intersections are too expensive to compute for KGs with millions of triples.
Approach
Decomposes the triple's k-hop neighborhood intersection into 3-way Jaccard similarity (estimated with asymmetric MinHash bit transforms) times 3-way union cardinality (estimated with HyperLogLog sketches), then feeds these intersection features into a fully-connected network instead of using embeddings or graph convolution.
Key results
- On WN18RR, Intersection Features reaches MRR 0.891-scale top results, exceeding the runner-up by 0.111 MRR as reported in the paper.
- On YAGO3-10, Intersection Features achieves MRR 0.617 and H@10 0.665 versus the best listed baselines around 0.58-0.59 MRR.
- On a small sampled NELL-995 subset, randomized estimated features (MRR 0.160) beat TransE (0.041), ComplEx (0.078) and RotatE (0.005).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use intersection features with the proposed link-prediction network | Knowledge graph link prediction · YAGO3-10 | MRR: 0.694 -> 0.617 | Hurt |
| use intersection features with the proposed link-prediction network | Knowledge graph link prediction · NELL-995 | MRR | Helped |
| use intersection features with the proposed link-prediction network | Knowledge graph link prediction · WN18RR | MRR: 0.485 -> 0.781 | Helped |
| estimate the union instead of measuring it exactly (ablation) | Intersection Features with exact-measured Jaccard · Sampled NELL-995 | MRR: 0.142 -> 0.073 | Hurt |
| estimate Jaccard instead of measuring it exactly (ablation) | Intersection Features with exact-measured union · Sampled NELL-995 | MRR: 0.142 -> 0.146 | Helped |
| estimate both Jaccard and union instead of measuring them exactly (ablation) | Intersection Features · Sampled NELL-995 | MRR: 0.142 -> 0.160 | Helped |
Surprising findings
- A plain fully-connected network on intersection features outperforms GNN-based and embedding-based KG models on large benchmarks.
- Randomized estimated intersection features sometimes perform comparably to or better than exact-measured features on the small NELL-995 subset.
Limitations
- Exact intersection computation is expensive, so the method relies on approximation error from MinHash and HyperLogLog.
- Baseline numbers are partly taken from prior papers or reproductions rather than uniformly re-run.
Experimental setup
Datasets: YAGO3-10 NELL-995 WN18RR FB15K237 FB15K
Benchmarks: YAGO3-10 NELL-995 WN18RR
Metrics: MRR Hits@1 Hits@3 Hits@10
Baselines: TransE TransH TransR DistMult ComplEx RotatE KBGAT CompGCN SE-GNN KRACL AdaProp MEIM
Builds on: TransE MinHash HyperLogLog OpenKE
Closest papers by meaning
- Replacing Paths with Connection-Biased Attention for Knowledge Graph Completion (AAAI 2025 · similarity 0.88)
- Structure Is All You Need: Structural Representation Learning on Hyper-Relational Knowledge Graphs (ICML 2025 · similarity 0.87)
- Towards Global-Topology Relation Graph for Inductive Knowledge Graph Completion (AAAI 2025 · similarity 0.87)
- Context-aware Inductive Knowledge Graph Completion with Latent Type Constraints and Subgraph Reasoning (AAAI 2025 · similarity 0.86)
- Toward a Unified Statistical Theory of Unsupervised Pretraining and Supervised Neural Knowledge Graph Learning (NeurIPS 2026 · similarity 0.86)
- Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion (ICML 2025 · similarity 0.86)
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.