Research map / Graph learning / Graph self-supervised learning
Weighted Embeddings for Low-Dimensional Graph Representation
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 weighted embeddings (positions plus degree-based weights, a simpler proxy for hyperbolic space) and the WEmbed algorithm for low-dimensional graph embedding, showing strong reconstruction gains over Euclidean and hyperbolic baselines on heterogeneous graphs.
Problem
Low-dimensional graph embedding: hyperbolic embeddings represent heterogeneous and hierarchical graphs well but are hard to compute and use downstream, while Euclidean embeddings need high dimensions for such graphs.
Approach
Embed nodes into a Euclidean position space plus a per-node weight, with distance ||p_u - p_v|| / (w_u w_v)^{1/d}; weights are set from degree (w = deg^{d/8}), positions are optimized with a linear threshold loss via Adam, and an R-tree over weight classes gives exact repulsive forces without negative sampling.
Key results
- On citeseer, WEmbed reaches F1 0.9999 at 8 dimensions in under 11 s, while Verse achieves 0.64, 0.977, and 0.992 at 8, 32, and 128 dimensions.
- WEmbed with 32 dimensions is comparable to Verse with 128 dimensions across the 2173-graph real-world set, with WEmbed's advantage growing with graph heterogeneity.
- PoincaréEmbed is outperformed by WEmbed by orders of magnitude in running time at 8 dimensions on the selected graphs, despite using 128 cores.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use weighted distances rather than Euclidean Verse embeddings | WEmbed versus Verse · Citeseer | F1-score: 0.641 -> 0.999 | Helped |
| use weighted distances rather than Euclidean Verse embeddings | WEmbed versus Verse · BlogCatalog | F1-score: 0.335 -> 0.309 | Hurt |
| use weighted distances rather than Euclidean Verse embeddings | WEmbed versus Verse · AstroPh2 | F1-score: 0.278 -> 0.619 | Helped |
| use weighted distances rather than Euclidean Verse embeddings | WEmbed versus Verse · CAIDA | F1-score: 0.319 -> 0.737 | Helped |
| use weighted distances rather than Euclidean Verse embeddings | WEmbed versus Verse · selected real-world graphs | F1-score | Mixed |
| use degree-based weights instead of uniform weights (ablation) | WEmbed · real-world graphs, especially those with high degree heterogeneity | F1-score | Helped |
| use degree-based weights instead of uniform weights (ablation) | WEmbed · GIRGs with varying power-law exponent | F1-score | Helped |
| use negative sampling for repulsive forces (ablation) | WEmbed · graph reconstruction | F1-score | Hurt |
| add a multi-level approach (ablation) | WEmbed · very low-dimensional embeddings | embedding quality | Helped |
Surprising findings
- Verse's quality is essentially independent of the power-law exponent in GIRG experiments, unlike the other Euclidean methods.
- Negative sampling resulted in substantially worse weighted embeddings, so WEmbed computes exact repulsive forces instead.
Limitations
- Weighted distance is not a metric (violates triangle inequality).
- Degree-based weights cannot embed trees with uniform degree distribution; the weights are not optimized.
- Multi-level approach only helps in very low dimensions per preliminary experiments.
Experimental setup
Datasets: real-world graph collection (2173 graphs, restricted to n<=10k and m<=50k) GIRG generated graphs Citeseer Cora BlogCatalog AstroPh CAIDA
Benchmarks: real-world graph collection (2173 graphs) selected real-world graphs (13) GIRG generated graphs
Metrics: F1-score for graph reconstruction embedding time in seconds
Baselines: DeepWalk Verse Force2Vec PoincaréEmbed
Builds on: Poincaré embeddings hyperbolic random graphs Verse Force2Vec DeepWalk
Closest papers by meaning
- Random Laplacian Features for Learning with Hyperbolic Space (ICLR 2023 · similarity 0.91)
- Hyperbolic Embeddings of Supervised Models (NeurIPS 2024 · similarity 0.90)
- Tight and fast generalization error bound of graph embedding in metric space (ICML 2023 · similarity 0.90)
- Generalization Bounds for Graph Embedding Using Negative Sampling: Linear vs Hyperbolic (NeurIPS 2021 · similarity 0.90)
- How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings (ICLR 2025 · similarity 0.90)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.88)
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.