M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering
Authors: Jiaxin Lu
Zetian Jiang
Tianzhe Wang
Junchi Yan
Venue: ICLR 2024 poster (2024)
Keywords: Graph Matching; Joint Optimization; Unsupervised Learning
Primary area: representation learning for computer vision, audio, language, and other modalities
TL;DR: We propose learning-free solver M3C and unsupervised learning model UM3C to address the problem of mixture graph matching and clustering.

Abstract: Existing graph matching methods typically assume that there are similar structures between graphs and they are matchable. This work addresses a more realistic scenario where graphs exhibit diverse modes, requiring graph grouping before or along with matching, a task termed mixture graph matching and clustering. Specifically, we introduce Minorize-Maximization Matching and Clustering (M3C), a learning-free algorithm that guarantees theoretical convergence through the Minorize-Maximization framework and offers enhanced flexibility via relaxed clustering. Building on M3C, we further develop UM3C, an unsupervised model that incorporates novel edge-wise affinity learning and pseudo label selection. Extensive experimental results on public benchmarks demonstrate that our method outperforms state-of-the-art graph matching and mixture graph matching and clustering approaches in both accuracy and efficiency.

Published as a conference paper at ICLR 2024
M3C: A FRAMEWORK TOWARDS CONVERGENT, FLEXIBLE, AND UNSUPERVISED LEARNING OF MIX- TURE GRAPH MATCHING AND CLUSTERING
Jiaxin Lu"i, Zetian Jiang"i, Tianzhe "aang",Juncii Yan
I Deparrment of Computer Science, University of Texas at Austin
2 DDeaarteett of Computer Science and Engineering, Shanghai Jiao Tong University jujiaxin@utexas. edu, (maple.jzt, usedt obe,
yar. janciuccii @ jtu. edu. on
ABSTRACT
Existing graph matching methods typically assume that there are similar struc- tures between graphs and they are matchable. This work addresses more real- istic scenario where graphs exhibit diverse modes, requiring graph grouping be- fore or along with matching, task termed mixture graph matching and cluster- ing. Specifically, we introduce Minorize-Maximizattin (M3C), a learning-free algorithm that guarantees theoretical convergence through the
Matching and Clustering
framework and offers enhanced flexibility via relaxed clustering. Building M3C, we further develop UM3C, unsupervised model that incorporates novel edge-wise affinity learning and pseudo label selection. Ex- tensive experimental results on public benchmarks demonstrate that our method outperforms state-of-the-art graph matching and mixture graph matching and clus- tering approaches in both accuracy and efficiency.
INTRODUCTION
Graph matching (GM) (Yan et al., 2020b) constitutes pervasive problem in computer vision and pattern recognition, with applications in image registration (Shen Davatzikos, 2002), recogni- tion (Duan et al., 2012: Demirci et al., 2006), stereo (Goesele et al., 2007), 3D shape matching (Berg et al., 2005; Petterson et al., 2009), and structure from motion (Simon et al., 2007). GM involves finding node correspondences between graphs by maximizing affinity scores, commonly formulated as the quadratic assignment problem (QAP), often referred to as Lawler's QAP (Loiola et al., 2007):
= arg max (X) Kvec(X)
s.t. X E {0, 1]m1 X X1,,, S 1,,, X 11,, S 1nz
(1)
Here, X is permutation matrix encoding node-to-node correspondences, and 1, is all-one vector. The inequality constraints accommodate scenarios with outliers, addressing the general and potentially ambiguous nature of the problem. Multiple graph matching (MGM) (Yan et al., 201 20;;;;;; Jiang et al., 2021) extends GM by enforcing cycle consistency among pairwise matching results. GM and MGM are both harhard, leading to the proposal of approximate algorithms, either learning- free (Yan et al., 2016) or learning- -aased (Yan et al., 2020a).
In GM, whether in two-graph matching multi-graph matching, a common assumption prevails: graphs must belong to the same category, and labels for both graphs and nodes required. How- ever, labeling can be costly, especially in domains like molecular design or drug discovery requiring domain-specific knowledge. Real-world scenarios involve mixtures of different graph types, e.g., in traffic tracing, frames may contain people, bicycles, and cars simultaneously. Matching with mixed graph types is a practical challenge in its nascent stage. In this paper, we introduce Mixture Graph Matching and Clustering (MGMC), aiming to align graph-structured data and simultaneously parti- tion them into clusters, as shown in Fig. 1. This task seeks to mutually optimize both matching and clustering problems, thereby enhancing the outcomes of both tasks: matching establishes a similarity metric for clustering, while cluster information improves the results of intra-cluster matching.
Recent studies have explored mixture graph matching and clustering in two works: Decayed Pair- wise Matching Composition (DPMC) (Wang et al., 2020b) and the graduated assignment neural
"Correspondence author. t denotes equal contribution. The SJTU authors in part supported by NSFC (92370201, 62222607) and STCSM ( 1051100.

---

Published as a conference paper at ICLR 2024
Table 1: Comparison of the existing three works designated for mixture graph matching and clus-
tering: DPMC (Wang et al., 2020b), GANN (Wang et al., 2020a), and ours: M3C/UM3C.
Methods
DPMC
GANN
M3C/UM3C (ours)
Optimization Space
Discrete
Continuous
Discrete
Framework
Graduated Assign
Supergraph Structure Joint Optimize Convergence Affinity I Learning
discrete tree
real-value edge fully connected
discrete and partly-connected
x
slow
fast
node
node and edge
Pseudo Label
unselected
selected w/ relaxed indicator 30% accuracy improvement over GANN
Empirical Robustness
mediocre
hardly work given outliers
network (GANN) (Wang et al., 2020a). However, they suffer from certain drawbacks that warrant attention: 1) Convergence. DPMC exhibits convergence instability, while GANN has slow conver- gence. 2) Rigid Structure. DPMC relies heavily on its tree structure, and GANN tends to converge to a sub-optimal due to its hard clustering nature. 3) Robustness. GANN's robustness is compro- mised by noise, shown in our experiments, where matching accuracy drops significantly with just two outliers and further deteriorates with more outliers.
We propose our solution, Minorize Maximization Matching and Clustering (M3C). M3C enjoys convergence guarantees and is based on a convergent alternating optimization solver. We utilize the cluster indicator from hard clustering to represent the discrete structure used for optimization, providing better information for graphs of different modes while preserving the convergence guar- antee of the algorithm. We additionally introduce UM3C. which integrates the learning- free solver into an unsupervised pipeline, incorporating edge-wise affinity learning, affinity loss, and a pseudo- label selection scheme for higher robustness. A comprehensive comparison with previous works is summarized in the appendix Sec. B with Table 1. The main contributions of this paper are:
We present M3C, a learning- free solver for the mixture graph matching and clustering problem, that guarantees convergence within the Minorize-Maximizatoen framework, enhanced by flexible optimization scheme enabled by the relaxed cluster indicator. This marks the first theoretically convergent algorithm for MGMC, to the best of our knowledge.
We enhance M3C by integrating it with an unsupervised pipeline UM3C. Edge-wise affinity learn- ing, affinity loss, and pseudo label selection are introduced for learning quality and robustness.
the---rr learning- free and learning-based methods on mixture graph matching and clustering experiments. UM3C even outperforms supervised models BBGM and NGM, establishing itself as the top-performer for MGMC on public benchmarks.
M3C and UM3C outperform
2 RELATED WORKS
Graph matching has gained attention recently, with various techniques explored, including spectrum, semi-definite programming (SDP), and dual decomposition (Gold & Rangara- jan, 1996; van Wyk & van Wyk, 2004; Cho et al., 2010; Tian al., 2012; Egozi et al., 2012; Swoboda et al., 2017; Xu et al., 2019: Zhang et al., 2019; Liu et al., 2021). Multiple graph matching (MGM) introduces cycle consistency as regularization to encourage matching transitivity, whose methods fall into two categories: matrix factorization- based (Kim et al., 2012; Pachauri et al., 2013; Huang & Guibas, 2013; Zhou et al., 2015; Chen et al., 2014; Leonardos et al., 2017: Hu et al., 2018; Swo- boda et al., 2019) and supergraph-basee approaches (Yan et al., 2015b;a; Jiang et al., 2021; Wang et al., 2020b). The former enforces cycle consistency through matrix factorization, connecting all graphs with a universe-like graph for global consistency. The latter iteratively updates two-graph matchings by considering metrics along the supergraph path. Recent studies explore deep learning methods for feature extraction and learning-fres frree neural network solvers for matching (Zanfir & Sminchisescu, 2018; Wang et al., 2019; 2021; Wang et al., 2020; Rolínek et al., 2020; Yu et al., 2021; Wang et al., 2020a; Liu et al., 2020; Nurlanov et al., 2023; Fey et al., 2020; Jiang et al., 2022b; Lin et al., 2023; Jiang et al., 2022a), covering both supervised and unsupervised learning pipelines.
Graph Matching
Graph Clustering In this paper, we tackle graph clustering, which aims to group similar graphs. One approach involves embedding each graph into Hilbert space and using clustering methods like k-means (Xu & Lange, 2019) Previous work (Wang al., 2020b;a) commonly use Spectral Cluster (Ng et al., 2002) based on pairwise affinity scores. Another approach (Hartmanis, 1982; Poljak & Rendl, 1995; Trevisan, 2012; Goemans & Williamson, 1995) utilizes max cut (De La Vega & Kenyon, 2001; Festa et al., 2002; Poljak & Rendl, 1995; Trevisan, 2012; 2; Goemans & Williamson,
2

---

Published as a conference paper at ICLR 2024
1995), treating input graphs nodes in supergraph and assigning weights edges based on pairwise scores. Alternatvv formulations for graph clustering include min cut (Johnson et al., 1993), normalized cuts (Xu et al., 2009), and multi-cuts (Kappes et al., 2016; Swoboda & Andres, 2017).
Mixture Graph Matching and Clustering Matching with mixtures of graphs entails finding node correspondence and partitioning graphs into clusters with works: DPMC (Wang et al., 2020b) and GANN (Wang et al., 2020a). GANN introduces GA-MGMC, a graduated assignment-based al- gorithm optimizing the MGMC problem in continuous space, followed by projecting results to discrete matching. DPMC, learning- -fre solver, constructs a maximum spanning tree on the super- graph and updates matching along the tree. Another work (Bai et al., 2019) embeds the input graph for matching into an embedding vector for graph clustering. Joint matching and node-level clus- tering are explored (Krahn et al., 2021), solving node correspondence and segmenting input graphs into sub-graphs. This paper focuses on the joint graph matching and clustering problem, a relatively new area in the literature. It represents an advancement for more open settings.
BACKGROUND AND PROBLEM FORMULATION
We introduce some preliminary concepts, definitions, and the proposed problem formulation in this section. The definition of notations are introduced in Appendix Sec. A.
Definition 1 (Matching composition). Matching composition involves combining pairwise match- ing results to enhance the initial matching configuration: X X X .... ..Xi,, We further
define the matching composition space of 9; and 9j to encompass all possible compositions between them Px(i.j) (Xik) ... ...kjl E N+ S k .h...., k, S N).
Definition (Supergraph), Supergraph is a common protocol for describing multi-graph matching The supergraph S = {V,E, E, } consists of vertices corresponding to graphs V -19,.-. GN and edges weighted by pairwise matching affinity scores Xij, with adjacency A [0, NKN
Each path on the supergraph corresponds to a matching composition. The weight of the path from
9; to Gj is defined as the affinity score of the matching composition: X.j = Xisk, Xki k Kk.jj The matching composition space of 9; and Gj can be represented as all the paths from 9i to 93 on the supergraph: P (i.j)) = {X ... ...K.,j [Vakk = -... ak,, =1}.
Definition 3 (Cluster indicator). The cluster indicator is defined to describe whether two graphs
belong to the same cluster. It is represented by the cluster indicator matrix C E {0. 17 NNN where Cjj 1 denotes the same class. The transitive relation GigCik S Cik serves the sufficient and necessary condition for C be a strict cluster division (see proof in the appendix). The number of clusters can be determined by the number of strongly connected components of C, namely SCC(C).
The MGMC problem can be formulated as a joint optimization problem, where matching results maximize pair similarity facilitate clustering, while the cluster indicator guides matching optimization in turn. Given the set of pairwise affinity and number of clusters No, the overall objective F(X, C) for joint matching and clustering can be written as follows:
Problem Formulation
Σns Cit vec(X.;) "K, vX)(X.))
max F(X, C) = maxx X
X,C
Enj Gig
8.1. 1,, S 11,,, m X!J1n, S Inys GKCky S C.y, Vi, k, SCC(C) No-
where X represents the pairwise matching matrices, and C denotes the cluster indicator matrix. The first part of constraints ensures that X.j E [0,1)axmn) is a (partial) permutation matrix, and the second part requires C E {0, NN to be strict cluster division with Ne clusters. The term En Gy acts as a normalization factor to mitigate the influence of cluster scale. The cycle consistency within each cluster is either enforced as constraint XRt S Xij, Ves = Ckj = Cij = 1, or softly encouraged by the algorithm.
4 A LEARNING-FREI APPROACH: M3C
In this section, we present our learning-fres algorithm, M3C. We start by converting the original problem into a nontrivial achievement not realized before (Sec. 4.1). Additionally, we propose a relaxed indicator that allows for more flexible exploration by relaxing the hard constraints from independent clusters to the global and local rank of affinities (Sec. 4.2). We finally present the full algorithm (Sec. 4.3).
(MM) framework (Hunter & Lange, 2004; Mairal, 2015), a
3

---

Published as a conference paper at ICLR 2024
car a dock
disstees
M33
Ferward Barkward
Traditional Feature Extractor
Twe-sruph Sahar
MM Framowork
Relaved indicator sugergraph
Hand AfllitA
Initial motching and affinity scrre
Obtain chuster result and output matzhing
Output: Chstered graphs with pairwise magping in each clustee!
laput Misture graphs
over images multiple
cleass with given key- points and structure.
A Affimity
Loss
Optimize via supergraph
Learned Alfinity
M MnneeioasMaiimmzaatttee Framooork
UM3C
Figure I: Pipeline of M3C and its unsupervised learning extension called UM3C. We use two clus- ters: ducks and cars as an illustration example. The node in the plot refers the graph sample for matching and different colors refer to different clusters. M3C a leaning free solver as shown in the dotted box in the top middle with minorize-maxinne maximization framework built a relaxed indicator (see Sec. 4). It extended to an unsupervised pipeline (see Sec. 5) by learning the edge-wic wise affinity matrix K and a pseudo label selection scheme.
4.1 CONVERTING THE PROBLEM SOLVING INTO A MINORIZE- MAXIIIE-MMIIIIZATIOO FRAMEWORK
Recall that DPMC (Wang al., 2020b) device alternative system for matching and clustering, suffers non-conver con-convergence. To utilize the mutual optimization nature and guarantee convergence, we introduce a Minorize-Maximizatin (MM) framework.
We start by presenting new objective with single variable X, denoted as f(X) (());
to incorporate the MM framework into our approach. Here, h(X) = arg max F(X, C). represents the optimal cluster division for X.
The MM framework works by finding surrogate function (X( F(X, h(x))). which mi-
norizes the original objective function fxX). By optimizing this surrogate function, we can itera- tively improve the objective maintain its value. The iterative steps are as follows:
Construct the surrogate function g (x = F(X, F=X,,(((()) h(x())) by inferring the best cluster based on the current matching results x())
Maximize g (() instead of f fXX), which can be solved using graph matching solvers.
The above iteration guarantees that f(X) is monotonic incremental:
((x(++1)) 2 (x(()) (x()) 2 9(x (xx)))))) = f(x()))
(3)
On the other hand, f(X) exhibits natural upper bound, i.e. f(X)= < Eis Eated Kyy b, c, d. According to the Monotone Convergence Theorem, monotone sequence of real numbers, such as f(X',, ), is bounded, then the sequence converges. Details of the proof can be found Sec. C.2.
4.2 RELAXATION ON CLUSTER INDICATOR
The proposed framework benefits from a convergence guarantee. However, subsequent theoretical analyses indicate that hard clustering tends to converge rapidly to a sub-optimal solution and lacks of the capability correct the clustering results. A similar challenge is also faced by GANN (Wang al., 2020a), which overlooks the intrinsic differences between matched pairs and assigns them clustering weights of either 1 or a constant 3. Owing to its inherent hard clustering characteristic, GANN's performance exhibits high sensitivity to both parameter fine-tuning and the presence of outliers. This underscores our motivation relax the hard constraints.
Proposition 4.1. If the size of each cluster is fixed, the hard cluster indicator converges to the local optimum in one step:
((t) = ((++1) (ff (f((
(2(1) } = (N((+)) (B+1)) gN.
(4)
9N.
4

---

Published as a conference paper at ICLR 2024
Please refer to Sec. C.3 for the detailed proof. Two key observations are: First, the cluster indicator attains local optimum for each cluster size group. Second, converges within one optimization step when the target cluster size is known. Such convergence fixes the optimization space for find- ing optimal matching compositions, constraining the exploration of both matching and clustering results. Experimental results confirming the quick convergence provided in Appendix. H.4.
To overcome the constrained exploration, we propose relaxing the hard constraints on the original cluster indicator. We present two relaxations on the number of graph pairs for the new indicator C:
Σ Byg =r.- N2 (global constraint);
Σ dig = r. N, Vi (local constraint)
(5)
Here, r E [O, 1] is a hyper-parameter that adjusts the ratio chosen pairs.
The global version limits the total number of selected graph pairs, while the local version re- stricts pair numbers for each graph. We re- fer to this new approach as the relaxed in- dicator, which provides three advantages: 1) The relaxed indicator assesses each graph pair individually. Considering the potential er- rors in clustering results, loosening cluster- ing constraints mnnstrints-ddisegarriin disregarding cluster numbers and transitive relations CaCAi I Cij csy-enables the incorporation of valuable information from other clusters. This, in turn, provides greater flexibility in the optimization space. 2) It en- hances pseudo label selection in unsupervised learning by selecting graph pairs with higher affinity scores, as discussed in Sec. 5. 3) Com- pared to GANN (Wang al.. 2020a), which also proposes relaxation for C. our approach maintains discrete constraints, resulting in bet- ter convergence than GA-MGMC.
CBE
DPMC
1 duck
Saperpshily
C clusters
Alternative Maciiiiaatoon
-hard
Initial matching and affiaity score from twn-graph sohvrr
Baurd Claskene
wilke Caske
Robeed seperpaph
Obtoin claster mealt and outgut matching
Figure 2: Three optimization structures. DPMC:
rigid tree structure, no convergence guarantec. M3C-Hard: constrained exploration. M3C: re- laxed indicator, better solutions with convergence.
4.3 THE CLUSTER INDICATOR RELAXED ALGORITHM: M3C
We introduce the M3C algorithm, which leverages the relaxed indicator C within the MM frame- work, consisting of three key parts: initialization, surrogate function construction, and maximization step. The details are outlined in Alg. 1 in the appendix.
Initialization We obtain the initial matching (0) using a two-graph solver, such as RRWM (Cho et al., 2010), which is both cost-effective and aligns with existing literature on multiple graph match- ing (Yan et al., 2015b; Jiang et al., 2021).
Surrogate Function Construction With the introduction of relaxed constraints in Sec. 4.2, we first present two methods for solving the optimal relaxed indicator Ć using the so-called global and local constraints, respectively.
Eij Gjj rN2
6,(0 = ((x((-11)= arg max
vee vec( (t-1) Ke, vec(x(())))
(6)
s.t. Σ Gjj 22 (global constraint) 6j
Σ Gij N,, Vi (local constraint).
In Eq. 6, given ((-1)) and r, the affinity scores and the normalization coefficients remain fixed. The objective is select graph pairs with higher affinity scores. For the global constraint, rank all graph pairs by affinity and set a threshold at the highest r22 values. For the local constraint, we rank the neighbors of each graph and select the top rN pairs in the context of k-nearest-neiihhorr These algorithms are denoted as global-rank and local-rank, respectively.
Building upon the local and global schemes, we propose a fused approach named fuse-rank. It combines both global and local constraints by introducing bi-level ranking. The local rank of pair of graphs (Gu,, Go) is determined as: P., + j. where Gú is the i-th nearest neighbor of G..
5

---

Published as a conference paper at ICLR 2024
and Go is the j-th nearest neighbor of Gu- Subsequently, we establish global threshold across all graph pairs based on { R. This approach allows the induced relaxed indicator C reflect both local and global affinity relationships among graphs. We will evaluate the performance of the above three strategies in our experiments.
Surrogate Function Maximization hard clustering, the maximization step optimizes within clusters, which is trivial to apply MGM algorithms. However, with the relaxed indicator, the op- timization structure changes and requires modification of the algorithm. We first present our approach, and then resonate why is a well-defined generalization address this issue.
With the supergraph mentioned in Def. 2 and the relaxed indicator, we can construct an incomplete supergraph with edges connecting graphs of the same class. The adjacency A of this supergraph corresponds numerically the relaxed indicator C, thus we simply set A Ć. Let P a denote all the paths (matching composition space) based on adjacency A, different from traditional MGM problem, the optimization step becomes:
(()
arg max
Σ vec(Xii) T (exvee(Xii))
(7)
X. (1.)
In 7 the optimization space P (A making it more likely to optimize graphs of the same class. This property mirrors that of the cluster indicator and renders the maximization objective equivalent to Eq. when given the relaxed indica- tor Ć. Furthermore, when the relaxed indicator degenerates hard cluster division, the supergraph reduces to several connected components, causing the optimization to focus solely on graphs within the same cluster. Hence, Eq.7 7 is a well-defined generalization of the maximization objective.
(i increases with the number of paths between Gj and 9j.
With the proposed algorithm, the relaxed indicator Ć is no longer fixed, expanding the optimization space of the maximization step. This enables the maximization step to enhance the quality of the relaxed cluster. Both steps work jointly, optimizing both clustering and matching results.
In summary, we have introduced a novel learning- free approach for joint matching and clustering with a convergence guarantee. In the following section, we aim to integrate deep neural networks into our framework to enable an unsupervised learning paradigm for graph matching and clustering.
UNSUPERVISED LEARNING MODEL: UM3C
We introduce UM3C, unsupervised extension to M3C, enabling joint matching and clustering within guaranteed convergence framework. Recent deep learning advancements in graph match- ing (Zanfir & Sminchisescu, 2018; Wang et al., 2019; Rolínek et al., 2020) highlight the value of learning node and edge features. However, M3C's discrete optimization hinders gradient computa- tion and machine learning integration. Previous attempts, like BBGM (Rolínek et al., 2020), strug- gled with gradient approximation and affinity generalization. GANN (Wang et al., 2021), although unsupervised. focused solely on Sropmans-Beckmann 's QAP, ignoring edge features and outlier handling. UM3C addresses these challenges with two techniques: 1) edge-wise affinity learning and affinity loss, guided by pseudo matching label from M3C solver; 2) Pseudo-label selection using the introduced relaxed indicator to improve pseudo label quality. We detail these techniques in the following subsections and present MBC's integration into the unsupervised learning pipeline.
5.1 EDGE-WISE AFFINITY LEARNING
Our solver M3C adopts Lawler's ' QAP (Loiola et al., 2007), which embraces second-order informa- tion for enhanced performance. This requires meticulous design of the affinity matrix K.
Recent research graph matching (Rolínek et al., 2020; Wang et al., 2021) adopts deep learning pipelines to compute node features F" and edge features Fú using VGG-16 (Simonyan & Zisser- man, 2014) and Spline CNN (Fey et al., 2018). A learned affinity Klearn can be constructed from these first and second-order features as: Klearn = (F")T T AF", Klearn = (F*) AF". Here, K,, and K, denote unary and quadratic affinities respectively, with A set to I for stable training.
Kg
Our goal is improve Klearn using ground truth x (or pseudo-label X Commonly, a dif- ferentiable pipeline calculates prediction matching X for applying the loss function. However, this approach conflates affinity construction and the solver, leading to customized affinities limited to the training solver and hampered generalization.

---

Published as a conference paper at ICLR 2024
We devise cross- loss to quantify the discrepancy between two input affinity matrices: L(Klcorn K
Σ
K pq
log(K (og(Ke (1 pg) log(1 pg
K)earn)
(8)
where K vee(X*t), ve Note that Kyy represents the element in the p-th row and q-th column of K between two graphs. This affinity loss decouples from solver effects, focusing solely on affinity quality, enhancing robustness and applicability to various solvers.
With its higher-order information, UM3C shows significantly greater robustness against noise, com- pared to GANN (Wang et al., 2020a), which centers only on node similarity and structural alignment.
5.2 UNSUPERVISED LEARNING USING PSEUDO LABELS
As previously mentioned, creating labels like X demands significant time and effort. Hence, we generate pseudo labels X using our learning-free solver M3C, aiming to replace X To enhance the quality of X we propose two techniques: affinity fusion and pseudo label selection.
The quality of X hinges on input affinity K. However, at the beginning of the training, the learned affinity Klearn random and unreliable. Conversely, the hand-crafted affinity Kraw cap- tures only geometric information of node pairs, i.e. distances and angles, limiting its expressiveness. Consequently, fuse both affinities, leveraging their strengths.
In particular, for its simplicity and experimental effectiiveness, we linearly merge learned and hand- crafted affinities, balanced by hyperparameter Krow adheres to standard procedure (Yan et al., 2015b; Jiang et al., 2021). Both affinities are normalized to the same scale. This design capitalizes on the reliability of hand-crafted affinity and the expressiveness of learned affinity. In initial epochs, Krow enhances the quality of pseudo matching X Later, learned affinity K Klearn surpasses Kraw, further refining the final result.
K Kiearn + alTaaw The hand-crafted
Furthermore, we optimize pseudo label pair selection for loss computation, guided by the relaxed indicator Ć. Unlike GANN, which accumulates losses for all pairs within inferred clusters, where a single incorrect assignment affects multiple pscudo label pairs differing categories. UM3C ad- heres to Ć and selects graph pairs with higher affinity rank as pseudo labels. This strategy, assuming higher affinity indicates greater accuracy, enhances pseudo affinity Kaad quality. The overall loss is:
Lall
2oj L(K KPddd.
This approach chooses more accurate matching pairs, bringing pseudo affinity closer to ground truth. Empirical validation of this approach can be found in Sec. 6.3.
6 EXPERIMENTS
6.1 PROTOCOLS
Experiments all learning-free free solvers were conducted on laptop with 2.30GHz 4-core CPU and 16GB RAM using Matlab R2020a. All learning- experiments were carried out on a Linux workstation with Xeon-3175X @ 1.GGHz CPU, one RX8000, and 128GB RAM.
Datasets We evaluate using two widely recognized datasets, Willow ObjectClass (Cho et al., 2013) and Pascal VOC (Everingham al., 2010). Detailed introduction and implementation of the datasets will be introduced in Sec. G.I. For convenience of notation, N₂ and N, (denoted as N, x N₂) represent the number of categories and graphs we selected and mixed for tests on MGMC.
Methods We present three method versions: M3C-hard, M3C, and UM3C. M3C-hard serves
baseline following the hard elustering MM framework (Sec. 4.1), employing Spectral Clustering and MGM-Floyd. M3C represents the relaxed algorithm from Sec. 4.3, and UM3C is the unsupervised learning model descrihed in Sec. 5, both using the fuse-rank scheme, if not otherwise specified. contexts. In learning- -ree ex-
We evaluate our methods in both learning- free and lcarning- periments, we mainly compare M3C with DPMC (Wang et al., 2020b) and MGM-Floyd (Jiang al., 2021), following protocols from Wang et al. (2020b;a). In learning-based experiments, compare UM3C with unsupervised method GANN (Wang et al., 2020a), and supervised learning method BBGM (Rolinck et al., 2020), NGMv2 ( (Wang et al., 2020), GCAN (Jiang et al., 2022b), and COMMON (Lin et al., 2023).
7

---

Published as a conference paper at ICLR 2024
Table 2: Evaluation of matching and clustering metric with inference time for the mixture graph matching and clustering on Willow Object Class. Following the previous work (Wang et al., 2020a), We select Car, Duck, and Motorbike as the cluster classes.
N,
3. N,
N:
3.
N. -8, 6. cutleess CP
N: =
3.
4 cutliers
Modal
Leaming
MA 1
CA1
CP1
RI T
i)
MA 1
CA
RIT
(imre(s)
MAT
CA
CP1
RI
time(s)
KRWad
Free
0,748
0,8115
0,879
12.771
0.4
0.595
[.54]
0.643
0.680
01.
0.572
0.547
0.661
0.685
0.6
Minchlal an
Frae
0.764
0.769
0.843
0.839
7.8
0.530
0.12
0.726
0.750
10.6
0.512
0.582
0.701
0.709
11.5
MrschAI.S
Frxe
0.535
0.571
0.589
0.702
1.3
0.245
0.39
0.487
0.576
2.5
0.137
0.383
0.480
0.571
2.6
CAD-C
Free
0.875
0.860
0.908
0:903
3.3
0.727
0.574
0.678
0.704
3.7
0.661
0.562
11674
0.695
4.9
MGM--Flyyd
free
0.879
0.931
0.958
0.952
0.716
0.364
0.667
0.696
0.651
0.580
0
0.706
2.9
DPMC
Free
0.872
0.890
0.931
0.923
0.672
0.17
0.724
0.733
0.630
0.500
0.707
0.722
VBC-haad
Froe
0.838
0.855
0.907
0.899
0.600
0.576
0.705
0.906
0.587
0.644
0.713
MBC (ours)
0.911
009338
0.657
0.653
0.758
0.635
0.646
0.748
0.753
NGMV2 BRCM
sup.
0,885
0.800
0.843
0.825
9.0
0.780
0.927
0,952
0.963
4.7
0.744
0.836
0,916
0.900
4.7
<0p
0.930
0.704
0.751
0.758
1.6
0.805
0.964
0.977
0.971
4.8
0.247
0.881
0.918
0.908
GANN
unsup.
0.896
0.963
03:770
0.899
0.933
0.461
00:47
30.2
UMBC (ours))
unsup.
0.983
0.988
0.984
0.986
0.981
0,987
0.986
Table 3: Evaluation of matching and clustering metric with inference time for the mixture graph matching and clustering on Pascal VOC. Mixture classes are randomly picked and average values of metrics are reported over all the combinations. "+UM3C(ours) means that UM3C apply the same feature extractor and two-graph solver with compared models. The pretrain weight of the feature extractor is loaded during the training to obtain a valid initial solution. Note that NGMv2 and BBGM are grouped together since their feature extractors are totally the same.
N.
N,
=8 8
N.
5.N,
10
Model
Learning
MA1
CA
CP1
RI
time(s)
MAT
CAT
CP1
RIf
time(s)
GANN UM3C
unsup.
0.2774
0.6949
0.7613
0.768
33,785
0,2372
0.5103
0.599
0.7816
64.015
unsup.
0,4979
0,7015
0.769
0.7756
5,2991
0.4817
0,5551
0.631
0.7921
24.661
NGMv2
sup.
0,8114
0.755
0,8083
0,8165
4.2586
0,821
0.6087
0.689
0.8167
18,8087
BBGM
sup.
0.7919
0.7973
0,8406
0.8371
2.2618
0.7926
0.7261
0.783
0.8656
8.5146
+UM3C(ours)
unsup
0.7928
0.8761
0,9065
0,9061
5.35
0.7862
0.7861
0,832
0.8989
24.8569
GCAN
sup. 0,8049
0,8089
0.8537
0.8438
4.6041
0.8041
0.672
0.7376
0.8459
23.8998
+UM3C(ours)
unsup. 0.75
0.824
0.8637
0.8565
7,5568
0.753
0.6846
0.7452
0.847
37,3579
COMMON sup.
0.8334
0.9318
0.9467
0.9458
0.9152
0.8334
0.8058
0.848
0,9122
2.9551
+UMBC(ours)
unsup
0,8435
0,9494
0.9629
0.9595
4.2193
0.8396
0.8129
0.8586
0.919
12:217
Evaluation Metries We employ matching accuracy (MA), clustering purity (CP), rand index (RI), clustering accuracy (CA), and time cost as evaluation metrics, following prior research (Wang et al., 2020b;a). MA assesses matching performance, while CP, RI, CA represent the quality of cluster division. Detailed mathematical definitions are provided in Sec. G.2. Mean results from 50 tests are reported unless specified otherwise.
6.2 PERFORMANCE ON MGMC
We conduct mixture graph matching and clustering experiments on Pascal VOC and Willow Object- Class, detailed in Table 2 and Table 3. For Pascal VOC, we explore two size settings: 3 clusters x images and 5 clusters x 10 images, where clusters and images are randomly chosen from the dataset. In the Willow ObjectClass dataset, we use the 3 clusters X 8 images setting while investi- gating the impact of outliers. This setting follows the previous work Wang et al. (2020a), selecting Car. Duck, and Motorbike as the cluster classes, with images randomly sampled for each class.
Table 2 presents the performance of our learning- free solver, M3C, demonstrating its competitive- ness compared to other learning-free algorithms. M3C achieves top matching accuracy (over 1% gain) in the settings without outliers. As the number of outliers increases, M3C's strength in cluster- ing metrics becomes apparent, with gains of 3% - 5% in clustering accuracy. M3C also sigmificantly outperforms M3C-hard, affirming the effectiveness of our designed relaxed indicator.
Our unsupervised model, UM3C, excels in both matching and clustering tasks. When compared to the peer method GANN, UM3C showcases superior performance on both Pascal VOC and Wil- low ObjectClass, achieving remarkable improvements of 5.9% 24.45% in matching accuracy and 0.66% 2% in clustering metries. This advantage becomes more pronounced in the presence of outliers, underscoring the robustness of our unsupervised approach. On the other hand, UM3C re- mains competitive even when compared to supervised models. On the Willow ObjectClass dataset, UM3C outperforms supervised models (BBGM and NGMv2) in both matching and clustering met- rics (1.6% 7.8% in MA and 1.2% 23% in CA, CP, RI). Concerning PoscalVOC, a more chal- lenging dataset, employing UM3C can further enhance the model's 's capabilities based on pretrained feature extractors, especially in clustering results.
8

---

Published as a conference paper at ICLR 2024
Stady
Towiiing
1.00
0.88
0.98
Midhial
0.86
0.50
GANN
Method
Methed
Spline
vorilla GANNN
0.52
varilla GMNN
Lobel so odtonn
MSC
0.00
M3C
0.50
Eigo- sff
Label Bie exton
Labett Salteciion
19
CA
CP
200
400
8:00
20
Mutric
Raraaion
Figure 3: Ablation study of M3C by adding components under 3 x Willow ObjectClass dataset without outliers. Left: Evaluation on matching and clustering performance. Right: Quality of pseudo labels during training and evaluation by iteration.
Furthermore, both M3C and UM3C stand out as time-efficient algorithms. demonstrated in Table 2. M3C consumes only 1.25 1.67x the time of the two-graph solver RRWM, while outpacing peer MGM methods by 2.3 11.5x in terms of speed. On the other hand. UM3C requires only 0.54 2x the time of the two-graph matching models NGMv2 and BBGM, delivering a speed advantage of 6.3x over the peer method GANN. Moreover, the "+UM3C" extension incurs a time cost of only 1.2 2.9s for the 3 x 8 setting and 6.0 14.5s for the 5 x 10 setting. significantly shorter than important to note that time-cost of UM3C Table exhibits
the time required by GANN. significant variability,, primarily due to different two-graph solvers and initialization methods.
6.3 ABLATION STUDY
We evaluate UM3C on Willow ObjectClass with 3 clusters images, excluding outliers, assess the effectiveness of different model components. We establish baseline by substituting M3C for the GA-GM solver in GANN. Given that GANN lacks Spline CNN for feature refinement, we also investigate the impact of introducing Spline CNN in the unsupervised method. The effectiveness of label selection and edge-wiss wise affinity learning validated by adding each component successively.
The pseudo label selection results, measured by the matching accuracy of pseudo labels during both shown the right side of Fig. 3. shows 5% improvement
training and evaluation, baseline M3C in the early training stage (first 100 iterations), affirming its ability to select pseudo labels closer to the ground truth.
Regarding edge-wise affinity learning, the left side of Fig. 3 illustrates its significant contribution to our model, highlighting the inadequacy of hand-crafted affinity and the necessity of learning edge-wise affinity. Spline CNN further enhances matching accuracy. Notably, our baseline method already outperforms GANN, attributed solver M3C.
6.4 ADDITIONAL EXPERIMENTS
We provide an index of additional experiments in the appendix for your reference. (H.1) Varying cluster number and cluster size: results on more diverse settings Willow ObjectClass. (H.2) Comparison of different ranking schemes. (H.3) Comparison of different clustering algorithms. (H.4) Convergence study M3C. (H.5) Hyperparameter study of M3C. (H.6) Generalization test of learned affinity Klearn (I) Visualization of matching results.
7 CONCLUSION AND OUTLOOK
We have presented principled approach for jointly solving graph matching and clustering in scenar- ios involving mixed modes. Our fearning-free solver, M3C, aligns with the minorrie-maxximiattin paradigm and introduces relaxed cluster indicator improve algorithm flexibility. Additionally, we integrate the M3C solver into an unsupervised learning pipeline, resulting in UM3C, with edge- wise affinity learning and pscudo label selection schemes. Remarkably, our methods outperform all state-of-the afrttherrt methods in the context of joint graph matching and clustering, which believe is a practical setting to advance the research of graph matching. For future work, we may apply our methods to other domains like protein docking (Wu et al., 2024) and combinatorial problem instance generation (Li et al., 2023; Chen al., 2024) whereby graph matching be building block.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
To foster reproducibility, we will make our code available at http://gihuu..oomhhnn... SITU/M3C. We give details of our models M3C and UM3C in 'Implementation Details' Ap- pendix. F, and our experimental protocol in 'Experiment Details' Appendix. G.
REFERENCES
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang- Simgnn: A neu- ral network approach fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 384-38433 392, 2019.
Alexander C Berg, Tamara L Berg, and Jitendra Malik. Shape matching and object recognition using low distortion correspondences. In 2005 IEEE computer society conference on computer vision and pattern recognition (CVPR'OS), (O5), volume pp. 26-33. IEEE, 2005.
Lubomir Bourdev and Jitendra Malik. Poselets: Body part detectors trained using 3d human pose annotations. 2009 IEEE 12th International Conference on Computer Vision, pp. 1365-1372, 2009.
Xinyan Chen, Yang Li, Runzhong Wang, and Junchi Yan. Mixsatgen: Learning graph mixing for sat instance generation. Int. Conf. Learn. Represent., 2024.
Yuxin Chen, Leonidas Guibas, and Qixing Huang. Near-optimal joint object matching via convex relaxation. In Eric P. Xing and Tony Jebara (eds.). Proceedings of the 31st International Con- ference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 100-108, Bejing, China, 22-24 Jun 2014. PMLR.
Minsu Cho, Jungmin Lee, and Kyoung Mu Lee. Reweighted random walks for graph matching. In European conference Computer vision, pp. 492-505. Springer, 2010.
Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs match. In ICCV, 2013.
W Fermandez De La Vega and Claire Kenyon. A randomized approximation scheme for metric max-cut. Journal of computer and system sciences, 63(4):531-541, 2001.
Boris Delaunay et al. Sur la sphere vide. Izv. Akad. Nauk SSSR, Ordelenie Matematicheski Extestvennyka Nauk, 17793-800)11-2, 1934.
M Fatih Demirei, Ali Shokoufandeh, Yakov Keselman, Lars Bretzner, and Sven Dickinson. Object recognition as many-to-many feature matching. International Journal of Computer Vision, 69(2): 203-222 2006.
Kun Duan, Devi Parikh, David Crandall, and Kristen Grauman. Discovering localized attributes for fine- fine-grained recognition. In 2012 IEEE Conference Computer Vision and Pattern Recognition, pp. 3474-3481. IEEE, 2012.
Amir Egozi, Yosi Keller, and Hugo Guterman. A probabilistic approach to spectral graph matching. IEEE transactions on pattern analysis and machine intelligence, 35(1):18-22) 27, 2012.
Mark Everingham, Lue Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes challenge 2007 (voc2007) results. 2007.
Mark Everingham, Luc Gool, Christopher K. Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. IJCV, 88(2):303-338, June 2010. ISSN 0920-5691.
Paola Festa, Panos M Pardalos, Mauricio GC Resende, and Celso C Ribeiro. Randomized heuristics for the max-cut problem. Optimization methods and software, 176) 2002.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splinecnn: Fast geomet- ric deep learning with continuous b-spline kernels. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 869-877, 2018.
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. arXiv preprint arXiv:2001.0066/ 2020.
10

---

Published as a conference paper at ICLR 2024
Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115-1145, 1995.
Michael Goesele, Noah Snavely, Brian Curless, Hugues Hoppe, and Steven M Seitz. Multi-view stereo for community photo collections. In 2007 IEEE 11th International Conference on Com- puter Vision, pp. 1-8. IEEE, 2007.
S. Gold and Anand Rangarajan. A graduated assignment algorithm for graph matching. IEEE Trans. Pattern Anal. Mach. Intell., 18:377-388, 1996.
Gregory Griffin, Alex Holub, and Pictro Perona, Caltech-256 object category dataset. Technical report, California Institute of Technology, 2007.
Juris Hartmanis. Computers and intractabilitty: guide to the theory of np-completeness (michael garey and david s. johnson). Siam Review, 24(1):90, 1982.
N. Hu, Q. Huang, B. Thibert, and L. Guibas, Distributable consistent multi-graph matching, CVPR, 2018.
Qi-Xing Huang and Leonidas Guibas. Consistent shape maps via semidefinite programming. In Computer Graphics Forum, volume 32, pp. 177-186. Wiley Online Library, 2013.
David R Hunter and Kenneth Lange. A tutorial on mm algorithms. The American Statistician, 58 (1):30-37, 2004.
Zetian Jiang, Tianzhe Wang, and Junchi Yan. Unifying offline and online multi-graph matching via finding shortest paths on supergraph. TPAMI, 43(10))3648-36 2021.
Zetian Jiang, Jiaxin Lu, Tianzhe Wang, and Junchi Yan. Learning universe model for partial match- ing networks over multiple graphs. ArXiv, 0bs/2210.103744 2022a.
Zheheng Jiang, Hossein Rahmani, Plamen Angelov, Sue Black, and Bryan M Williams. Graph- context attention networks for varied deep graph matching. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 2343-2352, 2022b.
Ellis Johnson, Anuj Mehrotra, and George L Nemhauser. Min-cut clustering. Mathematical programming, 62(1):133-15) 1993.
Jörg Hendrik Kappes, Paul Swoboda, Bogdan Savchynskyy, Tamir Hazan, and Christoph Schnörr Multicuts and perturb & map for probabilistic graph clustering. Journal of Mathematical Imaging and Vision, 56(2):221-2) 2272221-1372222 2016.
V. G. Kim, W. Li, N. J. Mitra, S. DiVerdi, and T. Funkhouser. Exploring collections of 3d models using fuzzy correspondences. In SIGGRAPH, 2012.
T. C. Koopmans and M. Beckmann. Assignment problems and the location of economic activities. Econometrica, pp. 53-76, 1957.
Maximilian Krahn, Florian Bernard, and Vladislav Golyanik. Convex joint graph matching and clustering via semidefinite relaxations. In 2021 International Conference on 3D Vision (3DV), pp. 1216-1226. IEEE, 2021.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Spyridon Leonardos, Xiaowei Zhou, and Kostas Daniilidis. Distributed consistent data associa- tion via permutation synchronization. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pp.
IEEE, 2017.
Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat for- mula generation and strong cructure-hardness-aae baseline. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2023.
11

---

Published as a conference paper at ICLR 2024
Yijie Lin, Mouxing Yang, Jun Yu, Peng Hu, Changqing Zhang, and Xi Peng. Graph matching with bi-level noisy correspondence. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 23362-23371, 2023.
Linfeng Liu, Michael Hughes, Soha Hassoun, and Liping Liu. Stochastic iterative graph matching. In International Conference on Machine Learning, pp. 6815-6825, PMLR, 2021.
Weijie Liu, Chao Zhang, Jiahao Xie, Zebang Shen, Hui Qian, and Nenggan Zheng. Partial gromov- wasserstein learning for partial graph matching. arXiv preprint arXiv:2012.01252, 2020.
Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, and
Tania Querido. A survey for the quadratic assignment problem. EJOR, pp. 657-90, 2007.
Julien Mairal. Incremental majorization pnporizatioo-mmiimiizaiioooo optimization with application to large-scale machine learning. SIAM Journal on Optimization, 25(2):829-88) 855, 2015.
Christopher D Manning, Hinrich Schütze, and Prabhakar Raghavan. Introduction to information retrieval, volume 39. Cambridge University Press, 2008.
Andrew Y Ng. Michael I Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances neural information processing systems, pp. 849-856, 2002.
Zhakshylyk Nurlanov, Frank R Schmidt, and Florian Bernard. Universe points representation learn- ing for partial multi-graph matching. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 37, pp. 1984-19999 1992, 2023.
Deepti Pachauri, Risi Kondor, and Vikas Singh. Solving the multi-way matching problem by per- mutation synchronization. In Advances in neural information processing systems, pp. 1660-1888. Citeseer, 2013.
James Petterson, Jin Yu, Julian J McAuley, and Tibério S Caetano. Exponential family graph match- ing and ranking. In Advances in Neural Information Processing Systems, pp. 1455-1463, 2009.
Svatopluk Poljak and Franz Rendl. Solving the max-cut problem using eigenvalues. Discrete Ap- plied Mathematics, 62(1-3):249 278, 1995.
William M Rand. Objective criteria for the evaluation of clustering methods. Journal of the Ameri- can Statistical association, 66(336):846 850, 1971.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vit Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In European Confer- ence on Computer Vision, pp. 407-424 Springer, 2020.
Dinggang Shen and Christos Davatzikos. Hammer: hierarchical attribute matching mechanism for
elastic registration. IEEE transactions on medical imaging, 21(11): 2002.
Ian Simon, Noah Snavely, and Steven M Seitz. Scene summarization for online image collections. In 2007 IEEE 1 11th International Conference on Computer Vision, pp. 1-8. IEEE, 2007.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2014.
Paul Swoboda and Bjoern Andres. A message passing algorithm for the minimum cost multicut problem. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 1617-1626, 2017.
Paul Swoboda. Carsten Rother, Hassan Abu Alhaija, Dagmar Kainmuller, and Bogdan Savchynskyy. A study of lagrangean decompositions and dual ascent solvers for graph matching. In Proceedings of the IEEE conference computer vision and pultern recognition, pp. 1607-1616, 2017.
Paul Swoboda, Ashkan Mokarian, Christian Theobalt, Florian Bernard, et al. A convex relaxation for multi-graph matching. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 11156-11165, 2019.
Yu Tian. Junchi Yan, Hequan Zhang, Ya Zhang, Xiaokang Yang, and Hongyuan Zha. On the conver- gence of graph matching: Graduated assignment revisited, In European conference on computer vision, pp. 821-835. Springer, 2012.
12

---

Published as a conference paper at ICLR 2024
Luca Trevisan. Max cut and the smallest eigenvalue. SIAM Journal Computing, 41(6):1769- 1786, 2012.
B.J. van Wyk and M.A. van Wyk. A pacs-based graph matching algorithm. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2004.
R. Wang. J. Yan, and X. Yang. Combinatorial learning of robust deep graph matching: an embedding based approach. IEFE TPAMI, 2020.
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, 2019.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Graduated assignment for joint multi-graph matching and clustering with application to unsupervised graph matching network learning. In NewrIPS, 2020a.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's S quadratic assignment problem with extension to hypergraph and multiple-grait -gapph match- ing. IEEE Trunsactions on Pattern Analysis and Machine Intelligence, 2021.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Unsupervised learning of graph matching with mixture of modes via discrepancy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1550010550010 2023. doi: 10.1109/PAMM.22233355777
Tianzhe Wang, Zetian Jiang, and Junchi Yan. Clustering-aware multiple graph matching via decayed pairwise matching composition. AAAI, 2020b.
Huaijin Wu, Wei Liu, Yatao Bian, Jiaxiang Wu, Nianzu Yang, and Junchi Yan. Ebmdock: Neural probabilistic protein-protein docking via a differentiable energy- model. In Int. Conf. Learn. Represent.. 2024.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov- wasserstein learning for graph matching and node embedding. In International conference on machine learning, pp. 6932-699 6941. PMLR, 2019.
Jason Xu and Kenneth Lange. Power k-means clustering. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6921-6931. PMLR, 09-15 Jun 2019.
Linli Xu, Wenye Li, and Dale Schuurmans. Fast normalized cut with linear constraints. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2866-2876 2873. IEEE, 2009.
J. Yan, J. Wang, H. Zha, X. Yang, and S. Chu. Consistency-driven alternating optimization for multigraph matching: A unified approach. TIP, 24(3):994-1099, 2015a.
Junchi Yan, Minsu Cho. Hongyuan Zha, Xiaokang Yang, and Stephen M Chu. Multi Multi-graph matching via affinity optimization with graduated consistency regularization. IEEE transuctions on pattern analysis and machine intelligence, 38(6): 1242, 2015b.
Junchi Yan, Xu-Cheng Yin, Weiyao Lin, Cheng Deng, Hongyuan Zha, and Xiaokang Yang. A short survey of recent advances in graph matching. In /CMR, 2016.
Junchi Yan, Shuang Yang, and Edwin Hancock. Learning graph matching and related combinatorial optimization problems. In IJCAI, 2020a.
Junchi Yan, Shuang Yang, and Edwin R Hancock. Learning for graph matching and related combi- natorial optimization problems. In International Joint Conference Artificial Intelligence, pp. 4988 4996, 2020b.
Tianshu Yu, Runzhong Wang. Junchi Yan, and Baoxin Li. Deep latent graph matching. Interna- tional Conference on Machine Learning, pp. 12187-12197. PMLR, 2021.
Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2684-2693, 2018.
13

---

Published as a conference paper at ICLR 2024
Zhen Zhang, Yijian Xiang, Lingfei Wu, Bing Xue, and Arye Nehorai. Kergm: Kerneiieed graph matching. Advances in Neural Information Processing Systems, 32, 2019.
Zhou and F. Torre Factorized graph matching. IEEE PAMI, 2016.
Xiaowei Zhou, Menglong Zhu, and Kostas Daniilidis. Multi-image matching via fast alternating minimization. In Proceedings of the IEEE International Conference on Computer Vision, pp- 0032-4040, 2015.
14

---

Published as a conference paper at ICLR 2024
APPENDIX
A NOTATION
We first present all notations used in this paper for a better understanding proposed algorithms and to facilitate the following discussion.
Table 4: Main notations and description used in this paper.
Notations
Descriptions
N
Number of input graphs.
is a set of graphs G = (91 ... 9x.).
g
Graph to be matched with vertex set Va and edge set Eg.
denotes all the possible pairwise matching results graph set G: X {Xighsss..
X, (X),,s,)
(y((X,,e)) (0, 1),,8>> denotes the pairwise matching results between and 9y. K, RP,",ymmy denotes the affinity matrix between 9i and gj. Its diagonal and off- diagonal elements store the node-to-node and edge-to-cdge affinities, respectively.
Kij
J.j
Jij vec(X:.) (ey.))(..;)) denotes the affinity score of graph pair (Gr, Gy).
Ce (0, 1J.NN is the cluster indicator of N graphs. Ci 1 if G, and Gj belongs to the same cluster, and cjj 0 otherwise.
C
number of nodes in graph and the number of its outliers
N₂ denotes the number of clusters. The size of cach cluster represented as (N .V N.........NN... When the size of clusters the same, we shorthand it as Ng.
No.
C
Ö (0. (0.1) 1)Nx is the relaxed cluster indicator by solving relaxed constraints.
A
A E {0, 1NNN denotes the adjacency matrix for supergraph (Def. 2).
vec(.)
Column--ectorrize operation given matrix.
sCC(-)
The number of strong connection components of the input cluster.
Hyperparameter for cluster relaxation. stands for the ratio graph pairs to choose.
Hyperparameter for affinity construction. a is the weight of the hand-craft affinity.
B COMPARISON WITH PREVIOUS WORKS
We underscore some key differences between proposed method and two previous works, DPMC (Wang al., 2020b) and GANN (Wang et al., 2020a; 2023), focusing on MGMC in Ta- ble 1. This comparison is to provide a comprehensive illustration of our novel contributions and substantial advancements in this field.
Some key points of differentiation are worth emphasizing:
Both approaches employed rigid optimization structures (a tree and fully connected graph), while M3C utilizes a discrete and partly connected supergraph, enhancing efficiency and flexibility in matching and clustering.
DPMC lacks convergence guarantee, and GANN requires hundreds of iterations for conver- gence, whereas M3C achieves convergence with fewer iterations.
While GANN claimed to jointly optimize matching and clustering, empirical results reveal its inability to adapt clustering once it incorporates clustering during matching, which becomes variant of hard clustering. In contrast, M3C demonstrates the crucial capability to jointly adjust its relaxed indicator alongside matching, defining feature of a true joint optimization framework.
GANN rooted in Koopmans-Beckee Beckmann'ss QAP (Koopmans considers structural similarity during matching. limiting its generalizability to edge feature learn- ing. In contrast, UM3C utilizes more generalized Lawler's 's QAP (Loiola et al., 2007) variation and introduces edge-wise affinity learning, making it more versatile.
Beckmann, 1957), which only
15

---

Published as a conference paper at ICLR 2024
C CONVERGENCE ANALYSIS OF M3C
C.1 CLUSTER DIVISION AND CLUSTER INDICATOR
In this section. we show the relationship between cluster division and cluster indication. We prove that the transitive relation CjjCkk I Cık: is the sufficient and necessary condition for C to be strict cluster division, which proposed in Def.
Sec. 3.
Proposition C.1. Transitive relation CijCk I Cik is the sufficient and necessary condition for C to be a strict cluster division, where C E {0, } xN and Ctj denotes whether Gú and 93 are belong to the same category.
Proof. Necessary condition: C is strict cluster division = c.jjkk S Cik-
When Cij = 1 and Cjk 1, Gj and G3 are of the same class, where 9j and G are of the same class, too. Therefore, 93 and Gr are of the same class, which means Gsk 1 and CijCik I Cik holds.
When one of Cij and 65 is equal to I and another equals O, we assume Gjj = and Cjk = without loss of generality. That is, Gj and Gj are of the same class while Gj and Ge are not. Therefore, 9j and 9g are not of the same class either, which means Cjk. 0 and Cjt 0 Cux also holds.
When Ctj and Cjt = 0, 9i and 9j are not of the same class, while 9j and 9s are neither of the same class. In that case, we cannot tell the relationship between Gj and Gk. so 0/1. It still holds that CryCAk Cik-
Sufficient condition:
CiyCsk I Csk =
a strict cluster division.
Gi and 9j. Gy and G3 are both of the same class, CijCkk = S Cik. which means Gsk = and 9; and Gn are of the same class.
If G; and Gj are of the same class, and 9j and Gū are of different classes, we have Gij Cji
and CуĄ: O. We find that c₁ = CfCCsk $ Cyk O, thus, C₁ and G, and Gy are not of the same class.
Above all, transitive relation GyCfk S Cik is the sufficient and necessary condition for C to be strict cluster division.
C.2 PROOF OF THE CONVERGENCE OF MINORIZE-MAXIMIZATION FRAMEWORK
In this section, we prove the convergence of the MM Framework.
The objective function F(X, C) is defined in Eq. 2 as:
Eij Gif (ec(X, TTTT K ve)(x))))))
max F(X, C) = max X.C
X,C
Enj Gij
(10)
s.t. X In, < 1n. X In, S 1ny
GACKS S cij. Vi,j,k SCC(C) = =Ner
X, E {0, 1m,.x,,,,s. ,cy E 10.
Let the C = hxX) solve the optimal cluster division for X, and f(X) F(X, hXX) be objective function with single variable X. Without loss of generality, we have
max x
(X)
max F(X,N(X)) max max F(X, C) max F(X, C)
(11)
x CIX
X,C
Therefore, f(X) is a variant of the objective function.
The MM algorithm works by finding surrogate function that minorizes the objective function (XX. Optimizing the surrogate function will either improve the value the objective function or leave unchanged. To optimize the surrogate function, two steps are conducted iteratively.
Construction. The surrogate function g( (1)) = F(X, h(x(1))) is constructed by inferring the
best cluster based on current matching results (1);
h (xx()) = arg max Σ Ciz vec(x 1/ K,,vee(X
(12)
s.t. CaaCaj I cig, Vi,jsh, SCC(C) = No.
16

---

Published as a conference paper at ICLR 2024
Maximization. Maximize 9(x[X(9) instead of f(X), which is solved by off-the-shelf graph matching solver.
x(+1) arg max (x arg max max f(x, ((x)))
x
x
arg max
vec(X:;) T (ec
(13)
s.t. X,,In, S 1m.. X,JIn In S Iny.
The Construction step ensures two properties that g (()) holds: 1) Since f(X) F(X, adopts the optimal cluster division, it holds for all X that
9 x F(,,,(XX h(x()) - ((X) = (X)
(14)
2) It also holds that
g 1 (1) = F(X
= -
(15)
With Eq. 14 and Eq. 15, for each iteration, the objective function will never decrease as shown in Eq. 3,
((x 2 ((x 2 g (0)) = f(x()))
(16)
Thus we finish the proof of the convergence of our proposed MM Framework.
C.3 QUICK CONVERGENCE OF HARD CLUSTERING
In this section, we show the proof of the proposition proposed in Sec. 4.2 that the hard clustering framework will converge quickly.
Proposition C.2 (Proposition 4.1). If the size of each cluster is fixed, the hard cluster indicator converges to the local optimum in one step:
c = if (N N 91 90
((t) 9N.
(N((++)) g1
N D2
(17)
9No.
Proof. According to the maximization step in the MM framework, the pairwise matching is updated individually, The improvement on Xi₃ does not influence the optimization of other pairs. Therefore, it holds that,
J((+1) 2 [((] ,
VC =1
(18)
VC = 0
where Jup = vec(X.;) Kejvec(X,j) denotes the pairwise affinity score.
We prove the proposition by contradiction. Assume that C(1) * c(++1, According to the optimiza- tion framework, we have that
[(x(+1) 2 (XX(+)1XX)) 2 x()
(19)
which means,
F(x((t), 2 F(x(+1), c( 2 f(x(0) (
(20)
Therefore,
F(x(++1) (((+1)) F(x(1+1) c(
((+1) ((+1)
Σ
J (t+1)
(t+1) Σ
%zj ij
ij
Σ
(21)
ij
20.
Since
(N()), NO0
N(0) = (N((t-1) (,((-1),((++111) 1(++1)
1(++1))
(22)
9N }
holds that,
Σ
(+1))
Σ
c
(1)
(23)
17

---

Published as a conference paper at ICLR 2024
Algorithm 1: Learning-free free solver M3C
Iterations number T. Cluster number No. Graph set (91.... GN Construct affinity matrix K from node coordinates of graph set (G1, GN through standard process (Yan al., 2015b; Jiang et al., 2021).
Input:
Obtain initialization matching x via two-graph solver e.g. RRWM (Cho et al., 2010);
for : do
/x Const ruuciinn-nttte Stn- x/
Construct the surrogate function g (x] via solving É = -(x((=1)) in Eq. 6 with three strategy candidates: global-rank, local-rank, or fuse-rank;
/+ Maximizat// Seeaatiin-Sttee +/
Set (+) as relaxed indicator C(t), maximizing (xx(x((-1) via Eq. 7 to find optimal
matching composition X on A (0;
end
Obtain the affinity score for each graph pair: Jig = vec [K "r,jXX))",,vee((x,,,, vec()())
Sparsification on the affinity score: { = (
Apply clustering algorithm, e.g. Spectral Clustering (Ng et al., 2002), Multi-Cut (Swoboda Andres, 2017), on {J } to get C.
Output: Matching x cluster C.
According to Eq. 18, we can further have
F(x(++1) c(++1) F(x((+11) c(O))
Σ (1+1) ]((+2)
Σ
((+1))
Σ
0
ij
ij
11
Σ
(++1)
Σ
(24)
Σ 4
(
(1D
AL 1) 00
10 -1
Σ
10
Σ
((+11
Σ
C
(0)
R11)) 111
( 0
(0D) 00 10 m1
8j
20.
Moreover, according
J
(++1)
(1)
Vel
have
Σ
Σ
Σ
Σ
((+1)
(25)
(0+1) -0.0 00-1
00
9 -1
which means
(t+1)
20.
(26)
Σ 5j
(1+1)
if
Σ
ij
That is to say
F(X()) c(++1)) > F(x() C(1),
(27)
which means (1)) is not the optimal cluster division for (t), Contradiction. Therefore, have (+)) C(++1)
D DETAILED ALGORITHM OF M3C
Please refer to Algorithm/ I and Algorithm 2 for a detailed presentation of our proposed learning- free solver M3C and unsupervised learning method UM3C.
18

---

Published as a conference paper at ICLR 2024
Algorithm 2: Unsupervised learning UM3C
Input: Images
IN} ), node coordinates (V..... ... Vx
Obtain node and edge features F" F via VGG16 and SplineCNN:
Construct Klearn from F", Fe by K (F") AF", Klarn (F=) AF";
Obtain hand-crafted Kraw following Zhou & Torre (2016); Yan et al. (2015b); Jiang et al.
(2021); Wang et al. (2020b);
K = =Keeern + a.Kraw;
ttraining then Xesd C M3C(K);
Knsd (X)d vec(XPed);
Lall = Eis City L(K K K
else
10
C.C M3C(K);
11 end
Output: Matching X, cluster C.
Table 5: Time complexity comparison of peer methods, where N and is the total number of graphs and number of nodes for each graph (we assume equal size here for notation simplicity), T; denotes the iterations needed for the algorithm to converge, and Tpair denotes the time cost of calling a two- graph matching solver.
method
time complexity for MGMC
MGM-Floyd (Jiang et al., 2021)
O(N + N + N Aparr + (NN.d
CAO-C (Yan et al., 2015b)
O(N*n + N N2 + EN N.d)
DPMC (Wang et al., 2020b)
O (N2n² + -N2 N + (NN.d) + 22TTpair)
GA-MGMC (Wang ct al., 2020a)
O (T'N2 N.d))
M3C (ours)
O (N + N2 log N (NNod) + N2
E
TIME COMPLEXITY ANALYSIS BETWEEN LEARNING-FREE SOLVERS
We analyze the time complexity of our method M3C and compare with other learning-free solvers in Table 5. Notably, our algorithm outperforms vanilla MGM-Floyd (Jiang et al., 2021) in terms of speedup due lower time complexity bound. Additionally, our approach benefits from significantly reduced constant factor.
Let N and denote the number of graphs and nodes in one graph (ignoring the different graph sizes for the brevity of notation), respectively, and Tpair denote the time cost of two-graph matching solver, such as RRWM (Cho et al., 2010). It costs O(N"Tpair) to calculate the score matrix and
O log N2) to construct the supergraph. In the worst case, we would add N(N-1) edges to the supergraph, resulting in )()3n3) time cost for performing MGM-Floyd. Additionally, spectral clustering is applied, with time cost of O(L Nod). where is the k-means iteration, and d is the dimension for embedded features. T denotes the number of iterations that M3C takes to converge. Therefore, the total time complexity given by O(T (N3 3 + N log N N.d) + N2 Tpaúr).
It's important to note that M3C runs faster than peer methods in Table 2. This is primarily due to two reasons. Firstly, M3C exhibits significantly lower constant factor in the maximization step, and the expected number of edges added is much smaller than in the worst case scenario. In practice, the actual run time of the maximization step can be approximated as 3 where 0 < I. Empirical studies show that 0 0.16 for N. larger No and Ng- Secondly, owing to the relaxed cluster indicator, MBC converges much faster than
and N₂ = 20, and this value may further decrease with
resulting in significantly reduced number of iterations: T3 & Tz. As result, the actual running time of M3C is significantly less than that of DPMC and GA-MGMC.
19

---

Published as a conference paper at ICLR 2024
F IMPLEMENTATION DETAILS
In this section, we introduce more implementation details of M3C and UM3C, including the detailed structure of the neural network we applied, the construction of affinity matrix K, and some hyper- parameters setting.
F.1 NETWORK STRUCTURE FOR FEATURE EXTRACTION
We utilize the feature extractor described in Rolínek et al. (2020) with few modifications. The process is outlined below:
Compute the outputs of relu4.2, relu5_1 of the VGG16 (Simonyan & Zisserman, 2014) net- work pre-trained on ImageNet (Krizhevsky et al., 2012), to obtain feature F1 and F2, respectively. These features then concatenated create the final CNN feature F:
F CONCAT F2)
(28)
The detailed network structure and parameters are shown in Table. 6.
Feed the obtained feature F and the graph adjacency A into the geometric feature refinement component. The graph adjacency AA is generated using Delaunay triangulation (Delaunay al., 1934) based on keypoint locations. We apply SplineConv (Fey et al., 2018) encode higher-order information and the geometric structure of the entire graph into node-wise features F":
SplineConv( (F.AA)
(29)
The Spline Conv operation is calculated as follows:
F
1
Σ Fj (E,))
(30)
WOI
JEN())
where F represents the node feature of Us. (i) denotes the neighborhood of uj. E.j F F stands for the edge feature of the edge between and uj. and he denotes kernel function defined over the weighted B-Spline tensor product basis.
F.2 CONSTRUCTION OF AFFINITY MATRIX K
In our paper, we discuss two types of affinities: the traditional Krew and the learned Klearn, The former is employed all learning free experiments, while both are utilized in the UM3C process.
Table 6: Network structure of "gg16 bn applied in UM3C. The pre-trained weight is downloaded by PyTorch. The bold line denotes the relu4_2, relu5_1, and final layers whose outputs applied as node features, edge features, and global features.
Layer
Channels
Kernel
Laver
Channels
Kernel
Conv2d
(3, 64)
(3,3)
ReL.U
(256, 256)
BatchNorm2d
(64, 64)
MaxPool2d
ReLU
(64, 64)
Conv2d
(256, 512)
(3.
Conv2d
(64, 64)
(3, 3)
BatchNorm2d
(512, 512)
BatchNorm2d
(64, 64)
ReL.U
(512, 512)
Rel.U
(64, 64)
Conv2d
5122,512)
(3,3)
MaxPool2d
BatchNorm2d
(512
Conv2d
(64, 128)
(3, 3)
ReLU
(12)
BatchNorm2d
(128, 128)
Conv2d
(112,
(3.
ReLU
(128, 128)
BatchNorm2d
(512, 512)
2
Conv2d
(128, 128)
(3,
ReLU
(512,512)
BatchNorm2d
(128, 128)
MaxPool2d
ReLU
(128, 128)
ConvZd
(112,
(3.3)
MaxPool2d
BatchNorm2d
(512, 512)
Conv2d
(128, 256)
(3,3)
ReLU
(512,512)
BatchNorm2d
(256, 256)
Conv2d
(512,512)
(3,3)
ReLU
(256. 256)
BatchNorm2d
(512.
Conv2d
(256, 256)
(3.3)
ReLU
(512, 512)
3
BatchNorm2d
(256, 256)
Conv2d
(112,
(3.3)
ReI.U.
(256, 256)
BatchNorm2d
(512, 512)
Couv2d
(256, 256)
(3.
ReLU
(512,512)
BatchNorm2d
(256, 256)
MaxPool2d
20

---

Published as a conference paper at ICLR 2024
Table 7: Parameters of UM3C.
WillowObject
PascalVOC
param
3 x 8
5 x 10
3 x
5 x 10
description
10-3
10 3 (100, 500)
10 10-3 3 10-5
10 3/ 10-5
learning rate
Ir-steps
(100, 500)
{100, 500}
{100, 500}
1v/=10 at these number of iterations
train:
train:
train: 0.5
train: 0.5
a
test:
test:
test: 0.5
test: 0.5
weight K
0.9
0.9
0.9
0.9
weight parameter in Kraw
a²
0.03
0.03
0.03
0.03
scaling factor Kraw max iterations of M3C
The construction of Kraw adheres to the standard protocol used in previous works (Zhou & Torre, 2016; Yan et al., 2015a;b; Jiang et al., 2021; Wang et al., 2020b). Kraw has no node affinity and relies on edge affinity, which is computed based on two factors: length similarity and angle similarity. For each edge
v1), (I2,, y2)), its length feature de is calculated as d, = (zz x2)² + (y) - 32)² and its angle feature 0, is computed 0. tan The edge affinity is determined using the following formula:
graw e1, e2 = exp (- (3 (3)de: dez + -1-17 (1-13) (0) -0azl)
(31)
The learned affinity Klearn is extracted using deep learning model, following the standard pipeline
(Rolínek et al., 2020; Wang et al., 2020a). Node features F, are obtained through VGG16 and SplineCony, while edge features are constructed as:
F = F² F
(32)
The learned affinity matrix K computed as:
K, = (F") AF",
K, (F) TF
(33)
Here, K,, represents unary affinity, K, denotes quadratic affinity, and A is set to for stable training.
UM3C constructs the affinity matrix through combination:
K K a.Ko
(34)
where is used to adjust the weight of Kraw, Further parameter details are provided in Sec. F.3.
F.3 PARAMETER SETTINGS
The detailed configuration of our model parameters is listed in Table 7, which are tuned based on their performance on the training data. The parameter 3 and a for Krow follows the parameter used for traditional solvers. The and time cost of M3C. For we found that as Klearn gets better when the training proceeds, less desirable Kraw would harm the performance of the solver under the simpler setting where N. = 3, Ng = 8, but is still instructive under more complex setting where N. = 5, Ng = 10. This also means that given more training categories, there is still room for improvement in unsupervised learning methods.
iteration T is chosen based the performance, convergence,
G EXPERIMENT DETAILS
G.1 DATASETS
We conducted experiments on two datasets: Willow Object Class (Cho et al., 2013) and Pascal VOC Keypoint (Everingham et al., 2010).
The Willow Object Class dataset comprises 304 images gathered from Caltech-256 (Griffin al., 2007) and Pascal VOC 2007 (Everingham et al., 2007). These images span categories: 208 faces, 50 ducks, 66 wine bottles. 40 cars, and 40 motorbikes. Each image is annotated with 10 keypoints, and we introduced random outliers for robustness tests.
21

---

Published as a conference paper at ICLR 2024
The Pascal VOC Keypoint dataset features natural images from 20 classes in VOC 2011 (Evering- ham et al., 2010), with additional keypoint labels provided by Bourdev Malik (2009). To tailor the dataset to the graph matching and clustering problem, we selected 10 classes: aeroplane, bicy- cle, bird, cat, chair, cow, dog, horse, motorbike, and sheep. We filtered out images with incomplete keypoint counts, ensuring that all remaining images had 9-10 common keypoints for each class. We also added random outliers to ensure that all images consistently contained exactly 10 keypoints. This resulted in training set of 944 images and evaluation set of 220 images.
In both datasets, we constructed graphs using Delaunay triangulation. For learning- baann models, images were cropped to object bounding boxes and resized to 256 x 256 pixels.
G.2 EVALUATION METRIC
Denote cluster with set of graphs {91 ... 9. The ground truth cluster division is denoted as Cst, and the predicted cluster denoted as Moreover, let (off denotes the ground truth cluster indicator and C(cs,) denotes the predict cluster indicator. Performance metrics include both matching accuracy and clustering quality:
Matching Accuracy (MA) We only consider the intra-cluster matching accuracy and thus by adapting the accuracy for single cluster, we have
MA
1
Σ 5J
(X.().
(35)
Σ
where AXc(X.;) denotes accuracy for matching Xij. Here C refers to an indicator for strict cluster division.
Clustering Purity (CP) (Manning et al., 2008): is given by
CP
max Je(.....N.))
(36)
where C₁ is the predicted cluster and Cj is the ground truth cluster j. and is the total number of graphs.
Rand Index (RI) (Rand, 1971): RI calculates the correct graph pairs overall.
Σ
Σ
(37)
N2
cy= =1
Cly=0,c
where Ens= 1.ff represents the number graphs predicted the same cluster with same label, 0, the number pairs that are in different clusters with different labels, and is normalized by the total number of graph pairs N2.
Clustering Accuracy (CA)
(Wang et al., 2020b), it is defined by:
C. nc, IC
nc, C. nCal Ca (c/
CA =
Σ
Σ
ΣΣ
(38)
N.
Cal
C.
C'
C.FCs
where Ca. C. are the ground truth clusters and C₁2, Cj denotes prediction.
G.3 APPLY 2GM AND MGM ON MGMC
To apply 2GM and MGM solvers MGMC, need first get the pairwise matching results from these solvers. Then we will generate respective clustering results based on resulting matching X and given affinity matrix [Ky). The details of the clustering algorithm are introduced in Sec. G.4. Both X and C are used for the evaluation of these solvers.
22

---

Published as a conference paper at ICLR 2024
Algorithm 3: Clustering algorithm.
Input: Matching results X, affinity matrix {K
Obtain the affinity score for each graph pair: Jij = vec(Xx,) " Kiy (ec(;));
Sparsification on the affinity score: { = ( kk);
Apply clustering algorithm, c.g. Spectral Clustering (Ng et al., 2002), Multi-Cut (Swoboda & Andres, 2017), on {J } to get C. Output: Cluster C.
G.4 DETAILS FOR CLUSTERING ALGORITHM.
For all solvers (2GM, MGM, and MGMC), we adhere to the same clustering procedure outlined in Alg. 3. The first step involves computing the affinity score Jig each pair of graphs. To enhance the effectiveness of clustering. we employ a sparsification technique, consistent with the pre-processing approach in Wang et al. (2020b), aimed at obtaining a more efficient input matrix. Specifically, when dealing with a pair of two graphs, if one graph is not among the k-nearest neighbors of the other, set their corresponding scores Jiy (and Jji) to zero. The parameter l is consistently set 10 for all tests. The resulting sparsified affinity score is denoted as J.j--
H ADDITIONAL EXPERIMENTS
H.1 1 VARYING CLUSTER NUMBER AND CLUSTER SIZE
We assess the model's generalization ability concerning the number of graphs and clusters. For
Na= = 3, the categories consist of car, motorbike, and wine bottle. For N₂ = 4, additional categories include face. We also investigate unbalanced cluster sizes for N₂ = 3, comprising 20 cars, 10 motorbikes, and 5 wine bottles. Both GANN and UM3C are trained with No = 5 and N, = 10, excluding outliers. During testing, two outliers randomly added to the graph in all settings.
Table demonstrates the robustness of our methods with varying cluster and graph numbers. Our learning-free free solver, M3C, exhibits competitive performance compared to DPMC, with a matching accuracy ranging from 1% loss to 2% gain, and clustering accuracy improvement ranging from 2% to 9%. These achievements further reflect the superiority of our proposed ranking scheme.
Notably, our UM3C outperforms in all performance metrics. It consistently achieves a cluster accu- racy above 0.97 and a matching accuracy exceeding 0.87 across all settings, representing 1 ~ 7% improvement matching accuracy and 2 ~ 18% enhancement in clustering accuracy. The fact that UM3C's s training setting differs from testing settings validates the strong generalization ability of our method acToss varying numbers of graphs, clusters, and the presence of outliers. Furthermore, our method, although trained under simpler conditions, can be effectively deployed in more complex scenarios, yielding satisfactory performance.
H.2 COMPARISON OF DIFFERENT RANKING SCHEMES
We compare three proposed ranking schemess across various test settings. M3C-Global, M3C-Local, and M3C-Fuse refer to global-rank, local-rank, and fuse-rank, respectively. We vary the number of graphs N₂ within each cluster while keeping the cluster number fixed at N. = 5, and we also vary the number of outliers in each graph while maintaining N. = and N₂ = 20.
Table 8: Evaluation of matching and clustering accuracy by varying the number of clusters, and number of graphs in each cluster on WillowObj. MA and CA are used for matching accuracy and clustering accuracy, respectively.
N₂ Metrics
20,
5 outlers
ouilies
(20,, 10,5, coutlirs
Learning
MA1
CA.1
1
MA
CA
MA
CA
MA 1
CA
MA.1
CAO-C
08849
0.946
0.501
0.708
0.844
0.679
MGM-Fleyd
free
0.815
0.915
0.812
0.578
0.819
0.807
0.798
0.727
0.799
0.707
0.778
0.755
DPMC
froe
0,867
0.912
0.827
0.594
0.775
0.772
0.739
0.713
0.756
0.744
0.795
0.823
M3C-hard
free
0.758
0.966
0.782
0.508
0.726
0.824
0,710
0.753
0.722
0.719
0.727
0.744
MBC comms)
free
03857
0.961
0.851
0.933
0.835
0.900
0,812
018005
(L809
0.780
0.792
01881
GANN
0.532
0.834
0.589
0.301
0.528
0.784
0.551
0.802
0.552
0.827
0.475
0.802
UM3C (ours)
0.874
0.992
0.897
0.951
0.879
0,972
0.576
0.975
0.878
0.975
0.872
0.964
23

---

Published as a conference paper at ICLR 2024
0.84
0.7
0.82
0.6
0.50
MSC-Gibbel
MSC-Lacal
MSC-Fuse
Mg
Ng
oudler
outlee
Figure 4: Comparison by four metrics of the three proposed ranking schemes (local, global, and fuse in Section 4.3) on the Willow ObjectClass dataset, by varying the cluster size Ng and number of outliers.
Table Comparison Spectral Clustering and Multi-Cut on learning-free solvers under the setting of No = 3, Ng 8, and n, = 2 outliers. Algorithms with '-MC' use multicut in clustering.
Method
MA
CA 1
CP f
RI f
MGGM-Floyd
0.709
0.567
0.673
0.699
With Spectral Clustering
M3C
0.687
0.653
0.750
0.758
MGM-Floyd-ME
0.709
0.603
0.716
0.724
With Multi-Cut
M3C-MC
0.687
0.634
0.734
0.745
Our findings from Fig. 4 indicate that M3C-Fuse outperforms all other methods, leading us to select M3C-Fuse the solver for unsupervised model, UM3C. These results also confirm that both global and local ranking schemes serve as effective approximations. Furthermore, this demonstrates the robustness and generalization ability of our ranking methods. Even in the presence of 10 outliers, method achieves matching accuracy exceeding 0.5 and clustering accuracy surpassing 0.65. Additionally, the performance of our methods improves both matching and clustering accuracy as the number of graphs increases. This observation also explains why M3C does not outperform other learning- frren solvers in Table 2 (in simpler settings) but demonstrates significant superiority Table (in more complex settings).
H.3 COMPARISON OF DIFFERENT CLUSTERING ALGORITIMMS
In previous experiments, for all solvers (under the settings of 2GM, MGM. and MGMC), adopt the same procedure for clustering. The first step involves computing the affinity score Ji, for each pair of graphs. To sparsify the affinity scores, we select only the 10 nearest neighbors for each graph and mask other pairwise affinities, following the approach in Wang et al. (2020b) to obtain a more effective input matrix. Subsequently, we employ a clustering algorithm on the sparse affinity { }-
We now conduct comparison between the clustering algorithms Spectral Clustering (Ng et al., 2002) and Multi-Cut (Swoboda & Andres, 2017) applied to two well-established traditional algo- rithms: MGM-Floyd and M3C-Fuse. We hope this comparison justifies our choice of clustering algorithm.
Table 9 presents the performance of all four combinations, As result, there is no substantial alternation in clustering performance. As both (Wang et al., 2020b;a) utilized spectral clustering, to ensure fair comparison, we adhere to their protocol and employ spectral clustering in our primary experiments.
Furthermore, posit that the key achieving effective clustering lies in obtaining high-quality matching and forming reliable affinity scores for clustering. Multi-Cut, as well Spectral Clus- tering, represents just one approach to produce robust clustering. The clustering visualization of different methods is shown in Fig. 5.
H.4 CONVERGENCE STUDY OF M3C
We experiment to show the changes in the supergraph structure of M3C-hard, M3C, and DPMC per iteration in Table 10. In the case of the two M3C variants, the structure refers to the cluster indicator (also the corresponding supergraph), whereas for DPMC, it pertains to the designed tree structure.
24

---

Published as a conference paper at ICLR 2024
Car
Face
Duck
Motorbike
Winebottle
Figure 5: Cluster visualization by projecting into 2-D space. We show the spectral embedding of different methods: DPMC, MBC, and UM3C under x 20, 2 outliers setting. The embedding is obtained based on pairwise affinity score and the dimension of the embedding space is 16. We apply I-SNE reduce the dimension to 2 to draw the visualization figures.
Table 10: Changes in supergraph structure (measured by the number of changed edges per itera- tion Σ ((+11) AA) over iterations under the setting of Ne = 3. Ng with 2 outliers as disturbance. For M3C, the structure is the cluster indicator C, and for DPMC, the structure is the maximum spanning tree.
Iteration #
2
3
5
7
9
10
M3C-hard
10.48
0.56
0
0
0
0
M3C
20.44
2.04
1.56
0.24
0.04
0.08
0
DPMC
10.16
6.16
3.28
1.20
0,48
0.32
0.24
0.24
0.24
The number is the edges changed per iteration, which is calculated by EIA (A(1)) - A (1) where A is the adjacency matrix the respective supergraph. convergence, while M3C-hard converges rapidly to a local optimum, confirming the fact that the cluster size in M3C-hard remains unchanged in most cases in the experiments and our proposed Proposition. 4.1 holds. M3C exhibits more balanced convergence rate, leading its well-balanced performance.
evident that DPMC oscillates without
Additionally, we validate the convergence of the three M3C variants using different ranking schemes: M3C-Global, M3C-Local, and M3C-Fuse. The ex- periment is conducted on the Willow ObjectClass dataset, with the settings of No and the presence algorithm for 6 cycles and report the mean and standard deviation of the curves based on 50 rep- etitions. The hyperparameters r for M3C-Global, M3C-Local, and M3C- are set to 0.05, 0.04, and 0.06, respectively. The results are depicted in Fig. They validate that our algorithm achieves rapid con- vergence within few iterations. In the case of each algorithm, it attains near-optimal target score by the second iteration. This supports the earlier assess- ment of supergraph structure convergence: the sec- ond iteration witnesses significant number edge changes, which diminishes the third iteration but still allows room for further enhancement. It is im-
MSC-Glbbll
N₁, 20, two outliers. We iterate each
uSCA
260
145
148
BecaSon
Convergence curve M3C. The rates are shown under three different schemes of ranking: M3C-Global, M3C- Local, and M3C-Fuse.
Figure
portant to note that variations target scores are consequence of selecting different values for each algorithm.
H.5 HYPERPARAMETER STUDY OF M3C
The major hyperparameter for M3C is r, which controls the number of graph pairs considered as belonging the same cluster and determines the number of edges in the supergraph. In this section,
25

---

Published as a conference paper at ICLR 2024
0.00
0.15
0.76
0.70
MAIK,
200
0.65
0.02
0.04
0.05
0.08
0.50
0.02
0.04
0.08
0.08
0.10 0.00
0.04
0.08
0.08
0.10
Figure 7: Sensitivity study of the hyperparameter r for the devised three ranking schemes. Experi- ments are conducted under the setting N₂ 5, Nº 20 and N, 5, Na 10, both with 2 outliers, on Willow ObjectClass. The marker denotes the performance of our chosen r, which add edges until the supergraph is connected.
MA LPMP
CA LPMP
RRWM
M3C
RRWM
M3C
UM3C NGMv2 BBGM
NGM2 BBGM
0,700
0.806
0.796
0.933
0.964
0.937
0.98
0.80
0.806
0.849
0.854
0.907
0.908
0.964
0.94
0.75
UM3C
0.837
0.850
0.863
0.982
0.957
0.990
0.92
0.70
Figure 8: Generalization test of learned affinity under N₂ 3 N₂ 8, no outliers on Wil- lowObject. The x-axis is the solver used, and the y-axis is the learning model of the learned affinity. All models are learned under the same setting the tests.
we first investigate the sensitivity of the hyperparameter for M3C-Global, M3C-Local, and M3C- Fuse, and subsequently, we present our tuning algorithm.
Figure illustrates the matching and clustering performance varying the hyperparameter v, consid-
ering two settings: N₂ = 5, N₁ 20, and N. = 5, N₁ = 10, each with n, = outliers. It is evident that the matching performance of M3C-Global remains stable when 0.04 for N. 5, N,, 20, and r 0.06 for N₂ 5, N₂ = 10. However, its clustering performance deteriorates when r 2 0.6 in both settings. This observation implies that the threshold should be within a reasonable range, as merely adding more edges does not necessarily improve performance. Conversely, having too few edges restricts the algorithm's 's optimization space. The findings from M3C-Local and M3C-Fuse further support this observation. As depicted in Fig. 7, they achieve optimal results at r = 0.15 and 0.03 for the 5 20 setting, and r 0.3 and 0.045 for the 10 setting.
worth noting that the optimal r varies for different inputs and settings, and de- termining the best r for each input can be a time-consuming process. Consequently, we employ an alternative approach to address this challenge. Rather than fixing specific value for r, we dy- namically add edges based on their rank until the supergraph becomes connected. The symbols 'x' and "+' in Fig. 7 represent the mean value of r and the corresponding mean performance achieved by this scheme in two settings, respectively. These empirical results demonstrate that this approach provides reliable approximation of the optimal r, enabling the algorithm to attain near-optimal performance without extensive computation. This is the method employed in both our conventional solver, M3C, and the unsupervised learning method, UM3C.
Additionally,
H.6 GENERALIZATION TEST OF LEARNED AFFINITY K Iearn
We conducted experiments evaluate the generalization capability of our learned affinity, demon- strating how our edge-wise affinity loss enhances the robustness of affinity across different solvers. The experiments were conducted on Willow ObjectClass under a 3 x 8 setting with outliers, em- ploying the solvers RRWM (Cho et al., 2010) (used in M3C), LPMP (Swoboda et al., 2017) (utilized BBGM), and M3C, as well as affinities learned by BBGM, NGMv2, and UM3C. In the case of UM3C, only klearn utilized for testing.
26

---

Published as a conference paper at ICLR 2024
As illustrated in Fig. UM3C exhibited superior generalization capabilities in terms of both match- ing and clustering accuracy. BBGM's learning pipeline limited its applicability to the LPMP solver, offering less utility for other solvers. Furthermore, the affinity generated by UM3C significantly im- proved the performance of LPMP compared to that generated by BBGM. These results affirm that our edge-wis, wise affinity learning enhances the robustness of the learned affinity, making it adaptable to various solvers.
H.7 SENSITIVITY TEST OF PSEUDO-LABELS
Sensitivity of pseudo-labels for UM3C. Experiments are conducted on Willow Object where we select Car, Duck, and Motorbike as the cluster classes. No outliers are included and apply RRWM to generate pseudo-labels during the training. "80%RRWM+UMSC denotes that the pseudo-labels is constructed by 80% RRWM results and 20% random permutation results.
Table 11:
Model
N
N
MA
CA
CP
RI
time(s)
g
100%RRWM M + UM3C
3
0.955
0.983
0.988
0.988
3.2
80%RRWM UM3C
3
0.786
0.932
0.953
0.947
3.3
60%RRWM UM3C
0.546
0.86
0.902
0.886
3.1
40%RRWM + UM3C
0.261
0.678
0.74
0.746
3.3
20%RRWA. UM3C
3 8
0.156
0.512
0.585
0.625
3.1
We conducted an experiment to assess the sensitivity of pseudo-labels. Table 11 reveals that match- ing accuracy is significantly influenced by the quality of pseudo-labels, demonstrating an almost linear relationship. It is noteworthy that clustering metrics appear more resilient to the degrada- tion of pseudo-labels. Even with 60% RRWM, the clustering results only decrease by 12.3% on CA. 8.6% on CP, and 10.2% on RI. These findings illustrate that UM3C effectively clusters objects even scenarios where matching pseudo-label are lacking. However, Table also indicates that if the pseudo-labels are excessively poor (20% RRWM and 40% RRWM), the cluster results may deteriorate rapidly.
27

---

Published as a conference paper at ICLR 2024
I VISUALIZATIONS
Figure 9: Comparison of different methods: (PMC()op), M3C(Middle), and UM3C(bottom). It is run on the setting with N₂ and Ng = 20 and outliers. Accuracy reported for each pairwise matching. All the pairs are randomly picked. Better viewing with color and zooming in.
Figure 10: Visualization of methods: M3C(top) and UM3C(bottom). is run the setting with N = 5 and N2 20 graphs and outliers. Accuracy is reported for each pairwise matching. All the pairs are randomly picked. Better viewing with color and zooming in.
28


Reviews:
[{"review_id": "mPaA4LF26J", "reviewer": "Reviewer_uZV9", "summary": "The author(s) introduce a manner to jointly solve the problem of graph matching and graph clustering. For, they propose an objective function and develop an algorithm in the framework of Minorize-Maximization. The resulting method is called M3C, after adding a relaxation of the hard cluster assignment. The last element of the work is to embed the M3C method into a learning framework for the affinity matrices, so that the method becomes unsupervised.  Numerical experiments study the usefulness of the proposed method.\n\nThe contributions are :\ni) the proposition of the joint matching and clustering for graphs, and that is interesting\nii) the algorithm to solve that, involving MM, then relaxation of the hard assignment matrix, and then the plugging into deep learning methods so as to obtain an unsupervised version. \n\nAll that is moderately original, still it has the advantage that it appears to work.", "questions": "- The topic of joint matching and clustering for graphs is sound, although the authors should strive to find situations that are more elaborated than their examples on images. This assumes that images are best coded as graphs, yet nothing is said in support of that; also; the graphs representing images are quite simple.\nThe authors should think about situations where the affinity graphs are less simple, and the graphs more complex. \n\n- page 1 : K (the affinity matrix) is not defined \n\n- p 6 in 5.1: Where is \\Lambda defined ?\n\n- Is there a comparison to simpler graph matching methods, for instance using optimal transport distance, that are known to also be usable for clustering ?\n\n- In 4.2, and then in 4.3, a softened version of the hard assignment matrix, C, is introduced. Is it only anrelaxation for easier convergence, or does the relaxed matrices capture something about possible confusion between the clusters ? It would be useful if it is the case,  as we often have clusters which are not as clear  cut as hard assignment is assuming.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- A sound problem, to try to study jointly matching and clustering for graphs\n\n- The theoretical parts, often postponed in the supplementary sections, are well written. Yet they are coming straight from classical results.\n\n- The numerical experiments are well conducted.\n\n- Adequate numerical performance on the two used datasets for comparison to other methods\n\n- A large choice of numerical  experiments, both in the main text and in the appendices", "weaknesses": "- The problem is sound, yet it does not appear to be really important. In addition, I am not certain of the added value of solving the two problems at the same time ; the authors should spend more energy to convince the readers of that. For instance, it seems that frameworks coming from optimal transport for graphs would solve both matching and clustering for graphs. Or isn't it possible ? Why is it better to design a method focusing on both in 1 step ?\n\n- In the absence of an insightful discussion (or proof...) about the necessity of considering graph matching and graph clustering in a joint approach, the article is over-stating somehow its contribution ; even if UM3C works, it's not certain it is needed.\n\n- the criteria proposed in equation (2) appear to be ad hoc \n\n- the Minorize-Maximization (MM) framework is not new, and here used in a classical way (hence most of it would move to the appendices)\n\n- the writing could be improved.\nThe presentation is nearly adequate, yet it comes with some repetitions. \nThe derivation of the overall objective for joint matching and clustering, eq (2), is not well presented and one does not fully know where it comes from, if there could be other choices, and globally what is ad hoc in this formulation and what is mandatory.\n\n- The authors rely heavily on the figures (1 and 2) for the readers to understand the full picture, but for me they are not that clear because there are too many elements displayed at the same place.", "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": "fudqXexDbb", "reviewer": "Reviewer_euAu", "summary": "This paper proposes a novel algorithm to jointly optimize graph clustering and matching. The optimization problem is formulated as a minorize-maximization problem with guaranteed convergence. An unsupervised variant is further introduced to incorporate edge-wise affinity and pseudo label selection. Experiments demonstrate the effectiveness of the proposed method.", "questions": "-\tSection 4.1: what’s the definition for $g(X|X^t)$? Is it the graph matching objective function given the clustering result h(X^t)?\n-\tConvergence statement above Eq.(3): Eq.(3) only guarantees your objective function is non-decreasing, but not necessarily guarantee convergence? I think another important reason for the convergence of f is that the solution space (X,C) is finite. In some scenarios, even the objective function remains unchanged, multiple optimal solutions may exists (i.e., $f(X_i,C_i)=f(X_j,C_j)$), and the solution may switch between $(X_i,C_i$ and $X_j,C_j$) instead of converging.\n-\tProposition 4.1: $N_{g_i}$ are used w/o definition. How can you guarantee the if condition that the sizes of clusters are the same in two consecutive iterations? I think this is a quite strict condition, and hence I don’t think this proposition provide insightful understanding to the convergence. Besides, you claimed a ‘quick convergence’ in Appendix C.3, it’s necessary to provide a convergence rate.\n-\tSection 4.2: you claimed disregarding the transitive relations as an advantage, can you explain why? As mentioned later you adopt a greedy search to get the top-$ rN^2$ values, this may breaks the transitive constraint, making it possible to have c_{ik}=1,c_{kj}=1$ but $c_{ij}\\neq 1$, which does not make sense to me.\n-\tEq. (6): how are $r$ selected? I think this is highly heuristic and may dramatically influence the model performance.\n-\tEq. (8): you claimed your method as unsupervised, but you need the hand-crafted $K^{raw}$ as input, which actually is another kind of supervision.\n-\tWriting\n  - Definition 2: $k_1,k_2,…$ and $N$ used w/o definition; How can you multiply the two matrices $X_{ik_1}$ with $X_{k_1k_2}$ as they are not necessarily (and mostly) with the same shape? The vertex set $\\mathcal{V}$ is defined as a set of graphs.\n  - Eq.(18): $c_{ij}^t\\to c_{ij}^{(t)}$.\n  - For equations not quoted in the main text, you should not number it and use ‘equation*’ environment instead.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "-\tIt is a novel idea to jointly address graph clustering and matching problems simultaneously, which are mutually beneficial.\n-\tFast convergence is achieved by the minorize-maximization framework.", "weaknesses": "-\tThe presentation of the paper needs further improvements. Several confusing symbols/notations are abused or used w/o declaration.\n-\tThe theoretical analysis may need further justification.\n-\tThough the UM3C method is called to be unsupervised, it still requires the hand-crafted affinity matrix, which is another kind of supervision.", "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": "AX6hsmUSJh", "reviewer": "Reviewer_sBU3", "summary": "This work explores a practical scenario in graph matching, where the collected graphs are of different types. To tackle this issue, the authors introduced a strategy named MGMC which simultaneously performs graph clustering and graph matching, along with a novel method M3C as an implementation of such strategy. M3C not only handles graph matching with mixed types, but also addresses several drawbacks of previous graph matching methods. Overall, the studied topic is meaningful and the work is solid despite some minor weaknesses, so I recommend acceptance for presenting it at ICLR.", "questions": "* What's the major benefit of MGMC? For matching with mixed graph types, we could employ graph-level classification or clustering (so that labeling is also avoided) methods to preprocess the dataset and apply conventional graph matching methods to individual classes. No ablation experiment is conducted to verify the effectiveness of MGMC anyway.\n* Is it possible to integrate the proposed method into a fully end-to-end GM pipeline (such as NGMv2)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is easy to read, and well-written in general.\n* The studied scenario in which the dataset is a mixture of different graph types is important in practical applications.\n* The proposed model along with its MM-based optimization algorithm solves several drawbacks of previous graph matching methods.", "weaknesses": "* The literature part lacks state-of-the-art works published in the last two years.\n* The authors didn't compare with the latest works. The most recent competitor MGM-Floyd was published in 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": {}}, {"review_id": "N5cwxehYON", "reviewer": "Reviewer_ra71", "summary": "The paper presents a full framework dedicated to graph matching using both unsupervised and supervised methods. The framework mixes graph matching and clustering leading to a method able to deal with heterogeneous set of graphs in a fully unsupervised way. The experiments show promising results on classical datasets.", "questions": "I have some questions on the cluster part,\n- the MM method asks to solve two problems (namely equations (6) and (7)). Both problems remain hard to solve so I don't see how they can be solved in a proper way. Only one method is proposed but not really described.\n- the supergraph is an important tool here. How is it really built? Do we need some heuristic to lessen the problem?\n\nSome other questions on the deep learning part,\n- how the features on edges are build? I don't see how the VGG-16 features are used in this case.\n- how much the method is sensitive toward the initialization of the pseudo-labels? From the experiments, RRWM seems good enough (in the sense they don't completely failed).", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The framework seems very general and address a very classical problem in computer vision. Compared to previous methods it can use both node and edges attributes for matching. The combination of supervised and unsupervised methods helps to improve classical methods with only handcraft features. Most of the paper is clear and easy to read.", "weaknesses": "The proposed work has several weakness,\n\n- the pairwise graph matching relies on the Lawler's QAP formulation which is known to not scale well with the size of the graphs. In the experiement all the graphs are shorts (less than 20 nodes for most), this is not the case in general.\n- the framework need an initialization with a classical pairwise method. We may expect some sentivity with the chosen method. I did not see any discussion on this part. Furthermore there exists better methods than RRWM like\n    - [KerGM](https://proceedings.neurips.cc/paper_files/paper/2019/hash/cd63a3eec3319fd9c84c942a08316e00-Abstract.html) which is able to use edge attributes\n    - [GWL](http://proceedings.mlr.press/v97/xu19b.html)\n- the comparison with the state of art is missing many others existing methods. The proposed methods are all from the very same team. I would expect a better state-of-art. For example on the deep learning side we have (to cite a few),\n    - [SIGMA](https://proceedings.mlr.press/v139/liu21i/liu21i.pdf)\n    - [Universe Points Representation Learning for Partial Multi-Graph Matching](https://arxiv.org/abs/2212.00780)\n    - [DGMC](https://openreview.net/forum?id=HyeJf1HKvS)\n- the full framework is focus on images. It is difficult to assess if it can be extended to general graphs. For example, in the DGMC paper there is an experiment where the attributes are only coordinates.", "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)