How do co-clicking patterns in bipartite graphs capture product substitutes from noisy behavior?
This explores how recommendation systems infer which products substitute for each other by reading the structure of who-clicked-what graphs — and why structural patterns survive the noise that single clicks don't.
This explores how recommendation systems infer which products substitute for each other by reading the structure of co-click graphs, and why that structure is more trustworthy than any individual click. The cleanest answer in the corpus comes from Taobao's Swing algorithm Can graph structure patterns outperform direct edge signals in noisy data?. A bipartite graph here just means two kinds of nodes — users and items — with an edge every time a user clicks an item. A single shared click between two products is weak evidence they're substitutes; people click for all sorts of accidental reasons. Swing's move is to stop trusting edges and start trusting small loops: when *multiple independent users* each click the *same pair* of items, that quasi-local pattern is hard to fake. Noise rarely conspires to line up the same way across many people, so the structure itself acts as a noise filter. That's the core mechanism — substitution isn't read off one signal, it's read off the coincidence of many.
Why noise is the real enemy here becomes vivid when you look at where it concentrates. Monolith's work on embedding tables Why do hash collisions hurt recommendation models so much? shows click data is power-law distributed — a handful of users and items account for most of the traffic — so errors and collisions pile up exactly on the entities you most need to get right. A method that leans on raw edge counts inherits that lopsidedness; a method that demands structural agreement is partly insulated from it. The two papers are really two halves of the same insight: behavioral data is skewed and dirty, so robustness has to come from how you read the graph, not from cleaning every click.
There's also a quieter point about what 'capturing substitutes' even means. Co-clicking tells you items are *interchangeable* in attention, but it can't tell you *why* — same price band, same use case, same brand? Knowledge Graph Attention Networks Can graphs unify collaborative filtering and side information? address the gap from the other direction: they fuse the user-item click graph with an item attribute graph, so similarity is justified by both behavior and shared properties, and high-order connections (friends-of-friends-of-items) surface relationships no single click reveals. Where Swing extracts signal from behavioral structure alone, KGAT argues that behavior plus side information catches substitutes that pure co-click would miss.
Finally, how you *model* clicks shapes what you can learn from them. The multinomial-likelihood result Why does multinomial likelihood work better for click prediction? shows that treating clicks as items competing for a fixed budget of attention — rather than as independent yes/no events — aligns training with ranking, because a click on one product is implicitly a non-click on its alternatives. That competitive framing is conceptually close to substitution itself: substitutes are the things that would have won the click instead. So the thread running across the corpus is that capturing substitutes from noisy behavior is less about better data and more about the right unit of evidence — loops over edges, structure over counts, competition over isolated events.
Sources 4 notes
Taobao's Swing algorithm constructs more robust product substitute graphs by exploiting quasi-local bipartite patterns rather than single edges. Structural signals are inherently noise-resistant because they require multiple independent noisy edges to coincidentally align, which rarely happens by chance.
Monolith's empirical work shows that real recommendation systems have power-law distributed frequencies, causing collisions to accumulate precisely on the entities models need most accurate. Fixed-size hashed tables worsen this over time as new IDs arrive.
KGAT merges user-item interaction graphs with item knowledge graphs into a Collaborative Knowledge Graph, using attention-based propagation to capture both user-similarity and attribute-similarity signals simultaneously—including high-order connections that standard supervised learning methods miss.
Multinomial likelihood better models click data because it forces items to compete for a fixed probability budget, implicitly optimizing for top-N ranking. Gaussian and logistic likelihoods allow high probability across many items simultaneously, misaligning training with ranking objectives.