The pose graph is a core component of Structure-from-Motion (SfM), where images act as nodes and edges encode relative poses. Since geometric verification is expensive, SfM pipelines restrict the pose graph to a sparse set of candidate edges, making initialization critical. Existing methods rely on image retrieval to connect each image to its k nearest neighbors, treating pairs independently and ignoring global consistency. We address this limitation through the concept of edge prioritization, ranking candidate edges by their utility for SfM. Our approach has three components: (1) a GNN trained with SfM-derived supervision to predict globally consistent edge reliability; (2) multi-minimal-spanning-tree-based pose graph construction guided by these ranks; and (3) connectivity-aware score modulation that reinforces weak regions and reduces graph diameter. This globally informed initialization yields more reliable and compact pose graphs, improving reconstruction accuracy in sparse and high-speed settings and outperforming SOTA retrieval methods on ambiguous scenes. The ode and trained models are available at https://github.com/weitong8591/global_edge_prior.
Figures & tables
Figure 1: Given a set of input image pairs ( left ), our method ranks all candidate edges by global matchability ( middle ) and constructs a compact, well-connected pose graph via multi-MST selection ( right ). The resulting initialization enables accurate and stable 3D reconstruction, even under sparse or ambiguous settings.
Figure 2: Overall pipeline. Input images are first encoded using a fine-tuned image encoder (DINOv2 backbone with SALAD aggregation). A complete graph is then constructed over image embeddings and processed by our GNN–MLP model to predict global edge ranks. During training, these predictions are supervised using geometry-derived ranking signals via a differentiable ranking loss. At inference, the predicted ranks guide the construction of multiple minimum spanning trees, whose union forms the initial pose graph. Incremental SfM is finally applied on this graph to recover the sparse 3D reconstruction.
Figure 3: COLMAP reconstruction [ 42 ] performance using pose graphs constructed from multiple MSTs guided by baseline embedding similarities or our learned global edge ranks. Top row: Relative pose accuracy on IMC23-PhotoTourism [ 21 ] ([email protected] ∘ , left; AUC@5 ∘ , middle) and on MegaDepth [ 30 ] (AUC@5 ∘ , right) as the number of MSTs k increases. Bottom row: Percentage of registered cameras on PhotoTourism (left), AUC@5 ∘ versus COLMAP runtime on PhotoTourism (middle), and percentage of accurately reconstructed cameras on VisymScenes [ 50 ] (right). Across all benchmarks, our method consistently achieves the highest accuracy, particularly in the sparse regime ( k=1 – 2 ), while maintaining competitive or superior reconstruction efficiency.
Method
Config
AUC@5 ∘↑
Time (min) ↓
k MSTs
→
2
3
5
5
MegaLoc
w/o modul.
60.2
64.8
70.5
1 7.3
w/ o modul.
64.1
65.3
74.7
14.1
DG++
64.2
64.9
68.4
1 8.6
Ours
w/o modul.
61.9
65.8
71.7
1 5.7
w/ o modul.
66.0
71.5
75.6
13.3
Table 1: Ablation of connectivity-aware score modulation on VisymScenes [ 50 ] . We report AUC@5 ∘ for pose graphs built from MegaLoc similarities and from our predicted global edge ranks, with and without modulation, as well as with DoppelGanger++ filtering. Modulation consistently improves accuracy for both methods, especially in the sparse regime ( k=2 – 3 ). COLMAP mapping time at k=5 is shown in minutes.
Figure 4: Edge selection strategies for pose graph initialization. We report COLMAP [ 42 ] relative pose AUC@5 ∘ on IMC23-PhotoTourism [ 21 ] ( left ) and MegaDepth [ 30 ] ( middle ) when using either k NN or the proposed k minimal spanning tree approach (MSTs) for graph construction. Oracle ∗ curves correspond to ground-truth rankings from SfM-derived geometry. The percentage of successfully registered cameras on PhotoTourism is shown on the right. MST-based selection yields substantially stronger connectivity and higher accuracy than k NN, and closely follows the oracle behavior across all k s.
Variant
AUC@5 ∘↑
k MSTs →
1
2
3
5
Ours w/ SALAD backbone
61.2
71.0
72.4
73.4
Ours w/o GNN
55.4
70.4
72.3
72.3
Ours
64.2
71.7
72.6
73.5
Oracle-RANSAC inliers
65.7
72.4
73.0
74.1
Oracle-3D inliers
65.4
72.1
73.5
74.3
Table 2: Ablation study on PhotoTourism evaluating different components of our method. We evaluate by using the weaker SALAD backbone and the removal of the GNN. The last three rows report oracle rankings derived directly from geometric signals (RANSAC inliers, 3D point overlap, or their combination), illustrating the relative strength of each supervision source. AUC@5 ∘ scores reported.
Modul.
Top-5
Normalized
AUC@5 ∘↑
candidates
dist.
k→ 2
3
5
×
×
×
61.9
65.8
71.7
×
✓
×
61.4
66.9
64.8
✓
×
×
63.5
64.7
68.9
✓
✓
×
63.7
65.5
68.3
×
✓
✓
60.3
67.3
67.1
Table 3: Ablation of the proposed connectivity-aware score modulation on VisymScenes. We evaluate three components: (i) whether modulation is applied, (ii) whether only the top-5 candidate edges per image are updated after each MST, and (iii) whether graph distances are normalized before modulation. Reported metrics are AUC@5 ∘ for pose graph initialization using k=2,3,5 MSTs. The best configuration combines modulation with normalized distances, yielding the strongest performance across all settings.