Graph recommenders score a user–item pair by averaging information from the user's past interactions. An average lets anyone who can add interactions move the result as far as they like. A seller who plants a few hundred fake clicks can drag an item toward a target audience, and the standard defenses do not model that seller at all: they treat bad edges as random accidents. Mechanism design without money, the study of decision rules that people cannot profitably game when no payments are involved, has a well-known answer to the averaging problem in one dimension. Replace the mean with a median, optionally padded with fixed "phantom" reports. The difficulty is that recommender embeddings are 64- or 128-dimensional vectors, and in that setting the clean median guarantees disappear.
This note observes that the dimensionality problem can be sidestepped, because a recommender never needs an aggregated vector. It needs an aggregated score, and a score is one number. We propose to take the per-neighbor scores that linear test-time aggregation already averages implicitly, and combine them with a generalized median whose phantom points sit at the model's own matrix-factorization prediction. The resulting rule has three properties. It costs almost nothing to train. It provably limits how far any coalition of injected edges can move a score. And it yields a cheap, per-user certificate that a top-20 list cannot be changed by $k$ fake interactions.
Core Claim
The setting is test-time aggregation in the style of TAG-CF. How Does Message Passing Improve Collaborative Filtering? showed that a plain matrix-factorization (MF) model, plus one neighborhood-averaging step applied only at inference, matches full graph neural networks. It also showed that the inference-time step is where nearly all the benefit lives: removing it costs about 29.7% NDCG@20 on Gowalla. Because the step is linear, the aggregated score $\langle \mathbf{e}_u^{\text{test}}, \mathbf{e}_i\rangle$ is exactly a weighted mean of scalar neighbor scores $\langle \mathbf{e}_j, \mathbf{e}_i\rangle$ over the user's interacted items $j$. That mean is the manipulable rule of facility location. We replace it with
$$ s(u,i) = \mathrm{median}\Big(\{\langle \mathbf{e}_j, \mathbf{e}_i\rangle : j \in \mathcal{N}_u\} \cup \{\phi_1(u,i), \dots, \phi_m(u,i)\}\Big), $$
where $\mathcal{N}_u$ is the set of items user $u$ interacted with and $\mathbf{e}$ are the trained MF embeddings. The $\phi_k(u,i) = \langle \mathbf{e}_u, \mathbf{e}_i\rangle + c_k\,\sigma_u$ are $m$ phantom scores placed around the user's own MF prediction, with offsets $c_k$ and a per-user spread $\sigma_u$. A mirrored rule aggregates over an item's interacting users.
The phantoms do two jobs, each grounded in the file. First, they are the generalized-median construction that The Capacity Constrained Facility Location Problem characterizes as the family of anonymous, manipulation-proof one-dimensional rules. This gives a principled design space instead of an ad hoc robust estimator. Second, they anchor the score at the MF prediction, in the spirit of using a learned prediction as the reference point, as the Harmonic Mechanism does in Strategic Facility Location via Predictions. Low-degree users, who have few neighbors and are exactly the users TAG-CF+ found benefit most, are therefore pulled toward their own prediction rather than toward whichever few edges they have.
The key property is an order-statistic bound. If an attacker adds $k$ edges to $\mathcal{N}_u$, $s(u,i)$ can move at most $k$ positions up the sorted list of $|\mathcal{N}_u| + m$ honest values. Comparing these shifted order statistics against the score of the $K$-th ranked item gives an exact, cheap certificate of top-$K$ stability.
The idea is new against both near misses in the file. Median Activation Functions for Graph Neural Networks applies medians to scalar node features on graphs of about 230 nodes, as a statistical filter. It has no phantoms, no ranking objective, no threat model, and no certificate. Dynamic Online Recommendation for Two-Sided Market with Bayesian Incentive Compatibility studies incentives in recommendation, but as bandit exploration without any graph. Our proposal also does not claim full dominant-strategy truthfulness for all users. The agents we model are providers who control injected edges. What we inherit from mechanism design is bounded influence and the generalized-median design space, not a blanket truthfulness theorem.
Research Program
The work has three parts.
Theory. We formalize a provider who controls a budget of $k$ fake interactions (added edges, or Sybil users) and whose payoff is the exposure of one target item to a target cohort. We prove the displacement and certification bounds above for both the user-side and item-side rules. We then characterize how phantom placement trades clean accuracy against manipulation resistance: many tight phantoms approach plain MF, and zero phantoms give the pure neighbor median. This mirrors the consistency–robustness trade-off of the Harmonic Mechanism.
System. We implement the rule inside the TAG-CF codebase (snap-research/Test-time-Aggregation-for-CF). To keep the cost near TAG-CF's, we apply the median to the top few hundred candidate items per user produced by linear TAG-CF. The extra work is then one sort over the user's degree per candidate.
Training-time poisoning. We test whether a test-time defense is enough. Injected edges also enter MF training through the ranking loss, so we evaluate attacks injected both after and before training. If poisoning during training dominates, the defense needs a training-side counterpart, and we will report that rather than hide it. This directly probes the tension in the file between TAG-CF's finding and training-time denoisers such as CGI.
Baselines
The naive reference is plain MF trained with Bayesian Personalized Ranking (BPR, a pairwise ranking loss), with no aggregation. The direct reference is linear TAG-CF and TAG-CF+ from How Does Message Passing Improve Collaborative Filtering?, which is the very mean we replace. The file reports relative figures only: TAG-CF+ improves MF's NDCG@20 by 39.2% for low-degree MovieLens-1M users, and removing test-time aggregation costs about 29.7% NDCG@20 on Gowalla. No absolute Recall@20 or NDCG@20 value was found on Lacuna for any baseline on these datasets. We will therefore rerun all baselines ourselves with the released configurations.
The strongest denoising competitors fall into two groups. The first is CAGCN*, from Collaboration-Aware Graph Convolutional Network for Recommender Systems, which down-weights edges whose user and item share few common neighbors. It reports nearly 10% Recall@20 over LightGCN. The second is the learned edge-masking model CGI, from Contrastive Graph Structure Learning via Information Bottleneck for Recommendation, which reports about 10% over SGL on MovieLens-1M and robustness to 5–20% fake edges. We add the contrastive-dropout model SGL, from Self-supervised Graph Learning for Recommendation, which reports that under 20% noise it beats LightGCN trained on clean data. LightGCN, from LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation, anchors the comparison.
Fairness rules apply to every method. All methods get the same splits, embedding size, and corrupted graphs. Each receives an equal hyperparameter-search budget measured in GPU-hours, which favors the cheaper methods only because they are cheaper.
Three ablations isolate the key ingredients:
- the scalar-score median with no phantoms;
- a trimmed mean of the same scalar scores;
- a coordinate-wise median of neighbor embedding vectors.
Beating the baselines means two things together. Clean NDCG@20 must stay within 2% of linear TAG-CF. And the target-item exposure gained per injected edge must be at least halved relative to the best of CAGCN*, CGI, and SGL, under an attack adapted to each defense.
Why not just…?
Why not just take the coordinate-wise median of neighbor embeddings? This is the most natural reading of Gap 1. It is a real competitor, because it also bounds each coordinate. However, the file notes that coordinate-wise medians distort directions in $\mathbb{R}^d$. They also give no clean bound on the inner-product score, so no certificate follows. The vector-median ablation settles this empirically on clean accuracy, attacked exposure, and certified fraction. If it matches the scalar rule on all three, the phantom and certification contributions still stand, but the "aggregate scores, not vectors" claim does not.
Why not just use a trimmed mean, or any off-the-shelf robust estimator, on the scalar scores? This is the strongest threat to the mechanism-design framing. A trimmed mean at the right trimming level may perform similarly. Our answer has two parts. Fixed trimming ignores degree, so it either over-trims high-degree users or under-protects low-degree ones. Phantoms anchored at the MF prediction handle low degree by design. The trimmed-mean ablation, broken out by degree bucket, decides whether this difference matters. If it does not, we will report the phantom median as one well-motivated member of a broader family, not as uniquely right.
Why not just prune suspicious edges with common-neighbor counts or a learned mask? CAGCN's common-neighbor ratio is near zero for every edge of a low-degree node, so it cannot separate genuine sparse interactions from fake ones. A coordinated attacker can also manufacture shared neighbors to pass the check. CGI's learned mask is trained against random corruption and adds substantial training cost. Our adaptive attacks, which are crafted against each pruner's scoring rule, test whether either holds up once the attacker knows the defense.
Why not just drop aggregation and serve plain MF? That throws away the gains TAG-CF documents. Plain MF is also still poisoned when fake edges are present during training. It is the naive baseline, and the poisoning experiment shows how much protection it actually provides.
Proposed Experiments
Datasets and noise. We use Yelp2018, Gowalla, Amazon-Book, and MovieLens-1M with the TAG-CF configurations. We first report clean Recall@20 and NDCG@20. We then follow the SGL and CGI protocol of 5–20% random fake edges.
Strategic attack. We inject up to $k$ Sybil users per target item. Each co-interacts with the target and with popular items of a chosen cohort, and is optimized as a best response against linear aggregation. We repeat this with attacks adapted to each defense, including an attacker who knows the phantom placement. Metrics are the target item's hit rate in cohort top-20 lists, as a function of $k$, and the fraction of users whose top-20 list is certified stable at $k = 1, 5, 20$.
Decisive checks. There are three:
- Whether exposure gain per fake edge falls well below that of every denoiser, while clean accuracy holds.
- Whether the advantage over the trimmed mean is concentrated in low-degree users, as the phantom argument predicts.
- Whether attacks injected before training, rather than after, erase the advantage.
The third check would show that test-time robustness alone is insufficient, and that a training-side component is needed.
References
- How Does Message Passing Improve Collaborative Filtering?
- The Capacity Constrained Facility Location Problem
- Strategic Facility Location via Predictions
- Median activation functions for graph neural networks
- Dynamic Online Recommendation for Two-Sided Market with Bayesian Incentive Compatibility
- Collaboration-Aware Graph Convolutional Network for Recommender Systems
- Contrastive Graph Structure Learning via Information Bottleneck for Recommendation
- Self-supervised Graph Learning for Recommendation
- LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation