Research map / Graph learning / Graph algorithms and clustering
Learning Representations for Hierarchies with Minimal Support
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 a minimal sufficient set of adjacency-matrix entries (via signed digraphs) for distinguishing transitively-closed DAGs, and a hierarchy-aware negative sampling that trains box embeddings (GT-BOX) on this reduced set, cutting training examples by up to ~99%.
Problem
Training node embedding models on large directed graphs requires sampling because not all adjacency entries can be observed; it is unclear which entries are needed to uniquely identify a graph with a known structural property such as being a transitively-closed DAG.
Approach
Use signed digraphs to formalize which positive and negative edges uniquely determine a transitively-closed DAG, prove the transitive reduction plus a pruned negative set (FINDMINDISTINGUISHER) is minimal, and pair it with energy models that have transitivity bias (box embeddings) so the reduced edge set suffices for training.
Key results
- On synthetic hierarchies with k=4 negatives, GT-BOX with hierarchy-aware negatives matches or beats full edge set, e.g. AUF1C of 0.909 vs 0.877 on Price's model with reduced negatives.
- Hierarchy-aware negative pruning reduces the negative pool by up to 99.78% on MeSH 2020 (895,739,985 to 1,953,539 edges), and GT-BOX on the reduced set converges to the highest F1 there.
- SIM-VEC degrades sharply (e.g. AUF1C 0.072 to 0.508 range) when trained on the reduced negative set, showing transitivity bias is necessary.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the minimal hierarchy-aware negative edge set E_H* instead of the full edge complement (ablation) | GT-BOX · MeSH 2020 | F1 | Helped |
| Use the minimal hierarchy-aware negative edge set E_H* instead of the full edge complement (ablation) | SIM-VEC · MeSH 2020 | F1 | Hurt |
| Use hierarchy-aware reduced edge sets rather than the original edge sets (ablation) | GT-BOX · Synthetic DAGs | AUF1C | Mixed |
| Use hierarchy-aware reduced edge sets rather than the original edge sets (ablation) | SIM-VEC · Synthetic DAGs | AUF1C | Hurt |
| Use E_H* instead of the full negative edge complement (ablation) | GT-BOX · Price graphs (c = 0.1) | F1 | Mixed |
| Use E_H* instead of the full negative edge complement (ablation) | GT-BOX · Balanced trees, nCRP, and Price synthetic graphs | AUF1C | Helped |
| Use the transitive reduction E_tr rather than the transitive closure E_tc for positive training edges (ablation) | GT-BOX · Synthetic DAGs | AUF1C | Mixed |
| Use hierarchy-aware negative sampling with a model that lacks transitivity bias (ablation) | SIM-VEC · Synthetic DAGs | F1 | Hurt |
| Use GT-BOX rather than SIM-VEC | Node embedding models · Graph modeling experiments | F1 | Helped |
Surprising findings
- SIM-VEC fails to converge to even 0.4 F1 when trained on the pruned negative set, unlike GT-BOX, indicating the reduced set only works with an energy function having transitivity bias.
Limitations
- Results and proofs apply only to transitively-closed DAGs; extension to other graph properties or inductive biases is not straightforward.
- Unclear behavior for graphs that are close to but not strictly transitively closed.
- Hierarchy-aware sampling requires an energy function with transitivity bias; SIM-VEC fails with the reduced set.
Experimental setup
Datasets: MeSH 2020 synthetic balanced trees nCRP graphs Price's model graphs
Benchmarks: MeSH 2020 synthetic balanced trees synthetic nCRP graphs synthetic Price's model graphs
Metrics: F1 AUF1C
Baselines: SIM-VEC uniform random negative sampling over edge complement
Builds on: box embeddings Global T-BOX SampledNCE
Closest papers by meaning
- On the Equivalence between Positional Node Embeddings and Structural Graph Representations (ICLR 2020 · similarity 0.90)
- Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning (ICLR 2025 · similarity 0.89)
- DeepWalking Backwards: From Embeddings Back to Graphs (ICML 2021 · similarity 0.89)
- View Space: Learning Representation across Arbitrary Graphs (ICML 2026 · similarity 0.89)
- iN2V: Bringing Transductive Node Embeddings to Inductive Graphs (ICML 2025 · similarity 0.88)
- Weighted Embeddings for Low-Dimensional Graph Representation (AAAI 2025 · similarity 0.87)
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.