The Edge Spectrum of Choice-Derived Item Graphs: Strong and Weak Edges Encode Different Relations in Collaborative Filtering

• URL: http://arxiv.org/abs/2608.29578v1
• Date: Sun, 30 Aug 2026 05:53:08 GMT
• Title: The Edge Spectrum of Choice-Derived Item Graphs: Strong and Weak Edges Encode Different Relations in Collaborative Filtering
• Abstract summary: We show that strong and weak edges encode qualitatively different relations.<n>We formalize this as a sign mismatch between the smoothing operator and the ranking gradient.<n>This diagnosis explains three empirical observations on MIND and EB-NeRD.
• Score: 38.85665556927363
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph collaborative filtering relies on item--item graphs whose edges are used for positive smoothing, under the implicit assumption that stronger edges encode more of the same relation as weaker ones. We show that this assumption fails for a practically important class of graphs: those whose edge weights come from a choice model. On such graphs, strong and weak edges encode qualitatively different relations, which we call an edge spectrum. Specifically, strong edges concentrate on the in-slate competitors of clicked items, exactly the pairs that the within-slate ranking gradient pushes apart, while weak edges do not. We formalize this as a sign mismatch between the smoothing operator and the ranking gradient, and prove that co-click graphs cannot exhibit the same misalignment by construction. This diagnosis explains three empirical observations on MIND and EB-NeRD: (i) drop-in choice-derived operators do not beat co-click, despite indexing structurally distinct neighborhoods; (ii) uniform scalar fixes (sign flip, in-slate margin loss) fail predictably, because the misalignment lives in the graph, not in the loss; (iii) only edge-magnitude-aware operators, with the regime boundary located by the diagnosis rather than by tuning, recover the predicted ordering. The neighbor cutoff $k$ is therefore a semantic switch, not a sparsification hyperparameter. Our claim concerns which interventions fail or succeed and why, not absolute headline gains, which the diagnosis itself predicts to be small under the attenuated propagation channel we observe. We turn the diagnosis into a reusable protocol practitioners can run before deploying any choice-derived item-side operator. Code: https://github.com/kyomusso/Edge-Spectrum-in-CF.

Related papers

• SEA: Spectral Edge Attacks on Graph Neural Networks [1.066048003460524]
  We propose a new family of adversarial attacks that leverage spectral robustness evaluation to guide perturbations.<n>We introduce two complementary attack variants: (i) a Spade-guided deletion attack that removes the most spectrally robust edges, and (ii) a Spade-guided addition attack that inserts edges between nodes that are maximally incompatible in the fragile spectral space.
  arXiv  Detail & Related papers  (2025-11-30T01:40:15Z)
• Adversarial Signed Graph Learning with Differential Privacy [13.459205297125534]
  Signed graphs with positive and negative edges can model complex relationships in social networks.<n>Training on sensitive signed graphs raises significant privacy concerns.<n>We present ASGL, a privacy-preserving adversarial signed graph learning method.
  arXiv  Detail & Related papers  (2025-11-29T04:02:48Z)
• A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNs [54.62268052283014]
  We present a unified theoretical perspective based on the framework of signed graphs.<n>We show that many existing strategies implicitly introduce negative edges that alter message-passing to resist oversmoothing.<n>We propose Structural Balanced Propagation (SBP), a plug-and-play method that assigns signed edges based on either labels or feature similarity.
  arXiv  Detail & Related papers  (2025-02-17T03:25:36Z)
• Why Does Dropping Edges Usually Outperform Adding Edges in Graph Contrastive Learning? [54.44813218411879]
  We introduce a new metric, namely Error Passing Rate (EPR), to quantify how a graph fits the network.<n>Inspired by the theoretical conclusions and the idea of positive-incentive noise, we propose a novel GCL algorithm, Error-PAssing-based Graph Contrastive Learning (EPAGCL)<n>We generate views by adding and dropping edges based on the weights derived from EPR.
  arXiv  Detail & Related papers  (2024-12-11T06:31:06Z)
• Countering adversarial perturbations in graphs using error correcting codes [7.553245365626645]
  adversarial perturbations occur during the transmission of the graph between a sender and a receiver. This study explores a repetition coding scheme with sender-assigned noise and majority voting on the receiver's end to rectify the graph's structure.
  arXiv  Detail & Related papers  (2024-06-20T12:14:01Z)
• ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks [53.41164429486268]
  Graph Neural Networks (GNNs) have exhibited the powerful ability to gather graph-structured information from neighborhood nodes. The performance of GNNs is limited by poor generalization and fragile robustness caused by noisy and redundant graph data. We propose a novel adversarial edge-dropping method (ADEdgeDrop) that leverages an adversarial edge predictor guiding the removal of edges.
  arXiv  Detail & Related papers  (2024-03-14T08:31:39Z)
• Are Gradients on Graph Structure Reliable in Gray-box Attacks? [56.346504691615934]
  Previous gray-box attackers employ gradients from the surrogate model to locate the vulnerable edges to perturb the graph structure. In this paper, we discuss and analyze the errors caused by the unreliability of the structural gradients. We propose a novel attack model with methods to reduce the errors inside the structural gradients.
  arXiv  Detail & Related papers  (2022-08-07T06:43:32Z)
• Reinforced Causal Explainer for Graph Neural Networks [112.57265240212001]
  Explainability is crucial for probing graph neural networks (GNNs) We propose a reinforcement learning agent, Reinforced Causal Explainer (RC-Explainer) RC-Explainer generates faithful and concise explanations, and has a better power to unseen graphs.
  arXiv  Detail & Related papers  (2022-04-23T09:13:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.