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

Abstract

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 ($\mathcal{O}(K^2)$), GNRR achieves $\mathcal{O}(c\cdot 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. Code to reproduce our experiment is available at https://github.com/difra100/Graph-Neural-Re-Ranking-via-Corpus-Graph

Accepted at AIxIA 2026. Author's accepted manuscript. Not the version of record