Karim Slimani
email: karim.slimani@isir.upmc.fr

Catherine Achard

Brahim Tamadazte

RoCNet++: Triangle-based descriptor for accurate and robust point cloud registration

Keywords: Point Cloud Learning, Registration, Geometric Descriptor, Attention Mechanism, Pose Estimation

come

Introduction

3D point cloud registration is a fundamental step in many robotics and computer vision tasks with applications in autonomous driving, visual servoing, augmented reality and medical imaging.

Given two overlapping sets of unordered points, point cloud registration aims to compute the rigid transformation that projects them onto each other. This inevitably involves estimating the point-wise correspondences between the two sets. Different methods attempt to solve this challenging step either incrementally by minimising a predefined metric, as in standard algorithms such as ICP [START_REF] Besl | Method for registration of 3-d shapes[END_REF] and RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF], or by estimating point cloud descriptors followed by nearest neighbour search in the descriptor space, as in the feature learning methods PRNET [START_REF] Wang | Prnet: Self-supervised learning for partial-to-partial registration[END_REF] and SpinNet [START_REF] Ao | Spinnet: Learning a general surface descriptor for 3d point cloud registration[END_REF]. This type of method aims to provide rigid transformation invariant features while dealing with the disorder aspect of the point cloud and taking advantage of the local surface properties. For example, PointNet [START_REF] Qi | Pointnet: Deep learning on point sets for 3d classification and segmentation[END_REF] projects the input data into a learned canonical space and uses a symmetric function to keep the output invariant to the order of the input points. In the same spirit, the widely used DGCNN [START_REF] Wang | Dynamic graph cnn for learning on point clouds[END_REF] proposes to capture local properties between points by introducing successive convolutional layers. They take as input graphs whose nodes are the K Nearest Neighbours (KNN) of each point. These graphs are dynamically updated in each layer by searching for the new KNN in the current feature space instead of the Cartesian coordinate space.

To learn the information on both local and global scales, most of the recent methods feed the extracted features into a transformer module as in DCP [START_REF] Wang | Deep closest point: Learning representations for point cloud registration[END_REF] and VRNet [START_REF] Zhang | Vrnet: Learning the rectified virtual corresponding points for 3d point cloud registration[END_REF]. Different models build on the classical transformers, adding richer geometric information such as the pairwise distances and triplet angles encoded by GeoTransformer [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] and the surface normal variations in RoCNet [START_REF] Slimani | Rocnet: 3d robust registration of point-clouds using deep learning[END_REF].

The features from the source point cloud are projected onto the target point cloud to create a similarity matrix used in a matching module that finds correspondences between the two point clouds. Sinkhorn algorithm [START_REF] Sinkhorn | Concerning nonnegative matrices and doubly stochastic matrices[END_REF] or dual softmax [START_REF] Li | Lepard: Learning partial point cloud matching in rigid and deformable scenes[END_REF] are often employed for this. Once correspondences have been established, the transformation is usually computed through methods like Singular Values Decomposition (SVD) as in MDGAT [START_REF] Shi | Keypoint matching for point cloud registration using multiplex dynamic graph attention networks[END_REF] or RANSAC as in Predator [START_REF] Huang | Predator: Registration of 3d point clouds with low overlap[END_REF]. Other methods predict point weights from the similarity matrix and estimate the transformation using a soft SVD as done in [START_REF] Wang | Deep closest point: Learning representations for point cloud registration[END_REF] or in SACF [START_REF] Wu | Sacf-net: Skip-attention based correspondence filtering network for point cloud registration[END_REF], where a skip-attention decoder is added to filter out false matches.

In this paper, we introduce RoCNet++, an improvement on RoCNet [START_REF] Slimani | Rocnet: 3d robust registration of point-clouds using deep learning[END_REF],

with two main contributions. The first one is a local triangle-based feature extractor that leverages the geometric properties of the point cloud, particularly the angle invariance of triangles under rigid transformation. This involves aggregating the three angles of the triangles formed by each point and its K nearest neighbours into a vector introduced into a simple Feed-Forward Neural Network (FFNN) to provide a highly discriminative representation. This vector, combined with several high-level features well-known in the literature, systematically improves their performances.

The second main contribution is the Farthest Sampling-guided Registration module, which estimates multiple rigid transformations given a set of matched points by constructing multiple smaller subsets of points using a sampling based on farthest point exploration. A rigid transformation is then computed on each subset and the best one is selected according to the number of inliers provided. Both contributions are evaluated on the point cloud registration problem using a well-established dataset, i.e., the ModelNet40 [START_REF] Wang | Prnet: Self-supervised learning for partial-to-partial registration[END_REF], by integrating it into RoCNet [START_REF] Slimani | Rocnet: 3d robust registration of point-clouds using deep learning[END_REF], as shown in (Fig. 1). We also propose to evaluate them on high-resolution point clouds by adopting the coarse-to-fine matching strategy proposed by [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] on KITTI [START_REF] Geiger | Are we ready for autonomous driving? the kitti vision benchmark suite[END_REF] and 3DMatch [START_REF] Zeng | 3dmatch: Learning local geometric descriptors from rgb-d reconstructions[END_REF] datasets.

The various upgrades proposed showed significant impact making the architecture more accurate in nearly all the performed experiments, scoring impressive matching results on the clean data of ModelNet40 with over 99% in three metrics: precision, accuracy and recall.

Related Work

3D Point Cloud Descriptors

Hand-crafted 3D descriptors aim to capture local point cloud information by incorporating various geometric characteristics such as distances, angles, surface normals, and curvature. Authors in TPSH [START_REF] Liu | Trigonometric projection statistics histograms for 3d local feature representation and shape description[END_REF] have demonstrated strong performance in terms of repeatability and robustness to noise by employing trigonometric projections to encode both spatial and geometric feature statistics in histograms while maintaining high efficiency compared to state-of-the-art methods. Learning-based methods emerged and became widely used for different 3D analysis tasks. For instance, PointNet++ [START_REF] Qi | Pointnet++: Deep hierarchical feature learning on point sets in a metric space[END_REF] that improves PointNet [START_REF] Qi | Pointnet: Deep learning on point sets for 3d classification and segmentation[END_REF] architecture, proposes a set of abstraction modules that capture multiple scales information by uniformly down-sampling the input to obtain a set of centroids, grouping the points using the nearest neighbours of each centroid and predicting a features vector based on a Point-Net layer. LGR-Net [START_REF] Zhao | Rotation invariant point cloud analysis: Where local geometry meets global topology[END_REF] introduced a novel attention module that allows combining local geometric attributes with the global point cloud topology by weighting the contribution of the two to consider the local region shape and thus ensures rotation-invariant features. Recent geometric registration methods for both deformable scenes [START_REF] Li | Lepard: Learning partial point cloud matching in rigid and deformable scenes[END_REF] and rigid scenes [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] adopted Kernel Point Convolution (KP-Conv) [START_REF] Thomas | Kpconv: Flexible and deformable convolution for point clouds[END_REF] as a backbone taking advantage of its efficiency on large-scale data and its ability to simultaneously extract features and down-sample the input point cloud.

RepSurf [START_REF] Ran | Surface representation for point clouds[END_REF] is a recent method proposing two variants of surface representation for point clouds using the second derivative from the Taylor series to describe the local geometry of each point. The first version utilizes features such as the normal vector, surface position, and normalized coordinates in triangles formed by points and their nearest neighbours. The second version proposes to learn a projection of the geometric features thanks to a Multi-Layers Perceptron (MLP) followed by a pooling operation. The method outperforms most of the state-of-the-art algorithms in segmentation, classification and 3D detection but exhibits limited robustness with noisy and disordered data. Triangle-NET [START_REF] Xiao | Triangle-net: Towards robustness in point cloud learning[END_REF] introduces various triangle-based func-tions to embed local structures by measuring edge lengths, interior angles, and surface normals at each vertex. These geometric features are transformed into a latent representation using graph aggregation. The method showed interesting robustness to noise and scale-invariance properties.

Registration

Iterative Methods

As most of the iterative algorithms for point cloud registration, Iterative Closest Point (ICP) [START_REF] Besl | Method for registration of 3-d shapes[END_REF] contains two main stages: point-wise matching and transformation estimation. ICP iteratively refines the estimated pose by alternately assigning points from the source cloud to their nearest neighbours in the target cloud and computing transformations using an SVD [START_REF] Besl | Method for registration of 3-d shapes[END_REF]. Recent variants of ICP, such as Go-ICP [START_REF] Yang | Go-icp: A globally optimal solution to 3d icp point-set registration[END_REF] and Fast ICP [START_REF] Zhang | Fast and robust iterative closest point[END_REF], have introduced techniques to enhance convergence speed and robustness to outliers while drawing inspiration from the original ICP. The main drawback of iterative methods is their sensitivity to initialization as they may converge to local minima. To handle this limitation, authors in [START_REF] Li | Deepsir: Deep semantic iterative registration for lidar point clouds[END_REF] have proposed to fuse learned features and geometric features that are updated by repositioning the input point clouds by a transformation estimated at each iteration. RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] is another commonly used iterative algorithm. It estimates the transformation by randomly selecting subsets of correspondences at each iteration, transforming the source cloud, and identifying inliers within a specified distance threshold. The global transformation is determined using the subset with the highest number of inliers. The authors of WSDesc [START_REF] Li | Wsdesc: Weakly supervised 3d local descriptor learning for point cloud registration[END_REF] employ differentiable voxelization to capture the local geometry. A voxel grid encodes in each voxel the probability of containing at least one point. Its orientation is defined by a local reference frame as its scale is learned by the network.

Learning-based Methods

Many registration methods are now based on learning. For example, R-PointHop [START_REF] Kadam | R-pointhop: A green, accurate, and unsupervised point cloud registration method[END_REF] extracts point descriptor invariant under rigid transformation using different neighbourhood sizes, thanks to a local reference frame (LRF) defined for the point by its nearest neighbours. The authors of WSDesc [START_REF] Li | Wsdesc: Weakly supervised 3d local descriptor learning for point cloud registration[END_REF] employ differentiable voxelization to capture the local geometry. A voxel grid encodes in each voxel the probability of containing at least one point. Its orientation is defined by the LRF and its scale is learned by the network. The method shows very interesting results on geometric registration benchmarks, however, the point-to-voxel operation may lead to significant computation costs for dense point clouds. DCP [START_REF] Wang | Deep closest point: Learning representations for point cloud registration[END_REF] and RTE [START_REF] Zhang | Self-supervised rigid transformation equivariance for accurate 3d point cloud registration[END_REF] propose to use features which are extracted with DGCNN [START_REF] Wang | Dynamic graph cnn for learning on point clouds[END_REF] and enhanced using attention mechanisms. A softmax applied to the dot product of these features leads to the matching that is introduced in a differentiable soft SVD [START_REF] Papadopoulo | Estimating the jacobian of the singular value decomposition: Theory and applications[END_REF] to predict the transformation. More recently, VRNet [START_REF] Zhang | Vrnet: Learning the rectified virtual corresponding points for 3d point cloud registration[END_REF] which is built in the same spirit, uses a correction-walk module to construct Rectified virtual Corresponding Points (RCPs) having the shape of the source and the same pose as the target. Although it demonstrated impressive results on ModelNet40, experiments showed the method encountered more difficulties in very low overlap and symmetric cases. Early 2023, RoCNet [START_REF] Slimani | Rocnet: 3d robust registration of point-clouds using deep learning[END_REF] introduces a surface normal variations encoding transformer based on sinusoidal functions [START_REF] Vaswani | Attention is all you need[END_REF]. This encoding is fed to a transformer which also takes as input point-wise features extracted with DGCNN. The matching is then solved as an optimal transport problem using Sinkhorn [START_REF] Sinkhorn | Concerning nonnegative matrices and doubly stochastic matrices[END_REF] allowing RANSAC to estimate the transformation in a limited number of iterations. PRNet [START_REF] Wang | Prnet: Self-supervised learning for partial-to-partial registration[END_REF] learns jointly keypoints detection, representation and matching and has been specifically designed to manage occlusion partial-to-partial point cloud registration. Geo-Transformer [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] detects superpoints and encodes their geometric structure using pair-wise distances and triplet-wise angles. The matching is performed by first searching the correspondence of super points before matching finerresolution dense points. The rigid transformation is then estimated in a local-to-global fashion.

Proposed Method

The registration method described in this article introduces two major improvements to the RoCNet [START_REF] Slimani | Rocnet: 3d robust registration of point-clouds using deep learning[END_REF] architecture, the first by adding a descriptor based on triangles invariance properties and the second one on the estimation of the rigid transformation between the point clouds using Farthest Sampling-Guided registration. An overview of RoCNet++ is depicted in Figure 1.

Background: the RoCNet Algorithm

The prior method RoCNet [START_REF] Slimani | Rocnet: 3d robust registration of point-clouds using deep learning[END_REF] relies on the following three main modules.

First, given two point clouds to register X ⊂ R 3×M and Y ⊂ R 3×N , the method utilizes the graph convolution based DGCNN [START_REF] Wang | Dynamic graph cnn for learning on point clouds[END_REF] to extract high dimensional features Φ X ⊂ R d×M and Φ Y ⊂ R d×N for each point from the two point clouds.

Second, a transformer is used to update features by applying successive self-attention and cross-attention mechanisms thanks to the classical equa- tions, respectively:

Φ X i = j=1 α ij (Φ X j W v ) (1)
Φ X i = j=1 α ij (Φ Y j W v ) (2)
where W v ∈ R d×d is the learned projection matrix for values, Φ X j and Φ Y j represent the feature vectors of the j th point from the point cloud X and Y in that order. In the case of self-attention, α ij coefficients are computed according to 3:

α ij = sof tmax j Å (Φ X i W s Q )(Φ X j W s K + n X i,j W s R ) T √ d ã (3)
where W s Q , W s K and W s R ∈ R d×d are the projection parameters for queries, keys and normal-based embedding n X i,j , d is the dimension of the features Φ X i . For cross-attention aggregation, α ij are computed by:

α ij = sof tmax j Å (Φ X i W c Q )(Φ Y j W c K ) T √ d ã (4)
where W c Q and W c K represent the projection parameters for queries and keys. The self-attention mechanism uses a surface normals encoder inspired by the frequency embedding introduced in [START_REF] Vaswani | Attention is all you need[END_REF]. The main motivation of the authors is to design a robust descriptor that captures the connections between points while being invariant to 3D transformations. Every couple of points x i and x j are linked with a vector g x i ,x j embedding the variation of their normal orientation n i and n j by sinusoidal functions whose frequency explicitly depends on the vector indices as shown in the following:

     g 2p x i ,x j = sin Ä ∠(n i ,n j ) τ ×10000 2p/d ä g 2p+1 x i ,x j = cos Ä ∠(n i ,n j ) τ ×10000 2p/d ä (5)
where p corresponds to the current value index of g x i ,x j , τ is a normalisation coefficient and d the dimension of the descriptor. A learned projection W s N ∈ R d×d is applied to get a final embedding n X i,j = g x i ,x j W s N . Let us call f X i and f Y j the final output features for the points x i ∈ X and y j ∈ Y , respectively. Their cross projection gives the similarity matrix S ∈ R M ×N . As reported in [START_REF] Shi | Keypoint matching for point cloud registration using multiplex dynamic graph attention networks[END_REF], a matching module relying on the Sinkhorn algorithm [START_REF] Sinkhorn | Concerning nonnegative matrices and doubly stochastic matrices[END_REF] estimates point-wise correspondences by incrementally normalizing S thanks to the iterations detailed in ( 6) and ( 6)

Iteration n : S ′ i,j = S i,j -log j exp(S i,j ) Iteration n + 1 : S i,j = S ′ i,j -log i exp(S ′ i,j ) (6)
The final matrix will be called S. A mutual top score searching along the two dimensions of S is used to find the hard correspondences between points which are used as input for a RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] that estimates the rigid transformation within 500 iterations.

Local Triangle-based Descriptor

The main idea developed in this work and illustrated in Figure 2, is to take advantage of the invariance of triangle angles when subjected to rigid transformations. Thus, whatever transformation is applied to a point cloud, the triangles formed by 3 points before and after the transformation will have exactly the same angles. If the interior angles of the triangles remain invariant under rigid transformations, they are also sensitive to noise and the smaller the triangles, the more sensitive they are. For each x i , we have therefore decided to weight the contribution of each triangle by its area using a softmax :

W i = sof tmax n Å 1 2 x i -x n1 i x i -x n2 i sin (α n ) ã , n ∈ [1, N t ] (7)
where x n1 i , x n2 i , x i are the three vertices of the n th triangle and α n is the angle at vertex x i .

The updated feature vector Θi ∈ R Nt×3 is obtained with:

Θi = Wi Θi ( 8
)
where Wi ∈ R Nt×3 is obtained by reshaping W i ∈ R Nt in order to get the same weight for the three angles of the same triangle Wi

= [W i , W i , W i ].
Finally, aiming for better robustness, we predict a high-dimensional descriptor Θ i ∈ R d/2 by feeding Θi to an FFNN which applies 1D convolutions, batch normalisation and ReLU function to the input.

We divide the dimension of the DGCNN [START_REF] Wang | Dynamic graph cnn for learning on point clouds[END_REF] descriptor Φ X ⊂ R d×M used in the baseline method RoCNet [START_REF] Slimani | Rocnet: 3d robust registration of point-clouds using deep learning[END_REF] by two ( ΦX ⊂ R

Φ X ←-[ ΦX , Θ X ] (9) Φ Y ←-[ ΦY , Θ Y ] (10)
Φ X and Φ Y are subsequently introduced in the self-attention and crossattention mechanisms detailed in (1), ( 2), ( 3) and (4) as in the baseline method RoCNet.

Farthest Sampling-guided Registration (FSR)

The second contribution we propose takes place at the end of the process when the rigid transformation is estimated from the matching points.

Inspired by RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] and the local-to-global registration proposed by [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF], we design a Farthest Sampling-guided Registration (FSR) module

H i = U i Σ i V T
i to obtain the rigid transformation as usually:

R i = V i U T 1 and t i = -R i X i + Y i ( 11
)
where X i and Y i are input and target point cloud for the subset CX i →Y i , R i and t i are the rotation matrix and the translation vector from X i to Y i . Using all subsets of matching points, different rotation matrices {R 1 , ..., R i , ..., R Ns } and translation vectors {t 1 , ..., t i , ..., t Ns } are obtained. As in [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF], FSR chooses the final transformation as the one which provides the maximum number of inliers from the initial set of correspondences C X→Y :

R X→Y , t X→Y = argmax i |C X→Y | n=1 R i x n + t i -y n < τ (12)
where x n and y n are a pair of matching points from C X→Y , R i , t i are the rotation and the translation estimated for the i th subset of points, |C X→Y | is the number of matched points and τ is a threshold for determining whether a pair consisting of a transformed point from the source point cloud and its estimated corresponding point from the target point cloud is an inlier or not.

Thus, FSR works similarly to RANSAC, except that the subsets used are not selected randomly, but are chosen to have points that are as far apart as possible, allowing a gain in efficiency by estimating an accurate transformation in just a few iterations. The intuitive idea is that the further apart the points are, the more robust the rigid transformation is estimated.

Experiments

The proposed architecture RoCNet++, with the addition of trianglebased descriptor and FSR registration, is evaluated for the first time on ModelNet40 [START_REF] Wu | 3d shapenets: A deep representation for volumetric shapes[END_REF] dataset. Secondly, we evaluate the added value of the new architecture on the KITTI database [START_REF] Geiger | Are we ready for autonomous driving? the kitti vision benchmark suite[END_REF] and 3DMatch indoor scenes [START_REF] Zeng | 3dmatch: Learning local geometric descriptors from rgb-d reconstructions[END_REF].

Since the feature extraction by DGCNN and the normal encoding transformer is encountering an out-of-memory issue due to excessive GPU consumption, we adopt the coarse-to-fine matching strategy proposed in GeoTransformer [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] on which we incorporate our descriptor by dividing the output dimension of the KP-Conv backbone used in the original paper and concatenating its predicted feature with those extracted by our triangle-based descriptor.

Specifically, we begin by collecting a low-resolution point set from each input point cloud, resulting in sets of superpoints X ⊂ R 3× M and Ŷ ⊂ R 3× N . We also gather higher-resolution sets (half the input resolution) to create dense points, X ⊂ R 3× M and Ỹ ⊂ R 3× Ñ . Next, we extract combined features from KP-Conv and the triangle-based descriptors for the superpoints before feeding them into the normal encoding attention mechanism. We denote the final features for the superpoints xi ∈ X and ŷj ∈ Ŷ as f X i and f Y j , respectively. To establish correspondences between superpoints, we compute a score matrix Ŝ ⊂ R M × N using the formula ŝi,j = exp

Ä -| f X i -f Y j |2 2 ä .
Finally, we construct the set of superpoint correspondences C X→ Ŷ by selecting the top-k scores from Ŝ. Once the superpoints paired, local patches P X i and P Y j are built around each xi ∈ X and ŷi ∈ Ŷ by assigning each dense point from X and Ỹ to its nearest neighbor from X and Ŷ respectively.

Inside each local patch, the dense point features f X i and f Y j are used to run an optimal transport algorithm as in [START_REF] Geiger | Are we ready for autonomous driving? the kitti vision benchmark suite[END_REF] and get a partial assignment matrix S. A mutual top selection on the obtained matrix gives us the dense correspondences C X→ Ỹ. For a fair comparison, we repeat the same experiments as reported [START_REF] Slimani | Rocnet: 3d robust registration of point-clouds using deep learning[END_REF] and [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] on ModelNet40, KITTI [START_REF] Geiger | Are we ready for autonomous driving? the kitti vision benchmark suite[END_REF] and 3DMatch [START_REF] Zeng | 3dmatch: Learning local geometric descriptors from rgb-d reconstructions[END_REF] datasets. The performances are extracted from [START_REF] Zhang | Vrnet: Learning the rectified virtual corresponding points for 3d point cloud registration[END_REF], [START_REF] Li | Wsdesc: Weakly supervised 3d local descriptor learning for point cloud registration[END_REF] and [START_REF] Kadam | R-pointhop: A green, accurate, and unsupervised point cloud registration method[END_REF] except Geo-Transformer [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] for which we use the official model implementation.

On ModelNet40, four measures will be presented as usually done in the related literature: the Root Mean Squared Error (RMSE) and the Mean Absolute Error (MAE) for translation and rotation. We use the Registration Recall (RR), the Relative Rotation Error (RTE) and the Relative Translation Error (RTE) metrics on KITTI and 3DMatch as reported in [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF].

KITTI odometry dataset [6]

It is composed of 22 sequences of point clouds obtained with a Velodyne HDL64 LiDAR. Ground truth poses are provided using GPS/INS system for the sequences 00 to 10 followed by an ICP [START_REF] Besl | Method for registration of 3-d shapes[END_REF] refinement and consider point cloud pairs that are at least 10 meters away for testing and downsampling them with a voxel size of 30 cm to obtain approximately 20k points per point cloud. We follow [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] to use the first six sequences for training, the seventh and eighth for validation and the last three sequences for evaluation.

3DMatch indoor scenes dataset [35]

To evaluate our method under challenging conditions with low-overlapping point clouds, we assess the matching and transformation estimation produced by RoCNet++ on the indoor scenes dataset 3DMatch. This dataset comprises 62 scenes, with 46 used for training, 8 for validation, and 8 for testing purposes. We adopt the same down-sampling procedure as in prior works [7; 18], where each input point cloud is down-sampled using a voxel size of 2.5 cm.

Implementation Details

The method is implemented with PyTorch on a Nvidia Tesla V100-32G GPU. On ModelNet40, the network was trained with Adam optimizer [START_REF] Kinga | A method for stochastic optimization[END_REF] for 30 epochs on clean data and for 100 epochs on noisy data with a learning rate of 10 -4 . The number of neighbours used for local triangle-based descriptor estimation is set to K = 12, leading to 66 triangles. The output dimension of DGCNN and the triangle-based descriptor is set to 64, producing a final concatenated descriptor with 128 dimensions. The farthest point sampling is operating N s = 5 times during testing, with N p = 100 points in each subset. The method is trained and supervised for feature extraction using the ground truth correspondences, while the transformation estimation bloc is parameter-free. For ModelNet40, the network is trained with a batch size of 4 examples using the gap loss [START_REF] Shi | Keypoint matching for point cloud registration using multiplex dynamic graph attention networks[END_REF] defined by:

L Gap = M i=1 log N +1 n=1 [max((-log Si, ī + log Si,n + α), 0)] + 1 + N j=1 log M +1 n=1
[max((-log Sj, j + log Sn,j + α), 0)] + 1 [START_REF] Li | Lepard: Learning partial point cloud matching in rigid and deformable scenes[END_REF] where α is a positive scalar set to 0.5, Si, ī and Sj, j are the scores for the ground truth true matches of the points x i and y j , respectively.

In the context of KITII and 3DMatch, we trained the model for 100 and 30 epochs respectively with a batch size set to 1 using Adam optimizer [START_REF] Kinga | A method for stochastic optimization[END_REF].

We used the overlap-aware circle superpoint matching loss denoted as L op , as reported in [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF]. To elaborate, for each superpoint patch P X i originating from the source point cloud, we conducted a search to find its positive sample Q + and negative sample Q -within the target point cloud. This search involved considering all patches with an overlap greater than 10% with P X i for positive samples and all patches with no overlap for negative samples.

L i op = 1 |P| |P| i=1 log   1 + p + j ∈Q + e √ (ri,j )θ + i,j (di,j -∆ + ) • p - k ∈Q - e θ - i,k (∆ --d k,i )    ( 14
)
where r i,j and d i,j are the overlap ratio and the distance in the superpoint features space between xi and ŷj respectively, ∆ + and ∆ -are positive and negative samples margins set to 0.1 and 1.4 respectively. Finally, θ + i,j = γ(d j,i -∆ + ) and θ - i,j = γ(∆ --d k,i ) represent the weights for each sample. In the case of the dense points matching loss, a set of ground truth superpoint correspondences C GT X→ Ŷ is first picked. For each couple k of these correspondences, a subset of correspondences M k is collected from the ground truth dense correspondences C GT X→ Ỹ to compute the negative log-likelihood loss.

L k d = - (x,y)∈M k log sk x,y - x∈Ii log sk x,m k+1 - y∈J k log si n k+1 ,y (15)
where I i and J i are the sets of dense points from the source and the target point clouds, respectively without any matching in the ground truth. The overall loss is the mean of the two previous losses. In the evaluation phase, FSR is performed for N s = 10 iterations for both 250 and 500 correspondences, when N s = 20 in all other cases. The sample size N p is determined by dividing the number of correspondences by N s . The refinement process from [START_REF] Bai | Pointdsc: Robust point cloud registration using deep spatial consistency[END_REF] is performed on the transformation estimated by FSR for 5 iterations on these two datasets.

Results on ModelNet40

ModelNet40 clean point clouds

Table 1 presents the registration performances on clean data from Mod-elNet40 with full and partial overlapping point clouds, respectively. RoC-Net++ achieves the best performance with significant improvements in each one of the four metrics evaluating the rigid transformation, reducing the translation and rotation errors with a factor greater than 50% in most of the metrics compared to the second-best method. An example of performed registrations is depicted in Figure 4. and for the RMSE in rotations estimation. RoCNet [START_REF] Slimani | Rocnet: 3d robust registration of point-clouds using deep learning[END_REF] and VRNet [START_REF] Zhang | Vrnet: Learning the rectified virtual corresponding points for 3d point cloud registration[END_REF] slightly overtake the proposed method in rotation for the MAE measure.

ModelNet40 noisy data

To evaluate the robustness of the proposed method, we conducted two experiments on noisy point clouds. The results on full point clouds reported in Table 3 shows that RoCNet++ outperforms most of the recent state-ofthe-art methods even in the presence of noise since the method is the best in 20 MAE(R) and MAE(t) while being the second best in the two other metrics

where GeoTransformer [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] outperforms the other methods in rotation errors while R-PointHop [START_REF] Kadam | R-pointhop: A green, accurate, and unsupervised point cloud registration method[END_REF] has the best performance in translation RMSE. Otherwise, the same Table shows that RoCNet++ is the best method in the case of noisy and partial overlapping input, thanks to its superiority in three over four metrics MAE(R), RMSE(t) and MAE(t) while being outperformed by only GeoTransformer [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] in RMSE(R).

KITTI Odometry Dataset

As discussed in Sec. 4, the large number of points contained in the KITTI dataset can lead to memory issues due to the combination of the Transformer and DGCNN. To tackle this problem, we adopted the approach presented in [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] using superpoints which consist of two steps. The first step is to match the superpoints extracted by KP-Conv. Secondly, dense correspondences are performed by creating local subsets of points for the paired superpoints. This process involves collecting neighbouring points for each superpoint. To generate feature vectors for each point, we concatenate the proposed triangle descriptor with the KP-Conv features. In this scenario, we apply the Transformer with normal variation encoding as reported in [START_REF] Slimani | Rocnet: 3d robust registration of point-clouds using deep learning[END_REF] at the superpoints level. Table 4 shows that our descriptor equals the state-of-the-art performance in Registration Recall (RR) and improves precision in Relative Rotation Error (RRE) while achieving the second-best performance in Relative Translation Error (RTE). In addition to this, we propose to compare the registration errors obtained using FSR, FGR [START_REF] Zhou | Fast global registration[END_REF], SVD, and RANSAC with different numbers of sampled correspondences by collecting 250, 500, 1000, 2500 and 5000 best similarity scores. The results reported in Table 5 show that FSR outperforms the other methods in rotation and translation, except in the case of 2500 samples where it ranks second (in translation) behind RANSAC. It can be highlighted that FSR surpasses RANSAC-50k, regardless of the number of samples. It can even outperform FGR in processing time (t) when using fewer than 1,000 samples. Some performed registrations are depicted in Figure 5.

3DMatch Indoor Scenes Dataset

We evaluate the performance of correspondence prediction using the same metrics employed in in [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] and [START_REF] Huang | Predator: Registration of 3d point clouds with low overlap[END_REF], i.e., Inlier Ratio (IR), which calculates the ratio of matched points with a distance smaller than τ 1 = 10 cm under the ground truth transformation; Feature Matching Recall (FMR), which represents the ratio of point cloud pairs with an IR above 5%. To assess the precision of the estimated transformation, we use three metrics: Registration Recall (RR); Relative Translation Error (RTE); and Relative Rotation Error (RRE). respondence sizes, where we select the top-k scores from the complete set of paired points, similar to the approach in [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF]. RoCNet++ surpasses Geotransformer [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF] and is second among all the methods and all cases. It matches the best scores when using 5000 and 500 points while performing best with 1000 sampled points and second with 2500 and 250 points. This suggests that RoCNet++ excels in challenging cases, consistently achieving a minimum of 5% inliers across a broader range of test examples. Inlier Ratio results are presented in Table 7 demonstrating that RoCNet++ produces accurate correspondences, as it consistently ranks second, following Geotransformer [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF], except for the sampling of 1000 points, where it achieves the highest scores.

For the registration results, Table 8 demonstrates the efficiency of FSR, which achieves the highest registration recall with fewer sampled correspondences (i.e., 250 and 500), while ranking as the second fastest method, just behind SVD. However, for larger sets of correspondences (i.e., 1000, 2500, and 5000), FSR is outperformed only by RANSAC-50k, which is approximately four times slower than our method. Finally, Table 9 shows that in terms of RRE and RTE, RoCNet++ achieves results comparable to Geotransformer [START_REF] Qin | Geometric transformer for fast and robust point cloud registration[END_REF], which is the best method across all metrics. RoCNet++ is narrowly outperformed by CoFiNet [START_REF] Yu | Cofinet: Reliable coarse-to-fine correspondences for robust pointcloud registration[END_REF] in RR.

ABLATION STUDY

In this ablation study, we show the improvements provided by the introduction of the triangle-based descriptor, by the weighting of the triangles and, finally, by the FSR method introduced.

Triangle-based Descriptor Ablation

Table 10, presents the matching performance of RoCNet++ in comparison to another version where the descriptor is replaced by FPFH [START_REF] Rusu | Fast point feature histograms (fpfh) for 3d registration[END_REF]. Additionally, we provide an analysis of RoCNet++ without the triangle-based descriptor and a version that combines FPFH and triangles. This analysis allows highlighting the impact of the triangles and its ease of incorporation into other descriptors. This analysis demonstrates that the use of triangles can clearly improve performances in both clean and noisy data. For example, the three metrics precision, accuracy and recall exceed the 99% in clean data.

Triangle Weighting Ablation

For a better understanding of the motivation behind the use of different weights for every single triangle, we provide a comparison between RoC-Net++ and the modified version on which the sof tmax is removed to let the same contribution for all triangles in the predicted descriptor. Table 11 highlights the important role played by the area weighting of the triangles in the presence of noise since the performance in all the matching metrics is improved. It is worth noting that in the case of clean data, the use of sof tmax has no huge impact on the matching performances which are already very high.

Influence of the Number of Triangles in the Descriptor

In this experiment, we study the influence of the number of K nearest neighbours used to construct the triangle-based descriptor. Let us notice that the number of neighbours imposes the number of triangles that is K(K-1)/2.

The analysis demonstrates that the best model for matching challenges is obtained for K = 12. We therefore kept this configuration throughout our studies.

Farthest Sampling-guided Registration (FSR) ablation

Finally, to validate the FSR algorithm effectiveness, we compare the registration results obtained using RANSAC, SVD and FSR for the same trained model on clean and noisy point clouds. Then, the global transformation is selected to be the one that yields the highest number of inliers.

The developed method was assessed using three well-established datasets, i.e., ModelNet40 (synthetic objects), KITTI (odometry), and 3DMatch (indoor scenes). Different scenarios have been set up to evaluate the performance of the method in the context of the state of the art: clean or noisy data under different overlap ratios. For the ModelNet40 data, RoCNet++ outperformed all the state-of-the-art methods in the case of clean data and in most cases of unfavourable conditions (e.g. noisy data). Finally, our method also performed well for the KITTI dataset, which is known to be challenging, improving 2 out of 3 metrics.

Although the proposed method has proved to be efficient for clean data, noisy data degrades performance significantly. It would be interesting to work on a new variant of the descriptor able to be more robust to noise. For instance, it would be interesting to replace the normals used in RocNet++ with EGI (Extended Gaussian Image), which have proved to be more robust to noise than simple surface normals. One other limitation is the complexity of handling large-scale databases such as 3DMatch due in particular to the use of transformers in the architecture. To remedy this, we proposed to adopt a coarse-to-fine matching strategy using a voxel-grid downsampling which may lead to the same computation cost problem depending on the size of the input point clouds. Hence, a significant reduction in the resolution of the point cloud, if required to address this issue, can lead to performance degradation as it may result in the loss of relevant local geometric information.

In future work, we plan to investigate new effective downsampling strategies and extend our approach to cross-modality (e.g., 2D-3D) registration and non-rigid correspondence estimation. Also, it would be interesting to consider the triangle-based descriptor in other applications such as segmentation and classification of points-clouds.

Acknowledgements

This work was supported by the French ANR program MARSurg (ANR-21-CE19-0026).

Figure 1 :

 1 Figure 1: Overview of the RoCNet++ pipeline.

Figure 2 :

 2 Figure 2: Triangle-based descriptor illustration for the point x i

d 2 ×M

 2 ) and concatenate it with the proposed triangle based descriptor, such that the dimension of the whole descriptor remains d:

Figure 3 :

 3 Figure 3: Farthest Sampling-guided Registration overview

  The synthetic ModelNet40 benchmark contains man-made point clouds representing 40 different classes split into 9,843 point clouds for training and 2,468 point clouds for testing. As in [28], 1024 points are sampled on each object and then transformed by applying a random rotation between 0 and 45 degrees around each axe and translating it along each direction by a random distance between [-0.5, 0.5] to create a target point cloud. A partial overlap is synthesized by sampling the 768 nearest neighbours of a random point in each point cloud. Finally, the 3D coordinates of each point are perturbed by adding a clipped Gaussian noise with a range of [0.05, 0.05], a zero mean and a variance of σ = 0.01.

Figure 4 :

 4 Figure 4: Illustration of some examples of performed registrations on ModelNet40 using RoCNet++ in case of clean data and full overlap versus the ground truth registrations.

Figure 5 :

 5 Figure 5: Illustration of some performed registrations on KITTI.

  proposed architecture is inspired by our recent RoCNet method, to which we have made two significant improvements. The first contribution concerns the setting up of a robust geometric descriptor encoding the 3D point as triangles formed by the K nearest neighbours. The extracted features correspond to the angles formed by each triangle, which are invariant to rigid transformations. These angles combined with the surface normals form the final descriptor. The second contribution of this paper refers to the estimation of the rigid transformation. To improve the accuracy of the estimated transformation, we introduced the Farthest Sampling-guided Registration (FSR) which allows estimating several rigid transformations for each subset of matched points obtained thanks to a furthest points sampling method.

Table 1 :

 1 Performances of RoCNet++ trained on all classes with clean point clouds onModelNet40.

			full overlap			partial overlap
	Method	rotation		translation		rotation	translation
		RMSE (↓) MAE(↓) RMSE(↓) MAE(↓) RMSE(↓) MAE(↓) RMSE(↓) MAE(↓)
	ICP [3]	12.28	4.613	0.04774 0.00228	33.683	25.045	0.293	0.2500
	DCP-V2 [27]	1.090	0.752	0.00172 0.00117	6.709	4.448	0.027	0.0200
	PRNET [28]	1.722	0.665	0.00637 0.00465	3.199	1.454	0.016	0.0100
	R-PointHop [9]	0.340	0.240	0.00037 0.00029	1.660	0.350	0.014	0.0008
	VRNet [37]	0.091	0.012	0.00029 0.00005	0.982	0.496	0.006	0.0039
	WSDesc [11]	-	-	-	-	1.187	0.975	0.008	0.0070
	GeoTransf [18]	0.232	0.075	0.00173 0.00063	0.327	0.118	0.002	0.0009
	RoCNet [23]	0.082	0.011	0.00047 0.00008	0.412	0.133	0.002	0.0002
	RoCNet++	0.028	0.003 0.00022 0.00002	0.035	0.061	0.0003 0.00006
	4.3.2. ModelNet40 unseen categories
	To access the generalisation performances of RoCNet++, errors on unseen
	categories are estimated and reported in Table 2. RoCNet++ outperforms

other methods in translation estimation (equality with VRNet

[START_REF] Zhang | Vrnet: Learning the rectified virtual corresponding points for 3d point cloud registration[END_REF]

in MAE Input Estimation

Table 2 :

 2 Performances of RoCNet++ trained on half the classes with clean and full overlap point clouds on ModelNet40.

	Method	RMSE(R)(↓) MAE(R)(↓) RMSE(t)(↓) MAE(t)(↓)
	ICP [3]	12.707	5.075	0.04853	0.00235
	DCP-V2 [27]	3.256	2.102	0.00631	0.00462
	PRNET [28]	3.060	1.326	0.01009	0.00759
	R-PointHop [9]	0.340	0.250	0.00039	0.00030
	VRNet [37]	0.209	0.028	0.00078	0.00009
	GeoTransf [18]	0.253	0.067	0.00173	0.00100
	RoCNet [23]	0.235	0.026	0.00180	0.00020
	RoCNet++	0.132	0.031	0.00023	0.00009

Table 3 :

 3 Performances of RoCNet++ trained on all classes of ModelNet40 with noisy data.

			full overlap			partial overlap
	Method	rotation		translation		rotation	translation
		RMSE(↓) MAE(↓) RMSE(↓) MAE(↓) RMSE(↓) MAE(↓) RMSE(↓) MAE(↓)
	ICP [3]	11.971	4.497	0.04832 0.00433	33.067	25.564	0.294	0.250
	DCP-V2 [27]	8.417	5.685	0.03183 0.02337	6.883	4.534	0.028	0.021
	PRNET [28]	3.218	1.446	0.11178 0.00837	4.323	2.051	0.017	0.012
	R-PointHop [9]	2.780	0.980 0.00087 0.00375	-	-	-	-
	VRNet [37]	2.558	1.016	0.00570 0.00289	3.615	1.637	0.010	0.006
	WSDesc [11]	-	-	-	-	3.500	0.759	0.006	0.004
	GeoTransf [18]	0.692	0.267	0.00519 0.00200	0.915	0.386	0.007	0.003
	RoCNet [23]	1.920	0.555	0.00260 0.00180	1.810	0.620	0.004	0.003
	RoCNet++	1.004	0.249	0.00133 0.00092	1.278	0.318	0.002	0.001

Table 4 :

 4 Registration performances on KITTI. The transformation is estimated using all the putative correspondences.

	Method	RTE(cm)(↓) RRE(deg)(↓) RR(%)(↑)
	Predator [7]	6.8	0.27	90.6
	FMR [8]	∼66	1.49	90.6
	SpinNet [1]	9.9	0.47	99.1
	CoFiNet [34]	8.2	0.41	99.8
	GeoTransformer [18]	6.8	0.25	99.8
	Ours	7.3	0.23	99.8

Table 5 :

 5 Registration performances on KITTI using different pose estimators (RTE (cm), RRE (degrees), and t(ms).

	#samples		5000			2500			1000			500			250
	RSAC5k	8.3	0.31	95	8.3	0.30	88	8.4	0.30	50	8.8	0.33	39	8.8	0.33	24
	RSAC10k	8.1	0.29	185	7.8	0.30	171	8.3	0.29	98	8.7	0.31	77	9.0	0.33	48
	RSAC50k	7.6	0.27	906	7.8	0.27	838	8.1	0.30	548	8.6	0.31	548	8.9	0.33	234
	FGR	9.4	0.38	56	9.4	0.38	55	8.4	0.35	53	8.8	0.36	52	9.4	0.40	51
	SVD	13.1	0.39	11	12.7	0.38	11	11.1	0.36	11	11.1	0.38	11	11.4	0.42	11
	FSR (ours)	7.3	0.27	171	7.4	0.28	143	7.6	0.28	50	7.9	0.29	37	8.2	0.30	27
	Input
	Estimation
	GT

Error RTE(↓) RRE(↓) t(ms) RTE(↓) RRE(↓) t(ms) RTE(↓) RRE(↓) t(ms) RTE(↓) RRE(↓) t(ms) RTE(↓) RRE(↓) t(ms)

Table 6 :

 6 Matching recall performances on 3DMatch versus number of correspondences.Table6displays the FMR results obtained using different sampled cor-

	# samples	5000 2500 1000	500	250
		Feature Match Recall (%)(↑)
	SpinNet [1]	97.6 97.2 96.8 95.5 94.3
	Predator [7]	96.6 96.6 96.5 96.3 96.5
	YOHO [26]	98.2 97.6 97.5 97.7 96.0
	CoFiNet [34]	98.1 98.3 98.1 98.2 98.3
	GeoTransformer [18] 97.9 97.9 97.9 97.9 97.6
	Ours	98.2 98.2 98.2 98.2 98.0

Table 7 :

 7 Inlier Ratio results on 3DMatch versus number of correspondences.

	#samples	5000 2500 1000	500	250
		Inlier Ratio (%)(↑)
	SpinNet [1]	47.5 44.7 39.4 33.9 27.6
	Predator [7]	58.0 58.4 57.1 54.1 49.3
	YOHO [26]	64.4 60.7 55.7 46.4 41.2
	CoFiNet [34]	49.8 51.2 51.9 52.2 52.2
	GeoTransformer [18] 71.9 75.2 76.0 82.2 85.1
	Ours	68.2 68.2 79.4 77.9 80.8

Table 8 :

 8 Comparison of different pose estimators with our pipeline on 3DMatch

		5000		2500		1000		500		250
	# samples
		RR(↑) t(ms)(↓) RR(↑) t(ms)(↓) RR(↑) t(ms)(↓) RR(↑) t(ms)(↓) RR(↑) t(ms)(↓)
	SVD	77.6	7	77.6	7	77.6	7	79.1	5	79.2	5
	FGR	85.1	107	84.5	101	85.3	101	86.4	096	85.9	089
	RANSAC-50k 90.2	560	90.4	550	90.2	506	89.6	339	88.9	235
	FSR (ours)	89.1	150	88.8	140	88.8	133	89.8	086	88.9	086

Table 9 :

 9 Registration errors obtained on 3DMatch using all the correspondences. RRE is in degrees, RTE is in centimeters and RR is in %

	Method	RR(↑) RRE(↓) RTE(↓)
	Predator [7]	89.0	2.029	0.064
	CoFiNet [34]	89.3	2.011	0.062
	Geotransf. [18] 91.5	1.625	0.053
	Ours	89.1	1.660	0.053

Input Estimation

Figure 6: Illustration of some examples of performed registrations on 3DMatch

Table 10 :

 10 Matching performances on ModelNet40 with partial overlap (P: Precision, A:

	Accuracy, R: Recall)
		clean data	noisy data
	Descriptor
		P(↑) A(↑) R(↑) P(↑) A(↑) R(↑)
	FPFH	92.1 84.6 88.3 72.1 71.0 71.2
	FPFH + Triangles	99.3 98.6 98.9 82.6 81.8 81.5
	DGCNN	98.0 97.2 97.6 85.8 85.9 85.5
	DGCNN+Triangles (ours) 99.9 99.8 99.8 89.4 89.4 89.2

Table 11 :

 11 Matching performances on ModelNet40 with partial overlapping input, where RoCNet++ ( †) is a version of the method without weighting of triangles.

		clean data	noisy data
	Method
		P(↑) A(↑) R(↑) P(↑) A(↑) R(↑)
	RoCNet++ ( †) 99.9 99.7 99.7 86.0 85.9 85.5
	RoCNet++	99.9 99.8 99.8 89.4 89.4 89.2

Table 12

 12

shows that FSR guarantees the best compromise for both cases: while RANSAC provides the best results on clean data but is less efficient in the presence of noise, SVD behaves oppositely, being efficient on noisy data but having surprising limits on clean data. The proposed Farthest Sampling-guided Registration (FSR) allows good performances in both cases by providing at least the second-best score in each metric.

Table 12 :

 12 Registration performances on ModelNet40 using RANSAC with 500 iterations, SVD and our FSR on partial overlapping data.

			clean data			noisy data
	Method	rotation		translation	rotation		translation
		RMSE (R)(↓) MAE(R)(↓) RMSE(t)(↓) MAE(t)(↓) RMSE(R)(↓) MAE(R)(↓) RMSE(t)(↓) MAE(t)(↓)
	RANSAC	<0.001	<0.001	0.0001	0.00002	1.513	0.633	0.004	0.003
	SVD	3.068	0.100	0.001	0.0001	1.268	0.349	0.002	0.001
	FSR (ours)	0.035	0.061	0.0003	0.00006	1.278	0.318	0.002	0.001


Hanna Abi Akl
email: hanna.abi-akl@dsti.institute

Hanna Abi

Akl Psychic

Manolis Koubarakis

Valentina Ivanova

Wen Zhang

Dimitris Plexousakis

Vassilis Christophides

; Heng

Haofen Wang

Andrea Nuzzolese

Evgeny Kharlamov

Zoi Kaoudi

; Gong

Heiko Paulheim

; Cogan

Eleni Tsalapati

Ioannis Chrysakis

George Vouros

Ioannis Karatzanis

; Lei

Terry R Payne

Valentina Presutti

Guilin Qi

María Poveda-Villalón

Bo Fu

Giorgos Stoilos

Laura Hollink

Jose Manuel Gomez-Perez

Daniel Garijo

Jeff Z Claudia D'amato

Irini Pan

Fundulaki

PSYCHIC: A Neuro-Symbolic Framework for Knowledge Graph Question-Answering Grounding

Keywords: Question Answering, Knowledge Graphs, Neuro-Symbolic Artificial Intelligence, Entity Linking, Linked Data, Language Models

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Knowledge veracity has always been one of the key topics of the Web [START_REF] Peng | Knowledge graphs: Opportunities and challenges[END_REF]. The ability to present users with a body of factual information to refer to is a challenge that continues to defy the growth of the web [START_REF] Peng | Knowledge graphs: Opportunities and challenges[END_REF]. In particular, the plethora of available information is plagued by the non-structured nature of this knowledge [START_REF] Peng | Knowledge graphs: Opportunities and challenges[END_REF].

One way the Semantic Web community addresses this issue is by constructing KGs which are structured repertoires of entities and relationships [START_REF] Peng | Knowledge graphs: Opportunities and challenges[END_REF]. These graphs encapsulate factual knowledge and allow users to retrieve it by navigating their different connections [START_REF] Peng | Knowledge graphs: Opportunities and challenges[END_REF]. The DBLP computer science bibliography is an example of such an effort that provides open bibliographic information on major computer science journals and proceedings [START_REF] Banerjee | Dblp-quad: A question answering dataset over the dblp scholarly knowledge graph[END_REF].

Aside from consolidating bodies of information, KGs provide a platform for information retrieval [START_REF] Peng | Knowledge graphs: Opportunities and challenges[END_REF]. In artificial intelligence (AI), question answering refers to the task of asking an AI agent a question and receiving an answer in return [START_REF] Ishwari | Advances in natural language question answering: A review[END_REF]. Large Language Models (LLMs) are popular agents that fill this role well due to their nature of ingesting huge amounts of information [START_REF] Pan | Large language models and knowledge graphs: Opportunities and challenges[END_REF]. However, this also makes them prone to giving out misinformation based on their inability to disseminate correct from incorrect knowledge [START_REF] Pan | Large language models and knowledge graphs: Opportunities and challenges[END_REF].

Integrating LLMs and KGs has emerged as a solution to mitigate the shortcomings of large language models [START_REF] Pan | Large language models and knowledge graphs: Opportunities and challenges[END_REF]. By querying a factual base of information, LLMs gain a way to validate their responses before sending them back to users [START_REF] Pan | Large language models and knowledge graphs: Opportunities and challenges[END_REF]. It is in this scope that the Scholarly QALD challenge presents its two sub-tasks, DBLP-QuAD and SciQA. We focus on DBLP-QuAD, a QA task over the DBLP1 KG. We distinguish two parts in the challenge: question answering, which requires participants to propose systems capable of retrieving specific information from the KG to answer a question, and entity linking, which requires participants to retrieve the list of entities related to a question.

In this paper, we show how a NS system can handle the tasks of QA and EL over a KG. The rest of the paper is organized as follows. In section 2, we discuss some of the related work. In section 3, we present the experimental setup. In section 4, we discuss the results. Finally, we present our conclusions in section 5.

Related Work

This section reviews some of the proposed systems designed for QA and EL over KGs.

Question answering over knowledge graphs

Several techniques have emerged to tackle the problem of QA over KGs. Zheng and Zhang make use of structured query patterns which involve identifying query graph candidates in the KG using EL and disambiguation and transforming them to SPARQL queries [START_REF] Zheng | Question answering over knowledge graphs via structural query patterns[END_REF] to answer questions. Pramanik et al. employs a similar approach by proposing a model that draws from relevant RDF triples to generate all possible query context graphs from which queries are created to answer natural language questions. Their findings result in an advancement in graph-based methods but prove their approach to be highly noisy [START_REF] Pramanik | Uniqorn: unified question answering over rdf knowledge graphs and natural language text[END_REF]. Sima et al. improve on this approach by leveraging graph algorithms to identify and rank domain-specific query candidates based on the node centrality of the relevant entities [START_REF] Sima | Bio-soda ux: enabling natural language question answering over knowledge graphs with user disambiguation[END_REF]. Zheng et al. go a step further in this direction by integrating semantic parsers to their query templates to refine the query-generation process. By aligning both natural language questions and query templates, they prove they can effectively answer complex and detailed questions [START_REF] Zheng | Question answering over knowledge graphs: question understanding via template decomposition[END_REF].

Nikas et al. combine graph-based techniques with neural-based methods to create a NS QA system [START_REF] Nikas | Open domain question answering over knowledge graphs using keyword search, answer type prediction, sparql and pre-trained neural models[END_REF]. In their work, they train a DistilBERT model based on an expected answer type to handle different kinds of questions [START_REF] Nikas | Open domain question answering over knowledge graphs using keyword search, answer type prediction, sparql and pre-trained neural models[END_REF]. The neural network also leverages SPARQL queries to gather facts for entity enrichment and boost its performance in extracting the correct answer from the provided context [START_REF] Nikas | Open domain question answering over knowledge graphs using keyword search, answer type prediction, sparql and pre-trained neural models[END_REF]. Cm et al. propose a similar pipeline by replacing the SPARQL endpoint with a supervised BERT model that performs relation extraction to add context information to the system [START_REF] Cm | Question answering over knowledge graphs using bert based relation mapping[END_REF].

Diomedi and Hogan propose a different approach by using neural machine translation to map the questions in natural language to SPARQL templates directly. They show that this method, coupled with tree-based entity disambiguation techniques, turns the QA problem to a slot-filling task and outperforms vanilla deep learning (DL) models [START_REF] Diomedi | Question answering over knowledge graphs with neural machine translation and entity linking[END_REF]. Aghaei et al. leverage a similar slot-filling pipeline on a domain-specific KG to demonstrate that it can reliably learn the pattern structures of the domain queries [START_REF] Aghaei | Question answering over knowledge graphs: A case study in tourism[END_REF].

In their work, Mavromatis and Karypis and Li et al. leverage graph networks to compute graph embeddings and compare them with the input question embeddings to target the correct answer entities [START_REF] Mavromatis | Rearev: Adaptive reasoning for question answering over knowledge graphs[END_REF][START_REF] Li | Improving question answering over knowledge graphs using graph summarization[END_REF]. Dutt et al. utilize graph convolution networks to score questions based on similarity and derive their corresponding graph paths to answer new questions [START_REF] Dutt | Perkgqa: Question answering over personalized knowledge graphs[END_REF].

Saxena et al. and Zuo et al. demonstrate how using KG embeddings can help solve multi-hop questions [START_REF] Saxena | Improving multi-hop question answering over knowledge graphs using knowledge base embeddings[END_REF][START_REF] Zuo | Improving question answering over knowledge graphs with a chunked learning network[END_REF]. Rony et al. propose a system whereby KG embeddings are stored in a vector database for faster retrieval and improved performance in answering complex questions [START_REF] Rony | Tree-kgqa: an unsupervised approach for question answering over knowledge graphs[END_REF].

Entity linking over knowledge graphs

Shi et al. present a survey on the techniques seen in EL over KGs. They regroup approaches into rule-based, machine learning (ML) and DL EL methods [START_REF] Shi | Knowledge-graph-enabled biomedical entity linking: a survey[END_REF]. In their work, Dubey et al. use rule-based methods by leveraging global traveling salesman approximate solver algorithms to disambiguate entities in large KGs [START_REF] Dubey | Earl: joint entity and relation linking for question answering over knowledge graphs[END_REF]. Steinmetz employ abstract meaning representation, a series of text dependency parsing rules, to identify and group sentences having the same meaning but different structures [START_REF] Steinmetz | Entity linking for kgqa using amr graphs[END_REF]. Using this technique, they perform data augmentation to enrich entity representation and achieve better performance on the EL task [START_REF] Steinmetz | Entity linking for kgqa using amr graphs[END_REF]. In a similar fashion, Radhakrishnan et al. use co-occurrences from large corpora to enrich existing KGs with entity information and create dense KGs as a basis for EL [START_REF] Radhakrishnan | Improved entity linking using densified knowledge graphs[END_REF].

Thawani et al. employ ML techniques by combining TF-IDF with Wikidata entries to generate feature vectors and score entity candidates accordingly [START_REF] Thawani | Entity linking to knowledge graphs to infer column types and properties[END_REF]. Li et al. make use of translating embeddings to encode entity-entity relationships and combine them with entity-relation embeddings to get better performance over KGs [START_REF] Li | Improving entity linking by introducing knowledge graph structure information[END_REF].

From a DL perspective, Huang et al. show that using BERT to calculate sentence embeddings over entities outperforms rule-based entity enrichment approaches [START_REF] Huang | Entity linking for short text using structured knowledge graph via multi-grained text matching[END_REF]. Banerjee et al. improve on this approach by concatenating entity embeddings with context using FastText embeddings in a pointer network entity linker structure designed to represent entities in a dense vector space and identify the correct one for any input entity [START_REF] Banerjee | Pnel: Pointer network based endto-end entity linking over knowledge graphs[END_REF].

Finally, Ding et al. propose a NS approach based on EL using SpaCy embeddings in a casebased reasoning by computing the cosine score between input entity embeddings and KG entity embeddings [START_REF] Ding | Jel: applying end-to-end neural entity linking in jpmorgan chase[END_REF]. The final entity is computed automatically according to the best matching embedding or manually labeled based on a threshold cosine score [START_REF] Ding | Jel: applying end-to-end neural entity linking in jpmorgan chase[END_REF]. Diomedi and Hogan experiment with a pipeline that integrates rule-based entity matching over DBpedia and Wikidata KGs and neural network models to associate the resulting entities to a fixed set from a designed KG [START_REF] Diomedi | Entity linking and filling for question answering over knowledge graphs[END_REF].

Experiments

Dataset description

The dataset considered for this shared task is divided in two parts: the DBLP-QuAD2 dataset which consists of 10000 question-SPARQL pairs and is answerable over the DBLP KG, and a dataset of 500 questions retaining the same format provided by the task organizers which will be referred to as seed data. We provide details for both datasets in the following subsections.

DBLP-QuAD data

DBLP-QuAD is a scholarly KGQA dataset with 10,000 question-SPARQL query pairs targeting the DBLP KG. DBLP-QuAD was created using the OVERNIGHT approach where logical forms are first generated from a KG. Canonical questions are then generated from these logical forms. The dataset is split into 7,000 training, 1,000 validation and 2,000 test questions. Each question-SPARQL pair consists of the following data fields: the id of the question (id), a string containing the question (question), a paraphrased version of the question (paraphrased_question), a SPARQL query that answers the question (query), the type of the query (query_type), the template of the query (template_id), a list of entities in the question (entities), a list of relations in the question (relations), a boolean indicating whether the question contains a temporal expression (temporal) and a boolean indicating whether the question is held out from the training set (held_out). Sample data is shown in Figure 1.

Seed data

Participants are provided with seed data to evaluate the performance of their systems on the QA and EL sub-tasks. This data is curated by the task organizers and consists of 500 random question-SPARQL pairs that comply with the same format as the DBLP-QuAD data. For the final evaluation, the organizers provided an additional set of 500 random questions containing only the question and its paraphrase. This dataset was used exclusively to score the performance of the participant systems in both sub-tasks.

System description

This section introduces our proposed system. It presents the system architecture and describes the training process in our experiments.

PSYCHIC model

Since the challenge presents itself as a QA task, we selected the DistilBERT-base uncased3 model to tackle it in an extractive QA setting. Extractive QA confines a model to selecting the appropriate answer chunk from a context given as input with the question. It also leverages some control over the model answers as opposed to generative QA which makes models generate the answer. Training a QA model involves giving the model an input composed of the question to be answered and a context that should contain the answer. In the scope of this shared task, we targeted two types of answers: the SPARQL query which should directly answer the given question and the list of entities for EL. We constructed the context to include both pieces of information and added information to guide the model regarding the nature of the question asked and the expected SPARQL answer: the query type and the template id provided in the DBLP-QuAD data. We also introduced symbolic information through a symbolic rule engine that inserts the special tokens [CLS] at the start of the context string and [SEP] between the different pieces of information in the context. These markers were added to ground the output of the model and enable it to discriminate between the different pieces of context information. The aim is to help the model learn the types of query structures and entities it will be asked to retrieve.

On the output side, we fine-tuned our PSYCHIC (Pre-trained SYmbolic CHecker In Context) model to return both the SPARQL query and the list of entities. We constructed the output as a string containing both pieces of information separated by the [SEP] token. We also introduced another symbolic rule engine which is a programmatic function designed to split the output string based on the [SEP] symbol to return the query and entities chunks separately. The PSYCHIC model architecture is presented in Figure 2.

Pipeline architecture

To answer both parts of the shared task, we need to return a result from a SPARQL query for the QA challenge and an entity list for the EL challenge. In that respect, the PSYCHIC model alone is not enough. The QA challenge defines an answer as the result of a SPARQL query, whereas PSYCHIC returns the queries themselves. This is a deliberate design choice since teaching a model to recognize patterned query structures is still an easier problem than teaching it to learn dynamic answers ranging from boolean values to lists of elements. Being able to correctly return the right query is essentially the hard part of the challenge, and the additional step to get the final answer consists in running the query returned by PSYCHIC using the SPARQL endpoint provided by the task organizers.

As such, we built the NS framework shown in Figure 3 to leverage the power of LLMs and symbolic reasoning. It takes as input the question-SPARQL pairs, processes them and prepares the question-context dataset needed for the PSYCHIC model. The model predicts the output in the form of a string containing the query, the separator [SEP] and the entity list. Two additional modules, the query and entity sanitizers, extract the relevant pieces of information from the output, namely the query and the entity list, by splitting the output string and validating the query and entity elements by matching them to their respective patterns. Through this sanitization process, these modules can perform error-correction to account for malformed strings returned by the model, e.g., transforming 'select distinct? answer where {? answer < https : / / dblp. org / rdf / schema # authoredby > < https : / / dblp. org / pid / 00 / 2941 > }' to 'select distinct ?answer where { ?answer <https://dblp.org/rdf/schema#authoredBy> <https://dblp.org/pid/00/2941> }' for the query and ['< https : / / dblp. org / pid / 00 / 2941 >'] to ['<https://dblp.org/pid/00/2941>'] for the entity list.

The resulting output from the query sanitizer module is a correctly-formed SPARQL query that is run using the SPARQL endpoint to return the expected final answer. The output of the entity sanitizer is the correctly-formed entity list. For the inference step, we distinguished two phases: the dev phase and the final phase. The dev phase corresponds to the phase when the first 500 random question-SPARQL pairs are made available by the organizers. The final phase represents the true system evaluation phase whereby the dataset used is the set of 500 random questions (and their paraphrases). The phases differ by the nature of the input given to the PSYCHIC model. In the dev phase, the context was constructed the same way as for DBLP-QuAD, i.e., following the [CLS] + QUERY_TYPE + [SEP] + TEMPLATE_ID + [SEP] + QUERY + [SEP] + ENTITIES pattern. In the final phase, since the only available information is the question and its paraphrase, we used an entity linker provided by the task organizers that leverages a t5-base language model with translating embeddings to return a list of predicted entities for each provided question. These results were concatenated using the symbolic rule engine to form a different context pattern, i.e., [CLS] + EL_RESULT1 + [SEP] + EL_RESULT2 + [SEP] + ... + [SEP] + EL_RESULTN for N returned entity results.

We used the F1-QA and F1-EL metrics, representing the F1 scores on each of the QA and EL sub-tasks respectively, to evaluate our system. All experiments were performed on a Dell G15 Special Edition 5521 hardware with 14 CPU Cores, 32 GB RAM and NVIDIA GeForce RTX 3070 Ti GPU.

Results

Table 1 displays the training results of the PSYCHIC model. Over 3 epochs, the model learns consistently with a perfect loss of 0 by the third epoch. Having integrated symbolic knowledge through the insertion of special tokens in the context proves to be a sound way to represent the different context chunks we want the model to learn. By the end of training, PSYCHIC can reliably return a complex output constituted of a query and an entity list for an input question.

The results of Table 2 seem to corroborate these findings. In the dev phase, the seed input structure is identical to that of DBLP-QuAD which means that PSYCHIC expects a similar context pattern. The model achieves a perfect score on both the QA and EL sub-tasks which suggests it is perfectly capable of discriminating query tokens from entity tokens. The results of the final phase are interesting in the sense that they seem to contradict this theory. The F1-QA score in particular suggests the model fails to predict any question query correctly. The reason for this bad performance lies in the fact that the input structure for the final phase set is radically different from the DBLP-QuAD and dev data as it contains no accompanying context for questions. Since PSYCHIC is an extractive QA model, it becomes very challenging for it to predict any kind of information without relevant context. We were not able to fill this context gap in the scope of this challenge. For the EL sub-task, we were able to fill the gap by using the entity linker predictions as missing context for the input questions. Because these context patterns were unseen by PSYCHIC during the training and dev phases, the F1-EL score achieved by the model is impressive since it reveals it can correctly identify valid entity pattern structures. This performance ranks PSYCHIC at third overall in the EL sub-task final standings as shown in Table 3.

Epoch Training Loss Step

Conclusion

In this shared task, we propose a NS framework to tackle QA and EL sub-tasks over a KG. We explore the effects of including symbolic learning in the context of LLMs and evaluate the overall performance on the sub-tasks for a changing context. In the future, we plan to extend these symbolic mechanisms to generative models such as retrieval augmented generation (RAG) pipelines.

Figure 1 :

 1 Figure 1: Example of DBLP-QuAD data

Figure 2 :

 2 Figure 2: PSYCHIC model architecture

Figure 3 :

 3 Figure 3: Solution system architecture

Table 3

 3 Final competition standings for the EL sub-task

	Validation Loss

https://blog.dblp.org/2022/03/02/dblp-in-rdf/

This section describes the framework for our experiments in terms of data, system and training process.

https://huggingface.co/datasets/awalesushil/DBLP-QuAD

https://huggingface.co/distilbert-base-uncased