Graph Neural Networks for Cross-Sell: Modeling the Product Co-Purchase Network at Scale

TL;DR: Association rules and collaborative filtering miss transitive product relationships -- if A co-occurs with B and B with C, they assign zero confidence to A-C even when they share a dense activity cluster. Graph neural networks propagate information across the co-purchase network to discover these multi-hop complementary relationships, capturing the long-tail cross-sell opportunities where margins live and pairwise methods are structurally blind.

Cross-Sell Is a Graph Problem

A customer buys a DSLR camera. Within the next 30 days, they purchase a 64GB SD card, a camera bag, a lens cleaning kit, and a tripod. None of these products share a category. None share a brand. A content-based filtering system, comparing product attributes, sees no connection between a Canon camera body and a Manfrotto tripod. A collaborative filtering model trained on user-item interactions might surface the tripod if enough past users followed the same trajectory. Transformer-based product embeddings improve on this by capturing session-level context, but they still model sequential rather than structural relationships. But neither approach captures the structural fact that these products inhabit a dense cluster in the co-purchase network — a cluster that reveals an underlying activity (photography) which organizes purchasing behavior across otherwise unrelated catalog segments.

This structural property is what makes cross-sell a graph problem rather than a matrix factorization problem or a frequency counting problem.

The standard cross-sell toolkit in e-commerce — association rules, collaborative filtering, content-based similarity — treats each product recommendation as either a pairwise co-occurrence statistic or a row in a latent factor matrix. These methods work. They have worked for decades. Amazon's "frequently bought together" feature, built on item-to-item collaborative filtering published by Linden, Smith, and York (2003), remains one of the highest-revenue recommendation surfaces in e-commerce.

But they miss transitive structure. If product A is frequently purchased with product B, and product B is frequently purchased with product C, but A and C have never appeared in the same basket, association rules assign zero confidence to the A-C pair. Collaborative filtering might surface C for buyers of A if the latent factors align, but this is incidental rather than structural. A graph neural network, operating on the co-purchase network, propagates information along the A-B-C path and learns that A and C are two hops apart in a dense subgraph — structurally similar even without direct co-occurrence.

This distinction is not academic. Transitive cross-sell captures the long-tail of complementary relationships that pairwise methods miss entirely. And the long tail is where margins live. The camera-to-tripod recommendation is obvious. The camera-to-specific-type-of-backpack recommendation — the one that requires understanding the activity graph, not just the purchase history — is where graph methods earn their computational overhead. These transitive relationships also power search ranking, where understanding product complementarity enables more effective cross-sell and upsell surfaces within search results.

The Product Co-Purchase Network

The co-purchase network is a graph G = (V, E) where nodes V represent products and edges E represent co-purchase relationships. An edge between products i and j exists if they were purchased together within a defined session window — typically the same order, or orders placed by the same user within 7-30 days. Edge weights encode co-purchase frequency, normalized by the individual purchase frequencies of each product (to avoid popularity bias where bestsellers connect to everything).

The structure of this graph is not random. It exhibits properties that are both predictable from network theory and operationally significant for recommendation quality.

Power-law degree distribution. A small number of products (batteries, phone cases, gift cards) connect to thousands of others. The vast majority connect to fewer than ten. This means the graph is sparse overall but contains dense local clusters. Any GNN architecture must handle this skew — naive message passing from high-degree hub nodes drowns the signal from structurally informative low-degree connections.

Community structure. Products cluster into communities that correspond roughly to shopping occasions or activity contexts. A home renovation cluster contains paint, brushes, tape, drop cloths, and primer — products spanning multiple categories but united by a single project. A baby shower cluster contains onesies, diaper bags, swaddles, and pacifiers. These communities are discoverable by standard graph partitioning algorithms, but GNNs learn them implicitly through the message-passing process.

Bipartite foundation. The raw data is not a product-product graph. It is a bipartite graph connecting users to products through purchase events. The product co-purchase graph is a projection of this bipartite structure onto the product node set: two products are connected if at least one user purchased both. This projection loses information — specifically, it loses which users created which connections. Heterogeneous graph approaches, discussed below, preserve this information by operating directly on the bipartite structure with additional node types.

The clustering coefficient of 0.34 is the statistic that matters most for cross-sell. It means that if product A co-occurs with products B and C, there is a 34% probability that B and C also co-occur. This transitivity is the structural signal that GNNs exploit. In a random graph with the same degree distribution, the expected clustering coefficient would be below 0.01. The observed value is 30x higher — evidence that co-purchase behavior is organized by latent structures (activities, occasions, projects) that connect products beyond pairwise frequency.

GNN Fundamentals: Message Passing and Node Aggregation

A graph neural network operates through a conceptually straightforward mechanism: iterative message passing. Each node in the graph maintains a feature vector — an embedding that encodes what the network knows about that product. At each layer of the GNN, every node collects messages from its neighbors, aggregates them, and updates its own embedding based on the aggregated information and its previous state.

Formally, the update rule for node v at layer k is:

Where $\mathbf{h}_v^{(k)}$ is the embedding of node v at layer k, $\mathcal{N}(v)$ is the set of neighbors of v, AGGREGATE is a permutation-invariant function (sum, mean, or max) that combines neighbor embeddings, and UPDATE is a learned transformation (typically a neural network layer followed by a nonlinearity).

For mean aggregation specifically, the message-passing step computes:

After K layers of message passing, the embedding of each node encodes information from its K-hop neighborhood in the graph. A 2-layer GNN for product v knows about v's direct co-purchases (1-hop) and the co-purchases of those co-purchases (2-hop). A 3-layer GNN extends to 3-hop neighborhoods. In practice, 2-3 layers suffice for most product graphs. Beyond that, the over-smoothing problem emerges: node embeddings converge toward a global mean, losing the local structure that makes recommendations useful.

The initial node features h_v^(0) encode product attributes — category, price bucket, brand, textual description embeddings, image embeddings, historical sales velocity. These are the starting point. The message-passing layers then enrich these features with structural context from the graph. After training, two products with similar initial features but different graph neighborhoods will have different final embeddings. Two products with dissimilar initial features but similar graph neighborhoods will have convergent final embeddings. This is the core value proposition: the graph structure provides a signal that product attributes alone cannot.

The loss function for training a cross-sell GNN is typically a link prediction objective: given the current graph, predict which edges exist (positive examples) versus which do not (negative examples). The model learns embeddings such that products connected by co-purchase edges have high similarity (dot product, cosine similarity) in the embedding space, while disconnected products have low similarity. The negative sampling strategy matters enormously — random negatives are too easy, and the model learns nothing useful. Hard negatives (products in the same category but rarely co-purchased) force the model to learn fine-grained distinctions.

GraphSAGE and GAT for Product Graphs

Two GNN architectures dominate production cross-sell systems: GraphSAGE (Hamilton, Ying, and Leskovec, 2017) and Graph Attention Networks (Velickovic et al., 2018). Each addresses a different structural challenge in product graphs.

GraphSAGE: Inductive Learning Through Neighbor Sampling

GraphSAGE was designed for large, evolving graphs — precisely the setting of an e-commerce product catalog. Its key innovation is neighbor sampling: instead of aggregating messages from all neighbors of a node (which is computationally prohibitive for hub products with thousands of connections), GraphSAGE uniformly samples a fixed number of neighbors at each hop. A typical configuration samples 25 neighbors at the first hop and 10 at the second, yielding a computational graph of at most 250 nodes per target — tractable even for graphs with millions of products.

The second innovation is inductive capability. Traditional GNN approaches (Kipf and Welling, 2017) are transductive — they learn embeddings for a fixed set of nodes and cannot generalize to new ones without retraining. GraphSAGE learns the aggregation function itself, not the embeddings. When a new product enters the catalog, the trained aggregation function produces an embedding from the new product's features and whatever neighbors it has acquired. No retraining required.

This property is operationally critical. E-commerce catalogs are not static. New products arrive daily — sometimes thousands per day on marketplace platforms. A transductive GNN requires retraining or fine-tuning with each catalog update. GraphSAGE produces embeddings for new products at inference time, using only the trained aggregator weights and the local graph neighborhood. This inductive capability directly addresses the cold-start problem — a new product with even a few co-purchase edges can be embedded meaningfully through its graph context.

The GraphSAGE update rule at layer $k$ is:

where $\mathcal{S}(v)$ is the sampled neighbor set and $\sigma$ is a nonlinearity (typically ReLU). The CONCAT operation distinguishes GraphSAGE from vanilla GCNs -- it preserves the target node's own information alongside the aggregated neighborhood signal.

Graph Attention Networks: Learning Edge Importance

GAT introduces attention mechanisms to the message-passing framework. Instead of weighting all neighbors equally (mean aggregation) or treating them as interchangeable (sum aggregation), GAT learns attention weights that determine how much each neighbor contributes to the target node's updated embedding.

For product graphs, this is directly interpretable. When computing the embedding for a DSLR camera, a GAT might assign high attention to the co-purchased lens (strong complementary signal) and low attention to the co-purchased gift wrap (weak, occasion-driven noise). The attention weights are learned end-to-end from the data, not hand-engineered. Combined with uplift modeling for promotions, these attention-weighted cross-sell signals can identify which complementary products to promote to specific customer segments for maximum incremental revenue.

The GAT attention coefficient between nodes $v$ and $u$ is computed as:

where $\mathbf{a}$ is a learned attention vector and $\|$ denotes concatenation. Multi-head attention runs $K$ independent attention mechanisms and concatenates (or averages) the results.

Here is a minimal PyTorch Geometric implementation for a product co-purchase graph using GraphSAGE:

import torch
from torch_geometric.nn import SAGEConv
from torch_geometric.data import Data
 
class ProductGraphSAGE(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels):
        super().__init__()
        self.conv1 = SAGEConv(in_channels, hidden_channels)
        self.conv2 = SAGEConv(hidden_channels, out_channels)
 
    def forward(self, x, edge_index):
        # Layer 1: aggregate 1-hop neighborhood
        x = self.conv1(x, edge_index).relu()
        x = torch.nn.functional.dropout(x, p=0.3, training=self.training)
        # Layer 2: aggregate 2-hop neighborhood
        x = self.conv2(x, edge_index)
        return x
 
# Build co-purchase graph: 50K products, 128-dim features
num_products = 50_000
x = torch.randn(num_products, 128)  # product feature vectors
# edge_index: [2, num_edges] tensor of co-purchase pairs
edge_index = torch.load("copurchase_edges.pt")
 
data = Data(x=x, edge_index=edge_index)
model = ProductGraphSAGE(in_channels=128, hidden_channels=256, out_channels=64)
embeddings = model(data.x, data.edge_index)
 
# Cross-sell score: cosine similarity between product embeddings
from torch.nn.functional import cosine_similarity
query_idx, candidate_idx = 0, 1
score = cosine_similarity(
    embeddings[query_idx].unsqueeze(0),
    embeddings[candidate_idx].unsqueeze(0)
)

In practice, the choice between GraphSAGE and GAT is often resolved by scale. Systems with fewer than 10 million product nodes can afford multi-head GAT with full neighbor attention. Systems with tens of millions of nodes — the Amazon, Walmart, and Alibaba scale — gravitate toward GraphSAGE with neighbor sampling, or hybrid architectures that use GAT attention within a sampled neighborhood.

Heterogeneous Graphs: Products, Users, Categories, Brands

The homogeneous product co-purchase graph is a useful simplification. But it is a simplification. Real purchase behavior is organized by multiple entity types — products, users, categories, brands, occasions, price tiers — each carrying distinct information about why co-purchases occur. Heterogeneous graph neural networks (HGNNs) operate on graphs with multiple node types and multiple edge types, preserving this richer structure.

A heterogeneous product graph might include:

• Product nodes — features: category, price, brand, text embedding, image embedding
• User nodes — features: purchase frequency, average basket size, category affinities, recency
• Category nodes — features: seasonality index, average price, catalog depth
• Brand nodes — features: market share, price tier, customer loyalty index
• Occasion nodes — features: temporal pattern, category mix, average basket value

Edge types then encode distinct relationships:

• User-purchases-Product (weighted by recency and frequency)
• Product-belongs-to-Category
• Product-manufactured-by-Brand
• Product-co-purchased-with-Product (within-session)
• User-browses-Product (implicit interest signal)
• Product-associated-with-Occasion (inferred from temporal patterns)

The message-passing mechanism in an HGNN is type-aware. Messages passed along user-purchases-product edges are transformed by a different learned weight matrix than messages along product-belongs-to-category edges. This allows the model to learn that brand affinity propagates differently than category co-occurrence, which propagates differently than user behavioral similarity.

The progression is clear. Each additional source of structural information improves recommendation accuracy. The jump from homogeneous to full heterogeneous is 53% in relative hit rate. The further addition of temporal edge information — encoding not just that products co-occur but when in the purchase sequence they tend to co-occur — adds another 8%.

The practical cost is complexity. Heterogeneous GNNs require type-specific weight matrices, edge-type-aware sampling strategies, and careful handling of node feature spaces that differ across types. Training time increases roughly linearly with the number of edge types. For teams without dedicated graph ML infrastructure, starting with a homogeneous product graph and adding heterogeneity incrementally is the defensible path.

Training GNNs on Purchase Sequences

The co-purchase graph represents a static snapshot: products that were bought together during some historical window. But purchase behavior is sequential. A customer buys a tent, then a sleeping bag two weeks later, then hiking boots a month after that. The order matters. A GNN trained only on the unordered co-purchase graph treats the tent-to-boots and boots-to-tent recommendations as equivalent. They are not. The tent buyer is likely to need boots. The boot buyer may have no interest in tents.

Incorporating temporal direction into GNN training requires modifying the graph construction and the training objective.

Directed edges. Instead of an undirected co-purchase graph, construct a directed graph where edge (i, j) exists if product j was purchased after product i by the same user within the session window. Edge weight reflects the frequency of this directional transition. The GNN message-passing mechanism then distinguishes between "products purchased before me" (predecessors) and "products purchased after me" (successors). Cross-sell recommendations are drawn from the successor distribution of the query product's embedding.

Sequential loss functions. Instead of symmetric link prediction (does edge i-j exist?), the training objective becomes next-item prediction: given the products purchased so far in a session, predict the next product. This can be framed as a ranking loss where the model scores the true next purchase higher than sampled negatives. The GNN produces an embedding for each product, and the sequential model operates on the ordered sequence of these embeddings.

Temporal edge decay. Co-purchases from six months ago are less informative than co-purchases from last week. Applying exponential decay to edge weights based on recency ensures the graph reflects current purchasing patterns rather than historical artifacts. The decay rate is a tunable hyperparameter — faster decay tracks trends more responsively but sacrifices statistical stability from older data.

The combination of directed edges, sequential objectives, and temporal weighting transforms the static co-purchase graph into a dynamic model of purchasing trajectories. The resulting embeddings encode not just "what goes with what" but "what comes next after what" — the operationally relevant question for cross-sell.

The Graph Cross-Sell Score

Given trained product embeddings from a GNN, the cross-sell score between a query product q and a candidate product c is the similarity between their embeddings in the learned space:

CrossSellScore(q, c) = sim(h_q, h_c) * P(complement | q, c) * recency_weight(q, c)

The first term, embedding similarity, captures structural proximity in the co-purchase graph. The second term, complement probability, is a learned classifier that distinguishes complements from substitutes (addressed in detail below). The third term, recency weight, ensures that seasonally relevant and trend-aware recommendations are surfaced.

This composite score can be decomposed for interpretability. A merchandiser reviewing the top cross-sell recommendations for a product can see: "This recommendation scores 0.87. The graph structural score is 0.92 (strong co-purchase neighborhood overlap). The complement probability is 0.94 (high confidence this is a complement, not a substitute). The recency weight is 0.98 (this co-purchase pattern is current)."

The Canon EOS R6 — a competing camera body — has high graph similarity to the Nikon D7500 because they occupy similar positions in the co-purchase network (surrounded by the same accessories). But the complement probability classifier assigns 0.08, correctly identifying it as a substitute. The composite score drops to 0.07, and the product is filtered from cross-sell results. Without the complement classifier, the highest-scoring cross-sell recommendations for cameras would be other cameras — useful for nobody.

GNN vs. Association Rules vs. Collaborative Filtering

The question is not whether GNNs are theoretically superior. The question is whether the improvement justifies the engineering and computational cost. A disciplined comparison requires holding the evaluation protocol constant and measuring on the same holdout data.

The following comparison uses a holdout set of 500,000 baskets from a mid-size e-commerce retailer (12 million annual transactions, 480,000 active SKUs). For each basket, one product is held out, and each method must rank the held-out product among 1,000 random negatives plus the true positive.

Three patterns emerge from this comparison.

First, the GNN methods outperform all baselines on hit rate and MRR. The GAT with temporal edges achieves 163% higher hit rate than association rules and 55% higher than matrix factorization. This gap is statistically significant and operationally meaningful — it translates directly to higher cross-sell conversion rates.

Second, catalog coverage — the fraction of products that appear in at least one recommendation list — tells a more nuanced story. Association rules cover only 12% of the catalog because they require minimum support thresholds that most long-tail products fail to meet. GNN methods cover 51-64% because the message-passing mechanism propagates signal to products with sparse purchase histories through their graph neighbors. A product purchased only 15 times can inherit cross-sell signals from its well-purchased neighbors. This long-tail coverage is where the revenue opportunity concentrates.

Third, the progression from simple to complex methods is monotonic but not linear. The jump from association rules to collaborative filtering is large. The jump from collaborative filtering to a basic GNN is moderate. The jump from a basic GNN to a heterogeneous temporal GNN is smaller still. Each increment of complexity buys a smaller increment of performance. The right choice depends on engineering capacity and catalog scale.

Complementary vs. Substitute: The Classification Problem

The co-purchase graph conflates two fundamentally different relationships. A customer buys a phone case with a phone (complement). A customer buys an iPhone and returns the Samsung they were considering (substitute exploration captured as co-browse). Both create edges in the graph. But the optimal cross-sell action for each is entirely different: recommend complements, suppress substitutes.

Distinguishing complements from substitutes is a classification problem on edges. Given two products connected in the co-purchase graph, predict whether the relationship is complementary (the customer needs both) or substitutive (the customer is choosing between them).

Features that discriminate between these relationship types:

• Category overlap. Products in the same leaf category are more likely substitutes. Products in different categories are more likely complements. A camera and a lens are in different categories (complement). Two cameras are in the same category (substitute).
• Price similarity. Substitutes tend to have similar price points. Complements span a wider price range (a $1,200 camera and a $25 SD card).
• Brand relationship. Same-brand, same-category products are almost always substitutes. Cross-brand accessories are almost always complements.
• Temporal pattern. Complements are purchased in quick succession (same session or within days). Substitutes show a browse-compare-decide-return pattern with longer gaps and more back-and-forth navigation.
• Return co-occurrence. If product B is frequently returned within days of purchasing product A, the relationship is substitutive — the customer tried both and kept one.

A logistic regression on these features achieves approximately 88% accuracy on labeled complement/substitute pairs. A gradient-boosted model reaches 93%. Embedding the classification directly into the GNN — training a multi-task objective that simultaneously predicts co-purchase links and classifies edge types — pushes accuracy to 96% because the GNN embeddings capture structural signals that feature engineering misses.

The operational consequence is significant. A cross-sell system without complement/substitute classification will recommend competing products — cameras on the camera page, running shoes on the running shoe page. This is not cross-sell. It is product comparison, and it cannibalizes margin by encouraging price-driven comparison shopping rather than basket expansion.

Handling Graph Dynamics: New Products and Seasonal Edges

A product graph is not a static artifact. It changes daily. New products enter the catalog with no purchase history and no graph connections. Existing products gain and lose edges as purchasing patterns shift. Seasonal structures emerge and dissolve: sunscreen and beach towels cluster densely in June but disconnect in November. Back-to-school supplies form a tightly connected subgraph in August that barely exists in March.

Each dynamic poses a distinct challenge for GNN-based cross-sell.

The cold-start problem. A new product has no co-purchase edges. In a graph-only model, it has no neighbors to receive messages from, and its embedding degenerates to the initial feature vector with no structural enrichment. Three mitigation strategies exist:

1. Feature-based initialization. If the GNN was trained with strong initial features (text embeddings from product descriptions, image embeddings from product photos, categorical features), the initial embedding may be sufficient for coarse cross-sell recommendations until co-purchase data accumulates.

2. Catalog-graph bridging. Connect new products to existing products through non-purchase edges: same subcategory, same brand, similar price point, similar description embedding. These "catalog edges" provide a structural neighborhood for message passing before purchase data exists. The edge weights on catalog edges should be lower than purchase-based edges, reflecting their lower confidence.

3. Inductive inference. GraphSAGE's inductive capability means that even a product with a single purchase event (and thus a single graph neighbor) can receive a structurally informed embedding through the trained aggregation function. The embedding quality improves rapidly with the first 5-10 co-purchase edges, then plateaus.

Seasonal graph dynamics. The co-purchase graph in December looks different from the graph in July. Gift-giving creates temporary edges between products that never co-occur outside the holiday season (a bestselling novel and a box of chocolates). Summer creates activity-based clusters that dissolve in winter.

The standard approach is temporal windowing: construct the graph from the most recent N months of purchase data, and reconstruct periodically. A 90-day window captures current seasonal patterns while retaining enough history for statistical stability. More sophisticated approaches maintain a base graph (computed from 12+ months of data) and overlay a seasonal delta graph (computed from the most recent 30 days), with learned weights controlling the blend.

The data reveals a steep improvement curve. A product with just 6-20 co-purchase events achieves 67% of warm-start recommendation quality. The path from cold to warm is not the cliff that many teams fear — it is a rapid ramp, with the most critical phase being the first 5-10 co-purchase events. Systems that accelerate this ramp (through promotional bundling, editorial curation, or strategic placement in recommendation slots for related products) can materially reduce the cold-start penalty.

Scalability: The PinSage Approach

The computational cost of GNN inference scales with the number of nodes, the number of edges, the number of message-passing layers, and the neighbor sampling budget. For a mid-size catalog of 500,000 products, a 2-layer GraphSAGE with 25/10 neighbor sampling produces embeddings in minutes on a single GPU. For Pinterest's graph of 3 billion pins and 18 billion edges, standard approaches fail entirely.

Ying et al. (2018) addressed this at Pinterest with PinSage, which introduced three techniques that have become standard for industrial-scale graph recommendations.

1. Importance-based neighbor sampling. Instead of uniform random sampling of neighbors, PinSage samples proportional to the frequency of random walk visits. Starting from the target node, a set of random walks explores the local graph, and the most frequently visited neighbors are selected for message passing. This concentrates computation on the structurally most informative neighbors — a form of attention without the quadratic cost of GAT.

2. Producer-consumer decoupling. PinSage separates embedding computation (producer) from recommendation serving (consumer). Embeddings are precomputed in batch for all nodes and stored in a key-value store. At serving time, the recommendation system performs a nearest-neighbor lookup in embedding space — a sub-millisecond operation using approximate nearest neighbor (ANN) indices. The GNN never runs at query time. This decoupling makes serving latency independent of graph size.

3. Curriculum training. PinSage trains with progressively harder negative examples. Early epochs use random negatives (easy to distinguish from positive co-purchases). Later epochs use hard negatives sampled from the graph neighborhood of the positive — products that are structurally close but not co-purchased. This curriculum accelerates convergence and improves the quality of fine-grained distinctions in the embedding space.

Pinterest reported a 150% improvement in engagement on related-pin recommendations compared to their previous system. The architecture handles billions of nodes with daily re-embedding, using MapReduce-style distributed computation across hundreds of machines.

The lesson for smaller teams is not to replicate PinSage. It is to recognize that the core ideas — importance sampling, precomputed embeddings with ANN serving, and curriculum training — apply at every scale. A team serving recommendations for a 500K-product catalog can implement the same architectural pattern on a single machine, achieving sub-millisecond serving latency and daily embedding refresh.

Deployment Architecture

A production GNN cross-sell system has four components: graph construction, model training, embedding storage, and recommendation serving. Each operates on a different cadence.

Graph construction runs daily or weekly. Raw purchase event data is aggregated into co-purchase edges, filtered by minimum support thresholds, weighted by recency and frequency, and stored as an adjacency list or edge list in a graph database or distributed file system. The computational cost scales linearly with the number of purchase events in the window.

Model training runs weekly or on-demand. The GNN is trained on the current graph using the link-prediction objective. Training time depends on graph size, model architecture, and hardware — from minutes for small graphs on a single GPU to hours for large graphs on a distributed cluster. Hyperparameter tuning (learning rate, embedding dimension, number of layers, neighbor sample size, negative sampling strategy) is performed on a validation set of held-out co-purchase edges.

Embedding storage is refreshed after each training run. Product embeddings are exported from the trained model and indexed in an approximate nearest neighbor (ANN) service — FAISS, ScaNN, or Milvus are common choices. The ANN index enables sub-millisecond retrieval of the K most similar products to any query product.

Recommendation serving runs at query time. When a user views a product page, the serving layer retrieves the product's embedding, queries the ANN index for the top-N nearest neighbors, filters substitutes using the complement classifier, applies business rules (in-stock, margin thresholds, suppression lists), and returns the ranked cross-sell recommendations. End-to-end latency from request to response is typically 10-50 milliseconds, dominated by the ANN lookup and business rule filtering.

A common failure mode is coupling model training too tightly to serving. If the training pipeline fails, the serving layer should continue operating with stale embeddings rather than returning no recommendations. Embedding staleness of up to one week is typically acceptable for cross-sell — co-purchase patterns shift slowly relative to trending or contextual recommendations.

A/B Testing Graph-Based Recommendations

A/B testing cross-sell recommendations introduces experimental design challenges that are absent from simpler feature tests.

Network interference. If treatment and control users share the same product graph, the treatment effect may spill over. A user in the treatment group who purchases a recommended cross-sell product creates a new co-purchase edge that subtly alters the graph for everyone — including control users. This interference biases the estimated treatment effect, typically toward zero (the treatment looks less effective than it is because control users benefit from graph improvements driven by treatment users).

The standard mitigation is cluster-based randomization. Instead of randomizing individual users, randomize at the level of user clusters that have minimal cross-cluster purchasing overlap. Geographic clusters, device-type clusters, or account-age clusters can serve this purpose. The tradeoff is statistical power: cluster randomization requires larger sample sizes to achieve the same precision as user-level randomization.

Metric selection. The primary metric for cross-sell A/B tests is incremental revenue per session from cross-sold items — not click-through rate, not add-to-cart rate, and not recommendation model accuracy. CTR measures interest. Add-to-cart measures intent. Revenue per session measures the thing that matters. A recommendation system that achieves high CTR on low-margin accessories while missing high-margin complements is a worse system, not a better one.

Secondary metrics should include:

• Basket size (units). Cross-sell should increase items per order.
• Basket diversity (categories). Cross-sell should pull purchases across categories, not concentrate them.
• Cross-sell attachment rate. The fraction of orders that include at least one cross-sold item.
• Cannibalization rate. Cross-sell should not displace organic purchases of the same products.
• Return rate on cross-sold items. If cross-sell recommendations drive impulse purchases that are returned at high rates, the net value is negative.

Testing duration. Cross-sell effects compound over multiple sessions. A user who discovers a useful accessory through cross-sell may return to purchase additional accessories in subsequent sessions — a halo effect that short-duration tests miss. Run cross-sell A/B tests for a minimum of four weeks, and measure both immediate (within-session) and lagged (cross-session) effects.

The chart illustrates why duration matters. The immediate lift in week 1 is 4.2%. By week 8, it has more than doubled to 9.2%. A team that calls the test after one week sees less than half the true effect. The cumulative lift — the metric that matters for business decisions — stabilizes around week 6-7. This is the minimum test duration for a reliable measurement of GNN-based cross-sell value.

References

1. Hamilton, W.L., Ying, R., & Leskovec, J. (2017). "Inductive Representation Learning on Large Graphs." Advances in Neural Information Processing Systems (NeurIPS), 30, 1024-1034.

2. Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2018). "Graph Attention Networks." International Conference on Learning Representations (ICLR).

3. Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W.L., & Leskovec, J. (2018). "Graph Convolutional Neural Networks for Web-Scale Recommender Systems." Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 974-983.

4. Kipf, T.N. & Welling, M. (2017). "Semi-Supervised Classification with Graph Convolutional Networks." International Conference on Learning Representations (ICLR).

5. Linden, G., Smith, B., & York, J. (2003). "Amazon.com Recommendations: Item-to-Item Collaborative Filtering." IEEE Internet Computing, 7(1), 76-80.

6. Wang, X., He, X., Wang, M., Feng, F., & Chua, T.S. (2019). "Neural Graph Collaborative Filtering." Proceedings of the 42nd International ACM SIGIR Conference, 165-174.

7. Fan, S., Zhu, J., Han, X., Shi, C., Hu, L., Ma, B., & Li, Y. (2019). "Metapath-based Heterogeneous Graph Neural Network for Intent Recommendation." Proceedings of the 25th ACM SIGKDD International Conference, 2478-2486.

8. Wu, S., Tang, Y., Zhu, Y., Wang, L., Xie, X., & Tan, T. (2019). "Session-based Recommendation with Graph Neural Networks." Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 346-353.

9. Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). "How Powerful are Graph Neural Networks?" International Conference on Learning Representations (ICLR).

10. McAuley, J., Pandey, R., & Leskovec, J. (2015). "Inferring Networks of Substitutable and Complementary Products." Proceedings of the 21st ACM SIGKDD International Conference, 785-794.

11. Zheng, L., Noroozi, V., & Yu, P.S. (2017). "Joint Deep Modeling of Users and Items Using Reviews for Recommendation." Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, 425-434.

12. Zhang, M. & Chen, Y. (2018). "Link Prediction Based on Graph Neural Networks." Advances in Neural Information Processing Systems (NeurIPS), 31, 5165-5175.