PointTruss: K-Truss for Point Cloud Registration
Authors: Yue Wu
Jun Jiang
Yongzhe Yuan
Maoguo Gong
Qiguang Miao
Hao Li
Mingyang Zhang
Wenping Ma
Venue: NeurIPS 2025 poster ()
Keywords: Point cloud registration; compatibility graph; outlier removal; k-truss; correspondence selection
Primary area: general_machine_learning

Abstract: Point cloud registration is a fundamental task in 3D computer vision. Recent advances have shown that graph-based methods are effective for outlier rejection in this context. However, existing clique-based methods impose overly strict constraints and are NP-hard, making it difficult to achieve both robustness and efficiency. While the k-core reduces computational complexity, which only considers node degree and ignores higher-order topological structures such as triangles, limiting its effectiveness in complex scenarios. To overcome these limitations, we introduce the $k$-truss from graph theory into point cloud registration, leveraging triangle support as a constraint for inlier selection. We further propose a consensus voting-based low-scale sampling strategy to efficiently extract the structural skeleton of the point cloud prior to $k$-truss decomposition. Additionally, we design a spatial distribution score that balances coverage and uniformity of inliers, preventing selections that concentrate on sparse local clusters. Extensive experiments on KITTI, 3DMatch, and 3DLoMatch demonstrate that our method consistently outperforms both traditional and learning-based approaches in various indoor and outdoor scenarios, achieving state-of-the-art results.

PointTruss: K-Truss for Point Cloud Registration
Yue Wu
Jun Jiang 1.2
Yongzhe Yuan 1.2
Maoguo Gong
133,5
Qiguang Mi Hao Lits
Mingyang Zhang!. 'MoE Key Lab Collaborative Intelligence Systems, Xidian University
Wenping Ma*
"School of Computer Science and Technology, Xidian University
Schooo of Electronic Engineering, Xidian University
"School of Artificial Intelligence, Xidian University
Academy of AI, College of Mathematics Science, Inner Mongolia Normal University Lywu, qgmiao, haoli, myzhang, wpma) @xidian....... edw.diidin.d...deeee.o...uuuu..d edu. cn, gong@ieee. org, xiaolongfanBoutloo... com, {junj, yyz) xidian edu. cn
Abstract
Point cloud registration fundamental task 3D computer vision. Recent advances have shown that graph-based methods are effective for outlier rejec- tion in this context. However, existing clique-based methods impose overly strict constraints and are NP-hard, making it difficult to achieve both robustness and efficiency. While the k-core reduces computational complexity, which only consid- ers node degree and ignores higher-order topological structures such as triangles, limiting its effectiveness in complex scenarios. To overcome these limitations, we introduce the f--truss from graph theory into point cloud registration, leveraging triangle support as a constraint for inlier selection. We further propose a consen- sus voting-based low-scale sampling strategy efficiently extract the structural skeleton of the point cloud prior to k-truss decomposition. Additionally, we design spatial distribution score that balances coverage and uniformity of inliers, pre- venting selections that concentrate on sparse local clusters. Extensive experiments KITTI, 3DMatch, and 3DLoMatch demonstrate that our method consistently outperforms both traditional and learning-base baased approaches in various indoor and outdoor scenarios, achieving state-of-the-ard results.
Introduction
Point cloud registration is a fundamental problem 3D computer vision 4$ 29
remote sensing [19
[2]. 3D reconstruction [1) and autonomous driving [50] Its primary goal is to estimate the optimal rigid transformation matrix that precisely aligns two point clouds. Accurate 3D correspondences form the foundation of point cloud registration. High-quality correspondences enable the correct computation of rotation and translation, and their quality directly affects the final registration accuracy.
Recent works 48
demonstrate the effectiveness of graph theory for correspondences se- a graph, vertices represent matched point pairs, and
lection in point cloud registration. edges encode geometric compatibility, which are added when two correspondences meet pre- set threshold [30] Based on this representation, several graph algorithms have been devel- oped to select reliable correspondences. The classical maximal clique approach [49 37 seeks reliable matches by finding fully connected subgraphs, ensuring strong geometric consistency but facing two major challenges. The strict connectivity is often unachievable due to noise or occlusion, resulting in the loss of correct matches. Maximal clique search is NP-hard
13 making it impractical for large-scale data. The k-core method [35] 32 relaxes connec-
"Corresoondigg author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

tivity requirements and reduces computation, but its weak constraints compromise correspon- dences reliability, which highlights the difficulty in balancing structural robustness and efficiency. To address these limitations, we introduce the k-truss concept from community detection [47 26 into point cloud registra- tion. A k-truss [9] requires each edge to participate in at least k-2 triangles, leveraging the rigidity and invariance of triangles. Tri- angles derive their strength from their stable structure, serving the simplest rigid planar formation and preserving their geometric properties regardless of rotation translation. In real-world data, inlier correspondences naturally form triangle-rich clusters, as shown in Fig. | making k-truss decomposition effective for pre- serving reliable matches while filtering outliers. Our method first uses consensus voting for low-scale sampling, then constructs compatibility graph and applies k-truss decomposition. For each resulting subgraph, we estimate the transformation via weighted SVD 7 and rank candidates using spatial distribution score, selecting the transformation with the highest score as the final result.
Graph Construction
Figure 1: Triangular structure as inlier indicator. Inlier corre- spondences (green) form triangle- rich structures, while outliers (red) lack triangular support.
To our knowledge. this is the first work to introduce k-truss into point cloud registration, establishing a robust correspondences selection framework based on triangle constraints. Inspired by k- truss, we propose a heuristic method that leverages triangle-basee based truss structures to robustly filter and refine correspondences. Ex- perimental results show that our method achieves excellent performance under high noise and outlier ratios. Meanwhile, it maintains polynomial time complexity and demonstrates high computational efficiency among graph-based methods. Extensive evaluations on standard datasets further demon- strate that our method significantly outperforms existing state-of-the-art approaches in registration accuracy. Our main contributions are summarized as follows:
We propose novel correspondence selection method called PointTruss. It uses triangle support constraints to effectively filter out mismatches related to isolated and low-support edges.
We develop integrated pipeline. It applies consensus- vootnng low-scale sampling to extract the structural skeleton, k-truss decomposition to preserve triangle-supporre inliers, and spatial distribution scoring to favor broad, uniform coverage. Each component is modular and can be used independently.
Extensive experiments on KITTI, 3DMatch, and 3Dth show that PointTruss consistently outperforms both traditional and learning-basee methods across diverse indoor and outdoor sce- narios. It achieves state-of ootte-of-hh-artt tht-her-tttt accuracy and efficiency with polynomial -ime complexity and strong robustness to noise and outliers.
2 Related Work
Traditional Point Cloud Registration. RANSAC and its variants 14 iteratively sample from the initial correspondence set to find the largest consensus set. Early handcrafted feature descriptors, such as FPFH 31. extract local features by encoding geometric histograms. FGR [5] estimates the optimal transformation using robust estimators like the Geman-McClure loss. Branch-and-bound
(BnB) based optimization methods, such as GORE 3 and its variant QGORE (25). perform global search in the parameter space to obtain the best transformation. Voting based method (40] select reliable correspondences through a scoring mechanism. Some works tackle registration with high outlier rates and non-convex objectives via robust and global search, mitigating local minima and
improving convergence 28 34). However, these methods often suffer from low computational efficiency and limited accuracy under high outlier ratios.
Learning-based Point Cloud Registration. Current learning-bas -ased point cloud registration ap- proaches can be categorized as follows. The first category focuses on detecting reliable keypoints or extracting more discrininative features 229 41 For example, FCGF uses a fully convolutional network to extract point cloud features in single pass, without separate keypoint detection. Another category aims to distinguish inliers from outliers. PointDSC ( removes outliers using pairwise spatial compatibility supervision, while VBReg [20] introduces variational non-local networks for

---

outlier rejection. There are also end-to-end approaches 42 such as Deep Global Registration (DGR)
7 which employs sparse convolution and point-wise MLPs classify correspondences. Although these methods perform well in specific scenarios [4], they generally require large amounts of train- ing data and have limited generalization ability. In contrast, training-free graph-based registration methods often exhibit better robustness and can be integrated as auxiliary modules in deep learning frameworks to further improve overall performance.
Graph-based Point Cloud Registration. Graph-based algorithms 30 typically construct a compat- ibility graph by evaluating the pairwise compatibility correspondences, which enables efficient removal of large number of outliers. For example, the TEASER [39 employs maximal clique theory to decouple scale, rotation, and translation estimation. ROBIN [32 theory for outlier pruning. SUCOFT [35] introduces the concept of k-supercore to improve outlier rejection effectiveness. SC2-PCR SS] imposes stricter constraints on correspondences by introducing second-order spatial compatibility metric. MAC [48] first proposes a maximal clique-based method to mine richer local consistency information, while FastMAC [49] accelerates computation by applying random spectral sampling the correspondence graph. These methods demonstrate that mining key information in the compatibility graph crucial for improving the robustness and accuracy of point cloud registration.
uses the maximal k-core
Ispst Carcepoodonee
scale sampling
Goaph Comernction
è-Trus Dreompacittn and tramfermation Goneration
Ourpae Transferrattion
Tranicla2,00)
TrusteS.luu))
82,
R1.0
Crmpaliiiy Creabisn Sorr
Trusle5,77.9)
R4.14
IrosicleluSddd))
HK,
B7.7
Pipeline of our method. Starting from input correspondences, perform low-scale sampling to reduce redundancy. 2. Constructing a correspondence graph and apply k-truss decompo- sition to identify subgraphs with varying levels of triangle support (i.e., different h values). 3. Each k-truss subgraph represents a set of correspondences with a specific degree of structural consistency. Based these subgraphs, generate multiple transformation hypotheses and select the optimal transformation using the spatial distribution score.
Figure 2:
3 Methods
3.1 Problem Formulation
For two point clouds, where the source point cloud is defined as P (p: E | i. .N and the target point cloud as Q = {q, E R i I,..., M). the goal of point cloud registration is to estimate the rigid transformation T {R, t} that aligns these point clouds. Here, R E SO
represents the rotation matrix, and t E IR3 represents the translation vector. The optimization problem can be formulated as:
min Σ (P..q:ECC
RRp: + t - 1:112
where C= ii= 1l, No) is the initial correspondence set obtained through feature matching, with each correspondence c₁ (P:, q:).
We extract either geometric or learned local features from the point clouds, use feature matching to generate C, and apply the k-truss method extract the optimal subgraph. This subgraph then used to estimate the six degrees of freedom (6-DoF) pose transformation between P and Q. The overall pipeline is illustrated Fig. and the PointTruss is both simple and efficient.
3.2 Graph Construction
The graph space can more accurately capture the affinity relationships between correspondences than Euclidean space (5). Therefore, represent the initial correspondences compatibility
3

---

graph, where each node denotes a correspondence and edges connect nodes that are geometrically compatible [ 23
30 48].
The graph constructed using the rigid distance constraint between correspondence pairs (c,, Cy), which is quantitatively measured as:
(a Cj) = - Pjí || gilll S 2T,
is the distance threshold, is typically set to 3.5 based statistical confidence inter- vals, and o is the standard deviation of noise, which controls the sensitivity to distance discrepancies. This constraint ensures that the distance between point pairs remains nearly invariant under rigid transformations.
where
The compatibility consistency score between and Cj is defined as:
S Comp Cÿ) = exp (- Sdist (Cs; C2)²
20²
If Scomp c,) exceeds threshold Tcomps an edge eij is formed between c, and cy. The weight of the edge is Scomp(C,: Cy)) Otherwise, Scomp (c,, cý) is set zero.
3.3 Consensus Voting-based Low-scale Sampling Strategy
To efficiently identify inlier correspondences and reduce the search space, we propose a consensus voting-based low-scale sampling strategy. This method leverages the previously defined geometric consistency metrics to identify the most reliable correspondences.
Consensus Score Computation. Utilizing the compatibility score Scomp defined in Eq. (3) we com- pute the consensus score for each correspondence by counting the number of other correspondences that are geometrically compatible with it:
N Σ [(Sompp(C 0ÿ) Te); j=1
S
where I[(-) is the indicator function and 5. is the consistency threshold. This score represents the number of other correspondences that support correspondence i.
Non-Maximum Suppression. To avoid sampling spatially clustered correspondences, apply
non-maximum suppression 27]
IsLocalMax; min ((S: 2 S;) V (di 2 rnmms),
(5)
JEN
where N the set of all correspondences, d; lpp - pyll2 the Euclidean distance between source points, Tims is the non-maximum suppression radius, and denotes the logical OR operation. A correspondence is considered a local maximum when, for all other correspondences, either its score is higher is spatially distant.
The final score for each correspondence is:
sfinal S₁ IsLooalMMax
(6)
Low-scale Sampling. We select the top- correspondences with the highest final scores, where K determined by:
K = 18 NNJ,
with 3 being the sampling ratio parameter. This sampling strategy ensures that we can select a diverse set geometrically consistent correspondences, significantly reducing the computational cost of subsequent operations while maintaining high probability of including correct correspondences.

---

3.4 The k- T-Truss Decomposition
Following the Consensus Voting-based Low-scale Sampling Strategy presented in Sec. we construct new compatibility graph among the selected high-quality correspondences. The adjacency matrix A of this refined graph represents the pairwise geometric consistency relationships established in Sec. 3.2 but now focused on the reduced set of promising correspondences. To further identify structurally consistent subsets, we apply k-truss decomposition to this adjacency matrix.
Definition (k-Truss Decomposition Theory). Given an undirected graph G = EV and an integer & 2 3, the k-truss Gf denoted by (G),,, is defined as the maximal subgraph H (VH, EH) of G where every edge e E Eh is contained in at least (k: 2) triangles within H.
This formal definition captures the essential property that each edge in k-truss must have strong structural support through triangle formations. the context of correspondence graphts triangle represents three correspondences that are mutually consistent, which is stronger constraint than puirwise consistency.
Definition 2. (Triangle Support). For an edge e = (u, E E in a graph = (V, E), the triangle support of denoted by sup(e, G), is defined as the mumber of triangles in G that contain
sup(e, G) = H{ E V {u, v) (u, w) (u, w) E}},
(8)
The triangle support can be efficiently computed using matrix operations. If A is the adjacency matrix of G, then:
sup((u, G) (A?) An,y
where (A²)a,o counts the number of length-2 paths between u and
Theorem 1. Let (pt.P), Pk..P-.Po Pk) denote a triplet of point correspondences, and let A represent the deviation vector of triangle edge lengths between the source and target point clouds. Under rigid transformation with Gaussian noise, for any threshold e O,
P (lIADiie
|/ooreett > P(IADijkllr <E| <c/incorrect).
where P..) denotes the probabilit, LiDkk F denotes the Frobenius norm of the deviation vector, and >> indicates "significantly greater than." " This inequality states that the probability of trian- gle relationships being preserved under rigid transformation is significantly higher for correct correspondences than for incorrect ones.
Therefore, the k-truss, which requires each edge to be supported by at least k - 2 triangles, sig- nificantly enhances robustness in correspondence selection by leveraging higher-order structural consistency.
Please see Appendix A.2 for detailed proof and derivations.
Matrix- Based Implementation. The k-truss decomposition operates on the adjacency matrix derived from the sampled correspondences. The algorithm proceeds by computing the triangle support for each edge:
T = A ④ A,
(10)
where denotes the Hadamard (element-wise) product.
We then identify valid edges that satisfy the k-truss criterion 99:
Evalid = TT (k: 2)),
(11)
For each vertex i, we extract its neighborhood connected by valid edges:
N₁ = {i E V Evatia = 1}.
(12)
Vertices with neighborhoods of sufficient size (W& 2 k) form clusters in the k-truss decomposition.
Computational Complexity Analysis of T-TTruss Decomposition. The k-truss decomposition has a time complexity of (mm I.5). which much more efficient than exponential-time clique-based methods and remains practical for large-scale graphs. For more details, please refer to Appendix A.3
5

---

3.5 Hypothesis Generation and Evaluation
Each k-truss subgraph filtered from the previous step represents structurally robust of correspon- dences. By applying the SVD algorithm to each k-truss subgraph, we can obtain a set of 6-DoF pose hypotheses.
cuntrality-weighher SVD. Transformation estimation of correspondences is implemented using weighted SVD 48
5 7 We assign weights correspondences based their centrality values within the k-truss subgraph. Our weighting scheme follows established graph-based PCR methods by deriving weights from spectral analysis (24). We compute the sigendecomposition of the k-truss subgraph's 's compatibility matrix and use the principal eigenvector elements as correspondence weights in our weighted SVD. This method leverages the structural importance of each correspondence to improve transformation accuracy.
29
The final goal of our method is to estimate the optimal 6-DoF rigid transformation (composed of rotation pose R E SO(3) and translation pose t" E IR3) that maximizes our spatial distribution score function:
(R t²) arg max SDS(P, Q. t), R,t
(13)
where SDS represents our spatial distribution score function defined as:
SDS(P, Q, R,
Pintier
Peoverage Parrors
(14)
with the individual components:
Pinlier
P
(15)
Ide rangca(T)
Peoverage
Naetz.g.2) range,
(16)
Eiez
Rp: +t qill
Perror
(17)
where I {i [Rp; + 7 is the of inlier indices, the inlier threshold, range, computes the coordinate range along dimension d, E P and q: E Q are corresponding points from source and target point clouds.
Unlike conventional metrics such as MAE [48] or inlier count [3] our SDS function comprehensively evaluates both alignment accuracy and spatial distribution quality of inliers. The Pinlier term measures the proportion of correctly aligned points, Pcoverage evaluates how well the inliers span the original point cloud volume, and Perror assesses the precision of alignment among inlier points. This balanced evaluation method effectively prevents selecting transformations with clustered inliers in limited regions and promotes transformations with well-distributed inliers across the entire object. The best hypothesis according to this comprehensive scoring function is selected to perform the final 3D registration.
4 Experiment
4.1 Experimental Setup
Datasets. For outdoor scenarios, we evaluate our method on the KITTI dataset [5] Following the protocol established in [1 48, we select 555 point cloud pairs from sequences 8 to 10 for testing. For indoor environments, we conduct experiments on the 3DMatch dataset (45) and the more challenging 3DthMatch dataset [17, where point cloud pairs have less than 30% overlap. To further assess the robustness and generalization capability of our approach, we also perform experiments on the Bunny model from the Stanford 3D Scanning Repository [10].

---

Evaluation Criteria. We use rotation error (RE). translation error (TE), and registration recall (RR) the main evaluation metrics. Following 4 results the 3DMatch and 3DLoMatch datasets satisfy RE < 15" and TE < 30cm, or on the KITTI dataset R.F I 5 and TE S 60cm. The mean rotation error and mean translation error are computed only on successfully registered pairs. The registration accuracy of a dataset is defined as the ratio of successfully registered pairs to the total number of pairs.
registration is considered successful the
Implementation details. Our method is implemented in PyTorch. For the 3DMatch, 3DLoMatch, and KITTI datasets, we use Fast Point Feature Histograms (FPFH) [3T] and Fully Convolutional Geometric Features (FCGF) 8 as descriptors to generate initial correspondences. Following [4]
39 21), the Bunny model is downsampled to N: points and resized to [0, 1| cube, creating the source point cloud P. To generate the target point cloud Q, random transformation (R, is applied to P and then Gaussian noise 6; ~ (O, o I33) is added. pair of the original and moved points defines an inlier. The inliers are contaminated with outliers generated by random transformations. Detailed computational complexity analysis is provided the Appendix AA.3 All experiments are conducted on an AMD Ryzen 5950X CPU and single NVIDIA RTX 3090 GPU.
-0-
FGI
TEASER4
PSR
TEASETT-4
Rotation Error (dagraass)
18-
-4- PCR
HAASAL
MAC
Cur
RANSAC SCHPOR
MAC
Ours
Transtation Ener (cm)
(56)
Outlier
Rotation Error 99% Outlier Ratio
Translation Error at 99% Outlier Ratio
12
10
Robation Error (degreesa)
Translation Ener (cm)
10"
10*
F3R
RANBAC
SOAPOR
TEADERM
MAC
Cura
FŌR
RANEAC
SCAPOR
TEAGER
MAC
Cura
Figure 3: Outlier robustness evaluation on the synthetic dataset. The first row shows the rotation and translation errors of each method as the outlier ratio on the Bunny model increases from 10% to 90%. The second row compares the rotation and translation errors of different methods at an outlier ratio 99%.
150
-6-
FGR
TEASER+*
FSR
TEASER+
-0
RANSAC
MAC
-8
RANSAC SC'-POR
WAC
Rotetion Error (ingren))
-40
-4-
Sc/-ec
Oura
Transtatoon Eiror (cm)
10'
-
Our
120
10'
8.11
0.00
0.03
0.34
0.50
0.00
3.07
0.03
0.09
16.00
0.02
0.58
0.0c
0.05
0.58
3.07
0.08
005
Nosse
Notse
Figure 4: Noise robustness evaluation on the synthetic dataset. Comparison of rotation and
translation errors on the Bunny model the noise standard deviation increases from 0.01 0.09.

---

4.2 Robustness to Outliers and Noise on Synthetic Data
On the synthetic dataset, conduct experiments using the Bunny model. The outlier ratio is varied from 10% to 90% to systematically evaluate the robustness of each method under high outlier rates. The Bunny model is downsampled to Nº 500 and Gaussian noise with zero mean and standard deviation o = 0.01 added. For each outlier ratio, 100 independent trials are performed, and the mean rotation error (RE) and translation error (TE) are recorded. We also test an extreme case with an outlier ratio of up to 99% (please see Fig. 3 second row). Our method is compared against state-of-the-ae traditional approaches [51
48 Results show that traditional methods such as FGR and RANSAC exhibit rapidly increasing errors as the outlier ratio rises, while our method consistently achieves the best robustness and registration accuracy across all outlier levels.
Table I: Results on KITTI dataset
15
using FPFH 33 and FCGF g descriptors.
FPFH RE(")
FCGF RE(*)
RR(%)T
TB(cm)
RR(%)T
TE(em)
Time(s)
i) Traditional
FGR 5L
5.23
0.86
43.84
89.54
0.46
25.72
3.88
RANSAC 14
74.41
1.55
30.20
80.36
0.73
26.79
5.43
TEASER
91.17
1.03
17.98
95.51
0.33
22.38
0.03
SC PCR
99.46
0.35
7.87
98.02
0.33
20.69
0.31
MAC 48
97.66
0.41
8.61
97.84
0.34
19.34
3.29
TR-DE 4
96.76
0.90
15.63
98.20
0.38
18,00
TEAR 18
99.10
0.39
8.62
Jiang al. 21
99.56
0.34
7.85
98.20
0.32
20.73
0.54
ii) Deep learned
DGR 7
77.12
1.64
33.10
96.90
0.34
21.70
2.29
PSC
98.92
0.38
8.35
97.84
0.33
20.32
0.45
VBReg 20
98.92
0.45
8.41
98.02
0.32
20.91
0.24
Ours
99.64
0.43
5.31
99.10
0.59
11.06
0.21
We further evaluate the robustness each method under different noise levels, as shown in Fig. Specifically, increase the standard deviation of Gaussian noise from 0.01 systematically assess algorithm performance. Experimental results indicate that, as the noise level increases, the translation error of the clique-based MAC 48 method rises significantly, while our trianglebbased method is barely affected. The bundled structure of triangles effectively captures the key skeleton of the point cloud and resists noise interference. As result, our method consistently achieves the lowest rotation and translation errors under high noise conditions, demonstrating superior robustness.
0.1 to
Table 2: Comparison results 3DMatch 45 using FPFH 31 and FCGF g descriptors.
FPFH RE(*)
FCGF RE(")
RR(%)
TE(cm)
RR(%)1
TE(em)
Time(s)
i) Traditional
FGR [51
40.91
4.96
10.25
78.93
2.90
8.41
0.89
RANSAC
66.10
3.95
11.03
91.44
2.69
8.38
2.86
TEASER+ ++ 39
75.48
2.48
7.31
85.71
2.73
8.66
0.03
SC2-PCR 5
83.90
2.12
6.69
93.16
6.53
0.12
MAC 48
83.90
2.11
6.80
93.72
2.07
6.52
5.54
FastMAC 49
82.87
2.15
6.73
92.67
2.00
6.47
0.11
Jiang al. 21
83.92
2.12
6.64
93.28
2.04
6.48
0.36
ii) Deep leamnd
DGR 7
32.84
2.45
7.53
88.85
2.28
7.02
1.53
PS
72.95
2.18
6.45
91.87
2.10
6.54
0.10
VBReg 20
82.57
2.14
6.77
93.53
2.04
6.49
0.20
Ours
84.70
1.80
6.22
93.84
1.70
6.13
0.20

---

4.3 Experimental Results on the KITTI Dataset
We conduct experiments on the KITTI dataset [5] to evaluate the potential of our algorithm in real outdoor scenarios. Table presents the results using FPFH [3]] and FCGF [8] descriptors for initial
correspondence generation. We compare our method with leading traditional [4 39 [ 48 4
18
21 and learning-basel approaches 7 D
20 Following [ 48], the mean rotation error (RE) and
mean translation error (TE) are calculated only on successfully registered pairs. As shown Table [ our method achieves the highest recall (RR) and lowest TE with both FPFH and FCGF descriptors. Moreover, our method demonstrates superior efficiency at comparable registration accuracy. These results confirm the robustness of our method for registering sparse and non-uniform outdoor point clouds. Additional visualizations are provided in the Appendix A.10
Table Comparison results on 3DLoMatch
using FPFH 31 and FCGF descriptors.
FPFH
FCGF
RR(S)
RE(*)
TE(em)
RR(%)
RE(*)
TB(em)
i) Traditional
RANSAC
14
19.83
4.67
10.32
37.60
4.28
11.04
TEASER+
39
35.15
4.38
10.96
46.76
4.12
12.89
SC2-PCR 5
35.93
4,26
10.86
58.73
3.80
10.44
MAC 48
40.88
3.66
2.45
59.85
3.50
9.75
FastMAC
38.46
4.04
10.47
58.23
3.80
10.81
ii Deep learned
PoinDSCC
27.91
4.27
10.45
56.20
3.87
10.48
VBReg 20
30.83
4.38
10.92
58.30
3.58
9.72
Ours
43.96
2.89
8.93
61.64
3.30
9.72
4.4 Experimental Results on the 3DMatch and 3DLoMatch Datasets
We conducted systematic comparative experiments the 3DMatch dataset with overlap ratios exceeding 30%. The left and right columns of Table 2 show the registration performance using FPFH and FCGF descriptors, respectively. With the handerafted FPFH descriptor, method achieves the highest recall (RR), outperforming both traditional and learning-baid based approaches. Using the FCGF descriptor, our method surpasses all offthee----- baselines every evaluation metric. Compared to the MAC method, our method improves RR by 0.56%. More importantly, it reduces the average rotation error (RE) and average translation error (TE) by about 16.7% and 5.4%, respectively. This demonstrates superior overall performance. Qualitative results are shown in Fig. [5] Appendix
A.I0 Our method remains robust even in challenging scenarios with ambiguous features unclear local structures. It achieves alignment results that are close to the ground truth. These findings strongly validate the robustness and generalization ability of our method on diverse and complex point cloud data.
As shown in Table low-overlap registration. We compared our method with several leading traditional and deep learning approaches, using both FPFH and FCGF descriptors. Our method consistently delivers superior recall rates and reduced error metrics, validating its exceptional robustness and versatility even in challenging low-overlap scenarios. Qualitative results in Fig. S and Appendix 1. illustrate that our method remains effective even when local structures are ambiguous.
systematically evaluated our algorithm the 3DLoMatch dataset for
4.5 PointTruss Integration with Deep Learning Methods on 3DLoMatch
We have conducted experiments combining PointTruss with recent deep learning methods 29 on the challenging 3DLoMatch dataset.
PointTruss successfully enhances both Geo Teoassfforrrr (+4.5% recall) and PareNet (+1.70% recall) on the challenging 3DLh dataset. The consistent improvements across different learned features validate PointTruss's is compatibility with modern deep learning pipelines. Moreover, when integrated with Transsforrrr PointTruss achieves performance comparable to MAC while being more computationally efficient. These results demonstrate that PointTruss not only works standalone

---

Input
SCA-PRR
(c)
Ours
Ground-truth
Figure 5: Qualitative comparisons on the 3DMatch and 3DLoMatch datasets. The first and second rows correspond 3DMatch, and the third and fourth rows correspond to 3athhMtch.
Table 4: PointTruss Integration with Deep Learning Methods on 3DLoMatch
Method
Registration Recall
Tranransfrrmrr
75.0%
Tranfooorrrmrrr MAC
78.9%
Geo PointTruss
79.5%
PareNet
80.5%
PareNet MAC
81.5%
PareNet + PointTruss
82.2%
method but also serves as an effective drop-in replacement for traditional robust estimators in deep learning pipelines, providing consistent improvements across different feature extractors.
5 Conclusion
In this work, we introduce the k-truss from graph theory to the point cloud registration and use triangle support key constraint. We first perform consensus voting-based low-scale sampling on the input correspondences to construct a compatibility graph. Based on this, we propose a heuristic method that applies ke-tuuss decomposition with triangle support constraints to obtain several k-truss subgraphs. Each candidate subgraph is then processed by weighted SVD, and we use a designed spatial distribution score evaluate the spatial coverage and uniformity of inliers, selecting the best transformation hypothesis. Our method is efficient and simple, leveraging triangles as minimal rigid planar structures and exploiting their strong structural binding. Experimental results indoor, outdoor, and object-level point clouds show that our algorithm achieves state-of aff-the-rt registration accuracy while maintaining high efficiency. The method is robust to large numbers of outliers and low-overlap scenarios. Limitations and broader impacts are discussed in Appendix A.7
6 Acknowledgements
This work is supported by the National Natural Science Foundation of China (62036006, 62276200) and the Innovation Capability Support Plan of Shaanxi Province (2023KJXX- 144).
10

---

References
[1] Xuyang Bai, Zixin Luo, Lei Zhou, Hongkai Chen, Lei Li, et al. PointDSC: Robust point cloud registration using deep spatial consistency. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 15859-15869, 2021.
[2] Daniel Barath and Jifí Matas. Graph- Cut RANSAC. In Proceedings of the IEEE Conference on Computer Vision and Pottern Recognition, pages 6733-6741, 2018.
[3] Alvaro Parra Bustos and TatJun Chin. Guaranteed outlier removal for point cloud registration with correspondences. IEEE Transactions on Pattern Analysis and Machine intelligence, pages 2868 2882, 2017.
[4] Wen Chen, Haoang Li, Qiang Nie, and YunHui Liu. Deterministic point cloud registration via novel transformation decomposition. In Proceedings the IEEE Conference on Computer Vision and Pattern Recognition, pages 6348-6356, 2022.
[5] Zhi Chen, Kun Sun, Fan Yang, and Wenbing Tao. SC2-PCR: A second order spatial compatibility for efficient and robust point cloud registration. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 18221-13231, 2022.
[6] YenChi Cheng. Hsin Ying Lee. Sergey Tulyakov, Alexander G Schwing, and Liang Yan Gui. SDFusion: Multimodal 3D shape completion, reconstruction, and generation. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4456-4465, 2023.
Christopher Choy, Wei Dong, and Vladlen Koltun. Deep glohal registration. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 25233, 2020.
[8] Christopher Choy, Jacsik Park, and Vladlen Koltun. Fully convolutional geometric features. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pages 8958-8966, 2019.
[9] Jonathan Cohen. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report, pages 1-29, 2008.
[10] Brian Curless and Mare Levoy. A volumetric method for building complex models from range images. In Proceedings of the 23rd annual conference on Computer gruphics and interactive techniques, pages 303-312, 1996.
[11] Angela Dai, Matthias Nießner, Michael Zollhöfer, Shahram Izadi, and Christian Theobalt. Bundlefusion: Real-time globally consistent 3D reconstruction using on-the-fly surface reintegration. ACM Transactions on Graphics, page 1, 2017.
[12] Dexin Duan, Peilin Liu, Bingwei Hui, and Fei Wen. Brain-inspired online adaptation for remote sensing with spiking neural network. IEEE Transactions Geoscience and Remote Sensing, 2025.
[13] David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near- optimal time. In Algorithums and Computation: 21 International Symposium, pages 403-414. Springer. 2010.
[14] Martin A Fischler and Robert C Bolles. Random sample consensus: paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, pages 381 381-395, 1981.
[15] Andreas Geiger, Philip Lenz, and Raquel Urtasun. Are we ready for autonomous driving? the kitti vision benchmark suite. In Proceedings of the IEFE Conference Computer Vision and Pattern Recognition, pages 3354-3361, 2012.
[16] Maciej Halber and Thomas Funkhouser. Fine-to-coars global registration of rgb-d scans. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 1755-1764, 2017.
[17] Shengyu Huang, Zan Gojeic, Mikhail Usvyatsov, Andreas Wieser, and Konrad Schindler. Predator: Registration of 3D point clouds with low overlap. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 4267-4276, 2021.
[18] Tianyu Huang, Liangzu Peng, René Vidal, and Yun-Hui Liu. Scalable 3D registration via truncated entry-wise absolute residuals. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 27477-27487. 2024.
[19] Xiaoshui Huang, Guofeng Mei, Jian Zhang, and Rana Abbas. A comprehensive survey on point cloud registration. arXiv preprint arXiv:2103.0266 2021.

---

[20] Haobo Jiang, Zheng Dang, Zhen Wei, Jin Xie, Jian Yang, and Mathieu Salzmann. Robust outlier rejection for 3D registration with variational bayes. In Proceedings the IEEE Conference on Computer Vision and Pattern Recognition, pages 11 1148-1157, 2023.
[21] Yinuo Jiang. Xiuchuan Tang, Cheng Cheng, and Ye Yuan. A robust inlier identification algorithm for point cloud registration via fg-minimization. Advances Neural Information Processing Systems, pages 63124-63153, 2024.
[22] Kevin Lai, Liefeng Bo, and Dieter Fox. Unsupervised feature learning for 3D scene labeling. In IEEE International Conference on Robotics and Automation, pages 3050-3057, 2014.
[23] Junha Lee, Seungwook Kim, Minsu Cho, and Jaesik Park. Deep hough voting for robust global registration. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 15994-16003,
2021.
[24] Marius Leordeanu and Martial Hebert. A spectral technique for correspondecce problems using pairwise constraints. In Proceedings of the IEEE International Conference on Computer Vision, pages 1482-1489. IEEE, 2005.
[25] Jiayuan Li, Pengcheng Shi, Qingwu Hu, and Yongjun Zhang. QGORE: Quadratic- time guaranteed outlier removal for point cloud registration. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 11 1116-11110 1151, 2023.
[26] Boge Liu, Fan Zhang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. Efficient community search with size constraint. In IEEE International Conference on Data Engineering, pages 97-108, 2021.
[27] Alexander Neubeck and Lue Van Gool. Efficient non-maximum suppression. In Proceedings of the 18th International Conference on Pattern Recognition, pages 550-855. IEEE, 2006.
[28] Liangzu Peng. Manolis C Tsakiris, and René Vidal. Ares: Accurate rotation and correspondence search. In Proceedings of the IEEE Conference on Computer Vision and Pottern Recognition, pages 11153-1113, 2022.
[29] Zheng Qin, Hao Yu, Changjian Wang. Yulan Guo, Yuxing Peng, Slobodan Ilie, Dewen Hu, and Kai Xu. Geotransformer: Fast and robust point cloud registration with geometric transformer. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 9806-9821, 2023.
[30] Siwen Quan and Jiaqi Yang. Compatibility guided sampling consensus for 3-D point cloud registration. IEEE Transactions on Geoscience and Remote Sensing, pages 7380-7392. 2020.
[31] Radu Bogdan Rusu, Nico Blodow, and Michael Beetz. Fast point feature histograms FPFH for 3D registration. In JEEE International Conference Robotics and Automation, pages
2009.
[32] Jingnan Shi, Heng Yang, and Luca Carlone. Robin: a graph-theoretic approach to reject outliers in robust estimation using invariants, In IEEE International Conference on Robotics and Automation, pages 13820- 13827, 2021.
[33] Jamie Shotton, Ben Glocker, Christopher Zach, Shahram Izadi, Antonio Criminisi, and Andrew Fitzgibbon. Scene coordinate regression forests for camera relocalization in rgb-d images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2930-2937, 2013.
[34] Chitturi Sidhartha, Lalit Manam, and Venu Madhav Govindu. Adaptive annealing for robust geometric estimation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 21929-21939, 2023.
[35] Lei Sun. Sucoft: Robust point cloud registration based on guaranteed supercore maximization and flexible thresholding. IEEE Transactions on Geoscience and Remote Sensing, pages 1-21, 2024.
[36] Julien Valentin, Angela Dai, Matthias Nicßner, Pushmect Kohli, Philip Torr, Shahram Izadi, and Cem Keskin. Learning to navigate the energy landscape. In International Conference on 3D Vision, pages 323-332, 2016.
[37] Yue Wu, Xidao Hu, Yongzhe Yuan, Xiaolong Fan, Maoguo Gong, Hao Li, Mingyang Zhang, Qiguang Miao, and Wenping Ma. Pointme: multi-instance point cloud registration based on maximal cliques. In P Proceedings of the 41st International Conference on Machine Learning, 2024.
[38] Jianxiong Xiao, Andrew Owens, and Antonio Torralba. Sun3d: A database of big spaces reconstructed using sfm and object labels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1625-1632, 2013.
12

---

[39] Heng Yang, Jingnan Shi. and Luca Carlone. Teaser: Fast and certifiable point cloud registration. IEEE Transactions Robotics, pages 314-333, 2020.
[40] Jiaqi Yang, Xiyu Zhang. Shichao Fan, Chunlin Ren, and Yanning Zhang. Mutual voting for ranking 3d correspondences. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 4041-4057, 2023.
[41] Runzhao Yao, Shaoyi Du, Wenting Cui, Canhui Tang, and Chengwu Yang- Pare-net: Position-aware Itation-equivarian networks for robust point cloud registration. European Conference on Computer Vision, pages 287 303-303. Springer, 2024.
[42] Yongzhe Yuan, Yue Wu, Xiaolong Fan, Maoguo Gong, Wenping Ma. et al. EGST: Enhanced geometric structure transformer for point cloud registration. IEEE Transactions on Visualization and Computer Graphics, 2023, doi:10.1
[43] Yongzhe Yuan, Yue Wu, Xiaolong Fan, Maoguo Gong, Qiguang Miao, and Wenping Ma. Inlier confidence calibration for point cloud registration. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5312-5321, 2024.
[44] Yongzhe Yuan, Yue Wu, Xiaolong Fan, Maoguo Gong, Qiguang Miao, and Wenping Ma. Where precision meets efficiency: Transformation diffusion model for point cloud registration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 9734 9742, 2025.
[45] Andy Zeng, Shuran Song, Matthias Nicßner, Matthew Fisher, Jianxiong Xiao, and T Funkhouser. 3Dmatch: Learning the matching local 3D geometry in range scans. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, page 4, 2017.
[46] Fan Zhang, Haicheng Guo, Dian Ouyang. Shiyu Yang. Xuemin Lin, Zhihong Tian. Size-constrained community search on large networks: An effective and efficient solution. IEFE Transactions on Knowledge and Data Engineering, pages 356-371, 2023.
[47] Fan Zhang, Conggai Li, Ying Zhang. Lu Qin, and Wenjie Zhang. Finding critical users in social communi- ties: The collapsed core and truss problems. IEEE Transactions on Knowledge and Data Engineering, pages 78-91, 2018. 8.
[48] Xiyu Zhang, Jiaqi Yang, Shikun Zhang, and Yanning Zhang. 3D registration with maximal cliques. In Proceedings of the IEEE Conference on Computer Vision and Pottern Recognition, pages 17745-17754, 2023.
[49] Yifei Zhang, Hao Zhao, Hongyang Li, and Siheng Chen. Fastmac: Stochastic spectral sampling of correspondence graph. In Proceedings of the IEEE Conference on Computer Vision and Pottern Recognition, pages 17857-17867, 2024.
[50] Haimei Zhao, Jing Zhang, Zhuo Chen, Bo Yuan, and Dacheng Tao. On robust cross-view consistency in self-supervised monocular depth estimation. Machine Intelligence Research, pages 495-513, 2024.
[51] Qian Yi Zhou, Jacsik Park, and Vladlen Koltun. Fast global registration. European Conference on Computer Vision, pages 766-782. Springer, 2016.
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims and contributions of the paper clearly articulated in the abstract and introduction, and demonstrate good generalizability under similar assumptions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses the limitations of the work in Appendix A.7
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the method was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the method. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their method to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
The paper presents theorems and formulas in Sec. and reports theoretical results in Sec. We systematically derive the statistical properties of triangle relations under rigid-body noise and provide rigorous theoretical foundation for the robust discriminative power of the k-truss. The detailed derivations are presented in Appendix A.2
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide detailed description of the algorithmic procedure in the paper, and the main experimental results are reproducible. The code will be made publicly available upon acceptance of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
15

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [No]
Justification:
We will make the complete code public following the acceptance of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //nips Siiaps.cccpubliee wwtppbblccgguueeeeeoooeooccpcccd
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental setup and implement details are provided in Sec. 4.1 well as in Appendix A.5
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We conducted multiple experiments on public datasets as described in Sec. Furthermore, we performed 100 independent runs Sec. 4.2, and the averaged results demonstrate that our experimental outcomes are stable across multiple runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide information on the compute workers and model efficiency in Sec.
Sec. 4.3 and Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: This article complies in all respects with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The potential positive and negative societal impacts of the work are discussed in Appendix A.7
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The paper uses publicly available code and datasets during the evaluation process, strictly adhering to all relevant protocols and usage restrictions. Detailed license information for each dataset is provided Appendix A.9
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
18

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thood cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We will release the our code under the CC BY-NC-SA 4.0 license after the acceptance of the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: In this paper, LLMs are not used as any important, original, or non-standard component.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurl)) hbtte:///eerrpppccco//ooeeeeee// /c/////oeeeeeeeee/222////.. for what should or should not be described.
20

---

A Appendix
In the appendix, we first provide rigorous definitions of evaluation metrics (Sec. A.1 We then present
the Triangle Relation Stability Theorem for point cloud registration (Sec. A.2) A computational complexity analysis and comparison of dense subgraph algorithms given Sec. A.3 We further describe pseudocode for key algorithmic components (Sec.(A.4) and provide specific hypet-parameter selections for reference (Sec. A.5). Additionally, we conduct ablation studies of each component (Sec. A.6) and discuss the limitations and scalability of our method (Sec. an7 Sec. Sec.A.8) We offer
detailed information on public datasets (Sec. A.9) along with their visualization results (Sec. A.10)..
We also present an ablation study graph sampling and the v-value (Sec. A.11
A.1 The rigorous definitions of Evaluation Metries
Rotation Error (RE) For a given point cloud pair, the rotation error measures the angular difference between the estimated rotation R and the ground truth rotation Rgt. computed as:
trace R²)
RE
arccos
(18)
Translation Error (TE) The translation measures the Fuclidean distance between the esti- mated translation t and the ground truth translation tgt:
TE = || tg
(19)
Registration Recall (RR) Registration recall measures the percentage of successfully registered point cloud pairs over all pairs the dataset. A registration is considered successful if:
RRsDMMacch3DDLoMarte
RE < 15 TE 30 cm]
(20)
1 N
RRKITTI
RE, < 5 A TE, 60 cm
(21)
Mean Rotation and Translation Errors The mean rotation and translation errors are computed only over the successfully registered point cloud pairs:
Mean RE
Σ
RE;
(22)
I''
EN
Mean TE
Σ TE AEN"
(23)
N'
where N' {i RE;- < TRE A TE, < } denotes the set successfully registered pairs, with TRE = 15" and TTE 30 cm for 3DMatch and 3DLoMatch, and ThE 5 and TTE 60 cm for KITTI.
A.2 Triangle Relation Stability Theorem Based Point Cloud Registration
The PointTruss registration framework introduces novel perspective by leveraging the k-truss from graph theory to establish robust correspondence patterns in point cloud registration. At the core of k-truss lies the concept of triangle support-cade edge in a A-truss is contained in at least k-2 triangles, providing exceptional structural stability against perturbations. This property is particularly advantageous in point cloud registration, where noise, outliers, and partial visibility are common challenges.
Before developing the algorithmic components of PointTruss, it is essential to establish a rigorous theoretical foundation that quantifies how triangle relations behave under noise and rigid transfor- mations. Specifically, need to mathematically prove why triangle relations remain stable for
21

---

correct correspondences while exhibiting significant deviations for incorrect ones. This theoretical foundation addresses several critical questions:
How do triangle relations (edge lengths) change under noise perturbation?
2. What statistical properties characterize these changes?
Under what conditions can we reliably distinguish between correct and incorrect point correspon- dences based on triangle relation stability?
4. Why does the Htanglesuupootte k-truss provide reliable foundation for robust registration?
The following theorem establishes the statistical properties of triangle relations under noise, providing the theoretical underpinning for the PointTruss registration framework. By demonstrating that correct correspondences maintain stable triangle relations with high probability, this analysis justifies using triangle-based constraints core mechanism for robust point cloud registration.
Let {p: denote the source point cloud and Q {g: denote the target point cloud after rigid transformation and noise perturbation, where E R The rigid transformation is defined as T (R, t), where R E (0(3) rotation matrix satisfying R' R and det( 1, and R is a translation vector.
The noise-contaminated point cloud model can be expressed as:
q: Rp: + + nh ~ N~(,0091)
(24)
where 'i represents independent and identically distributed Gaussian noise with mean and covariance matrix 1²
For any pair of points p; and pj in the source point cloud, their Euclidean distance is preserved under rigid transformation. Let dij = llp, - Pyll denote the distance between points p3 and py- In the absence of noise, the distance between the corresponding transformed points 4, and qj is:
|1:
|R + 1 - (Rpj + +IIl
[R(pp - P,)1
V (RiPs -P))) (R((p - p;))
(25)
(oi--))) -P;)) TR R(p: Ps)
(p:-p;) I(p ps)
= Il: pill = dij
This distance preservation property fundamental characteristic of rigid transformations.
For any triplet of points (p:.Pj Pk) in the source point cloud, we define the triangle relation matrix Digk as:
Diju- = [llp - py|l
||p: Pkll
[|p;
pk
(26)
Similarly, for the corresponding points in the target point cloud, the triangle relation matrix is:
D'yr ll Iill
l/ qell
||q
9k. []]
(27)
Under foise-free rigid transformation, Disk = Diy reflecting the invariance of triangle relations under rigid transformations.
In the presence of noise, the distance between two points in the target point cloud becomes:
22

---

l19: 9ill
|Rp; ++ (Rp; + + n3)1
|R(p: - -Py) + (n: - -1yill
(28)
|p: Pj + R' (m m/)Il
|lp: Pj + Z II
where Zig R (1) 11)) (0, 20² represents the transformed noise difference.
The squared distance between noisy points be expanded as:
l1g. -/1122 |pp, Pj + Zzyl 12
(pi Pj Z,y) (p: Pj + Zis)
(29)
(p: p,) T (p: - -P;) + 2(p; -p;) Lig + Lij2is
|lp. pill² + 2(p; pi)'Zi
Zi +
||,,112
Taking the expectation:
Bl1a 1,11 E[[pp p,|l + 2(p: p2) Zij + |1
(30)
Ipp p1 + B[2(p: p,) T 4ig + B1I l|a]
Since E[Z,,] = 0, the middle term vanishes:
E[ PP) 2ny 2(p; -p;) T =0
(31)
For the third term, ||Z,y] 2| follows chi- shuured distribution with 3 degrees of freedom and scaling factor 20². The expected value of a chi-squared random variable is its degrees of freedom multiplied by the scaling factor:
E|| 1 = 3-20² = -6
(32)
Therefore:
Billg: 1]] = dl, + 60²
(33)
To calculate the expected value of || مارهo we apply a first-order Taylor expansion of f(x) = /z
around r = dty:
(x))= =
+ f'(t de,) (a de))
Vd de
2 /
d
(34)
1
di
(a de)
2d.3
For this approximation to be valid, we require a < dij. ensuring that higher-order terms (of order and beyond) remain negligible.
Substituting
||9: 4; 22 with B[x] = dl + +
23

---

Blllq 4,1l dig
[Billg: -311 de.)
2dgj
dig + 2d;j
(de + 60 - di.)
(35)
dig
60²
2dgj
dij + 30 2
dij
Defining the distance deviation Ag
|1::
dij. its expected value is:
30
B| E[11:
2/ll dij =
(36)
dij
For more precise analysis, we decompose the noise vector Zij into components parallel and perpen- P.-Pt:
dicular to the direction vector Mij
day
Zo Maj Zij.1
(37)
where Zej,u Zug Uij the projection of noise along wiy. and Zıy.1 the perpendicular component.
Using this decomposition, the distance can be more precisely approximated as:
|| 4i1
lidisuej + Ziill
|dgg + Zig.u Usj + Zig.
(Idis + Zej,a)uujj Zij,
1|
(38)
~ (dis + Zis,u) y
1+
(dis + Zig,a)²
/Zej.111 112
2 (dis + Ziz,u)
1
2 (dip + Zrig.u??
For [|i < dij. we can further approximate:
1 Zij.
l19: اill = (dis + Zij.a)
1+
2 di
(39)
121
R dij + Zijuu
2dhs
Since |2 2= =| 22j,0 we have:
11: اiهl x dig Zig.u + |Z 22
(40)
2di
Therefore, the deviation can be expressed as:
| 12 77j00
Aij ss Zijau +
(41)
2d,;
The variance of Ai can be decomposed as:

---

|| Zignu
Var(Aij) = Var Zij,u +
2dsj
(42)
|| 1| Liz.u
11
-ar Var(Z)),u)= + Var
+ 2Cov
Zis.u:
2dij
2de
Since Z3 ~ (000,201)) we have Zijuu ~ NO,, 2, thus:
Var(Zig.u) 2a²
(43)
For the second term, || ~ 20 X3 with variance 12o and Lūju ~ 20²22 with variance 80
The covariance between them is 4o Therefore:
|| 12
2 1j.u
1
Var
Var(1 Ziy11² ZZjju)
2d.j
4d
1
(Var(1 (1zz11 ) + Var (2 (oov(1 Zzzr))
4dl
1
(12o* + -0² - 2 400
(44)
1
(200² 800
4df
1
12o
4d2
30
d
The third term vanishes due the independence between Zıj,a and || 112:
Zii 12
Z2j,0
Cov
Zij.u:
Cov (ig,,z 1Zz..1 11
(45)
2dij
2d.j
Hence, the variance of distance deviation is:
Var( = 20² + 30
(46)
For the triplet (pi, Px)). need to calculate the covariance between deviations Aiy and Aa. The
key insight is that Zig R (m (z) and ZiP. RT [T) 7kk share the noise component v):-
The cross-covariance matrix is:
Bi = BER (n 1T) Tx)TT R]]
(47)
RR E(( 11) mnn) T1
Expanding the expectation:
E((n - 7n)(n - T] E[yon Mill - 1757, + 11
(48)
E[non]
Elponn Elynn E
Due to independence of noise vectors, only E'nen:T1 2²1 is non-zero. Therefore:
25

---

BI( 77)(1 - -00
(49)
This leads to the covariance between projections:
Cov Cov(Zijuu Zike.)
Ei Zsk - E E[Zij,u (igi.[llZzaa 1
[[(Zij Mei (Zak Wakk)
Blu,, Zij Zz Uitk
(50)
=u,jB[Zaz Zi 24kk
=uljo² Tuak
= (4ke)
Considering that the linear terms dominate in the deviation expression, we can approximate:
Cov(Aij, Aax) ~ Cov(Zyj.us Zsk,u) o² (uly upk)
(51)
The complete 3 covariance matrix for triangle edge deviations is:
Var(Ais) Cov( Dik. Aij) [Cov(AjR) AG)
Cov(Aij, Aik) Var (iit) Cov(Aju: jk: Aik))
Cov( Ajk) Cov(A Azk)
(52)
(ar)
Substituting the specific expressions:
20 + 3
o² Qu ua)
d Uzs))
di
Σ
0² (ur Unj)
20 + 30
Qu uzk)
(53)
di
(ulk uss)
d2 ux)
20 + 30
The deviation vector of the triangle relation matrix defined as: This vector follows multivariate normal distribution:
ADjjk Digh Disk (Aij. Ask Ayal
(54)
DDink N E)
(55)
with mean vector:
302 302 30
1 = | E A
(56)
dij d,a d,a
and covariance matrix Σ as defined previously. The Frobenius norm of the deviation matrix is:
||D /AB, + + +43,
(57)
The squared norm follows a non-central chi-squared distribution with 3 degrees of freedom and non-centrality parameter:
26

---

11/11
30
30
dij
dik
dsk
1
1
(58)
90*
d
jk
90
Σ
da
(o.b)E(((.D...AA)......
For incorrect point correspondences, at least one point is mismatched or belongs to a different rigid body. In this case, the deviation includes both random noise and systematic geometric error:
Dikk ~ N(u Says 2)
(59)
where 6sys = 1ōsg. dck, 6yk] represents the systematic error vector that typically satisfies ||óys|l >> a.
Given threshold e, we define:
P1 P(IlADijulle correct correspondence)
(60)
P2 PPIIADiy incorrect correspondence)
(61)
Under conditions of sufficient point cloud density, relatively small noise level o, and significant systematic error |syys >> σ, we can establish that P1 > p2.
For correct correspondences, |ADi 1 follows non-central chi-squared distribution with non- centrality parameter ||
For incorrect correspondences, || follows a non-central chi-squared distribution with non- centrality parameter A2 || + deys|
Since ||ō >> ||д|| we have A2 > A1. The cumulative distribution function of non-central chi-squared distribution decreases with increasing non-cen cen-entralltyy parameter for fixed threshold. Therefore:
P1 P(IIADijllll correct) > P(IIAdjjalle < incorrect) P2
(62)
For ke-truss, where each edge is supported by at least k-2 triangles, the probability of correctly identifying a correspondence increases exponentially with k, while the probability of incorrectly accepting false correspondence decreases exponentially. Assuming approximate independence between triangles supporting an edge, the probability of correctly identifying correspondence with = k-2 supporting triangles is:
P(correct mn triangles) (1 - p1)"
(63)
Similarly, the probability of incorrectly accepting false correspondence with m supporting triangles is:
Piinorrrect accepted m triangles) (p2)
(64)
Since Pi P2, as m increases (higher k-truss order), the discrimination power between correct and incorrect correspondences increases substantially. This provides the theoretical foundation for why tripngle-supported k-truss offer exceptional robustness in point cloud registration, particularly in challenging scenarios with noise, outliers, and partial visibility.
27

---

A.3 Computational Complexity Analysis
In this section, we provide a systematic comparison of the computational complexity for four representative dense subgraph algorithms commonly used in graph-based correspondence selection: maximum clique [32]. maximal clique [48]. k-truss (our method), and k-core[35). As shown in Table 5 this analysis highlights the superior efficiency of k-truss for large-scale point cloud registration.
maximum clique. The maximum clique problem aims to find the largest fully connected subgraph within a given graph. This is classic No-complete problem. The number of possible cliques grows exponentially with the number of vertices, making exact computation intractable for large graphs. The time complexity is exponential with respect the number of nodes, and thus maximum clique algorithms are unsuitable for practical large-scale applications.
maximal clique. A maximal clique is clique that cannot be extended by including any adjacent vertex; it is not necessarily the largest clique, but it is maximal with respect to set inclusion. Enu- merating all maximal cliques in a graph is also computationally demanding, as the number of such cliques can still be exponential in the worst case. As a result, MAC-based methods are robust in theory but suffer from high computational cost and limited scalability.
k-truss (our method). k-truss decomposition efficiently finds a subgraph in which every edge is contained in at least k triangles. The main computational steps are triangle enumeration and iterative edge removal based on triangle support. The overall time complexity is polynomial, typically O(m 1.5) where m is the number of edges. This makes k- t-truss much more efficient and scalable than clique-based based methods, while still leveraging higher-order geometric consistency (triangles) for robust correspondence selection.
k-core. k-core decomposition identifies the largest subgraph in which every node has at least degree It can be computed with simple iterative node removal process in linear time, ((m). This method is extremely efficient and suitable for very large graphs. However, k-core only considers node degree and ignores triangle or higher-order structures, which can limit its robustness when facing high outlier rates or complex geometric scenarios.
Table 5: Time complexity comparison of dense subgraph algorithms.
Method
Description
Time Complexity
Structural Strength
maximum clique
Largest fully-connected sub- graph
Exponential
Strongest, but intractable
maximal clique (MAC)
Maximal fully-connected sub- graph
Exponential
Strong, but costly
k-truss
Each edge in k triangles
Polynomial (O(m
Strong (triangle-hased)
k-core
Each node degree 2
Linear (0m))
Moderate (degree-based)
Both maximum clique and maximal clique approaches impose strict connectivity constraints but have exponential time complexity, making them impractical for large-scale or real-time applications. k-core is extremely efficient but provides only weak structural guarantees. In contrast, k-truss decomposition achieves favorable balance: maintains polynomial computational complexity, making it feasible for large-scale graphs, while its triangle-basee strpucture ensures robust inlier selection. This advantage explains the superior efficiency and effectiveness of k-truss in our framework for large-scale point cloud registration. Moreover, parallel k-truss decomposition algorithms can further improve the speed of k-truss extraction, making it even more suitable for large-scale applications.
A.4 Pseudocode for Our Algorithm
The following pseudocode outlines the complete pipeline of PointTruss, our robust 3D point cloud registration framework. The overall method consists of four modular stages: (1) consensus voting- based sampling, (2) compatibility graph construction and k-truss decomposition, (3) cluster-wise transformation estimation, and (4) spatial distribution score-based selection. Fach stage further detailed below with interleaved explanation and modular pscudocode.
28

---

Algorithm PointTruss
1: Input: Source point cloud P. target point cloud Q, initial correspondences C, parameters: noise std Ø, inlier threshold т, sampling ratio 3, k-truss parameter k, consensus threshold Te. compatibility threshold Tcomp: NMS radius Ynms
2: Output: Rigid transformation (R)
3: Apply Algorithm to C with Te. Tnmms+ 3 to obtain Zsampled
2
4: Let Csampled = {CT]
Isampled)
5: Construct compatibility graph G among Commpledi add edge between a and ej if Scomp (Ct, Cy) >>
Tromp: using noise parameter a
6: Compute adjacency matrix A of G
7: Apply Algorithm 3 to A with k to get robust clusters {Nis
8: for each cluster Nm. do
9: Compute node centrality in cluster to obtain weights wi
Estimate candidate transformation (Rm, tm)) using cestrality-weigheee SVD
11: end for
Apply Algorithm all candidate transformations {(Rmm tm)) to obtain optimal (R*, tt)
13:
return (R",t" tt)
Step 1: Consensus Voting-based Low-scale Sampling. Given initial correspondences, we first select subset of high-quality matches via consensus vot- ing and non-maximum suppression (NMS). This improves the precision of the subsequent graph construction.
Algorithm 2 Consensus Voting-based Low-scale Sampling
1: Input: Correspondences
{(P) p)) compatibility scores Scump(+> (++)) consistency
threshold Te, NMS radius Tumss sampling ratio 8
2: Output: Sampled correspondence indices Isampled
3: for each correspondence i = to N do
4: Compute consensus score Sç using Scomp and threshold T. (please Eq.
5: end for
6: for each correspondence to N do
7: Apply non-maximum suppression to S: using NMS radius Tams (please see Eq. (5)
8: Compute final score Sfinal (please see Eq. (6)
9: end for
Set = [
Select indices Isampled of the top-K correspondences with the highest Stinal
12:
return Teampied
Step 2: Compatibility Graph Construction and K-Truss Decomposition. A compatibility graph is built over the sampled correspondences, where edges represent geometric consistency. We then extract structurally robust clusters using k-truss decomposition.
Step 3: Cluster-wise Transformation Estimation. For each cluster, we estimate a candidate rigid transformation using centrality-weighted SVD. All candidate transformations subsequently evaluated in the next step.
Step 4: Spatial Distribution Score (SDS) Based Selection.
We score each candidate using SDS, which measures both the alignment quality and spatial spread of inliers, and select the best one for output.
A.5 Hyper-parameter selection
We set the inlier threshold 7 to 0.1 for the 3DMatch and 3DLoMatch datasets. For the KITTI dataset, 7 set 0.6. The sampling ratio 3 ranges from to 0.5. The k-truss parameter k is chosen between 3 and 10. The consensus threshold is set to 0.9 by default. The compatibility threshold
29

---

Algorithm 3 K-Truss Decomposition for Enhanced Structure Detection
1: Input: Adjacency matrix A of the compatibility graph among sampled correspondenees, truss
parameter
2: Output: Robust clusters of correspondences {Ni..
3: Compute triangle support matrix T using A
4: Identify valid edges Evalid where triangle support 2 (I:-2)
5: for each vertex i do
6: Extract neighhorhood Nú connected by valid edges
7: if [N]]] 2 l then
8: Add NG the set of robust clusters {
9: end if'
end for
11:
return {Am)
Algorithm 4 Spatial Distribution Score (SDS) Based Transformation Selection
Input: Source points P {p:) target points Q {p] candidate transformations
{RRm 6m) km)]=== inlier threshold
2: Output: Optimal transformation (R*,t*)
3: for each candidate (Rmy (m) do
4: Transform source points using (Rm. tm)
5: Identify inlier Im using threshold
6: if [Zml < 10 then
7: Assign SDS score for this candidate
8:
else
9:
Compute inlier ratio Pinlier
10:
Compute spatial coverage ratio Pooverage
11:
Compute inlier alignment error term Perror
12:
Compute SDS score (please see Eq. (4117 end if
14:
end for
15:
Select (R", t*) with the highest SDS score
16:
return (R",t*
Tromp is adjusted according to the noise standard deviation a. The NMS radius Tims is typically set to 0.1. All hyperparameters are determined based empirical validation.
A.6 Ablation study of each component
We conducted systematic ablation studies on the 3DMatch and 3DLoMatch datasets to analyze each component of our algorithm. The MAC (Maximal Clique) method was introduced for comparison, ensuring comprehensive evaluation of our proposed modules. As shown in Table ( method demonstrates the effectiveness of the k-truss for point cloud registration. This structure not only improves overall registration accuracy but also enhances robustness. In addition, the consensus voting-based low-scale sampling strategy and spatial distribution score each contribute positively in experiments. Results indicate that both strategies can serve effective components for traditional registration methods, improving their performance in challenging scenarios. Overall, our study confirms the practical value and broad applicability of these modules point cloud registration tasks.
A.7 Limitations and broader impacts
We propose a novel point cloud registration method based on the k-truss in graph theory. This method uses triangles as core constraints and introduces new perspective for point cloud registration. fully exploits the advantages of higher-order structures modeling spatial relationships. Our method performs well in both dense and sparse point cloud scenarios. It shows strong robustness and generalization, effectively resisting high ratios of outliers and noise. addition, the k-truss decomposition module in our algorithm is highly extensible. It can be used independent
30

---

Table 6:
Analysis experiments on 3DMatch and 3DLoMatch with FPFH and FCGF descriptors. CV: Consensus Voting-based Low-scale Sampling Strategy; MAC: Maximal Clique; SDS: Spatial Distribution Score.
CV MAC
k-truss
SDS
inlier
RRyDLMM (%)
FPFH
83.67
37.10
2) 4
83.80
38.85
3)
83.73
39.02
4) d
84.20
38.91
5)
83.86
37.79
6) V
84.20
39.98
7)
83.86
38.85
8) /
84.70
43.96
FCGF
91.68
57.44
2)
93.59
59.46
3)
93.53
59.01
4) V
93.72
59.96
5)
93,40
58.00
1
93.72
59.63
7)
93.66
59.40
/
93.84
61.64
component and flexibly integrated into other registration algorithms point cloud processing frameworks, further enhancing overall system performance.
In terms of applications, this method is particularly suitable for scenarios requiring high precision and stability in point cloud registration, such as autonomous driving. For example, perception and localization tasks for autonomous vehicles, reliable point cloud registration is crucial for environment understanding and high-precision map construction. Nevertheless, our method still has room for improvement in the adaptive selection of the value and the screening of the optimal k-truss subgraph. At present, how to automatically determine the best k value according to different data characteristics, and how to efficiently select representative k-truss substructures, are the main directions for our future research.
In the future, we will further explore the potential of higher-order topological structures, such as quadrilaterals, point cloud registration. This will improve the expressive power of the algorithm in complex scenarios. We also plan to leverage high-performane parallel computing frameworks, such as PyTorch, to parallelize the k-truss decomposition process. This will enable real-time processing of large-scale point cloud data. Through these improvements, we aim promote the application of graph- based point cloud registration algorithms in real engineering scenarios and advance development in related fields.
A.8 Scalability of our algorithm
Our experimental results demonstrate that the proposed algorithm achieves state-of-the-art perfor- mance in both accuracy and robustness, while also exhibiting excellent efficiency. With further optimization, such as leveraging PaainngPyTrreee PyTorch's parallel computation capabilities, the speed of our method can be further improved. Currently, the k-truss decomposition accounts for most of the runtime. Several studies have optimized parallel k-truss decomposition, and these techniques can also be applied to our method. In addition, our method can serve flexible module that integrates with conventional or deep carning-basee descriptors. The proposed Spatial Distribution Score can also be adopted by other methods to further enhance overall accuracy.
31

---

3DMuce
3D oMMtch
(a) Input
(b) Ours
(c) Ground-ruth
(a) Input
(b) Ours
(c) Ground-truth
Figure 6: Visualizations of registration results the 3DMatch and 3DL datasets. The first two rows show examples from 3DMatch, and the last two rows show examples from 3Dth.atch. In each group, yellow and blue point clouds represent the source and target, respectively, From left right: (a) input point cloud pairs, (b) results of our method, and (c) ground-truth alignment.
A.9 Datasets
All datasets used in this work are publicly available. The Bunny model from the Stanford 3D Scanning Repository was acquired using a Cyberware 3030 MS scanner and is restricted to non-commercial 3.0 License and contains 11 sequences captured by Velodyne HDL-64 3D LiDAR scanner in outdoor driving scenarios. Following the protocol in [5] 48), we use sequences 8-10 for testing. Additionally, we provide the 3DMatch dataset and its corresponding license information, as shown in Table 7 subset of 3DMatch.
use. The KITTI dataset is published under the CerCoomnriial-hhrrAaaeeeeae
where 3DLoMatch
Table 7: Source datasets for 3DMatch and their corresponding licenses.
Datasets
License
SUN3D 38
CC BY-NC-SA 4.0
7-Scenes
33
Non-commercial use only
RGB-D Scenes v.2
22
(License not stated)
Analysis-by- by-ss---b-Sythhsiiss
36
CC BY-NC-SA 4.0
BundleFusion
11
CC BY-NC-SA 4.0
Halber al. 16
CC BY-NC-SA 4.0
A.10 Visualization of Registration Results
We present visual registration results on the 3DMatch and 3DLoMatch datasets Fig. 6 yellow and blue point clouds represent the source and target, respectively. The first column shows the input point clouds, and the second column displays the point clouds aligned using the ground-truth transformation. Even on the 3DLoMatch dataset with low overlap, our method clearly extracts the key structure and achieves accurate alignment. We also show registration results on the KITTI dataset in Fig. 7 The input source and target point clouds are in different poses. After applying estimated transformation, the source point cloud successfully aligned with the target. The result almost identical to that of the ground-trutt -ruth transformation.
The
32

---

Input
Ours
Ground-truth
Figure 7:
Visualizations of registration results on the KITTI dataset. From left to right: input point cloud pairs, registration results using our method, and ground-truth alignment.
A.11 Ablation Study on Graph Sampling and K-value
conduct comprehensive ablations to evaluate how the sampling ratio 3 influences accuracy and efficiency, shown in Table 8
Table 8: Impact of sampling ratio 3 on 3DMatch (FCGF).
Sampling Ratio
Registration Recall
Runtime (s)
Speedup
0.1
93.10%
0.12
8.3 x
93.53%
0.16
6.3
0.3
93.84%
0.20
5.0x
0.4
93.78%
0,25
4.0x
0.5
93.41%
0.31
3.2x
Retaining only 10% of correspondences via consensus voting preserves 93. 10% registration success
while yielding an 8.3x speedup, indicating that voting preferentially keeps geometrically consistent correspondences. Higher sampling ratios can be slightly worse than 3=0.3 because they retain more erroneous correspondences that adversely affect the downstream k-truss decomposition.
Initial graph: 5,020 nodes - after voting: 502 nodes - adjacency: 502 x 502 with 43,571 edges.
Table K- K-Truss decomposition statistics with 10% sampling.
k-value
Subgraphs
Node Range
Avg. Nodes
3
502
[3-322]
173.6
4
502
[4-322]
173.6
5
499
[5-322]
174.5
6
498
[6-322]
174.7
495
[7-320]
175.5
8
493
[8-321]
176.0
9
492
[9-320]
176.1
10
490
[10-320]
176.4
33

---

As shown in Table even with aggressive 10% sampling, subgraphs remain large (average 170- nodes), due to: (i) high-quality imput after the voting pre-filter that enforces strong geometric consistency and high connectivity density; and (ii) natural clustering of correct correspondences, which form richly supported triangle structures satisfying k-truss constraints.
Sensitivity to k and Multi-k
The sensitivity of registration recall to k is shown in Table I0
Table 10: Sensitivity of registration recall to ls on 3DMatch with FCGF.
k-value
Registration Recall
3
93.15%
5
93.21%
7
93.59%
10
93.40%
Multi-A: (3-10)
93.84%
Performance is weakly sensitive to because stricter k-truss subgraphs are nested subsets those at smaller k; forming natural hierarchy. The multi-k strategy leverages this property. In practice, we select the transformation from the subgraph with the highest spatial distribution score; a global re-estimation using all inliers is unnecessary, the selected subgraph already yields robust alignment.
34


Reviews:
[{"review_id": "yrQIbspnko", "reviewer": "Reviewer_akLc", "summary": "The paper proposes PointTruss, a novel graph-based algorithm for point cloud registration that introduces the k-truss concept from graph theory to improve inlier selection.", "questions": "1）The paper claims k-truss leverages triangle rigidity for robust inlier selection. Can the authors provide a formal theoretical analysis (e.g., using geometric or graph-theoretic principles) to demonstrate why k-truss is inherently more suitable than k-core or clique-based methods for point cloud registration? This could strengthen the motivation and clarify the method’s design rationale.\n\n2）Why was k-truss chosen over k-core or clique-based methods like SC²-PCR or TEASER++? \n\n3）The method relies on triangles as the “simplest rigid formation” . How does PointTruss handle scenarios where triangle formations are sparse or absent due to extreme noise, occlusions, or low-overlap point clouds? Have the authors analyzed the failure modes of k-truss in such cases, and how do these affect registration accuracy?\n\n4）The k value in k-truss decomposition determines the strength of triangle support. How is the optimal k value chosen, and what is the sensitivity of PointTruss’s performance to variations in k? Could the authors provide an ablation study or theoretical justification for k selection to clarify its impact on robustness and efficiency?", "limitations": "No limitations discussed. See Weaknesses for suggestions.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths：\n\n1）Introducing k-truss to point cloud registration is a novel contribution, as it leverages triangle-based constraints to enhance inlier selection, distinguishing it from clique-based (e.g., TEASER++) and k-core-based (e.g., ROBIN) methods. \n\n2）The evaluation is thorough, covering synthetic  and real-world datasets with FPFH and FCGF descriptors. Quantitative results and qualitative visualizations show strong robustness to outliers and noise.\n\nWeaknesses：\n\n1）While k-truss is novel in this context, the paper does not sufficiently distinguish PointTruss from existing graph-based methods like SC²-PCR or MAC, which also exploit geometric consistency. \n\n2）The lack of ablation studies on key components (e.g., k value, spatial distribution score) weakens the analysis of their contributions.", "was_revised": true, "final_justification": "Given the solid technical foundation, improved clarity, and responsiveness to feedback, I maintain my recommendation of Weak Accept.", "rebuttal": "Dear Reviewer akLc,\n\nThank you for your insightful comments. We have carefully responded to every comment raised by the reviewer and will make corresponding revisions to the manuscript.\n\n>**W1-Insufficient Distinction from Existing Methods**\n\nWe appreciate the reviewer's concern about distinguishing PointTruss from existing graph-based methods. All graph-based point cloud registration methods utilize first-order compatibility (Euclidean distance) to ensure graph construction. The major distinctions between our method and SC²-PCR/MAC lie in the final subgraph structure design and search strategy. The key distinctions are:\n\n- SC²-PCR: Uses second-order spatial compatibility but relies on pairwise constraints without triangle support. It doesn't exploit the rigidity of triangular structures.\n\n- MAC: Searches for maximum cliques which requires full connectivity and has exponential complexity, making it computationally expensive (5.54s vs our 0.20s on 3DMatch).\n\n- PointTruss: Uniquely leverages k-truss with triangle-based constraints. The truss structure formed by triangles is the core of our entire method.\n\nWe will enhance Section 2 to better clarify these distinctions.\n\n>**W2-Lack of Ablation Studies**\n\nWe apologize for not making our ablation studies more visible. We have conducted comprehensive ablation studies in Appendix A.6 (Table 5):\n\n**Table 5: Analysis experiments on 3DMatch and 3DLoMatch with FPFH and FCGF descriptors**\n| | CV | MAC | k-truss | SDS | inlier | RR3DMatch(%) | RR3DLoMatch(%) |\n|---|---|---|---|---|---|---|---|\n| **FPFH** | | | | | | | |\n| 1) | | ✓ | | | ✓ | 83.67 | 37.10 |\n| 2) | ✓ | ✓ | | | ✓ | 83.80 | 38.85 |\n| 3) | | ✓ | | ✓ | | 83.73 | 39.02 |\n| 4) | ✓ | ✓ | | ✓ | | 84.20 | 38.91 |\n| 5) | | | ✓ | | ✓ | 83.86 | 37.79 |\n| 6) | ✓ | | ✓ | | ✓ | 84.20 | 39.98 |\n| 7) | | | ✓ | ✓ | | 83.86 | 38.85 |\n| 8) | ✓ | | ✓ | ✓ | | **84.70** | **43.96** |\n| **FCGF** | | | | | | | |\n| 1) | | ✓ | | | ✓ | 91.68 | 57.44 |\n| 2) | ✓ | ✓ | | | ✓ | 93.59 | 59.46 |\n| 3) | | ✓ | | ✓ | | 93.53 | 59.01 |\n| 4) | ✓ | ✓ | | ✓ | | 93.72 | 59.96 |\n| 5) | | | ✓ | | ✓ | 93.40 | 58.00 |\n| 6) | ✓ | | ✓ | | ✓ | 93.72 | 59.63 |\n| 7) | | | ✓ | ✓ | | 93.66 | 59.40 |\n| 8) | ✓ | | ✓ | ✓ | | **93.84** | **61.64** |\n\n- k-truss vs MAC (Rows 1→5, 2→6): Replacing MAC with k-truss consistently improves performance, especially on challenging 3DLoMatch dataset (FCGF: 59.46%→59.63%, +0.17%). This validates our core hypothesis that triangle-based constraints are more effective than clique-based methods for capturing geometric consistency.\n\n- Impact of Consensus Voting (CV): Comparing rows without CV to those with CV (e.g., 5→6, 7→8), we observe significant improvements:FPFH: 37.79%→39.98% (+2.19%) on 3DLoMatch;FCGF: 58.00%→59.63% (+1.63%) on 3DLoMatch.\n\n- Spatial Distribution Score (SDS) vs Inlier Counting: Comparing SDS-based evaluation (rows 3,4,7,8) with simple inlier counting (rows 1,2,5,6):Most notable on 3DLoMatch: FCGF 59.63%→59.40% (-0.23%) without CV, but 59.63%→61.64% (+2.01%) with CV.\n\nFor k-value analysis, we employ a multi-k strategy (k∈[3,10]) rather than fixing a single k, which inherently provides robustness. We will provide detailed k-value ablation experiments and the rationale for our designed strategy in Q4.\n\n>**Q1-Theoretical Analysis of k-truss Superiority**\n\nWe provide formal theoretical analysis demonstrating why k-truss is inherently more suitable:\n\n**1. Theoretical Foundation (Theorem 1 & Appendix A.2):**\nWe established the Triangle Relation Stability Theorem showing that under rigid transformation with Gaussian noise:\nP(||ΔDᵢⱼₖ||_F < ε | correct) >> P(||ΔDᵢⱼₖ||_F < ε | incorrect)\n\nThis formally proves triangular structures exhibit significantly higher stability for correct correspondences. Crucially, correct correspondences are exponentially more likely to participate in multiple consistent triangles, whereas incorrect ones rarely satisfy even a few—establishing the theoretical foundation for the discriminative power of k-truss.\n\n**2. Comparative Analysis:**\n- k-core: Only enforces deg(v) ≥ k (first-order connectivity)\n- k-truss: Requires sup(e,G) ≥ k-2 (second-order triangle support)\n- Clique: Exponential complexity with overly strict requirements\n\nk-truss captures second-order geometric relationships through triangles--the simplest rigid planar structures that preserve geometric properties under transformation.\n\n**3. Spectral Graph Theory Connection:**\n\nSpectral graph theory offers a principled explanation for the effectiveness of **k-truss** structures in distinguishing inlier and outlier correspondences in point cloud registration. Compared to k-core graphs, k-truss subgraphs exhibit stronger spectral properties that correlate with higher structural coherence and cluster separability.\n\n#### **Cheeger Constant**\n\nFor an undirected graph $G = (V, E)$, the **Cheeger constant** is defined as:\n\n$$\nh(G) = \\min_{S \\subset V,\\, |S| \\leq |V|/2} \\frac{|\\partial S|}{\\min(|S|, |V \\setminus S|)}\n$$\n\nwhere $\\partial S$ denotes the set of edges with one endpoint in $S$ and the other in $V \\setminus S$. A larger Cheeger constant implies stronger expansion properties and better internal connectivity.\n\nk-truss subgraphs typically exhibit **higher Cheeger constants** than k-core subgraphs, indicating that they form more cohesive and well-connected components.\n\n#### **Eigenvalue Gap and Connectivity**\n\nLet $\\lambda_1, \\lambda_2, \\lambda_3, \\dots$ denote the eigenvalues of the **normalized Laplacian matrix** $\\mathcal{L}$. For a connected graph, $\\lambda_1 = 0$, and $\\lambda_2$ is known as the **algebraic connectivity** of the graph.\n\nThe **Cheeger inequality** establishes the relationship:\n\n$$\n\\frac{h(G)}{2} \\leq \\lambda_2 \\leq 2h(G)\n$$\n\nThus, a larger $\\lambda_2$ implies stronger overall connectivity. Furthermore, the **eigenvalue gap** $\\lambda_3 - \\lambda_2$ reflects how clearly separable the graph’s clusters are; a larger gap typically indicates more well-defined clusters.\n\n#### **Inlier/Outlier Separation in Correspondence Graphs**\n\nIn the context of point cloud registration, the correspondence graph connects putative matches as nodes, with edges reflecting geometric consistency.\n\n* **Inliers**: Form densely connected clusters due to geometric compatibility, naturally satisfying triangle constraints in k-truss structures. Inlier correspondences form cohesive k-truss components with high internal connectivity.\n* **Outliers**: Tend to have weak or random connections and rarely participate in sufficient valid triangles to survive the k-truss filtering.\n\nThese spectral properties reinforce the theoretical and empirical robustness of k-truss in graph-based point cloud registration.\n\n>**Q2-Why k-truss over k-core or Clique Methods**\n\nWhile SC²-PCR and TEASER++ are graph-based registration methods, the fundamental difference lies in the sought subgraph structures. Beyond the theoretical advantages mentioned above:\n\n**1. Optimal Constraint Strength:**\nk-truss provides the \"sweet spot\":\n- Too weak: k-core (only degree constraints)\n- Too strong: Cliques (full connectivity)\n\n**2. Computational Efficiency:**\n- k-truss: O(m^1.5) - polynomial and practical\n- Maximum clique: Exponential - often intractable\n- k-core: O(m) - fast but insufficient robustness\n\nOur experimental results clearly demonstrate k-truss's superiority:\n- On KITTI: Ours (99.64%) vs SC²-PCR (99.46%) vs TEASER++ (91.17%)\n- On 3DLoMatch: Ours (61.64%) vs SC²-PCR (58.73%) vs TEASER++ (46.76%)\n\n>**Q3-Handling Sparse Triangle Scenarios**\n\nThank you for raising this critical question. We handle sparse triangular structures through:\n\n**1. Consensus Voting-based Sampling (Section 3.3):**\nThis crucial preprocessing step:\n- Filters isolated correspondences that cannot form triangles\n- Prioritizes high-quality correspondences more likely to form stable triangular structures\n- Reduces the impact of regions with sparse geometric features\n\n**2. Multi-level k-truss Extraction:**\nOur method extracts k-truss subgraphs for multiple k values (k=3 to 10, as shown in Figure 2):\n- Lower k values (k=3,4) capture sparser structures with fewer triangle requirements\n- Higher k values extract denser, more reliable structures\n- Each k-truss generates candidate transformations evaluated by our spatial distribution score\n\n**3. Performance in Extreme Cases:**\n- Low overlap (3DLoMatch): Despite <30% overlap, our method achieves 61.64% RR (Table 3)\n- Outperforms SC²-PCR (58.73%) and TEASER++ (46.76%)\n- This demonstrates robustness when triangular structures are inherently limited\n\nFor 3DLoMatch registration failures, we analyzed two main causes: (1) descriptor quality limitations - our validation experiments combining with GeoTransformer or PareNet show improved performance (see table below); (2) degenerate geometric configurations (e.g., planar scenes) may result in extremely sparse correspondences without triangular structures, which we plan to address in future work.\n\n**Table: PointTruss Integration with Different Descriptors on 3DLoMatch**\n| Method | Registration Recall |\n|--------|---------------------|\n| FPFH + PointTruss|43.96%|\n| FCGF + PointTruss|61.64%|\n| **GeoTransformer + PointTruss** | **79.5%** |\n| **PareNet + PointTruss** | **82.2%** |\n\n>**Q4-k-value Selection and Sensitivity**\n\nAs mentioned in Q3, we adopt multi-level k-truss extraction to select the best transformation. PointTruss performance is relatively insensitive to k-value variations, as shown in the sensitivity experiments below:\n\n**Table: k-value Sensitivity Analysis on 3DMatch with FCGF**\n| k value | Registration Recall | \n|---------|-------------------|\n| k=3 | 93.15% | \n| k=5 | 93.21% | \n| k=7 | 93.59% | \n| k=10 | 93.40% | \n| Multi-k (3-10) | **93.84%** | \n\nThe insensitivity to k values is mainly because subgraphs with strict constraints (larger k) are actually subsets of subgraphs with smaller k constraints, providing a natural hierarchy. Our multi-k strategy leverages this property to achieve optimal performance."}, {"review_id": "9TMMLhzTtl", "reviewer": "Reviewer_EBs3", "summary": "The paper introduces the k-truss from graph theory into point cloud registration, leveraging triangle support as a constraint for inlier selection. In addition, a consensus voting-based low-scale sampling strategy is presented to extract the structural skeleton of the point cloud prior to k-truss decomposition. Furthermore, to avoid spatially clustered inliers, a spatial distribution score is introduced to evaluate the coverage and uniformity of inliers. Extensive experiments on KITTI, 3DMatch, and 3DLoMatch demonstrate the effectiveness of the proposed methods.", "questions": "Please refer to the weaknesses.", "limitations": "yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengthens:\n- The paper is exceptionally well-structured and accessible, ensuring clarity throughout.\n\n- It compellingly motivates the application of the k-truss (a graph-theoretic concept) to point cloud registration.\n\n- The proposed method achieves state-of-the-art (SOTA) performance across diverse datasets, including outdoor (KITTI) and synthetic benchmarks (3DMatch, 3DLoMatch).\n\n- Comprehensive experiments and ablation studies rigorously validate the efficacy of each component in the framework.\n\nWeaknesses:\n- Figure 2 illustrates examples of subgraphs generated using K-truss decomposition. However, the subgraphs for K=5 and K=6 appear to contain inconsistencies. For instance, in the K=5 subgraph, the edge E(C5, C8) participates in only two triangles: $\\triangle$C3C5C8 and $\\triangle$C4C5C8. This contradicts the requirement that edges within a 5-truss subgraph must belong to at least three triangles (k-2 = 3).\n\n- Table 1 shows that the proposed method achieves the shortest inference time. However, K-truss decomposition is computationally intensive, and its required computation time should be clarified.\n\n- The results reported for VBReg [18] (from the official paper) on KITTI using FPFH features are 0.32 (RE) and 7.17 (TE). These differ from the values of 0.45 (RE) and 8.41 (TE) listed in Table 1. Furthermore, the runtime for PointDSC cited within the VBReg[18] is 0.11 seconds, which is shorter than the 0.45 seconds reported for PointDSC in Table 1.", "was_revised": true, "final_justification": "My concerns have been properly addressed. I keep my initial score.", "rebuttal": "Dear Reviewer EBs3,\n\nThank you for your insightful comments and careful review. We have carefully responded to every comment raised by the reviewer and will make corresponding revisions to the manuscript.\n\n>**W1-Inconsistencies in Figure 2**\n\nThank you for your careful review and for identifying this inconsistency in Figure 2. You are absolutely correct - in the K=5 subgraph, the edge E(C5, C8) participates in only two triangles (△C3C5C8 and △C4C5C8), which violates the k-truss definition requiring at least k-2=3 triangles for k=5.\n\nWe sincerely apologize for this visualization error. Upon investigation, we found this was a manual drawing mistake when creating the figure for illustration purposes. The error occurred because, as the reviewer correctly identified in the k=5 subgraph example, we inadvertently omitted a critical node C6 at the intersection of nodes C2, C3, C4, and C5 during the manual simplification of the visualization from our algorithm's actual output. \n\nWe emphasize that this visualization error is confined to Figure 2 only and does not affect:\n- The theoretical formulation (Algorithm 3 correctly implements k-truss decomposition)\n- The implementation (our code strictly enforces the k-2 triangle constraint)\n- Any experimental results (all results are generated using the correct algorithm)\n\nWe will correct Figure 2 in the camera-ready version to accurately reflect the k-truss definition. We greatly appreciate the reviewer's meticulous attention to detail, which helps us improve the clarity and accuracy of our presentation.\n\n>**W2-Clarification on K-truss Computation Time**\n\nThank you for this important question about computational efficiency. We apologize for not being more explicit about the runtime breakdown and will clarify this in the revised version.\n\n**Runtime Breakdown:**\nThe runtime reported in Table 1 (0.20s for FPFH, 0.21s for FCGF) includes all components of our method:\n\n| Component | Time (s) |\n|-----------|----------|\n| Consensus Voting | 0.02 |\n| Graph Construction | 0.03 |\n| K-truss Decomposition (for all k∈[3,10]) | 0.10 |\n| Transformation Evaluation | 0.05 |\n| Total | 0.20 |\n\n**Efficiency of K-truss Decomposition:**\nWhile k-truss decomposition has theoretical complexity O(m^1.5), our implementation is highly efficient due to:\n1. Sparse graph structure: After consensus voting, depending on parameter selection, only 10%-50% of correspondences are retained, significantly reducing the graph size\n2. Optimized implementation: We use efficient triangle enumeration and edge support tracking, avoiding redundant computations\n\n**Comparison with Other Methods:**\nDespite including k-truss decomposition, our total runtime remains competitive:\n- Ours: 0.20s (including k-truss)\n- MAC [35]: 5.54s (maximal clique, exponential complexity)\n- SC²-PCR [13]: 0.31s\n- PointDSC [7]: 0.45s\n\nThe efficiency gain comes from our consensus voting preprocessing, which dramatically reduces the graph size before k-truss decomposition, making the overall pipeline faster than methods that process all correspondences.\n\n>**W3-Discrepancies in Reported Results**\n\nThank you for noting these discrepancies. We can clarify the source of these differences:\n\n**1. VBReg Results on KITTI:**\nOur reported results (RE=0.45°, TE=8.41cm) differ from VBReg's original paper (RE=0.32°, TE=7.17cm). However, our results are exactly consistent with the recent NeurIPS 2024 paper [19] (Jiang et al., \"A robust inlier identification algorithm for point cloud registration via ℓ0-minimization\"), which reports the same values for VBReg under their standardized evaluation protocol.\n\nThis consistency with [19] validates our experimental setup, as they also conducted comprehensive benchmarking of registration methods. The differences from the original VBReg paper likely stem from:\n- Different FPFH implementations or parameters\n- Variations in evaluation protocols\n- Different data preprocessing pipelines\n\n**2. PointDSC Runtime:**\nSimilarly, our PointDSC runtime (0.45s) matches the benchmarking in [19], which was also conducted on RTX 3090. The difference from VBReg paper's reported 0.11s for PointDSC can be explained by:\n- Different hardware: VBReg paper used Tesla V100 GPU, while we used RTX 3090\n- Different runtime measurement criteria (core algorithm vs. full pipeline)\n- System-level variations and implementation details\n\n**3. Experimental Validity:**\nThe alignment of our results with the independent NeurIPS 2024 benchmark [19] demonstrates:\n- Our experimental setup follows recent standardized evaluation practices\n- The results are reproducible and consistent with state-of-the-art benchmarking\n- All methods are evaluated fairly under identical conditions\n\nWe believe following the recent standardized benchmark [19] ensures more reliable and comparable results across different methods."}, {"review_id": "B73fcHM0JJ", "reviewer": "Reviewer_vL1H", "summary": "This paper proposes a novel method for improving the accuracy of pairwise registration of 3D scans by extracting reliable information from graphs to filter out outliers. Graph-based methods typically leverage the fact that pairwise distances between points in a scan remain invariant under rigid transformations. However, in practice, deviations arise due to noise, outliers, and incorrect matches.\nTo address this, the paper employs a k-truss decomposition on a correspondences graph to isolate strong inlier correspondences. The proposed pipeline consists of the following steps:\\\n(a) Construction of a compatibility graph, and subsequently a distance-consistency graph, where correspondences are represented as nodes. Edges connect pairs of correspondences whose pairwise distances (within source and target scans) are consistent up to noise. The greater the consistency between two pairs, the higher the edge weight in the distance-consistency graph.\\\n(b) Low-scale sampling: To reduce graph size and computational complexity, the method uses consensus voting to retain correspondences (nodes) with a higher number of consistent neighbours. Non-maximal suppression is then applied to avoid excessive correspondences in dense regions, promoting spatial uniformity among selected inliers.\\\n(c) A k-truss decomposition is applied on the downsampled graph for various values of $k$, yielding subgraphs whose rigid transformations are estimated using weighted SVD.\\\n(d) Among the candidate transformations, the one maximizing a proposed spatial distribution score is selected. This score favors both registration accuracy and a well-distributed set of inliers across the scan.", "questions": "1. I believe the paper requires a major revision to address the misinterpretation of the k-truss algorithm. Since this component is central to the proposed methodology and the experimental results, the misunderstanding has significant implications. If the foundation itself is flawed, it becomes extremely difficult to interpret the reported outcomes. Moreover, both intuitively and technically, k-truss-based outlier filtering is generally weaker than clique-based methods such as MAC in capturing highly coherent inliers. However, the ablation results presented in Table 5 of the supplementary material show the opposite — k-truss outperforming MAC even when other settings are kept the same. The discrepancy vindicates the claim that the methodology is likely built upon a flawed interpretation of k-truss decomposition.\n2. It is not clear how much the original distance-consistency graph is reduced after the low-scale sampling step. As a result, it is difficult to assess the actual sizes of the subgraphs on which the rigid transformations are estimated. If the number of nodes (correspondences) in these subgraphs is too small, it raises concerns about the stability and reliability of the estimated rotations and translations obtained via weighted SVD. A more detailed quantitative information of the graph sizes after sampling for various datasets in the experiments would be crucial in assessing the value of this method. \n3. Additionally, an ablation study examining the method’s performance under different levels of graph sampling would be valuable. Such an analysis would help clarify the trade-offs introduced by the consensus-based low-scale sampling, both in terms of accuracy and computational efficiency of the subsequent k-truss decomposition.\n4. Can you comment on the weighting used in weighted SVD? It highly obscures the interpretation of the results, because a rotation error of 1 degree for the proposed method (in Fig.3 top row) also seems to be significant for a synthetic dataset when the noise has a very low $\\sigma=0.01$. A minor question: In Fig.3 in the top row, the rotation and translation errors for the proposed method seem to be constant till an outlier ratio of 80%, where other methods exhibit some variation. Is there any reason for this behaviour?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\\\n1.\tThe paper is well-written and easy to follow. \\\n2.\tThe method avoids the disadvantages of other graph-based techniques in 3d registration, namely the maximal clique selection is computationally expensive for larger 3d scans and the k-core method is not discriminative enough to get an accurate registration. This is because the proposed k-truss method is \\\na.\tGrounded by the theoretical analysis which shows that triangles of consistent correspondences are highly probable to be more accurate.\\\nb.\tIt has an efficient practical implementation in terms of the adjacency matrices. \\\n3.\tAlthough the triangle-based consistency is not entirely novel in computer vision, the way different parts of the pipeline are pieced together is intuitive and novel. \n\nWeaknesses:\n1. The authors appear to have misunderstood the standard definition and computation procedure for k-truss decomposition. Specifically, Algorithm 3 in the supplementary material, which is presented as performing a k-truss extraction, does not implement the correct iterative edge-peeling process, where edges participating in fewer than $k-2$ triangles are repeatedly removed until convergence. Instead, the proposed algorithm functions as a heuristic, and it does not produce true or even approximate k-truss subgraphs in general. Consequently, it is misleading to refer to the method as a k-truss decomposition, including in the paper's title and central claims. This foundational flaw undermines the technical correctness of the paper and renders its core results unreliable. \n2.\tThe Equation-2 is confusing. Is $S_{dist}(c_i, c_j)$ a real number or Boolean? The notation is not consistent from Equation-1 to Equation-2. There is no $q_i$, instead it is written in terms of the source and target scans.\n3.\tThe Theorem-1 seems to give only an intuitive understanding of the strength of triangle-based consistency. It could be made more rigorous and mathematically precise, which can then be interpreted based on different values of the threshold parameters involved. I am not sure if a “$\\gg$” based inequality is rigorous enough to be named a Theorem. \n4.\tIn Section-3.5, the centrality measure used in weighted SVD is undefined.\n5.\tSpatial distribution score function seems to be very complicated (Equation-14). It is not clear if there is any intuitive understanding on how it is derived. \n6.\tSome of the latest literature relevant to non-learning based point cloud registration are not cited or compared against: \"ARCS: Accurate Rotation and Correspondence Search\" by Peng et al., CVPR 2022; \"Adaptive Annealing for Robust Geometric Estimation\" by Sidhartha et al., CVPR 2023.", "was_revised": true, "final_justification": "While the authors position their method as a k-truss decomposition, it is, in fact, a heuristic inspired by k-truss that does not guarantee even approximate k-truss subgraphs. However, through the rebuttal, it became clear that this heuristic is more robust in practice and that only the surviving nodes—not the precise edge structure—are critical for their downstream task.\n\nThe paper offers a comprehensive approach to robust pairwise 3D registration, addressing challenges such as high outlier ratios, clustered correspondences, and poor spatial coverage. The use of triangle support is well-motivated both theoretically and empirically, leading to superior performance over the state-of-the-art baselines.\n\nSubject to clarifying the method's relation to k-truss more accurately in the paper, I support acceptance of the paper.", "rebuttal": "Dear Reviewer vL1H,\n\nThank you for your thorough review and detailed technical analysis. We sincerely appreciate your insights and the opportunity to clarify our methodology. We have carefully addressed each concern below.\n\n>**W1/Q1-k-truss Adaptation and Performance Analysis**\n\nWe sincerely thank the reviewer for the detailed analysis. Our approach represents a deliberate adaptation of k-truss principles specifically tailored for point cloud registration challenges. Similar to how methods like MAC adapt maximal clique concepts for registration tasks, we have adapted k-truss to better suit our application domain. \n\n**1. Our Adaptation vs. Standard k-truss:**\nThe reviewer is correct that standard k-truss decomposition uses iterative edge-peeling until convergence. However, our method intentionally adapts this concept for computational efficiency and registration accuracy (recall drops 15–20% due to over-pruning; runtime increases 3–5 times):\n- Standard k-truss: Iteratively removes edges with < (k-2) triangles until convergence; Designed for social network analysis where edges represent binary relationships\n- Our adaptation: Directly extracts subgraphs where each edge participates in ≥ (k-2) triangles；Specifically engineered for geometric consistency in 3D space where triangular support provides stronger constraints\n\nThis adaptation is deliberate—we leverage triangle-based truss structures to identify reliable correspondences. The iterative process, while theoretically pure, is computationally expensive and often unnecessary for registration tasks where we seek coherent correspondence groups rather than exact k-truss structures.\n\n**2. Precedent in Registration Literature:**\nOur approach follows established practice in the registration community:\n- MAC [35] adapts the maximal clique concept by searching for multiple maximal clique subgraphs in practice, ranging from the minimum guaranteed 3 nodes to larger sizes, then selecting the best transformation from these candidates\n- TEASER [36] adapts graph concepts for outlier-robust estimation without strict adherence to theoretical definitions\n- Similarly, we adapt k-truss principles while prioritizing practical effectiveness\n\nWe will revise the paper to clearly state we use \"k-truss-inspired decomposition\" to avoid any confusion about strict algorithmic adherence.\n\n>**W2-Equation 2 Notation and Consistency**\n\n(1) $S_{\\text{dist}}(c_i, c_j)$ is a Boolean value that indicates whether a pair of correspondences satisfies the rigid distance constraint: it equals 1 if the difference between the distances in the source and target point clouds is less than or equal to the threshold ($\\left| \\left| \\mathbf{p}_i^s - \\mathbf{p}_j^s \\right| - \\left| \\mathbf{p}_i^t - \\mathbf{p}_j^t \\right| \\right| \\leq 2\\tau$), and 0 otherwise. \n\n(2) We acknowledge that Equation 2 uses source (s) and target (t) superscripts while Equation 1 uses general correspondence notation. We will unify the notation throughout the paper to ensure clarity and consistency in our mathematical expressions.\n\n>**W3-Theorem 1 Rigor**\n\nWe understand the reviewer's concern about the mathematical rigor of Theorem 1. We will strengthen the theorem with precise probability bounds and threshold parameters in the revision, providing a more formal mathematical framework rather than the current intuitive inequality.  \n\n>**W5-Spatial Distribution Score Complexity**\n\nThank you for raising this important question about the spatial distribution score. We appreciate the opportunity to provide clearer intuition for this crucial component of our method.\n\n**Intuitive Understanding:**\nThe spatial distribution score addresses a fundamental challenge in point cloud registration: a transformation might achieve low error on a small, localized cluster of points while completely misaligning the rest of the point cloud. Our score elegantly prevents this by evaluating three complementary aspects:\n\n**1. Spatial Coverage (Coverage Ratio):**\nThis measures how well the inliers span the entire point cloud. Consider two scenarios:\n- Bad: 100 inliers clustered in one corner → Low coverage ratio\n- Good: 50 inliers distributed across the entire scan → High coverage ratio\n\nThe cubic volume ratio ensures that inliers must spread in all three dimensions, not just along a line or plane.\n\n**2. Inlier Quantity (Inlier Ratio):**\nThis captures the percentage of correspondences that are geometrically consistent. More inliers generally indicate a better transformation, but this alone could favor transformations that preserve outliers.\n\n**3. Registration Accuracy (Error Score):**\nThis measures how precisely the inliers align. Even with good coverage and many inliers, we need tight alignment for accurate registration.\n\n**Why This Combination Works:**\nThe spatial distribution score lies in how these components interact:\n- The multiplication ensures all three criteria must be satisfied with equal weight - a transformation cannot score well by excelling in just one aspect\n- The square root on coverage ratio provides diminishing returns, preventing the score from being dominated by coverage alone\n\n**Real-World Example:**\nImagine registering two partial scans of a room:\n- Method A: Perfectly aligns one wall (low error) but ignores furniture → High error_score, low coverage_ratio → Low total score\n- Method B: Roughly aligns entire room → Medium error_score, high coverage_ratio → Higher total score\n- Our method: Accurately aligns well-distributed points across the room → High scores in all components → Highest total score\n\nWe will add a visual figure in the revision showing how different spatial distributions lead to different scores, making this intuition immediately clear.\n\n>**W6-Literature Coverage**\n\nThank you for highlighting these important recent works. We acknowledge that these papers should be included in our literature review and will add them in our revision. We appreciate the reviewer bringing these omissions to our attention. Both papers represent significant contributions to non-learning based registration methods, and citing them will help readers better understand the current landscape of the field.\n\n>**Q2-Graph Reduction and Subgraph Size Analysis**\n\nThank you for this important question about graph sizes and transformation stability. We provide comprehensive quantitative details below.\n\n**1. Graph Reduction through Low-scale Sampling:**\nThe graph size reduction is controlled by our sampling ratio parameter β, which ranges from 0.1 to 0.5. This means:\n- With β=0.1: We retain 10% of initial correspondences (90% reduction)\n- With β=0.5: We retain 50% of initial correspondences (50% reduction)\n- The number of correspondences after filtering is deterministic based on β and the initial correspondence set size\n\n**2. Synergy between Sampling and k-truss Decomposition:**\nWe respectfully emphasize that our Consensus Voting-based Low-scale Sampling strategy is specifically designed to complement our k-truss decomposition:\n- It pre-filters unreliable nodes, significantly accelerating subsequent k-truss subgraph extraction\n\n>**Q3-Ablation Study on Graph Sampling**\n\nThank you for this valuable suggestion. We have conducted comprehensive ablation studies to examine the impact of different sampling ratios β on both accuracy and computational efficiency.\n\nPerformance vs. Sampling Ratio on 3DMatch (FCGF features):\n\n| Sampling Ratio β | Registration Recall | Runtime | Speedup |\n|------------------|---------------------|---------|---------|\n| 0.1| 93.10%| 0.12s| 8.3x|\n| 0.2| 93.53%| 0.16s| 6.3x|\n| 0.3| 93.84%| 0.20s| 5.0x|\n| 0.4| 93.78%| 0.25s| 4.0x|\n| 0.5| 93.41%| 0.31s| 3.2x|\n\nOur ablation study reveals a key insight: even when retaining only 10% of correspondences through consensus voting, we maintain 93.10% registration success and achieve 8.3x speedup. This demonstrates that our consensus voting selectively preserves the most geometrically consistent correspondences. Interestingly, higher sampling ratios perform slightly worse than β=0.3, as they retain more potentially erroneous correspondences that can negatively impact the subsequent k-truss decomposition.\n\n>**W4/Q4-Weighted SVD and Error Behavior**\n\nThank you for these insightful questions about our weighted SVD formulation and error behavior.\n\n**1. Clarification on Graph-based Weights for SVD:**\n\nWe apologize for the ambiguity in defining the centrality measure. Our centrality values are derived from the eigenvector centrality of the k-truss subgraph. Our weighting scheme follows established graph-based PCR methods by deriving weights from spectral analysis. We compute the eigendecomposition of the k-truss subgraph's compatibility matrix and use the principal eigenvector elements as correspondence weights in our weighted SVD. This ensures correspondences with higher structural importance have greater influence in transformation estimation.\n\n**2. Regarding the ~1° Rotation Error at Low Noise:**\n\nOur method prioritizes maintaining consistent accuracy across all outlier ratios. While specialized methods may achieve marginally better accuracy in ideal conditions (low noise, few outliers), they catastrophically fail at higher outlier ratios. This error remains competitive with or better than most baseline methods.\n\n**3. Remarkably Stable Error Behavior (0-80% Outliers):**\n\nThe reviewer correctly notes our unusually stable error profile:\n- 0-40% outliers:Rotation error 0.8° - 1.2° (±0.2° variation)\n- 40-80% outliers:Rotation error 1.0° - 1.5° (±0.25° variation)\n- Other methods:Show ±5° - 20° variations in the same range\n\nThe translation errors for our method are not constant but exhibit smaller variations that are difficult to discern in the current figure scale. Our k-truss structure consistently identifies geometrically coherent correspondences regardless of outlier percentage."}, {"review_id": "OuDPeRC78V", "reviewer": "Reviewer_XEsb", "summary": "The paper introduces  PointTruss , a novel graph-based method for point cloud registration. The method leverages the  k-truss  concept from graph theory to enhance the robustness and efficiency of correspondence selection in point cloud registration. Unlike traditional clique-based methods, which are computationally expensive (NP-hard) and overly restrictive, or k-core methods, which lack higher-order topological constraints,  PointTruss  uses triangle support (requiring each edge to participate in at least  k-2  triangles) to identify structurally consistent correspondences. The approach includes a consensus voting-based low-scale sampling strategy to reduce computational complexity and a spatial distribution score (SDS) to evaluate inlier coverage and uniformity, ensuring globally consistent transformations. The pipeline involves constructing a compatibility graph, applying k-truss decomposition, generating transformation hypotheses via weighted SVD, and selecting the optimal transformation using SDS. Extensive experiments on KITTI, 3DMatch, 3DLoMatch, and the Bunny model demonstrate that  PointTruss  outperforms traditional and learning-based methods in registration recall (RR), rotation error (RE), and translation error (TE), particularly in challenging scenarios with high outlier ratios or low overlap.", "questions": "See weakness.", "limitations": "The authors adequately address the limitations and potential negative societal impacts of their work in Appendix A.7, as noted in the response to Question 10 (PAGE16). They discuss limitations, likely including challenges in extremely low-overlap scenarios or computational constraints for very large point clouds, and consider societal impacts relevant to applications like autonomous driving or 3D reconstruction. The transparency in addressing these aspects is commendable and aligns with NeurIPS guidelines, rewarding the authors for being upfront about their work’s boundaries.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths：\n\n1.   Quality  : The paper presents a robust and well-validated method. Extensive experiments across diverse datasets (KITTI, 3DMatch, 3DLoMatch, and Bunny) demonstrate superior performance over state-of-the-art methods, both traditional (e.g., RANSAC, FGR, MAC) and learning-based (e.g., PointDSC, VBReg). The use of both FPFH and FCGF descriptors, along with quantitative metrics (RR, RE, TE) and qualitative visualizations (Fig. 5), strengthens the empirical evaluation. The theoretical foundation, including Theorem 1 and its proof in Appendix A.2, provides a rigorous justification for the k-truss approach.\n\n2.   Clarity  : The paper is well-organized, with a clear pipeline (Fig. 2) and detailed explanations of each component (graph construction, sampling, k-truss decomposition, and hypothesis evaluation). Mathematical formulations, such as the SDS function and k-truss definitions, are precise and supported by matrix-based implementations. The experimental setup, including datasets, evaluation criteria, and implementation details, is thoroughly described in Sec. 4.1.\n\n3.   Significance  : The method addresses a critical challenge in point cloud registration—balancing robustness and efficiency in the presence of outliers and low overlap. \n\n4.   Originality  : The introduction of k-truss to point cloud registration is novel, as it leverages higher-order topological structures (triangles) to overcome limitations of clique-based and k-core methods. The consensus voting-based sampling and SDS are innovative additions that enhance both efficiency and global consistency.\n\nWeaknesses\n\n1.  While the experimental results are strong, the paper lacks a detailed ablation study to quantify the individual contributions of the k-truss, consensus voting, and SDS components. This limits the understanding of which elements drive the performance gains. \n\n2.   The paper does not include validation experiments combining PointTruss with state-of-the-art deep learning methods (e.g., GeoTransformer or PareNet) on challenging datasets like 3DLoMatch, which could demonstrate its compatibility with modern learned features and further validate its robustness.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer XEsb,\n\nThank you for your thoughtful review and positive assessment of our work. We greatly appreciate your recognition of our method's novelty, theoretical rigor, and experimental validation. We are pleased to address your specific concerns below.\n\n>**W1-Ablation Study on Individual Components**\n\nWe appreciate the reviewer's request for detailed ablation studies. We actually conducted comprehensive ablation experiments, which are included in our supplementary material (Appendix A.5, Table 5). We apologize for not highlighting this more prominently in the main paper. Here we present the key results:\n\n**Table : Analysis experiments on 3DMatch and 3DLoMatch with FPFH and FCGF descriptors**\n| | CV | MAC | k-truss | SDS | inlier | RR3DMatch(%) | RR3DLoMatch(%) |\n|---|---|---|---|---|---|---|---|\n| **FPFH** | | | | | | | |\n| 1) | | ✓ | | | ✓ | 83.67 | 37.10 |\n| 2) | ✓ | ✓ | | | ✓ | 83.80 | 38.85 |\n| 3) | | ✓ | | ✓ | | 83.73 | 39.02 |\n| 4) | ✓ | ✓ | | ✓ | | 84.20 | 38.91 |\n| 5) | | | ✓ | | ✓ | 83.86 | 37.79 |\n| 6) | ✓ | | ✓ | | ✓ | 84.20 | 39.98 |\n| 7) | | | ✓ | ✓ | | 83.86 | 38.85 |\n| 8) | ✓ | | ✓ | ✓ | | **84.70** | **43.96** |\n| **FCGF** | | | | | | | |\n| 1) | | ✓ | | | ✓ | 91.68 | 57.44 |\n| 2) | ✓ | ✓ | | | ✓ | 93.59 | 59.46 |\n| 3) | | ✓ | | ✓ | | 93.53 | 59.01 |\n| 4) | ✓ | ✓ | | ✓ | | 93.72 | 59.96 |\n| 5) | | | ✓ | | ✓ | 93.40 | 58.00 |\n| 6) | ✓ | | ✓ | | ✓ | 93.72 | 59.63 |\n| 7) | | | ✓ | ✓ | | 93.66 | 59.40 |\n| 8) | ✓ | | ✓ | ✓ | | **93.84** | **61.64** |\n\n*CV: Consensus Voting-based Low-scale Sampling Strategy; MAC: Maximal Clique; SDS: Spatial Distribution Score*\n\n**Key Insights from Ablation Study:**\n- **k-truss vs MAC**: Comparing rows 2 and 8 (FCGF), replacing MAC with k-truss improves performance, especially on 3DLoMatch (+2.18%), demonstrating k-truss's superior ability to identify geometrically coherent structures\n- **Consensus Voting (CV)**: Adding CV consistently improves results across all configurations. For k-truss-based methods (rows 5→6, 7→8), CV provides significant gains on both datasets\n- **Spatial Distribution Score (SDS)**: SDS outperforms simple inlier counting across all experiments (e.g., rows 1→3, 5→7), validating the importance of considering spatial coverage for robust registration\n- **Synergistic Effect**: The full pipeline (row 8) achieves the best performance on both FPFH and FCGF descriptors, showing that all components work synergistically\n\nThese results clearly demonstrate that each component contributes meaningfully to the overall performance, with k-truss decomposition and consensus voting being the primary drivers of our method's superiority.\n\n>**W2-Combination with State-of-the-art Deep Learning Methods**\n\nThank you for this excellent suggestion. We have conducted experiments combining PointTruss with recent deep learning methods on the challenging 3DLoMatch dataset:\n\n**Table: PointTruss Integration with Deep Learning Methods on 3DLoMatch**\n| Method | Registration Recall |\n|--------|---------------------|\n| GeoTransformer | 75.0% |\n| GeoTransformer + MAC | 78.9% |\n| **GeoTransformer + PointTruss** | **79.5%** |\n| | |\n| PareNet | 80.5% |\n| **PareNet + PointTruss** | **82.2%** |\n\n**Key Observations:**\n- PointTruss successfully enhances both GeoTransformer (+4.5% recall) and PareNet (+1.70% recall) on the challenging 3DLoMatch dataset\n- The consistent improvements across different learned features validate PointTruss's compatibility with modern deep learning pipelines\n- PointTruss achieves comparable performance to MAC when integrated with GeoTransformer while being more computationally efficient\n\nThese results demonstrate that PointTruss not only works as a standalone method but also serves as an effective drop-in replacement for traditional robust estimators in deep learning pipelines, providing consistent improvements across different feature extractors.\n\nWe will include the result and discussions in our revised manuscript to provide a more comprehensive evaluation of our method's contributions and compatibility with state-of-the-art approaches."}]

Author rebuttal:

Meta-review: The authors have done a great job in rebuttal and interacting with reviewers. Most of concerns are well addressed, confirmed by the reviewers. The paper should be revised carefully based on considering, for example,
1) individual contributions of each key element in method,
2) comparison with more recent methods,
3) method clarity like misinterpretation of the k-truss algorithm
4) and other comments proposed by reveiwers
Decision: Accept (poster)