1. Bibliographic Information

1.1. Title

VoRec: Enhancing Recommendation with Voronoi Diagram in Hyperbolic Space

1.2. Authors

• Yong Chen: Institute of Artificial Intelligence, Xiamen University, China.
• Li Li: School of Artificial Intelligence, Shenzhen Polytechnic University, China.
• Wei Peng: Department of Psychiatry and Behavioral Sciences, Stanford University, USA.
• Songzhi Su (Corresponding Author): Institute of Artificial Intelligence, Xiamen University, China.

1.3. Journal/Conference

This paper was published in the Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '25). SIGIR is widely regarded as the premier global conference for research in information retrieval, information systems, and recommendation technologies, known for its high selectivity and rigorous peer-review process.

1.4. Publication Year

Published: July 13, 2025.

1.5. Abstract

The sparse nature of user-item interactions in recommender systems often degrades the quality of embedding representations. While existing methods use auxiliary information like item tags to mitigate this, they frequently overlook the structured spatial distribution and logical relations within the embedding space. To address this, the authors propose VoRec, a framework that utilizes the Voronoi diagram in hyperbolic space. By partitioning the space into tag-specific subspaces, VoRec captures membership, exclusion, and hierarchical relations between tags and items. The framework integrates two hyperbolic models (Poincaré and Lorentz) and employs unique active (contrastive learning) and passive (adaptive parameter freezing) strategies to optimize the Voronoi sites. Experiments on four benchmark datasets show an average improvement of 16.35% in Recall and NDCG over state-of-the-art baselines.

1.6. Original Source Link

• Official Source: ACM Digital Library / SIGIR '25

• Code Implementation: GitHub Repository

• Publication Status: Officially published.

  ---

2. Executive Summary

2.1. Background & Motivation

Recommender systems are critical for managing information overload, but they face a fundamental "Cold Start" or "Data Sparsity" problem: most users only interact with a tiny fraction of available items. To solve this, researchers use tags (e.g., "History," "Europe") to group items. However, current methods treat tags as "flat" or ignore how they should be physically organized in the mathematical space where items live (the embedding space).

The authors identify that standard Euclidean space (the flat geometry we learn in school) is poorly suited for hierarchical data. As hierarchies expand, Euclidean space "cramps" the data. Furthermore, previous work fails to model the spatial structure of tags—how different tag regions should be separated, nested, or distributed to prevent "over-recommendation" of certain item clusters.

2.2. Main Contributions / Findings

• Introduction of Voronoi Diagrams to Recommendation: The paper is the first to use Voronoi diagrams—a geometric way of partitioning space—to create distinct "territories" for different tags in a recommendation model.

• Hyperbolic Space Integration: By operating in Hyperbolic space, which expands exponentially, the model can naturally accommodate complex hierarchies (like tag taxonomies) without the distortion found in Euclidean space.

• Dual-Model Hybridization: It combines the Poincaré model (best for visualization and distance) with the Lorentz model (best for stable mathematical operations) to get the best of both worlds.

• Site Update Strategies: It introduces Active Updates (using Contrastive Learning to keep tags distinct) and Passive Updates (adaptive freezing based on Information Gain) to ensure the spatial partitions are stable and effective.

• Performance: VoRec achieved massive gains, particularly on sparse datasets like Amazon Clothing, where it outperformed previous methods by over 38%.

  ---

3. Prerequisite Knowledge & Related Work

3.1. Foundational Concepts

3.1.1. Embedding Space

In machine learning, an embedding is a way of representing a discrete object (like a user, a book, or a tag) as a vector of numbers in a high-dimensional space. The goal is to place "similar" items close together so the computer can calculate their relationship using distance formulas.

3.1.2. Hyperbolic Geometry

Most AI models use Euclidean space (flat). However, Hyperbolic space has a constant negative curvature. Imagine a Pringle chip or a saddle. In this geometry, the "volume" of space grows exponentially as you move away from the center. This makes it perfect for trees or hierarchies, because a tree's number of branches also grows exponentially with depth.

• Poincaré Disk: A model of hyperbolic space confined within a circle.
• Lorentz (Hyperboloid) Model: Another model that is mathematically easier to optimize for computers.

3.1.3. Voronoi Diagram

A Voronoi Diagram is a partition of a plane into regions close to each of a given set of objects (called sites). For every site, there is a corresponding region (a Voronoi cell) consisting of all points closer to that site than to any other. In VoRec, tags are the "sites," and items fall into the "cells" belonging to their tags.

3.1.4. Graph Convolutional Networks (GCN)

A GCN is a type of neural network that operates on graphs (networks of nodes and edges). It allows a node (like a User) to learn from its neighbors (the Items they liked).

• LightGCN Formula: A popular baseline mentioned in the paper: $ e_{u}^{(k+1)} = \sum_{i \in \mathcal{N}_u} \frac{1}{\sqrt{|\mathcal{N}_u||\mathcal{N}_i|}} e_i^{(k)} $ This formula shows how a user's embedding $e_u$ at layer $k+1$ is updated by averaging the embeddings of the items they interacted with ($\mathcal{N}_u$).

3.2. Previous Works and Technological Evolution

The field moved from Matrix Factorization (basic math tables) to Metric Learning (treating recommendation as a distance problem, e.g., CML). Later, Graph Neural Networks (e.g., LightGCN) became dominant by capturing high-order relationships (friends of friends). Recently, researchers started using Hyperbolic space (e.g., HGCF) to handle hierarchies. VoRec is the next step in this evolution, adding geometric partitioning via Voronoi diagrams to the hyperbolic graph framework.

---

4. Methodology

4.1. Principles

The core intuition of VoRec is that an item belongs to a specific semantic "territory" defined by its tags. By using a Weighted Voronoi Diagram in Hyperbolic Space, the model can explicitly enforce that items stay within their tag's boundary, that parent tags (like "Clothes") contain child tags (like "Shirts"), and that unrelated tags (like "Law" and "History") stay far apart.

4.2. Core Methodology In-depth (Layer by Layer)

4.2.1. Hyperbolic Weighted Voronoi Diagram (HWVD)

In a standard Voronoi diagram, every site is equal. In VoRec, the authors use a Multiplicative Weighted Voronoi Diagram. This allows some tags (sites) to have more "influence" or "area" than others, which is perfect for modeling hierarchies (a parent tag is "heavier" and covers more space than its children).

The authors define the Voronoi cell for a tag site $t_i$ using a distance function $D_{\hat{P}}$ that incorporates a learnable weight $w_i$. The distance from a point $x$ to a tag site $y$ with weight $w$ in the Poincaré model is: $ D_{\hat{P}}(x, y, w) = \frac{d_P(x, y)}{e^w} $ Where:

• $d_P(x, y)$ is the standard Poincaré distance: $ d_P(x, y) = \frac{2}{\sqrt{c}} \mathrm{arctanh}(\sqrt{c} | -x \oplus_c y |) $

• $\oplus_c$ is the Möbius addition (the hyperbolic version of adding two vectors): $ x \oplus_c y = \frac{(1 + 2c \langle x, y \rangle + c |y|^2)x + (1 - c|x|^2)y}{1 + 2c \langle x, y \rangle + c^2 |x|^2 |y|^2} $

• $e^w$ is the weight of the tag, which scales the distance (larger $w$ makes the effective distance smaller, making the tag's cell larger).

  The Voronoi cell $Vor(t_i)$ is then the set of all points $x$ where the weighted distance to $t_i$ is the smallest: $ Vor(t_i) = { x \in \mathcal{P}^n : D_{\hat{P}}(x, t_i, w_i) \leq D_{\hat{P}}(x, t_j, w_j), \forall t_j \in \mathcal{T} } $

To ensure items actually fall into their correct Voronoi cells, the authors use a Voronoi Hinge Loss: $ \mathcal{L}{vor} = \sum{v^{\mathcal{P}} \in \mathcal{V}} \sum_{t_i \in \mathcal{T}} [ D_{\mathcal{P}}(v^{\mathcal{P}}, t_o, w_o) - D_{\mathcal{P}}(v^{\mathcal{P}}, t_i, w_i) + m_1 ]_+ $ In this formula, $t_o$ is the actual tag of item $v$, and $t_i$ are other tags. This loss forces the distance to the correct tag to be smaller than the distance to any other tag by at least a margin $m_1$.

4.2.2. HGCN-based Recommendation (Lorentz Model)

While partitioning happens in the Poincaré model, the actual "message passing" (learning from neighbors in the user-item graph) happens in the Lorentz model because it is more numerically stable.

1. Mapping: Items are moved from Poincaré ($\mathcal{P}$) to Lorentz ($\mathcal{L}$) using the mapping $p^{-1}$: $ p^{-1}(x_1, \dots, x_n) = \frac{(1 + c|x|^2, 2x_1, \dots, 2x_n)}{1 - c|x|^2} $
2. Projection to Tangent Space: Because you cannot "add" points on a curved surface directly, they are projected to a "flat" tangent space using the Logarithmic Map: $ h_u^{\mathcal{L}, 0} = \log_o^c(u^{\mathcal{L}}) $
3. Aggregation: Neighbors' information is averaged in this flat space: $ h_u^{\mathcal{L}, l+1} = h_u^{\mathcal{L}, l} + \frac{1}{|\mathcal{N}u|} \sum{v \in \mathcal{N}_u} h_v^{\mathcal{L}, l} $
4. Projection Back: The result is pushed back onto the curved Lorentz surface using the Exponential Map ($\exp_o^c$).
5. Recommendation Loss: The final task is optimized using a triplet loss based on the Lorentz distance $d_\ell$: $ \mathcal{L}{rec} = \sum{(u, v_p, v_q)} [d_\ell(u^{\mathcal{L}}, v_p^{\mathcal{L}}) - d_\ell(u^{\mathcal{L}}, v_q^{\mathcal{L}}) + m_2]_+ $ Where $v_p$ is an item the user liked and $v_q$ is one they didn't.

4.2.3. Voronoi Site Update Strategies

The tag sites themselves need to move to find the best locations.

• Active Update (Contrastive Learning): To keep parent and child tags close but ensure different tags stay apart, they use an InfoNCE loss: $ \mathcal{L}{cl} = - \sum{t_i \in \mathcal{T}'} \log \frac{\exp(d_P(t_i, t_p) / \tau)}{\sum_{t_j \neq i} \exp(d_P(t_i, t_j) / \tau)} $ This pulls tag $t_i$ toward its parent $t_p$ and pushes it away from all other tags $t_j$.
• Passive Update (Freeze Site Parameters): Voronoi boundaries are very sensitive. To prevent the model from becoming unstable, the authors calculate the Information Entropy $H$ of the item-to-tag distribution: $ H = - \sum_{v \in \mathcal{V}} \pi_v^\top \log(\pi_v) $ They use the Information Gain ($IG = H' - H$) to decide how long to "freeze" the tag positions, allowing items time to settle into their cells.

4.2.4. Final Optimization

The total loss is a weighted sum: $ \mathcal{L} = \alpha_u \mathcal{L}{rec} + \lambda_1 \mathcal{L}{vor} + \lambda_2 \mathcal{L}_{cl} $ Where \alpha_u = d_\ell(u^{\mathcal{L}}, o) is a dynamic scaling factor that helps the model learn better as it moves further into the hyperbolic space.

---

5. Experimental Setup

5.1. Datasets

The authors used four real-world datasets from the Amazon Reviews '23 collection and Ciao:

• Ciao: A smaller dataset with very few tags (28) but higher density.

• CDs & Vinyl (CD): A medium dataset with 375 tags.

• Clothing: A large, extremely sparse dataset.

• Book: The largest dataset with over 1.3 million interactions.

  The following are the statistics from Table 1 of the original paper:

  Dataset	# Users	# Items	# Interactions	# Tags	Density
  Ciao	5,180	8,836	104,905	28	2.3e-3
  CD	22,170	20,089	519,283	375	1.2e-3
  Clothing	47,252	25,885	720,242	272	5.9e-4
  Book	56,832	50,370	1,337,594	392	4.7e-4

5.2. Evaluation Metrics

1. Recall@K:
   • Definition: Measures the proportion of items the user actually liked that were successfully found in the top-K recommended list.
   • Formula: $\mathrm{Recall@K} = \frac{|\mathrm{Rel} \cap \mathrm{Rec}_K|}{|\mathrm{Rel}|}$
   • Explanation: $\mathrm{Rel}$ is the set of relevant items (ground truth), and $\mathrm{Rec}_K$ is the set of the top K recommended items.
2. NDCG@K (Normalized Discounted Cumulative Gain):
   • Definition: Not only checks if the right items were recommended but also if they were placed at the top of the list (ranking quality).
   • Formula: $\mathrm{NDCG@K} = \frac{\mathrm{DCG@K}}{\mathrm{IDCG@K}}$ where \mathrm{DCG@K} = \sum_{i=1}^K \frac{2^{rel_i}-1}{\log_2(i+1)}
   • Explanation: $rel_i$ is the relevance of the item at rank $i$. IDCG is the "Ideal" DCG (perfect ranking), used for normalization.

5.3. Baselines

The paper compares against 14 models, including:

• Traditional: BPRMF (Matrix Factorization).

• Metric Learning: CML, HyperML (Hyperbolic metric learning).

• Tag-based: AGCN (Graph + Attributes).

• Graph-based: LightGCN, HGCF (Hyperbolic GCN), HRCF.

• Advanced: $LogiRec++$ (Logic-based hyperbolic recommendation).

  ---

6. Results & Analysis

6.1. Core Results Analysis

VoRec significantly outperformed all baselines. On the Clothing dataset, which is the most sparse, VoRec showed a massive 38.68% improvement in Recall@10. This suggests that the geometric partitioning is most helpful when data is scarce, as it provides a strong "prior" structure for the items to follow.

The following are the results from Table 2 of the original paper:

6.2. Ablation Studies

The authors tested what happens if you remove parts of the model (Table 3):

• w/o VD (No Voronoi Diagram): Performance dropped by 12-21%, proving the diagram is the most vital innovation.
• w/o H (No Hyperbolic Space): Moving to flat Euclidean space hurt performance, especially on datasets with many tags, confirming that hyperbolic geometry is better for hierarchies.
• w/o CL/Fz (No Update Strategies): Performance dropped slightly, showing that these refinement strategies help stabilize the model.

6.3. Visualization and Evolution

Figure 7 in the paper shows how item embeddings evolve:

1. Warm-up: Items are a mess in the center.
2. Exploration: Items spread out to explore the Voronoi cells.
3. Convergence: Items settle into tight, clear clusters defined by their tags. This visualization confirms that the Voronoi boundaries successfully "corral" items into logical regions.

---

7. Conclusion & Reflections

7.1. Conclusion Summary

VoRec successfully demonstrates that geometric space partitioning via Voronoi diagrams is a powerful tool for recommendation. By combining the capacity of hyperbolic space with the logical structure of tag taxonomies, the model creates a highly organized embedding space. This organization allows the model to better understand user preferences even when interaction data is sparse, leading to significant performance gains over modern graph-based and logic-based methods.

7.2. Limitations & Future Work

• Tag Dependency: The model relies heavily on the existence of a tag taxonomy. For datasets without tags or with poor-quality tags, the benefits might be limited.
• Computational Complexity: While the authors mention it reduces overhead compared to complex knowledge graphs, calculating Voronoi boundaries in hyperbolic space for thousands of tags might be computationally demanding.
• Future Direction: The authors suggest looking at density-based partitioning within Voronoi cells to distinguish between popular and niche items within the same tag.

7.3. Personal Insights & Critique

This paper is a fascinating bridge between computational geometry and machine learning. The use of the "Information Gain" to adaptively freeze parameters is a clever solution to the "shimmering" problem where boundaries move too fast for the model to learn. However, one potential issue not deeply explored is how the model handles "multi-tag" items. If an item belongs to three tags, which Voronoi cell should it "live" in? The current hinge loss might force it into one, potentially losing the nuance of the other two. Future iterations could explore "Fuzzy Voronoi Diagrams" where items can belong to multiple regions simultaneously.