Research map / Graph learning / Graph algorithms and clustering

How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings

ICLR 2025 · Graph learning › Graph algorithms and clustering · approach: Graph embedding and spectral sparsification · 0 citations (OpenAlex)

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 metric (Euclidean latent distance) node embeddings with a logarithmic search and KD-tree/HBDM-based linearithmic scaling to find exact low-dimensional graph embeddings, reaching much lower dimensions than LPCA-based prior work, including exact reconstruction of graphs up to a million nodes.

Problem

Exact network reconstruction via low-dimensional embeddings is poorly understood: the lowest exact embedding dimension is unknown, prior work gave only coarse estimates with LPCA on small graphs, and exact checks are quadratic in the number of nodes.

Approach

Replace the LPCA inner-product reconstruction with a Euclidean latent distance model (threshold on distance against a radius beta), which provably needs at least two fewer dimensions; combine a binary search over dimensions with SVD warm starts, KD-tree reconstruction checks, and HBDM hierarchical likelihood approximation followed by zero-margin hinge-loss refinement for linearithmic scaling.

Key results

• On Cora, the L2 latent distance model reaches exact reconstruction at D*=6 (mean 6.2 over 5 searches) versus 16 reported by Chanpuriya et al. for LPCA-based embedding.
• On ca-HepPh the L2 model reaches D*=16 versus 32 previously reported; on p2p-Gnutella04 D*=14 versus 32.
• The method achieves exact reconstruction for graphs up to a million nodes (roadNet-PA and com-amazon are reported as large-scale examples, with the tighter bound left for future work).

Measured effects reported in the paper

Surprising findings

• The L2 metric model reliably found D=1 on a synthetic block graph while LPCA needed D=3 and was unreliable.
• Stochastic random geometric network generation prevented recovery of the exact embedding dimension, even in high dimensions, while deterministic thresholding allowed exact recovery.

Limitations

• The search returns an upper bound on the exact embedding dimension rather than the true minimum, and optimization can get stuck in local minima.
• Results for the largest networks (com-amazon, roadNet-PA) were not searched for tighter bounds due to computational cost.
• Exact embeddings can encode zero links, so link-prediction use requires treating unobserved links as missing.

Experimental setup

Datasets: Cora Citeseer Pubmed ca-HepPh ca-GrQc Facebook Wiki-Vote p2p-Gnutella04 com-amazon roadNet-PA

Benchmarks: Cora Citeseer Pubmed ca-HepPh ca-GrQc Facebook Wiki-Vote p2p-Gnutella04 com-amazon roadNet-PA

Metrics: exact embedding dimension (D*) Frobenius reconstruction error misclassified dyads degree, clustering and shortest-path distributions of recons

Baselines: LPCA latent eigenmodel (R_EIG) Chanpuriya et al. reported dimensions case-control sampling random node sampling

Builds on: LPCA exact embedding (Chanpuriya et al.) latent distance model HBDM (Nakis et al.) latent eigenmodel

Closest papers by meaning

• Node Embeddings and Exact Low-Rank Representations of Complex Networks (NeurIPS 2020 · similarity 0.91)
• Representation Learning for Scale-Free Networks (AAAI 2018 · similarity 0.91)
• Weighted Embeddings for Low-Dimensional Graph Representation (AAAI 2025 · similarity 0.90)
• On the Effect of Misspecifying the Embedding Dimension in Low-rank Network Models (ICML 2026 · similarity 0.89)
• Community Detection Guarantees using Embeddings Learned by Node2Vec (NeurIPS 2024 · similarity 0.87)
• Information Loss and Disparate Effects in Network Embeddings (NeurIPS 2026 · similarity 0.87)