Reachability-Constrained Pruning of the Message-Passing Graph for Long-Tail Recommendation

Graph-based recommenders learn user and item vectors by repeatedly averaging each node with its neighbors in the graph of who-interacted-with-what. They are known to push recommendations toward already-popular items. Recent theory locates the cause in the graph itself: an item's influence on training gradients grows with its degree $d_i$ as $d_i^{3/2}$ (How Graph Convolutions Amplify Popularity Bias for Recommendation?), and the neighbor-averaging process concentrates vector length on high-degree hubs (Topology-Aware Popularity Debiasing via Simplicial Complexes). The fixes built on this diagnosis leave the graph alone. They subtract a bias vector after training, add a loss penalty, or rebuild a separate graph at test time. We propose to change the graph the model averages over. The method chooses a subset of interaction edges to use for message passing, while still training on every interaction. The selection is a discrete search with an explicit constraint: every long-tail item must keep enough multi-hop paths to users, so pruning hub edges does not cut niche items off from the signal they need.

This is a combinatorial edge-selection problem over millions of edges. We borrow scaling tools from topology optimization, where similar search spaces have been made tractable. One is spectral partitioning guided by sensitivity weights, as used for power-grid line switching (Convex relaxation for mixed-integer optimal power flow problems). The other is neighborhood-restricted local search, as used for influence maximization (An Efficient Network-aware Direct Search Method for Influence Maximization). The question we most want answered is pointed. Is popularity bias in graph recommenders a function of node degree alone, so that a one-parameter degree reweighting suffices? Or do the specific edges matter? The proposal is built so that either answer is informative.

Core Claim

Our hypothesis is that the edges driving popularity bias differ from the edges a degree heuristic would drop. A degree-only rule weakens all hub edges uniformly. On sparse graphs, that also severs the few paths through which a tail item's users connect to the rest of the graph. A search that removes hub edges only where they are redundant for tail reachability should therefore beat the best tuned degree-only rule on tail accuracy, and the gap should be largest on the sparsest datasets. The prediction is falsifiable. If a tuned degree-dependent edge reweighting matches the searched subgraph on Gowalla and Yelp2018, the combinatorial machinery is unnecessary, and we will report that.

Formally, let $m \in \{0,1\}^{E}$ mask the $E$ interaction edges used for propagation, and let $Z_L(m)$ be the item embeddings after $L$ propagation layers of a warm-started LightGCN-style model. We solve

$$\min_{m} \; H(m) - \lambda\, A(m) \quad \text{s.t.} \quad r_j(m) \ge \rho \;\; \text{for every tail item } j, \qquad \textstyle\sum_e (1-m_e) \le B .$$

The terms are defined as follows:

  • $H(m)$ is the "hub share". For users adjacent to tail items, it is the average fraction of their layer-$L$ representation contributed by the top-20% most popular items.
  • $A(m)$ is overall validation recall of the propagated model.
  • $\lambda$ trades the two terms off.
  • $r_j(m)$ counts users reachable from tail item $j$ within $L$ hops in the pruned graph.
  • $\rho$ is the reachability floor.
  • $B$ is the pruning budget.

The constraint on $r_j$ is what a degree heuristic cannot express. The loss used for training still covers all observed interactions; only the averaging graph changes.

Research Program

The work has three parts.

Diagnostic study. On a trained LightGCN, we measure per-edge sensitivity: the gradient of $H$ and of tail validation recall with respect to a relaxed edge mask. We then ask how much of its variance is explained by the endpoint degrees alone. If degree explains nearly all of it, the core claim is already in trouble, and we will say so before building the search. This step serves as an early stop-or-go check.

Search at scale. The search space is $2^{E}$. Following the power-grid work, we compute a Fiedler-vector partition of the interaction graph, weighting edges by the sensitivity scores from the diagnostic. That work used dual multipliers from a semidefinite relaxation as edge weights. Our analogue is the mask gradient, which plays the same role of pricing each edge's effect on the objective. Cutting low-sensitivity edges yields blocks that can be optimized nearly independently and in parallel.

Within each block, we run a swap search in the style of NaDS:

  • Phase one considers only edges incident to users who neighbor tail items currently violating or near the reachability floor.
  • Phase two widens to two-hop neighborhoods if phase one finds no gain.
  • Phase three opens the whole block.

In influence maximization, this restriction cut function evaluations by 35–60% at equal solution quality. We expect a similar saving because most edges are far from any tail item. Each candidate is scored by a few propagation steps of the frozen warm-start model, not by retraining.

Retraining. We retrain on the pruned propagation graph and check whether the gradient-dominance and rank-collapse symptoms actually shrink. We measure effective rank of the embedding covariance, as in Mitigating the Popularity Bias of Graph Collaborative Filtering: A Dimensional Collapse Perspective, and the degree-versus-gradient-norm slope predicted by the $d_i^{3/2}$ analysis. A warm-start, search, retrain loop of one or two rounds is the full method.

Relation to prior work. The prior work plays three distinct roles.

Baselines

Unmodified LightGCN. This is the do-nothing reference: the same backbone, embedding size, and training schedule on the full graph. On Yelp2018, the dimensional-collapse paper reports LightGCN Recall@20 of 0.0639.

Degree-only reweighting. This is the ablation that isolates our key ingredient, and the most dangerous competitor. It keeps every edge but scales each message by $(d_u d_i)^{-\gamma}$, or drops edges with probability increasing in item degree, using a single degree exponent $\gamma$ or dropout rate. It directly targets the $d_i^{3/2}$ term, so it is the cheapest way to get what our method promises. We give it the same tuning budget in GPU-hours as our search plus retraining, sweeping its parameter on validation tail recall. No reported result was found on Lacuna for degree-reweighted propagation as a popularity debiaser. A second ablation drops the reachability constraint from our search, which tells us whether the constraint, rather than search itself, carries the gain.

DAP. This is the strongest post-hoc method (How Graph Convolutions Amplify Popularity Bias for Recommendation?). It clusters embeddings with K-means and subtracts a per-cluster popularity vector at each layer. Its paper reports tail-set gains of 23.96% in Recall and 28.27% in NDCG on Gowalla, and over 50% on Yelp2018, using the bottom-80% item protocol that we adopt. Because DAP is post hoc, we also apply it on top of our pruned model. Composability is part of the claim.

Training-time methods. These are GCF$_{logdet}$, which reports Yelp2018 overall Recall@20 of 0.0725 with a 1.51x larger relative gain on unpopular items, and PAAC, which reports +30.2% NDCG@20 and an 87.5% head-tail gap reduction on Yelp2018. They are the strongest loss-based competitors. Both are rerun from their published settings on our splits, with tuning budget matched to ours.

MACR. This is the counterfactual score-subtraction method (Model-Agnostic Counterfactual Reasoning for Eliminating Popularity Bias in Recommender System), which reports an average 241% HR@20 gain over LightGCN on a debiased test protocol. It is included as the output-layer reference point.

What counts as winning. Beating a baseline means higher tail Recall@20 and NDCG@20 at no more than a one-point relative loss in overall Recall@20, averaged over five seeds with non-overlapping confidence intervals. The decisive comparison is against the tuned degree-only reweighting.

Why not just…?

Why not just reweight messages by degree instead of searching over edges? This is the real threat. The $d_i^{3/2}$ result is stated purely in terms of degree, which suggests a degree correction might be enough. Our evidence against it so far is indirect: the sparse-graph failures of PAAC hint that uniform hub suppression hurts where tail items have few paths. The diagnostic stage settles the question directly. If endpoint degree explains most of the variance in edge sensitivity, or if tuned reweighting matches our method on Gowalla and Yelp2018, we will conclude that topology search is not needed and publish the tuned degree baseline as the result.

Why not just apply DAP or TSP after training? They are cheap and strong, with TSP reporting a 37.5% tail Recall@20 gain on Adressa in seconds to minutes. But they act on representations already shaped by hub-dominated gradients. The dimensional-collapse analysis argues that subtraction cannot restore dimensions lost during propagation. We test this by measuring effective rank: if DAP on unpruned LightGCN matches our method's tail accuracy and rank, the post-hoc route wins. We also report DAP on top of our pruned model, since the methods are not exclusive.

Why not just learn a soft edge mask end to end, as in Gumbel-softmax rewiring? A differentiable mask is simpler to implement. It is the natural relaxation of our problem, and we run it as a baseline with the same objective. Its weakness is the hard reachability floor: penalty relaxations of combinatorial constraints often satisfy them on average while violating them for exactly the sparse nodes we care about. We report the fraction of tail items below the floor for both methods. If the soft mask meets the constraint and matches accuracy, we drop the discrete search.

Why not just add a loss penalty such as LogDet? GCF$_{logdet}$ already fights collapse during training without touching the graph. Pruning and penalties are complementary, so we test the combination. If LogDet alone matches pruning-plus-LogDet, graph editing adds nothing beyond what the penalty provides.

Proposed Experiments and Decisive Checks

Datasets and protocol.

  • Static benchmarks: Yelp2018, Gowalla, and Amazon-book, with the bottom-80% tail protocol used by DAP and the uniform-item debiased test sets used across this literature.
  • Non-stationary setting: Adressa and Globo, where popularity shifts quickly. Here we re-run the search on rolling windows. This tests whether a pruned graph transfers across a popularity spike, a weakness the GSDA authors name explicitly.
  • Metrics: overall and tail Recall@20 and NDCG@20, head-tail gap, effective rank of item embeddings, and the fitted slope of gradient norm against degree.
  • Cost reporting: search wall-clock and function-evaluation counts, with and without the phase-restricted neighborhoods and the spectral partition, to show that the complexity tools are what make the search feasible on Amazon-book.

Decisive checks. There are three, in order of importance:

  1. The searched subgraph beats tuned degree-only reweighting on tail metrics, with the margin largest on Gowalla.
  2. Removing the reachability constraint erases most of that margin.
  3. The retrained model shows a flatter degree-gradient slope and higher effective rank than DAP-corrected LightGCN.

Failure of the first check is a clean negative result for topology search. Failure of the second means the gain comes from search, not structure. Failure of the third means the method works for reasons other than the mechanism we claim.