Learning Structured Universe Graph with Outlier OOD Detection for Partial Matching
Authors: Zetian Jiang
Jiaxin Lu
Haizhao Fan
Tianzhe Wang
Junchi Yan
Venue: ICLR 2025 Poster (2025)
Keywords: graph matching
Primary area: applications to computer vision, audio, language, and other modalities

Abstract: Partial matching is a kind of graph matching where only part of two graphs can be aligned. This problem is particularly important in computer vision applications, where challenges like point occlusion or annotation errors often occur when labeling key points.  Previous work has often conflated point occlusion and annotation errors, despite their distinct underlying causes. We propose two components to address these challenges: (1) a structured universe graph is learned to connect two input graphs $X_{ij} = X_{iu} X_{ju}^\top$, effectively resolving the issue of point occlusion; (2) an energy-based out-of-distribution detection is designed to remove annotation errors from the input graphs before matching. We evaluated our method on the Pascal VOC and Willow Object datasets, focusing on scenarios involving point occlusion and random outliers. The experimental results demonstrate that our approach consistently outperforms state-of-the-art methods across all tested scenarios, highlighting the accuracy and robustness of our method.

Published as a conference paper at ICLR 2025
LEARNING STRUCTURED UNIVERSE GRAPH WITH OUT- LIER OOD DETECTION FOR PARTIAL MATCHING
Zetian Jiang" Jiaxin Lu Jiaxin Sch. of Computer Science & Sch. of Artificial Intelligence, Shanghai Jiao Tong University
Haozhao Fan', Tianzhe "ang",Juncii Yan 12+
Shanghai Artificial Intelligence Laboratory
DDpaatment of Computer Science, University of Texas at Austin {maple jzt, usedtobe, junjuhch! Jθs jcu. edu. en,
cn, luji lujiaxinn www.exieea..eeeeee
ABSTRACT
Partial matching is a kind of graph matching where only part of two graphs can be aligned. This problem is particularly important in computer vision applications, where challenges like point occlusion or annotation errors often occur when label- ing key points. Previous work has often conflated point occlusion and annotation errors, despite their distinct underlying causes. We propose two components to address these challenges: (1) structured universe graph is learned to connect two input graphs X,,
X effectively resolving the issue of point occlusion; (2) an energy- based out- of-diitribuutin detection is designed to remove annotation errors from the input graphs before matching. We evaluated
method the Pascal VOC and Willow Object datasets, focusing on scenarios involving point occlusion and random outliers. The experimental results demonstrate that our ap- proach consistently outperforms ofte-offthhe-at methods across all tested scenarios, highlighting the accuracy and robustness of our method.
INTRODUCTION
Graph matching has been a fundamental task in traditional computer vision for long time, applied in areas such as structure from motion (Vjjayanarasinhan et al., 2017), object tracking (Nam & Han, 2016; Iqbal et al., 2017), optical flow (Sun et al.. 2018), stereo matching (Luo et al., 2016; Chang & Chen, 20, and pose estimation (Gasse et al., 2019). With the rise of deep learning. integrating graph matching and neural networks has led to significant improvements in accuracy and efficiency (Zanfir & Sminchisescu, 2018; Wang et al., 2019), making more suitable for downstream tasks. Beyond these, graph matching has also shown great potential in other fields, such as bioinformatics for protein structure comparison (Luo al., 2021) and drug design (Kriege et al., 2019), well as in social network analysis for community detection and network alignment (Chen et al., 2020).
In particular, graph matching aims to find node correspondence between graph-structure data via both node and edge affinity (Gold & Rangarajan, 1996; Cho et al., 2010). It is well-known Na-Hard problem and often formulated as the quadratic assignment problem (QAP):
max vec X) Kvec(X) X
(1)
s.t. X E (0, 1)n X1,, = 1,; X 1 1n-
Here, X represents binary permutation matrix, where X.j 1 indicates that node in the first graph corresponds to node j in the second graph. K E R=2xn* is a hand-craften or learned affinity matrix whose diagonal (off-diagonal) encodes node (edge) affinities.
While theoretically elegant, the QAP's assumption of perfect one-to-one node correspondence between graphs rarely holds in real-world applications. Practical scenarios often involve partial matching, where only subsets of nodes between graphs correspond, as illustrated in Figure 1. Tradi- tional approaches attempted to address this limitation by introducing dummy nodes with zero affinity. However, this solution proves inadequate for handling real-world challenges such as occlusions and annotation errors.
"Correspondence author. i denotes equal contribution. The SJTU authors in part supported by NSFC (62222607, 92370201), and SJTU Global Strategic Partnership Fund (2023 SITU-UCI.).

---

Published as a conference paper at ICLR 2025
intier
outier Ivald non-matches)
cutler (annotation enors)
fitered outtler
correct matching
wrong malching
cornect motching on valid non-metches
Pairwise Matching
Figure 1: Overview of the problem setting and UGM. Partial Matching: Due occlusion, viewpoint differences, and annotation errors, only a subset of key points on each graph can be matched. Left: Prior works have limited capability in detecting and filtering outliers. Right: UGM employs two key components to improve partial matching performance: (1) universe graph that serves bridge to aggregate matches from different graphs, and (2) an outlier filter to remove spurious matches. This design ensures that only inliers are matched, significantly enhancing partial matching performance.
Several recent works have explored ways to overcome this limitation. BBGM (Rolinek al., 2020a), for instance, bypasses the constraint that each node must find a specific match by learning negative affinity score. However, this approach heavily relies on the neural network's ' capacity, and the actual performance gains often limited. GCAN (Jiang al., 2022) reformulates graph matching integer linear programming (ILP), introducing a placeholder node for each graph to absorb outliers. While this helps, learning for ILP remains a challenging task. AFAT (Wang et al., 2023) predicts which node match to discard by analyzing matched points and the affinity matrix. However, post-processing step, its effectiveness is limited because outliers may have already disrupted the initial matching, weakening its ability to correct errors. Another approach, URL (Nurlanov et al., 2023), learns universe point representation, which serves central reference for key point alignment across all images. Although it addresses the issue point occlusion, it still suffers from redundant matches as the erroneous annotation outliers fail to find the corresponding universe point representation.
key insight often overlooked by these literature the distinction between point occlusion and annotation errors: occlusion-caused outliers may find correspondences in other graphs, while annota- tion errors are inherently meaningless. Building this observation, we propose Universe Graph Matching (UGM), which addresses these challenges through two key innovations: universe graph learning approach that utilizes the structured universe graph to serve as a bridge for matching graph pairs X:j = XT,XX Ju- This method leverages the inherent structural information from input graphs, enhancing the accuracy and robustness of the learned universe graph for handling point occlusions. (2) An mergy-based out-of-distribution detection method that effectively identifies and removes annotation errors at test time. Through training with margin loss, we effectively differentiate between the energy scores of erroneous annotation outliers and valid in-distribution keypoints. By removing annotation errors, we significantly reduce the complexity of the partial matching problem (as we will discuss in Sec. 3.3), thereby improving overall matching accuracy.
(1) A latent
Our primary contributions
We propose Latent Universe Graph Learning, which enhances universe matching robustness through combined node features and structural information.
We are the first to introduce the Energy-based OOD Detection for annotation error identification, enabling pre-matching outlier filtering for improved accuracy.
We evaluate the proposed UGM approach on keypoint matching tasks under occlusion and random outlier settings using both Pascal VOC and Willow datasets. Our experimental results demonstrate that UGM consistently outperforms state-of-the of-the-arr art methods, highlighting the effectiveness and robustness of our method.
RELATED WORKS
2.1
CLASSICAL GRAPH MATCHING
Two-graph matching has been widely studied, which involves constructing graphs for the objects to be matched and aligning the nodes and edges between the two graphs. (Gold & Rangarajan, 1996) solves graph matching via graduated assignment (GA) algorithm, which computes the partial derivative
2

---

Published as a conference paper at ICLR 2025
of the objective function with Taylor expansion to turn the GM problem into linear assignment problem. RRWM (Cho et al.. 2010) constructs an association graph for matching graphs and applies the random walk algorithm with matching constraints. RRWHM (Lee et al., 2011) is the extended version of RRWM where the association graph is built with higher-order geometric information extracted from the graph. DS++, DS* (Dym et al., 2017; Bernard et al., 2018) design different ways to tightly relax GM to a convex problem and then project the results back to the original solution space. LPMP (Swoboda et al., 2017) proposes several additional Lagrangian relaxations of the graph matching problem and leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent updates.
In addition, numerous works have focused on matching multiple graphs, which is called Multi-Grap Matching. There are mainly two forms of methods. The first solves the problem in discrete space, which includes composition-basel method CAO (Yan et al., 2015b), MGMM-Flyye (Jiang et al., 2021), rreesstructure-baset approach MatchOpt (Yan et al., 2015a), DPMC (Wang et al., 2020b), and Mlajorize-Minimizzee works (Pachauri et al., 2013; Huang & Guibas, 2013; Chen et al., 2014; Wang et al., 2018) etc. tries to relax the MGM problem into continuous space and re-project the solution to obtain a discrete matching result.
framework based approach M3C (Lu et al., 2024). Another line of
2.2 DEEP LEARNING OF GRAPH MATCHING
Deep learning has recently been applied to graph matching on images (Zanfir & Sminchisescu, 2018), whereby CNN extracts node features from images followed by spectral matching and is learned using a regression-like node correspondence supervision. This work is improved via introducing GNN to encode structural (Wang et al., 2019; Wang et al., 2020) or geometric (Zhang & Lee, 2019) informa- tion, with a combinatorial loss based on cross-entropy loss, and Sinkhorn network (Adams & Zemel, 2011) 1) as a differential matching solver. The work (Yu et al., 2020) extends PCA (Permutation loss and Cross- -raph Affinity GM) (Wang et al., 2019) by edge embedding and Hungarian based (Kuhn, 1955) attention mechanism to stabilize end-to-end training. BBGM (Blackbox Deep Graph Match- ing) (Rolínek et al., 2020b) proposes a better front-end feature extraction backbone with Spline Convolution (Fey et al., 2018), and the gradient is backpropagated by fitting linear gradient of the discrete graph matching solver (Pogančić et al., 2019). NGM (Neural Graph Matching Nets) (Wang et al., 2021; 2020a) proposes to address the most general Lawler's QAP form, based on the novel feature extractors e.g. (Rolínek et al., 2020a) with the proposed learnable graph matching solver. DL.MM (Deep Latent Graph Matching) (Yu et al., 2021), based on BBGM, predicts consistent graph topology utilizing deterministic and generative models to improve the matching quality. GCAN (Jiang et al., 2022) formulates the graph matching problem as an Integer Linear Programming problem and explores a novel node feature extraction framework with attention. AFAT (Wang et al., 2023) uses the attention model to predict which node match to discard by analyzing matched points and the affinity matrix. COMMON (Lin et al., 2023) adopts contrastive learning approach, utilizing the infoNEC loss to supervise training similarity matrices for both edges and nodes. URL (Nurlanov et al., 2023) introduces a novel universe point representation learning method, applying universe key point matching to the graph matching field for the first time.
2.3 OUT-OF-DISTRIBBTIOO DETECTION
Out-of-distributin (OOD) detection is a growing field aimed at identifying data points that deviate from the distribution on which a model was trained. This is crucial for improving the robustness and safety of machine learning systems. Many OOD detection methods can be applied to pre-trained models without modifying the training process. These methods often rely on statistics from the model's output, such as maximum softmax probability, distinguish between in-distribution (ID) and OOD data (Hendrycks & Gimpel, 2016; Liang et al., 2017). Energy- methods, on the other hand, assign an energy score to each input, where OOD data typically results in higher energy values (Liu et al., 2020; Bao et al., 2024). Generative models, such as VAEs and GANs, have also been used to estimate the likclihood that given data point belongs to the training distribution (Nalisnick et al., 2018). More recently, self-supervised tasks have been employed to improve OOD detection by learning representations that are highly correlated with the training distribution, enabling the model to identify deviations (Schwag et al., 2021), 1). Contrastive learning has further ad advanced OOD detection by ensuring that OOD data points are positioned far from ID data in the learned representation space (Winkens et al., 2020).
OOD detection
3

---

Published as a conference paper at ICLR 2025
Feature Extraction
Latent Universe Graph Learning
Evaluation Phase
Fosture
Spiie Conv
K,
LPMP
Feature
Crowe Cemmmnn Poee
X
Erandy
Latert Universe
Figure 2: Pipeline of Universe Graph Matching. The pipeline consists of two main components: 1) structured universe graph learning, which includes the training of node and edge affinities, and 2) outlier ood detection through energy score. The dark blue arrows indicate the training phase, while the light blue arrows represent the inference phase.
3 METHODOLOGY
In this section, we will introduce our method Universe Graph Matching (UGM) from two parts: structured universe graph learning and outlier ood detection in Section 3.1 and 3.2, respectively. The overall pipeline is shown in Figure 2, and more implementation and training details are provided in Appendix B. Meanwhile, we also discuss UGM perspective of problem formulation and analyze its strength as well as drawbacks in Section 3.3.
3.1 STRUCTURED UNIVERSE GRAPH LEARNING
We begin by defining the structured universe graph, which serves the foundation for approach. The universe graph U (N,, E R xd E, E Rm is composed of both node embeddings N and edge embeddings E,, The number of nodes n., corresponds the distinet types of key points present in the input graphs. We define this latent U as a complete, directed graph, where every pair of nodes is connected by directed edge, resulting in m. any edge in the input graph will have corresponding edge in the universe graph. Moreover, the directed edges capture the inherent asymmetry real-works relationships between key points, such as varying geometric or contextual dependencies, offering greater flexibility in encoding complex structural information.
X (n,, 1) edges. This ensures that
now introduce the pipeline to match latent universe graph U to the input graph G, The input graph G, (N; E Ra E; E mm consists of node features N; and edge features E, As in previous works, these features are initially extracted using a CNN-based backbone, followed by refinement through GNN. Node affinity K,, and Edge affinity K, are constructed by:
K, N,N,, K. E.E.
The matching between the universe graph U and the input graph G, is then obtained using traditional graph matching solver, such LPMP (Swoboda et al., 2017):
X, GMMoolver(K,, K.).
In our training process, we use the ground truth universe matching g instead ground truth pairwise matching ij. as the supervision signal. gf E {0. 1m is permutation matrix which denotes the ground truth correspondence between input graph G, and universe latent graph. In fact, the universe matching set (X... < i < N) and the pairwise matching set (Xi,]1 S i.j < N) are fully equivalent and can be obtained via nen-negative factorisation (Bernard al., 2019):
Xo0 X10
XO1
XON XIN
Xou X1a
X
X,
(X
X
X XxX (4)
X
XN1
XNN
Even if some pairwise matchings are missing, we can still recover the universe matching by first applying spectral decomposition and then projecting the result back into the discrete space (Pachauri al., 2013). It worth noting that, in most computer vision tasks, the matching matrix is typically
4

---

Published as a conference paper at ICLR 2025
generated from keypoint annotations, and these annotations naturally serve as the ground truth universe matching.
In practice, we cannot directly supervise Xiv with X as most graph matching algorithms are non-diffcrentiable. Even when using differentiable algorithms, such as RRWM (Cho et al., 2010), the high number of iterations would make wradient-based optimization difficult. Therefore, instead of supervising the solution, we directly act on the node and edge affinities. By treating the universe's nodes and edges indices as labels, we apply the cross-entropy loss to the node affinity K,, and edge affinity K. for training: gmpph = ((n))oftax((K).....o Bo) CE(soflmax(K.)) Me)
(5)
where
Yn arg max X()),,
We yn (EdgelD((O)) x nu + yn (EdgeID(L))
(6)
Note EdgelD E N2x denotes directed edges in the graph. Ed)eID(O) denotes the indices of the source nodes and EdgelD(1) denotes the indices of the target nodes. Another important consideration in the matching process is the diversity of categories. The input may consist of pairs from different categories, each ideally requiring its own distinct latent universe graph. A straightforward approach would be to learn a separate graph representation for each category. However, this method would cause the latent universe graph to grow excessively as the number of categories increases. Consequently, the complexity of the graph matching solver could escalate quadratically even worse, making impractical for large-scale problems.
To address this, we propose learning a single latent universe graph, where key points from different categories are mapped to the same universe node. For example, the left front wheel of car and the left handlebar of a bicycle can share the same universe node embedding. In fact, a single universe node embedding is shared among all categories, allowing the graph's 's size to be limited by the maximum number of points across all categories. The same principle applies to edge embeddings, which further reduces space complexity.
However, since the latent universe graph shares node and edge embeddings for all categories, the embeddings N, and E,, inherently lack category-specifie information. To reintroduce this information for affinity construction, we add a class embedding to each key point feature F extracted by CNN- based backbone. This ensures that the nodes N; and edges E; of the input graph still carry the necessary class information. The class embedding is derived from the global features H of the input images pair as follows:
C Encoder H,, H,), F; (F, C), F5- Concat(F,, CF
(7)
3.2 OUTLIER DETECTION
Although the structured universe graph effectively handles point occlusion, it cannot address error annotation outliers, as these outliers do not have corresponding nodes in the universe graph. We frame the identification of these erroneous annotation outliers as an out-of-distribution (OOD) detection problem.
nut-of-disttibution detection typically refers to model's ability to identify and appropriately handle data that deviates significantly from its training distribution. In the context of keypoint annotation, the correctly annotated keypoints adhere to a well-defined, coherent distribution that is consistent across all data. In contrast, erroneously annotated outliers generated through random and unpredictable factors, causing them to deviate substantially from this established distribution. This inherent difference in data characteristics enables us to frame the outlier detection problem within an OOD) detection framework, leveraging the disparity between the structured nature of valid annotations and the stochastic nature of annotation errors.
Following Liu et al. (2020), we define an energy score function for each node i of input graph:
E(w,) = - In Σ Kn.i,))/T.
where K, J), denotes the node affinity between i; on input graph and it on universe graph, and T is a temperature constant. When v is an inlier, it should have a corresponding point in the latent universe graph, resulting in relatively low energy score. Conversely, when i is an outlier, all the values of K, (i. will be relatively low, leading to higher energy score.
5

---

Published as a conference paper at ICLR 2025
While the energy score can be used for pre-trained neural network directly, the energy gap between in-distribution and out-of-distribution data may not always be optimal for differentiation. To address this, we also introduce a margin loss that fine-tunes the neural network to explicitly create a larger energy gap:
(9) where Din is the in-distribution training data, Dous is the ditto--distribution training data, Min and Mout are the margins for in- and out-of-distribution data, respectively. This loss assigns lower energy scores to in-distribution data and higher scores to OOD data. By contrastively shaping the energy landscape during training, the model becomes more effective at distinguishing between in- and -f--iiiiiittiutiinnnn data.
Lenergy = Eu-.D. (max((), E(v) - mmn) + LuwDD (max(0, Mout - E(V)))
To apply the energy score in our network, we first compute the energy & for each node in the input graph G; based on its affinity with nodes in the latent universe graph U. Nodes with energy scores above a certain threshold T, indicating high likelihood of being outliers, are removed before the graph matching process:
G Giltered
= (V = (us(E(us)= & +), E = (eaglE(us) S E,E(()) {T}}
(10)
We use the newly obtained graph G Gillered to construct the filtered node affinity K Killeredd and edge affinity K Keflteeed, and then feed it into the graph matching solver to obtain the matching result.
X fitteed
GMSoovee(K filtered K[llered)
(11)
Vu
This preprocessing step improves the quality and accuracy of the subsequent matching between the input graph and the latent universe graph. After the matching process, the removed outlier points are reintroduced into the solution to maintain the integrity of the input data.
SOT
E(va) > T,
(ia()))
(12)
x
fiitorrd (v:) iu
E(v)) S T.
3.3 DISCUSSION
Universe Graph Matching essentially decomposes the ambiguous partial matching problem into two well-defined subgraph matching problems. Partial matching, where only parts of the input graphs aligned, is difficult to formalize with clear optimization objectives and constraints. Conventional approaches, such as adding dummy nodes or relaxing the condition X1, 1, X1,, S 1a, have proven inadequate. Our key contribution lies in introducing latent universe graph, which enables us to decompose the partial matching problem between two graphs as X., = X.. ju This reformulation shifts the objective from maximizing the match X,, between the input graphs maximizing the match Xiv: Xju between each input graph and the latent universe graph. Since the latent universe graph contains all points and edges, the input graphs become its subgraphs, turning the solution of Xx.. into a well-defined subgraph matching problem. This more precise and structured problem definition in universe graph matching improves performance over traditional pairwise graph matching on partial matching tasks.
However, the latent universe graph alone cannot fully address the error annotation points, which lack corresponding matches in the universe graph and violate the assumption that input graphs are subgraphs of the universe graph. While introducing dummy nodes in to the universe graph U could potentially account for these outliers, this approach faces several challenges. Estimating the appropriate number of dummy nodes is difficult, and the randomness of error annotations makes complicate to learning effective dummy node embeddings. Our solution adopts an OOD detection approach, treating error annotation outliers as -uit---iitti points and excluding them before solving the subgraph matching problem.
Despite its advantages. our approach still faces several challenges: 1) Universe latent graph is inherently limited to closed-set problems, relying on class information and training data, which restricts generalization to unseen categories. However, few-shot learning can significantly alleviate this limitation, as shown in our experiments in Appendix ??, demonstrating the method's potential to adapt new classes. 2) The universe graph is a complete graph; however, the distribution of edges in the input graphs is uneven. This mismatch leads to suboptimal learning of many edge embeddings, with some edges either absent or appearing only rarely in the training data. 3) While the universe graph is more stable and structured than universe point representation, the universe graph cannot fully prevent errors in X from propagating to all X. matches. All in all, expanding graph partial matching to a more general form, both in terms of mathematical modeling and finer design, requires long-term exploration.

---

Published as a conference paper at ICLR 2025
4 EXPERIMENT
4.1 PROTOCOL
Datasets We evaluate our method on Pascal VOC (Everingham et al., 2010) and Willow Object Class (Cho et al., 2013), two widely recognized datasets.
The Pascal VOC (Everingham et al., 2010) with Berkeley annotations (Bourdev & Malik, 2009) contains images with bounding boxes surrounding objects of 20 classes. We follow the standard data preparation procedure of NGM and BBGM (Wang ct al., 2021; Rolínek et al., 2020b). Each object is cropped to its bounding box and scaled to 256 256 px. We follow the unfiltered setting (Rolinek et al., 2020b), which preserves all key points for graph pairs, to evaluate our method's performance under point occlusion. Moreover, which serve as error annotation key points. We also follow prior works to split the train and test. dataset, where training data includes 7,020 images and test data includes 1,682 images.
randomly sample the coordinates
images to add outliers,
The Willow Object Class (Cho et al., 2013) contains images from Caltech- 256 (Griffin et al., 2007) and Pascal VOC 2007 (Everingham et al.), which consists of 256 images from categories: 40 cars, 40 motorbikes, 50 ducks, 66 wine bottles, and 109 faces. Each image is annotated with the same ten key points. Following standard procedure, we also rescale the image to 256 x 256 px. In experiments, we randomly drop 0- 6 key points for each image for the 'occlusion' setting. We also add 10 random outliers as we do in PascalVOC for the 'random outlier' setting. We choose 20 images from each category
training dataset and leave others for evaluation.
Compared Method We compare our methods UGM with previous work of two kinds: traditional solver with pre-defined affinity and deep graph matching learning model. For the learning-free traditional solvers, we consider four works: GAGM (Gold & Rangarajan, 1996), RRWM (Cho al., 2010), BPF (Wang al., 2017), and ZAC (Wang al., 2020). We generate node and edge affinities using the pre-trained BBGM learning framework and input these affinities into each solver to obtain their respective matching results. For learning-basel models, we compare our method with NGMv2 (Wang et al., 2021), BBGM (Rolinek et al., 2020b), DLGM (Yu et al., 2021), GCAN (Jiang et al., 2022), AFAT (Wang et al., 2023), and URL (Lin et al., 2023). To report the performance of prior works, we adhere to the following principles: 1) If a prior work's 's experimental settings align with ours, we directly report the performance metrics provided in their paper. 2) If the experimental setting is unique to our work, we attempt to replicate the prior methods under their original experimental settings and then adapt them to our setting to obtain comparable performance metrics. However, we failed to replicate the methods of DLGM and URL because they did not release publicly available code. Therefore, we did not report their performance in some of the experiments (Table 2 and Table 3).
We see the matching prediction as a binary classification task for each entry. Therefore, Fl score is applied as an evaluation metric, which is introduced by BBGM (Rolínek et al., 2020b). The F1 score is calculated as follows:
Evaluation Metric
Precision Recall
2TP
F = 2
(13)
Precision + Recall 2TP + FP + FN
where TP denotes true positive, FP denotes false positive, and FN denotes false negative.
4.2 PERFORMANCE ON PASCAL VOC
To thoroughly evaluate the performance of our proposed UGM method, we conducted experiments on the Pascal VOC dataset under two distinct settings: the unfiltered setting, where all key points are preserved without the introduction of additional noise, and the random outlier setting, where two random outliers are further added to each input image. All the results are shown in Table and 2.
Our proposed UGM method demonstrates superior performance in both setting, surpassing the state-of-the-art (SOTA) models by a significant margin. Specifically, in the unfiltered setting, UGM outperforms the best-performing SOTA model by 2.2% in terms of average Fl score. Similarly, in the random outlier setting, UGM still leads the comparison, exceeding the next best method by 4.8%. This consistent improvement across both settings highlights the robustness and generalization ability of our approach.
A comparison of the two tables reveals how much performance degrades between the unfiltered and random outlier settings, allowing us to evaluate the robustness of learning- based models in the presence of outliers. Our UGM method experiences performance drop of 8.8%, ranking second
7

---

Published as a conference paper at ICLR 2025
Table 1: F1 Score performance Pascal VOC under 'unfiltered' setting. All the key points preserved, and no additional outliers are added. Top: learning-free free graph matching solver with pre-learned affinity. Middle: deep learning graph matching model. Bottom: out method UGM.
Method
acro
bike
bird
bost
bottle
bas
car
cat
chair
cow
table
deg
horse
motor
person
plant
sheep
safa
train
tv
GAGM
37.3
60.3
47.7
39.1
75.0
53.7
36.1
59.2
34.8
56.2
40.2
54.4
51.9
54.3
39
83.8
48.5
19
58.3
68.7
50.9
KRWM
29.4
6377
52.1
19.3
76.5
57.9
25.5
64.3
37.9
60.3
43
57.9
54.2
54
43.3
K5
50.4
22
06.1
099
33.3
51.2
77.0
59.0
26.7
63.3
36.9
60.6
49.7
58.1
54.3
84.9
50.7
66.4
70.4
54.0
57.5
43.9
72.1
61.2
33.6
66.2
61.8
61.4
93.2
58.1
69.8
57.0
NGMv2
55.3
98.4
45.9
S9.1
39.2
55.7
58
44.4
50.3
41.3
72.4
58.8
BBGM
57.5
85.8
51
63.8
42.4
47.9
61.5
63.4
45.1
94.2
57.4
75
58.5
47.4
86.4
71.2
53.1
66.9
65.7
66.9
7008
47.4
96.5
61.4
77.5
GCAN
60.6
69.3
66.3
03.2
6499
66.9
63.1
62.5
63.5
96.
53.5
30.6
64.6
AFAT
47.1
708
58.1
45.5
90.8
66.5
49.5
58.3
50.6
64.6
47.2
60.5
62.3
65.7
46.3
95.4
52.7
47.4
74.2
83.8
62.0
URL
62.7
75.2
73
56.7
93.7
66.2
76.7
69.2
64.9
76.6
44.6
74.4
78.8
80.9
62.5
96.9
70,3
55.4
13.6
82.1
71.7
DGM
57.4
76.3
71.2
55.3
91.7
72.3
80.3
72,3
70.1
74.6
61.5
75.3
71.6
76.1
63.8
97.2
73.6
61.8
93.1
$4.8
73.9
Table 2: Fl Score performance on Pascal VOC under 'random outlier' setting. Two random outliers are further added to each input image. Top: learning-free graph matching solver with pre-learned affinity. Middle: deep learning graph matching model. Bottom: out method UGM.
Method
2070
hird
boat
bottle
bus
car
cat
chair
cow
table
dog
horee
motor
prrson
plant
shoep
soft
train
GAGM
26.7
49.3
36.6
25.1
61.9
40.7
9.0
45.4
22.5
39.5
13.1
41,0
37.3
39.1
27.9
59.8
29.1
19.7
20.0
54.9
35.2
RRWM
28.3
54.6
40.3
20.4
70.6
46.3
9.0
49.3
21.5
42.8
15.1
44.8
18.1
39.1
66.8
29.3
18.1
22.1
25.8
55.2
3888
26:0
70.7
9.5
22,9
36.9
28.6
28.1
50.8
34.0
76.0
$5.9
23.8
63.7
33.2
58.8
37.7
50.4
55.8
55.4
30.1
50.8
72.1
55.7
BBGM
34,4
35.0
78.5
$7.6
21.5
54.6
$0.3
37.4
49.8
50.8
54.7
20.6
44.1
44.5
GCAN
44.4
78.88
72.3
45,9
58.0
62.8
54.6
60.3
61.2
51.5
62.6
48.8
70.0
60.3
APAT
41.2
66.9
51.4
16.5
82.7
61.8
37.9
56.9
$4.8
55.7
28.0
54.4
55.1
60.3
58.2
86.3 3
48.8
32.6
57.1
77.1
53.1
UGM
29.9
6355
48.5
85.3
71.8
66.5
54.6
67.4
07.4
65.2
66.2
57.6
8800
62.2
47.2
05.6
65.1
among the learning-bast based models, just behind GCAN. In comparison, models like NGMv2 and BBGM exhibit larger performance declines of 1 11.8% and 13.2%, respectively. The relatively low decrease in UGM's 's performance demonstrates its robustness and adaptability, particularly in noisy and complex environments, making it reliable option for real-world graph matching tasks.
We also perform an random outlier pressure test on our method UGM. Results are shown in Figure 3. Classes like sofa, train, and table see a significant performance drop (32% 61 %) as the number of random outliers increases. This decline is primarily due to the limited amount of training data, particularly for classes like 'table', which has only 28 images, and 'sofa', which has 73 images in the train dataset. The fewer images available, the lower the quality of the constructed latent universe graph, making it more difficult to distinguish between inliers and error annotation outliers. On the other hand, classes like TV. boat, horse, and bus are more robust, with relatively smaller drops in performance (9.9% 13.9%).
4.3 PERFORMANCE ON WILLOW OBJECT
In this experiment, we evaluate the performance of various sarring--bseed graph matching models on the Willow dataset under three settings: occlusion, random outlier, and occlusion random outlier. These settings simulate real-world challenges, where key points may be missing (occlusion), or noisy data (outliers) may be introduced. All the results are shown in Table 3.
Our proposed UGM method demonstrates superior performance across all three settings. In the occlusion setting, UGM achieves the highest average Fl score of 91.9%, outperforming the next best model, GCAN, by sigmificant margin of 9.7%. In the random outlier setting. UGM again leads with average score of 85.4%, surpassing AFAT, the second-best model, by 1.7%. Finally, in the occlusion + random outlier setting, UGM shows exceptional robustness, maintaining the highest average score of 71 71.11 %,, which is 5.9% higher than the second-ples -pacce model.
It is worth noting that the extent of our lead varies across the three settings.
In the occlusion setting, UGM demonstrates a significant advantage. This suggests that the latent universe graph structure offers considerable benefit compared pairwise matching approaches,
8

---

Published as a conference paper at ICLR 2025
Results by Category and Outlirr Level
100
80
50
30
4070
bus
cOm
bable
dog
horse moter person
plant
sheep
solat
bain
a0g
ooutler
outtlers
outilers
outtlers
Butillrss
10 outiless
Figure 3: Random outlier pressure test of UGM on Pascal VOC. All the key points are preserved. and additional outliers are added to each input image.
Table 3: F1 Score performance on Willow Object Class. Occlusion: randomly drop 0-6 key points for each input image. Random Outlier: randomly add 1-10 outliers for each input image. Occlusion + Random Outlier: both operations are applied. Only the learning model's performance is reported.
Occlusion
Random Outlier
Occlusion + Random Outlier
Method
duck
face
motor
bottle
avg
dack
face
motor
bottle
duck
face
bottle
arg
NGMv2
80.9
73.8
84.9
85.7
76.7
80.4
78.9
66.6
84.3
63.1
76
73.8
46.3
45.2
61.6
42.9
54.6
50.1
BRGM
77.5
788
92.7
83.1
82.3
82.9
65.1
60.7
85.5
71.6
65,5
69.7
36,2
35.5
57.2
35.0
52,4
43.3
GCAN
74.
88.5
88.3
82.2
748
75.7
77.1
56.9
AFAT
77.1
73.7
88.0
76.6
86.4
80.4
82.2
77.7
92.7
77.2
88.6
83.7
70.8
54.7
79.1
53.8
67.9
65.2
UGM
87.7
86.2
99.5
90.2
96.0
91.9
88L1
72.9
96.8
82.5
86.5
85.4
64.4
62.1
89.6
65.1
74.5
71.1
as Universe Graph Matching essentially decomposes the ambiguous pairwise partial matching problem into two well-defined subgraph matching problems, thereby improving its ability to handle missing key points.
In the random outlier setting, the performance gap between UGM and other models is narrower. While our OOD -uttoo-ddittibution)) detection technique offers a clear advantage, the improve- ment is less pronounced. This is likely due to the fact that our approach does not introduce additional training parameters, which limits the potential for further gains.
Finally, in the occlusion + random outlier setting, UGM once again achieves a clear lead. This demonstrates the strong synergy between the latent universe graph learning and energy based OOD detection technique. The two techniques work in harmony, with no conflicting or contradictory effects, allowing UGM to excel in the most challenging conditions.
4.4 ABLATION STUDIES
The ablation study results presented in Table 4 highlight the contribution of each key compo- nent-class embedding, universe graph, and out- lier filter-to the overall performance. Without the outlier filter component, we matched all the points in the input graph to the latent universe graph. Without edge learning, we only learned the universe node representation and used a linear assignment solver to obtain the matching results between the input graph and the universe point representation. Without class embedding, we di- rectly used the local key point features extracted by the backbone learn the node embeddings.
Table Ablation study on Pascal VOC with 'random outlier' setting. All the key points are preserved, and two random outliers are added to each input image. Fl score reported.
class embedding edge learning
filter
Fl score
65.12
x
56.88
63.49
58.71
These results demonstrate that each component plays a unique role in enhancing the model's perfor- mance. Specifically, removing the outlier filter has the most significant negative impact, underscoring its importance in handling noise and maintaining robust graph matching.
Furthermore, we also conduct a sensitivity test for hyperparameters on Pascal VOC under the 'random outlier' setting, as shown in Figure 4. In this sensitivity analysis, we investigate the effects of varying three patprrrrmmettesttteeraauuu T, threshold 7, and the pair of values for min and mon- Unless

---

Published as a conference paper at ICLR 2025
07
67
21.00m
-5
644
68
642
$1.75
62
02
Terpenture
Threshoi
Figure 4: Sensitivity test for hyperparameters on Pascal VOC under 'random outlier' setting. Temper- ature T in energy function, OOD threshold and min: Mout in energy loss are tested.
BBGM
NGMv2
GCAN
AFAT
UGM
GT
Figure 5: Visualization on Pascal VOC of UGM and peer methods. The green dashed lines represent correct matches, while the red dashed lines represent incorrect matches. Ground truth matching is shown at the bottom.
specified otherwise, the default parameter values are set to 1.0, min -3, Mout -6, and 7-mmm- + m2.
For the temperature experiment, we tested values ranging from 0.8 to 10. The results show that performance peaks at temp=1.0 with an average value of 65.1, and gradually decreases as the temperature increases. The threshold experiment explores a range from -1.5 to -6. The average performance is highest at 7=-2.5 with value of 66.37, and the performance decreases consistently as the threshold becomes more negative. Although adjusting 7 can achieve higher FI score, we are concerned that this might lead to some overfitting in the model. Therefore, we still report the model results using the default value = (mZ, + Mout) )/2 in other contexts. For the Min and Most experiments, we analyze both their margin (difference) and absolute offset. Performance peaks (-3, -6), where the margin is 3, but the overall impact of varying the range (from to 7) or shifting their absolute values is minimal.
5 CONCLUSION
In summary, this work presents a novel approach to addressing the challenges of partial matching in graph-based keypoint aligmment tasks. We introduce Structured Universe Graph Learning to effectively resolve point occlusion by connecting input pairs via learned latent graph. Additionally, by incorporating both node features and structural information, the robustness of the matching process is further enhanced. We also adopt Energy-basee emrors before matching, improving the overall quality of the matching process. Through extensive evaluations the Pascal VOC and Willow Object datasets, our method consistently outperforms sifte--f--hh-aaae techniques, particularly in challenging scenarios involving both point occlusion and random outliers, demonstrating the effectiveness and robustness of our approach.
Dut-oof-Dsttrbbu
Detection to filter out annotation
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Ryan Prescott Adams and Richard S Zemel. Ranking via sinkhorn propagation. arXiv: 1925, 2011.
Tianyi Bao, Qitian Wu, Zetian Jiang, Yiting Chen, Jiawei Sun, and Junchi Yan. Graph out-of- distribution detection goes neighborhood shaping. In Forty-first International Conference Machine Learning, 2024.
Florian Bernard, Christian Theobalt, and Michael Moeller. Ds*; Tighter lifting-free convex relaxations for quadratic matching problems. In CVPR, pp. 4310-4319, 2018.
Florian Bernard, Johan Thunberg. Jorge Goncalves, and Christian Theobalt. Synchronisation of partial multi-matchings via non-negative factorisations. Pattern Recognition, 92:146-155, 2019.
Lubomir D. Bourdev and Jitendra Malik. Poselets: Body part detectors trained using 3d human pose annotations. ICCV, pp. 1365-1372, 2009.
Jia-Ren Chang and Yong-Sheng Chen. Pyramid stereo matching network. In CVPR, pp. 5410-5418, 2018.
Hongxu Chen, Hongzhi Yin, Xiangguo Sun, Tong Chen, Bogdan Gabrys, and Katarzyna Musial. Multi-level graph convolutional networks for cross-platform anchor link prediction. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2020.
Yuxin Chen, Leonidas Guibas, and Qixing Huang. Near-optimal joint object matching via convex relaxation. In /CML, pp. 100-108, 2014.
Minsu Cho, Jungmin Lee, and Kyoung Mu Lee. Reweighted random walks for graph matching. In ECCV, pp. 492-505, 2010.
Minsu Cho, Alahari Karteek, and J. Ponce. Learning graphs to match. ICCV, pp. 25-32, 2013.
Boris Delaunay al. Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7(793-800):1-2, 1934.
Nadav Dym, Haggai Maron, and Yaron Lipman. Ds++ a flexible, scalable and provably tight relaxation for matching problems. ACM Transactions on Graphics (TOG), 36(6):1-14, 2017.
M. Everingham, L. Van Gool, C. K. Williams, J. Winn, and A. Zisserman. The PASCAL Visual Object Classes Challenge 2007 (VOC2007) Results. http://www.pascal- http://hallaogeeeeooco/eeo////s/
Mark Everingham, Lue Gool, Christopher K. Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. IJCV, 88(2):303-338, June 2010. ISSN 0920-5691.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splinecnn: Fast geometric deep learning with continuous b-spline kernels. In CVPR, pp. 869-877, 2018
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. arXiv preprint arXiv: 01699, 2019.
S. Gold and Anand Rangarajan. graduated assignment algorithm for graph matching. IEEE TPAMI, 18:377-388, 1996.
Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. Technical report, California Institute Technology, 2007.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pp. 770-778, 2016.
Dan Hendrycks and Kevin Gimpel. baseline for detecting misclassified and out-of-diitribution examples in neural networks. arXiv preprint arXiv: 1366, 2016.
Qi-Xing Huang and Leonidas Guibas. Consistent shape maps via semidefinite programming, In Computer Graphics Forum, volume 32, pp. 177-186. Wiley Online Library, 2013.
11

---

Published as a conference paper at ICLR 2025
Umar Igbal, Anton Milan, and Juergen Gall. Posetrack: Joint multi-person pose estimation and tracking. CVPR, pp. 2011-222200 2011-2020, 2017.
Zetian Jiang, Tianzhe Wang, and Junchi Yan. Unifying offline and online multi-graph matching via finding shortest paths on supergraph. IEEE TPAMI, 43(10))3648-366) 3640)363,,, 2021.
Zheheng Jiang, Hossein Rahmani, Plamen Angelov, Sue Black, and Bryan M Williams. Graph- context attention networks for azeeidried deep graph matching. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 2343-2352, 2022.
Nils M Kriege, Lina Humbeck, and Oliver Koch. Chemical similarity and substructure searches. 2019.
Alex Krizhevsky, lly Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. NeurIPS, 25:1097-1105, 2012.
H. W. Kuhn. The hungarian method for the assignment problem. In Export. Naval Research Logistics Quarterly, pp. 83-97, 1955.
Jungmin Lee, Minsu Cho, and Kyoung Mu Lee. Hyper-graph matching via reweighted random walks. In CVPR, pp. 1633-1640, 2011.
Shiyu Liang, Yixuan Li, and Rayadurgam Srikant. Enhancing the reliability of out-of--ditributtin image detection in neural networks. arXiv preprint 170.009000 2017.
Yijie Lin, Mouxing Yang, Jun Yu, Peng Hu, Changqing Zhang, and Xi Peng. Graph matching with bi-level noisy correspondence. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 23362 23371, 2023.
Weitang Liu, Xiaoyun Wang. John Owens, and Yixuan Li. Energy-based nuttoo-diistribution detection. Advances in neural information processing systems, 33:21464-2111 21475, 2020.
Jiaxin Lu, Zetian Jiang, Tianzhe Wang, and Junchi Yan. M3c A framework towards convergent, flexible, and unsupervised learning of mixture graph matching and clustering. 2024.
Shitong Luo, Chence Shi, Minkai Xu, and Jian Tang. Predicting molecular conformation via dynamic graph score matching. Advances in Neural Information Processing Systems, 34: 34:19784-19795 2021.
Wenjie Luo, Alexander G Schwing, and Raquel Urtasun. Efficient deep learning for stereo matching. In CVPR, pp. 5695-5703, 2016.
Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan Gorur, and Balaji Lakshminarayanan, Do deep generative models know what they don't know? arXiv preprini arXiv: 1.X.::1100 2018.
Hyconseob Nam and Bohyung Han. Learning multi-domain convolutional neural networks for visual tracking. In CVPR, pp. 4293-4302, 2016
Zhakshylyk Nurlanov, Frank R Schmidt, and Florian Bernard. Universe points representation learning for partial multi-graph matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 1984-1992. 2023.
Deepti Pachauri, Risi Kondor, and Vikas Singh. Solving the multi-way matching problem by permutation synchronization. In NeurlPS, pp. 1860-1868, 2013.
Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differen- tiation of blackbox combinatorial solvers. In ICLR, 2019.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vit Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In ECCV, pp. 407-424, 2020a.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vit Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In ECCV, pp. 407-424, 2020b.
Vikash Sehwag, Mung Chiang, and Prateck Mittal, Ssd: A unified framework for self-supervised outlier detection. arXiv preprint arXiv:2 /205 2021.
12

---

Published as a conference paper at ICLR 2025
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. ICLR, 2014.
Deqing Sun, Xiaodong Yang, Ming-Yo Yu Liu, and Jan Kautz. Pwe-net: Cnns for optical flow using pyramid, warping, and cost volume. In CVPR, pp. 8934-8943, 2018.
Paul Swoboda, Carsten Rother, Hassan Abu Alhaija, Dagmar Kainmuller, and Bogdan Savchynskyy. A study of lagrangean decompositions and dual ascent solvers for graph matching, In CVPR, pp. 1607-1616, 2017.
Sudheendra Vijayanarasimhan, Susanna Ricco, Cordelia Schmid, Rahul Sukthankar, and Kate- rina Fragkiadaki. Sfm-net: Learning of structure and motion from video. arXiv preprint arXiv:170.007804, 2017.
Fudong Wang, Nan Xue, Jin-Gang Yu, and Gui-Song Xia. Zero-assignment constraint for graph matching with outliers. In CVPR, pp.
2020.
Qianqian Wang, Xiaowei Zhou, and Kostas Daniilidis. Multi-image semantic matching by mining consistent features. In CVPR, pp. 685-694, 2018.
R. Wang, J. Yan, and X. Yang. Combinatorial learning of robust deep graph matching: an embedding based approach. IEEE TPAMI, 2020.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In ICCV, pp. 3056-3065, 2019.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's quadratic assignment problem with extension to hypergraph and multiple- -gaphh matching. IEEE TPAMI, 2021.
Runzhong Wang, Ziao Guo, Shaofei Jiang, Xiaokang Yang, and Junchi Yan. Deep learning of partial graph matching via differentiable top-k. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6272 6281, 2023.
Tao Wang. Haibin Ling, Congyan Lang, and Songhe Feng. Graph matching with adaptive and branching path following. IEEE TPAMI, 2017.
Tao Wang. He Liu, Yidong Li, Yi Jin, Xiaohui Hou, and Haibin Ling. Learning combinatorial solver for graph matching. In CVPR, pp. 7568-7577, 2020a.
Tianzhe Wang, Zetian Jiang, and Junchi Yan. Clustering- aware multiple graph matching via decayed pairwise matching composition. In Proc. AAAI Conf. Artif. Intell, pp. 7-12, 2020b.
Jim Winkens, Rudy Bunel, Abbijit Guha Roy, Robert Stanforth, Vivek Natarajan, Joseph R Ledsam, Patricia MacWilliams, Pushmeet Kohli, Alan Karthikesalingan, Simon Kohl, et al. Contrastive training for improved out-of-distribution detection. arXiv preprint arXiv:2007.05566. 2020.
J. Yan, J. Wang, H. Zha, X. Yang, and S. Chu. Consistency-driven alternating optimization for multigraph matching: unified approach. IEEE TIP, 24(3):994 1009, 2015a.
Junchi Yan, Minsu Cho, Hongyuan Zha, Xiaokang Yang, and Stephen M Chu. Multi gulti-graph matching via affinity optimization with graduated consistency regularization. IEEE TPAMI, 126)):22-12 2015b.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with hhannel-nddependnn embedding and hungarian attention. In ICLR, 2020.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Deep latent graph matching. In ICML, pp. 12187-12197, 2021.
Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching. In CVPR, pp. 2684 2693, 2018.
Zhen Zhang and Wee Sun Lee. Deep graphical feature learning for the feature matching problem. In ICCV, pp. 5087-5096, 2019.
13

---

Published as a conference paper at ICLR 2025
APPENDIX
A NOTATION
We first present all notations used in this paper for better understanding of proposed algorithms and to facilitate the following discussion.
Table 5: Main notations and description used in this paper.
Notations
Descriptions
N
Node embedding or node feature on the graph.
E
Edge embedding node feature the graph.
U ,, R E,, R x denotes the latent universe graph, where nu and my represents the node and edge number of the latent universe graph.
U
G, [N; R E, Rm xd] denotes the input graph, where n, and m, represents the node and edge number of the input graph.
G;
EdgelD E Naxm denotes directed edges in the graph. EdgelD(O) denote the indices of the source nodes and EdgelI((I) denote the indices of the target nodes.
EdgelD
K
K, E R2 denotes the node affinity between the input graph and the universe graph.
K,
Kg C R th denotes the edge affinity between the input graph and the universe graph.
X,j
Xij C {0, 1) 1 denotes the matching between the input graphs
X
Xij E {0, 1 denotes the matching between the input graph and the universe graph.
C
Class embedding for image pair.
H;
Global feature extracted by backhone for the input image.
F,
Key point feature extracted by backbone for the input image.
Evx)
Energy score for node
Energy score threshold for outlier filter.
Din Dout
Din Dout denotes in-distribution data and
data respectively.
B IMPLEMENTATION DETAIL
We utilize the standard feature extractor pipeline with a few modifications.
Fisrt of all, we replace the VGG16 (Simonyan & Zisserman, 2014) backhone with ResNet50 (He et al., 2016). We compute the outputs of relu3_5, _5, relu4_1 of the ResNet50 network pre-trained on ImageNet (Krizhevsky et al., 2012), to obtain feature F, and Fz, respectively. These features are then concatenated create the key point feature F:
(14) Class embedding is added F as introduced in Equation 7, and we apply MLP layer to reduce the feature dim to keep the same dimension with the output of the VGG16- based backbone.
F CONCAT(F), F2)
Then we feed the obtained feature and the graph adjacency A into the geometric feature refinement component. The graph adjacency A is generated using Delaunay triangulation (Delaunay al., 1934) based on keypoint locations. We apply SplineConv (Fey et al., 2018) to encode higher- order information and the geometric structure of the entire graph into node-wise features F":
N, E = SplineConv(E (F,
(15)
The Spline Conv operation calculated as follows:
F,
1 W(
Σ
F, (F FFFFFF)
(16)
JEN(()
where F, represents the node feature of Ug, (ii denotes the neighborhood of vs and he denotes a kernel function defined over the weighted B-Spline tensor product basis.
14

---

Published as a conference paper at ICLR 2025
Algorithm 1 Universe Graph Matching
Require: Input images I, input key points P. learnable parameters 0, learning rate 1/. epoch number E. margins Min; Mouts Temperature T' OOD threshold
Ensure: Trained parameters 8" and universe latent graph U
1: Initialize 0 randomly
2: Initialize node and edge embedding of universe latent graph U randomly
3: for = to do
4: for image pair I; 1 in train/test dataset do
5: # extract features
6: Extract key point feature F by CNN backbone via Eq. 14
7:
Add class embedding to F via Eq.
8:
Refine F with Spline Conv obtain node N and edge feature via Eq. 15 and Eq. 16
9:
10:
# build affinity
Construct node affinity K,, and edge affinity Kg via Eq. Calculate energy & for each node via Eq. 8 Filter out random outlier with OOD threshold 7 via Eq. 10
12:
13:
15:
training then
16:
# loss and update
17:
Calculate permutation loss with Kfilteree and Kfiltered for both I and I
18:
Calculate energy loss with E, Min, and Mout via Eq. 9 for both I and
Final loss [ Epemmtation Lenery, and compute gradient VoC, Vuc
20:
Update parameters: +- 0 v
21:
Update universe embedding: U U VVL
else
23:
# build pairwise matching
24:
Use LPMP solver obtain universe matching Xin, Xjuu via Eq. 11 and Eq. 12 Build pairwise matching by X X ju
25:
26:
end if
27:
end for
end for
29:
return 0*, U
Node and edge affinity construction, universe matching, and outlier filter process have been introduced in Section 3.1 and 3.2. We finally build pairwise matching by Xij X ju'
All the models are trained on on Linux workstation with 10920X RTX3090, and 128GB RAM. The training and inference algorithm is shown in A Algorithm 1. In default, we train our UGM with hyper parameters Min -6, mout n) le 3, and 15.
CPU, one
3, T 1.0, -4.5.
C BACKBONE COMPARISON
To systematically evaluate the impact of network architecture on performance, we conducted com- prehensive experiments comparing VGG and ResNet as backbone models across all methods. This analysis ensures fair comparison by providing results using consistent architectures while also quantifying how architectural choices influence each method's 's effectiveness.
As demonstrated in Table feature extractor configurations, including VGG+Spline2D, VGG+Attention, and ResNet+Spline2.. The sole exception occurs with VGG+Spline2D+33D where URL achieves better results through its utilization of spline3D features. However, due the unavailability of URL's implementation, were unable to integrate this feature extractor into our UGM model. To facilitate a fair comparison, we adopted ResNet50 as the common backbone architecture.
method consistently outperforms existing approaches across multiple
While evaluating architectural impacts, observed that not all baseline methods exhibited perfor- mance improvements when transitioning to ResNet. To maintain scientific rigor and transparency, we have included these results in this appendix, allowing for a more proper discussion of architectural sensitivities across different approaches.
15

---

Published as a conference paper at ICLR 2025
Table 6: Backhone fairness comparison Pascal VOC with unfiltered setting. The performance with the VGG backbone is reported by their paper, and the performance with the ResNet backbone is reproduced via publicly available code. denotes that the method has not released its code.
Method
Backbone
GNN
Fl score
Backbone
GNN
F1 score
NGMv2
VGG
Spline2D
58.8
ResNet
Spline2D
57.46
BBGM
VGG
Spline2D
61.4
ResNet
Spline2D
64.45
DLGM
VGG
Spline2D
64.8
ResNet
Spline2D
GCAN
VGG
Attention
64.6
ResNet
Attention
64.67
AFAT
VGG
Attention
62
ResNet
Attention
59.55
URL
VGG
Spline2D
67.6
ResNet
Spline2D
URL
VGG
Spline2D+31
71.7
ResNet
Spline2ID+3D
UGM
VGG
Spline2D
70.5
ResNet
Spline2D
73.9
D EFFECT OF ENERGY MARGIN Loss
nnditiributionn onttttttttrbttto
inditiibbution intotetttntuttoonn
25800
20000
Oot-eiciarittoon dbobxlee
10033
13000
33000
7540
2500
Enery Values
Enarge Vafurs
Figure 6: Left: Energy histogram of ID and OOD samples without energy loss finetuning, Right: Energy histogram of ID and OOD samples with energy loss finetuning
The effect of energy margin loss is shown in Figure 6. Left shows the energy distribution of in- distribution (ID) and out-of-distribution (OOD) samples before applying the Energy Margin Loss, where the energy values for both ID and OOD samples overlap significantly, making it difficult to distinguish between them. After finetuning with the Energy Margin Loss, the energy values for IDD samples shift toward lower energy levels, while OOD samples are pushed toward higher energy levels. This separation of energy distributions effectively enhances the model's s ability to distinguish between ID and OOD samples, demonstrating the efficacy of the Energy Margin Loss in improving model robustness.
16


Reviews:
[{"review_id": "uoAfeFRmN4", "reviewer": "Reviewer_SAEb", "summary": "This paper presents a novel approach for partial graph matching. The proposed method introduces a complete and universal graph as the complete set for all the cases. By decomposing the one step matching problem into two steps: First, matching with the universal graph. Then filter out the outliers and match the second time. The proposed method achieve robust and accurate matching results. The proposed method is validated on several popular benchmarks.", "questions": "1. EdgeID in eqn.6 needs to be defined.\n2. It is not clear how eqn.4 is applied in generating GT for X_{iu}. First, the number of nodes in universal graph is larger the N, then the factorization is not unique, which one to pick? Second, X^{GT} is in {0, 1}. It is not clear X_{u} is continuous or discrete. If it is continuous, in eqn.6, the authors choose argmax as the label, does this approximation affect the performance?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed latent universal graph is novel and effectiveness.", "weaknesses": "1. The proposed method can only be applied in closed set problem. It is not a general graph matching solver. Though introducing the class embedding, it cannot generalize to unseen class in inference time.\n2. How to define the OOD data in eqn.9? If we can see the OOD data in training, how can they treat as OOD? Does the method generalize well to indeed OOD data (not seen in training)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qwaWHEPnFJ", "reviewer": "Reviewer_6zax", "summary": "This paper proposes Latent Universe Graph Learning and out-of-distribution detection for point occlusion and annotation error in graph matching problems. The paper evaluates the proposed method on the Pascal VOC and Willow Object datasets. The method achieves SOTA performance and the ablation study shows the components are effective.", "questions": "See weaknesses above. My main concerns are about the experiments.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The motivation is good. The proposed method can be easy to follow because of the intuitive motivation.\n- The paper is well-written, clear, and full of details.\n- SOTA performance and good ablation studies.", "weaknesses": "- No qualitative results are provided. Especially for the represented successful cases that cannot be solved in the baseline method. Besides, as mentioned in discussion subsection, some failure cases should be shown to let the readers better understand the margin of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5qg5R9XwVv", "reviewer": "Reviewer_24Cj", "summary": "The paper presents a method to match graphs with a mechanism to deal with outliers (i.e., query nodes w/o an actual matching reference node). The proposed approach learns embeddings for both nodes and edges and uses supervised learning via affinity matrices. To deal with outliers, the proposed method calculates an energy based on the affinity scores to filter out query nodes w/o matching reference nodes. The paper presents experiments on visual semantic matching using Pascal VOC and Willow Object datasets where the proposed method often outperforms baseline methods.", "questions": "1. What values of temperature, m_in, m_out, and threshold were used for the experiments?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The proposed approach considers both nodes and edge information in the graph. In its presentation, it looks like a general formulation. I think this is interesting as edges can help the matching process in many aspects.\n2. The mechanism to deal with outliers is needed given that in practice they occur very often and can decrease performance in a considerable manner.", "weaknesses": "1. Clarity of the approach is poor. The most important weakness is the presentation of the proposed approach in Section 3.1. This lowers the chances of the proposed approach to reproduce the results. First, there is no high-level description of the proposed approach, and as a reader we have to figure out from the mathematical description and non-informative narrative. For instance, in line 197, the term “ground truth universe matching” and symbol X^gt_iu is never properly defined, and ultimately the paragraph says that it uses ground truth pairwise matching X^gt_ij. Second, lines 224-227 states that “keypoints from different categories are mapped to the same universe node”. I don’t think this makes sense, because this will make the network confuse categories. Right? Lastly, it is also unclear why an attention-based approach could not be used. Attention can be useful also in rejecting outliers. In fact there are previous approaches derived for feature matching (e.g., LoFTR [C]).\n\n2. The proposed formulation requires the use of class information. This prevents the generalization to other matching problems (e.g., feature matching for geometric problems such as in 3D reconstruction or stereo matching).\n\n3. Outlier detection mechanism is weak. This is because it is based on thresholding the similarity information which can cause it to reject correct matches; consider the case where a wheel from a bike gets confused with a wheel from a car. This mechanism seems to be ad-hoc. Why not learn a function to detect these? I can imagine learning a function that turns off the similarity entry in the affinity matrix. The ground-truth could be easily generated by assigning a node of class A to class B, and perhaps more fruitful if A and B share visual similarities.\n\n4. Experiments are incomplete. First, the experiments are missing recent benchmarks: IMC-PT-SparseGM benchmark [A] and only showing two benchmarks in my opinion falls short of truly showing convincing evidence of the proposed method performance. Second, some of the baselines on the presented benchmarks do not contain the SOTA methods (e.g., [B]) and report different metrics from those reported in [B], where the COMMON method achieves a high accuracy rating on the Willow dataset. Lastly, the ablation studies are quite small. They are missing threshold value performance, m_in, and m_out, as well as temperature T. What values were used for the ablation and experiments?\n\nReferences:\nA. Wang, Runzhong, et al. \"Deep learning of partial graph matching via differentiable top-k.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023.\nB. Lin, Yijie, et al. \"Graph matching with bi-level noisy correspondence.\" Proceedings of the IEEE/CVF international conference on computer vision. 2023.\nC. Sun, Jiaming, et al. \"LoFTR: Detector-free local feature matching with transformers.\" Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2021.\n\n-----\nPost-discussion\n\nAfter discussing and reviewing additional results, the authors addressed most of my concerns. I will raise my raiting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hfUs5anJ7z", "reviewer": "Reviewer_1X7r", "summary": "This work proposes a new method for partial matching in graph-based keypoint alignment tasks. It introduces Structured Universe Graph Learning to address point occlusion by linking input pairs through a learned latent graph, leveraging both node features and structural information for enhanced robustness. Additionally, an Energy-based Out-of-Distribution Detection is used to filter out annotation errors before matching, improving quality. Extensive evaluations on the Pascal VOC and Willow Object datasets show that this method outperforms state-of-the-art techniques, especially in challenging scenarios with point occlusion and random outliers, proving its effectiveness and robustness.", "questions": "Typos:\n\n- The URL paper is mis-cited in line 351/352.\n\n- There is a typo in line 108", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This work addresses a classic, significant problem in the literature by applying a modern deep-learning approach.\n\n2. The proposed method outperforms both classical and learning-based methods, demonstrating robustness even in the presence of \noutliers and out-of-distribution (OOD) key points.\n\n3. The authors discuss the limitations of their approach.\n\n4. The paper includes ablation studies to analyze the impact of their design choices.", "weaknesses": "1. The paper would benefit from improved writing, particularly in the abstract and introduction, to make it more accessible to readers who are not familiar with this specific problem.\n\n2. While the authors report the F1 score, it would be helpful to include the Accuracy metric, as done in some previous works, for a more comprehensive comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pfUFmSR7ix", "reviewer": "Reviewer_Mt6s", "summary": "This paper addresses two key challenges in graph matching: (1) the partial matching problem, where not all nodes are visible in both graphs being matched, and (2) the issue of out-of-distribution outliers. To tackle the first problem, the paper reformulates the matching process between two graphs (A → B) by introducing a universal graph (U), such that matching is performed between each input graph and this universal graph (A → U, B → U). The results are then combined to obtain the final matching (A → B). This approach effectively decomposes the ambiguous partial matching problem into two well-defined subgraph matching tasks. For the second problem, a margin loss is applied to increase the energy distribution difference between in-distribution and out-of-distribution data.", "questions": "Please address my concerns in weaknesses.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-organized, and the concept of a universal graph is intriguing. This approach has the potential to inspire future research in this area.", "weaknesses": "- The universal graph\n\n  The paper states that all input graphs are subsets of the universal graph. However, input graphs could represent different structures, such as those for cars, dogs, and TVs, so how is this ensured? Can authors provide specic details on how the universal graph is consructed to accommodate diverse object categories, including its size and the process of creating ground truth matches between input and the universal graph?\n\n- The generalization issue\n\n  The proposed universal graph is crucial to this method, as its structure is determined by the training data. So it may not generalize well to unseen categories. Please discuss how the method might perform on unseen categories or provide experiments demonstrating its generalization capabilities to new object classes not seen during training.\n\n- In Figure 2, how are the node/edge features extracted from the image feature maps? Maybe the authors should describe it more concretely (step-by-step) for better understanding.\n\n- Could you clarify what EdgeID(0) and EdgeID(1) represent in Equation 6?\n- Please add training details in the paper. \n- I see codes for the comparative method URL (ICCV23) are available here. https://github.com/XLearning-SCU/2023-ICCV-COMMON", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UM5ORgwgRB", "reviewer": "Reviewer_Ruy3", "summary": "This paper focuses on partial matching problems in computer vision, aiming to address the problems of point occlusion and annotation errors. This paper proposes two components to address these challenges: 1) a structured universe graph is learned to connect two input graphs for point occlusion; 2) an energy-based out-of-distribution detection is designed to remove annotation errors from the input graphs before matching.", "questions": "1) The computational complexity of the algorithm is not compared.\n\n2) The paper lacks the visualization of results, including the visualization of ablation experiments.\n\n3) Universe Graph Matching essentially decomposes the ambiguous partial matching problem into two well-defined subgraph  matching problems. Universe Graph Matching can better deal with the occlusion phenomenon, but for the general situation, whether the matching accuracy will be improved. It might be better to do an analysis.\n\n4) Limitations and future work are not discussed.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The paper is well written and the theoretical and experimental analysis is basically complete\n\n2) The paper proposes two novel and effective approaches to address point occlusion and annotation errors in partial matching task\n\n3) The proposed method outperforms state-of-the-art methods, showing the effectiveness and robustness.", "weaknesses": "1) The computational complexity of the algorithm is not compared.\n\n2) The paper lacks the visualization of results, including the visualization of ablation experiments.\n\n3) Universe Graph Matching essentially decomposes the ambiguous partial matching problem into two well-defined subgraph  matching problems. Universe Graph Matching can better deal with the occlusion phenomenon, but for the general situation, whether the matching accuracy will be improved. It might be better to do an analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)