Every e-commerce company has a version of this problem: an order gets placed, the delivery is attempted, and the package comes back. Return-to-Origin, or RTO as it's known in the industry, is one of the most expensive and operationally painful events in the e-commerce supply chain.
At Meesho, where we serve millions of customers across Tier-1, Tier-2, and Tier-3 India, RTO is not just a logistical headache. It hits sellers hard, disrupts cash flows, and creates a cycle of financial loss that is difficult to break.
The question our data science team set out to answer was: can we predict which orders are likely to come back, before they do?
The answer turned out to require rethinking the fundamental structure of how we model relationships between entities in an order and that led us to publish DPHGNN (Dual Perspective Hypergraph Neural Network) at KDD 2024, one of the most competitive machine learning conferences in the world.
Why This Is Harder Than It Looks
At first glance, RTO prediction sounds like a standard classification problem. You have historical order data, some features about the customer, seller, and product and you want to predict a binary outcome: will this order be returned or not?
But the reality is more complex. An order isn't just a transaction between one customer and one seller. It involves multiple entities – the customer, the product, the supplier, the courier – all interacting within a single order event. And critically, the relationships between these entities aren't simple one-to-one connections. They're multi-party interactions.
This is where conventional graph-based models hit their limits. Graphs model relationships between pairs of nodes. But real-world order transactions involve groups of entities interacting simultaneously — not pairs.
If you model an order as a graph, you're forced to break a naturally group-level relationship into artificial pairwise connections. You lose information in that translation. And when you're trying to predict outcomes that depend on the full group dynamic – like whether a courier-supplier-customer combination is historically prone to RTO – that information loss hurts.
What we needed was a data structure that could natively represent these group-level relationships. That's where hypergraphs come in.
A Quick Primer: Graphs vs Hypergraphs
In a regular graph, each edge connects exactly two nodes. In a hypergraph, a single "hyperedge" can connect any number of nodes simultaneously. This makes hypergraphs a much more natural fit for modeling complex, multi-party relationships.
In our case, each order transaction becomes a hyperedge connecting four entity types: the customer, the product, the supplier, and the courier. Instead of approximating these relationships through pairwise links, we can represent the actual group interaction directly.
Hypergraph Neural Networks (HGNNs) extend the idea of Graph Neural Networks (GNNs) to this richer structure, propagating information through these group-level connections rather than just between node pairs.
But here's the catch: existing HGNNs had significant limitations that made them unreliable in practice, particularly on real-world data that is sparse, imbalanced, and structurally complex like ours.
What Was Broken With Existing HGNNs
The field of hypergraph learning broadly divides into two camps: spatial methods (which propagate messages through local neighborhoods) and spectral methods (which use mathematical transformations to learn global structure). Each had strengths the other lacked.
More specifically, we observed three recurring problems:
- The spatial vs. spectral performance gap: On some datasets, spatial methods significantly outperformed spectral ones and on others, it reversed. No single approach was reliably better.
- Over-smoothing: As you stack more layers in an HGNN, node features tend to blur together, especially in sparse or highly symmetric graphs. This was a serious problem in our RTO data, where order structures are repetitive and symmetric by design.
- Automorphism blindness: In a symmetric hypergraph (like ours, where every order has the same four entity types), standard HGNNs can't distinguish between structurally identical nodes, even if they represent different real-world entities. They literally assign the same learned representation to different nodes, which makes the model useless for classification.
These weren't just academic limitations. In our experiments, every baseline HGNN we tested performed poorly on our CO-RTO dataset for exactly these reasons.
What DPHGNN Does Differently
DPHGNN is built around a single core idea: don't force a choice between spatial and spectral – do both, and let them reinforce each other. Here's how we approached each problem:
1. Bringing Two Perspectives Together
Rather than choosing between spatial and spectral learning, DPHGNN uses both in a unified architecture. The model has two main components that run in parallel:
- A static update layer that captures spectral inductive biases – essentially, global structural patterns encoded through hypergraph Laplacians.
- A dynamic feature fusion layer that explicitly pulls in information from the underlying graph structure and injects it into the hypergraph message-passing process.
Think of it this way: the static layer gives each node a unique "fingerprint" based on its position in the overall structure. The dynamic layer then uses actual pairwise interaction patterns to enrich the hypergraph-level messages.
2. Breaking Symmetry With Spectral Identifiers
The automorphism problem – where structurally identical nodes get identical representations is a fundamental weakness in standard HGNNs. DPHGNN tackles this by combining three different Laplacian operators (each capturing a different view of the graph's structure) and concatenating their outputs rather than summing them.
This concatenation is crucial. Summing Laplacians mathematically collapses them into redundant information. Concatenating them preserves the distinctiveness of each view, giving each node a unique spectral identifier that helps break symmetry groups – even in highly uniform hypergraph structures like ours.
3. Topology-Aware Attention
Before information flows through the hypergraph, DPHGNN first decomposes it into three different graph views capturing different structural semantics and uses cross-attention to learn which view matters most for each node at each step.
This is what we call Topology-Aware Attention (TAA). It allows the model to adaptively weight spatial and spectral information depending on the local structure around each node, rather than applying a one-size-fits-all aggregation.
4. Provably More Expressive
We didn't just benchmark DPHGNN empirically, we also proved theoretically that it is at least as expressive as the 3-GWL (Generalized Weisfeiler Leman) test for distinguishing non-isomorphic hypergraphs. This makes DPHGNN, to our knowledge, the first HGNN that provably breaks automorphism groups, a significant theoretical advance in the field.
Results: On Benchmarks and in Production
Across 8 Standard Benchmarks
We tested DPHGNN against seven state-of-the-art baselines across eight standard hypergraph datasets, ranging from academic citation networks to restaurant review hypergraphs. DPHGNN consistently outperformed the best baselines across most datasets, demonstrating that combining spatial and spectral inductive biases generalises well across very different data structures.
The performance improvement wasn't marginal. On some datasets, DPHGNN outperformed the best spatial baseline by over 6%, and the best spectral baseline by over 5%.
On Our RTO Dataset (CO-RTO)
The real test was on our own data. CO-RTO is a challenging dataset: it's sparse, highly symmetric, class-imbalanced (roughly 1:4 RTO to non-RTO), and contains exactly the kind of automorphism groups that break standard HGNNs.
DPHGNN achieved a macro F1-score of ~51%, outperforming the best baseline by approximately 7 percentage points. Given the class imbalance and structural difficulty of this dataset, this is a meaningful improvement.
Every baseline we tested suffered from over-smoothing, automorphism blindness, or both. DPHGNN was the only architecture robust enough to handle all three structural challenges simultaneously.
How It's Deployed at Meesho
Running a hypergraph model in production at e-commerce scale requires careful engineering alongside the ML. Here's a brief sketch of the deployment architecture:
- Data ingestion: Large-scale transaction data is pulled in real-time via a streaming pipeline and distributed across clusters for feature computation.
- Hypergraph construction: For each order, we construct a hyperedge containing the four entity nodes – customer, product, supplier, courier along with their feature vectors.
- Transductive inference: Because model predictions influence downstream order actions (flagged orders get blocked), we use a holdout sample where no action is taken, to preserve unbiased training data for future model iterations.
- Inference and actioning: Once trained, predictions for the latest transactions are generated on GPU clusters and published to a queue consumed by the order management system.
This feedback loop where model actions affect future data is one of the trickiest parts of deploying ML in operational settings, and it requires careful design to avoid data contamination in training.
What We Learned
A few things stand out from this work that we think generalise beyond RTO prediction:
- Graph structure matters more than model complexity: Choosing the right data representation – hypergraph over graph had a bigger impact than architectural sophistication. Getting the problem formulation right is the highest-leverage decision.
- Spatial and spectral aren't competitors: The best results came from combining both perspectives. In practice, the relative importance of each shift depends on the data structure, which is exactly why a unified, adaptive approach works better than picking a side.
- Theoretical guarantees matter for trust: The expressivity proof wasn't just academic. It gave us confidence that the model was fundamentally capable of solving the problem before we ran a single experiment.
- Class imbalance + sparse graphs is a brutal combination: Standard ML fixes for class imbalance (resampling, cost-sensitive loss) help, but they can't compensate for a fundamentally limited model architecture. The architecture needs to be designed with this constraint in mind from the start.
What's Next
This work opens several directions we're actively exploring:
- Extending hypergraph modeling to other e-commerce prediction tasks where multi-entity relationships are central – fraud detection, seller quality scoring, and demand forecasting are all natural candidates.
- Scaling the hypergraph construction and training pipeline to handle growing transaction volumes without proportional cost increases.
- Exploring inductive (rather than transductive) settings, so the model can generalise to entirely new entities it hasn't seen during training – a key requirement as our seller and customer base grows.
The full paper is available at KDD '24 proceedings and code is open-sourced on GitHub.
About the Authors
Raghu Kolla and Debashis Mukherjee are ex-data scientists at Meesho, Bangalore. This work was conducted in collaboration with researchers at IIT Delhi and IIIT Delhi, and published at the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2024).
