Weighted Embeddings for Low-Dimensional Graph Representation

Thomas Bläsius, Jean-Pierre von der Heydt, Maximilian Katzmann, Nikolai MaasAAAI 2025 · DOI

TL;DR

This paper introduces "weighted embeddings" as a simpler, yet equally effective, alternative to hyperbolic embeddings for representing complex graphs. Their proposed algorithm, WEMBED, achieves state-of-the-art performance on heterogeneous graphs, outperforming existing Euclidean methods, especially in lower dimensions, while maintaining competitive running times.

What Problem Does This Paper Address?

Machine learning often involves representing complex data, like graphs, as low-dimensional vectors (embeddings). This allows downstream tasks to easily compare and process these objects. While Euclidean space is the standard for these embeddings, recent research suggests that hyperbolic geometry is better suited for hierarchical or scale-free graphs (graphs where node connections follow a power-law distribution). However, hyperbolic embeddings are computationally challenging and difficult to integrate into existing tools. This paper addresses the need for a method that captures the representational power of hyperbolic geometry without its associated complexities.

Methods

The core innovation is the concept of weighted embeddings. Instead of mapping nodes to points in hyperbolic space, nodes are mapped to points in standard Euclidean space, but each node also gets a weight. The distance between two nodes is then calculated using a modified Euclidean distance that incorporates these weights: $dist(u, v) = \frac{||p_u - p_v||}{(w_u w_v)^{1/d}}$. This weighted distance metric is shown to be closely related to hyperbolic distances, offering similar benefits for representing heterogeneous data.

The paper also introduces the WEMBED algorithm to efficiently compute these weighted embeddings. WEMBED works by:

  1. Weight Estimation: Assigning initial weights to nodes based on their degree.
  2. Position Optimization: Using gradient descent to optimize node positions in Euclidean space, minimizing a loss function that encourages connected nodes to be close and unconnected nodes to be far apart.
  3. Geometric Data Structure: Employing an R-tree based structure to efficiently query for neighbors within a certain weighted distance, significantly speeding up the gradient calculation for large graphs. This structure partitions nodes by weight to handle the varying radii of influence.

Datasets

The authors evaluated WEMBED on:

  • Generated Graphs: Specifically, Geometric Inhomogeneous Random Graphs (GIRGs) were used to control graph heterogeneity and evaluate scaling behavior.
  • Real-World Graphs: A dataset of over 2000 real-world networks (n < 10k nodes, m < 50k edges) was used, along with a set of 13 selected, often larger, networks. These graphs were treated as unlabeled, undirected, and unweighted, and reduced to their largest connected component.

Key Insights and Ideas

  • Weighted Space as a Simpler Hyperbolic Alternative: The paper convincingly argues that weighted Euclidean space can capture many of the benefits of hyperbolic geometry for heterogeneous graphs, but with significantly less algorithmic complexity and easier integration into existing tools.
  • WEMBED's Efficiency and Quality: The WEMBED algorithm is not just theoretically sound but also practically effective, achieving high-quality embeddings with competitive running times, often outperforming state-of-the-art Euclidean methods.
  • Heterogeneity is Key: The experiments strongly suggest that the benefits of weighted (and hyperbolic) embeddings are most pronounced in graphs with high degree heterogeneity. This highlights a crucial characteristic of graphs that can be better represented in these non-Euclidean spaces.
  • Algorithmic Tractability: The simplicity of weighted embeddings makes them more amenable to optimization techniques, potentially leading to better performance and easier debugging compared to their hyperbolic counterparts.

Key Results

  • Superiority on Heterogeneous Graphs: WEMBED consistently outperforms state-of-the-art Euclidean embeddings (DeepWalk, VERSE, Force2Vec) on heterogeneous graphs, especially in lower dimensions.
  • Competitive Performance: For less heterogeneous networks or higher dimensions, WEMBED's performance is on par with the best Euclidean methods.
  • Efficiency: WEMBED is significantly faster than the hyperbolic embedder POINCARÉEMBED, often by orders of magnitude, and is competitive with other Euclidean methods. For example, it computes an 8-dimensional embedding for the Citeseer network in under 11 seconds.
  • High Reconstruction Accuracy: WEMBED achieves very high F1-scores (e.g., 0.9999 for Citeseer) for graph reconstruction, indicating excellent embedding quality.
  • Dimensionality Reduction Benefits: The paper shows that WEMBED can achieve high quality with fewer dimensions compared to Euclidean methods. For instance, WEMBED (32 dimensions) often matches or exceeds the performance of VERSE (128 dimensions).

Limitations and Future Work

  • Weight Heuristic: The current weight assignment in WEMBED is a simple heuristic based on node degrees. The authors suggest that optimizing weights using other centrality measures or techniques could further improve performance, especially for hierarchical structures with uniform degrees.
  • Metric Property: Weighted distance is not a true metric (it doesn't satisfy the triangle inequality). While this doesn't seem to hinder performance for heterogeneous graphs, its implications for other graph structures (like trees) and its precise differences from hyperbolic space warrant further rigorous study.
  • Algorithmic Improvements: Future work could explore more advanced negative sampling techniques and further optimize the geometric data structure to improve running times.
  • Applications: The authors envision WEMBED and the concept of weighted embeddings being valuable for downstream tasks like node classification, graph neural networks, and applications in NLP and computer vision.

Summary updated

BibTeX
@inproceedings{blasius2025weighted,
  author = {Thomas Bläsius and Jean-Pierre von der Heydt and Maximilian Katzmann and Nikolai Maas},
  title = {{Weighted Embeddings for Low-Dimensional Graph Representation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i15.33711},
}
Figure