Learning Structured Universe Graph with Outlier OOD Detection for Partial Matching

Q: The computational complexity of the algorithm is not compared.

A: Regarding the solver component of our method, we utilized LPMP and its computational complexity is analyzed in [1]. For the deep learning network component, it is indeed difficult to derive a analytical complexity. Instead, we provide a runtime comparison with previous works.

[1] 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

Q: The paper lacks the visualization of results, including the visualization of ablation experiments.

A: Thank you for the suggestion. Due to time constraints and the need to address other feedback, we couldn’t include the visualizations in this version. However, we are actively working on them and will add them before the rebuttal deadline.

Q: 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.

A: When there is no occlusion phenomenon, as long as the universe graph is well-trained, Universe Graph Matching will not compromise the matching results. This is evident from the experiments shown in the middle of Table 3 (Willow Object dataset with additional random outliers only). While the improvement in this setting is less pronounced compared to the occlusion scenario, there is still a measurable enhancement in matching accuracy. This demonstrates that Universe Graph Matching is capable of maintaining or even improving performance in general situations, further validating its robustness and effectiveness.

Q: Limitations and future work are not discussed.

A: We have discussed limitation of our work in Section 4.3. "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 E, demonstrating the method's potential to adapt to 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_{iu}$ from propagating to all $X_{ij}$ matches."

Q: The paper lacks the visualization of results, including the visualization of ablation experiments.

A: Thank you for your valuable suggestion. We have added two visualization sections to the manuscript. One is included in the main text to showcase successful cases, highlighting the advantages of our method in partial matching through a clear comparison with baseline methods. The other is provided in the appendix, where we present the matching results for a random selection of image pairs to demonstrate the overall effectiveness of our approach. Additionally, we have expanded the ablation study to explore the sensitivity of hyperparameters. The corresponding visualizations and results have been updated in the main text.

Q: 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.

A: We have introduced our network details in Appendix B. Specifically, we fist compute the outputs of relu3_5, relu4_1 of the ResNet50, to obtain feature F1 and F2 respectively. These features are then concatenated to create the key point feature F, as well as class embedding. Then we apply an MLP layer to reduce the feature dim to keep the same dimension. We feed the obtained feature F and the graph adjacency A into the geometric feature refinement component. The graph adjacency A is generated using Delaunay triangulation based on keypoint locations. We apply SplineConv to encode higher-order information and the geometric structure of the entire graph into node features and edge features.

Q: Could you clarify what EdgeID(0) and EdgeID(1) represent in Equation 6?

A: Thank you for your reminder. EdgeID $\in N^{2 \times m}$ denotes directed edges in the graph. EdgeID(0) denotes the indices of the source nodes and EdgeID(1) denotes the indices of the target nodes. We have added the definition to our paper.

Q: Please add training details in the paper.

A: Thank you for your reminder. We added a training algorithm box in Appendix B, as well as all the hyper parameters used in training process. You can check the paper for more details.

Q: I see codes for the comparative method URL (ICCV23) are available here. https://github.com/XLearning-SCU/2023-ICCV-COMMON

A: It seems that the reviewer meant to refer to COMMON rather than URL.

Actually, the setting we study is entirely different from that of COMMON. COMMON focuses on standard graph matching, where all outliers have been pre-filtered. In contrast, we study partial matching, a setting that is closer to real-world applications.

Meanwhile, we did evaluate the performance of COMMON under the partial matching setting. However, due to the differences in settings, COMMON's performance was terrible. Reporting such results in the main paper might unfairly affect the reputation of other works. Therefore, we provided these results only in the rebuttal phase and do not include them in the paper.

F1 Score on Pascal VOC. Top shows the performance of unfiltered setting, and bottom shows the performance of 2 random outlier setting.

F1 score performance on Willow Object.

Q: 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?

A: As we mentioned in paper, "We define this latent U as a complete, directed graph, where every pair of nodes is connected by a directed edge. This ensures that any edge in the input graph will have a corresponding edge in the universe graph. Moreover, the directed edges capture the inherent asymmetry in real-world relationships between key points, such as varying geometric or contextual dependencies, offering greater flexibility in encoding complex structural information.”

Building on this, our approach indeed results in uneven sample distributions for learning edge embeddings, as discussed in the limitations section: “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.” Fortunately, if an edge appears rarely in the training data, it is also likely to appear infrequently in the test data. As a result, these under-trained embeddings have a minimal impact on the overall performance of the model. This aligns with the practical observation that the model can effectively generalize despite the imbalance in edge distributions.

Q: 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.

A: Yes, Universe latent graph is inherently limited to closed-set problems, relying on class information and training data, which restricts generalization to unseen categories. However, generalizing the universe graph to unseen classes requires only a small amount of labeled data.

To validate this, we conducted a few-shot test to compare the generalization ability of different methods. Specifically, the dataset is divided into two groups: 16 base classes and 4 few-shot classes. For the base classes, we provide all available training data, allowing methods to fully learn the features and structures of these categories. For the few-shot classes, we limit the training data to only 20 labeled images per class (about 5% of full data), simulating a typical few-shot learning scenario where labeled data is scarce.

The table shows the few shot learning performance on Pascal VOC under ‘unfiltered’ setting. F1 scores are reported on the left and the delta (compared to standard results in Table. 1) are reported on the right. UGM achieves an average delta of -8.63, significantly better than GCAN (-13.15) and NGMv2 (-12.03), with a lower standard deviation (4.16). This demonstrates UGM's ability to retain stable and competitive performance across few-shot classes, outperforming other methods in effectively handling the challenges posed by limited training data.

We provide more comprehensive results and analyses in Appendix E of the paper, where you can find further details.

Q: 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.

A: Thank you for the feedback. Due to time constraints and the need to address other comments, we haven’t revised it yet, but we will improve the abstract and introduction with more background on graph matching before the rebuttal deadline.

Q: 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.

A: In graph matching, it is customary to report matching accuracy for the intersection setting and F1 score for the partial matching setting, which is followed by by almost all previous works GMN, PCA, BBGM, NGMv2, DLGM, CIE, AFAT, COMMON, and URL.

F1 score is first used by BBGM. As it says “we propose to preserve all keypoints. Matching accuracy is no longer a good evaluation metric as it ignores false positives. Instead, we report F1-Score, the harmonic mean of precision and recall.”

In fact, matching accuracy is essentially the recall of matching predictions, while the F1 score can be considered an extended form of matching accuracy. This is because, in the intersection setting, recall and precision are identical, resulting in F1 score = recall = matching accuracy. However, in the partial matching setting, the F1 score takes false positive predictions into account, making it a more comprehensive metric than matching accuracy.

Q: 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.

A: Thank you for your valuable suggestion. We have improved the Introduction section by adding more explanations about graph matching and its mathematical formulation to make the paper more accessible to readers who may be less familiar with this field.

Q: 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?

A: Thanks for your suggestion. We add more sensitivity test on our hyper parameters temperature T, threshhold $\tau$, m_in, m_out in Section 4.4 ablation study. We also add our training details in Appendix B, including all these value we used in training.

Q: Outlier detection mechanism is weak. 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.

A: From a theoretical perspective, learning a function to detect random outliers inherently introduces bias. Random outliers refer to keypoints that do not belong to the predefined keypoint label set, and their occurrence is characterized by randomness and unpredictability. To simulate random outliers, we select coordinate points randomly across the image. Evidently, due to the variability of images, the distribution of these random outliers differs between the training set and the test set. Under such circumstances, using a learnable function to capture the characteristics of random outliers is prone to bias. Its behavior becomes difficult to interpret or control, especially when encountering edge cases or adversarial samples. In contrast, OOD detection based on energy scores does not introduce additional training parameters and is grounded in well-established theoretical foundations, making it a more reliable approach for detecting random outliers.

From an experimental perspective, AFAT has already proposed learning an attention-based function to detect outliers. However, the experimental results in Tables 2 and 3 clearly demonstrate that our method has a significant advantage over AFAT.

Q: 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.

A: Our method is not suitable for evaluation on the IMC-PT-SparseGM benchmark. The IMC-PT-SparseGM benchmark is a graph matching dataset focused on landmark buildings, containing images of 16 buildings, with 13 used as the training set and 3 as the test set. However, as discussed earlier, our method, UGM, cannot generalize to totally unseen categories. The buildings in the test set do not appear in the training set, and we are unable to construct their universe latent graph. Therefore, we did not evaluate our method on this benchmark.

Q: 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.

A: First, the setting we study is entirely different from that of COMMON. COMMON focuses on standard graph matching, where all outliers have been pre-filtered. In contrast, we study partial matching, a setting that is closer to real-world applications.

Secondly, the metrics used in these two settings are inherently different. It is customary to report matching accuracy for the intersection setting and F1 score for the partial matching setting, which is followed by almost all previous works GMN, PCA, BBGM, NGMv2, DLGM, CIE, AFAT, COMMON, and URL.

Finally, we did evaluate the performance of COMMON under the partial matching setting. However, due to the differences in settings, COMMON's performance was terrible. Reporting such results in the main paper might unfairly affect the reputation of other works. Therefore, we provided these results only in the rebuttal phase and do not include them in the paper.

F1 Score on Pascal VOC. Top shows the performance of unfiltered setting, and bottom shows the performance of 2 random outlier setting.

Results on Willow will update soon.

Q: 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.

A: Thank you for your reminder. $X_{iu}^{gt} \in \{0, 1\}^{n_i \times n_u}$ is a permutation matrix (discrete) which denotes the correspondence between input graph $G_i$ and universe latent graph. We have added the definition to our paper. Meanwhile, we offer a notation table in Appendix A to explain main notations and description used in this paper.

Q: 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?

A: For the claim that "keypoints from different categories are mapped to the same universe node", it's just a trade off between the size and node feature quality of universe latent graph. Different keypoints sharing the same node indeed compromises matching accuracy to some extent. However, it effectively prevents the size of the universe graph from increasing with the growth of categories, thereby enabling our method to achieve better scalability. Moreover, experimental results demonstrate that our approach surpasses the state-of-the-art (SOTA), suggesting that the performance degradation caused by this design choice is not as significant as we initially anticipated.

Q: 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]).

A: Attention-based approach has already been explored by GCAN and AFAT to either improve feature quality or reject outlier matchings. Both of them are compared to our method in all the experiments.

Q: 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).

A: Yes, Universe latent graph is inherently limited to closed-set problems, relying on class information and training data, which restricts generalization to unseen categories. However, generalizing the universe graph to unseen classes requires only a small amount of labeled data.

To validate this, we conducted a few-shot test to compare the generalization ability of different methods. Specifically, the dataset is divided into two groups: 16 base classes and 4 few-shot classes. For the base classes, we provide all available training data, allowing methods to fully learn the features and structures of these categories. For the few-shot classes, we limit the training data to only 20 labeled images per class (about 5% of full data), simulating a typical few-shot learning scenario where labeled data is scarce.

The table shows the few shot learning performance on Pascal VOC under ‘unfiltered’ setting. F1 scores are reported on the left and the delta (compared to standard results in Table. 1) are reported on the right. UGM achieves an average delta of -8.63, significantly better than GCAN (-13.15) and NGMv2 (-12.03), with a lower standard deviation (4.16). This demonstrates UGM's ability to retain stable and competitive performance across few-shot classes, outperforming other methods in effectively handling the challenges posed by limited training data.

We provide more comprehensive results and analyses in Appendix E of the paper, where you can find further details.

COMMON performance on Willow Object. F1 score is reported.

Q: 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.

A: Thank you for the suggestion. Due to time constraints and the need to address other feedback, we couldn’t include the visualizations in this version. However, we are actively working on them and will add them before the rebuttal deadline.

Q: Why there are no results reported in Table 2 and Table 3 for some related works listed in Table 1 (e.g., URL)? Are the experiments about other methods in Table 1, 2, 3 are re-implemented by yourself? Please explain it.

A: To clarify our approach to reporting the performance of prior works, we adhere to the following principles:

1. If a prior work’s experimental settings align with ours, we directly report the performance metrics provided in their paper.
2. For new experimental settings in our work, we replicate the prior methods under their original experimental settings and then adapt them to our own setting to obtain comparable performance metrics.

For the specific results reported in Tables 1, 2, and 3:

1. Table 1 and the random outlier setting of Table 3 reported experiments that have been conducted in prior works. Therefore, we directly report the performance metrics from their original papers.
2. The other experimental settings in Table 2 and Table 3 are new settings presented in our work. For these, we replicated the methods from prior works (e.g., BBGM, NGMv2, GCAN, and AFAT) based on widely recognized graph matching benchmarks ThinkMatch, and the open-source code provided by these works. We successfully reproduced their results on the Pascal VOC dataset and adapted these methods to our experimental settings to evaluate their performance.
3. However, for methods like DLGM and URL, the authors neither released their code nor provided sufficient details about their network architecture or training procedures. This lack of information made it infeasible for us to replicate their results. As a result, we did not report their performance in Table 2 and Table 3.

Based on your feedback, we have provided a detailed explanation in the "Compared Methods" part of Section 4.1 in the paper.

Q: 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.

A: Thank you for your valuable suggestion. We have added two visualization sections to the manuscript. One is included in the main text to showcase successful cases, highlighting the advantages of our method in partial matching through a clear comparison with baseline methods. The other is provided in the appendix, where we present the matching results for a random selection of image pairs to demonstrate the overall effectiveness of our approach.

Q: 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.

A: Yes, Universe latent graph is inherently limited to closed-set problems, relying on class information and training data, which restricts generalization to unseen categories. However, generalizing the universe graph to unseen classes requires only a small amount of labeled data.

To validate this, we conducted a few-shot test to compare the generalization ability of different methods. Specifically, the dataset is divided into two groups: 16 base classes and 4 few-shot classes. For the base classes, we provide all available training data, allowing methods to fully learn the features and structures of these categories. For the few-shot classes, we limit the training data to only 20 labeled images per class (about 5% of full data), simulating a typical few-shot learning scenario where labeled data is scarce.

The table shows the few shot learning performance on Pascal VOC under ‘unfiltered’ setting. F1 scores are reported on the left and the delta (compared to standard results in Table. 1) are reported on the right. UGM achieves an average delta of -8.63, significantly better than GCAN (-13.15) and NGMv2 (-12.03), with a lower standard deviation (4.16). This demonstrates UGM's ability to retain stable and competitive performance across few-shot classes, outperforming other methods in effectively handling the challenges posed by limited training data.

We provide more comprehensive results and analyses in Appendix E of the paper, where you can find further details.

Q: 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)?

A: 1）OOD data refers to keypoints that are not part of the predefined keypoint label set and cannot be mapped to any nodes in the universal latent graph. These points typically arise from erroneous or invalid keypoint annotations.

2）During training, random annotation keypoints (random choose a coordinate(x, y) on the image) are treated as OOD to enhance the model’s generalization to unseen distributions, not to mimic the true test OOD distribution. Meanwhile, the OOD keypoints for both training and testing are generated by random annotation, but the images used are entirely disjoint, ensuring no leakage of the test OOD distribution into training.

3）Yes, the generalization ability of our method is demonstrated by the experimental results. Since the OOD distributions for training and testing are generated independently and come from completely disjoint image sets, the test results inherently reflect the model’s ability to generalize to unseen OOD distributions.

Q: EdgeID in eqn.6 needs to be defined.

A: Thank you for your reminder. EdgeID $\in N^{2 \times m}$ denotes directed edges in the graph. EdgeID(0) denotes the indices of the source nodes and EdgeID(1) denotes the indices of the target nodes. We have added the definition to our paper.

Q: 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?

A: First, $X_{iu}^{gt} \in \{0, 1\}^{n_i \times n_u}$ is a (discrete) permutation matrix that defines the correspondence between input graph $G_i$ and universe latent graph. This is fundamental to understanding our method.

Equation 4 serves a theoretical purpose - demonstrating the equivalence between universe matching and pairwise matching representations. Methods like non-negative factorization [1] and spectral method [2] exist to convert between these representations. However, in practice, $X_{iu}^{gt}$ is directly obtained from keypoint annotations. Each keypoint has a semantic label (e.g., left eye, right shoulder) that naturally corresponds to a node in our universe graph, providing unambiguous ground truth universe matching.

[1] Florian Bernard, Johan Thunberg, Jorge Goncalves, and Christian Theobalt. Synchronisation of partial multi-matchings via non-negative factorisations. Pattern Recognition, 92:146–155, 2019.

[2] Deepti Pachauri, Risi Kondor, and Vikas Singh. Solving the multi-way matching problem by permutation synchronization. In NeurIPS, pp. 1860–1868, 2013.