Learning Latent Topology for Graph Matching
Authors: Tianshu Yu
Runzhong Wang
Junchi Yan
Baoxin Li
Venue:  (2021)
Keywords: Graph matching
generative graph model
latent structure learning

Abstract: Graph matching (GM) has been traditionally modeled as a deterministic optimization problem characterized by an affinity matrix under pre-defined graph topology. Though there have been several attempts on learning more effective node-level affinity/representation for matching, they still heavily rely on the initial graph structure/topology which is typically obtained through heuristic ways (e.g. Delauney or $k$-nearest) and will not be adjusted during the learning process to adapt to problem-specific patterns. We argue that a standalone graph representation learning is insufficient for GM task, whereby a GM solver may favor some latent topology other than pre-defined one. Motivated by this hypothesis, we propose to learn latent graph topology in replacement of the fixed topology as input. To this end, we devise two types of latent graph generation procedures in deterministic and generative fashion, respectively. Particularly, the generative procedure emphasizes the across-graph consistency and thus can be viewed as a \textbf{co-generative} model. Our methods show superior performance over previous state-of-the-arts on several benchmarks, thus strongly supporting our hypothesis.

Under review as a conference paper at ICLR 2021
LEARNING LATENT TOPOLOGY FOR GRAPH MATCHING
Anonymous authors Paper under double-blind review
ABSTRACT
Graph matching (GM) has been traditionally modeled as a deterministic optimiza- tion problem characterized by an affinity matrix under pre-defined graph topology. Though there have been several attempts on learning more effective node-level affnity/representation for matching, they still heavily rely on the initial graph structure/topologyy which is typically obtained through heuristic ways (e.g. Delau- nay or k-nearest) and will not be adjusted during the learning process to adapt to problem-specific patterns. We argue that such mechanism for learning on the fixed topology may restrict the potential of a GM solver for specific tasks, and propose to learn latent graph topology input. To this end, we devise two types of latent graph generation procedures in a deterministic and generative fashion, respectively. Particularly, the generative procedure emphasizes the across- across-graph graph consistency and thus can be viewed as a saiching-guided generative model. Our methods show superior performance over previous state-of-the-arts public benchmarks.
replacement of the fixed topology as
INTRODUCTION
Being long standing NP-hard problem (Loiola et al., 2007), graph matching (GM) has received per- sistent attention from the machine learning and optimization communities for many years. Concretely, for two graphs with nodes for each, graph matching seeks to solve!:
maxz Mz
s.t.
Z E {0, 1)
Hz =
where the affinity matrix M E xn?"xn? affintiisssimillaitiiss and is the column- wise vectorization form of the permutation matrix Z. H is a selection matrix ensuring each row and column of Z summing to 1. 1 is column vector filled with 1. Eq. (1) is the so-called quadratic assignment problem (QAP) (Cho et al., 2010). Maximizing Eq. (I) amounts to maximizing the sum of the similarity induced by matching vector Z. While
xn² encodes node (diagonal elements) and edge (off-diagonal)
Eq. (I) does not encode the topology of graphs, Zhou & Torre (2016) further propose to factorize M to explicitly incorporate topology matrix, where a connectivity matrix A E {0, 1) | is used to indicate the topology of a single graph (Ai = 1 if there exists an edge between nodes and j;
Aij 0 otherwise). To ease the computation, Eq. (1) is typically relaxed by letting E [0, 1]"² and keeping other parts of Eq. (1) intact. Traditional solvers to such relaxed problem generally fall into the categories of iterative update (Cho et al., 2010; Jiang al.. 2017) numerical continuation (Zhou & Torre, 2016; Yu et al., 2018). 1)), where the solvers are developed under two key assumptions: 1) Affinity M is pre-computed with some neg-negative metrics, e.g. Gaussian kernel, 7,2 d.2-distance or Manhattan distance; 2) Graph topology is pre-defined as input either in dense (Schellewald & Schnörr, 2005) or sparse (Zhou & Torre, 2016) fashion. There have been several successful attempts towards adjusting the first assumption by leveraging the power of deep networks to learn more effective graph representation for GM (Wang et al., 2019a; Yu et al., 2020; Fey al., 2020). However, to our best knowledge, there is little previous work questioning and addressing the problem regarding the second assumption in the context of learning- based graph matching". For example, existing
'Without loss of generality, we discuss graph matching under the setting of equal number of nodes without outliers. The unequal case can be readily handled by introducing extra constraints or dummy nodes. Bipartite matching and graph isomorphism are subsets this quadratic formulation (I (Loiola et al., 2007).
"There are some loosely related works (Du al., 2019; 2020) network alignment and link prediction without learning, which will be discussed in detail in the related works.

---

Under review as a conference paper at ICLR 2021
standard pipeline of keypoint matching in computer vision will construct initial topology by Delaunay triangulation or k-nearest neighbors. Then this topology will be freezed throughout the subsequent learning and matching procedures. In this sense, the construction of graph topology is peeled from matching task as a pre-processing stage. More examples can he found beyond the vision communities such in social network alignment (Zhang & Tong, 2016; Heimann al., 2018; Xiong & Yan, 2020) assuming fixed network structure for individual node matching in two networks.
We argue that freezing graph topology for matching can hinder the capacity of graph matching solvers. For a pre-defined graph topology, the linked nodes sometimes result in less meaning- ful interaction, especially under the message-passingg mechanism graph neural networks (Kipf & Welling, 2017). We give a schematic demonstration in Fig. 1. Though some earlier at- tempts (Cho & Lee, 2012: Cho et al., 2013) seek to adjust the graph topology under traditional non-deep learning setting, such procedures cannot be readily integrated into end-to-end deep learning frameworks due to undifferentiable nature. Building upon the hypothesis that there exists some latent topology better than heuristically created one for GM, our aim is to learn (or its distribution) for GM. Indeed, jointly solving matching and graph topology learning can be intimidating due to the combinatorial nature, which calls for more advanced approaches.
Positive matching
Negative matching
In this paper, we propose an end-to-end framework to jointly learn the latent graph topology and per- form GM, termed as deep latent graph matching (DLGM). We leverage the power of graph genera- tive model to automatically produce graph topology from given features and their geometric relations, under specific locality prior. Different from gener- ative learning on singleton graphs (Kipf & Welling, 2016; Bojchevski et al., 2018), our graph generative learning is performed in pairwise fashion, lead- ing to a novel watching-guider generative paradigm. The source code will be made publicly available.
Diteaey sxace graet
Genemred svace zopóe
Generate
Generate
We explore a new direction for more flexible GM by actively learning latent topology, in contrast to previous works using fixed topology input; 2) Under this setting, we pro- pose a deterministic optimization approach to learn graph topology for matching; 3) We further present a generative way to produce latent topology un- der probabilistic interpretation by Expectation- Maximization. This framework can also adapt to other problems where graph topology the latent structure to infer; 4) Our method achieves state-of- the-art performance on public benchmarks.
Contributions: 1)
BBGM: 11/13
DIGM-G: 13/13
Figure 1: Matching of BBGM (Rolinek et al., 2020) 11/13 with Delaunay triangulation and our DLGM-G 13/13 using generated graph (Pascal VOC). DLGM-G generates graph with 4 more edges than Delaunay (33 vs 29) for both source and target. But with 4 more common edges across source and target than Delaunay triangulation (26 vs. 22), it leads to better accu- racy. Blue and red edges denote common edges in Delaunay and learned graph pairs.
RELATED WORKS
In this section, we first discuss existing works for graph topology and matching updating whose motivation is a bit similar to ours while the technique is largely different. Then we discuss relevant works in learning graph matching and generative graph models from the technical perspective.
Topology updating and matching. There are a few works for joint graph topology updating and matching, in the context of network alignment. Specifically, given two initial networks for matching, Du et al. (2019) show how to alternatively perform link prediction within each network and node matching across networks based on the observation that these two tasks can benefit to each other. In their extension (Du et al., 2020), a skip-gram embedding framework is further established under the same problem setting. In fact, these works involve a random-wald walk based node embedding updating and classification based link prediction modules and the whole algorithm runs in a one-shot optimization fashion. There is neither explicit training dataset nor trained matching model (except
2

---

Under review as a conference paper at ICLR 2021
for the link classifier), which bears less flavor of machine learning. In contrast, method involves training an explicit model for topology recovery and matching solving. Specifically, our deterministic technique (see Sec. 3.4.1) solves graph topology and matching in one-shot, while the proposed generative method alternatively estimates the topology and matching (see Sec. 3.4.2). Our approach allows to fully leverage multiple training samples in many applications like computer vision boost the performance on test set. Moreover, the combinatorial nature of the matching problem is not addressed in (Du al., 2019; 2020), and they adopt greedy selection strategy instead. While we develop a principled combinatorial learning approach to this challenge. Also their methods rely on considerable amount of seed matchings, yet this paper directly learns the latent topology from scratch which is more challenging and seldom studied.
Learning of graph matching. Early non-deep learning- methods seek to learn effective metric (e.g. weighted Euclid distance) for node and edge features affinity kernel (e.g. Gaussian kernel) in a parametric fashion (Caetano et al., 2009; Cho et al., 2013). Recent deep graph matching methods have shown how to extracte more dedicated feature representation. The work (Zanfir & Sminchisescu, 2018) adopts VGG16 (Simonyan & Zisserman, 2014) as the backbone for feature extraction on images. Other efforts have been witnessed in developing more advanced pipelines, where graph embedding (Wang et al., 2019a; Yu et al., 2020; Fey et al., 2020) and geometric learning (Zhang & Lee, 2019; Fey et al., 2020) are involved. Rolínek et al. (2020) study the way of incorporating traditional non non-differentiable combinatorial solvers, by introducing differentiatiable blackbox GM solver (Pogancic et al., 2020). Recent works in tackling combinatorial problem with deep learning (Huang et al., 2019; Kool & Welling, 2018) also inspire developing combinatorial deep solvers, for GM problems formulated by both Koopmans-Beckmann Wang et al., 2019a) and Lawler's QAP (Wang et al., 2019b). Specifically, Wang et al. (2019a) devise a permutation loss for supervised learning, with an improvement in Yu et al. (2020) via Hungarian attention. Wang al. (2019b) solve the most general Lawler's 's QAP with graph embedding technique.
Beckmann's QAP (Nowak et al., 2018;
Generative graph model. Early generative models for graph can date back to (Erdos & Renyi, 1959), in which edges are generated with fixed probability. Recently, Kipf & Welling (2016) present a graph generative model by re-parameterizing the edge probability from Gaussian noise. Johnson (2017) propose generate graph in an incremental fashion, and in each iteration a portion of the graph is produced. graph from a sequence of molecule representation. Adversarial graph generation is considered in (Pan et al., 2018; Wang et al., 2018; Bojchevski et al., 2018). Specifically, Wang et al. (2018); 8); Bojchevski et al. (2018) seek to unify graph generative model and generative adversarial networks. In parallel, reinforcement learning has been adopted to generate discrete graphs (De Cao & Kipf, 2018).
et al. (2018) utilized recurrent neural network to generate
3 LEARNING LATENT TOPOLOGY FOR GM
In this section, we describe details of the proposed framework with two specific algorithms de- rived from deterministic and generative perspectives, respectively. Both algorithms are motivated by the hypothesis that there exists some latent topology more suitable for matching rather than fixed one. Note the proposed deterministic algorithm performs a standard to jointly learn the topology and matching, while our generative algorithm consists of alterna- tive optimization procedure between estimating latent topology and learning matching under an Expectation- Maaitiiiaiaiiiiiiiiionn (EM) interpretation. In general, the generative algorithm assumes that latent topology is sampled from a latent distribution, where the expected matching accuracy sufficing this distribution is maximized. Therefore, we expect to learn topology generator sufficing such distribution. We reformulate GM into Bayesian fashion for consistent discussion in Sec. 3.1, detail deterministiclgeneratiee latent module in Sec. 3.2 and discuss the loss functions from a probabilistic perspective in Sec. 3.3. We finally elaborate on the holistic framework and the optimization procedure for both algorithms (deterministic and generative) in Sec. 3.4.
pass
3.1 PROBLEM DEFINITION AND BACKGROUND
GM problem can be viewed as a Bayesian variant of Eq. (1). In general, let ((+) and (()) represent the initial source and target graphs for matching, respectively. We represent graph as G == [X, E, A}.
where X E Raxdi is the representation of n nodes with dimension d, E B mx are features of
3

---

Under review as a conference paper at ICLR 2021
m edges and A {0, 1)xxx* is initial connectivity (i.e. topology) matrix by heuristics e.g. Delaunay triangulation. For notational brevity, we assume dj and d2 keep intact after updating the features across each convolutional layers of GNN (i.e., feature dimensions of both nodes and edges will not change after each layer's update). Denote the matching Z E {0. 1 j between two graphs, where Zij = indicates a correspondence exists between node i in g and node j in g()) and Zij otherwise. Given training samples (Zz, g( ( with 1,2, .., N, the objective of learning-based based GM aims to maximize the likelihood:
max II Po (Z .(())
where 0 denotes model parameters. (-) measures the probability of matching Z& given the k-th pair, and is instantiated via network parameterized by 0.
Being a generic module for producing latent topology, our method can be flexibly integrated into existing deep GM frameworks. We build up our method based on state-of-the-art (Rolinek et al., 2020), which utilizes SplineCNN (Fey al., 2018) for node/edge representation learning. SplineCNN is a specific graph neural networks which updates node representation via a weighted summation of its neighbors. The update rule at node of a standard SplineCNN reads:
d1
(x (1)
mıli) (i(e(i))) JEN((
Σ
N(1)
where zı(j) performs the convolution on node j and outputs a dy-dimensional feature. gr(-) delivers the message weight given the edge feature e(i,j) (N)) refers i's neighboring nodes Summation over neighbors follows the topology A. Since our algorithm learns to generate topology, we need to explicitly express Eq. (3) in differentiable way w.r.t. A. To this end, we rewrite Eq. (3) as:
(x g A) = (Å G)
(4)
where Å is the normalized connectivity with each row normalized by the degree [i(ii) (see Eq. (3)) of the corresponding node i. G and X correspond to outputs of gr(-) and x²(()) operators, respec- tively. (- is the Hadamard product. With Eq. (4), we thus can perform back-propag on comnectivityyloologyy A. See more details in Appendix A.2.
3.2 LATENT TOPOLOGY LEARNING
Existing learning-basees based graph matching algorithms consider A to be fixed throughout the computation without questioning if the input topology is optimal not. This can be problematic since input graph construction is heuristic, and never takes into account how suitable it for the subsequent GM task. In our framework, instead of utilizing fixed pre-defined topology, we consider produce latent topology under two settings: 1) a deterministic and 2) generative way. The former is often more efficient while the latter method can be more accurate at the cost of exploring more latent topology. Note both methods produce discrete topology to verify our hypothesis about the existence more suitable discrete latent topology for GM problem. The followings describe deep structures.
Deterministic learning: Given input features X and initial topology A, the deterministic way of generating latent topology E {0, [0,1)xxx jxx is::
Rounding(sigmoidly/ Wy,)) with Y LGGNCXXAA
(5)
where G.N(.) is the graph convolutional networks (GCN) (Kipf & Welling, 2017) and y, corresponds to the feature of node i in feature map Y. W the learnable parameter matrix. Note function Rounding(-) is undifferentiable, and will be discussed in Sec. 1.
Generative learning: We reparameterize the representation as:
P(y (yy:XAA) = (yss/,,, diag(o())
We consider the case when only node feature E. and topology A are necessary. Edge feature E can be readily integrated another input.
4

---

Under review as a conference paper at ICLR 2021
with μ G (X, A) and o GCN. A) two GCNs producing mean and covariance. It
is equivalent to sampling a random vector from i.dd. uniform distribution ~ U( 1), then applying
y == σ, where (-) is element-wiss product.
Similar as Eq. (5) by introducing learnable parameter W. the generative latent topology is sampled following i.i.d. distribution over each edge (i:
P(AY) IIIII P(A,
with P(A,j = yy) sigmoid(y, Wy,)
Since sigmoid(.) maps any input into (0, 1). Eq. (7) can be interpreted as the probability of sampling edge (i.j). As the sampling procedure is undifferentiable, we apply Gumbel-softmax trick (Jang et al., 2017) as another reparameterization procedure. As such, a latent graph topology A can be sampled fully from distribution P(A) and the procedure becomes differentiable.
3.3 LOss FUNCTIONS
In this section, we explain three loss functions and the behind motivation: matching loss, locality loss and consistency loss. The corresponding probabilistic interpretation of each loss function can be found in Sec. 3.4.2. These functions are selectively activated in DLGM-D and DLGM-G (see Sec. 3.4). In DLGM-G, different loss functions are activated in inference and learning steps.
i) Matching loss. This common term measures how the predicted matching Ž diverges from ground- truth Z. Following Rolínek al. (2020), we adopt Hamming distance node-wise matching:
LM Hamming(2 (2 Z)
ii) Locality loss. This loss is devised to account for the general prior that the produced/learnt graph topology should advocate local connection rather than distant one, since two nodes may have less meaningful interaction once they are too distant from each other. In this sense, locality loss serves as prior or regularizer in GM. As shown in multiple GM methods (Yu et al., 2018; Wang et al., 2019a; Fey et al., 2020), Delaunay triangulation an effective way to deliver good locality. Therefore in our method, the locality loss is the Hamming distance between the initial topology A (obtained from Delaunay) and predicted topology for both source graph and target graph:
Lg = Hamming( A (o) A (+) + Hamming A (t) A (9)
We emphasize that locality loss serves as a prior for latent graph. It focuses on advocating locality, but not reconstructing the initial Delaunay triangulation (as in Graph VAE (Kipf & Welling, 2016)).
iil) Consistency loss. One can imagine that a GM solver is likely to deliver better performance if two graphs in a training pair are similar. In particular, we anticipate the latent topology A (s) and A (1) to be isomorphic under a specific matching, since isomorphic topological structures tend to be easier to match. Driven by this consideration, we devise the consistency loss which measures the level of isomorphism between latent topology A (+) and A (t),
Cc(-Z)) Z Z
A (0) ZA ZT
- (+)
(10)
Note Z does not necessarily refer to the ground-truth, but can be any predicted matching. In this sense, latent topology A (*) and A can be generated jointly given the matching Z as guidance information. This term can also serve as consistency prior or regularization. We given a schematic
example showing the merit of introducing consistency loss in Fig. 2(b).
3.4 FRAMEWORK
A schematic diagram of our framework is given in Fig. 2(a) which consists of a singleton pipeline for processing a single image. It consists of three essential modules: a feature backbone BN a latent topology module (Nc) and feature refinement module (Nx). Specifically, module NG corresponds to Sec. 3.2 with deterministic or generative implementations. Note the geometric relation of keypoints provide some prior for generating topology A. We employ VGG16 (Simonyan & Zisserman, 2014)
5

---

Under review as a conference paper at ICLR 2021
Delammy
Image with keypoints
locality prior
lateot
NG
Natching
Np
NR
Sameene x =
A
A
feature
Singleton pipeline
(a) Singleton pipeline of DLGM.
(b) Example of consistency loss.
Figure 2: (a) One of the two branches of our DLGM framework (see the complete version in Appendix A.1). Ng: VGGI6 as backbone producing a global feature of input image, and initial X and E; Ng: deterministic or generative module producing latent topology A; Ng: SplineCNN for feature refinement producing updated X and E. (b) A schematic figure showing the merit of introducing consistency loss Le for training. Initial topology A (+) and A (+) are constructed using Delaunay triangulation. Given matching Z guidance, latent topology A
(s) and A are generated from inputs A (+) and A (1), respectively. Note the learned topology A (+) and A (9) isomorphic (C, = 0) w.r.t. Z which is easier to match in test, comparing to non-isomorphic input structures (C. 4).
as NB and feed the produced node feature X and edge feature E to NG. Ng also produces global feature for each image. After generating the latent topology A, we pass over X and together with A to NR (SplineCNN (Fey et al., 2018)). The holistic pipeline handling pairwise graph inputs can be found in Fig. in Appendix A. which consists of two copies singleton pipeline processing source and target data (in Siamese fashion), respectively. Then the outputs of two singleton pipelines formulated into affinity matrix, followed by a differentiable Blackbox GM solver (Pogancic et al., 2020) with passsng mechanism (Swoboda et al., 2017). Note pipeline with only NB + N n is identical to the method in (Rolínek et al., 2020). Readers are referred this strong bascline (Rolinck al., 2020) for more mutual algorithmic details.
without Ng, the holistic
3.4.1 OPTIMIZATION WITH DETERMINISTIC LATENT GRAPH
We show how to optimize with deterministic latent graph module, where the topology A is produced by Eq. (5). The objective of matching conditioned on the produced latent topology A becomes:
max II
(+) A
Z
g(() g(!)
(11)
Eq. (11) can be optimized with standard back- preppppopaattoon with three loss terms activated, except for the Rounding function (see Eq. (5)), which makes the procedure undifferentiable. To address this, we use straight-through operator (Bengio et al., 2013) which performs standard rounding during the forward pass but approximates with the gradient of identity during the backward pass on [o. 1]:
(Rounding(#)/000 =1
(12)
Though there exist some unbiased gradient estimators (e.g., REINFORCE (Williams, 1992)), the biased througgh estimator proved to be more efficient and has been successfully applied in several applications (Chung et al., 2017: Campos et al., 2018). All the network modules (NG + N + N1) are simultaneously learned during the training. All three losses activated in the learning procedure (see Sec. 3.3), which are applied on the predicted matching Z, the latent topology A and A (1). We term the algorithm under this setting DLGM-D.
3.4.2 OPTIMIZATION WITH GENERATIVE LATENT GRAPH
See more details in Appendix A.3. In this setting, the source and target latent topology A (+) and A are sampled according to Eq. (6) and (7). The objective becomes:
max II 1:
Po
Zk.
((1)
(13)
(9)

---

Under review as a conference paper at ICLR 2021
Unfortunately, directly optimizing Eq. (13) is difficult due the integration over A which is intractable. Instead, we maximize the evidence lower bound (ELBO) (Bishop, 2006) as follows:
log Po(Z)g(e) g(0) 2
(14)
log Po. (0) 1g(0) g()) log (+ A (g(o)) g())
BQ, (A()), A000A ((O)
where Qs (0) (1) , can be any joint distribution of A (+) and A (9) given the in- (
put graphs g()) and g(o Equality of Eq. (14) holds when @p (+) A
PA (*) A Z. " For tractability, we rationally introduce the independence by assum- ing that we can use an identical latent topology module Qs (corresponding to NG in Fig. 2(a)) to separately handle each input graph:
(A (+) A g(+), ((O) = (.
(15)
which can greatly simplify the model complexity. Then we can utilize a neural network to model Q+ (similar to modeling Po). The optimization of Eq. (14) is studied in (Neal & Hinton, 1998), known as Expectation-Mxximizttinnn
the Expectation Maximization (EM) algorithm. Optimization of Eq. (14) alternates between E-step and M-step. During E-step (inference), Po is fixed and the algorithm seeks to find an optimal Qa to approximate the true posterior distribution (see Appendix A.3 for explanation):
PA A (1) Z2 g(+)) g())
(16)
During M-step (learning), Qs is instead fixed and algorithm alters to maximize the likelihood:
QQ (A(1111)))) Q.. (A(A())())) log Po (s) A (0) (())) g(o)) x - -LM
(17)
We give more details on the inference and learning steps as follows.
Inference. This step focuses on deriving posterior distribution (A(A (+) A (1) Z,
using its approximation Qa. To this end, fix the parameters in modules Ng and NR, and only update the parameters & in module NG corresponding to Qa- As stated in Sec. 3.2, we employ the formulate
Gumbel-softmax trick for sampling discrete A (Jang al., 2017). To this end, 2D vector a.y
[P = 1),1- 19,1-P(A,, = 1)]T. Then the sampling becomes: softmax (log(a.)) + h:j;7)
(18)
where hy is a random 2D vector from Gumbel distribution, and is a small temperature parameter. We further impose prior latent topology A given A through locality loss:
log II 1.
P P(A Aij) & - CA
(19)
which is to preserve the locality in initial topology A. It should also be noted that Z is the predicted matching from current Po. as Q+ is an approximation. Besides, we also anticipate two generated
topology A (+) and AC (1) from graph pair should be similar (isomorphic) given matching Z:
log P
AA A
(1) (Z) x Lo
A
(0)
(6)
Z
(20)
In summary, we activate locality loss and consistency loss during the inference step, where the latter loss is conditioned with the predicted matching rather than the ground-truth. Note that the inference step involves twice re- parameterizzaion tricks corresponding to Eq. (6) and (18). respectively. While the first generates the continuous topology distribution under edge independence assumption, the second performs discrete sampling sufficing the generated topology distribution.
Learning. This step optimizes Pg by fixing Qs. We sample discrete graph topologies As completely from the probability of edge P(A., 1). Once latent topology As are sampled, we feed them to module Nn together with the node-level features from NB. Only NB and Nr are updated this step, and only matching loss LM is activated.
Remark. Note for each pair of graphs in training, we use an identical random vector s for generating both graphs' topology (see Eq. (6)). We pretrain the network Pg before alternativly training Pa and Qo- During pretraining. we activate NB + NR modules and L loss during pretraining, and feed the network the topology obtained from Delaunay the latent topology. After pretraining, the optimization will switch between inference and learning steps until convergence. We term the setting of generative latent graph matching DLGM-G and summarize it in Alg.
7

---

Under review as a conference paper at ICLR 2021
Algorithm I: Deep latent graph matching with generative latent graph (DLGM-G)
1: Input: 9", Gf and ground truth Z: Output: matching 2:
2: Pretrain Po using Eq. (1 given Delaunay as input topology;
3: while not converge do
4: # Inference (F-step):
5: Obtain predicted matching using fixed Ps:
6: Update Qo (i.e. No) with loss C2 + (-122) according to Eq. (16);
7:
# Learning (M-step):
8:
Obtain predicted graph topology (+) and A ( using Qo:
9: Update Po (i.e. Nş and Na) with loss Lat given A ( and A according to Eq. (17);
10:
end while
11:
Predict topology and the matching Z with whole network activated (i.c. No + +N + Na);
Table 1: Accuracy (%) on Pascal VOC (best in bold). Only inlier keypoints are considered.
method aero bike hird bottle
car
Cal
chair cow
dog
horse mbike person
plant sheep sola train
Iv
Ave
GMN 31.1 46, 58.2 45.9 70.6
76.4
61.2
61.7
35.5
53.7 58.9
57.5
56,9
49.3
34,1
77.5
S7.1
53.6
83.2 88.6
57.9
GAT-H 47.2 61.6 63.2 53.3
79.7
70. 65.3 70.5
38.4
64.7 62.9
65.
66.2
62.5
41.1
78.8
67.1
61.6
81.4 91.0
64.6
PCA 40.9 55.0
47.9
76.9
77.9 63.5
67.4
33.7
65.5
68.9
62.8
44.9
77.5
67.
57.5
86.7 90,9
63.8
CIE,-H 51.2 69.2
70.1 55.0
82.
72.8
69.0
74,2 39.6
68.8
71.8
70.0
718
66.8
44,8
85.2
69.9
65.4
85.2 92.4 68.9
DGMC 50.4 67.6 70.7 70.5
87.2
85.2
82.5 74.3 46.
69.4
69.9
73.9
73.8
65.4
51.6
98.0
73.2
69.6
94.3 89.6
73.2
BBGM 61.5 75.0 78.1 80.0
87.4
93.0 89.1 80.2
58.1
77.6
76.5
79.3
78.6
78.8
66.7
97.4
76.4
77.5
97.7 94,4
80.1
DLGM-D (ours) 60.8 76.0
77.5 19.6
88.0
95.0
90.4
81.0
67.3
82.4
94.1
79.6
812
80.5
68.9
9%.6
77.1
87.5
97.0
95.3
82.9
DLGM-G (ours) 64.7 78.1 78.4 81.0
87.2 94.6
89.7
82.5 68.5
83.0
93.9
82.3
82.8
82.7
69.6
98.6
78.9
88.9
97.4 96.7 83.8
Table 2: Fl-score (%) on Pascal VOC. Experiment are performed on a pair of images where both inlier and outlier keypoints are considered. BBGM-max a setting in Rolínek al. (2020).
method acto bike bird boat bottle bus car cat chair cow table dog horse mbike person plant sheep sola truin tV
Ave
BBGM-max 33.5 68.6 46.7 36.1 83.4
58.1 25.6 51.7 27.3 51.0 46.0 46.7
48.9
58.9
29.6
93.6
42.6 35.3 70.7 79.3
$1.9
BBGM 42.7 70.9 57.5
85.8
51.0 63.8 42.4 63.7 47.9
63.4
69.0
46.1
94.2
57.4 39.0 78.0 82.7
61.4
DLGM-D (ours) 42.5 71.8 57.8
46.8
86,9
70.3
53.4
66.7
53.8
67.6
64.7 64.6
65.2
70.1
47.9
95.5
59.6
47.7 77.7 82.6 63.9
DLGM-G (ours) 43.8 72.9 58.5
47.4
86.4
71.2
53.1
66.9
54.6
67.8
64.9
65.7
66.9
70.8
47.4
96.5
61.4
48.4
77.5
83,9 64.8
4 EXPERIMENT
We conduct experiments on datasets including Pascal VOC with Berkeley annotation (Everingham et al., 2010; Bourdev & Malik, 2009), Willow ObjectClass (Cho et al., 2013) and SPair-71K (Min et al., 2019). We report the per-category and average performance. The objective of all experiments is to maximize the average matching accuracy. Both our DLGM-D and DLGM-G are tested.
Peer methods. We conduct comparison experiments against the following algorithms: 1) GMN (Zanfir& & Sminchisescu, 2018), which is a seminal work incorporating graph matching into deep learning framework equipped with spectral solver (Egozi et al., 2013); 2) PCA (Wang al., 2019a). This method treats graph matching as feature matching problem and employs GCN (Kipf & Welling, 2017) to learn better features; 3) /IE,//AT-H (Yu et al., 2020). This paper develops a novel embedding and attention mechanism, where GAT-H is the version by replacing the basic embedding block with Graph Attention Networks (Veličković et al.. 2018); 4) DGMC (Fey et al., 2020). This method devises a post-processing step by emphasizing the neighborhood similarity; 5) BBGM (Rolínek et al., 2020). integrates a differentiable linear combinatorial solver (Pogancic et al., 2020) into a deep learning framework and achieves sate-of-theear performance.
Results on Pascal VOC. The dataset (Everingham et al., 2010; Bourdev & Malik, 2009) consists 7,020 training images and 1,682 testing images with 20 classes in total, together with the object bounding boxing for each. Following the data preparation in (Wang et al., 201 2019a), each object within the bounding box is cropped and resized to 256 x 256. The number of nodes per graph ranges from 6 to 23. We further follow (Rolinek et al., 2020) under two evaluating metrics: 1) Accuracy: this is the standard metric evaluated the keypoints by filtering out the outliers; 2) F1-score: this metric is evaluated without keypoint filtering, being the harmonic mean of precision and recall.
Experimental results the two setting shown in Tab. and Tab. 2. The proposed method under either settings of DLGM-D and DLGM-G outperforms counterparts by accuracy and fc-score. DLGM-G generally outperforms DLGM-D. Discussion can be found in Appendix A.5.
8

---

Under review as a conference paper at ICLR 2021
Table Accuracy (%) on SPair-7 IK compared with state-of-the-arl methods (best in bold).
method aero bike bird boat bottle bus
cat chair cow dog horse mbike person plant sheep train
Ave
DGMC 54.8 44.8 80.3 70.9 65.5 90.1 78.5 66.7 66.4 73.2 66.2
66.5
65.7
59.1
98.7
68.5
84,9 98.0
72.2
BBGM 66.9 57.7 85,8 78.5 66.9 95.4 4 86, 74.6 68.3 78.9 73.0 67.5
79.3
73.0
99.1
74,8
95.0 98.6
78.9
DLGM-D (ours)
69.8 64.4 86.8 79.9 69.8 96.8 87.3 77.7 77.5 83.1 76.7
69.6
85.1
75.1
98.7
76.4
95.8
97.9
81.3
DLGM-G (ours)
70.4 66.8 86.7
81.7
69.2
96.4 85.8 79.5
78.4
84.0
79.4
69.4
84.5
76.6
99.1
75.9
96.4
98.5
82.0
Quality of generated topology. We further show the consistency/locaiiy curve vs epoch in Fig. 3, since both consistency and locality losses can somewhat reflect the quality of topology generation. shows that both locality and consistency losses descend during the training. Note that the consistency loss with Delaunay triangulation (green dashed line) is far more larger than our generated ones (blue/red dashed line). This clearly supports the claim that our method generates similar (more isomorphic) typologies, as well as preserving locality.
Consistencyl
Table 3: Accuracy (%) on Willow Object.
OLCM locality
DLC M-Dr convateryy
Method
setting
face
mbike
car
duck
whottle
DLE M-G: localllty loss
Pt
98.1
65.0
72.9
74.3
70.5
Deluinyy contiseeryy loss
DLEMM-D conseiency less
GMN
Wt
99.3
71.4
82.8
76.7
Pt
100.0
69.8
78.6
82,4
95.1
PCA
W1
100.0
76.7
84.0
93.5
96.9
Pt 93.9
71.5
75.4
73.2
97.6
CIE
W1
100.0
90.0
82.2
81.2
97.6
98.6
69.8
84.6 76.8
90.7
DGMC
W1
100.0
98.8
96.5
93.2
99.9
Epoch
BBGM
Pt
100.0
95.8
89.1 89.8
97.9
Wt
98.9
95.7
93.1
99.1
Figure 3: Consistency and locality loss (Eq. (9) and (10)) keep decrease over training showing the effectiveness for adaptive topology learning for matching.
DLGM-D (ours)
Pt
100.0
95.5
91.3
91.4
97.9
Wt
100.0
99.4
95.9
92.8
99.3
DI DLGM- (ours)
96.4
92.0
91.8
Wt 100.0
99.3
96.5
93.7
99.3
Results on Willow Object. The benchmark (Cho et al., 2013) consists of 256 images in 5 categories, where two categories (car and motorbike) preparation protocol in Wang et al. (2019a), we crop the image within the object bounding box and resize it to 256 256. Since the dataset is relatively small, we conduct the experiment verify the transfer ability of different methods under two settings: 1) trained on Pascal VOC and directly applied to Willow (Pt); 2) trained on Pascal VOC then finetuned on Willow (Wt). Results under the two settings are shown in Tab. 3. Since this dataset is relatively small, further improvement is difficult. is shown both DLGM-D and DLGM-G have good transfer ability.
subsets selected from Pascal VOC. Following the
Results on SPair- 71K. The dataset (Min et al., 2019) is much larger than Pascal VOC and WillowOb- ject since it consists of 70,958 image pairs collected from Pascal VOC 2012 and Pascal 3D+ (53,340 for training, 5,384 for validation and 12,234 for testing). It improves Pascal VOC by removing ambiguous categories sofa and dining table. This dataset is considered to contain more difficult matching instances and higher annotation quality. Results are summarized in Tab, 4. Our method consistently improves the matching performance, agreeing with the results in Pascal VOC and Willow.
CONCLUSION
Graph matching involves two essential factors: the affinity model and topology. By incorporating learning paradigm for affinity/feature, the performance of matching on public datasets has significantly been improved. However, there has been little previous work exploring more effective topology for matching. In this paper, we argue that learning a more effective graph topology can significantly improve the matching, thus being essential. To this end, we propose to incorporate latent topology module under an end-to-end deep network framework that learns to produce better graph topology. We also present the interpretation and optimization of topology module in both deterministic and generative perspectives, respectively. Experimental results show that, by learning the latent graph, the matching performance can be consistently and significantly enhanced on several public datasets.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv: /308.3:/000.300 308.3432, 2013.
Christopher M Bishop. Puttern recognition and machine learning- springer, 2006.
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. Netgan: Generating graphs via random walks. In ICML, 2018.
Lubomir Bourdev and Jitendra Malik. Poselets: Body part detectors trained using 3d human pose annotations. In ICCV, 2009.
T. Caetano, J. McAuley, L. Cheng, Q. Le, and A. Smola. Learning graph matching. TPAMI, 31(6): 1048-1058, 2009.
Víctor Campos, Brendan Jou, Xavier Giró-i Nieto, Jordi Torres, and Shih-Fu Chang. Skip rmn: Learning skip state updates in recurrent neural networks. In ICLR, 2018.
M. Cho and K. M. Lee. Progressive graph matching: Making a move of graphs via probabilistic voting, In CVPR, 2012.
M. Cho, J. Lee, and K. M. Lee. Reweighted random walks for graph matching. In ECCV, 2010.
M. Cho, Alahari, and Ponce. Learning graphs to match. ICCV, 2013.
Junyoung Chung, Sungjin Ahn, and Yoshua Bengio. Hierarchical multiscale recurrent neural networks. In ICLR, 2017.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint arXiv: 1rXhv:1805.1197. 2018.
Xingbo Du, Junchi Yan, and Hongyuan Zha. Joint link prediction and network alignment via cross-graph embedding. IJCAI, 2019.
Xingbo Du, Junchi Yan, Rui Zhang, and Hongyuan Zha. Cross-network skip-gram embedding for joint network alignment and link prediction. IEEE Transactions on Knowledge and Data Engineering. 2020.
A. Egozi, Y. Keller, and H. Guterman. probabilistic approach to spectral graph matching. TPAMI, 2013.
Paul Erdos and Alfied Renyi. On random graphs In Publicationes Mathematicae Debrecen 6, 1959.
Mark Everingham, Luc Gool, Christopher K. Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. Int. Comput. Vision, 88(2):303-335 June 2010.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splinecnn: Fast geometric deep learning with continuous b-spline kernels. In CVPR, 2018
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils Kriege. Deep graph matching consensus. In ICLR, 2020.
Rafael
Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobags Benjamín Sánchez- Lannheez-engeling.. Dennis Sheberla, Jorge Aguilera-Iparae Iparrauuire, Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik, Automatic chemical design using data-driven continuous representation of molecules. ACS central science, 4(2):268-22 2766, 2018.
Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. Regal: Representation learning-based graph alignment. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 117-126. ACM, 2018
Jiayi Huang, Mostofa Patwary. and Gregory Diamos. Coloring big graphs with alphagozero. arXiv: /90::9902//000 10162, 2019.
10

---

Under review as a conference paper at ICLR 2021
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In ICLR, 2017.
Bo Jiang, Jin Tang, Chris Ding, Yihong Gong, and Bin Luo. Graph matching via multiplicative update algorithm. In NIPS, 2017.
Daniel D Johnson. Learning graphical state transitions. In ICLR, 2017.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv: 161 2016.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Woute Kool and Max Welling. Attention solves your tsp. arXiv:1803.08477 2018.
E. M. Loiola, N. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido. A survey for the quadratic assignment problem. EJOR, pp. 657-90, 2007.
Juhong Min, Jongmin Lee, Jean Ponce, and Minsu Cho. Spair- 71k: A large-scale benchmark for semantic correspondence. arXiv preprint arXiv:1908. 10543, 2019.
Radford M Neal and Geoffrey E Hinton, view the em algorithm that justifies incremental, sparse, and other variants. In Learning in graphical models, pp. 355-368. Springer, 1998.
A. Nowak, S. Villar, A. Bandeira, and Bruna. Revised note on learning quadratic assignment with graph neural networks. In DSW, 2018
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. 2018.
Les Piegl and Wayne Tiller. The NURBS book. Springer Science & Business Media, 2012.
Marin Vlastelica Pogancic, Anselm Paulus, Vít Musil, Georg Martius, and Michal Rolínek. Differen- tiation of black-box combinatorial solvers. In ICLR, 2020.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In ECCV, 2020.
Christian Schellewald and Christoph Schnörr. Probabilistic subgraph matching based on convex relaxation. In EMMCVPR, 2005.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. /CLR, 2014.
Paul Swoboda, Carsten Rother, Hassan Abu Alhaija, Dagmar Kainmuller, and Bogdan Savchynskyy. A study of lagrangean decompositions and dual ascent solvers for graph matching, In CVPR, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In ICLR, 2018.
Hongwei Wang. Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. Graphgan: Graph representation learning with generative adversarial nets. In AAAI, 2018.
R. Wang, J. Yan, and X. Yang. Learning combinatorial embedding networks for deep graph matching. In ICCV, 2019a.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's quadratic assigmment problem with extension to hypergraph and mulliple-graphe matching. arXiv preprint arXiv: 11 2019b.
Ronald J Williams. Simple statistical gradient- following algorithms for connectionist reinforcement learning. Machine Learning, ((3):229-256, 1992.

---

Under review as a conference paper at ICLR 2021
Hao Xiong and Junchi Yan. Btwalk: Branching tree random walk for multi-order structured network embedding. IEEE Transactions on Knowledge and Data Engineering, 2020.
Tianshu Yu, Junchi Yan, Yilin Wang. Wei Liu, et al. Generalizing graph matching beyond quadratic
assignment model. In NIPS, 2018.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with channel-independent embedding and hungarian attention. In ICLR, 2020.
A. Zanfir and C. Sminchisescu. Deep learning of graph matching. In CVPR, 2018.
Si Zhang and Hanghang Tong. Final: Fast attributed network alignment. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 1354-1354. ACM, 2016.
Zhen Zhang and Wee Sun Lee. Deep graphical feature learning for the feature matching problem. In ICCV, 2019.
Zhou and Torre. Factorized graph matching. IEEE PAMI, 2016.
A APPENDIX
A.1 HOLISTIC PIPELINE
We show the holistic pipeline of our framework in Fig. consisting of two "singleton pipelines" (see introduction part of Sec. for more details). general, the holistic pipeline follows convention in series of deep graph matching methods by utilizing an identical singleton pipeline to extract features, then exploits the produced features to perform matching (Yu et al., 2020; Wang al., 201 9a; Fey et al., 2020; Rolínek et al., 2020). Except for the topology module No, all others parts of our network are the same as those in Rolínek et al. (2020).
A.2 SPLINECNN
SplineCNN method to perform graph-based representation learning via convolution operators defined based on B-splines (Fey et al., 2018). The initial input to SplineCNN is g [X, E, A}. where X gaxd1 and A (0. 1)m indicate node features and topology, respectively (same as in Sec. 3.1). E E [0, 1jnxxxdx is so-called pseudo-coordinates and can be viewed as n² d2- dimensional edge features for a fully connected graph (in case m n²², see Sec. 3. Let normalized edge feature e(i,j) E.j. [0, 1]da if directed edge (i.j) exists (As,) 1). and 0 otherwise (At., = 0). Note topology A fully carries the information N(()) which defines the neighborhood
updated X B()
Source
Singleton pipeline
Forming affinity
Matching loss
global feature
GM solver
concatenation
global feature
Target
Singleton pipeline
updated X g()
Figure 4: Holistic pipeline of DLGM consisting of two singleton pipelines.
12

---

Under review as a conference paper at ICLR 2021
of node i. During the learning, X and E will be updated while topology A will not. Therefore SplineCNN is a geometric graph embedding method without adjusting the latent graph topology.
B-spline is employed as basic kernel in SplineCNN, where basis function has only support a specific real-valued interval (Piegl & Tiller, 2012). Let ((NV), (LLi,,)sss .... (NV ( be d2 B-spline bases with degree q. The kernel size is defined in k = (k1...,a,) ka,). In SplineCNN, the continuous kernel function gi [01, b1] x ... |ad2 682) - defined as:
(n(e) Σ "p. - (p)(e) PEP
(21)
where P (NH,)) x ... (NH,); is the B-spline bases (Piegl & Tiller, 2012) and upp is the trainable parameter corresponding to the /th node feature in X, with Bp being the product of the basis functions in P:
P II N (4)
(22)
where e is the useudo-coordinate in E. Then, given the kernel function g (9I,..., Id, and the node feature E guxds, one layer of the convolution at node in SplineCNN reads (same Eq. (3)):
d
(x (i)
Σ JEN(()
zi(i) g(e(i.)))
(23)
N(1)
where zı(j) indicates the convolved node feature value of node j at lth dimension. This formulation can be tensorized into Eq. (4) with explicit topology matrix A. In this sense, we can back propppre the gradient of A. Reader are referred to Fey et al. (2018) for more comprehensive understanding of this method.
A.3 DERIVATION OF DLGM-D
We give more details of the optimization DLGM-D in this section. This part also interprets some basic formulation conversion (e.g. from Eq. (2) to its Bayesian form). First, we assume there is no latent topology A (s) and A (s) at the current stage. In this case, the objective of GM is simply:
max II Ps 1 g(
(24)
where Pe measures the probability of a matching Zμ given graph pair gl and Gi If we impose the latent topology A (a) and A (t), as well as some distribution over them, then Eq. (24) can be equivalently expressed as:
max II
Po ZA ( max II
Po ZE.
A
(5) A
(25)
where Pe (2x1 , ((()) is the marginal distribution of Po AZR
(e) A g(o) g with respect
to Zg since A (x) and A are integrated over some distribution. Herein we can impose another
distribution of the topology (A (4) (t) glt) .g(()) characterized by parameter Φ, then we have:
log
Po
Zz
g Qa(A(A
(e) A (0 ( gg())
log
Po
ZE.
(4)
(A(A
A 10 g(e) (())
(26)
Po ZR.
=log
B ol (00
Qo(A G
2B 2B " AP999
log (2 (3)
(g()))())) g()) - log (a(A(s) (M), A Ag
13

---

Under review as a conference paper at ICLR 2021
where the final step is derived from Jensen's inequality. Since optimizating Eq. 25 is difficult, can alter to maximize the right hand side of inequality of Eq. (26) instead, which is the Evidence Lower Bound (ELBO) (Bishop, 2006). Since two input graphs are handled separately by two identical subroutines (see Fig. 2a), we can then impose the independence topology ( and ( Qo(A (+), A (0) (g))))) g( Q (A (+) (()) (9 (9)))) In this sense, we can utilize the same parameter @ to characterize two identical neural networks (generators) for modeling Q..
Assuming I is fixed, ELBO is determined by Qg. According to Jensen's 's inequality, equality of Eq. (26) holds when:
Pg
Zz. A (8)
(0)
=C c
(27)
Qo A (+) c g%
where c of 0 is a constant. We then have:
[
Po
Zz A
(+)
G g =
20 (A
(0)
A
( g .00
(28)
Al As Qo is distribution, we have:
A A
S SAPAA 2o (A())
(5)
10 -
(29)
Therefore, have:
JAP.AN
Po (Zz, Zay
A
A ( "
(30)
We now have:
Po ZR. A
g g
20 (A
A
A (1) 1 ,0(h))
(0 g6
Po
ZR.
S 10
Po
(1 (5) gf
(31)
Po
Zi.
(4) k
(0) gl c
Po
ZR 1 .9th
= =P
A
ZZ g/ g
Eq. (31) shows that, once 0 is fixed, maximizing ELBO amounts to finding a distribution Q+ approximating the posterior probability Po the generator Qs to produce latent topology given graph pair and the matching Z. This corresponds to the Inference part in Sec. 3.4.2.
[A Zz, G , _(()) This can be done by training
A.4 ABLATION STUDY
In this part, we evaluate the performance of DLGM-D and DLGM-G by selectively deactivating different loss functions (refer Sec. 3.3 for more details of the functions). We also conduct the test on DLGM-G using different sample size of the generator. This ablation test conducted on Pascal VOC dataset and average accuracy is reported in Tab. 5.
We first test the performance of both settings of DLGM by selectively activate the designated loss functions. Experimental results summarized in Tab. 5a. As matching loss LMs is essential for GM task, we constantly activate this loss for all settings. We see that the proposed novel losses Lo and L1 can consistently enhance the matching performance. Besides, DLGM-G indeed delivers better performance than DLGM-D under fair comparison.
We then test the impact of sample size from the generator Qo under DLGM-G. Experimental results are summarized in Tab. 5b. We see that along with the increasing sample size, the average accuracy ascends. The performance becomes stable when the sample size reaches over 16.
14

---

Under review as a conference paper at ICLR 2021
Table Ablation on Pascal VOC dataset. (a) Selectively deactivating loss functions Pascal VOC. LM. Le and L1 are selectively activated in DLGM-D and DLGM-G. "full" indicates all loss functions are activated. Average accuracy (%) reported. (b) Average matching accuracy under different sampling sizes from the generator Qo with "full" DLGM-G setting.
(a) On losses
(b) On sample size
method
Ave
#Sample
Ave
DLGM-D (LM + Lc)
79.8
82.5
DLGM-D (LMs
Lt.
79.5
83.2
DLGM-G (CM + Lc)
80.9
83.2
DLGM-G (Car Lt)
80.4
83.5
DLGM-D (full)
82.9
16
83.8
DLGM-G (full)
83.8
32
83.7
Class
aero & bike
bird & boat
bottle & bus
car & cat
chair cow
table & dog
horse mbike
person & plant
sheep & sofa
train & tv
Table 6: Matching examples of DLGM-G on 20 classes of Pascal VOC. The coloring of graphs and matchings follows the principle of Fig. 1 in the manuscript. Zoom for better view.
A.5 MORE VISUAL EXAMPLIES AND ANALYSIS
We show more visual examples of matchings and generated topology using DLGM-G on Pascal VOC Tab. 6 and Tab. 7, respectively. Each table follows distinct coloring regulation which will be detailed as follows:
15

---

Under review as a conference paper at ICLR 2021
Tab. 6. For each class, the left and right images corresponds to Delaunay triangulation. The image in the middle refers to the predicted matching and generated graph topology. Cyan solid and dashed lines correspond to correct and wrong matchings. respectively. Green dashed lines are the ground-truth matchings that are missed by our model.
Tab. 7. In this table, the leftmost and the rightmost columns correspond to original topology constructed using Delaunay triangulation. The two columns in the middle are the generated topology using our method given Delaunay triangulation as prior. Blue edges are the edges that Delaunay and generated ones have in common, Green edges corresponds the ones that are in Delaunay but not in generated topology, while red edges are the ones that are generated but not in Delaunay.
We give some analysis for the following questions.
In what case a different graph generated?
Since there are some generated graphs are identical to Delaunay, this question may naturally arise. We observe that, DL.GM tends to produce an identical graph to Delaunay when objects are rarely with distortion and graphs are simple (c.g. iv, bottle and plant in Tab. 6 and last two rows in Tab. 7). However, when Delaunay is not sufficient to reveal the complex geometric relation or objects are with large distortion and feature diversity (e.g. cow and cat in Tab. 6 and person in Tab. 7), DLGM will resort to generating new topology with richer and stronger hint for graph matching. other words, DLGM somewhat finds way identify if current instance pair is difficult easy to match, and learns an adaptive strategy to handle these two cases.
Why DLGM-G delivers better performance than DLGM-D?
In general, DLGM-D a deterministic gradient- based method. That is, the solution trajectory of DLGM-D almost follows the gradient direction each iteration (with some variance from mini- batch). Though it is assured to reach a local optima, only following gradient is too greedy since generated graph is coupled with predicted matching. Besides, the topology is discrete, the optimal continuous solution will have a large objective score gap to its nearest discrete sampled solution once the landspace of the neural network too sharp. On the other hand, DLGM-G performs discrete sampling under feasible graph distribution at each iteration, which generally but not fully follows the gradient direction. This procedure can thus find better discrete direction with probability, hence better exploring the searching space. This behavior is similar to Reinforcement Learning, but with much higher efficiency. Additionally, EM framework can guarantee the convergence (Bishop, 2006).
16

---

Under review as a conference paper at ICLR 2021
Delaunay
Generated
Generated 2
Delaunay 2
Table 7: Generated topology compared with original Delaunay triangulation in a pairwise fashion. Note the sst and the 4th columns correspond to two input images with topology constructed by Delaunay triangulation, respectively. 2nd and 3rd columns are the generated topology given Delaunay results as prior.
17


Reviews:
[{"review_id": "TNvAz1iDek", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors address the problem of discrete keypoint matching. For an input pair of images, the task is to match the unannotated (but given as part of the input) keypoints. The main contribution is identifying the bottleneck of the current SOTA algorithm: a fixed connectivity construction given by Delauney triangulation. By replacing this with an end-to-end learnable algorithm, they outperform SOTA with a decent margin.\n\nContribution & significance: The topic of discrete keypoint matching has had a lot of progress in the last five years and is gaining attention even from more product-oriented branches of computer vision. The benchmarks used for evaluation (PASCAL-VOC, SPair71k) are, in fact, quite difficult, and even 2-3 points of progress require non-trivial effort. The core insight of improving this particular part of the pipeline is creative and novel. In these regards, the paper certainly meets the bar set for ICLR.\n\nExperiments are conducted thoroughly and on multiple standard datasets. I appreciate the ablation study. Minor suggestions are below.\n\nWeaknesses:\n\n1) **Code**  For a mostly experimental paper, it is imperative to release code (as is also common in the line of work for keypoint matching). If the code was already uploaded, I would have given the paper a higher rating.\n\n2) **Co-generative model** The authors for some reason insist on this interpretation of their architecture (it appears in boldface in the abstract). In practical terms, it means that a) one term of the loss function doesn't depend on ground truth b) a reparametrization trick is used. I do not think, this justifies making the co-generative a central point of the paper. In my eyes, it would simply help the paper if these remarks were removed.\n\n3) **Relevance for wider ICLR community** Given the very specialized domain, the work would perhaps be a better fit for a conference fully focused on computer vision. Note that e.g. (Fey, ICLR 2020) included also NLP experiments and made a more general point about matching procedures. I am afraid that in the current form, this paper won't attract too wide ICLR audiences. Is there a way to demonstrate/make-a-plausible-case-for wider applicability?\n\n4) **At times unclear writeup** It wasn't always easy to understand what exactly the authors mean. Both in natural language and in technical parts. In the technical parts, the authors use very heavy notation and produce multiple large formulas that on the other have very standard content (e.g.. eq 11 and 14). On a technical level, the tools applied to introducing differentiability are very standard.  But that is absolutely fine since the core contribution is **where** they are applied.  There is no need to \"produce enough formulas\" such as by rewriting standard ELBO arguments over much larger notation (as it is in Appendix A3).\n\n5) **Qualitative analysis** This is a missed opportunity. High-quality images that clearly demonstrate where the advantage is coming from, could easily be a highlight of this paper and should certianly be present in the main text. The current analysis in the supplementary is quite short and the displayed images are tiny, very hard to understand and **in almost all cases do NOT show the difference between the baseline and the proposed method.** I can't stress enough how instructive it would be to insert a section where eg. only examples of tables are analyzed (since that's the class with maximum gain) and one can clearly see what the architecture does differently (without zooming to 400%). Some parts of the technical presentation could be shortened.\n\nMinor remarks follow:\n- line 4 - footnote: It only is without loss of generality when negative costs are allowed, otherwise the argmax is always a maximal matching and outliers are not ignored.\n- line 4 (LaTeX): This symbol for real numbers is very non-standard\n- Figure 1 is hard to navigate. I suggest just focusing on the topology and dropping the matchings.\n- page 3 - summation itself is undifferentiable - this is more misleading than anything. The point of this section is that one can introduce soft edges instead of the hard edges.\n- page 4 - consistency loss - This needs an example or a figure for an explanation.\n- page 4 - with full linearization (Swoboda, 2007) - This work doesn't linearize anything as far as I know. It is a SOTA combinatorial QAP solver based on message passing and dual ascent.\n- Eq 11, I don't see any reason to include this. it is just a trivial factorization with heavy notation.\n- Page 7, Figure 3 has poor visual quality and a very tiny font.", "extra_scores": {}, "extra_text": {}}, {"review_id": "S81_iY_ENp", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors propose a method for what they call Graph Matching, where the main contribution is to learn the connectivity matrix A, given the input features, and jointly learn the matching.\n\nThe paper is well written in general, and the contributions are clear. There are some \".\" and \",\" missing after equations.\n\nThis may be a matter of taste, but to me, graph matching (or the graph matching problem) refers to the problem of, given two graphs, finding the bijection between the set of vertices that minimices some distance. Usually, if A and B are the adjacency matrices of the two graphs, one tries to minimize $\\|A-PBP^T\\|_F$, over the set of permutation matrices.\n\nAdding features to the vertices is a first extension of this problem, which I still consider a graph matching problem.\nNow, if in the problem the inputs are a set of points in $\\mathbb{R}^d$ and some features, and as part of the solution, one infers a possible adjacency matrix (or topology, as in the paper), then for me the term graph matching is misleading.\n\nUnfortunately, I have no expertise in this latter problem, and therefore I just can say that the formulation seems correct, and the numerical results are promising.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PlMNDcR9bz8", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors argue that standalone representation learning is insufficient for the Graph Matching task and propose multiple novel approaches to address this via using a latent graph topology instead of a fixed one. Empirical results demonstrate the efficacy of their approach.\n\nI was not completely convinced by the arguments made by the authors and their motivation. Overall the paper felt a little heuristic in nature and the presentation made it difficult to follow. Here are the major aspects which were unclear to me (refer below).\n\n1) What is the primary motivation for the authors ? Why do the authors think using a latent graph topology is in general better than using a fixed topology ? Is it always true that using a fixed topology is undesirable or only in some cases only ? Some arguments/examples from the authors which can validate this using real-world settings would have helped. Irrespective of Graph Matching problem, Social Networks can be a good application for verifying this. Fake (due to noise) and real edges in connections/friendship network would be a good indicator for the authors' intuition i.e. the latent topology should be able to filter out the fake edges.\n\n2) With regards to eqn. 1, is the condition Hz = 1 enough to ensure that each row and column sums to 1 ?\n\n3) Why did the authors only consider absolute/boolean assignments (0/1) in the paper rather than partial assignments which can be more flexible i.e. soft assignments (0 <= z_i <= 1) such that each row and column sums to 1 ? Is there some specific reason for this ?\n\n4) In section 2.4.1, the authors propose to use the straight-through operator for their rounding task. Did the authors try any other approaches ? How did the bias of the straight-through operator hamper their final optimization solution and by how much ?\n\n5) With regards to eqn. 15 wherein the authors use an independence assumption, how much did the accuracy of their estimation suffer as a result to this quantitatively ?\n\n6) The authors also mention that their deterministic learning approach is often more efficient while the generative learning method can be more accurate at the cost of additional overhead. Do the authors have results with regards to this overhead ? How significant is it and how does it compare to time complexity of the other state-of-the-art methods ? This is even more relevant given for many of the results, the improvement is only marginal compared to other competitors.\n\n7) Based of the results, can the authors claim that improvement in the results over other competitors is due to the efficacy of their approach and the factuality of their arguments ? Could it be due to richness/complexity of their model/learning strategy ? \n\n8) What do the authors mean by \"normalized connectivity\" in section 2.1 ? Does it mean the augmented Adjacency matrix which contains self loops i.e. A_tilde = A + I ? \n\n9) Given the authors in their approach model the adjacency matrix, thus how does the authors' approach compare against traditional graph based modeling techniques i.e. Stochastic Block Model and Erdős–Rényi model for instance ? \n\nI would appreciate it if the authors made their code available for review/reproducing results. Additionally I felt the paper needed more analysis/discussion. Overall the presentation of the paper needs to improve significantly. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "8AT9PBpvXw", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper deals with graph matching, where the latent topology of the two graphs is not fixed but estimated during the learning process.\n\nThe authors propose two algorithms, namely deterministic learning and generative learning, which both achieve state-of-the-art accuracy scores on several datasets.\n\nI think that the approach developed in this paper can be of interest but its presentation makes it difficult to follow and understand.\n\n\nFirst, it is implicit in the first part of the paper that it deals with topologies obtained from images.\nThe authors should explain what the graph topology models in the image and how it is obtained in the literature. They mention algorithm names (Delaunay triangulation and k-nearest neighbors, section 1), and that the construction is heuristic (page 3), but do not provide any clue on the (formal) definition of the topology. (I recall that the paper deals with estimation of the graph topology.)\n\n\nIn section 2, it is proposed to estimate both the topologies of the two graphs and their matching. In my opinion, the problem is not defined in a sufficient formal way so that the reader can exactly understand the rationale behind the methods.\nI also think that, at this stage, the connection with how the topology is initially estimated in the literature would both help the reader to understand the optimization problem at stake, and highlight the originality of this piece of work.\n\nI have the following (naive) question: isn't the optimal topology the one that does not allow any edges in the graph, since it should allow the greatest flexibility in the matching of the nodes? Of course, this solution is not of interest for the applications, but I do not see why it is excluded from the investigated approach.\n\n\nThe authors claim that optimizing eq. (13) is intractable and thus choose to maximize a lower bound through an EM-like algorithm. However, they do not prove the relation with the initial optimization problem. As is usually the case, does it allow for local optimization of (13)?\n\n\nIn the real data analysis, the methods are compared through their accuracy scores and not on the estimation of the latent topology. Of course, it is irrelevant at this place since the other algorithms do not estimate it. Nevertheless, it should be interesting to have a quantitative analysis of this output of the algorithm.\n\n\nFor all of these reasons, I think that this paper deserves to be significantly improved before being published.\n\n\nMore comments and questions:\n\n+ The reader can not read and understand Figure 1 given on page 2 without reading the paper until page 7.\n\n+ What is the normalized connectivity (page 3)?\n\n+ The authors mention twice in the paper that there is only little work on \"exploring graph topology learning / generation for deep graph matching\" (introduction and conclusion) without any references explicitly related to this sentence. Are there papers that deal with the same strategy? I believe that the article should be clearer on that point. On this topic, I also think that the structure of the paper should be revised, with the section dedicated to related works (section 4) presented earlier.\n\n+ The qualitative analysis presented in Appendix A.5 is very interesting and should be presented in the main document.\n\n\nTypos:\nPage 5: which in intractable\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6xPML3UEa9W", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper discusses the problem of graph matching (GM), which is the combinatorial (NP-hard) problem of finding a similarity between graphs, and has various applications in machine learning. More specifically, the paper proposes methods to leverage the power of deep networks to come up with an end-to-end framework that jointly learns a latent graph topology and perform GM, which they term as deep latent graph matching (DLGM).\n\nStrengths: The proposed method seems justified. The authors both explore a novel direction for GM by actively learning latent topology.  They further propose both a deterministic optimization-based approach a generative way to learn effective graph topology for matching. Regarding the empirical results of the paper, the authors report that their methods achieve state-of-the-art performance on public benchmarks, in comparison against a few peer methods (in measures of both accuracy and F1-score). \n Other than that, their claims appear to be correct, and so is the empirical methodology. Relation to prior work and differences are discussed.\n\nWeaknesses/Comments: The paper was very difficult to follow (maybe it is due to the fact that I am not highly familiar with part of the field.  Nevertheless, I think that the organization of the paper can be improved).  I think there is a missing word in the second last sentence on page 2: For notational brevity, we assume d1 and d2 keep the same across convolutional\nlayers. Same dimensions maybe?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an interesting take on Graph Matching by posing the problem as learning the Topology through Graph Convolutional Networks.  There is consensus that the methods proposed are new but the impact is not clear.
One major point against the paper seems to be that Code is yet to be released.
Decision: Reject