ClusterGNN: Cluster-based Coarse-to-Fine Graph Neural Network for Efficient Feature Matching

1. Introduction

• Feature correspondences support applications including SLAM, Structure-from-Motion, and camera pose estimation.Classical nearest-neighbor pipelines use descriptor similarity but ignore geometric information and the global receptive field.Source: §1 · p. 1
• Complete-graph attention has quadratic complexity in the number of keypoints, many of which are irrelevant or weakly correlated for matching.The introduction notes that self- and cross-attention can be sparse, making dense message passing redundant.Source: §1 · p. 1
• ClusterGNN learns coarse-to-fine clusters that form local graphs, so each point attends only within its local graph.This is presented as a way to reduce redundant connectivity while retaining self- and cross-attention for feature matching.Source: §1 · p. 2
• 59.7% lower runtime and 58.4% lower memory consumption on dense detection are reported versus SuperGlue.The method also reports state-of-the-art results across various tasks.Source: §1 · p. 2

2. Related Work

• Classical pipelines match descriptors by nearest neighbors and filter incorrect matches, while SuperGlue uses attentional GNN message passing on complete graphs within and between images.Complete-graph attention has quadratic runtime and memory complexity, limiting scalability with many points.Source: §2 · p. 2
• Efficient-attention approaches use fixed local or strided patterns, seeds, pooling, or low-rank approximations, but these assumptions may not suit irregular keypoints and cross-image matching.Fixed neighborhoods can limit long-range interactions, and the cited approximations are described as less appropriate for feature matching.Source: §2 · p. 2
• ClusterGNN draws on content-based sparse attention to cluster tokens and pass messages within local subgraphs.Its architecture initializes complete inter- and intra-image graphs, then hierarchically partitions them before attention updates and matching.Source: §2 · pp. 2–3, Figure 2 · p. 3

3.1. Problem Definition

• Feature matching is defined as pairing keypoints from two images that match in real-world coordinates.The problem is specified for image pairs with keypoints, confidence scores, and descriptors.Source: §3.1 · p. 3
• Large camera-view differences and long-term environmental changes can lead nearest-neighbor methods to produce wrong matches.The passage contrasts this with GNN attention that iteratively removes matching-unrelated noise and learns global geometric information.Source: §3.1 · p. 3

3.2. Motivation

• Many keypoints are non-repeatable or irrelevant, and self- and cross-attention matrices tend to be sparse, with most values near zero.These observations motivate sparse structures for efficient feature matching.Source: §3.2 · p. 3
• ClusterGNN groups strongly correlated points into local subgraphs for attention updates, then uses coarse-to-fine clustering to address erroneous grouping within an image.The passage notes that direct classification across images may place points from the same image in the wrong cluster.Source: §3.2 · p. 3

3.3. Network Architecture

• ClusterGNN initializes complete intra- and inter-image graphs, applies cluster-based attention updates, then computes matching probabilities from updated features.The matching module uses dot products, a learnable dustbin channel for unmatched keypoints, and dual-softmax probabilities.Source: §3.3 · pp. 3–4, §3.3.3 · p. 5

3.3.1 Complete Graph Initialization Module

• Encoded keypoints, confidence scores, and descriptors form joint representations that initialize complete within-image and between-image graphs for attention-based updates.The module uses multi-head attention; its GNN layers pass and aggregate messages between nodes.Source: §3.3.1 · p. 4

3.3.2 Cluster GNN Module

• Cluster-based sparse attention approximates complete-graph self- and cross-attention by updating features within local subgraphs.Queries and keys from both images are united, and a cluster matrix groups query–key pairs assigned to the same cluster.Source: §3.3.2 · p. 4
• The learnable clustering uses query/key attention similarity to assign features to cluster centers and construct the cluster matrix.Training initializes centers with k-means and updates them using a weight β set to 0.99; at test time, trained centers cluster input features directly.Source: §3.3.2 · pp. 4–5
• O(n^2/k) attention complexity trades approximation quality against computation, with k = √n described as a theoretical balance for features from one image.Because matching features from two images may have different statistics, a fixed √n can over-segment clusters; ClusterGNN instead increases cluster counts for coarse-to-fine grouping.Source: §3.3.2 · p. 5

3.3.3 Matching Module

• The matching module scores updated features by dot product, adds a learnable dustbin channel for unmatched keypoints, and applies dual-softmax before mutual-check prediction.At test time, matches are predicted with argmax and a mutual check.Source: §3.3.3 · p. 5

3.4. Loss

• Ground-truth matches and non-matching keypoints are supervised with cross-projection error, using thresholds below 3 pixels for matches and above 5 pixels for non-matches.Source: §3.4 · pp. 5–6
• A clustering loss is introduced to improve clustering and enable semi-supervision.Source: §3.4 · p. 6
• The total loss combines matching loss with clustering losses computed across clustering stages, balancing the two with γ = 0.1.Source: §3.4 · p. 6

3.5. Implementation Details

• Training uses MegaDepth, a dataset with 1M internet images from 196 locations, sparse COLMAP 3D models, and multi-view-stereo depth maps.Training pairs are selected by SfM co-visibility overlap, and images are resized so the larger edge is 1600 pixels.Source: §3.5 · p. 6
• The implementation uses four-head attention, three initialization GNN layers, and four ClusterGNN stages with 16, 32, 64, and 128 clusters.Each cluster stage has two cluster-based GNN attention layers; query vectors in the initialization module are chunked into four parts to reduce GPU memory cost.Source: §3.5 · p. 6

4.1. Pose Estimation

• ClusterGNN outperforms other methods with ASLFeat on pose estimation, slightly degrades against some baselines with other features, and yields more true matches.The reported comparisons cover SIFT, ASLFeat, and SuperPoint features.Source: §4.1 · p. 6, Table 1 · p. 7

4.2. Homography Estimation

• ClusterGNN achieves competitive homography-estimation performance, with a slight improvement over SuperGlue and SGMNet.Source: §4.2 · p. 6, Table 2 · p. 7

4.3. Visual localization

• ClusterGNN achieves competitive performance against SuperGlue on indoor and outdoor visual localization across different features.Source: §4.3 · p. 7, Table 3 · p. 8, Table 4 · p. 8

4.4. Efficiency

• With dual softmax on 10k keypoints under dense detection, ClusterGNN reduces runtime by 59.7% versus SuperGlue and memory by 58.4%; SGMNet is more time-efficient, while ClusterGNN achieves better memory efficiency and performance.Source: §4.4 · p. 8

4.5. Ablation Study

• Varying cluster counts avoids the significant performance drop seen with fixed counts, while dual softmax achieves competitive performance to Sinkhorn.Fixed-count settings tested were 16, 32, 64, and 128 clusters; dual softmax is non-iterative.Source: §4.5 · p. 8

• ClusterGNN uses learned coarse-to-fine clustering to dynamically construct local subgraphs, achieving competitive performance while reducing runtime by 59.7% and memory by 58.4%.Source: §5 · p. 8