Large recommender models are trained on graphs of who interacted with what, split across many machines. Two facts about these systems are usually handled separately. First, the network linking the machines is not uniform: traffic between two machines on the same rack is cheap, while traffic that crosses racks, pods, or a torus dimension is expensive. Graph partitioners nonetheless treat every machine as equally far from every other. Second, user tastes drift, so the parts of the graph that training actually touches keep changing. A partition computed once slowly decays, and recomputing it from scratch moves large amounts of data across exactly the expensive links.
This note proposes splitting the partition problem by timescale and matching each timescale to a tier of the physical network. We conjecture that the coarse community structure of a recommendation graph, the broad tastes that need years of sparse history to estimate, changes slowly, and that drift mostly reshuffles users between nearby fine-grained clusters. If that holds, the coarse partition, built on the long-horizon graph, should be pinned to the expensive network boundaries and rarely changed. The fine partition, built on a recency-weighted graph, should be placed within the cheap boundaries and updated often. Most drift-driven data movement would then stay inside a rack. The claim is testable before any system is built, and if the timescale separation is absent in real data, the idea fails cleanly.
Core Claim
In mini-batch training of graph recommenders such as LightGCN, which keeps only linear neighbor averaging, or SimGCL, which adds embedding noise and a contrastive uniformity loss to fight sparsity, the traffic over an interaction edge is proportional to how often that edge is sampled. We sample interactions with recency weighting, following the exponential discount that NS-DPO applies to stale preference pairs. Under that sampling, the communication graph is the time-decayed interaction graph. We weight edge $e$, observed at time $t_e$, at current time $t$ as $w_e(t)=\gamma^{\,t-t_e}$. The expected per-epoch communication cost of an assignment $p$ of vertices to machines is
$$C(p,t)=\sum_{(u,v)} w_{uv}(t)\,c\big(p(u),p(v)\big),$$
where $c(i,j)$ is the measured cost of moving one embedding between machines $i$ and $j$: zero on the same machine, small within a rack, large across racks or torus dimensions. The proposal minimizes $C$ hierarchically. The top level partitions into $R$ groups, one per expensive physical domain, using a slow discount $\gamma_{\text{slow}}$ close to 1. The lower level partitions each group across its machines using a fast discount $\gamma_{\text{fast}}$. Each level is updated incrementally and at its own cadence, and each carries both an edge balance constraint and an embedding-row (vertex) balance constraint.
Two claims follow and both can be falsified. The first is that, at equal accuracy, this design moves fewer bytes over expensive links than either a topology-blind incremental partitioner or a static hierarchical one, counting both training traffic and migration traffic. The second is that the slow level is required, not optional. Partitioning on the recent graph alone is the sliding-window shortcut, and interaction sparsity predicts it will produce unstable, noisy coarse cuts, since recent data alone is too thin to reveal communities.
Prior Work and What It Leaves Open
Three partitioning systems motivate the design and supply its mechanics. Spinner runs label propagation with a capacity penalty on Giraph, and its incremental mode adapts to 2% new edges 85% faster than recomputing. Hermes repartitions a live graph database online, using a logical simulation phase before physical migration and directional rules that prevent oscillation. TopoX fuses low-degree vertices and splits hubs before partitioning. We reuse Spinner-style label propagation for both levels, the Hermes logical-then-physical migration, and TopoX-style hub splitting for popular items. All three assume a uniform network and treat edges as permanent. None separates timescales or prices a migration by where it goes.
Two further papers constrain the design. The partitioning benchmark for distributed GNN training shows that traffic is dominated by embedding and feature vectors, which justifies counting bytes of embeddings rather than edges. It also shows that edge-balanced partitioners leave vertex imbalances above 1.0, which crash workers. That is why we impose a vertex balance constraint: in an ID-embedding recommender, nearly all memory sits in vertex rows. DistGNN hides traffic by computing on neighbor aggregates up to $r$ epochs stale, staying within 1% accuracy at $r=5$. It is the main rival explanation for why topology might not matter, and it is also a tool we borrow for cross-rack contrastive negatives.
Network-side work motivates pricing the cut by physical cost and constrains how that cost is obtained. Swing shows that collectives which ignore torus layout suffer congestion deficiency 2.0 against 1.19 for a topology-aware schedule, and are up to 2.2–3x slower. Geography-based analysis and the AS-boundary delay model show that naive proxies such as distance or hop count mispredict cost. We therefore take $c(i,j)$ from measured per-pair throughput and latency rather than from a topology diagram, and refresh it on a coarse schedule to bound probing overhead.
On the drift side, SPLIT decomposes a user's history into multiple evolving preference threads using reinforcement learning. Its finding that tastes are multi-threaded, with dormant threads returning, is the behavioral basis of our timescale conjecture. Dormant threads belong to the slow graph, and active ones to the fast graph. We do not use its online allocator, which is costly. Our closest systems relative, KIP, isolates drifting heavy keys in Spark and Flink streams. It works on flat keys, not on graphs or network tiers.
Research Program
The first stage is a measurement study that requires no system. On timestamped interaction logs, we compute partitions at successive time windows at two granularities, $R$ coarse groups and $R\times M$ fine parts. For each pair of consecutive windows, we measure how much decayed edge weight changes sides. The conjecture predicts that the coarse cut churns much less than the fine cut, and that this gap widens as the slow discount lengthens. We also measure how unstable coarse cuts become when they are computed from a recent window alone; sparsity predicts high instability. If the coarse and fine levels churn at similar rates, we stop and report a negative result.
The second stage builds the partitioner. It runs two label propagation processes over the same cost function $C$, one per level, each with edge and vertex capacity penalties. Migration decisions are first simulated on metadata, then executed on a schedule: the fine level is touched every update window and the coarse level only when its decayed cut gain exceeds the expected cross-domain cost of migrating. Popular items are split across groups so that hub replication is a deliberate choice rather than an accident.
The third stage integrates training. A distributed LightGCN/SimGCL trainer uses recency-weighted interaction sampling and fixed-fanout neighbor sampling. The contrastive loss in SimGCL needs negatives spread across the whole catalog to enforce uniformity, but locality-preserving placement concentrates similar items on the same machines. We therefore draw negatives from within the rack each step and supplement them with a cache of cross-rack embeddings refreshed every $r$ steps, in the spirit of DistGNN's delayed communication. Uniformity of the learned embeddings and long-tail recall are tracked to detect the sampling bias this could introduce.
Baselines
The naive reference is random hash placement of users and items, retrained on the same recency-weighted sampling. It needs no preprocessing and is what many embedding-table systems do. Any proposed method must beat it in cross-rack bytes per epoch while staying within noise on accuracy, otherwise none of the machinery is justified.
The strongest existing partitioning competitor is a high-quality static partitioner computed on the full history and then incrementally maintained. We run it in two variants. One is KaHIP, the strongest vertex partitioner for DistDGL-style mini-batch training in the benchmark study, which reports average speedups of 1.37x over random on DistDGL. The other is Spinner-style incremental label propagation on the uniform-cost objective. The benchmark also reports HEP100 averaging 4.36x over random on full-batch DistGNN, but that is an edge partitioner for a different training mode, so we treat 1.37x as the relevant reference for mini-batch recommenders. We found no reported result on Lacuna for any topology-aware or drift-aware partitioner on recommendation graphs, nor for distributed LightGCN or SimGCL training.
On accuracy, the reference is centralized SimGCL. Its paper reports Recall@20 more than 25% above LightGCN on Amazon-Book, and the file gives no absolute value, so we reproduce both models centrally on our time-ordered splits before comparing.
A strong systems baseline is the two-step procedure of partitioning topology-blind, then mapping parts onto machines to minimize $C$, applied after every repartition. It isolates whether jointly hierarchical placement matters at all.
The key ablation is identical to our method except that both levels use the same discount, either all fast or all slow. This isolates the timescale separation, which is the one ingredient that is new here.
Fairness rules apply to all methods. Every method uses the same sampled training stream, the same embedding dimension, the same update cadence, the same machine count and memory caps, and the same partitioner wall-clock budget per update window. Hyperparameters, including SimGCL's noise magnitude and loss weight, are tuned once on a central validation slice and then frozen across all placements. Beating a baseline means a lower total of cross-domain bytes, training plus migration, over the full replayed timeline, together with lower epoch time on the tiered cluster. Recall@20 and NDCG@20 must stay within the run-to-run spread of the central model.
Why not just…?
Why not just partition once with a good static hierarchical partitioner and never repartition? This is the most serious threat. If the coarse structure is very stable, a one-time rack-aligned partition may capture nearly all the benefit, and the fine level adds little. The measurement stage answers this directly, because it quantifies how fast the decayed fine cut decays. The static hierarchical baseline is run over the full replayed timeline. If its cross-rack traffic stays flat, we report that the timescale idea reduces to "partition hierarchically once," which is still a useful, cheaper finding.
Why not just use a sliding window and repartition from scratch periodically? Windowing discards the long history that sparse collaborative filtering depends on. SimGCL's motivation is precisely that sparse supervision collapses long-tail embeddings, and SPLIT shows that dormant preference threads return. Recomputing from scratch also moves data across expensive links, and Spinner's incremental mode is 85% faster than full recomputation even before migration cost is counted. The all-fast ablation is the windowing approach in our setting, and we report both its coarse-cut instability and its migration bytes.
Why not just hash and hide the latency with stale communication, as DistGNN does? For small embedding dimensions on a well-provisioned network, overlap may make placement irrelevant. DistGNN's stale aggregates at $r=5$ cost under 1% accuracy. But overlap does not reduce bytes. On oversubscribed or torus networks, the congestion results in Swing indicate that bytes crossing scarce links set the time. We run hash placement with the same staleness budget our method uses for cross-rack negatives, and we sweep embedding dimension and network oversubscription to locate where hiding stops being sufficient.
Why not just partition topology-blind and remap parts to machines afterwards? Remapping minimizes $C$ only for the cut it is given, and it reshuffles whole parts after each repartition, which can create large cross-rack migrations. The two-step baseline measures whether this matters. If it matches our method on both training and migration bytes, the hierarchical coupling is unnecessary, and we would keep only the timescale separation applied to the remapped partition.
Proposed Experiments
The datasets are Gowalla, Yelp2018, and Amazon-Book in timestamped form with chronological splits: train on everything before a cutoff, then replay later interactions in windows, testing each window's recommendations on the next. The sequential Amazon, Wechat, and Foursquare logs used by SPLIT serve as a second drift regime. These graphs fit on one machine, which is an advantage for accuracy, because every distributed run can be checked against an exact central reference. It is a limitation for scale. The file names no billion-edge, timestamped interaction benchmark, so we raise scale by replicating users with perturbed timelines, and we state plainly that this is synthetic.
Network costs come from two sources. The first is a real cluster with rack-level oversubscription, from which $c(i,j)$ is measured. The second is a simulated torus and fat-tree, set up following the interconnect simulations in Swing. The metrics are cross-domain and cross-machine bytes per epoch, migration bytes broken down by tier, epoch time, peak per-worker memory and vertex imbalance, Recall@20 and NDCG@20 per window, and embedding uniformity plus long-tail recall to check the effect of rack-local negatives.
Three results decide the question, in order. The first is the churn ratio between coarse and fine cuts on real timelines. Without a clear gap, the proposal ends. The second is total cross-domain bytes against the static hierarchical baseline and the single-timescale ablation over the replayed timeline, with accuracy held equal. The third is the crossover point in embedding dimension and oversubscription at which hash placement with staleness stops matching topology-aware placement. That point tells practitioners when any of this is worth the trouble.
References
- LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation
- Are Graph Augmentations Necessary?: Simple Graph Contrastive Learning for Recommendation
- Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift
- Spinner: Scalable Graph Partitioning in the Cloud
- Hermes: Dynamic Partitioning for Distributed Social Network Graph Databases
- TopoX: Topology Refactorization for Efficient Graph Partitioning and Processing
- An Experimental Comparison of Partitioning Strategies for Distributed Graph Neural Network Training
- DistGNN: scalable distributed training for large-scale graph neural networks
- Swing: Short-cutting Rings for Higher Bandwidth Allreduce
- Geography-based structural analysis of the Internet
- Network Delay Model for Overlay Network Application
- Sequential Recommendation with User Evolving Preference Decomposition
- System-aware dynamic partitioning for batch and streaming workloads