Learning Structured Universe Graph with Outlier OOD Detection for Partial Matching

Authors: Zetian Jiang, Jiaxin Lu, Haizhao Fan, Tianzhe Wang, Junchi Yan
Primary area: applications to computer vision, audio, language, and other modalities
Keywords: graph matching

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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 8, 5, 6

Reviews and discussion:
<thread>
creation date:
1729871640312

thread_type:
official_review

<thread_object>
creator: reviewer_ruy3

<content>
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.

strengths:
1) The paper is well written and the theoretical and experimental analysis is basically complete

2) The paper proposes two novel and effective approaches to address point occlusion and annotation errors in partial matching task

3) 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.

2) The paper lacks the visualization of results, including the visualization of ablation experiments.

3) 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.

questions:
1) The computational complexity of the algorithm is not compared.

2) The paper lacks the visualization of results, including the visualization of ablation experiments.

3) 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.

4) Limitations and future work are not discussed.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730051023537

thread_type:
official_review

<thread_object>
creator: reviewer_mt6s

<content>
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.

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

  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?

- The generalization issue

  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.

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

- Could you clarify what EdgeID(0) and EdgeID(1) represent in Equation 6?
- Please add training details in the paper. 
- I see codes for the comparative method URL (ICCV23) are available here. https://github.com/XLearning-SCU/2023-ICCV-COMMON

questions:
Please address my concerns in weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730571950030

thread_type:
official_review

<thread_object>
creator: reviewer_1x7r

<content>
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.

strengths:
1. This work addresses a classic, significant problem in the literature by applying a modern deep-learning approach.

2. The proposed method outperforms both classical and learning-based methods, demonstrating robustness even in the presence of 
outliers and out-of-distribution (OOD) key points.

3. The authors discuss the limitations of their approach.

4. 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.

2. 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.

questions:
Typos:

- The URL paper is mis-cited in line 351/352.

- There is a typo in line 108
</content>
</thread_object>

</thread>
<thread>
creation date:
1730642647005

thread_type:
official_review

<thread_object>
creator: reviewer_24cj

<content>
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.

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.
2. 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]).

2. 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).

3. 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.

4. 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?

References:
A. 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.
B. Lin, Yijie, et al. "Graph matching with bi-level noisy correspondence." Proceedings of the IEEE/CVF international conference on computer vision. 2023.
C. 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.

-----
Post-discussion

After discussing and reviewing additional results, the authors addressed most of my concerns. I will raise my raiting.

questions:
1. What values of temperature, m_in, m_out, and threshold were used for the experiments?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730711128951

thread_type:
official_review

<thread_object>
creator: reviewer_6zax

<content>
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.

strengths:
- The motivation is good. The proposed method can be easy to follow because of the intuitive motivation.
- The paper is well-written, clear, and full of details.
- 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.

questions:
See weaknesses above. My main concerns are about the experiments.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731060594441

thread_type:
official_review

<thread_object>
creator: reviewer_saeb

<content>
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.

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.
2. 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)?

questions:
1. EdgeID in eqn.6 needs to be defined.
2. 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732102156709

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
**We sincerely thank all the reviewers for their thoughtful feedback and positive recognition of our work.** For instance, Reviewer SAEb commended that “the latent universal graph is novel and effective,” Reviewer Mt6s highlighted that “this approach has the potential to inspire future research in this area,” Reviewer Ruy3 acknowledged that “the paper is well written, and the theoretical and experimental analysis is basically complete,” and Reviewer 1X7r praised our method for “demonstrating robustness even in the presence of outliers and out-of-distribution (OOD) key points.” We deeply appreciate these encouraging remarks, which motivate us to further refine our work and contribute to the field.

Secondly, the reviewers have provided many invaluable suggestions, such as evaluating the generalization of our method to unseen classes, clarifying training details, conducting sensitivity analyses on hyperparameters, and addressing certain missing definitions or typos. **We have responded to most of these comments and have uploaded a revised version of the paper incorporating these improvements. All new additions and modifications in the manuscript are highlighted in red to facilitate the reviewers' review.**

Finally, due to the large number of comments and the limited time available, there are still a few suggestions we have not yet addressed, such as incorporating additional visualizations and further improving the readability of the paper. **We are actively working on these aspects and will continue to update our manuscript to ensure all issues are addressed before the rebuttal period ends.** Thank you for your understanding and constructive feedback.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732567881111

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Thank you again for your detailed and constructive feedback, which has significantly helped us improve our paper.

Since our last response, we have carefully addressed all remaining comments and suggestions from the reviewers. This includes incorporating additional visualizations, refining the readability of the paper, and ensuring all aspects of the reviewers’ feedback are thoroughly considered. The revised manuscript has been updated accordingly, and we have highlighted all modifications in red for easier review.

We hope the current version of the manuscript meets the reviewers’ expectations. If there are any further concerns or additional suggestions, please feel free to let us know. We are more than happy to address them to further improve the paper.

Thank you again for your time and thoughtful feedback throughout this process.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes a data-driven method for graph matching. This paper investigates the particular angle where graphs overlap partially or contain 'erroneous' nodes (e.g., such nodes may originate from annotation/network prediction errors). Such outliers violate assumptions implicit in standard graph-matching techniques based on quadratic (pseudo)-boolean formulations.

To this end, the proposed method encodes two input graphs (nodes and edges) and performs 1st stage matching. At this stage, the network predicts node/edge embeddings and performs (data-driven) inlier/outlier estimation that filters out erroneous nodes. Filtered (post outlier removal) nodes are inputs to 2nd stage matching network that utilizes consolidated methods (quadratic pseudo-boolean optimization, Swoboda et al., 2017). 

Different from prior art that directly performs matching between two given input graphs, the proposed method learns "universal graphs" that represent per-semantic-class graph priors. Matching between graphs A and B is then (i) first performed A $\to$ U, B $\to$ U, where U is the universal graph representing a certain semantic class. Individual matching results are combined to obtain the final matching.

The proposed method is shown to be robust and accurate on two widely used benchmarks for graph matching. 

The paper received overall positive ratings: 5, 6, 6, 6, 8.

Reviewers comment that the overall motivation (outlier issue) is great, and the proposed "latent universal graph" (that performs 1st stage matching and outlier removal) is novel and shown to be effective. Reviewers also find the paper well-written and detailed and appreciate good results. 

The paper received some criticism.

Reviewers 1X7r and 24Cj point out that the paper would benefit from improved writing, especially the abstract and introduction. The writing is quite technical and difficult to follow, and higher-level overviews and intuitions are missing. As 24Cj points out, this prevents the generalization to other matching problems (e.g., feature matching for geometric problems such as in 3D reconstruction or stereo matching). 

Reviewers also point out that the paper would significantly benefit from showing qualitative results, including visualizations of represented successful cases that cannot be solved in the baseline method, as well as failure cases of the proposed method.  

Reviewer Mt6s points out that closely related approaches were proposed in the domain of data-driven keypoint matching and utilized for solving real-world problems (image retrieval [A], image matching [B]).  These utilize two-stage networks that perform outlier estimation filtering and 2nd stage refinement. 

Overall, the author responded to criticism well and reached a consensus to recommend accepting this paper, with the exception of Mt6s (similar to the prior art). AC read the paper and references and finds the proposed work to have quite a different focus/core contributions (namely, the concept of universal graph for intermediate matching). 

Overall, we side with the reviewer's recommendation to accept this paper. However, AC strongly agrees that this paper would benefit from revising the presentation and urges the authors to consider the reviewer's comments and revise this paper. Specifically, the paper must clarify in the introduction that it is not investigating a general graph-matching problem but a niche problem within that space, where semantic classes must be known a priori. I suggest following 1X7r and 24Cj comments on revising the abstract, intro, and method section.  


**References:**

* [A] Learning Super-Features for Image Retrieval
(Philippe Weinzaepfel, Thomas Lucas, Diane Larlus, and Yannis Kalantidis). ICLR 2022.
* [B] Learning to Match Features with Seeded Graph Matching Network
(Hongkai Chen, Zixin Luo, Jiahui Zhang, Lei Zhou, Xuyang Bai, Zeyu Hu, Chiew-Lan Tai, and Long Quan). ICCV 2021.