Cross-Document Neural Re-Ranking via Query-Induced Subgraphs

Neural re-rankers typically score query-document pairs independently, neglecting cross-document context within the retrieved candidate set. We propose Graph Neural Re-Ranking (GNRR), a framework that extracts a sparse, query-induced subgraph from a pre-computed semantic corpus graph and applies Graph Neural Networks (GNN) to propagate cross-document signals. Unlike self-attention re-rankers, which scale quadratically with the number of candidates (O(K2)), GNRR achieves O(c⋅K) online complexity, where c is the fixed corpus graph degree and K the candidate set size. We evaluate five GNN operators within this framework and find that architecture choice substantially affects generalization to harder queries: the GCN variant is the only one that consistently improves over TCT-ColBERT across all three TREC benchmarks. On TREC-DLHard, the most challenging evaluation benchmark, GNRR achieves +5.2% relative AP over TCT-ColBERT and +9.0% AP over a self-attention re-ranker. Notably, self-attention re-ranking degrades AP on DLHard (−3.5% versus TCT-ColBERT), suggesting that sparse corpus-graph structure provides a complementary re-ranking signal that dense self-attention fails to capture. Efficiency analysis shows that GNN models require fewer parameters and lower per-query latency at K=1000 than self-attention, with linear rather than quadratic scaling in candidate set size.