The Edge Spectrum of Choice-Derived Item Graphs: Strong and Weak Edges Encode Different Relations in Collaborative Filtering
Information Retrieval
Summary
The authors found that in item--item graphs used for recommendation, strong and weak connections represent very different types of relations instead of just stronger or weaker versions of the same thing. This difference, which they call an "edge spectrum," causes common smoothing techniques to misalign with the actual ranking goals. They show why standard fixes don't work and propose methods that consider edge strength properly to improve performance. Their work provides a diagnostic tool for developers to check if choice-based graph operators will work well before using them.
Authors
Keigo Sakurai, Takahiro Ogawa, Miki Haseyama
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.