Improving Graph Matching with Positional Reconstruction Encoder-Decoder Network
Authors: Yixiao Zhou
Ruiqi Jia
Hongxiang Lin
Hefeng Quan
Yumeng Zhao
Xiaoqing Lyu
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Matching
Positional Encoding

Abstract: Deriving from image matching and understanding, semantic keypoint matching aims at establishing correspondence between keypoint sets in images. As graphs are powerful tools to represent points and their complex relationships, graph matching provides an effective way to find desired semantic keypoint correspondences. Recent deep graph matching methods have shown excellent performance, but there is still a lack of exploration and utilization of spatial information of keypoints as nodes in graphs. More specifically, existing methods are insufficient to capture the relative spatial relations through current graph construction approaches from the locations of semantic keypoints. To address these issues, we introduce a positional reconstruction encoder-decoder (PR-EnDec) to model intrinsic graph spatial structure, and present an end-to-end graph matching network PREGM based on PR-EnDec. Our PR-EnDec consists of a positional encoder that learns effective node spatial embedding with the affine transformation invariance, and a spatial relation decoder that further utilizes the high-order spatial information by reconstructing the locational structure of graphs contained in the node coordinates. Extensive experimental results on three public keypoint matching datasets demonstrate the effectiveness of our proposed PREGM.

Improving Graph Matching with Positional Reconstruction Encoder-Decoder Network
Yixiao Zhou
Ruiqi Jia
Wangxuan Institute of Computer Technology Peking University
Wangxuan Institute of Computer Technology Peking University
Hongxiang Lin
Hefeng Quan
Wangxuan Institute of Computer Technology Peking University
School of computer science and engineering Nanjing University of Technology
Yumeng Zhao
School of Artificial Intelligence
Beijing University of Posts and Telecommunications
Xiaoqing Lyu"
Wangxuan Institute of Computer Technology, Beijing Institute of Big Data Research Peking University
Abstract
Deriving from image matching and understanding, semantic keypoint matching aims at establishing correspondence between keypoint sets in images. As graphs are powerful tools to represent points and their complex relationships, graph match- ing provides effective way find desired semantic keypoint correspondences. Recent deep graph matching methods have shown excellent performance, but there is still lack of exploration and utilization of spatial information of keypoints nodes in graphs. More specifically, existing methods are insufficient to capture the relative spatial relations through current graph construction approaches from the locations of semantic keypoints. To address these issues, we introduce posi- model intrinsic graph spatial
tional reconstruction encoder-decoder (PR-EnDee) structure, and present an end-to-ent graph matching network PREGM based on PR- EnDec. Our PR-EnDec consists of positional encoder that learns effective node spatial embedding with the affine transformation invariance, and spatial relation decoder that further utilizes the high-order spatial information by reconstructing the locational structure of graphs contained in the node coordinates. Extensive experimental results on four public keypoint matching datasets demonstrate the effectiveness of our proposed PREGM.
Introduction
Image matching is common and basic matching problem in multimedia and visual applications. The goal of image matching is to find a dense semantic content correspondence between two images, while feature-based matching is typical strategy solve the above problems, and in feature matching,
"Correspondence: 1vxiaoqingēpku..de edu. en. Author emails: {chnzyx, jorxx,jiarui jiariiiira@pppp... epkui edu. en, Linhongxlangdstu.p .ku. edu. 220106840131ehjsse edu. zhaoyumeng.5 311@bupt.......... edu. Ivxiaoging@pku. en
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the semantic keypoints in images are the most commonly used matching targets. Semantic keypoint matching aims at establishing correspondence between keypoint sets imgges, and it has been applied to a wide range of applications, such as object tracking and pose estimation
35 24
image retrieval 40
[39 3 etc.
The semantic keypoint data has the properties of non-Euclidean and unstructured for its disorder and discreteness, and graphs are powerful tools represent some complex objects and their interactions. Specifically, we take each semantic keypoint as a node, and build edges by heuristic methods according to the positions of nodes construct a corresponding graph. Graph matching is an effective method to solve the correspondence between the semantic keypoints in two images.
As deep learning models scalable and time-efficient, Graph Neural Networks (GNNs) are in- creasingly utilized in graph matching tasks, such as GMN [4), PCA
32 and BBGM 22
etc.
However, most graph matching approaches rely on the matching of basic items of graphs, i.e. computing affinities of nodes and edges, lack the mining and utilization of spatial context information hidden in the locations of keypoints as nodes of graphs. Recently, in task scenarios such as point cloud and knowledge graph, which the nodes in graphs have locational information, there are methods such as 12188] utilizing positional encoder to add the spatial information as additional features. However, current methods in graph matching domain lack such spatial positional information supplementation. As the positional information is closer to the intrinsic characteristic of the graph, is important to integrate spatial descriptions into graph feature embeddings in graph matching.
But utilizing underlying spatial information faces the following challenges: 1) Through taking key points as graph nodes and edges are associated with pairwise distance, such as delaunay triangulation, is not sufficient to mine hidden relative positional relationship. 2) The description of spatial information from coordinates of keypoints is relatively simple compared with conventional visual features, so needs more refined network structure to learn location information, order to facilitate subsequent feature fusion.
To address the two challenges mentioned above, we propose a positional reconstruction encoder- decoder network (PR-EnDec) in our PREGM by integrating more spatial information into semantic features and learning more distinguishable node features. The positional encoder in PR-EnDec aims to learn the encoding of node positional information with spatial invariance, specifically, the affine transformation invariance of node coordinates. The spatial relation decoder in PR-EnDec designed to recover the locational structure from the learned features of the encoder, and it reconstructs the relative distances and areas among the sampled nodes. To implement the joint learning of PR-EnDec about the intrinsic positional features in graphs, we, consequently, propose corresponding contrastive loss function and a reconstruction loss function in the encoder and the decoder respectively.
Our main contributions are summarized as follows:
We propose an end-to-end graph matching network, PREGM, which learns more distin- guishable node features, not only captures visual information in images but also models intrinsic spatial structure of keypoints by our designed PR-EnDec.
Our PR-EnDec consists of a positional encoder that learns effective graph positional encod- ing with affine transformation invariance, and a spatial relation decoder used enhance such learning by reconstructing the graph locational information such as relative distances and areas from learned positional encoding. We also design a corresponding contrastive loss function and reconstruction loss function in the encoder and decoder respectively to help learn effective node positional characteristics.
We evaluate our PREGM on four public keypoint matching datasets. Our experimental results demonstrate that PREGM outperforms state-of-the-art methods. We also present an ablation study, which shows the effectiveness of each component of PREGM.

---

2 Related Work
2.1 Graph Matching
Graph matching is always an effective strategy to find correspondence between semantic keypoints as graphs have sufficient representation ability for points and their complex relationships, and it can then be applied to downstream tasks such as image matching and understanding. As it is famous for being one of the practically most difficult NP-complete problems, researchers often use optimization algorithms to find an acceptable suboptimal solution for the graph matching problem. Traditional graph matching methods [17 20 36 generally use heuristic search algorithms to find suboptimal solutions.
Recent graph matching methods begin to combine combinatorial optimization with deep learning models. GMN 4 proposes an end-to-end graph matching framework, calculates the unary and pairwise affinities of nodes through CNN features, and also uses spectral matching as a differentiable solver to combine deep learning with graph matching. PCA [3 uses graph neural network (GNN) to learn and aggregate graph structure information into node feature representation, and introduces Sinkhorn network [I] as the combinatorial solver for finding node correspondence. BBGM 29 presents an end-to-end trainable architecture that incorporates a sate-of-theeand differentiable combinatorial graph matching solver, and introduces global attention mechanism to improve the matching performance.
Although the research on graph matching has made the above progress, the existing methods lack the distinguishing and informative graph spatial feature descriptions, and adaptive adjustment of node correspondence on graph matching. In this paper, we overcome these limitations by proposing a positional reconstruction encoder-decom (PR- (PR-EnDec) and designing contrastive learning and positional feature reconstruction procedure to guide the learning of graph matching.
2.2 Positional Encoding Graphs
Positional Encoding was first proposed in the Transformer model. In general, positional encoding refers to the process of encoding spatial relationships or topological information of elements as supplementary information in order augment the representational capacity of a model. The categorization of positional encoding can be further elaborated as follows: spatial positional encoding utilizes point location as input, while topological positional encoding employs the graph structure as input.
For spatial positional encoding, the point location is used input obtain high-dimensional embedding that contains effective locational information. Space2 (21 introduces theory and grid 2D multi-scale spatial positional encoder by using sinusoidal functions with different frequencies. PointCNN [18) designs a point set spatial positional encoder with Point Conv layers consisting of sampling layer, grouping layer, and aggregation layer. DGCNN (38 considers both global shape structure and local neighborhood information, and proposes spatial positional encoder layers containing dynamic graph neighborhood and edge convolution module. This paper proposes spatial position encoding on graphs by leveraging the characteristic of node representation containing coordinate information in image keypoint matching.
Topological positional encoding is specific to graph matching, where the graph structure is used as input obtain the topological embedding of the nodes. Maskey et al. [22] generalizes Laplacian- based positional encoding by defining the Laplace embedding to more general dissimilarity functions such as p-norm rather than the 2-norm used in the original formulation. INFMCS [16] designs a ioriuutttion-invarian node ordering based on closeness centrality, and effectively enhances the representation of graph structural features.
In recent years, there has also been research on spatial positional encoding in the field of graph matching. GCAN [13] utilizes SplineCNN [10] to encode positional information in 2D spatial space, and successfully capture structural information of the graph.
However, there remains the open question of how to further mine intrinsic spatial node information in graphs. In this paper, we propose a positional reconstruction encoder-decoder architecture to obtain effective node spatial positional encoding using 2D point location.
3

---

The framework of our PREGM. The visual features are extracted by "ggl6_ bn from images, and the positional encoding obtained by our pretrained positional encoder from graphs. The visual features and positional encoding of nodes are further fused to be fed into the following modules. Next, the fused features are updated and refined by the message passing module SplineCNN. Finally, we compute node affinity from updated features and adopt differentiable graph matching solver LPMP to find the correspondence matrix X.
Figure I:
3 Problem Formulation of Graph Matching
Given the keypoints in the images, each node generally associated with keypoint, and edges are built according the spatial position relationship between nodes when building an undirected graph. The graph is represented by G = (4, E, V, E):
V {U1, m. J denotes the node set.
* E' C V x V denotes the edge.
. V {vilv] E Rdd = 1,2, 2,
|V] denotes the node feature set.
E e 1,2, | denotes the edge feature set.
We the adjacency matrix & to represent the connections of nodes in undirected graph G, that is, A, = 1 iff there an edge esj = (ve. uy) e E.
Given two graphs G = (V1, R1, V1, E1) and G2 = (V2, R2, V2, E2), where V V2l n, the goal of graph matching is find the correspondence matrix X E {0, 1) " between nodes V, and V2 of the two graphs G1 and G2 wherein X;, = iff 02 E V1 corresponds to vy E V2.
The ultimate goal of the graph matching problem is to find the optimal node correspondence between two graphs G, and G so the graph matching problem is often considered as a quadratic assignment programming problem (QAP problem):
x argmaxx Kx,
where vXc(X) E {0, 10,1," X1, = In and X 1, x' denotes the desired node correspondence, and 1, denotes vector of n ones. K RD "xn""" is the corresponding affinity matrix:
sha ge ja.jo:
ii=jjaa
K Kiajj
else if A 0,
otherwise.
where s. represents the affinity between node features v, E V and Va E V2, s represents the affinity between edge features Cij E E and Cab Ez.
Methodology
The framework of our PREGM Network is illustrated in Figure The positional encoder module of pretrained PR-EnDec takes the coordinates of keypoints as input. It extracts a positional encoding vector for each keypoint in the images. Next, the positional encoding and the visual features extracted by vggl6_i bn are further fused. Then, the fused features are fed into the message-pase passing module to obtain the refined node feature. Finally, the node affinity is computed and processed by the L.MPP solver, generating the node correspondence matrix X introduced in the problem formulation.

---

Triangle Sampling
jelf-attention Reconstraction
diog
Arta
Arts
KLP
Irput Graph
Pasitional Enooder
Spotial Relation becoder
Figure The framework of our PR-EnDec network and the detailed structure of its positional encoder and spatial relation decoder.
As independent stage, pretrain the abovementioned positional encoder along with the spatial relation decoder module of PR-EnDec (as shown in Figure 2). The pretraining stage enables the positional encoder learn the high-order spatial information. The PR-EnDec consisting
modules,
Positional Encoder. This module takes the coordinates of keypoints as input and learns positional encoding. We first obtain the nigh-dimensiona coordinate embedding vectors by an MLP. The vectors are then fed into self-attention blocks and a normalization layer to learn positional encoding. The attention mechanism provides sequence independence and relative information of nodes. Besides, propose a contrastive loss for the encoder module. The loss function ensures the affine transformation invariance and learns the relative position information.
Spatial Relation Decoder. To reconstruct the spatial structure graphs, this module generates triangle assignments by distance-based random sampling. In each triangle assignment, the module takes positional encoding corresponding to the three keypoints as the input self-attention blocks. Next, the processed features are fed into MLPs, and the relative spatial relations of the three points are reconstructed. We adopt a Mcan Squared Error (MSE) loss to compare the ground truth relative spatial relations and the decoder's 's predictions.
4.1 Positional Encoder
The Positional Encoder only takes geometric features of keypoints as inputs,
V" [ufloo E R I....,n), n denotes the node geometric feature set.
Specifically, we utilize the 2D Cartesian coordinates of each node vs as its geometric feature of [x,, V:). The coordinate embedding sub-module embeds the geometric feature v into latent representations by a two-layer MLP, denoted as p². The updated geometric graph G = (V,p"(9)) is then fed into the following attention sub-module.
The attention sub-module consists of Im attention blocks (denoted as Alln)) and normalization layer (denoted as Norm), which updates latent representations of G An attention block is composed of multi-head self-attention layer and feed-forward layer, which captures the spatial feature of Go by aggregating the latent representations of each node.
v = p" (V8),
(3)
D Att 1,,1,,2 1,2, ..., 2......... 4m
The self-attention mechanism is sqquence-independens which is well suited for extracting high-order relative position information between nodes. There is normalization layer after attention blocks to allow the positional encoding of nodes to be better fused with visual features nodes the graph matching task. The final positional encoding obtained by the encoder module is denoted as Foos.
Fpos = Norm(Vg
(5)
Encoder Loss. For two given graphs G1 E,, and G (V1, E1, E1), the positional encoder generates the positional encoding denoted as F1 plss [f 1.2. [V] and F2 F { 1, 2, ..., [V]] respectively. We expect that for all matched node in graph G and node j in graph G2, the corresponding node positional encoding f and 13 should be similar. To let the encoder learn the relative position information of the nodes, we perform contrastive learning that
5

---

perseves the affine invariance of the positional encoding. Specifically, we adopt negative samples to conduct contrastive learning to avoid the encoder module outputs trivial node features that are all similar.
Therefore, we classify (G1; G2) as positive graph pair if V is affine transformed by V or the keypoints in V and v are one-by-one matched. On the contrary, (G1, G2) is negative graph pair if the keypoints are not matched.
For each training batch, the positive graph pair set GSp and negative graph pair set CS, are generated by node permuting affine transformation. Let I and FS,, denote the corresponding positional encoding pair set of G and GS, respectively, we propose a contrastive loss Lcon.
Sp=
Σ (oor pax E
eap(T sim F ()
(6)
Sn
Σ
exp(T sim(Fy post pos))
(Fo P EPs).
Sp
Leon Log(
(8)
Sp + S
where Sp and S,, denote the of the exponential of positive/negative pairs' similarity, respectively, Additionally, T denotes the temperature constant, and sim() denotes the cosine similarity.
4.2 Spatial Relation Decoder
To learn the oigh-order spatial information, we propose k-th-order geometric reconstruction assign- ments. Sampling points from the node set as an assignment, the corresponding geometric feature set is denoted as V/2 and positional encoding set as Fsub C Ppns- If decoder Dec takes Fsub as input, we claim the decoder provides k-th-order relative position information there exists non-degenerate geometric function F. F(V?) z Dec(Fsub). Specifically,
choose 3 and function JF with Euclidean distance and triangle area to learn the third-order relative position information.
The decoder module first samples three keypoints and obtains the corresponding geometric feature set V {ua, og. eg) and positional encoding set Frub {fa: fo. fc). The random sampling method related to the Euclidean distance from the previous sampled node to learn the relative information better, for the sampling method guarantees that the distances between the sampled nodes are not too far. Next, the sampled feature set Fsuh is fed into In attention blocks. The intermediate feature is denoted Feus = (far for fe). We utilize 2 MLPs, denoted pa and Pa. to approximate Euclidean distance and triangle area function, respectively. The reconstructed relative position information of the decoder is represented
RC ipa(fa pa. Pa) fe)l-
Let Dis denotes Euclidean distance and Area denotes triangle area function, RC's corresponding geometric function F is obviously
F(V?) diss, dis3, area].
(10)
where disl Dis(ug, vg),, dis2 Dis(e (vi vg), dis3 Dis(ug, ug), area Area(eg, og vg) denote ground-truth third-order relative position information for the decoder to reconstruct.
Decoder Loss. Since we calculate the approximated relative position information RC and the ground-truth RC F(V?), we propose the reconstruction loss Lrec:
Lree MSE(RC,
(11)
PR-EnDec Loss. Finally, combine the two losses to guide the training of our PR-EnDec jointly,
CPR-EnDer = Lcon + Lrec:
(12)
where À controls the relative importance of Lrea-
Through pretraining of PR-EnDec, we obtain an effective encoder for extracting spatial positional encoding for utilization in subsequent PREGM.

---

4.3 Graph Matching with PR-EnDec
Our training procedure is divided into two stages: In the first stage, we pretrain our PR-EnDec, and in the second stage of graph matching, our positional encoder module of PR-EnDec serves sub-module of the base graph matching model. providing learned positional encoding in the first stage.
After the training of PR-EnDec, freeze all parameters of the encoder module and put it in the training of graph matching tasks. The positional encoding Foos generated by the positional encoder module is fused with visual features F extracted by standard CNN:
Ffused Linear (Fos)) + Fuie.
(13)
where Linear denotes a linear layer.
Next, we feed the fused features into message-passingg module to produce the refined node features, and the message-passing module is implemented by a two-layer SplineCNN [10]. After the message- passing module, node and edge affinities are computed and passed to the differentiable graph matching solver LPMP in [25]. The resulting correspondence matrix X is compared to the ground truth X and the loss function is their Hamming distance:
LGM X (1 1-0xX*)-- + X
(1-
(14)
So far, the graph matching problem formulated previously is solved by our PREGM with the two sequential training phases: the PR-EnDec pretrain and the graph matching task.
5 Experiments
We conduct experiments on four public keypoint matching datasets and verify the effectiveness of each component of our PREGM by ablation study. We introduce the datasets, baselines, implementation details, and then report the results. The results demonstrate that our PREGM consistently outperforms all other approaches.
5.1 Datasets
We evaluate our PREGM on four public keypoint matching datasets: PascalVOC ObjectClass 4. SPair-71k
8
Willow
23 and IMC-PT-SparseGGN [14].
The PascalVOC dataset includes 20 classes of keypoints with Berkeley annotations 2 and images with bounding boxes. The PascalVOC dataset relatively challenging, since the scale, pose and illumination of instances in images are rich and diverse, and the number of annotated keypoints in each image also varies from to 23, When conducting experiments on the Pascal dataset, we follow the standard protocol 32 37 First, each object cropped according to its corresponding
bounding box and scaled to 256 x 256 px. Second, we use 7,020 images for training and 1,682 for
testing.
The Willow ObjectClass dataset contains images of five categories: face, duck, winebottle, car, and motorbike, the first three categories are from the Caltech-256 dataset [12], and the last two categories are from the Vas 2007 dataset [8] Each category contains at least 40 different images, and each image is labeled with 10 distinctive keypoints
the target object be matched. Following the [4] 32). we crop the images to the bounding boxes of the objects and rescale to 256 x 256 px, 20 images of each class selected during training, and the rest are for testing.
default setting in
The SPair-711 1k dataset is relatively novel dataset, which was recently published in the paper 23 about dense image matching. Spair-7lk contains 70958 image pairs of 18 categories from PascalVOC 2012 dataset [8] and Pascal 3D+ dataset [T.. Compared with the other two datasets, SPair7 1-k has the advantages of higher image quality and richer annotations which includes detailed semantic keypoints, object bounding boxes, viewpoints, scales, truncation, and occlusion differences image pairs. In addition, compared with Pascal dataset, SPair-71 7 1 removes two classes with ambiguous and poor annotations: sofa and dining table. Following [29), we use 53,340 image pairs for training, 5,384 for validation, and 12,234 for testing, and we also scale each image to 256x 256 px.
The MMC-PT-SparseGM dataset contains object categories and 25061 images 14, which gather from 16 tourist attractions around the world. The IMC-PT-Spaa MCC-PT-SparseGM benchmark involves matching
7

---

Table 1: Matching accuracy (%)
Pascal dataset.
Mehhl
End
Eour
beilcc
bus
-21
cdl
clur
Subl
dog
bosse
mibas
petie
punt
sleep
5154
tab
Ang
GNCUP
25.9
17.1
06.2
53.1
15.3
35.3
23.5
14.7
36.3
19.2
25.2
15.3
19.5
19.5
20.7
61.3
37.4
50.3
07.3
14.3
41.6
ABFF
32.9
40.4
47.3
54.5
50.4
15.1
46.7
56.3
40.9
33.9
16.3
34.8
50.5
59.6
50.3
63.2
57.0
50.2
70.5
41.3
42.7
GMN
31.9
47.3
31.9
4038
58.7
72.2
53.5
52.3
34.6
63.5
72.3
07.7
54.5
51.0
55.5
75.
49.5
4510
63.3
56.3
35.3
PCA
40.9
55.0
65.8
47.9
76.9
77.9
63.5
67.4
33.7
63.5
63.6
61.3
68.9
62.5
44.9
17.5
67.4
57.5
66.7
98.9
63.8
CHE
51.2
70.1
35.0
82.8
72.8
14.3
39.6
718
7000
71.8
06.3
64.8
09.9
06.4
K3.2
92.4
NOM
19.5
57.8
79.4
61.2
62.4
73.9
73.8
73.2
696
75.3
55.1
DIP-GM
76.0
76.2
T644
EA-NGM-12
79.4
76.8
77.1
79.5
ASAIR
14.3
79.5
86.1
89.3
96.0
38.8
78.9
79.5
64.9
77.5
77.1
96.5
957
811
COMMON
63.6
75.3
808
79.5
59.1
92.5
93.1
61
61.6
80.7
96.
82.0
61.6
79.5
06.6
98.9
T8.9
500
99.3
913
82.
63.5
76,4
79.
76.7
90.3
94.1
92.
834
71.
R33
92.4
814
820
15.0
09.1
98
754
963
96.1
93.1
841
Table 2: Matching accuracy (%) on Willow dataset.
Method
WT
duck
mbike
whottle
Avg
GNCCP
86.4
77.4
100.0
95.6
95.7
91.0
ABPF
88.4
80.1
100.0
96.2
96.7
92.3
GMN
X
74.3
82.8
99.3
71.4
76.7
80.9
PCA
X
X
84.0
93.5
100.0
76.7
96.9
90.2
CIE
82.2
81.2
100.0
90.0
97.6
90.2
NGM
84.1
77.4
99.2
82.1
93.5
87.3
98.3
90.2
100,0
98.5
98.1
97.0
DGMC
V
V
96.5
93.2
100.0
98.8
99.9
97.7
EAGM
x V
94.4
89.7
100.0
99.3
99.2
96.5
BBGM
X
96.9
89.0
100.0
99.2
98.8
96.8
100.0
99.1
97.4
97.4
96.8
100.0
99.8
96.8
98.2
Ours
/
97.8
99.0
100.0
99.6
100.0
99.3
larger scenes and take a step closer to the real-world downstream tasks. We take 13 classes as the training set and the other classes the test Experiments conducted the benchmark with 50 anchors.
5.2
Baselines and Metries
We compare PREGM with the state-of-the-are methods, including two types of baselines: (1)
non-learning methods GNCCP [20]. ABPF [6]; (2) 11 learning-basee methods GMN 44, PCA
32
CIE [43] NGM 33), DGMC 91 EAGM (27, BBGM (29, DIP-GM [42), IA-NGM-v2
26
ASAR
28 COMMON [19]. For a fair comparison, we follow previous work (32 and extract
node visual initial features from relu4 2 and relu5_1 1 of vgg 1alb___oo bn (00 via feature alignment. For
the input image pairs, we construct the edges of graphs by Delaunay triangulation (6 We adopt common metric matching accuracy to evaluate the experimental results, which computed as the number of correctly matched keypoint pairs averaged by the total number of all true matched keypoint pairs.
5.3 Experimental Settings
In our implementation, we build up our PREGM based on the state-of-the-art method 29 which presents an end-to-end trainable architecture that incorporates a state-of-the-arr differentiable combi- natorial graph matching solver. Our codes will be available in the future. In all experiments, we use the same set of hyperparameters. We employ Adam [15 optimizer with initial learning rate of 1 x 10-4 for PR- PR-EnDec, and x 10 for other models, and the learning rate is halved every three epochs. We empirically set I, = and L, = the encoder and decoder, and choose temperature constant 7 in Leon, and balance factor À 1/32 in LPR-EnDes We also set batch size 8 for VOC, Willow ObjectClass, and Spair- k datasets. Our learning procedure is divided into two stages: The pre-training of the PR-EnDec is uniformly conducted on the PascalVOC dataset. Then the graph matching framework trained on each dataset, while the parameters of the positional encoder are fixed. All experiments are run on single
GPU.
8

---

Table 3: Matching accuracy (%) Spair-71k dataset.
Mathol
bike
brd
heat
hoille
bats
car
chair
dog
bore:
mhike
person
paan
sheep
Irain
Avg
GMN
50.1
214
46.3
61.88
62.0
61.5
49.5
46.3
56.3
76.1
44.1
61.2
15.7
35.7
PCA
42.3
72.1
56.8
75.5
DGMC
54.8
44.8
80.3
70.9
65.5
90.1
78.5
66.7
66.4
73.2
66.2
66.5
65.7
59.1
98.7
68.5
84.9
98.0
72.2
BBGM
66.9
57.7
85.8
78.5
66.9
95.4
86.1
74.6
68.3
78.9
75.0
67.5
79.3
73.0
99.1
74.8
95.0
98.6
78.9
DIPGMM
63.7
54.5
89.0
80.9
64.2
95.0
873
73.5
71.0
79.7
73.4
68.1
75.1
71.2
98.8
76.9
96.0
99.2
78.7
Ous
71.3
61.0
89.6
$2.0
68.4
98.4
91.5
75.1
84.1
77.3
74,9
834
74,8
99.5
77.6
97.5
99.8
Table 4: Matching accuracy (%) on the IMC-PT-SparseGM.
Method
Reichstag
Sacre coeur Se_petess_ square _quure
Avg
GANN-GM
76.0
44.2
50.5
56.9
BBGM 99.1
79.5
86.8
88.4
Ours 99.8
84.8
87.6
90.7
5.4 Performance Evaluation
We conduct experiments on four public datasets: PascalVOC, WillowObjeet Class, Spair-71k and IMC-PT-SparseGM for the keypoint matching problem, and follow the most common experimental setting, where intersection filtering is applied to generate graphs with the equal size.
Firstly, we report the matching accuracy of the 20 classes and average accuracy on VOC dataset in Table [ where the best results are shown in bold. The results demonstrate that our model PREGM performs much better than all traditional graph matching methods, and also achieves better performance against state-of-ther -fftth--rt deep graph matching models with matching accuracy 84.1 1. And in the 20 classes of PasalVOC dataset, our PREGM has achieved the best results in the other 17 classes except for the boat, bottle and train class. As there are large differences in the scale, pose and illumination of matching objects, FascalVOCC is complex matching dataset, thus the matching accuracy of traditional graph matching methods is not more than 50%, and the performance of deep graph matching methods is relatively better. Our PREGM learns effective node spatial characteristics by PR-EnDec, so as to further improve the graph matching performance.
For the relatively simple WillowObject Class dataset, as shown in Table there are two different training strategies: PT and WT, which PT means matching frameworks are pre-trained on VOC, and WT means learning models are then fine-tuned on WillowObject Class Dataset. In this paper, we adopt two strategies: PT only, both PT and WT, and in both situations, our model achieves the best performance among other state-of-the-ar methods with matching accuracy 98.2% and 99.3%. The results again demonstrate the effectiveness of learning positional node features hidden in graphs in PREGM.
We also conduct experiments on Spair-7 lk dataset, as shown in Table 3 we compare our PREGM with deep learning methods GMN, PCA, DGMC, BBGM, and DIP-GM. Our PREGM performs best with matching accuracy 81.9%, and shows superiority in total 18 classes, which demonstrates the generalization ability of our model on different objects. SPair-71k dataset, as a relatively new dataset, has the advantages of high image quality, rich annotation, and fixed image pairs for matching, which is more convincing dataset. Thus our PREGM achieves the best results on the SPair-71k dataset, which further proves the effectiveness our PREGM.
Additionally, we evaluate our model on the IMC-PT-SSarseGMM dataset, as shown in Table our model demonstrates outstanding performance on this demanding benchmark. The results outshine the performance of the other methods, GANN-GM (34] and BBGM, by significant margin. In terms of the average accuracy across these landmarks, our model excels with an impressive mean accuracy of 90.7%. The IMC-PT-Sparsed and high partial rate, making one of the most comprehensive benchmarks for visual graph matching. Our approach, showcased in these results, demonstrates its ability to handle larger scenes and move closer to real-world applications, such as structure from motion.
dataset is characterized by its substantial number of images, nodes,
Table 5: Ablation Study on Pascal VOC dataset.
Method baseline 84.1%
wlo positional encoder wlo spatial relation deceder
recen .area
visual features
Accuracy
83,4%
81.7%
83,8%
82.7%
76.8%

---

Table 6: Parameter analysis of learning rate on Pascal
(x
9
10
11
12
Accuracy 83.2%
83.7%
83.8%
84.1% %
83.9%
83.7%
83.7%
5.5
Ablation Study and Parameter Analysis
To evaluate the effect of each component in our framework, we conduct comprehensive ablation studies with/without positional encoder, spatial relation decoder, and we also consider the two separate cases of no reconstruction of areas and relative distances the loss function of spatial relation decoder. Furthermore, we conducted additional ablation experiments by removing visual features evaluate the effectiveness of the spatial features extracted by model. The experiments are performed on PascalVOC dataset. As shown in Table compared with the baseline, the results demonstrate that all modules bring substantial performance gains, the reconstruction of relative distance is more important in the decoder, and the spatial relation decoder contributes most to the overall performance. Moreover, with the fact that only taking spatial features as node features can achieve relatively good performance, it further proves the effectiveness of the spatial features learned from our PR- PR-EnDec.
We also conduct parameter analysis to select hyperparameters. As shown in Table/6] PREGM achieves the best performance when learning rate that adjusting the learning rate causes an accuracy fluctuation of about 1%. For the balance factor in the loss function, when À 1/128, 1/32, and 1/8, the matching accuracy 83.7%. 84.1% 1,, and 83.3% 33 respectively. Thus we select À = 1/32 as our default setting, and the results show that our method is rather sensitive the choice of X, and our designed loss function in positional encoder and spatial relation decoder indeed improves the performance.
10-1 which is our default setting, and it also shows
Conclusion
In this paper. we present an end-to-ent novel deep graph matching network PREGM that Iearns more distinguishable node features by modeling spatial positional information in graphs. Our PREGM designs common encoder-decoder architecture consisting of a positional encoder that learns effective node positional encoding and a spatial relation decoder that reconstructs the positional structure of graphs. Our experiments and ablation studies on four public keypoint matching datasets demonstrate the state-of-the-arr performance of our method. The exploration direction of future work includes optimizing the loss function of the positional encoder extract purer spatial structural information and improve the feature fusion method to obtain better fused feature representation.
Acknowledgement
We acknowledge support from National Key R&D Program of China 1021ZD01133000)
References
[1] Ryan Prescott Adams and Richard S Zemel. Ranking via sinkhorn propagation. arXiv preprint 110. 1925, 2011.
[2] Lubomir Bourdev and Jitendra Malik. Poselets: Body part detectors trained using 3d human pose annotations. In 2009 IEEE 12th International Conference on Computer Vision, pages 1365-1372. IEEE, 2009.
[3] Zhe Cao, Tomas Simon, Shih-En Wei, and Yaser Sheikh. Realtime multi-person 2d pose estimation using part affinity fields. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7291-7299, 2017.
[4] Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs match. In Proceedings of the IEEE International Conference on Computer Vision, pages 25-32, 2013.
[5] Minsu Cho, Jungmin Lee, and Kyoung Mu Lee. Reweighted random walks for graph matching.
In European conference Computer vision, pages 492-505. Springer, 2010.
10

---

[6] Paolo Cignoni, Claudio Montani, and Roberto Scopigno. Dewall: A fast divide and conquer delaunay triangulation algorithm ed. Computer-Aided Design, 30(5):333-341, 1998.
[7] Amir Egozi, Yosi Keller, and Hugo Guterman. A probabilisstic approach to spectral graph matching. IEEE transactions on pattern analysis and machine intelligence, 35(1):18-3) 27, 2012.
[8] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. International journal of computer vision, 88(2):303-338, 2010.
[9] M. Fey, J. E. Lenssen, C. Morris, J. Masci, and N. M. Kriege. Deep graph matching consensus. In International Conference on Learning Representations (ICLR), 2020.
[10] Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splineenn: Fast geometric deep learning with continuous b-spline kernels. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 869-877, 2018.
[11] Ivan Gonzalez- Diaa,, Murat Birinci, Fernando Diaz-de Maria, and Edward J Delp. Neighborhood matching for image retrieval. IEEE Transactions on Multimedia, 19(3):544-555) 2016.
[12] Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. 2007.
[13] Zheheng Jiang, Hossein Rahmani, Plamen Angelov, Sue Black, and Bryan M Williams. Graph- context attention networks for siziev deep graph matching. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2343 2352,, 2022.
[14] Yuhe Jin, Dmytro Mishkin, Anastasiaa Mishchuk, Jiri Matas, Pascal Fua, Kwang Moo Yi, and Eduard Trulls. Image matching across wide baselines: From paper to practice. International Journal of Computer Vision, pages 517-547, 2021.
[15] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
[16] Zixun Lan, Binjie Hong. Ye Ma, and Fei Ma. More interpretable graph similarity computation via maximum common subgraph inference. arXiv preprint arXiv:2208 04580, 2022.
[17] Marius Leordeanu, Martial Hebert, and Rahul Sukthankar. An integer projected fixed point method for graph matching and map inference. Advances in neural information processing systems, 22, 2009.
[18) Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen. Pointenn: Convolution on x-transformed points. Advances neural information processing systems, 31, 2018.
[19] Yijie Lin, Mouxing Yang, Jun Yu, Peng Hu, Changqing Zhang, and Xi Peng. Graph matching with bi-level noisy correspondence, 2022.
[20] Zhi- Yong Liu and Hong Qiao. Gneep graduated nonconvexityand concavity procedure. IEEE Iransactions on pattern analysis and machine intelligence, 36(6): 1 125112588800 1267, 2013.
[21] Gengchen Mai, Krzysztof Janowicz, Bo Yan, Rui Zhu, Ling Cai, and Ni Lao. Multi- scale representation learning for spatial feature distributions using grid cells. arXiv preprint LrXiv:2003.00824, 2020.
[22] Sohir Maskey, Ali Parviz, Maximilian Thiessen, Hannes Stärk, YIli Sadikaj. and Haggai Maron. Generalized laplacian positional encoding for graph representation learning. In NeurIPS 2022 Workshop on Symmetry and Geometry in Neural Representations.
[23] Juhong Min, Jongmin Lee, Jean Ponce, and Minsu Cho. Hyperpixel flow: Semantic corre- spondence with multi-layer neural features. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 3395-3404, 2019.
[24] Hyeonseob Nam and Bohyung Han. Learning multi-domain convolutional neural networks for visual tracking. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4293-4302, 2016.
11

---

[25] Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil. Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.
[26] Tianxiang Qin, Shikui Tu, and Lei Xu. la-ngm: A bidirectional learning method for neural graph matching with feature fusion. Machine Learning, pages 1-27, 2022.
[27] Jingwei Qu. Haibin Ling, Chenrui Zhang, Xiaoqing Lyu, and Zhi Tang. Adaptive edge attention for graph matching with outliers. IJCAI, pages 966-972, 2021.
[28] Qibing Ren, Qingquan Bao, Runzhong Wang, and Junchi Yan. Appearance and structure aware robust deep visual graph matching: Attack, defense and beyond. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15263-15272, 2022.
[29] Michal Rolinek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vit Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In European Conference on Computer Vision, pages 407-424. Springer, 2020.
[30] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014.
[31] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[32] Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In Proceedings of the IEEE/CVF international conference on computer vision, pages 3056-3065 2019.
[33] Runzhong Wang. Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learn- ing lawler's 's quadratic assignment problem with extension to hypergraph and multiple-graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2021.
[34] Runzhong Wang, Junchi Yan, and Xiaokang Yang. Unsupervised learning of graph matching with mixture of modes via discrepancy minimization. IEEE Transactions of Pattern Analysis and Machine Intelligence, 2023.
[35] Tao Wang and Haibin Ling. Gracker: A graph-based planar object tracker. IEEE transactions on pattern analysis and machine intelligence, 40(6):1494-155 2017.
[36] Tao Wang, Haibin Ling, Congyan Lang, and Songhe Feng. Graph matching with adaptive and branching path following. IEEE Transactions on Pattern Analysis and Machine Intelligence, (0(12):2853-286) 2018.
[37] Tao Wang. He Liu, Yidong Li, Yi Jin, Xiaohui Hou, and Haibin Ling. Learning combinatorial solver for graph matching. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pages 7568-7577, 2020.
[38] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph enn for learning on point clouds. Acm Transactions On Graphics (tog), 38-5).11 2019.
[39] Paul Wohlhart and Vincent Lepetit. Learning descriptors for object recognition and 3d pose estimation. In Proceedings of the IEEE conference on computer vision and pattern recognition. pages 1109-3118, 2015.
[40] Jun Wu, Hong Shen, Yi-Dong Li, Zhi-Bo Xiao, Ming-Yu Yu Lu, and Chun-Li Wang. Learning hybrid similarity measure for image retrieval. Pattern Recognition, 46(1 46(11):2927-293) 2013.
[41] Yu Xiang, Roozbeh Mottaghi, and Silvio Savarese. Beyond pascal: A benchmark for 3d object detection in the wild. In IEEE winter conference on applications of computer vision, pages 75-82. IEEE, 2014.
12

---

[42] Zhoubo Xu, Puqing Chen, Romain Raveaux, Xin Yang, and Huadong Liu. Deep graph matching meets -xxed-integer linear programming: Relax at your own risk? arXiv preprint arXiv:2108.00333 2021.
[43] Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with bhdeeeel-ndeeeeddent embedding and hungarian attention. In International conference on learning representations, 2019.
[44] Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 2684-2693, 2018.
13


Reviews:
[{"review_id": "Kfx6gpK9QW", "reviewer": "Reviewer_Pb59", "summary": "The authors introduce a positional reconstruction encoder-decoder (PR-EnDec) to model intrinsic graph spatial structure, and present an end-to-end graph matching network PREGM based on PR12 EnDec. The PR-EnDec consists of a positional encoder that learns effective node spatial embedding with the affine transformation invariance, and a spatial relation decoder that further utilizes the high-order spatial information by reconstructing the locational structure of graphs contained in the node coordinates.", "questions": "What is the purpose of graph matching? Any use case related to NeRFs or generative models?\n", "limitations": "I have no idea about the limitations of graph matching.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I haven not personally conducted any research on graph matching, but the idea look interesting to me.\nI suggest AC rely on other more experienced reviewer in this area.", "weaknesses": "My knowledge of graph matching is limited and therefore cannot find any weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your time and effort in reviewing our paper on graph matching. Your feedback is invaluable to us as it provides insights that contribute to the overall quality of our work.\n\nTo address your question about the purpose of graph matching, we are glad to provide a brief explanation. Graph matching plays a crucial role in various fields, including computer vision, image analysis, and pattern recognition. Its purpose is to establish correspondences between nodes of different graphs, facilitating tasks such as object recognition, image alignment, and shape matching.\n\nOnce again, thank you for your time, and we look forward to incorporating your suggestions and improving our work based on your feedback."}, {"review_id": "tTdWt4FGwR", "reviewer": "Reviewer_pkGJ", "summary": "This paper presents a new method to improve graph matching by supplementing visual features with positional encodings. Specifically, an encoder-decoder model is pre-trained to reconstruct a graph’s relative spatial relation based on node coordinates only. The encoder is additionally trained under a contrastive loss to classify positive or negative graph pairs. The pre-trained encoder provides the positional encodings, which is used to compute node and edge affinities with CNN visual features jointly. The proposed method is validated on three graph matching datasets: PascalVOC, WillowObject Class, and Spair-71k, with the best performance among all compared methods. Ablation study shows the contribution of different components in the proposed method.\n", "questions": "1. For the visual features, why is VGG-16 used instead of a deeper model like ResNet-50?\n2. For the decoder reconstruction target, is the original coordinate, which is a natural choice, a good choice? If not, why?\n", "limitations": "This paper has not discussed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed positional reconstruction encoder-decoder network is a simple and effective method to extract positional features. Reconstructing the spatial relation between nodes in a graph is a good target for the encoder-decoder network.\n2. This paper proposes to use positional encodings to improve graph matching, which proves to be effective on three datasets. This is also in line with conclusions of some existing research, such as the vision transformer, in which positional encodings are shown to be very important. This work suggests all future work on graph matching can benefit by adding positional features.\n3. The ablation study has shown the importance of each component in the proposed method, including both encoder and decoder, the reconstruct targets, and visual features. Parameter analysis also provides the reason for the choice of hyper-parameters.\n4. This paper is well-written and easy to follow.\n", "weaknesses": "Some technical details of the proposed method are not clarified. What are the detailed configurations of the multi-head self-attention layers? How are positive and negative pairs for the encoder generated? Are the visual features sampled for each node of the graph? How are the graph edges defined? How are the edges used in the encoder? How are the node and edge affinities computed?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thorough review and valuable feedback on our paper. Your insightful comments have greatly contributed to the refinement and clarity of our work.\n\nWe are pleased to address your specific concerns and queries:\n\nDetailed Configurations of Multi-Head Self-Attention Layers: For each multi-head self-attention layer, we employed an attention mechanism with 8 attention heads and a feed-forward network. This configuration allows the model to capture complex relationships between nodes effectively.\n\nGeneration of Positive and Negative Pairs for the Encoder: Positive pairs are identified when graph $\\mathcal{G}^2$ is affine transformed by graph $\\mathcal{G}^1$, or keypoints in both graphs are one-to-one matched. Negative pairs correspond to situations where keypoints in two graphs are shuffled and not one-to-one matched. We expect the corresponding node positional encoding $f_i^1$ and $f_i^2$ should be similar only if node $V_i^1$ matches $V_i^2$.\n\nSampling Visual Features for Each Node of the Graph: Yes, we sampled visual features for each node. We computed feature vectors using the relu4\\_2 and relu5\\_1$ layers of the VGG16 network. These feature vectors are spatially interpolated to correspond to keypoints using bi-linear interpolation.\n\nDefinition and Use of Graph Edges in the Encoder: The edges within each graph are generated through Delaunay triangulation. However, edge information is not incorporated into the position encoder. Instead, it plays a key role in the message passing module during the graph matching phase.\n\nComputation of Node and Edge Affinities: Node affinities are calculated using a similar approach to the\nunary costs in BBGM. Specifically, we compute $c^v_{i,j}=\\sum_kf^v_s(i)_ka_kf^v_t(j)_k$, where $f^v_s(i)$ and $f^v_t(j)$ represent feature vectors for vertices $i$ and $j$ in the source and target graphs, respectively. The affinity $a$ is obtained using a one-layer neural network from the global feature vector $g$ extracted by max-pooling the final VGG16 layer. Edge affinities, on the other hand, are not employed in our model.\n\nChoice of VGG-16 over Deeper Models: We used VGG-16 as a convention inherited from PCA. While we experimented with replacing it with ResNet-50, the improvement was not significant, leading us to stick with VGG-16 for consistency.\n\nDecoder Reconstruction Target: The choice of using original coordinates as the reconstruction target has its rationale. While the translation invariance is somewhat compromised, we focus on capturing high-order spatial relationships between nodes. First-order spatial information as a target would reduce the encoder's utilization of spatial information, diminishing the model's overall performance.\n\nOnce again, we express our gratitude for your insightful feedback. Your constructive critique has helped us enhance the clarity and effectiveness of our proposed method. We are committed to addressing the remaining technical details and ensuring a comprehensive discussion of limitations in the revised manuscript.\n\nThank you for your dedication to improving the quality of scientific research."}, {"review_id": "dn451W7rs4", "reviewer": "Reviewer_TCc6", "summary": "The paper introduces an improved method for graph matching in semantic keypoint matching - the Positional Reconstruction Encoder-Decoder Network (PR-EnDec) and an end-to-end graph matching network PREGM. PR-EnDec efficiently learns node spatial embedding and reconstructs the locational structure of graphs from node coordinates. PREGM models the intrinsic spatial structure of keypoints and captures visual information, enhancing node positional features. Tests on three keypoint matching datasets showed improved performance over existing methods, with an ablation study demonstrating the effectiveness of each PREGM component.\n", "questions": "Please see the weaknesses part in the above section. ", "limitations": "Limitations are not described in this paper, and potential negative societal impact is missing.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper introduces an innovative PR-EnDec model to effectively capture and utilize the spatial context information hidden in the locations of keypoints, which has not been adequately addressed in existing methods. The PR-EnDec incorporates a positional encoder and a spatial relation decoder, which not only capture the relative spatial relations but also learn the affine transformation invariance, enabling the network to learn more refined location information. Given the widespread use of image matching in various fields, such as object tracking, image retrieval, and pose estimation, the proposed improvements could have significant impacts on a variety of applications.", "weaknesses": "1. Lack of Visualizations\n\nWhile the paper presents an innovative approach and comprehensively assesses the performance of the proposed method, I would like to express a concern regarding the absence of sufficient visualizations. Visualizations can offer empirical evidence of model performance and further support the reported quantitative results. For instance, visual representations of keypoint matching results can provide intuitive insights into how the proposed method works in practice and highlight its ability to handle complex spatial relationships. In light of the above, the lack of sufficient visualizations in this paper might impede comprehensive understanding and thorough evaluation of the presented method. Therefore, I would suggest incorporating necessary visual aids into the paper to provide a more effective and comprehensive presentation of the methodology, the performance, and the practical implications of the proposed PREGM model.\n\n2. The Formatting of Table 4 and Table 5\n\nIn the current presentation, multiple experimental results appear to be consolidated into single rows within these tables. This presentation may potentially lead to confusion and misinterpretation of the results. Placing more than one set of results on a single line may obscure important details, making it harder for readers to draw meaningful conclusions from the data. As a suggestion to enhance clarity and readability, it would be beneficial to dedicate each row to one specific experimental result. This layout would allow for more detailed descriptions of the corresponding experimental settings and the related results, thus improving understanding. Moreover, it will facilitate the direct comparison of different experimental conditions and results, which is particularly critical in identifying trends, nuances, and potential implications. Therefore, I would recommend revising the formatting of Table 4 and Table 5 to present one set of experimental results per row, thereby ensuring that the wealth of information is conveyed as comprehensibly as possible.\n\n3. Lack of discussion about limitations and potential negative societal impact\n\nWhile the paper exhibits a commendable effort in proposing and testing a new methodology in graph matching, I would like to raise a concern regarding the lack of discussion on the potential limitations of the proposed method and its possible negative social implications. I suggest that the authors include a discussion of the possible limitations of the PREGM model and potential negative societal impacts in the paper, thereby presenting a more comprehensive and nuanced understanding of their work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We extend our gratitude for your meticulous evaluation and constructive feedback on our paper. Your insights have significantly contributed to the refinement of our work.\n\nWe are committed to addressing your concerns and queries:\n\nLack of Visualizations: We sincerely appreciate your suggestion regarding the inclusion of visualizations. Visual aids indeed offer a valuable means of providing empirical evidence and enhancing the clarity of our proposed methodology and its performance. We acknowledge the importance of intuitive insights, and we will ensure the incorporation of meaningful visual representations of keypoint matching results in our revised manuscript. These visualizations will help elucidate the inner workings of our approach and provide readers with a comprehensive understanding of its practical applications.\n\nThe Formatting of Table 4 and Table 5: Your feedback regarding the formatting of tables is duly noted. We understand the significance of clear and concise presentation for facilitating an accurate interpretation of experimental results. In line with your recommendation, we will reformat Table 4 and Table 5 to ensure that each set of experimental results is presented in a dedicated row. This adjustment will improve the clarity and readability of the tables, enabling readers to readily compare different experimental conditions and outcomes.\n\nLack of Discussion about Limitations and Potential Negative Societal Impact: We appreciate your concern regarding the omission of a discussion on the limitations of our proposed method and its potential societal implications. Specifically, equal point matching is acknowledged as one of our limitations in our work. In the revised version of our paper, we will thoroughly address the possible limitations of the PREGM model and consider potential negative societal impacts associated with its application.\n\nWe genuinely value your feedback and suggestions, as they underscore our commitment to enhancing the quality and comprehensiveness of our research. Your dedication to fostering a deeper understanding of our contributions is invaluable.\n\nThank you once again for your time and insightful review."}, {"review_id": "Wl0j3BEatL", "reviewer": "Reviewer_LuNk", "summary": "This paper introduces a positional reconstruction encoder-decoder (PR-EnDec) to model intrinsic graph spatial structure for image key-points matching. By using graph to represent the image structure, the proposed model can utilize the high-order spatial information by reconstructing  the locational structure of graphs contained in the node coordinates.", "questions": "The proposed method takes the reference [28] as the baseline model (line 278), thus, this method should be compared on all three datasets.", "limitations": "See weakness and questions", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The structure of the whole manuscript is good. The introduced positional encoder that learns effective graph positional encoding with affine transformation invariance.\n\n2. The figures and tables are in good illustration.", "weaknesses": "1.For experimental comparison, the compared methods are old. Besides, the evaluation datasets, such as PascalVOC [8], Willow ObjectClass [4], and SPair-71k  are small and little old.  Some more recent large-scale datasets, such as PhotoTourism (IMC-PT) 2020 should be evaluated. \n\n2.Given the Problem Formulation of Graph Matching in sec.3, the compared two graphs have the same number of nodes. However, for the real application, the keypoints number constraint is not reasonable. \n\n3.Figure 2 shows the framework of the proposed PR-EnDec network that consists of the detailed structure of its positional encoder and spatial relation decoder.  However, in figure1, the Spatial Relation Decoder is missing. \n\n4.Compared to the previous works, the two stage training pipeline is complex.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We extend our sincere appreciation for your diligent review and insightful feedback on our paper. Your thoughtful comments have greatly contributed to the enhancement of our work.\n\nWe are committed to addressing your concerns and queries:\n\nExperimental Comparison and Dataset Choice: We thank you for highlighting the importance of using recent and large-scale datasets for evaluation. In response, we have included experimental results on the PhotoTourism (IMC-PT) 2020 dataset in the Appendix. Furthermore, we will present comprehensive tabular data and in-depth analysis of the results in the revised manuscript to ensure a thorough understanding of the proposed method's performance.\n\nKeypoints Number Constraint in Problem Formulation: We want to clarify that the convention of comparing graphs with equal numbers of points is commonly used in graph matching. However, we acknowledge the importance of considering scenarios with unequal keypoints, as it aligns more closely with real-world applications. In line with your suggestion, we are planning to explore and incorporate unequal point matching as a valuable future direction for our research.\n\nFigure 1 and Spatial Relation Decoder: We appreciate your attention to the spatial relation decoder. While it might appear missing in Figure 1(graph matching phase), please note that it is not absent from the overall framework. The decoder is employed specifically to enhance the training of the positional encoder. Its primary purpose is to improve the performance of the positional encoder by providing a reconstruction target during the training phase.\n\nComplexity of Two-Stage Training Pipeline: Your observation about the complexity of the two-stage training pipeline is accurate. We acknowledge that the concurrent training of positional encoders and graph matching presents a certain level of complexity. In light of this, we'd like to highlight that even the approach DGMC employed a two-stage training pipeline. While our results demonstrate superior performance, we acknowledge your point. Moving forward, we envision training positional encoders and conducting graph matching simultaneously as a promising direction.\n\nComparison with Baseline Model: We appreciate your observation and confirm that we have compared the proposed method with the baseline model BBGM on all three datasets.\n\nOnce again, we are genuinely grateful for your feedback, and we are committed to addressing these issues to ensure the clarity, comprehensiveness, and effectiveness of our paper. Your dedication to fostering high-quality research and constructive critique is invaluable.\n\nThank you for your time and consideration."}, {"review_id": "z6ssNv0APG", "reviewer": "Reviewer_1xTE", "summary": "In this paper, the authors propose to improve the existing deep graph matching paradigm via positional reconstruction. The authors claim that existing deep GM works mainly focus on the visual feature to compute the affinities while neglecting the location and position of the key points in the graphs. To this end, they propose to capture the spatial features as well as the visual features in their model PREGM. The proposed encoder decoder PR-EnDec can learn effective graph positional encoding/coding with well-designed loss functions. The experiments on multiple datasets show the performance of the proposed method.", "questions": "1. I think the authors should further show the difference in spatial information between their work and BBGM since BBGM does consider spatial information. \n2. The experiments table may need to be completed. I think it is OK when your method does not outperform all the baselines in one of the datasets, but you need to show the results, right?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The consideration of utilizing spatial information is interesting to me since existing deep GM works mainly focus on how to improve the extraction of visual features. The positional encoding is further fused with the visual features, and updated by the well-defined loss functions.\n2. The experiments on multiple datasets show that the proposed method PREGM can outperform current SOTA methods.  \n3. The paper is well-written and easy to follow.\n", "weaknesses": "1. In fact, in the framework of existing works such as BBGM, the geometry information is already the input of SplineCNN. So, I think the authors may over-claim their novelty since existing works also consider spatial information to some extent.\n2. In the experiments on Willow and Spair71k datasets, not all baselines are reported in the table. I wonder is there a reason for that? I check the best baseline (COMMON) in the Pascal VOC dataset and find that they have reported their performance on Spair71k (84.5\\%), which is higher than the performance of the proposed method PREGM.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your thorough evaluation and insightful comments on our paper. Your feedback has significantly contributed to refining the clarity and impact of our work.\n\nWe are committed to addressing your queries and suggestions:\n\nClaim of Novelty Regarding Spatial Information: We sincerely acknowledge your perspective and understand that the framework of existing works, such as BBGM, incorporates spatial information to a certain extent. In our manuscript, we aim to highlight that we are further applying spatial information in a distinct manner. We appreciate your guidance in framing our contribution accurately.\n\nDifference in Spatial Information:\nWe thank the reviewer for suggesting a deeper analysis of the distinction in spatial information between our work and BBGM. Our method introduces spatial information at multiple levels:\n\na. Higher-order Information: The parameters involved in the splineCNN training within BBGM do not encompass spatial information beyond order 2 (edges). Our method, on the other hand, extends this by incorporating spatial information directly into the positional encoding of individual nodes.\n\nb. Global Information: Our encoder directly facilitates information exchange between nodes, bypassing the reliance on edge construction through triangular dissection. This design choice enables better global spatial information utilization compared to BBGM.\n\nAs the reviewer pointed out, both approaches harness spatial information, but the embodiment and integration of this information differ significantly. We will elucidate these distinctions further in the revised manuscript to ensure clarity.\n\nIncomplete Experimental Results:\nWe acknowledge the reviewer's concern regarding missing baseline results in the experimental table, particularly for the Willow and SPair71k datasets. We appreciate the suggestion to include all relevant baseline data. The omission of these results was due to the unavailability of some baseline methods' data on these specific datasets.\n\nSpecifically, the baseline method COMMON exhibits an accuracy of 84.5\\% on the SPair71k dataset, surpassing our proposed method. However, we observed a discrepancy in the reported accuracy of BBGM across different experimental sources(78.9\\% in the original paper, 82.1\\% in COMMON's experimental data), which makes it challenging to directly compare results. Moreover, differences in dataset parameters may contribute to these variations. We have taken the reviewer's advice seriously and tested the open-source code of COMMON with the same settings and achieved an accuracy of 82.85\\% on the Spair71k dataset. We will include this result in the revised manuscript..\n\nFurthermore, we apologize for any confusion caused by not fully populating the experimental table. We commit to diligently addressing this concern by providing comprehensive experimental results, including those where our method does not achieve the best performance. We appreciate the reviewer's understanding and will ensure that our revised manuscript reflects these improvements.\n\nYour hints have been immensely valuable in providing context and guiding our responses. Your dedication to a thorough evaluation has motivated us to enhance the rigor and clarity of our research.\n\nOnce again, we express our gratitude for your diligence and insightful feedback."}]

Author rebuttal:
The attachment contains the experimental results for IMC-PT.

Meta-review: All reviewers unanimously recommended acceptance, appreciating the novel idea of positional encoding for graph matching as well as strong experimental results. There were concerns about missing details and comparisons, and the rebuttal addressed most of them, satisfying the reviewers. AC also agrees with the reviewers’ consensus that this paper provides an interesting contribution to the community, recommending acceptance. AC encourages the authors to incorporate the reviewers’ comments into the final version.
Decision: Accept (poster)