View PDF HTML (experimental)

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 this https URL

Submission history

From: Christian Giannetti [view email]
[v1] Mon, 17 Jun 2024 16:38:19 UTC (299 KB)
[v2] Mon, 14 Sep 2026 16:02:56 UTC (1,922 KB)