How Does Topology Bias Distort Message Passing in Graph Recommender? A Dirichlet Energy Perspective

W1: "I think the title of the paper should accurately reflect the contributions ..."

A1: Thanks for raising this point. We agree that the scope of our paper is focused on graph-based recommender systems (RS) and this research focus could be better reflected in the title. Since the LightGCN-style architecture is widely adopted by graph-based RS and state-of-the-art models, we focus primarily on presenting the bias issue presented in such models in empirical results. However, our theoretical framework and the induced method can be applied to general graph-based models. We are willing to modify our title to "How Does Topology Bias Distort Message Passing in Graph Recommenders? A Dirichlet Energy Perspective".

W2: "The idea that message passing (MP) is inherently minimizing Dirichlet energy is not a new insight ..."

A2: First, we want to clarify the theoretical differences of our paper with existing oversmoothing research papers. Dirichlet energy has long been used to study the oversmoothing problem in graph representation learning. while our paper shares the definition of aligning Dirichlet energy optimization with graph message passing, we present completely distinct theoretical analysis and methodology in our paper. Existing oversmoothing papers have established that the Dirichlet energy is exponentially minimized over the stacking of message passing layers and eventually result in the difference of node representations vanishing. On the contrary, our theoretical results show that the norm updates of node embeddings not only relate to their degrees (Corollary 3.1) but also are bounded by their Dirichlet energy (Lemma 3.2). Moreover, we extend the Dirchlet energy analysis to higher order simplicial complexes (SC) and present how message on SC can reduce the norm concentration phenomenon under such theoretical framework. We believe that our theoretical contributions are distinct from existing oversmoothing papers in both problem studied and the resulting methodology, showing originality and novelty in the study of topology bias. Nevertheless, we agree that clearly positioning our work in relation to existing studies on Dirichlet energy is important. We will add these details in the related work section.

W3: "Although the norm concentration analysis is interesting, the idea that higher degree nodes receive larger message ..."

A3: We partially agree that the degree bias problem shares some similar aspects to our paper, but there are still some key differences we want to clarify. The degree bias often describes how nodes with high degrees in graph affect the classification results of other nodes, under the assumption of homophily, i.e., nodes closely connected tend to share the same class label. The debiasing process mainly focuses on improving the label accuracy for low degree nodes. However, we study how the topology bias in a graph distorts the message passing dynamics in graph-based recommenders, leading to popular items being dispropotionately recommended to users. The recommendation process can be regarded as a link prediction task in a heterogeneous user-item bipartite graph. We want our debiasing method to help niche items (low degree nodes) have an appropriate portion in final recommendation lists and thus provide results fit users' real interests. Moreover, the papers studying degree bias often deal with the node classification task in a semi-supervised manner, where labels are only available for a small subset of nodes. In contrast, nodes in graph-based RS are supervised by all their interactions, providing a supervision signal even for low-degree nodes. In summary, while they are both bias issues originated from unbalanced node degree distribution, they have distinct tasks, debiasing goals, bias formation mechanism and learning dynamics. Therefore, we believe our contributions are distinct and do not overlap with this line of research on degree bias

W4: "The resolution proposed to mitigate this topology bias is test-time simplicial complex ..."

A4: Regarding the reviewer's concern about complexity, we want to further stress that our proposed TSP is designed as a test-time module that operates on a pre-trained model. The computational overhead of our TSP method, including the Hodge Laplacian calculation, does not affect the training efficiency of the underlying recommendation model. This one-time computation per test phase is a key advantage of our approach. As for the degree bias solutions, specially [1-6] mentioned by reviewer, as in our answers to Weakness 3, we want to kindly remind the reviewer that these methods all focus on node classification tasks. Due to distinct task, debiasing goals, learning dynamics and bias formation mechanism, we believe they are not directly applicable to topology bias in RS and thus can not serve as baselines for comparison with our proposed method.

W5: "L26-27 maybe explain in 1-2 lines what exactly is Matthew effect?"

A5: The Matthew effect describes the rich-get-richer phenomenon and is widely used in recommendation fairness works to represent the bias reinforcement loop. More specifically in topology bias, the popular items tend to have larger embeddings norms (Corollary 3.1) and updates (Lemma 3.2), which results in potentially higher prediction scores. This leads to more frequent recommendations, making these items even more popular. In this reinforcement loop, popular items can eventually dominate the recommendation lists and become disproportionately recommended to all users.

W6: "The computational complexity for lifting the graphs into simplicial complex is missing."

A6: The process of lifting a graph to a k-simplicial complex (e.g., finding all 3-cliques for 2-simplices) is a one-time, offline preprocessing step performed at test time. We apply the widely used clique mining Bron–Kerbosch [7]. For a graph with $n$ vertices, the worst-case complexity is $O(3^\wedge{(n/3)})$ [8, 9].

References

[1] On Generalized Degree Fairness in Graph Neural Networks. Liu et al, AAAI 2023.

[2] GRAPHPATCHER: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation. Ju et al, NeurIPS 2023.

[3] Tail-GNN: Tail-Node Graph Neural Networks. Liu et al, KDD, 2021.

[4] Investigating and Mitigating Degree-Related Biases in Graph Convolutional Networks. Tang et al. CIKM 2020.

[5] Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks. Subramonian et al, 2024.

[6] Degree-based stratification of nodes in Graph Neural Networks. Ali et al, ACML 2023.

[7] Algorithm 457: finding all cliques of an undirected graph. Bron, C. et al, Communications of the ACM 1973.

[8] On cliques in graphs. Moon J. W. et al, Israel Journal of 1965.

[9] The worst-case time complexity for generating all maximal cliques and computational experiments. Tomita Etsuji et al, Theoretical Computer Science 2006.

W1: "The authors might have considered to include a further baseline (RP3Beta ..." Q1: "Could the authors provide additional results when running the model RP3beta ..."

A1: We expand our experiments by adding the new baseline RP3beta compared with our method. The results of tail performance are listed below:

These additional result further present the strong performance of our proposed TSP method.

W2: "In relation to the above, I think the authors might also consider to measure other recommendation measures ..." Q2: "How are the recommendation performance when considering additional standard bias and fairness metrics ..."

A2: Thank you for your suggestions. We agree that the metrics mentioned can further present the debiasing ability of our proposed method. Due to limited rebuttal time we only evaluate methods on LightGCN backbone. We show these additional results of EFD (with exponential discount $0.85^{k–1}$) and APLT of below:

The constant better performance of TSP in fairness metrics further prove its ability to mitigate the topology bias and produce balanced recommendation.

Q3: "Do the authors have any intuition on how their theoretical analysis and subsequent ..."

A3: This is a very insightful question. In our current framework, we treat users and items symmetrically when constructing the semantic graph. However, the framework is flexible enough to handle them asymmetrically. For instance, one could use different similarity thresholds ($\theta$) for user-user and item-item pairs to reflect the different semantics and densities of these relationships. It would also be possible to construct simplices only on the item side to specifically focus on diversifying item representations. We believe this is a fascinating and promising direction for future research.

W1: "Graph-based (or message passing-based) recommender methods are ..."

A1: We agree that graph recommenders are often considered less efficient when trained on large graphs. However, our proposed TSP is designed as a test-time module that operates on a pre-trained model. The computational overhead of our TSP method, including the Hodge Laplacian calculation, does not affect the training efficiency of the underlying recommendation model. This one-time computation during test phase is a key advantage of our approach.

Furthermore, the additional computational overhead introduced by our method is quite small. We have included a scalability analysis in Section 5.4 of our original paper, which demonstrates that our proposed TSP adds only a limited and acceptable overhead to the backbone models during inference time across datasets of varying sizes, as shown in Table 3.

W2: "Additional experiments on larger scale datasets would be appreciated."

A2: We thank the reviewer for this suggestion and agree that scalability is a crucial aspect of graph-based models. While the definition of a "large-scale" dataset can vary, we have selected datasets that are considered substantial within the context of recent research. For example, the work cited by the reviewer [1] evaluates GCNs on datasets with up to around 100k nodes. Our experiments include datasets of comparable or greater scale, ranging from Gowalla (~14k nodes, ~100k interactions) to Globo (~160k nodes, ~2.5M interactions). We believe these results can already demonstrate our model's scalability across different dataset scales. Nevertheless, we are committed to providing a thorough empirical analysis. To best address the reviewer's concern, we would be grateful for any clarification on the specific scale or type of dataset that would be considered sufficient for a more comprehensive evaluation.

Q: "The term 'semantic graph' is quite confusing. IIUC, the graph-based ..."

A3: We use the term "semantic graph" to emphasize that its structure is derived from the semantic similarity of node embeddings, which capture latent relationships (e.g., user preferences, item attributes) learned by the GNN, as opposed to the raw, explicit user-item interaction topology. This new topology is more reflective of the underlying semantic meaning of the nodes. We agree that this process can be considered as a form of graph augmentation or structure learning. However, our goal is not merely to augment the graph but to construct a new topology specifically guided by our Dirichlet energy analysis to mitigate topology bias.

References

[1] UltraGCN: Ultra Simplification of Graph Convolutional Networks for Recommendation, CIKM 2021

Dear Reviewer HkJG, It would be useful if you could respond to the rebuttal of the authors to indicate if your concerns are satisfactorily answered.

sincerely AC