Learning Partial Graph Matching via Optimal Partial Transport
Authors: Gathika Ratnayaka, James Nichols, Qing Wang
ICLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The empirical evaluations on standard graph matching benchmarks demonstrate the efficacy of the proposed approach. Our contributions are threefold: (i) we introduce a novel optimization objective that balances matched and unmatched nodes; (ii) we establish a connection between partial graph matching and linear sum assignment problem, enabling efficient solutions; (iii) we propose a deep graph matching architecture with a novel partial matching loss, providing an end-to-end solution. The empirical evaluations on standard graph matching benchmarks demonstrate the efficacy of the proposed approach. |
| Researcher Affiliation | Academia | Gathika Ratnayaka1, James Nichols2, & Qing Wang1, 1 School of Computing, Australian National University, Australia 2 Biological Data Science Institute, Australian National University, Australia EMAIL |
| Pseudocode | No | The paper describes the methodology and architecture in narrative text and mathematical formulations but does not present a clearly labeled pseudocode block or algorithm. |
| Open Source Code | Yes | Our code is available at Git Hub: https://github.com/Gathika94/OPGMrs.git. |
| Open Datasets | Yes | We use three image keypoint matching datasets that inherently contain outliers: 1) the Pascal VOC Keypoint with Berkeley annotations (Everingham et al., 2010), which includes keypoint-annotated images from 20 classes; 2) SPair-71k (Min et al., 2019), featuring 70,958 high-quality image pairs from Pascal VOC 2012 and Pascal 3D+, covering 18 classes; and 3) IMC PT Sparse GM (Wang et al., 2023), a recently proposed dataset specifically for partial graph matching. |
| Dataset Splits | No | The paper states: "We follow the same experimental setting in (Wang et al., 2023)" for image keypoint matching and mentions for PPI networks: "noisy versions, which contain 5%, 10%, 15%,20%,25% additional interactions (low-confidence interactions), respectively." However, it does not explicitly provide the training, validation, and test splits used for its own experiments within the main text of this paper. |
| Hardware Specification | Yes | All experiments on efficiency analysis were conducted on a Linux server equipped with an Intel Xeon W-2175 2.50GHz processor (28 cores), an NVIDIA RTX A6000 GPU, and 512GB of main memory. |
| Software Dependencies | Yes | We use Sci Py s LAP solver (Virtanen et al., 2020), which is computationally efficient. In contrast, GCAN (Jiang et al., 2022b) formulates partial graph matching as an integer linear programming (ILP) problem, which is solved using Google s OR-tools (Perron & Furnon) in (Wang et al., 2023). |
| Experiment Setup | Yes | Hyperparameters For the image keypoint matching task, the hyperparameters of OPGM-rs are searched within the following ranges: ρ {0.1, 0.2, 0.3, 0.4, 0.5}, λ {0.01, 0.2, 0.3, 0.4, 0.5, 0.6, 0.8, 1.0}, learning rate {0.001, 0.002}, VGG16 backbone learning rate {0.0001}, batch size {4, 8}, and number of epochs {15, 20, 25}. To select ρ, we perform a grid search from 0.1 to 0.5 with a step size of 0.1. We use the Adam algorithm (Diederik, 2014) as our optimizer, and the initial learning rate decays by a factor of 0.5 after every two epochs. For the PPI network matching task, the hyperparameters of OPGM-rs are searched within the following ranges: ρ = 1011, λ {0.25, 0.5, 0.75, 1.0}, learning rate {0.0001, 0.0002}, and number of epochs = 100. The Adam algorithm (Diederik, 2014) is also used as the optimizer. |