Many recommender systems have no usable friend or follower network, so they build a substitute: they connect users whose rating or click histories look alike, and then run a graph neural network over those inferred "implicit social" edges. Graph neural networks are models that update each node by averaging over its neighbors. This proposal starts from a simple observation. A user–user graph built from the cosine similarity of interaction histories is, up to normalization, the matrix $RR^\top$, where $R$ is the user-by-item interaction matrix. That is exactly two hops of the user–item graph that the collaborative-filtering backbone already propagates over. Its strongest eigenvectors are the leading singular vectors of $R$, and these are dominated by popularity and broad taste. So the implicit graph mostly adds more averaging along the directions the backbone has already averaged. The predictable result is over-smoothing, where user representations collapse toward a few shared directions as layers are added.
We propose to build the implicit graph from what the backbone cannot see. We first subtract the top-$k$ singular components of $R$, then compute user similarity on what remains. The resulting edges connect users who agree on niche, idiosyncratic items rather than on the head of the catalogue. Our claim is that this residual graph slows the collapse in the dimensionality of user embeddings as depth grows, and gives better ranking accuracy than a raw similarity graph with the same number of edges. We will test the collapse claim with rank-based measures of over-smoothing, not with energy measures that are known to miss it.
Core Claim
Let $R_k = U_k \Sigma_k V_k^\top$ be the best rank-$k$ approximation of the interaction matrix. Let $\tilde R = R - R_k$ be the residual, with rows renormalized per user. The residual implicit graph links each user to its top-$m$ neighbors under cosine similarity of the rows of $\tilde R$:
$$ A^{\text{res}}_{uv} = \mathbb{1}\left[v \in \text{top-}m_{v'} \cos(\tilde r_u, \tilde r_{v'})\right]. $$
The raw implicit graph uses the same rule on the rows of $R$. We make three claims. The first is that the leading eigenvectors of the raw graph align closely with the top singular vectors of $R$, which LightGCN-style propagation on the user–item graph already amplifies. Measured by principal angles, that alignment should be much weaker for the residual graph. The second is that, under message passing on the union of the user–item graph and the implicit graph, the effective rank of user embeddings decays more slowly with depth for the residual graph than for the raw graph. Effective rank is an entropy-based count of how many directions an embedding matrix really uses. The third is that this slower decay translates into ranking accuracy that holds up at depth, at matched edge density.
The mechanism is a graph-construction choice, not a new layer. That makes the claim easy to falsify. If a raw similarity graph combined with an embedding-rank penalty, or a popularity-debiased similarity graph, does just as well, the claim fails.
Relation to Prior Work
Three lines of work build implicit user or item graphs from behavior, and none asks what those edges do to over-smoothing. Recommender System Using Implicit Social Information induces a user network from rating similarity and shows it can nearly match explicit trust networks. This motivates the zero-explicit-link setting. Graph Neural Networks with Dynamic and Static Representations for Social Recommendation adds a cosine-thresholded item graph. SGNNRec mines Apriori co-occurrence rules to create implicit trust edges. Both use shallow aggregation and never examine depth. Generating Reliable Friends via Adversarial Training (RSGAN) learns friend distributions rewarded purely by a ranking loss. All of these choose edges by similarity or by utility. We choose edges by their complementarity to the backbone's own spectrum.
Two lines of work remove edges instead. Graph Bottlenecked Social Recommendation (GBSR) prunes a given social graph with an information-bottleneck objective. It also reports that naive social edges can make LightGCN worse, which is direct evidence of the problem we target. Spectral Graph Pruning Against Over-Squashing and Over-Smoothing deletes edges to enlarge the spectral gap of the normalized Laplacian and slows energy decay. Both methods take a graph as given and decide what to drop. We change what gets built in the first place, and we use both methods as baselines applied to the raw implicit graph.
Our measurement methodology comes from Are we measuring oversmoothing in graph neural networks correctly?. That paper shows Dirichlet energy stays flat while accuracy collapses by around ten layers, and that effective rank tracks accuracy, with a reported average Pearson correlation of 0.91 on node-classification benchmarks. The same paper constrains our claims. High rank is necessary but not sufficient, since random noise has full rank. We therefore never report rank without accuracy, and we treat a residual graph that raises rank but lowers accuracy as a failure.
The gated aggregation of When Do GNNs Work and the high-pass channel of Complete the Missing Half fight smoothing inside the network. Our proposal is the graph-side analogue of the high-pass idea. The residual graph routes messages along the non-dominant part of the interaction spectrum, without changing the aggregator.
Research Program
The work has three parts. The first is diagnostic. On each dataset we build the raw cosine implicit graph and compute the principal angles between its top eigenvectors and the top singular vectors of $R$. We then train LightGCN on the user–item graph alone and on the user–item graph plus the implicit graph, sweeping depth from 1 to 8 layers. At each layer we record effective rank and numerical rank of the user embedding matrix. Numerical rank is the squared Frobenius norm divided by the squared spectral norm. The hypothesis predicts strong eigenvector alignment for the raw graph, and a faster drop in effective rank when the raw graph is added.
The second part is construction. We build the residual graph for $k$ in a small grid, roughly 1 to 64. We tie $k$ to the effective rank of the backbone's own trained embeddings, as a principled default: remove the directions the backbone already uses. Edge count per user, $m$, is matched exactly to the raw graph so that density cannot explain any difference.
The third part asks what the residual edges are. On datasets that do have explicit trust links (Ciao, Epinions, Douban, Yelp, LastFM), we hide those links during training. We then measure what fraction of residual edges versus raw edges coincide with declared ties. RSGAN's observation that only a minority of explicit links reflect real taste alignment means this is a descriptive check, not a target.
We also expect one honest risk. Cold-start users have nearly empty residual rows, so their residual similarities will be noisy. We will report results separately for users with fewer than ten interactions. For these users we test a fallback that mixes in raw-graph neighbors.
Baselines
The naive reference is LightGCN on the user–item graph with no implicit edges, at its best depth. GBSR's observation that LightGCN often beats poorly built social models makes this the bar that any implicit graph must clear first.
The second reference is LightGCN plus the raw cosine top-$m$ graph. This is the standard construction used, in item form, by GNN-DSR. It is the direct ablation of our single ingredient: the two graphs differ only in subtracting $R_k$ before computing similarity.
The strongest existing competitor is GBSR run on the raw implicit graph instead of an explicit one. GBSR learns which social edges to keep under an information bottleneck and reports a 17.06% NDCG@20 gain over its strongest baseline on Douban-Book. The file gives only this relative figure. No absolute NDCG@20 value for GBSR or its backbone was found on Lacuna, so we will reproduce LightGCN-S and GBSR ourselves on every dataset.
We also run PROXYDELETE spectral pruning on the raw implicit graph, at the edge budget that matches residual-graph density. On Roman-Empire it lifted GCN accuracy from about 70% to about 78%, but it has not been tested on recommendation graphs. The adversarial baseline is RSGAN's friend generator. Its reported gain is over 11% relative in NDCG@10 across Douban, Epinions and LastFM; no per-dataset absolute number was found on Lacuna.
All methods share the LightGCN backbone where applicable, the same embedding size, the same training splits, the same early-stopping rule, and the same hyperparameter search budget of 30 trials each. The residual method's $k$ and $m$ count against its own budget.
Beating the strongest baseline means two things. At the best tuned depth, the residual graph must exceed GBSR-on-raw-graph in NDCG@20 and Recall@20 on at least four of five datasets, with paired significance over five seeds. At depth 6 and beyond, it must retain clearly more of its best-depth accuracy.
Why not just…?
Why not just skip the implicit graph and use LightGCN? This is the most likely outcome if the raw graph is all one builds, and GBSR's own analysis supports that worry. Our diagnostic predicts exactly why: the raw graph is redundant with two-hop propagation. The question is whether non-redundant edges help. The naive baseline settles it directly. If the residual graph does not beat plain LightGCN, the proposal fails.
Why not just keep the GNN at two layers? At two layers smoothing is mild, and the residual graph might give no advantage there. We will report the shallow regime honestly. GAIPSRec's ablation showed that paths of length two to four beat 1-hop neighbors on Ciao, with a reported 3.28% MAE gain over the best baseline. That suggests longer reach matters, but not that very deep stacks matter. Our claim therefore has two parts. The residual graph should help at the best tuned depth because its edges carry new information, and at greater depth because it collapses more slowly. If it helps only at depth and loses at the best depth, the result is of limited practical value and we will say so.
Why not just add an embedding-rank or decorrelation penalty and keep the raw graph? This is the real threat. It attacks the same symptom without changing the graph. Rank-collapse results also show that attention alone does not prevent collapse, so a penalty is the natural fix. We include LightGCN plus raw graph plus an effective-rank penalty on user embeddings, tuned over the same budget. If it matches the residual graph, then the graph construction is not what matters and we will report that.
Why not just debias similarity for popularity? Removing only the first singular component is close to popularity debiasing, for example by down-weighting popular items. The $k=1$ setting of our method is that alternative, so the $k$-sweep shows whether removing more than popularity matters.
Proposed Experiments
We use Ciao, Epinions, Douban-Book, Yelp and LastFM, with explicit social links withheld. We use leave-out ranking evaluation with NDCG@20 and Recall@20, plus per-layer effective and numerical rank of user embeddings.
The first decisive check is mechanistic. The raw graph's top eigenvectors should show small principal angles to the top singular vectors of $R$, and the residual graph's should not. If both graphs align equally, the premise is wrong.
The second check is the depth sweep from 1 to 8 layers at matched density. The residual graph should show a slower fall in effective rank and in NDCG@20 than the raw graph. Following the rank-collapse paper's caution, we also report the correlation between effective rank and NDCG across depths, to test whether that correlation transfers to recommendation.
The third check is the comparison against the rank penalty and the $k=1$ popularity-debiasing setting. It separates "a better graph" from "any rank regularizer."
The fourth check is the cold-start breakdown, with and without the raw-graph fallback.
Compute is modest. The truncated decomposition and kNN search run once per dataset at the scale reported in the file, from a few thousand users up to Yelp's 99k.
References
- Recommender System Using Implicit Social Information
- Graph Neural Networks with Dynamic and Static Representations for Social Recommendation
- SGNNRec: A Scalable Double-Layer Attention-Based Graph Neural Network Recommendation Model
- Generating Reliable Friends via Adversarial Training to Improve Social Recommendation
- Graph Bottlenecked Social Recommendation
- Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
- Are we measuring oversmoothing in graph neural networks correctly?
- When Do GNNs Work: Understanding and Improving Neighborhood Aggregation
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks