Graph-Theoretic Insights into Bayesian Personalized Ranking for Recommendation

We thank reviewer uD2G for the concise summary of our paper. Below we address his/her concerns.

Question 1:

"The inclusion and meaning of the abstract node need to be more clearly presented, since this is the reason why the calculation method of the original BPR loss can be understood as a 2-hop path. This is also one of the core issues addressed in this paper."

Response:
We are appreciative to the reviewer for the thoughtful suggestion. The concept of "abstract node" is used as a theoretical tool to reinterpret the inner product in BPR from a graph perspective. Specifically, the user embedding $\mathbf{e}_u$ and item embedding $\mathbf{e}_v$ are both vectors in the same latent space, and their inner product $\langle \mathbf{e}_u, \mathbf{e}_v \rangle$ can be viewed as a projection through a shared set of latent dimensions. Each dimension of this space can be interpreted as an abstract node that connects to both users and items.

To make this more interpretable in topological terms, we consider each latent dimension as an "abstract node" that connects to all users and items. Under this view, the inner product corresponds to counting 2-hop connections: $user \rightarrow abstract node \rightarrow item$.

This analogy allows us to model the BPR loss as a function of 2-hop connectivity in a user-item-abstract network. This formulation reveals that BPR only captures coarse structural similarity (i.e., 2-hop paths) and motivates us to extend it to TopoLa distance, which incorporates higher-order even-hop paths to better reflect global graph topology.

Question 2:

"Although the paper provides reasonable insights, the novelty of the proposed BPR+ has limitations."

Response:
We are grateful to the reviewer for the thoughtful comments on our method. The primary novelty of our work lies in re-examining the widely used BPR loss from a graph-theoretic and network geometry perspective. To the best of our knowledge, this line of thinking has not been explored before. This reinterpretation not only reveals the limitations of the conventional inner product formulation, which effectively corresponds to 2-hop connectivity, but also provides a foundation for integrating latent hyperbolic geometry with graph neural networks.

Based on this theoretical understanding, we introduce the TopoLa distance as a fine-grained topological metric derived from multi-hop path structures, going far beyond BPR's coarse similarity modeling. Building upon this insight, we propose BPR+, which can be viewed as a significantly generalized framework. Its relevance extends beyond BPR, as many other widely-used techniques in graph representation learning, including InfoNCE, self-attention, and contrastive learning, also rely on inner product similarity. Our work highlights the limitations of such similarity measures in theory and provides a new direction for rethinking them from a topological perspective.

We believe this shift offers valuable insight for the community, and hope that future research will further build upon this line of thought.

Question 3:

"There is a lack of comparison with related work. More relevant work would help readers understand the background and the contributions of this paper."

Response:
We sincerely thank the reviewer for this helpful suggestion. We review many representative extensions of BPR. Most of them focus on improving input features, loss functions, or specific application scenarios, while keeping the core scoring function, namely the inner product, unchanged. For example, ABPR [1] models feedback uncertainty, VBPR [2] integrates visual features, DPR [3] addresses item recommendation bias, and LkP [4] focuses on ranking diversity. These methods significantly improve BPR from different perspectives, but none of them question or modify the use of the inner product itself.

In contrast, our work focuses on this fundamental assumption. We revisit BPR from a geometric and graph-theoretic perspective and analyze how the inner product may fail to capture meaningful topological relationships, especially under conditions such as over-smoothing. Based on this observation, we propose using a network geometry-based distance (TopoLa) to replace the inner product as a new way to compute sample similarity.

[1] Pan W, Zhong H, Xu C, et al. Adaptive Bayesian personalized ranking for heterogeneous implicit feedbacks[J]. Knowledge-Based Systems, 2015, 73: 173-180.
[2] He R, McAuley J. VBPR: visual bayesian personalized ranking from implicit feedback[C]//Proceedings of the AAAI conference on artificial intelligence. 2016, 30(1).
[3] Zhu Z, Wang J, Caverlee J. Measuring and mitigating item under-recommendation bias in personalized ranking systems[C]//Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval. 2020: 449-458.
[4] Liu Y, Walder C, Xie L. Learning k-determinantal point processes for personalized ranking[C]//2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024: 1036-1049.

We are grateful for the reviewer's thoughtful engagement with our work and their constructive suggestions. Below are our responses to each raised point.

Question 1:

"To which power the computations in equations 10-11 are computed?"

Response:
We thank the reviewer for raising this valuable point regarding the efficiency of computing TopoLa distance. In our formulation, Eq.10 represents a direct matrix-based calculation of even-hop path counts between nodes. It is designed primarily to intuitively illustrate how structural information is aggregated across multiple hops. While it captures all even-length paths, repeated matrix multiplications (e.g., $\boldsymbol{A}^2$, $\boldsymbol{A}^4$, ..., $\boldsymbol{A}^{2k}$) can indeed lead to high computational cost, especially for large $k$. This limitation is also reflected in the runtime analysis shown in Figure 5.

To address this, we introduce Eq.11, which is derived from Eq.10 via singular value decomposition (SVD). By applying SVD to the embedding matrix, the even-hop contributions are encoded into the diagonal matrix $\boldsymbol{\Sigma}$, and since only its diagonal elements are non-zero, the cost of computing high powers of $\boldsymbol{\Sigma}$ becomes constant-time, i.e., $O(1)$ for each exponentiation. This dramatically reduces the overall computational burden of accumulating even-hop contributions.

Because of this optimization, the cost of computing even-hop path contributions becomes independent of the hop count, allowing us to incorporate an arbitrary number of hops without any significant increase in runtime. In our experiments, we observed that contributions from paths beyond 40 hops have a negligible effect on the final TopoLa distance. Therefore, we truncate the expansion at 40 hops to balance accuracy and efficiency.

Question 2:

"Can the proposed approach be potentially applied to monopartite graphs (i.e., graphs with nodes from one single partition, such as citation networks)? And, in case, which would it be the implication of that? Could it be beneficial also to them?"

Response:
Thanks for raising this subtle question. Our method is inherently compatible with monopartite graphs. As shown in the definition of the embedding matrix $\boldsymbol{E}$ in the paper, we concatenate user and item embeddings into a single matrix. This formulation treats users and items as nodes of the same type within a unified latent space, which aligns well with the concept of a monopartite graph.

Moreover, the proposed TopoLa distance is defined based on the connectivity patterns (i.e., multi-hop paths) between nodes, regardless of their original semantic roles or partitions. Whether the graph consists of user-item pairs or homogeneous nodes (e.g., in citation networks), our method captures the global structural relationships through even-hop connectivity and thus remains applicable and effective in such scenarios.

Question 3:

"The literature has shown how computing more than 1 negative for each positive item in the BPR loss can be beneficial to improve the performance [*]. How this would impact on your loss function? Would this increase the computational complexity?"

Response:
We thank the reviewer for asking this interesting question. Our current implementation of BPR+ follows the original BPR setting, which samples one negative item per positive instance. However, as the reviewer observed, sampling multiple negatives per positive can often lead to improved model performance.

The proposed BPR+ framework can naturally accommodate this extension. In fact, the TopoLa-based formulation remains unchanged under multiple negative sampling, as the abstract network is constructed per batch and the TopoLa distance is computed based on all sampled pairs. The only difference lies in the increased number of user-item pairs within each batch.

This extension would linearly increase the computational cost with respect to the number of negatives per positive, but the additional overhead remains tractable, especially given the fact that our method uses an SVD-based optimization in TopoLa computation. We appreciate the suggestion and will consider including this variant in future work.

We thank reviewer fhF3 for his/her thorough and insightful comments on our method as well as its theoretical analysis. We are highly appreciative of the positive rating. Below are our responses to each raised point.

Question 1:

"Firstly, the paper acknowledges the over-smoothing phenomenon in higher layers of LightGCN while proposing the new method involving multi-layer aggregation. I would appreciate clarification on whether the TopoLa-based approach is susceptible to over-smoothing, or if specific design optimizations have been implemented to prevent this issue."

Response:
We are grateful to the reviewer for raising this subtle and important issue. Compared to BPR, the introduction of latent hyperbolic geometry in BPR+ alleviates the negative effect of over-smoothing on relationship estimation.

Over-smoothing refers to the convergence of node features as the network depth increases, leading to indistinguishable embeddings across nodes. In the case of BPR, which relies on inner product to evaluate pairwise relationships, this convergence causes the scores between different sample pairs to become numerically similar. As illustrated in Figure 4a, when dot products are concentrated around a constant value (e.g., 20), the corresponding topological similarities can still vary significantly (e.g., from 20% to 50%). This implies that BPR could yield coarse-grained and uninformative relationship scores under over-smoothed conditions.

Contrarily, BPR+, by incorporating latent hyperbolic geometry, is more sensitive to subtle structural differences in the graph. Even if node features are similar, the TopoLa distance is still able to reflect the variation in topological similarity between nodes (Figure 4b). As a result, BPR+ provides a more fine-grained and discriminative measurement of node relationships, even in the presence of over-smoothing.

Question 2:

"Then, the proposed methodology demonstrates that the addition/removal of a single node can influence representation learning across the entire graph. This characteristic raises concerns about its adaptability to real-world scenarios with dynamic user/item pools. I would like to understand the authors' analysis and potential improvements regarding this aspect."

Response:
We sincerely thank the reviewer for this insightful and important question. We acknowledge that the TopoLa distance is conceptually defined over the entire abstract network and thus reflects a form of global structural modeling. However, in practice, our method does not compute TopoLa distance over the full user-item graph at each step. Instead, the BPR+ loss is calculated within each mini-batch, and the corresponding abstract network is constructed only from the users and sampled items in that batch. This means that the actual computations are localized, and the full graph structure is not directly involved in each training step.

Taking LightGCN as an example, with a batch size of 1,500 and a network containing 40,000 items, introducing or removing a single item changes its sampling probability by approximately $1500/40000 = 3.75\%$. This change is minor and only affects whether the node is sampled into a future batch. As a result, the composition of nodes in any specific batch remains relatively stable, and the structure of the corresponding abstract network exhibits minimal variation.

Therefore, while the TopoLa distance can reflect how structural relations change with node addition/removal, such changes only take effect when the node is actually sampled into the batch. Since loss computation is restricted to the batch, the representation learning process remains stable and unaffected by a single node's presence or absence unless it is sampled.

In summary, the proposed method benefits from structural awareness via TopoLa, but the training is performed on localized, batch-level networks, which makes it naturally robust to small-scale perturbations in the overall user/item pool.

Question 3:

"Third, beyond time complexity, space complexity represents another critical consideration for graph algorithms, as storing intermediate node states often requires substantial memory resources. Has the new method been evaluated in terms of its space complexity requirements? These three points constitute my primary questions after careful reading."

Response:
We are very thankful for the constructive comments and suggestions. As the main modification of BPR+ lies in replacing the inner product with the TopoLa distance, the space complexity primarily depends on how the relevant matrix representations are stored and computed.

In BPR, computing the inner product requires storing the embedding matrix $\boldsymbol{E} \in \mathbb{R}^{(m+n) \times N_e}$, where $m$ and $n$ are the numbers of items and users, respectively, and $N_e$ is the embedding size. This leads to a space complexity of $O((m+n) N_e)$.

In contrast, BPR+ introduces an additional step of SVD decomposition on $\boldsymbol{E}$, producing three matrices: $\boldsymbol{U} \in \mathbb{R}^{(m+n) \times r}$, $\boldsymbol{\Sigma} \in \mathbb{R}^{r \times r}$, and $\boldsymbol{V} \in \mathbb{R}^{r \times N_e}$, where $r$ is the rank of $\boldsymbol{E}$ satisfying $r < \min(m+n, N_e)$. Therefore, the space complexity for computing the TopoLa distance is $O((m+n)r + r^2)$. Since $r$ is typically smaller than $N_e$, the overall space cost of BPR+ remains manageable and, in some cases, even lower than that of directly storing the full matrix $\boldsymbol{E}$.

To provide a concrete example:

In our experiments with LightGCN, each batch typically contains $m = 1500$ users and $n = 3000$ items, with embedding size $N_e = 64$. The SVD rank $r$ is also set to $64$ for simplicity.

• The space cost of BPR is:
  $(m+n) \times N_e = 4500 \times 64 = 288000$

• The space cost of BPR+ is:
  $(m+n) \times r + r^2 = 4500 \times 64 + 64 \times 64 = 292096$

Thus, BPR+ introduces only an additional 4,096 units of memory, corresponding to a 1.4% increase in space complexity compared to BPR.

Considering the performance improvements gained through TopoLa and the small overhead incurred, we believe this trade-off is acceptable and practical.