Learning Partial Graph Matching via Optimal Partial Transport
Authors: Gathika Ratnayaka
James Nichols
Qing Wang
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Matching
Optimal Transport
Primary area: learning on graphs and other geometries & topologies

Abstract: Partial graph matching extends traditional graph matching by allowing some nodes to remain unmatched, enabling applications in more complex scenarios. However, this flexibility introduces additional complexity, as both the subset of nodes to match and the optimal mapping must be determined. While recent studies have explored deep learning techniques for partial graph matching, a significant limitation remains: the absence of an optimization objective that fully captures the problem’s intrinsic nature while enabling efficient solutions. In this paper, we propose a novel optimization framework for partial graph matching, inspired by optimal partial transport. Our approach formulates an objective that enables partial assignments while incorporating matching biases, using weighted total variation as the divergence function to guarantee optimal partial assignments. Our method can achieve efficient, exact solutions within cubic worst case time complexity. 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.

Published as a conference paper at ICLR 2025
LEARNING PARTIAL GRAPH MATCHING VIA OPTIMAL PARTIAL TRANSPORT
Gathika Ratnayaka's James Nichols", & Qing Wang',
School of Computing, Australian National University, Australia
2 Biological Data Science Institute, Australian National University, Australia (gathika ratnayaka, james nichols, qing wang) @anu. edu.
ABSTRACT
Partial graph matching extends traditional graph matching by allowing some nodes remain unmatched, enabling applications in more complex scenarios. However, this flexibility introduces additional complexity, as both the subset of nodes to match and the optimal mapping must be determined. While recent studies have explored deep learning techniques for partial graph matching, significant lim- itation remains: the absence of an optimization objective that fully captures the problem's 's intrinsic nature while enabling efficient solutions. In this paper, we propose a novel optimization framework for partial graph matching, inspired by optimal partial transport. Our approach formulates an objective that enables partial assignments while incorporating matching biases, using weighted total variation the divergence function to guarantee optimal partial assignments. Our method can achieve efficient, exact solutions within cubic worst case time complexity. Our contributions are threefold: (i) we introduce 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.
INTRODUCTION
Graph matching is fundamental problem in network analysis, aiming to establish one-to-one correspondences between nodes in two graphs based on defined objective. has broad applications across various fields, including computer vision (Sun et al., 2020), bioinformaties (Zaslavskiy et al., 2009), and social network analysis (Zhang et al., 2019), where is used to solve complex yeal-world problems. Traditional graph matching assumes bijective mapping between the nodes of two graphs or a total injective mapping from the smaller graph to the larger one. However, these assumptions often restrict its applicability in more complex, real-world scenarios. Partial graph matching, generalized version of the graph matching problem, addresses these limitations by allowing some nodes in both graphs remain unmatched (Wang et al., 2023; Jiang et al., 2022b). It seeks an optimal partial assignment, an injective partial function between node sets, thereby expanding the practical utility of graph matching. This approach is particularly useful in applications where not all nodes have meaningful counterparts. For example, in image keypoint matching, not all keypoints in two given images have correspondences (Jiang et al., 2022b), and in biological networks, certain proteins may lack direct counterparts in other species (Zaslavskiy, 2010).
Solving partial graph matching is inherently more complex than traditional graph matching due to the additional challenge of determining both the subset of nodes to match and the optimal mapping itself. Graph matching is generally framed as a combinatorial optimization problem, where the choice of optimization objective is crucial. Early works formulated it as Quadratic Assignment Problem (QAP). which is hP-hard (Koopmans & Beckmann, 1957; Lawler, 1963). Recent approaches (Wang et al., 2021; 2020a; Rolínek et al., 2020; Fey al., 2020) use neural networks to learn node representations and derive a cross cross-graph node-to-node cost matrix. This allows graph matching to be framed as linear assignment problem (Burkard al., 2012; Yu al., 2020), assuming

---

Published as a conference paper at ICLR 2025
bijective mapping between two node sets of equal size. Even if two graphs have unequal number of nodes, the problem can still be framed as a linear sum assignment by assuming an injective mapping from the smaller graph to the larger one (Bonneel & Cocurjolly, 2019; Wang et al., 2019b). A key advantage of this approach is that it can be efficiently solved with cubic worst-case time complexity using the Hungarian algorithm (Kuhn, 1955). However, Partial graph matching does not assume a total mapping, adding an extra layer of complexity. It requires selecting the subset of nodes to be matched while determining the mapping, making the problem more challenging. Consequently, traditional linear assignment methods like linear sum or k assignment cannot be directly applied.
Despite its challenging nature, recent studies have attempted to address the partial graph matching problem using deep learning techniques (Jiang et al., 2022b; Wang et al.. 2023). One approach (Jiang et al., 2022b) frames the problem as an Integer Linear Programming (II.P) task with dummy nodes. However, ILPs rely on branch and bound algorithms, which lack polynomial worst-case time com- plexity, and the use of dummy nodes can hinder node representation learning (Wang et al., 2023). Another approach (Wang et al., 2023) estimates the number of matchings (k) between two graphs, solving it as a k-assignment problem (Burkard et al., 2012) using Greedy TopK algorithm (Wang et al., 2023). However, determining the optimal & is difficult and requires separate neural modules, leading to multiple training stages. These limitations highlight the need for an efficient optimization objective that captures the inherent nature of partial graph matching.
Present work We address limitations in partial graph matching studies by proposing a novel optimization objective that finds optimal partial mapping between two node sets while identifying which nodes should be matched. While optimal transport has been previously studied for graph matching (Xu et al., 2019; Saad-Eldin et al., 2021; Chen et al., 2020), its conservation of mass constraint, requiring all mass to be transported between distributions, limits its applicability to partial graph matching. In optimal partial transport, the mass conservation constraint is relaxed, allowing partial mass to be transported, with the optimal amount of mass determined during the optimization process (Séjouréé et al., 2023; Bai et al., 2023). Although optimal partial transport and partial graph matching share similarities, i.e., both involve partial solutions, with the former identifying a plan where not all mass is transported and the latter finding a mapping where not all nodes are matched, they differ fundamentally. Partial graph matching requires the mapping to be an injective partial function (a partial assignment), while optimal partial transport does not. As a first step to bridging this fundamental difference, we reformulate partial graph matching as an optimal partial transport problem, where each node is assigned a unit mass and weighted total variation acts as the divergence function dynamically balance matched and unmatched nodes. The optimization problem accomplishes two critical objectives:
(i) it guarantees the existence of an optimal solution that induces a partial assignment, and (ii) it enables the incorporation of information related to relative significance of nodes to the matching process.
Based on these theoretical observations, we define new optimization objective for partial graph matching. We demonstrate that the proposed optimization objective for partial graph matching can be solved by embedding it in a linear sum assignment problem. This enables solving the partial graph matching problem within cubic worst case time complexity.
In summary, we make the following contributions this work:
We define a new optimization problem for partial graph matching, inspired by optimal partial transport. This formulation provides a robust optimization objective that carefully balances the selection of matched and unmatched nodes. Further, the formulation enables the incorporation of information related to the relative significance of each node to the matching process, which we term as matching bias.
To solve the proposed optimization problem efficiently, we explore the underlying structure of its solution spaces. This reveals a notable embedding of the partial graph matching problem in a linear sum assignment problem. Furthermore, the solutions of the latter assignment problem can be mapped efficiently to solutions of the partial matching problem, which are themselves optimal. This allows us to solve the partial graph matching problem exactly within cubic worst case time complexity.
Building the theoretical insights of our proposed optimization objective, we introduce deep graph matching architecture that embeds feature and structural properties into the cross- graph node-to-node cost matrix and matching biases. This architecture provides an end-to-end
2

---

Published as a conference paper at ICLR 2025
solution for the partial graph matching problem, incorporating novel loss function called partial matching loss.
We conduct experiments to empirically validate our proposed approach on partial graph matching benchmarks. The results demonstrate the efficacy and efficiency of the proposed approach.
2 RELATED WORK
2.1 DEEP GRAPH MATCHING
Several graph matching methods leverage neural networks to learn matching-aware node embed- dings (Jiang et al., 2022b; Rolínek al., 2020; Wang al., 2020a; Yu et al., 2020; Gao et al., 2021). These methods integrate cross-graph node affinity with feature and structural data to learn node embeddings. The learned embeddings then used to derive cross-graph node-to-node affinities. Then, the soft correspondences between nodes are typically obtained by applying Sinkhorn nor- malization on the cost-graph node-to-node affinity matrix. Once the soft correspondence matrix is obtained, it is projected into the space of permutation like binary matrices to achieve one-to-one node correspondences using algorithms such as the Hungarian algorithm (Kuhn, 1955) and Stable Matching algorithm (Ratnayaka et al., 2023), assuming total injective mapping from the smaller graph to the larger graph.
Optimal transport techniques have also been discussed to solve the graph matching problem (Xu et al., 2019), where each node in the source graph is matched to node in the target graph. Moreover, optimal partial transport techniques have been applied to subgraph matching (Pan et al., 2024), where a preset fraction of mass (corresponding to a fixed number of nodes) from a smaller graph is matched to nodes in a larger graph. This approach constrains the matching process by specifying in advance how many nodes from the smaller graph must be matched. However, these approaches are not directly applicable to partial graph matching, which requires identifying corresponding nodes between two graphs without any prior assumptions about the number of nodes to be matched. Moreover,spectra methods have been successfully applied both graph matching (Wang al., 2019a) and also to compactly encode maps between graphs and subgraphs (Pegoraro et al., 2022). While these problems share similarities in attempting to find correspondences node or graph level, they differ fundamentally from partial graph matching in their matching objectives and constraints.
So far, only a few deep learning approaches have addressed partial graph matching. Jiang al. (2022b) introduces dummy nodes to bypass explicit match number estimation, framing the problem as an Integer Linear Programming (ILP) task. However, ILP with branch and bound suffers from high time complexity, and the use of dummy nodes can distort node representations by implying higher similarity with unmatched nodes. Wang et al. (2023) attempts to solve partial graph matching as a k-assignment problem. However, the match count (k) between two graphs is not known in partial graph matching problem, their approach to handle partial matchings include two steps, first estimating the match count (k) by using separate neural module and solving entropic optimal transport problem and then using the estimated k value to solve partial graph matching as a k-assignment problem. This two step approach increase computational complexity and error propagation. Another line of work (Nurlanov et al., 2023; Jiang et al., 2022a) to perform partial graph matching have explored universe graph representation learning, where "universe" graph is constructed for each object class in keypoint- based image analysis. However, these methods require prior knowledge specific to each class, such as the exact number of distinct keypoints (nodes) class, making them difficult to generalize to graphs or images from previously unseen classes. In contrast, our work tackles a more general form of the partial graph matching problem, operating without class spesifc assumptions and accommodating graphs from unseen classes with arbitrary structures.
2.2 OPTIMAL TRANSPORT AND THE ASSIGNMENT PROBLEM
Assignment problems, especially the linear sum assignment problem, can be modeled as Optimal transport problem by considering assignment costs as transportation costs between two discrete distributions (Burkard et al., 2012). The Hungarian algorithm (Kuhn, 1955) which is well-known methods for solving the linear sum assignment problem, operates with a worst-case time complexity of On and is widely used in many real world applications (Munkres, 1957; Yu et al., 2020).
3

---

Published as a conference paper at ICLR 2025
In contrast to the linear sum assignment problem, partial graph matching be considered an assignment problem where elements in both sets can remain unassigned. This characteristic makes conventional optimal transport methods unsuitable for solving partial assignment problems. While efforts have been made to adapt optimal partial transport for partial assignments (Bai et al., 2023; Bonneel & Coeurjolly, 2019), these methods have limitations. (Bai et al., 2023) propose optimal partial transport formulation that can guarantee an optimal solution inducing a partial assignment between sets, but their algorithm is restricted to one-dimensional data with convex cost metrics, whereas partial graph matching typically involves higher-dimension cost functions. Moreover, their formulation does not account for matching bias of elements, which crucial in partial graph matching, especially in data-driven approaches where certain elements should be prioritized for assignment. Efficient algorithms (S (O(n²)) for solving partial assignments in aigee-dimenniooal spaces with general cost functions have not yet been developed, leaving a gap in the literature.
data and requires more flexible
BACKGROUND
Notations We denote the set of source elements Ws and the set of target elements as WT. We also use || || to refer the I norm, (.)r to refer the Frobenius inner product, and 1 to denote column vector of ones with elements. For any given matrix Rmxn and T2 denotes marginals of π where प = Tl, and T2 = Tm
Optimal Transport (Balanced) Let y E ERO and R be two non-negative vectors repre- senting distributions with equal total mass, such that || = -ell1. We are also given C' E Rm*xa where Cip denotes the cost of transporting unit of mass from location in the source W' to location j in the target set Wr. The (balanced) optimal transport problem considers all possible transport plans II,,,)) v) = {
matrix
[,,, 11, π 1mm = n} and is defined as,
min C). OT 14, u) =EI((L.))
The marginal conditions v1, = 14 and π -1mm = v impose the mass conservation constraint, ensuring that the total mass is transported from one distribution to the other.
Optimal Partial Transport In the optimal partial transport problem, the mass conservation con- straint is relaxed, allowing partial mass transportation between distributions. While some stud- ies (Chapel et al., 2020; Figalli, 2010) address predefined amounts of partial mass, we consider the optimal partial transportation problem where the amount of partial mass being transported determined by the optimization objective.
Let IIg (p, be the set of admissible partial transport plans defined as (u, ( E Rmxx Il,, S p1 π m S Sv}-
20
The optimal partial transport problem usually defined as OPT = min (T,, C) pD(T + p pD(T2ll)).
= (a.2))
Here, p > 0, which is also termed as the unbalancedness parameter, is used to control the tolerance for destroying or creating mass, and D(-I-) represents a divergence between two discrete measures. The term (T,, C)r captures the cost of transporting the mass by æ while pD(Tr)p) + pD(Tzllv) accounts for the mass that has not been transported.
In the optimal transport literature, Total Variation (TV) and Kullback-Leibler (KL) divergence are commonly used divergence functions (Séjourné et al., 2023). Using TV as the divergence function in optimal partial transport is known to identify zero entries in the optimal plan based on the cost matrix (Bai et al., 2023; Séjourné et al., 2023).
PARTIAL GRAPH MATCHING PROBLEM
We represent graph G (V, where V is the set of nodes and E is the set of edges. Let Gs = (Vs, Es) be the source graph and Gr = (Vr, Er) be the target graph for matching, with assume <
Vv = and [Vr Without loss of generality,
4

---

Published as a conference paper at ICLR 2025
In this work, we tackle the partial graph matching problem through the lens of optimal partial transport, which offers a flexible and efficient framework for dealing with graphs of different sizes and structures. To this end, we define an objective function that is well suited to partial graph matching task. We first state this objective as a general optimal transport problem, then adapt to our setting of graph matching.
We represent Vg and VT as mass vectors js E Imm and V E IR' respectively. We also assume a cost matrix C' E Rmxn, where Ci indicates the cost of moving unit mass from i E Vs to j Vr. We take inspiration from the use of the objective function defined in Eq. (3), and adapt it to our purposes. In particular, we use a weighted total variation (TV) divergence, which both ensures sparse optimal transport plans, and furthermore allows us to incorporate a matching bias to each node in the source and target graphs. The matching bias weights are given by two vectors, a E Rg for nodes in Vs and 18 for nodes in Vr, finally resulting in a objective function given by
TC( C, a, 3) = (T,, C)F + ((a, =1) (B, -2)))
As we consider marginal constraints m1, < 4 and π Tm S v, the weighted total variation diver- gences can be written (a., TI), and (B,v~ u In the general transport setting our set of feasible partial plans would be Ilg (H,, v) as defined as in Eq. (2), and the optimal partial transport problem with weighted total variation as the divergence function then is
WOPT v) == min TC(T; C, B).
(5)
=Ellg(
It should be noted that in our partial graph matching method discussed in Section 7, the cost matrix C, and matching bias values a and 3 are learned from data. In our setting however, we require optimal partial assignments rather than plans, meaning that each node in graph is matched to a node in the other graph or no node at all. We can define the set M of all m x n binary matrices representing possible partial assignments between Vg and Vi follows
M ( (0, 1) mx Vi E Vs. Σ Try S and Vj E VT, Σ Tay S 1).
j=1
For any π E M, Myy if and only if node E Vs is matched with node j E Vr. Given the graphs
Gs and Gr, the partial graph matching problem seeks to find an optimal π E M with respect to the objective given in Eq. (4), that is we are solving the
PGMp == min TC(T; c,,
(6)
REM
Note that the partial assignments form a subset of the partial transport plans between 1m and 1, that is M Ig (1m; 1n), and in fact we have that M = IIg (1m; 1n) n {0, 1)mmxm.
5 PARTIAL GRAPH MATCHING SOLUTIONS
In this section we demonstrate that partial assignments solutions of PGMp (i.e. that sit in M) do indeed occur in the solution set WOPT, p (1m: I,), which we can consider to be relaxed version of PGM,- We further note that in general solutions of WOPT, v) are not necessarily partial assignments as the marginal constraints might rule out solutions in M.
First we consider the following theorem, which shows that our choice of weighted TV defined in Eq. (4) can distinguish between feasible and non-feasible assignments.
Theorem 5.1 (Infeasible Assignments). Let x E arg minn (a.v) TC(T; C, a) be any optimal solution of Eq. (5). For any S i S m and S S n we have that Cit > p(a; + (3)) = TiJ =
From this theorem, we define C25 > p(a, + 33) as the feasibility condition for i and j. If the cost Cjj exceeds this threshold, no mass will be transported between i and j. When considering graph matching, this means that no assignment will occur between E Vs and E Vr.
Now consider the unit- weighted case, that is when μ 1m and 1, The following theorem demonstrates that there is at least one solution of Eq. (5) that is a partial assignment between Vs and Vr, i.e. is solution of Eq. (6).
5

---

Published as a conference paper at ICLR 2025
Theorem 5.2 (Existence of Optimal Solution). If 11 1m V/ 1n there exists optimal plan '²" E arg ((..)) (T; C, a, 3) such that πt E M.
For the remainder of the paper we consider μ 1m. V 1n and to distinguish our objective function in this case, we write TC to denote the total cost in this unit-weight setting, that is
TC(T; C, ax 8) = (T, F) + p(aa, 1m mi) + (3, 1, - T2))
(7)
From Theorem 5.2, when (T; C, or, 3) is the objective function of Eq. (5), there exists optimal plan π E M that ensures each node is either matched with at most one element or left unmatched, inducing a valid partial matching between Vs and Vr. Moreover, based on Theorem 5.1, , if og dg for two source elements p and q. then p is more likely to satisfy the feasibility condition with each target element compared to g, giving p higher chance of being assigned to target element.
6 SOLVING THE PARTIAL GRAPH MATCHING PROBLEM
Although Theorem 5.2 shows that there is always an optimal transport plan that induces a valid solution to the partial graph matching problem, it does not specify how find such a plan. In this section, we address this challenge. Our main result demonstrates that it is possible to derive a linear sum assignment problem for which a closed-for form mapping exists from any of its given solution to a solution of the partial graph matching problem defined in Eq. (6). The significance of this result that it allows us adapt the celebrate Hungarian algorithm to solve the partial graph matching problem with cubic worst-case time complexity algorithm.
Given two sets of elements with equal cardinality, the linear sum assignment problem aims to find bijective assignment that minimizes the total cost of assignment (Burkard et al., 2012). In order to demonstrate connection between the partial graph matching problem and the linear sum assignment problem, we first create set VD by appending (n - m) dummy elements to Vs, thus making
Vv = |rrl= = n. Let a,, > 0 be any value such that a. > max Ol.. We define a cost matrix 15i5m
C E R Raxx s.t.,
Ciji pla; B,).
if < is m and Cyjy S p(a, 33) if < S m and Cjp > p(a; 3j) p(a. + +z), if < i n.
Oz
(8)
Let P,, = (IT E {0, 10,11 xln = TI, = 1n denote the set of n x n permutation matrices. Then, consider the following linear assignment problem,
LAP(Vo, Vr,C) C) = min C)
(9)
FCP
We first establish an equivalence between the objective functions the partial graph matching problem in Eq. (6) and the linear sum assignment problem in Eq. (9).
To this end we define a closed form mapping that will obtain valid solutions to the original partial graph matching problem Eq. (6) from solutions of the linear write h : Ruan >> gmxx to denote the mapping which for S i S m and 1 S & n. is given by Tays Cf S p(a; + B,),
assignment problem Eq. (9). We
[MT]] 100l--10 (0
(10)
otherwise.
Lemma 6.1 (Equivalence). Given cost matrix C' and the weights a and B, any permutation matrix т E Pn will have h())) E M and l(()) satisfies (Tr, C)F (T()(T); C, + p(n m.)....
The following theorem effectively states that h(T²)) will be valid solution for our problem of interest.
Theorem 6.2 (Optimal Solution). x E arg argmin (T,, C)P, then x² = h((T)) ) is a solution of partial graph matching problem, that is n" arg min [C C, 3).
The proofs of all the theorems and lemmas including Theorem 6.2 are provided the appendix. Remark 6.3. It is known that the linear sum assignment problem be solved using the Hungarian algorithm, which has a cubic worst-case time complexity (Kuhn, 1955). Therefore, the worst case time complexity of solving the partial graph matching problem is Onn²).

---

Published as a conference paper at ICLR 2025
Matching Blas
Layer
Ground Truth (M)
Gy = (gg.g))
ANo
Affinity Miatrix
(A)
Partial Masching Loss
Node-to fo--tt---ii Node
Cost
Gy - (g).
Cost Matri
(C)
Figure 1: An overview of end-to-end learning architecture for partial graph matching. Given two input graphs Gs and Gr, neural network N NN generates cross-graph node-to-node affinity matrix A. The affinity matrix A is then used to learn the matching bias values a. 3, and also the cost matrix C. The partial matching loss is computed by taking into account the ground truth, C, a, and B.
7 PARTIAL GRAPH MATCHING ARCHITECTURE
In this section, we present an end-to-end learning architecture ( (Fig. 1) for partial graph matching, building upon the theoretical properties discussed earlier. This architecture learns both the cost matrix C' and the matching biases of nodes (a and (3). We also introduce novel loss function, partial matching loss, designed optimize performance in partial graph matching.
Graph Affinity Encoding Graph affinity encoding uses neural network NNg to transform ge- ometric affinities between nodes into node embeddings, leveraging their features and structural information. These embeddings are then used to construct matrix representing the cross-graph affinity between nodes in graphs Gs and Gr- Specifically, given two input graphs 9s and Gr. the neural network NNę G x G + Rmx" parameterized by 0, returns cross- poss-graph node-to-node affimity matrix A E R Essentially, the neural network NN₂ first applies an embedding function femb G Rmxd generate node embeddings femb(Gs, E Rmxdd and femb(Gr) E Raxd for the graphs 9s and Gr, respectively. Then, the affinity function faff : Rmxd x Raxd >> mR combines these embeddings compute cross-graph node-to-node affinity matrix such that
NNo GT) = safs Jema (Gm))
Matching Biases and Cost The matching biases and 3 calculated based on the cross-graph node-to-node affinity matrix A. Let A+ E TR be defined as A = max (ig. 0). For each node i e Vs. define r; maxigisn At.. Similarly, for each node Vr, define rj (a(wrs rτ) 0.5) for each E Vs and 8 2 (a(wrs x rz) 0.5) for each j E VT, where o(-) is the sigmoid function, and Wra 2 0 is learnable parameter. A value of a; 3, closer indicates higher chance of node or being matched, while value closer to 0 indicates a lower chance. Similarly, for By. value closer to suggests a higher chance of node being matched, and value closer suggests lower chance.
siaxisism A
The matching bias is then caleulated as a;
We compute the cost matrix C' between the nodes of Gs and Gr by applying Sinkhorn normalization (Sinkhorn, 1964) to the cross-graph node-to-node affinity matrix A. This normalization transforms A into a doubly stochastic matrix S [0, 1] m|xx such that S1, = Im and ST1,, S I, (Knight, 2008). The cost matrix E [0, 1|mxx is then derived from with each element defined as C.5 Sip for all nodes i in Gs (where < S m) and j in GT (where 1 < < n).
Partial Matching Loss We have two primary learning objectives during training: (1) learning the matching cost matrix C, and (2) learning the matching biases and / of nodes in the source and target graphs. Below, we propose a new loss function that integrates these two learning objectives.
Let I(-) denote the indicator function. Using the feasibility condition from Theorem 5.1, define the matching attention matrix as:
Zij TM2 or Cÿ & spaa + 92))
7

---

Published as a conference paper at ICLR 2025
Based on Z and the ground truth matching matrix M M, propose the loss term Leost to guide the learning of the matching cost matrix C::
Cost
Σ 1.3
Ziz MMg log(1 - Cit) + (1 --j) log(())))
node pair is included in the loss Leost under two conditions: (1) The ground truth indicates the pair
should be matched (M = 1). or (2) The pair should not be matched (Mi, = 0) but the matching cost below the feasibility condition (Ci, S p(a; + 92)). According to Theorem 5.1, pairs exceeding the threshold are infeasible and thus are not penalized in the loss, as they cannot produce false positives.
To guide the learning of the matching biases a and B. we propose the loss term Liias:
m Lbins E ail + Σ (MT1m)) [1 8,12.
n
The goal of Loias is to increase the matching bias of node that should be matched. The partial matching loss is defined as L = Leost + XLbias, where E (0, 1] is the regularization parameter.
EXPERIMENTS
We evaluate the performance and robustness our proposed approach through several experiments: (1) We evaluate the efficacy of our approach through experiments on image keypoint matching datasets and Protein-Protein Interaction (PPI) networks under varying noise levels; (2) We analyze the effects of the matching biases and 33 on overall performance by considering two model variants: OPGM, with fixed equal matching biases (a 1m: 3 1,), and OPGM-rs, with learnable matching biases. Note that when training OPGM, I, = Leost, we do not need to learn matching biases. (3) We conduct a sensitivity analysis on the unbalancedness parameter p and regularization parameter À to understand their impact partial graph matching performance; (4) We analyze the runtime efficiency of our approach compared to other baselines. Our code is available at GitHub: https: / thub. www.coootttiieecccc 94 /PPGMMS git.
8.1 EXPERIMENTAL SETUP
Image Keypoint Matching this task, we focus on image keypoint matching, which aims to find corresponding annotated keypoints between two given images. 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-annotte annotated images from 20 classes; 2) SPair-711 7 (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 SparseGM (Wang al., 2023), a recently proposed dataset specifically for partial graph matching.
Experimental Setting. We follow the same experimental setting in (Wang et al., 2023). A pre-trained VGG16 model (Simonyan & Zisserman, 2014) is used to extract visual features of annotated image keypoints. Graphs are created using the extracted keypoint features following the same protocol as in (Wang et al., 2023). We use the neural network proposed in GCAN (Jiang et al., 2022b) NNg to learn node embeddings and compute the cross-graph node-to-node affinity matrix.
Consistent with (Wang et al., 2023), we report the matching Fi-score as the evaluation metric. When reporting the results, we run 5 random starts and report the 95% confidence interval as the error bars, similarly to (Wang et al., 2023). We considered the following baselines: NGM-v2 (Wang et al., 2020b), GCAN (Jiang et al., 2022b), AFAT-U (Jiang et al., 2022b), and AFAT-I (Wang et al., 2023). We consider the implementation and results reported for baselines in (Wang al., 2023)! for evaluations. In Table 1, and Table 2(1eft), GM Network denotes the neural network architecture that each of the given baselines used learn node embeddings and to obtain the cross-graph node-to-node affinity matrix (A). PMH indicates the technique that is used to distinguish matching vs non-matching nodes and obtain the final partial matching.
8

---

Published as a conference paper at ICLR 2025
Network
FMH
bost
potio
pluze
abeop
dummy
NOM-22
AFAT-1
43.5
32.4
00.31
39:7
68.6
16.1
46.3
51.4
41.3
77.0
81.1
89.4
+0.4
NGM-2
AR314
50.4
43.6
63.9
32.1
61.2
58.5
35.0
68.4
15.7
62.7
56.4
47.7
51.9
44,5
78.5
56.7
79.2
91.2
56.4 200.4
GCAN
41.3
64.0
30.3
55.
57.4
64.8
64.4
46.4
68.4
83.3
91.9
542-0.3
APALU
33.3
54.9
35.2
47.2
43.5
53.8
GUAN
AMAH
46.8
84.3
05.9
12.4
61.5
53.8
33.7
08.0
38.1
60.1
56.3
47.9
48.3
43.8
81.2
48.4
82.5
95.0
50.3
20.4
OCAN
OPGM
51.9
43.8
66.6
18.9
60.9
00.6
57.8
678
17.
64.3
68.9
47.6
47.8
43.1
77.5
49.
80.1
911.
56.5
+0.4
Table I: Performance (matching Fl Fl-score) on the dataset SPair-71K. The best results are colored in black and the second hest are in blue.
Inference time
Dutset Name
IMCPT 50
IMCEPT LU0
tekchsing
pr
pegerers
561.1
NGMM-2
dammy
$8.5
56.1
63.0
66 3103
80.0
$1.0
71.5
06.510.3
NGM-2
NGM-2
AFAT-U
APATT
90.5
92.3
55.7
65.7
72.8884
72.0a0.3
$2.0
57.0
$7.0
12.2
71.4
70.120.3
70.360.2
400
367.1 371.8
GUAN
67.2
68 4603
06
GOAN
APAT-D
M69
67.1
41.1404
$2.6
75.8
71.540.2
200
117.8
GUAN
APRTJ
91.0
68.3
67.5
72.9:86
K2.7
57.8
72.4
70980.4
GCAN
91.2
57.0
68.1
72.1002
39.1
72.350.4
GUAN
OPGM
91.1
99.2
67.0
72.760
8233
69.5
75.7
7288661
OPGM
APArd
APAT-U
GCAN
Table 2: (left) Performance (matching Fl-score) on the datasets IMCPT 50 and IMCPT 100, where the best results are colored in black and the second best are in blue; (right) Inference time of our model OPGM-rs against the tfte-of-thhe-at methods AFAT-I, AFAT-U, and GCAN on the dataset IMCPT 100.
PPI Network Matching In this task, we focus on Protein Protein Interaction network matching under varying noise levels. PPI network matching dataset is a standard graph matching benchmark that can be used to evaluate performance of a graph matching model under various noise levels (Liu et al., 2021; Ratnayaka et al., 2023). It is a protein protein interaction (PPI) network of yeasts, consisting of 1004 proteins and 4920 high-confidence interactions among those proteins. The PPI network matching problem is to match this network with its noisy versions, which contain 5%, 10%, 15%,20% 2,5% additional interactions (low-confidence interactions), respectively.
Experimental Setting. We adopt the experimental settings of the baseline methods SIGMA (Liu et al., 2021) and StableGM (Ratnayaka et al., 2023) and use node correctness (the percentage of nodes that have the same matching as the ground truth) as the evaluation metric, similarly to (Liu et al., 2021; Ratnayaka et al., 2023). The neural network architecture NNg follows the design used in these baselines, where each node's input feature derived from its degree. A 5-layer Graph Isomorphism Network (GIN) (Xu et al., 2018) is employed. Node-to-node affinities across graphs are computed using the cosine similarities of node embeddings. Note that PPI network matching focuses on finding bijective mapping between two graphs with an equal number of nodes. As shown in Theorem 5.1, our method achieves bijective mapping for sufficiently large p. Hence, we set p = 10 for this task.
SIGMA
StaNeGMM
SPain-TKK KK
IMCPT 100
SPair-IK
IMCPT
OPGM-F
80
80
Node Conrectness
80
F1-Score (5))
F1-Seore (%)
70
70
60
50
50
40
40
10
15
20
0 0.2
0.4
0.6
0.8
Noise (%)
P
Figure 2: (left) Performance (node correctness) of our model OPGM-rs -rs against SIGMA and StableGM on PPI Network Matching with varying noise levels; (middle) Sensitivity analysis of our model OPGM-rs on the unbalancedness parameter (right) Sensitivity analysis of our model OPGM-rs on the regularization parameter A. Performance in sensitivity analysis is measured by matching F1-score.

---

Published as a conference paper at ICLR 2025
8.2 RESULTS AND DISCUSSION
Ext-1 Architecture efficacy Table I presents the results for the Spair-71K dataset (Table 1). Both OPGM and OPGM-rs outperform other baselines in terms of mean Fc-score and achieve superior results in 11 out of 18 classes. The Spair-71K dataset provides several advantages over the Pascal VOC Keypoint dataset, including higher image quality, richer keypoint annotations, and the removal of ambiguous annotations (Rolínek et al., 2020). Evaluations on the Pascal VOC Keypoint dataset are discussed the appendix, where our models perform slightly worse than some baselines, likely due to the poor and ambiguous annotations in Pascal VOC (Rolínek et al., 2020). These results highlight the effectiveness of our approach for visual graph matching, particularly on high-quality datasets like Spair-7IK.
Table 2 (left) presents the results for the IMCPT 50 and IMCPT 100 datasets. On the IMCPT 100 dataset, models achieve higher mean Fl-scores than the baselines and outperform them in out of 3 classes. For the IMCPT 50 dataset, our method performs comparably to the best baselines. Notably, the IMCPT 100 dataset, with the largest number of nodes among visual graph matching datasets (Wang et al., 2023), showing the efficacy of our approach for partial graph matching.
As shown in Fig. 2 (left), OPGM-rs consistently outperforms other baselines across all noise levels for PPI network matching (see the appendix for numerical results). However, at higher noise levels, the performance gap between OPGM-Is and StableGM narrows.
Ext-2 Impact of matching biases From the results given in Tables and and Fig. 2 (left), it is clear that OPGM-rs consistently outperforms OPGM in most cases, highlighting the importance of learning the matching biases of nodes in partial graph matching.
Ext-3 Sensitivity analysis We evaluated the impact of the unbalancedness parameter p and the regularization parameter À on partial graph matching performance using Spair- and IMCPT 100 datasets. For p. we varied its values while keeping other hyperparameters fixed. As shown in Fig. 2 (middle), mean F1 Fl-sscoess highlight p's critical role: smaller values restrict valid matches, while larger values may allow incorrect matches, both reducing performance. For X, starting from 0.01, we tested X E {0.2, 0.4, 0.6, 0.8, 1} with fixed hyperparameters. As shown in Fig. 2 (right), the mean Fl-scores show slight variation, indicating that the impact of À is not significant.
Ext-4 Efficiency analysis We evaluated the average runtime for processing a pair of graphs (i.c., keypoint-annotatel images) during the inference phase for OPGM-rs, GCAN, AFAT-I, and AFAT-U using the IMCPT 100 dataset, the largest image keypoint matching dataset (Wang et al., 2023). Matching was performed on 3,000 keypoint-annotated pairs. As shown in Table 2 (right), OPGM-rs demonstrates significantly lower inference time compared to the other models. It is important to note that all models use the same neural network architecture from (Jiang et al., 2022b) (corresponding to NN₂) to compute the cross- gross node-to-node affinity matrix A and the Sinkhorn algorithm to derive the doubly stochastic affinity matrix S, differing only in their partial matching techniques.
CONCLUSION AND LIMITATIONS
In this work, we proposed a new problem formulation for partial graph matching based on optimal partial transport. Our approach can dynamically determine which nodes would be matched or left unmatched during the optimization process. We demonstrate how our problem formulation enabled solving the partial graph matching problem within cubic worst case time complexity. We then showed how our proposed solution for partial graph matching can be effectively integrated to a learning setting. Evaluations on various partial graph matching benchmarks demonstrate that our method outperform the basclines in most of the benchmarks. Beyond these specific tasks discussed in this work, the optimization problem we proposed and the solution mechanism we developed can be adapted any application requiring optimal partial assignment between two sets.
While our proposed method demonstrated strong performance on datasets with reliable annotations, its effectiveness diminished when faced with unreliable or ambiguous annotations, or higher noise levels in the data. Enhancing the robustness of our method under these challenging conditions an important direction for future work.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This research was supported partially by the Australian Government through the Australian Research Council's ' Discovery Projects funding scheme (project DP210102273), We also would like thank anonymous reviewers for their comments, which helped improve the quality of the paper.
REFERENCES
Yikun Bai, Bernhard Schmitzer, Matthew Thorpe, and Soheil Kolouri. Sliced optimal partial transport. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp.
13681-13690, 2023.
Nicolas Bonneel and David Coeurjolly. Spot: sliced partial optimal transport. ACM Transactions on Graphics (TOG), 38(4):1-13, 2019.
Rainer Burkard, Mauro Dell' Amico, and Silvano Martello. Assignment problems: revised reprint. SIAM, 2012.
Luis Caffarelli and Robert McCann. Free boundaries in optimal transport and monge-ampere obstacle problems. Annals of mathematics, pp. 673-730, 2010.
Lactitia Chapel, Mokhtar Z Alaya, and Gilles Gasso. Partial optimal tranport with applications on positive-unlabeled learning. Advances in Neural Information Processing Systems, 33:2903-2913, 2020.
Liqun Chen, Zhe Gan, Yu Cheng, Linjie Li, Lawrence Carin, and Jingjing Liu. Graph optimal transport for cross-domain alignment. In International Conference Machine Learning, pp.
1542-1553, PMLR, 2020.
P Kingma Diederik. Adam: A method for stochastic optimization. (No Title), 2014.
Mark Everingham, Lue Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. International journal of computer vision, 88(2): 303-338, 2010.
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. arXiv preprint arXiv:2001.09633 2020.
Alessio Figalli. The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2):533-566 -600 2010.
Quankai Gao, Fudong Wang, Nan Xue, Jin-Gang Yu, and Gui-Song Xia. Deep graph matching under quadratic constraint. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5069-5078, 2021.
Zetian Jiang, Jiaxin Lu, Tianzhe Wang, and Junchi Yan. Learning universe model for partial matching networks over multiple graphs. arXiv preprint 10. 2022a.
Zheheng Jiang, Hossein Rahmani, Plamen Angelov, Sue Black, and Bryan M Williams. Graph- context attention networks for size-varied deep graph matching. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 2343 22522, 2022b.
Philip A Knight. The sinkhom algorithm: convergence and applications. SIAM Journal on Matrix Analysis and Applications, 30(1):261-275 2008.
Tjalling C Koopmans and Martin Beckmann. Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society, pp. 53-76, 1957.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97 1955.
Fugene I. Lawler. The quadratic assignment problem. Management science, 94)::566-59, 1963.
11

---

Published as a conference paper at ICLR 2025
Linfeng Liu, Michael C Hughes, Soha Hassoun, and Liping Liu. Stochastic iterative graph matching. In International Conference on Machine Learning, pp. 6815-6825. PMLR, 2021.
Juhong Min, Jongmin Lee, Jean Ponce, and Minsu Cho. Spair-71k: A large-scale benchmark for semantic correspondence. arXiv preprint arXiv:1908. 10543, 2019.
James Munkres. Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics, 5(1):32-38, 1957.
Zhakshylyk Nurlanov, Frank R Schmidt, and Florian Bernard. Universe points representation learning for partial multi multi-graph matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 1984- 1992, 2023.
Wen-Xin Pan, Isabel Haasler, and Pascal Frossard. Subgraph matching via partial optimal transport. In 2024 IEEE International Symposium on Information Theory (ISIT), pp. 3456-3461. IEEE, 2024.
Marco Pegoraro, Riccardo Marin, Arianna Rampini, Simone Melzi, Luca Cosmo, and Emanuele Rodolà. Spectral maps for learning subgraphs. arXiv preprint arXiv:2205. 2022.
Laurent Perron and Vincent Furnon. Or-tools. URL https: httpps::/deeellpprrs..og/ aptimization.
com/
Gathika Ratnayaka, Qing Wang, and Yang Li. Contrastive learning for supervised graph matching. In Uncertainty in Artificial Intelligence, pp. 1718-1729. PMLR, 2023.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, and Georg Mar- tius. Deep graph matching via blackbox differentiation of combinatorial solvers. In European Conference Computer Vision, pp. 407-424. Springer, 2020.
Ali Saad-Eldin Benjamin D Pedigo, Carey E Priebe, and Joshua T Vogelstein. Graph matching via optimal transport. arXiv preprint arXiv:21 2021.
Thibault Séjourné, Gabriel Peyré, and François-Xavier Vialard. Unbalanced optimal transport, from theory to numerics. Handbook of Numerical Analysis, 24:407-471, 2023.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogmition. arXiv preprint arXiv:1409.1556 2014.
Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. The annals of mathematical statistics, 35(2):876-87,, 1964.
Hui Sun, Wenju Zhou, and Minrui Fei. survey on graph matching in computer vision. In 2020 13th International Congress Image and Signal Processing, Bio.edical Engineering and Informatics (CISP-BMEIJ) pp. 225-230. IEEE, 2020.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapcau, Evgeni Burovski. Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Ker,, Eric Larson, C Carey, Îlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 10.100884415522-09--0666
Fu-Dong Wang, Nan Xue, Yipeng Zhang, Gui-Song Xia, and Marcello Pelillo. A functional representation for graph matching. IEEE transactions on pattern analysis and machine intelligence, 42(11):2737-2754 2019a.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 3056-3065, 2019b.
Runzhong Wang. Junchi Yan. and Xiaokang Yang. Combinatorial learning of robust deep graph matching: an embedding based approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020a.
12

---

Published as a conference paper at ICLR 2025
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's quadratic assignment problem with extension to hypergraph and multiple- calliple-graph matching. IEEE Transactions Pattern Analysis and Machine Intelligence, 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. He Liu, Yidong Li, Jin, Xiaohui Hou, and Haibin Ling. Learning combinatorial solver for graph matching. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 7568-7577, 2020b.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov-wasserstein learning for graph matching and node embedding. In International conference machine learning, pp. 6932-6941, PMLR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2018.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with channel-independent embedding and hungarian attention. In International conference learning representations, 2020.
Mikhail Zaslavskiy. Graph matching and its application in computer vision and bioinformatics.
Theses, École Nationale Supérieure des Mines Paris, 2010.
Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert. Global alignment of protein-protein interaction networks by graph matching methods. Bioinformatics, 25(12):129-11267 2009.
Wen Zhang, Kai Shu, Huan Liu, and Yalin Wang. Graph neural networks for user identity linkage. arXiv preprint 1eXx::9903002144 2019.
13

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 EQUIVALENCE BETWEEN OPTIMAL TRANSPORT AND OPTIMAL PARTIAL TRANSPORT
Inspired by (Bai al., 2023; Caffarelli & McCann, 2010), we show that the optimal partial transport problem proposed in Eq. (5) has an equivalance with an optimal (balanced) transport problem. In the following we will write || E |ps] or || = _ij==1 [Tyl to denote the 1-norm or sum of elements of probability vectors and matrices noting that all 14, Tay 0.
Let K be a constant satisfying K 2 ||l| + ||]|a and we define extended vectors D, E R as
Mi -
if S m,
Uj { (K- ||l|a)) if m < i m + and Bs
if S n, if < S +
i.s
and note that |A1|1 |0111 K. We define Ô ((m==))(n+n)) such that
CCp pla, + Bj) if S and j S
Ci.y
(11)
if otherwise.
We consider the following balanced optimal transport problem between the extended vectors ja that optimizes over the set of admissible couplings I1 D) = {x E R 20 ju, π m- i}-
(m+ x(m+n)
T Tlm+n
OT(A, D)
min (T, (T, C). =gMl(p,))
(12)
We claim that there exists an equivalence between this OT problem and Eq. (5). Proposition A.1 (Equivalent Cost Couplings). For any â, E [í D) with #[1 mi[1 n|
#' ml m] =
(Ō,5) = =O,,")
and
TO(T;C,a,3) = (C, f) + p(lla|l + ([111)).
Proof. Based on the definition of Ć we can derive that for any E I[ 8),
(C, (),)r
Caj
Together with the above result and the fact that #[1 ml[1
#' m][1 : n, we can derive
m
2
m
(.,)pp = ΣΣ
C5J =
ΣΣ
Capl'y = (0,
(13)
1=1
j=1
i=1
Thus, (C,
From Eq. (7), we know that,
= C) +l((a, 1, m1) + (8, 1m -T2)
= (Ci p(as + (;))) + p(1aa) + [1
==
= (, f) + p(laa)) + +11111)
where in the last step we used Eq. (13). Thus, the proof is complete.
14

---

Published as a conference paper at ICLR 2025
Proposition A.2 (Equivalence of Minimizers). For any ft [[(p))) that minimizes equation 12 then the top left comer π = #[1 m|[1 n| satisfies π E IIg (1, v), and x furthermore minimizes equation 5.
Proof. For any Ā [[ 2), let A[1 mi[1 [1 n] = π.
From the definitions of and v, we know that pi1 m] = μ and 011 n] v. Therefore, T S μ and S v. Thus, т E IIg 1/).
From Proposition A.I, we know that,
TC C,a,), (Č, () p(laall + 11.111).
We also know that for any á I( 3 E (u, s.t. #|1 mi[1 n]. Therefore, TC(#; C,a,9) is minimized when (C, ftr is minimized. Consequently, for any [T D) that minimizes Eq. (12) then the top left corner #[l m|[1 n| satisfies e ll,( v), and furthermore minimizes Eq. (5).
A.2 PROOFS
Theorem 5.1 (Infeasible Assignments). Let x= E arg minn (a.)) [T C, 0) B) be any optimal solution of Eq. (5). For any 1 S i S m and S S we have that Cij p(a: + (3) m 0.
Proof. When total variation is assumed the divergence function ((I-)), Eq. (4) can be written as TC(T; C, a, B) = (T, C)F + p ((a, - x1) + (3, 18,v-100 -
(8,v-Tz))
For any given source sample E Vs and any given target sample E Vr, we can write TC( C, a. a, by separating the terms related to masses of p E Vs and q Vr (See Eq. (7) well).
TC(T;C,a,3)
Σ Σ
Cg +
Σ 15 149
TTp Cps +
Σ 1sism ipp
Tze Cig + Cp
Kisslsiss i/
149
+p
Σ
ad(m - (T1)s) ( aap
Hp
Σ
Tpj
Ty
Isism ipp
1 18j5n
+p
Σ
8 (TT))) + By
14
Σ 1545m A
Tig
Ty
18j5n Ap4
We consider two plans n, n' E (T, v) such that Tg # m/p but otherwise mij mly for all other 1 & i S m ,1 E S n. Note that this is possible as they are partial transport plans that do not have strict marginal equality constraints. In this case we find that
TC(T; a, 3) TC(a, 3, C) (Tpq
(Cm + B,))
We note that this implies strict monotonicity of the total transport cost if Cpg plaz + Bg) 0, i.e. that TC(T; C, B) > TC(a, n', C") if Tpq > Tpp-
Therefore, if Cpg p(app + 3,) > then the optimal strategy is always going to be to set ag = ensuring the lowest total cost possible. In other words, if for any sample p Vs and q Vr.
Omg > p(a, + 3,), it is always less costly to transport no mass from to
Therefore, if n-" II (H, be any optimal solution of Eq. (5). Then, Vi Vs. Vj E Vr, if Cj > p(a; + B,) then mł = 0.
15

---

Published as a conference paper at ICLR 2025
Theorem 5.2 (Existence of Optimal Solution). If μz 1m V 1n there exists optimal plan TT E arg (g..e) [T; C, a; 3) such that πT" E M.
Proof. Let us define extended vectors v = 1m+n fa 1m+n- Once again we make use of the matrix C' as defined in Eq. (11).
Next, we consider the following optimal transport problem that optimizes over the set admissible couplings [[ 2) = [ E R (m++) (m)tt)
20 | |
f Im; IT mmtn = G = 1 1mta).
OT(A, min {T, C).
(14)
Tell(p.0)
From the results of Appendix 1. we can derive that the optimization problem OT D) given in Eq. (14) has clear equivalence to the optimization problem OPT,(1, given in Eq. (5) when K = m + n. From Appendix A. we also know that the optimal plan for Eq. (5) can be obtained by restricting an optimal plan स E arg x {x, C) to the set [1 m] x [1 [1:
It should be noted that when i = mm and jr tn the set [ī D) corresponds to the set of doubly stochastic matrices. By the Sorkhoff-von-eeummnn theorem, it is known that the set of doubly stochastic matrices forms convex polytope and its extremal points are permutation matrices. From the Linear Programming theory, over a polytope (here, it is the set of doubly stochastic matrices) lies at extreme point of the polytope. Thus, there always exist an optimal plan क E [[ which is a permutation matrix. Therefore, the optimal plan n arg minn (C(T; C, ax,3) that is obtained by restricting such arg min (T, C. (which is permutation matrix) to its restriction [1 m] x [1 n] (i.e., ग #[1 m]] n)) will be a binary matrix with atmost one I per row column. Therefore. we can always find an optimal plan x* E arg minngg(ww)) TC(T;; C, a, 3) s.t. π E M.
known that at least one optimal solution to a linear program
Lemma 6.1 (Equivalence). Given cost matrix C' and the weights and B, any permutation matrix Pn will have h()) E M and h(T) satisfies (7, C)F TC(h(T); C, C, B) p(n m m)a..
Proof. We first recall the definition of given component-wise Eq. (8) by if m and Cej p(a: (3)) if S m and Ci > p(a; + 3,)
Cijy Ciz = pla; + 3,), p(a. + Bz),
if > m
We use case-by-case definition decompose the Frobenius inner product. We now define index sets of rows and columns which indicate where म takes a value of that violates the conditions for setting Ciy. that
m, m,j such that Fiz = and Cj S p(a; + {B)} J ((..)):
I = ((i,)) ((t:):lsiism15:
n, such that Fij = 1 and Cj p(a; + 8,)}
K- ((i.)) :m :::::iiss:
n, <
n, such that Fyz = 1}
and note that the sets disjoint within [1....,n} x {1, f1....,ni n). We now decompose the inner product as follows
T.. C)
Σ Cigh(TTa +p (I
(as (ai+ B,) + (FU)ET
(as
Σ (a. + B.
(N.J)K
where we have immediately used the fact that Taz = h(T), for all (i,5) E I. Note furthermore that I is exactly the index set where h(x)) is non-zero, hence that
Σ (LJ)EI
We recall the notation h(T): that denotes the first marginal given by (I(() = Ej= h(T) For any fixed row index i where for some the pair (i, E J, then the the marginal vectors have values
16

---

Published as a conference paper at ICLR 2025
(T1); 1 whereas (h(T)1); O. On the other hand, if for fixed i if there is pair (i,j) J, then the marginal is given by (h(T))) = but it does not contribute to the sum, and we see that we have
O3 E (M(T))):)a.
We have a similar logic for the column sums, with the exception that some of the marginal mass is accounted for in the index k, similar to above have that
Σ 3 +
BIT T 11-
(.JEJT
(F.))K
j=1
Finally, is complete permutation, we know that each row < é S n has some index j for which Fe = and hence
Σ (KJ)EX
a (n mm)a.
All put together this yields
(T,, C) (C,((T))
Σ 1 (h(T)))) + Σ (h(TT))) + (n m)a,
j=1
(CCN(T)) + 1m - h(=))) + (8, 1, - h(T)2)) + p(n m)a+
C,, p(n m)a..
Before we prove Theorem 6.2, we prove the following two technical lemmas which will be used to prove Theorem 6.2.
Lemma A.3. Let E M be solution for the partial graph matching problem, that is nT*
argmin TC( C,,,,, 8), For any S S m and any S S n,
(( 0) and (( 0) = Cpg 2 p(a, + Bg)
Proof. We prove this by contradiction and assume there exist p, such that (T = O, (TT)₂ = O. and Cpg < p(ap + Bg). As (xi), = and (Tā)₂ 0, TC(m"; C, a. (3 can be expanded
C, Σ Σ
CiyCitt +p
Σ 18i5 ipp
a=(1 (Ti):) ap
1sism 15j5n 1pp 374
+p
3 (TZ),) + Bg 15jSa J#4
Σ
Now we consider a plan n' E M such that p4 = 1, but otherwise THy TH for all other 1 < i S m and 1 j n. Note that this is possible mass of p and g is not transported in π²" Based on marginal constraints, we know that " implies that TTI = 0 for all j * 9 and क = 0 for all
i # p. Therefore, TC(''; C, a. 3) can be rewritten as,
T,( Σ
Σ
ClSCis + Cpa
Σ
a; (TT)s)
15i5m 15j5n
15ism
17p j74
ifp
+p
Σ
85(1 - (T/21)
15jSa
Jfq
17

---

Published as a conference paper at ICLR 2025
Thus we that the difference in the objective between these two plans is TC(T', PC(*";C,or a, Cpq p(ap + 8q), and finally Cpg < plap + Bgy we have
TC(T';
However, this is contradiction x² arg arg (T C, 3). Therefore, the assumption wrong. Thus, for any x² E airgmin MiM (T(;;; C), (Ti)p = and (m²)₂ = 0 implies that Opg p(ap + (g).
Lemma A.4. Let x² E M be solution for the partial graph matching problem, that is "t" arg giM (T( C) Then, there exists π Pn such that {T,, C) ( p(n m)....
Proof. Let us consider some π arg min (T; C,a,8) Our objective is to show that we can find n' Pn such that TC(a, C, + (n m)a* (ग', C) where C' E Rax= defined as Eq. (8)
First, we extend ı to n' E (0, 1)ax by padding with zeros, defnnigg it as
Tiji
if i S m
if m.
The idea of the proof that follows is that we define a permutation matrix P,, that is equal to where it is 1, but fills in the unmatched nodes with some arbitrary permutation. That is, we assume decomposition s.t. for all i Sn
Ty = T + fijs
(15)
with T/j = 1 if uij 1, and we note that the marginals satisfy कı क| + #1 1, and m2 =
T2 + #2 = 1,, Now the total cost function Eq. (7) can be rewritten as
T, = (T, C)p +
Σ
aa((f)) Σ (y((2)
By the definition of Tey. we know that for all i > m, F.. = 0. Therefore, for all i > m, #1 = 1.
Thus, we have,
Σ
( = (n - m))
i=++1
Therefore, can derive the following,
m
1
TC(T; C, + p(n m)a+ = +
Σ
ai (+i): Σ
B, +
Σ (#1):a
j=1
i=m+1
Σ
Σ
pla: + -ij +
Σ
p(Bz + +..
1<ism 18/5n
13t5m 13j5R
mciin 15$5a
(16)
The contrapositive of Theorem 5.1 tells us that as π is optimal, Taj = implies that Ct. S p(a, 3,))
By definition of n'. we know that, T/I if and only Tij 1. so hence T/ also implies that Cj S p(a; + B2). Thus, based on the definition of C in Eq. (8), we can deduce that
Σ CrpCi
Σ 13
Cr
Σ Cip 13t5 13,5n
(17)
13
13/50
13,5
18

---

Published as a conference paper at ICLR 2025
From Eq. (15), we know that, for any 1 S i,j S Myj if and only if (T(); 0 and (T2)) 0.
Moreover, from the definition of x², for any i m and 1 S I n, (T{); = and (xb) = 0
and only if (T1); 0 and (Ta) = 0. And, from Lemma A.3, we know that (T));
and (Ta)
implies that Ciy 2 p(a: + [g). Therefore, for any S i S m and 1 j S n, #iy = implies that Cij 2 p(a; + B5) hence that Cip p(a; + B,)) Thus, we can deduce,
Σ p(a: + B,) 18is 1875
Σ C.yCij isism 1315n
(18)
From definition of C, we know that for all i> mn pla, + Bg). Therefore, have,
Σ
( + ar )a. = Σ C
(19)
mciSn 15
15/5n
From Eqs. (17) to (19), and using the fact that m/, for mn <is n. can rewrite Eq. (16)
C, + p(n m)a,
Σ
Σ
CiyC
Σ micisn ISJSn
C.
Isis
Isism
15f5n
13J5n
Σ
Cryy +
Σ
Ci.Cii
i 13/3a
1sisa
13/5n
= ( C)
(20)
Theorem 6.2 (Optimal Solution). If x" E arg min (n, C)p, then x² = h(m²)) is solution of partial graph matching problem, that is n" E arg MMM (T,T;,,,,
Proof. Let π E arg (T O) be any optimal solution of Eq. (9) and x* E
arg MMM TT(;;; C, a, B) be any optimal solution of Eq. (5)
From Lemma A.4, we know that, there exists a E Pa s.t. Therefore,
= = C).
(F. S (,,, C) TŌ(="; C, 3) p(n m)a. From Lemma 6.1, we have h(TT) E .M as defined in Eq. (10) from म* such that the following condition holds,
(21)
(C(((=)); a, 3) + (n - mmaa = (T,
(22)
Finally, from Eq. (21) and Eq. (22).
TC(((T"): C, 8) + p(n m)a, &TC(T"; 3) p(n mmmma-maa m))=
and as n² is already a minimizer TC, implies that TC(,(T); 3) TC( C,a, which indicates that h(T²)) E arg min ( C, 8))
Thus, from any म* arg mill EP. (T,, F' which is an optimal solution of Eq. (9), it is possible to derive h(T=)) E arg aingingeM TC(T; C, a. 9),, which solves Eq. (6)). Thus, the proof complete.
B ADDITIONAL. DETAILS ON EXPERIMENTS
Discussion on PascalVOC and PPI Network Matching As shown in Table 3, OPGM and OPGM- rs achieve lower mean matching Fl-scores compared to the AFAT-U (GCAN) and AFAT-I (GCAN) models. This is mainly due to the poor performance of OPGM-rs in the table and sofa classes, which are known to have ambiguous and poor annotations. Notably. these classes were excluded from the SPair-71K K dataset for the same reason (Rolínek al., 2020).
19

---

Published as a conference paper at ICLR 2025
dog
prnum
sherp
NGM-22
46.2
61.9
5%.1
41.9
83.9
63.9
54.1
60.3
40.5
36.2
68.6
S6L
61.9
46.7
91.2
96.2
37.
63.2
12.2
NGM-1
ABSTA1
45.7
67.7
41.9
96.1
66.1
49-5
15.3
61.8
45.3
90.9
37.3
60 60-34044
NGM-2
45.0
50.92003
ARATU
47.1
45.8
19.6
657
46.3
52.7
GCAN
AR33
46.1
465
90.7
66.1
46.1
$1.9
59.3
61.
65.0
44.7
50.9
49.3
74.0
GCAN
OPGM
46.5
70.1
55.5
47.
89.5
62.4
46
66.8
68.9
55.4
46.2
56.9
56.2
67.7
47.7
96.9
51.5
42
73.1
82.9
00.8 204
CCAN
OPGM-
47.1
71.
97.
479
89.
66.
46.
61.3
50.0
65.4
332
594
61.
68.7
48.3
98.6
53A
39.9
76.1
88.1
61.00 2012
Table 3: Matching F1-score on Pascal VOC Keypoint. The best results are colored in black and the second best are in blue
Method
Yeast 5%
Yeast 10%
Yeast 15%
Yeast 20%
Yeast 25%
SIGMA
84,710.4
42.5
57.411.1
46.7 12.3
41.4
StableGM
86.1 +: 0.9
75.6 10.8
67.9 1.1
63.2 1.0.9
$7 4: 0.5
OPCM (ours)
87.8 0.3
50 10.4
71.9
10.9
66.9 11.0
58.8 10.8
OPGM-i (ours)
88.3 00.5
79.8 #0.6
71.7 :0.8
66.2 +0.9
57.7 11.0
Table 4: Node correctness (%) results the PPI dataset. The best results colored in black and the second best in blue
In PPI network matching, as shown in Table 4, OPGM-rs generally outperforms OPGM at lower noise levels, but OPGM demonstrates better performance noise increases. This behavior can be attributed to the learnable cost matrix C in OPGM-rs, which is utilized during training. When inputs are noisy, the information in C' may also become noisy, and simultaneously learning and B alongside C' can negatively impact the training process under high noise levels. These observations indicate that OPGM-rs is more sensitive to poor ambiguous annotations and increased noise in the data, which adversely affects its performance.
Discussion on efficiency analysis As detailed in Section 8, all the models analyzed in Table 2(right) use the same neural architecture (Jiang et al., 2022b) to compute the cross-graph node-to-node affinity matrix and apply Sinkhorn normalization to obtain the doubly stochastic affinity matrix.
Our model, OPGM-rs, solves the partial graph matching problem as described in Section 6 by solving linear sum assignment problem (LAP). We use SciPy'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 s OR-tools (Perron Furnon) in (Wang et al., 2023). Solving an ILP problem is generally more computationally expensive than solving a linear sum assignment problem using LAP solvers.
AFAT-I and AFAT-U models introduce additional complexities by employing separate neural modules to estimate the number of matchings between graphs. This process includes solving an entropy regularized optimal transport problem, followed by the Greedy TopK algorithm (Wang et al., 2023), which is based on the Hungarian algorithm, to compute the final matching. These extra steps increase the average inference time of AFAT-I and AFAT-U compared to OPGM-rs.
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.
Hyperparameters For the image keypoint matching task, the hyperparameters of OPGM-rs are searched within the following ranges: p E {0.11 0.2, 0.3, 0.4, 0.5). E {0.01, 0.2, 0.3, 0.4, 0.5, 0.6, 0.8, 1.0), learning rate E (0.001, 0. 0.002}. VGG16 backbone learning rate E {0.0001), }. batch size {4, 8). and number of epochs f15, 20, 25}. To select p. 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: p = 10t1 X (0.25, 0.5, 0.75, 1.0). learning rate E {0.0001, 0.0002), and number of epochs 100. The Adam algorithm (Diederík, 2014) is also used the optimizer.
Failure mode analysis The feasibility of matching pair of nodes and j is influenced by their cost Cijy the matching biases ag and By. and the hyperparameter p. A specific failure mode we observed
20

---

Published as a conference paper at ICLR 2025
Mismatching
Partiality
Total
Error Rate (%)
IMCPT100
IMCPT30
Spair7
VoC
Datasets
Figure 3: Failure mode analysis across four different datasets.
is when node pairs that should be matched according to the ground truth deemed infeasible by the optimization objective Eq. (9) (as described Theorem 5.1). Consequently, these nodes remain unmatched in the final solution. This failure mode typically arises when the graph matching network NN, assigns an excessively low affinity (resulting in a high matching cost) to pairs of nodes that should otherwise be matched.
We quantify the error by analyzing:
Partiality error: The percentage of true matches (as per the ground truth) that fail to meet the feasibility condition outlined in Theorem 5.1. This error reflects mismatches caused by incorrect partiality identification involving matching biases.
Mismatching error: The percentage true matches that are identified as true matches even though they meet the feasibility condition.
Figure 3 demonstrates the partiality error, mismatching error and total error related to this failure mode across four different datasets. The total error is equal to the summation of partiality error and the mismatching error.
21


Reviews:
[{"review_id": "pNecfIPXc6", "reviewer": "Reviewer_i3qN", "summary": "The paper proposes a new optimization framework for partial graph matching, a variant of traditional graph matching that allows for some nodes to remain unmatched. This flexibility accommodates complex real-world scenarios, where not all entities have a direct counterpart. The authors introduce an optimization objective that balances matched and unmatched nodes using concepts from optimal partial transport, providing an efficient, cubic-time complexity solution via the Hungarian algorithm.", "questions": "please address the points mentioned as weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper applies concepts from optimal partial transport to graph matching, resulting in a framework that handles partial assignments rigorously. By connecting the problem to the linear sum assignment, the authors leverage the Hungarian algorithm, achieving cubic time complexity—an important advancement for handling larger datasets.\n\n- Experimental results on multiple datasets illustrate the proposed method’s robustness and competitive edge over established baselines, particularly in terms of matching F1-scores and runtime efficiency.\n\n- The end-to-end architecture, with its unique loss function, offers practical advantages for data-driven applications, adapting dynamically to different matching scenarios.", "weaknesses": "- The paper shows that the proposed model’s performance decreases dramatically with increasing noise level, with the PPI dataset. Although the proposed method performs better than other methods generally. The performance decrease rate is similar or enven larger than other methods, as shown in Fig 2 (left). \n- It seems the approach’s performance is sensitive to the unbalancedness parameter ( \\rho ), as shown in sensitivity analyses.\n- For applications where annotations are inconsistent or sparse, such as biological or social network datasets, the model’s dependence on well-annotated data could limit its generalizability.", "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": "fuar4SWMA1", "reviewer": "Reviewer_HfMe", "summary": "The paper proposes a new objective for partial graph matching based on total variation and partial optimal transport. The paper shows that this formulation leads to a specialized version of optimal transport, and one optimal solution exists in the unit-weight setting. \nThen, the paper proposes to solve the problem by adapting the Hungarian algorithm and training a neural network to learn two components: the matching cost matrix and the biases to represent the matched and unmatched nodes.\n\nThe experiments cover protein-protein interaction networks and image key-point matching, showing results under different noise levels and analyzing the method's efficiency.", "questions": "Please, refer to the weaknesses section comments for the major questions I would see addressed in the rebuttal.\n\nMinor:\n1) line 075: multiple missing spaces: \"transportidentifies\", \"transportcan\", \"transportdoes\"\n2) The recent work \"Spectral Maps for Learning on Subgraphs\", Pegoraro et al., NeuReps 2023, seems relevant for the paper. In particular, the paper suggest to use spectral properties to infer properties on subgraphs, and also correspondence. Similarly \"A functional representation for graph matching\", Wang et al., PAMI 2019, propose to use spectral properties to compute matching on (full) graphs. I believe a discussion on this line of works would be interesting.\n3) How does the method perform in case of rewiring of the partiality?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) The paper addresses a challenging and fundamental problem, with an impact on several down stream domains. The derivation lead to a formulation includes also a computational complexity statement for the problem, which seems useful for future works.\n2) The general formulation is interesting and leads to a concrete network formulation. The network seems practical, and the authors have attached the code, so I am confident the work can be reproduced.\n3) Although the performance does not push the state of the art further, the method seems particularly more computationally efficient.", "weaknesses": "1) The method requires setting a series of hyperparameters tailored for the domain, which might be difficult in practice. For example, by my understanding, the parameter \\rho seems quite important and encodes the amount of partiality. This is quite an assumption, and it would be nice to find some heuristics to fix it automatically (e.g., the ratio of the number of nodes or the graph radius, etc.). Could you offer a comment on this, and in case a possible heuristic? Is it possible to explicitly relate \\rho to the amount of partiality?\n2) Since this work is a bit outside my direct expertise, I had a hard time grasping all the details, especially building an intuition. The paper itself does not show visual results, and then it is not straightforward to understand how concretely the proposed methodology differentiates in terms of artifacts (e.g., is the error caused by wrong matching bias and partiality identification, or more about mismatching?) would be interesting to add some qualitative examples, especially for keypoint, that is particularly easy to interpret. Did you observe any specific failure mode or particularly challenging setting? Could you provide a visualization to support the intuition about the main source of the error?", "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": "HgYaEgALm0", "reviewer": "Reviewer_aXCT", "summary": "This paper introduces OPGM, which addresses the partial graph matching problem. It begins by establishing theoretical connections between optimal partial transport and the partial matching problem. The paper then presents a method that leverages this formulation to learn matching bias and a cost affinity matrix, improving the outcomes of partial graph matching. Experimental results on various datasets demonstrate that this method is comparable or better than existing approaches.", "questions": "1. How effective is the applied bias term in identifying non-matching points, and what are the false positive and negative rates? It would be important to quantify the effectiveness of the proposed scheme.\n\n2. What would the performance of other methods look like if they simply applied a thresholding scheme on their cost matrix similar to this study? An ablation study would be appreciated.\n\n3. How is the parameter $\\rho$ chosen? Is it chosen by some heuristics? Fig. 2 (middle) suggests that $\\rho$ values supporting better performance are quite narrow (0.35-0.4), and these values vary across different tasks. Determining this parameter is one of the most challenging aspects of partial matching, so it is essential to understand how to set $\\rho$ without extensive trial and error.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "The motivation behind the study is clear, and the results presented looks convincing.", "weaknesses": "1. The connection between optimal transport and the graph matching problem is already well-established, making it seem redundant to re-establish this connection in the partial setting.\n\n2. The use of the term “optimal” in the title may be misleading. A significant challenge in partial matching is setting thresholds ($\\rho$, $\\alpha$, $\\beta$ in this paper) to eliminate redundant points. The paper assumes these thresholds are predefined, which undermines the rigor of claiming their results as “optimal”.\n\n3. PascalVOC is still the most important benchmark for the graph matching community, including its result only in the appendix does not seem appropriate, especially when this method does not do better on this benchmark.\n\n4. The paper omits two critical references [1,2], both of which have achieved better results on PascalVOC.\n\n[1] Nurlanov et al., \"Universe Points Representation Learning for Partial Multi-Graph Matching\"\n\n[2] Jiang et al., \"Learning Universe Model for Partial Matching Networks over Multiple Graphs\"", "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": "9bfCyKSKUA", "reviewer": "Reviewer_KhhU", "summary": "The paper formulated the partial graph matching problem as an optimal partial transport problem, enabling partial assignments (not have to be a bijective mapping) between a source graph and the target graph.The linear solver Hungarian algorithm is adopted to the LAP objective.", "questions": "Theorem 5.1 about filtering infeasible assignments with a hard threshold seems to be not necessary even without a k-LAP algorithm. Since the proposed method will output an optimal partial matching in anyway, why it needs to filter out some infeasible assignments at the very beginning?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "1. Formulating partial graph matching problem into an optimal transport problem is natural. \n2. The objective is a linear assignment problem (LAP) and easy to be optimized.\n3.  Both qualitative and quantitative results on several commonly used datasets valid the effectiveness of the proposed formulation.", "weaknesses": "1. The main contribution of the paper is to formulate the partial graph matching problem into an optimal partial transport problem, which is not new [1,2] and is a common relaxation of the original quadratic objective of graph matching involving both vertices and edges constraints (into a linear assignment problem).\n2. Line 065 is not 100% accurate since there are some efficient algorithms (e.g. [3] is quite intuitive and easy to implement as the k-LAP is transformed into a standard LAP that can be efficiently solved by the Hungarian algorithm) targeting towards k-assignment problem. As such, manually filtering out infeasible assignments with a hard threshold in Theorem 5.1 is not necessary.\n3. Some important references are missing [4,5].\n4. The objective of Eq(9) is almost equivalent to the first order term of Koopmans-Beckmann’s QAP with partial matching constraints in Eq(10), and the network design is the same as GCAN, together with the common linear solver Hungarian algorithm making the contributions both network design and optimization insight a bit marginal. In fact, one promising and more insightful way for the paper to stand out among others is to explicit formulate graph edges into optimal transport objective or constraints rather only implicitly involved into feature aggregation by GCN.\n\nTo conclude, the paper proposed an optimal transport objective with partial matching constraints for partial graph matching problem. However, I haven't seen any special design for the partial graph matching nor optimal transport.\n\n\n\n[1] Pan et al. Subgraph Matching via Partial Optimal Transport. arxiv, 2024\n[2] Xu et al. Gromov-Wasserstein Learning for Graph Matching and Node Embedding. ICML, 2019.\n[3] Volgenant et al. Solving the k-cardinality assignment problem by transformation. European Journal of Operational Research, 2004.\n[4] Fey et al. Deep Graph Matching Consensus. ICLR, 2020.\n[5] Gao et al. Deep graph matching under quadratic constraint. CVPR, 2021.", "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)