Deep Graph Matching Consensus
Authors: Matthias Fey
Jan E. Lenssen
Christopher Morris
Jonathan Masci
Nils M. Kriege
Venue:  (2020)
Keywords: graph matching
graph neural networks
neighborhood consensus
deep learning

Abstract: This work presents a two-stage neural architecture for learning and refining structural correspondences between graphs. First, we use localized node embeddings computed by a graph neural network to obtain an initial ranking of soft correspondences between nodes. Secondly, we employ synchronous message passing networks to iteratively re-rank the soft correspondences to reach a matching consensus in local neighborhoods between graphs. We show, theoretically and empirically, that our message passing scheme computes a well-founded measure of consensus for corresponding neighborhoods, which is then used to guide the iterative re-ranking process. Our purely local and sparsity-aware architecture scales well to large, real-world inputs while still being able to recover global correspondences consistently. We demonstrate the practical effectiveness of our method on real-world tasks from the fields of computer vision and entity alignment between knowledge graphs, on which we improve upon the current state-of-the-art.

Published as a conference paper at ICLR 2020
DEEP GRAPH MATCHING CONSENSUS
Matthias Fey!.3 Jan E. Lenssen 1:4 Christopher Morris Jonathan Masci Nils M. Kriege'
'TU Dortmund University Dortmund, Germany
NNAISENSE
Lugano, Switzerland
ABSTRACT
This work presents a two-stage neural architecture for learning and refining struc- tural correspondences between graphs. First, we use localized node embeddings computed by a graph neural network to obtain an initial ranking of soft corre- spondences between nodes. Secondly, networks to iteratively re-rank the soft correspondences to reach a matching con- sensus in local neighborhoods between graphs. We show, theoretically and em- pirically, that our message passing scheme computes a well-founded measure of consensus for corresponding neighborhoods, which is then used to guide the iter- ative re-ranking process. Our purely local and sparsity-aware architecture scales well large, real-world inputs while still being able recover global correspon- dences consistently. We demonstrate the practical effectiveness of our method on real-world tasks from the fields of computer vision and entity alignment be- tween knowledge graphs, on which we improve upon the current state-of-the the art. Our source code available under https:: pestps://giaee thub. com/ rustylss deep graph mat ching consensus
employ synchronous message passing
INTRODUCTION
Graph matching refers to the problem of establishing meaningful structural correspondences of nodes between two or more graphs by taking both node similarities and pairwise edge similarities into account (Wang et al., (019b). Since graphs are natural representations for encoding relational data, the problem of graph matching lies at the heart of many real-world applications. For exam- ple, comparing molecules in cheminformatics (Kriege et al. 2019b), matching protein networks in bioinformaties (Sharan & Ideker 2006 Singh et al. 2008), linking accounts in social net- work analysis (Zhang & Philip 20155, ) and tracking objects, matching 2D/3D shapes or recognizing actions in computer vision (Vento& & Foggia 2012) be formulated graph matching problem.
The problem of graph matching has been heavily investigated in theory (Grohe et al., 2018) and practice (Conte al. (2004). usually by relating it to domain aagain-agnostic distances such the graph edit distance (Stauffer et al. (017)) and the maximum common subgraph problem (Bunke & Shearer) 1998), or by formulating it as quadratic assignment problem (Yan et al.) 2016). Since all three ap- proaches are NP-hard, solving them to optimality may not be tractable for large-scale, real-world instances. Moreover, these purely combinatorial approaches do not adapt the given data distribu- tion and often do not consider continuous node embeddings which can provide crucial information about node semantics.
Recently, various neural architectures have been proposed to tackle the task of graph matching (Zanfir & Sminchisescu 2018 Wang al. 2019b] Zhang Lee 2019 Xu et al.) 2019d by [Der et al. 2019, Zhang et al. 2219a] Heimann et al. 2018) graph similarity (Bai et al.) 2018 2019 Li et al., 2019) in a data-dependent fashion. However, these approaches are either only capable of computing similarity scores between whole graphs (Bai et al. 2018 2019: [Li et al.] 2019), rely
on an inefficient global matching procedure (Zanfir& & Sminchisescu, 2018 8 Wang et al. 2019b Xu
ct al. 2019d Li al. 2019), do not generalize to unseen graphs (Xu et al. 2019b Derr et al.] 2019
Zhang et al. 2019a). Moreover, they might be prone to match neighborhoods between graphs
CCorrespnndence to matthiiin ias. fey@udo edu Work done during an intersship NNATSENSE

---

Published as a conference paper at ICLR 2020
inconsistently by only taking localized embeddings into account (Zanfir & Sminchisescu 2018 Wang et al. 2019b Zhang
Lee 2019 Xu et al. 2019d: Derr et al. 2019; Heimann et al. 2018).
Here, propose fullyydiifereenttabl graph matching procedure which aims to reach data-driven neighborhood consensus between matched node pairs without the need to solve any optimization problem during inference. In addition, approach is purely local, i.e., it operates neighborhoods around nodes, and is sparsity-aware, i.e., it takes the sparsity of the underlying struc- tures into account. Hence, our approach scales well to large input domains, and can be trained in an end-to-end fashion to adapt to a given data distribution. Finally, our approach improves upon the state-of-the-an on several real-world applications from the fields of computer vision and entity alignment on knowledge graphs
fixed-size
2 PROBLEM DEFINITION
graph 9 = (V. A, E) consists of a finite set of nodes V ... an adjacency matrix A E {0, 13 M a node feature matrix X E IR v|x. and an optional (sparse) edge feature matrix E E RIVXXVIX For subset of nodes S C V. G[S] = (S, As.s. Xs.: Es.s.) denotes the subgraph of induced by S. We refer to (i) = {j E V: d(i s } as the T-hop neighborhood around node i E V. where d: V x V - N denotes the shortest-path distance in G. A node coloring a function + Σ with arbitrary codomain E.
The problem of graph matching refers to establishing node correspondences between two graphs. Formally, we are given two graphs. a source graph 9, = (V., A., X., E.) and a target gruph G. = (V,, A,, X., Ex), w.l.o.g. [Va| I [V.), and are interested in finding a correspondence malrix S 10 1V. which minimizes an objective subject the one-to-one mapping constraints Ejer, Sig 11 Vi E V. and Liev, St.j < Vj E V.. As result, S infers an injective mapping T: V. + V/ which maps each node in G, to node in Gr-
Typically, graph matching is formulated an edge-preserving, quadratic assignment problem Anstreicher 2003 Gold & Rangarajan 1996 Caetano et al. 2009 Cho et al. 2013), ie.,
Σ tr'v, ie'EV.
4 St
argmax S
subject to the one-to-one mapping constraints mentioned above. This formulation is based on the intuition of finding correspondences based on neighborhood consensus (Rocco al. 2018), which shall prevent adjacent nodes in the source graph from being mapped to different regions in the target graph. Formally, neighborhood consensus is reached if for all node pairs (i, V. V. with Sk = 1, it holds that for every node i' ( there exists a node j' E (J) such that S = 1.
In this work, consider the problem of supervised and semi-supervised matching of graphs while employing the intuition of neighborhood consensus as an inductive bias into our model. In the supervised setting, we are given pair-wise ground-truth correspondences for set of graphs and want our model to generalize to unseen graph pairs. In the semi-supervised setting, source and target graphs are fixed, and ground-truth correspondences are only given for a small subset of nodes. However, we are allowed to make use of the complete graph structures.
3 METHODOLOGY
In the following, we describe our proposed end-to-end, deep graph matching architecture in de- tail. See Figure for a high-level illustration. The method consists of two stages: local feature matching procedure followed by an iterative refinement strategy using synchronous message passing networks. The aim of the feature matching step, see Section 3.1 is to compute initial correspondence scores based on the similarity of local node embeddings. The second step is an iterative refinement strategy, see Sections 3.2 and (.33 which aims reach neighborhood consensus for correspondences using a differentiable validator for graph isomorphism. Finally, in Section 3.4 we show how to scale
method to large, real-world inputs.
2

---

Published as a conference paper at ICLR 2020
les
Iul.
Va.
V
g
Stage
Stage
4Pps
S
f.l,
Tull
St
Vo
02
Figure 1: High-level illustration of our two-stage neighborhood consensus architecture. Node fea- tures are first locally matched based on graph neural network o before their correspondence scores get iteratively refined based neighborhood consensus. Here, an injective node coloring of 9s is transferred to G, via S, and distributed by 0g on both graphs. Updates on S are performed by neural network &8g based on pair-wise color differences.
3.1 LOCAL FEATURE MATCHING
We model our local feature matching procedure in close analogy related approaches (Bai et al. 2018 2019) Wang et al., 2019b) Zhang & Lee 2019; Wang & Solomon, 2019) by com- puting similarities between nodes in the source graph Ge and the target graph G. based on node embeddings. That is, given latent node embeddings H. Lo (X., s. A,, E.) R and
H. Ve, (X,, Ar, E,) RIV.xx computed by shared neural network Ve, for source graph G. and target graph G., respectively, we obtain initial soft correspondences as
( sinkhorn (5()) E [0, 1V. with S H,H, RIVIIIM
Here, sinkhorn normalization is applied obtain rectangular Houbly-stochaste correspondence matrices that fulfill the constraints Liey. Sig 1 Vi V, and Eiev, S1 I 1ij V. Sinkhorn
& Knopp 1967 Adams & Zemei 2011 Cour et al. 2006).
a discrete distribution over potential correspon- dences in G. for each node i E V. We train Le, in dicriminative, supervised fashion against ground truth correspondences gi (-) by minimizing the negative log- ligeliill of correct correspon- dence scores L (imitial) - EiEv, log(s(() (t))))))))
We interpret the i-th row vector ((0) E [0, 1
We implement Le as Graph Neural Network (GNN) to obtain localized, permutation equivariant vectorial node representations (Bronstein et al. 2017 Hamilton et al. 2017: Battaglia et al.] 2018 Goyal & Ferrara 2018). Formally, a GNN follows a neural message passing scheme (Gilmer et al. 2017 and updates its node features fi
((t-1) in layer é by aggregating localized information via
a
AGGREGATE
( (T (M) .eg..) : EM())) R((0 (PDATE ( (T]
(T((-1)
(2)
where = E X and & denotes a multiset. The recent work the fields of geometric deep learning and relational representation learning provides a large number of operators choose from (Kipf & Welling 2017 Gilmer et al., 20177] Veličković et al. 2018:; Schlichtkrull et al. 2018
Xu et 2019c). which allows for precise control of the properties of extracted features.
3.2 SYNCHRONOUS MESSAGE PASSING FOR NEIGHBORHOOD CONSENSUS
Due to the purely local nature of the used node embeddings, feature matching procedure is prone to finding false correspondences which are locally similar to the correct one. Formally, those cases pose violation of the neighborhood consensus criteria employed in Equation (T). Since finding
3

---

Published as a conference paper at ICLR 2020
global optimum is NP-hard, we aim to detect violations of the criteria in local neighborhoods and resolve them in an iterative fashion.
We utilize graph neural networks to detect these violations in neighborhood consensus step and iteratively refine correspondences S E {O...., L}, starting from ( Key to the proposed
algorithm is the following observation: The soft correspondence matrix E [o. [0.1] 1 is map from the node function space L(g,) L [(R(Va)) to the node function space L(G,) L(R())). Therefore, we can use S to pass node functions x. E L(gs), Iz E L(ge) along the soft correspon- dences by
= Zs and L =
to obtain functions मt LGG.) 32. E ((g.) in the other domain, respectively.
Then, our consensus method works as follows: Using S we first map node indicator functions, given as an injective node coloring V. - {0, Vol in the form of an identity matrix [ from G, to Gs. Then, distribute this coloring in corresponding neighborhoods by performing synchronous message passing on both graphs via a shared graph neural network L B2. i.e.,
O₂ = 1z [1)]: As, E.) and O2 = -Vo (1 |v. A., E.).
(4)
We can compare the results of both GNNs to recover a vector di, = 0. - which measures the neighborhood consensus between node pairs (i,j) E V, x Ve. This measure can be used to perform trainable updates of the correspondence scores
Sij
s((+1) sinkhorn( (Sthoor(((**)))) Aa with 5.j = $10 + 08 (cT..)
-
(5)
based on an MLP &0. The process can be applied L times to iteratively improve the consensus in neighborhoods. The final objective C = ((mittia)) + [ ((reiined) with L (relinned)
Eiev, log(s(()) (6))
combines both the feature matching error and neighborhood consensus error. This objective is fully- differentiable and can hence be optimized in an end-to-end fashion using stochastic gradient de- scent. Overall, the consensus stage distributes global node colorings to resolve ambiguities and false matchings made in the first stage of our architecture by only using purely local operators. Since an initial matching is needed to test for neighborhood consensus, this task cannot be fulfilled by Ve, alone, which stresses the importance of our two-stage approach.
The following two theorems show that dr.s is a good measure of how well local neighhorhoods around and j are matched by the soft correspondence between G. and G. The proofs can be found in Appendix B [] respectively.
Theorem 1. Let Go and Gi be two isomorphic graphs and let Ms, be a permutation equivariant GNN, i.e., PT V (X, A) = Vo, P.PTA AP) for any permutation matrix P E {0. 13 1 S E {0, 13 (3.131V.187 12.1111/V encodes an isomorphism between Is and Gt, then di,m(()) = for all i E V.. Theorem 2. Let Gs and G, be two graphs and let o2 be a permulation equivariant and T-aayered GNN for which both (GGREGATE( and (PDATE(() are injective for all (1....,,): If J = ō. x(Nr(5) then the resulting submatrix (N)()) E [0, ( is a permutation matrix describing an isomorphism between the T T-hop subgraph (.) around E V, and the T T-hop subgraph Gi)) around j V,. Moreover, if di S... Ô for all Va, then S denotes a full isomorphism between Ge and Gr-
Hence, a GNN Lo that satisfies both criteria in Theorem I and provides equal node embeddings a((*) and 0,61) if and only if nodes in a local neighborhood are correctly matched to each other. A value di, * Ö indicates the existence of inconsistent matchings in the local neighborhoods around i and j. and can hence be used to refine the correspondence score S..j-
Note that both requirements, permutation equivariance and injectivity, are easily fulfilled: (1) All common graph neural network architectures following the message passing scheme of Equation @ are equivariant due to the use of permutation invariant neighborhood aggregators. (2) Injectivity of graph neural networks is a heavily discussed topic in recent literature. It can be fulfilled by using a GNN that is as powerful as the Weisfeiler & Lehman (1968) (WL) heuristic in distinguishing graph structures, e.g., by using sum aggregation in combination with MLPs on the multiset of neighboring node features, of. (Xu et al. 2019c Morris al. 2019)
4

---

Published as a conference paper at ICLR 2020
3.3 RELATION TO THE GRADUATED ASSIGNMENT ALGORITHM
Theoretically, relate our proposed approach to classical graph matching techniques that sider a doubly-stochastic relaxation of the problem defined in Equation (T). of. (Lyzinski et al.) 2016) and Appendix | for more details. seminal work following this method is the graduated as- signment algorithm (Gold & Rangarajan 1996). By starting from an initial feasible solution S new solution S(I+1) is iteratively computed from (()) by approximately solving linear assignment problem according to
S(L+1) f softassign Σ Sis with Qu 1949 JEV.
(6)
S
V'E.
where Q denotes the gradient of Equation T at S The softassign operator is implemented by applying sinkhorn normalization on rescaled inputs, where the scaling factor grows every itera- tion to increasingly encourage integer solutions. Our approach also resembles the approximation of the linear assignment problem via sinkhorn normalization.
Moreover, the gradient Q is closely related to our neighborhood consensus scheme for the particular simple, non- trainable GNN instantiation (XX, A,
AX. Given O, A, = A, and O₂ = A,S 14, = A,ST, we obtain Q 20,0, by substitution. Instead of updating s()) based on the similarity between O₂ and O obtained from a fixed-function GNN V, we choose to update correspondence scores via trainable neural networks Lo and oo based on the difference between O, and O.. This allows us to interpret our model as deep parameterized generalization of the graduated assignment algorithm. In addition, specifying node and edge attribute similarities in graph matching often difficult and complicates its computation (Zhou De la Torre 2016 Zhang al. (019c)) whereas our approach naturally supports continuous node and edge features via established GNN models. We experimentally verify the benefits of using trainable neural networks Le instead of L X, A, E) AX in Appendix D
3.4 SCALING TO LARGE INPUT
We apply number of optimizations to our proposed algorithm to make it scale to large input do- mains. See Algorithm| Tin in Appendix A for the final optimized algorithm.
Sparse correspondences. We propose to sparsify initial correspondences St by filtering out low score correspondences before neighborhood consensus takes place. That is, we sparsify ( by computing top k correspondences with the help of the KEOPS library (Charlier et al. 2019) without
ever storing its dense version, reducing its required memory footprint from O to (kl).... In addition, the time complexity of the refinement phase is reduced from O(V + & to ( V. | + |E,] + (El)). where |&| and && denote the number of edges in 9, and G. respectively. Note that sparsifying initial correspondences assumes that the feature matching procedure ranks the correct correspondence within the top is elements for each node E V.- Hence, also optimizing the initial feature matching loss [ (ininal) is crucial, and can be further accelerated by training only (5 against sparsified correspondences with ground -tuth entries (S 1, (S
Replacing node indicators functions. Although applying Ve, on node indicator functions Ipy is computationally efficient, it requires a parameter complexity of O(VVI). Hence, we propose to replace node indicator functions I|v,] with randomly drawn node functions R.O (O 1),
where R R V.lxe with < [1sl. in iteration i. By sampling from a continuous distribution, node indicator functions are still guaranteed to be injective (DeGroot & Schervish] 2012). Note that Theorem still holds because it does not impose any restrictions the function space L(G.). Theorem does not necessarily hold anymore, but we expect our refinement strategy to resolve any ambiguities by re-sampling R. in every iteration I. We verify this empirically in Section 4.1
For clarity of presentation, we closely follow the original formulation of the method for simple graphs hut ignore the edge similarities and adapt the constant factor of the gradient according our objective function.
5

---

Published as a conference paper at ICLR 2020
Softmax normalization. The sinkhorn normalization fulfills the requirements of rectangular doubly-stochastic solutions. However, may eventually push correspondences to inconsistent in- teger solutions very early from which the neighborhood consensus method cannot effectively recover. Furthermore, is inherently inefficient to compute and runs the risk of vanishing gradi- ents a5(0))0000 /05()) (Zhang et al., 2019b). Here, we propose to relax this constraint by only applying row-wise softmax normalization on S(O,, and expect our supervised refinement procedure to nat- urally resolve violations of Eiev, S.g, S on its own by re-ranking false correspondences via neighborhood consensus. Experimentally. we show that row-wise normalization is sufficient for our algorithm to converge to the correct solution, cf. Section 4.1
Number of refinement iterations. Instead of holding L fixed, we propose differ the number of refinement iterations L (trin) and ( (tmin)) < L [less), for training and testing, respectively. This does not only speed up training runtime, but it also encourages the refinement procedure to reach convergence with as few steps as necessary while we can run the refinement procedure until conver- gence during testing. We show empirically that decreasing (ttrann)) does not affect the convergence abilities of our neighborhood consensus procedure during testing, cf. Section 4.1
4 EXPERIMENTS
We verify our method on three different tasks. We first show the benefits of our approach in an abla- tion study synthetic graphs (Section 4.1) and apply it to the real-world tasks of supervised key-
point matching in natural images (Sections 4.2 and 4.3) and semi-supervised cross-lingual knowl-
edge graph alignment (Section 4.4) afterwards. All dataset statisties can be found in Appendix [H]
Our method is implemented in PYTORCH (Paszke et al. 2017) using the PYTORCH GEOMETRIC (Fey & Lenssen 2019) and the KEOPS (Charlier al. 2019) libraries. Our implementation can process sparse mini-batches with parallel GPU acceleration and minimal memory footprint in all algorithm steps. For all experiments, optimization done via ADAM (Kingma Ba 2015) with a fixed learning rate of 10-3, We use similar architectures for Ve, and Va, except that we omit dropout (Srivastava et al. (014)) in L For all experiments, we report Hits @ evaluate and compare our model to previous lines of work, where Hits k measures the proportion of correctly matched entities ranked in the top k.
4.1 ABLATION STUDY ON SYNTHETIC GRAPHS
In our first experiment, we evaluate our method on synthetic graphs where we aim to learn a match- ing for pairs of graphs in a supervised fashion. Each pair of graphs consists of an undirected Erdös & Rényi (1959) graph G, with [Val {50, 100} nodes and edge probability target graph G. which is constructed from G. by removing edges with probability p. without dis- connecting any nodes (Heimann et al. 20.8). Training and evaluation is done on 1 000 graphs each
(0.1,0.27 and
for different configurations ps E {0.0. 0.1, 0.2, 0.3, 0.4, 0.5). In Appendix F we perform additional experiments to also verify the robustness of our approach towards node addition or removal.
Architecture and parameters. We implement the graph neural network operators Vo and Vo. by stacking three layers (I' 3) of the GIN operator (Xu et al. 2019c)
h 1(++) MLP(++1)
Rio +
(
due to its expressiveness in distinguishing raw graph structures. The number of layers and hidden dimensionality of all MLPs is set to 2 and 32, respectively, and apply ReLU activation (Glorot et al. 2011) and Batch normalization (loffe & Szegedy 2015) after each of its layers. Input features initialized with one-hot encodings of node degrees. We employ Jumping Knowledge style concatenation h = w ,...,,y 7((7) Xu et al.
2018 to compute final node representations hT, We train and test our procedure with 7. ((trmm)) 10 and 7, T,lstt) 20 refinement iterations, respectively.
Results. Figures 2(a) and 2(b) show the matching accuracy Hits@| for different choices of [V.] and p. We observe that the purely local matching approach via max ($(0)) starts decreasing in

---

Published as a conference paper at ICLR 2020
softmaxx (())
sinkhoru(S
sinkhoru
softmax ((4)
softmax((oop
100
Erro L (refined)
0.1
Hits@8 (96
Hits (96
012
Hit 1 [k (9%
0.5
60
60
1.5
0.4
0.6
01
0
6.0
P.
10
30
50
0
10
21
30
40
50
20
30
30
10
50
Structural
Pa
(%)
Structural noise P. (%)
Ieraaionn L (test)
Top; correspondences
(a) [V]] 50, p 0.2
(b)
[2] 100, p 0.1
(c) [V]]
100, p 0.1
(d) [2]]
100, 0.1
Figure 2: The performance of our method synthetic data with structural noise.
performance with the structural noise Ps increasing. This also holds when applying global sinkhorn normalization on S(0)_ However, our proposed two-stage architecture can recover all correspon- dences, independent of the applied structural noise p.. This applies to both variants discussed in the previous sections, i.e., our initial formulation sinkhorn( (S(1.). and our optimized architecture using random node indicator sampling and row-wise normalization softmax(5 (S()). This highlights the overall benefits of applying matching consensus and justifies the usage of the enhancements made towards scalability Section 3.4.
In addition, Figure 2(c) visualizes the test error L (refined) for varying number of iterations (tes), We observe that even when training to coneeenverg,,ce, our procedure is still able converge by increasing the number of iterations (test))) during testing.
Moreover, Figure 2(d) shows the performance of our refinement strategy when operating on spar- sified top h correspondences. In contrast to its dense version, it cannot match all nodes correctly due to the poor initial feature matching quality. However, consistently converges to the perfect solution of Hits@I z Hits k in case the correct match is included in the initial top k ranking of correspondences. Hence, with increasing k. we can recover most of the correct correspondences, making it an excellent option to scale algorithm to large graphs, cf. Section 4.4
4.2 SUPERVISED KEYPOINT MATCHING NATURAL IMAGES
We perform experiments on the PASCALVOC Everingham et al. 2010) with Berkeley annotations (Bourdev Malik 2009) and WILLOO-OBBJCCTCC
(Cho et al. 2013) datasets which contain sets of image categories with labeled keypoint locations. For PASCALVOC. we follow the exper- imental setups Zanfir & Sminchisescu (2018) and Wang al. (2019h) and use the training and test splits provided by Choy et al. (2016). We pre-filter the dataset exclude difficult, occluded and truncated objects, and require examples to have least one keypoint, resulting in 6 953 and 1 671 annotated images for training and testing, respectively. The PASCALVOC dataset contains instances of varying scale, pose and illumination, and the number of keypoints ranges from 1 to 19. In contrast, the WILLOW-OBECTCLAN orientations for each of its five categories, and each image consists of exactly 10 keypoints. Fol- lowing the experimental setup of peer methods (Cho al. 2013 Wang et al. 2019b). we pre-train our model on PASCALVOC and fine-tune it over 20 random splits with 20 per-class images used for training. We construct graphs via the Delaunay triangulation of keypoints. For fair comparison with Zanfir & Sminchisescu (2018) and Wang et al. (2019b), input features of keypoints are given by the concatenated output re relu4. 2014) IMAGENET (Deng et al. 2009).
dataset contains least 40 images with consistent
relu5_ of pre-trained VGG16 (Simonyan & Zisserman,
Architecture and parameters. network operator
We adopt SPLINECNN (Fey et al. 2018 as our graph neural
((++)) o [ 1 1 (G,)) (00
whose trainable B-spline based kernel function (-) is conditioned on edge features ε, between node-pairs. To align results with the related work, evaluate both isotropic and anisotropic

---

Published as a conference paper at ICLR 2020
Table I: Hits @1 1 (%) on the PASCALVOC dataset with Berkeley keypoint annotations.
Method
Acro Bike Bird Bost Bottlc Bus
Car
Cat Chair Cow
Table
Dog
Horse
M-Bike Person
Plant Sheep
Safa
Train
TV Mean
58.2
70.6
76.5
53.7
58,9
57.5
56.9
49.3
PCA-GM
40.9
55.0
65.8
47.9
76.9
77.9
63.5
67.4
33.7
66.5
63.6
61.3
58.9
62.8
44,9
77.5
67.4
57.5
W6.7
90,9
63.8
MLP
0
45.8
34.7
42.6
58.2
41.5
45.5
57.6
50.4
68.2
50.3
72.2
82.1
60.1
15.3
99.4
24.6
31.7
52.9
38.1
88.2
86.2
47.7
562
68.2
56.3
37.6
50.7
35.4
46.5
58.0
58.8
45.8
89.0
74.8
64.1
79.9
75.3
63.3
$2.8
L
45.3
57.1
54.9
54.7
71.7
82.6
75.3
65.9
31.6
50.8
86.1
56.9
67.1
53.1
49.2
77.3
59.2
91.7
82.0
84.2
64.8
GNN
0
44.3
62.0
48.4
53.9
73.3
804
72.2
64.2
30.3
52.7
79.4
56.6
62.3
56.2
47.5
74.0
59.8
79.9
81.9
83.0
63.1
Potrropic
46.5
54.9
60.9
79.4
84.1
68.3
61.5
80.6
59.7
69.8
58.4
76.4
L 20
50.1
65.4
55.7
65.3
80.0
83.5
78.3
69.7
34.7
60.7
70.4
59.9
70.0
62.2
56.1
80.2
70.3
88.8
81.1
84.3
68.3
MLP
L 4=0
0
34.3
45.9
37.3
47.7
53.3
75.2
61.5
61.7
27.7
10.5
85.9
16.6
50.2
39.0
37.3
58.0
49.2
82.9
65.0
74.2
53.8
anisotropic
L
48.7
57.2
47.0
65.3
72.3
73.9
$7.6
76.7
70.0
31.0
30.0
57.5
55.5
91.7
92.8
55.4
59.5
67.9
56.2
56,9
48.7
85.1
87.2
58.3
94.9
87.9
86.0
67.6
GNN
L
0
42.1
57.5
49.6
59.4
83.8
84.0
78.4
67.5
37.3
60.4
85,0
58.0
66.0
54.1
52.6
93.9
60.2
85.6
87.8
82.5
67.3
anisotropic
45.5
67.6
56.5
66.8
86,9
85.2
84.2
73.0
43.6
66.0
92.3
64.0
79.8
56.6
56.1
95.4
64.4
95.0
91.3
86.3
72.8
20
47.0
65.7
56.8
67.6
N6.9
87.7
X5.3
72.6
42,9
69.1
84.5
63.8
78.1
55.6
58.4
98.0
68.4
92.2
94.5
85.5
73.0
Table 2: Hits@I (%) with standard deviations on the WILLOW-OBIECTCLASS dataset.
Method
Face
Motorbike
Car
Duck
Winebottle
GMN Janfir & Sminchisescu 2018
99.3
71.4
74.3
82.8
76.7
PCA-GM (Wang et al.
2019b
100.0
76.7
84.0
93.5
96,9
L
98.07 + 0.79
48.97 + 4.62
65.30 + 3.16
66.02 + 2.51
77.72 + 3.32
0. MLP
isotropic
10
100.00 0.00
67.28 + 4.93
85.07 + 3.93
83.10 = 3.61
92.30 :: 2.11
20
100.00 0.00
68.57
3.94
82.75 +: 5.77
84.18 +: 4.15
90.36 2.42
L = 0
99.62 = 0.28
73.47 +: 3.32
77.47 = 4.92
77.10 + 3.25
88.04 + 1.38
Ve
GNN
isotropic
L 10
100.00 1 0.00
92.05 1: 3.49
90.05 1 5,10
88. 88.98 1: 2.75
97.14 T 1.41
L = 20
100.00 + 0.00
92.05 + 3.24
90.28 + 4.67
88.97 + 3.49
97.14 + 1.83
98.47
0.61
49.28 1: 4.31
64.95 1: 3.52
66.17 1: 4.08
78.08 2.61
00 MLP
anisotropic
10
100.00
0.00
76.28
4.77
86.70 + 3.25
83.22 + 3.52
93.65 1.64
20
100.00 0.00
76.57 + 5.28
89.00 + 3.88
84.78 + 2.73
95.29 2.22
L == 0
99.96 1 0.06
91,90 1: 2.30
91.28 1: 4.89
86.58 1: 2.99
98.25 1 0.71
Vo. GNN
anisotropic
L 10
100.00
0.00
98.80 + 1.58
96.53 = 1.55
93.22 3.77
99.87 + 0.31
20
100.00 0.00
99.40 + 0.80
95.53 + 2.93
93.00 # 2.71
99.39 0.70
edge features which are given as normalized relative distances and 2D Cartesian coordinates, re- spectively. For SPININENN, we use a kernel size of 5 in each dimension, a hidden dimensionality of 256, and apply ReLU as our non-linearity function a. Our network architecture consists of two convolutional layers (T" 2), followed by dropout with probability 0.5, and final linear layer. Dur- ing training, we form pairs between any two training examples of the same category, and evaluate our model by sampling fixed number of test graph pairs belonging to the same category.
Results. We follow the experimental setup of Wang al. (2019b) and train our models using nega- tive log-likelihood due to its superior performance in contrast to the displacement loss used in Zanfir & Sminchisescu (2018). We evaluate our complete architecture using isotropic and anisotropic
GNNs for L E (0, 10, 20). and include ablation results obtained from using L e, MLP for the local node matching procedure. Results of Hits@ I are shown in Table and for PASCALVOC and WILLLOW-OBEECCIASS. respectively. We visualize qualitative results of our method in Ap- pendix
We observe that our refinement strategy is able to significantly outperform competing methods as well as our non-refined baselines. On the at least reduces the error of the initial model (L 0) by half across all categories. The benefits of the second stage are even more crucial when starting from a weaker initial feature matching baseline (V., 8, MLP), with overall improvements of up to 14 percentage points PASCALVOC. However, good initial matchings do help our consensus stage to improve its performance further, as indicated by the usage of task-specific isotropic or anisotropic GNNs for Vo.
dataset, our refinement stage
8

---

Published as a conference paper at ICLR 2020
Table 3:
Hits@ (%)
the PASCALPF dataset using synthetic training setup.
Method
Acno Bike Bird Boat
Bottle
Bus
Car
Cat
Chair Cow
Table
Dog
Horse M-Bike
Person
Plant
Sheep
Sofa
Train
TV Menn
Zhang
94.5
72.8
76.7
L ==0 0
68.2 81.7
77.3
90.4
98.7
98.3
92.5
91.5
91.7
79.4
95.8
90.1
80.0
79.5
72.5
98.0
76.5
59.6
93.4
97.8
87.6
Ours
81.3
94.2
98.8
99.3
98.6
98.2
99.6
94,1
100.0
99.4
86.6
86.6
88.7
100.0
100.0
100.0
100.0
99.3 95.8
L =
81.1
92.0
94.7
100.0
99.3
99.3
98.9
97.3
99.4
93:4
100.0
99.1
86.3
86.2
87.7
100.0
100.0
100.0
100.0
99.3 95.7
4.3 SUPERVISED GEOMETRIC KEYPOINT MATCHING
We also verify our approach by tackling the geometric feature matching problem, where we only make use of point coordinates and no additional visual features are available. Here, we follow the experimental training setup of ZZang & Lee (2019), and test the generalization capabilities of our model on the PASCALPF dataset (Ham et al. 2016). For training, we generate synthetic set of graph pairs: We first randomly sample 30-60 source points uniformly from [-1,1]². and add Gaussian noise from (00, 0.05²) to these points to obtain the target points. Furthermore, we add 0-20 outliers from [-1.5, 1.5)² to each point cloud. Finally, construct graphs by connecting each node with its k-nearest neighbors (k- = 8). We train our unmodified anisotropic keypoint architecture
from Section 4.2 with input T; = I E IR Vi E V. U V. until it has seen 32 000 synthetic examples.
Results. We evaluate our trained model on the PASCALPF dataset (Ham et al., 2016) which con- sists of 351 image pairs within 20 classes, with the number of keypoints ranging from 4 to 17. Results of Hits@ are shown in Table 3 Overall, our consensus architecture improves upon the of results of Zhang & Lee (2019) almost all categories while our L 0 baseline weaker than the results reported in Zhang & Lee (201)) showing the benefits of applying our consensus stage. In addition, it shows that our method works also well even when not taking any visual information into account.
4.4 SEMI-SUPERVISER CROSS-LINGUAL KNOWLEDGE GRAPII ALIGNMENT
We evaluate our model on the DBPI5K datasets (Sun al. 2017) which link entities of the Chi- nese, Japanese and French knowledge graphs of DBPEDIA into the English version and vice versa. Each dataset contains exactly 15 000 links between equivalent entities, and we split those links into training and testing following upon previous works. For obtaining entity input features, we fol- low the experimental setup of Xu et al. (2019d): We retrieve monolingual FASTTEXT embeddings (Bojanowski et al. 2017) for each language separately, and align those into the same vector space afterwards (Lample et al. 2018). We use the sum of word embeddings as the final entity input representation (although more sophisticated approaches are just conceivable).
Architecture and parameters. Our graph neural network operator mostly matches the one pro- posed in Xu et al. (2019d) where the direction of edges is retained, but not their specific relation type:
K ((+1) = o (H1))
Σ W J-1
W
(( (())
We use ReLU followed by dropout with probability 0.5 as our non-linearity o, and obtain final node representations via h4 W, [7 ..... J. We use a three-layer GNN (T 3) both for obtaining initial similarities and for refining alignments with dimensionality 256 and 32, respectively. Training performed using negative log likelihood in semi-supervised fashion: For each training node in V., we train L (inimn)) sparsely by using the corresponding ground-trute node in Vi, the top k 10 entries in St: and randomly sampled entities in V,, For the refinement phase, we update the sparse top correspondence matrix L 10 times. For efficiency reasons, we train L (imitial) and L (refined) sequentially for 100 epochs each.
We report Hits and Hits@ 10 to evaluate and compare our model to previous lines of work, see Table 4 In addition, report results of a simple three-layer MLP which matches nodes purely based on mitial word embeddings, and a variant of our model without the refinement of initial correspondences (T. 0). Our approach improves upon the state-of-the-ee
Results.
all categories with

---

Published as a conference paper at ICLR 2020
Table 4: Hits @ (%) and Hits @ 10 (%) on the DBP15K dataset.
ZH +EN
EN
-ZH
JA-EN
EN
+JA
FR->N
EN-FR
Method
@1 @ 10
@9
60 1010
69
@ 10
691
@
60
10
@1
60
GCN Wang al.
2018
41.25
74.38
36.49
69.94
39,91
74.46
38.42
71.81
37.29
74.49
36.77
73.06
BOOTEA
Sun
2
62.94
84.75
62.23
85.39
65.30
87.44
MUGNN
Cao al 2019
49.40
84,40
50.10
85.70
49.60
87.00
NAEA
Lu ef ai.
2019
65.01
86.73
64.14
87.27
67.32
89.43
RDGCN (Wu et a
2019
70.75
84.55
76.74
89.54
88.64
95.72
GMNN
Xu ct al.
2019d
67.93
78.48
65.28
79.64
73.97
87.15
71.29
84.63
89.38
95.25
88.18
94.75
Ve.
MLP
L
58.53
78.04
54,99
74.25
59.18
79.16
55. 40
75.53
76.07
91.54
74.89
90.57
L =
67,59
87.47
64.38
83.56
71.95
89.74
68.88
86.84
83.36
96.03
82.16
95.28
Ours (sparse)
L 10
80.12
87.47
76.77
83.56
84,80
89.74
81.09
86.84
93.34
96.03
91.95
95.28
gains of up to 9.38 percentage points. In addition, our refinement strategy consistently improves upon the @its@ 1 of initial correspondences by significant margin, while results of Hits 10 are shared due to the refinement operating only on sparsified top 10 initial correspondences. Due to the scalability of our approach, we can easily apply a multitude refinement iterations while still retaining large hidden feature dimensionalities.
5 LIMITATIONS
Our experimental results demonstrate that the proposed approach effectively solves challenging real- world problems. However, the expressive power of GNNs is closely related to the WL heuristic for graph isomorphism testing (Xu et al. 2019c Morris et al., 2019), whose power and limitations are well understood (Arvind et al. 2015). Our method generally inherits these limitations. Hence, one possible limitation is that whenever two nodes are assigned the same color by WI., our approach may fail to converge to one of the possible solutions. For example, there may exist two nodes i V; with equal neighborhood sets (i) NG( One easily see that the feature matching procedure generates equal initial correspondence distributions s: :: resulting in the same mapped node indicator functions I (0 = TT. S from G. to nodes i and j. respectively. Since both nodes share the same neighborhood, Vo, also produces the same distributed functions .
-! -.(0)_ As result, both column vectors ((() and 8(()) receive the non-convergence. In theory, one might resolve these ambiguities by adding small amount noise to Ş(U), However, the general amount of feature noise present in real-world datasets already ensures that this scenario is unlikely occur.
update, leading to
RELATED WORK
Identifying correspondences between the nodes of two graphs has been studied in various domains and an extensive body of literature exists. Closely related problems are summarized under terms maximum common subgraph (Kriege et al., 2019b). network alignment (Zhang) 2016), graph edit distance (Chen et al.) 2019) and graph matching (Yan et al.) 2016). We refer the reader to the Ap- pendix F for detailed discussion of the related work these problems. Recently, graph neural networks have become a focus of research leading to various proposed deep graph matching tech- niques (Wang et 2019b; Zhang Lee 2019 Xu al., 2019d] Derr al. (209)). In Appendix G we present a detailed overview of the related work in this field while highlighting individual differ- ences and similarities to our proposed graph matching consensus procedure.
CONCLUSION
We presented two-stage neural architecture for learning node correspondences between graphs in a supervised or semi-supervised fashion. Our approach is aimed towards reaching a neighborhood consensus between matchings, and can resolve violations of this criteria in iterative fashion. In addition, we proposed enhancements to let our algorithm scale to large input domains. We evaluated architecture real-world datasets which it consistently improved upon the state-of- tate-of-the-art.
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGEMENTS
This work has been supported by the German Research Association (DFG) within the Collaborative Research Center SFB 876 Providing Information by Resource-Constrene Analysis, projects A6 and B2.
REFERENCES
R. Adams and R. Zemel. Ranking via sinkhorn propagation. CoRR, abs/1 106.1925, 2011.
Y. Aflalo, A. Bronstein, and R. Kimmel. convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences, 112(10), 2015.
K. Anstreicher. Recent advances in the solution of quadratic assignment problems. Mathematical Programming, 97, 2003.
V. Arvind, J. Kbler, G. Rattan, and O. Verbitsky. On the power of color refinement. In Fundamentals of Computation Theory, 2015.
Y. Bai, H. Ding, Y. Sun, and W. Wang. Convolutional set matching for graph similarity. In NeurlPS- W, 2018.
Y. Bai, H. Ding, Bian, T. Chen, Y. Sun, and W. Wang. SimGNN: A neural network approach to fast graph similarity computation. In WSDM, 2019.
P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanzhez-Gonzalez, V. F. Zambaldi, M. Malinowski, A. Tacchetti, Raposo, A. Santoro, R. Faulkner, Ç. Gülçehre, F. Song, A. Ballard, Gilmer, G. E. Dahl, A. Vaswani, K. Allen, C. Nash, V. Langston, C. Dyer, N. Heess, D. Wierstra, P. Kohli, M. Botvinick, O. Vinyals, Li, and R. Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/1806 01261, 2018.
M. Bayati, D. Gleich, A. Saberi, and Y. Wang. Message-passing algorithms for sparse network alignment. ACM Transactions on Knowledge Discovery from Data, 7(1), 2013.
J. Bento and S. loannidis. A family of tractable graph distances. In SDM, 2018.
P. Bojanowski, E. Grave, A. Joulin, and T. Mikolov. Enriching word vectors with subword informa- tion. Transactions of the Association for Computational Linguistics, 2017.
S. Bougleux, L. Brun, V. Carletti, P. Foggia, B. Gazre, and M. Vento. Graph edit distance as quadratic assignment problem. Pattern Recognition Letters, 87, 2017.
L. Bourdev and Malik. Poselets: Body part detectors trained using 3D human pose annotations. In ICCV, 2009.
M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond euclidean data. Signal Processing Magazine, 2017.
H. Bunke. On relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters, 18(8), 1997.
H. Bunke and K. Shearer. A graph distance metric based on the maximal common subgraph. Pattern Recognition Letters, 19(4), 1998.
T. S. Caetano, J. McAuley, L. Cheng, Q. V. Le, and A. J. Smola. Learning graph matching. IEEE Transactions on Puttern Analysis and Machine Intelligence, 31(6), 2009.
Y. Cao, Z. Liu, C. Li, Z. Liu, J. Li, and T. Chua. Multi-channel graph neural network for entity alignment. In ACL, 2019.
B. Charlier, J. Feydy, and Glaunès.
2019.
X. Chen, H. Huo. J. Huan, and J. S. Vitter. An efficient algorithm for graph edit distance computa- tion. Knowledge-Bill Based Systems, 163, 2019.

---

Published as a conference paper at ICLR 2020
M. Cho, K. Alahari, and J. Ponce. Learning graphs match. In 2013.
C. Choy, J. Gwak, Savarese, and M. Chandraker. Universal correspondence network. NIPS, 2016.
D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recogni- tion. International Journal of Pattern Recognition and Artificial Intelligence, 18, 2004.
X. Cortés, D. Conte, and H. Cardot. Learning edit cost estimation models for graph edit distance. Pattern Recognition Letters, 125, 2019.
T. Cour, P. Srinivasan, and J. Shi. Balanced graph matching. In NIPS, 2006.
M. DeGroot and M. Schervish. Probability and Statistics. Addison- Wesloy,, 2012.
J. Deng, W. Dong, R. Socher, L. J. Li, K. Li, and L. Fei-Fei. ImageNet: A large-scale hierarchical image database. In CVPR, 2009.
Derr, H. Karimi, X. Liu, J. Xu, and J. Tang. Deep adversarial network alignment. CoRR, abs/1902. 103017 2019.
A. Egozi, Y. Keller, and H. Guterman. A probabilistic approach to spectral graph matching. IEEE Transactions Pattern Analysis and Machine Intelligence, 35(1), 2013.
Erdós and A. Rényi On random graphs Publicationes Mathematicae Debrecen, 1959.
M. Everingham, L. Van Gool, C. K. Williams, J. Winn, and A. Zisserman. The Pascal visual object classes (VOC) challenge. IJCV, 2010.
M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR-W, W, 2019.
M. Fey, J. E. Lenssen, Weichert, and H. Müller. SplineCNN: Fast geometric deep learning with continuous B-spline kernels. In CVPR, 2018.
M. R. Garey and D. S. Johnson. Computers and Intractability: Guide the Theory of NP- Completeness. W. H. Freeman, 1979.
Gilmer, S. Schoenholz, F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
X. Glorot, A. Bordes, and Y. Bengio. Deep sparse rectifier neural networks. In AISTATS, 2011.
Gold and A. Rangarajan. graduated assignment algorithm for graph matching. IEEE Transac- tions Pattern Analysis and Machine Intelligence, 18(4), 1996.
M. Gori, M. Maggini, and Sarti. Exact and approximate graph matching using random walks. IEEE Transactions Puttern Analysis and Machine Intelligence, 27(7), 2005.
K. Gouda and M. Hassaan. CSLGED: An efficient approach for graph edit similarity computation. In ICDE, 2016.
P. Goyal and E. Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge-Bard -Based Systems, 151, 2018.
M. Grohe, G. Rattan, and G. J. Woeginger. Graph similarity and approximate isomorphism. In Mathematical Foundations of Computer Science, 2018.
A. Grover and J. Leskovec. Nece2Vec: Scalable feature learning for networks. In SIGKDD, 2016.
O. Halimi, O. Litany, Rodolà, A. M. Bronstein, and Kimmel. Self-supervised learning of dense shape correspondence. In CVPR, 2019.
B. Ham, M. Cho, C. Schmid, and J. Ponce. Proposal flow. In CVPR, 2016.
12

---

Published as a conference paper at ICLR 2020
W. L. Hamilton, R. Ying. and J. Leskovec. Representation learning graphs: Methods and appli- cations. IEEE Data Engineering Bulletin, 40(3), 2017.
M. Heimann, H. Shen, T. Safavi, and D. Koutra. REGAL: Representation learning-basee based graph alignment. In CIKM, 2018.
loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, 2015.
M. Jaggi. Revisiting Frank- Wolfe: Projection-free sparse convex optimization. In ICML, 2013.
V. Kann. On the approximability of the maximum common subgraph problem. In STACS, 1992.
Kristian Kersting, Martin Mladenov, Roman Garnett, and Martin Grohe. Power iterated color finement. In AAAI, 2014.
D. P. Kingma and J. L. Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
G. W. Klau. A new graph-based method for pairwise global network alignment. BMC Bioinformat- ics, 10, 2009.
G. Kollias, S. Mohammadi, and A. Grama. Network similarity decomposition (NSD): A fast and scalable approach network alignment. IEEE Tranactions Knowledge and Data Engineering, 24(12), 2012.
N. M. Kriege, P. L.. Gíscard, F. Bause, and R. C. Wilson. Computing optimal assignments in linear time for approximate graph matching. In ICDM, 2019a.
N. M. Kriege, I.. Humbeck, and O. Koch. Chemical similarity and substructure searches. In Ency- clopedia of Bioinformatics and Computational Biology. Academic Press, 2019b.
G. Lample, A. Conneau, M. Ranzato, L. Denoyer, and H. Jégou. Word translation without parallel data. In ICLR, 2018.
M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In ICCV, 2005.
M. Leordeanu, M. Hebert, and R. Sukthankar. An integer projected fixed point method for graph matching and MAP inference. In NIPS, 2009.
Lerouge, Z. Abu-Aisheh, Raveaux, P. Hroux, and S. Adam. New binary linear programming formulation to compute the graph edit distance. Pattern Recognition, 72, 2017.
Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli. Graph matching networks for learning the similarity of graph structured objects. ICML, 2019.
O. Litany, T. Remez, E. Rodolà, A. M. Bronstein, and M. M. Bronstein. Deep functional maps: Structured prediction for dense shape correspondence. In ICCV, 2017.
V. Lyzinski, D. E. Fishkind, M. Fiori, J. T. Vogelstein, C. E. Priebe, and G. Sapiro. Graph matching: Relax at your risk. IEEE Transactions Pattern Analysis and Machine Intelligence, 38(1), 2016.
D. W. Matula. Subtree isomorphism in O(n3/2). In Algorithmic Aspects of Combinatorics, vol- ume 2. Elsevier, 1978.
C. Morris, M. Ritzert, M. Fey, W. L. Hamilton. J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
R. L. Murphy, B. Srinivasan, V. Rao, and B. Ribeiro. Relational pooling for graph representations. In ICML, 2019.
13

---

Published as a conference paper at ICLR 2020
M. Ovsjanikov, M. Ben-Chen, J. Solomon, A. Butscher, and L. J. Guibas. Functional maps: A flexible representation maps between shapes. ACM Transactions on Graphics, 31(4), 2012.
L. Page. S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer. Automatic differentiation PyTorch. In NIPS- W, 2017.
G. Peyré, M. Cuturi, and J. Solomon. Maanov-Wassersteinn averaging of kemel and distance matri- ces. In ICML, 2016.
K. Riesen and H. Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing, 27(7), 2009.
K. Riesen, M. Ferrer, R. Dorneereer, and H. Bunke. Greedy graph edit distance. In Machine Learning and Data Mining Pattern Recognition, 2015a.
K. Riesen, M. Ferrer, A. Fischer, and H. Bunke, Approximation of graph edit distance in quadratic time. In Graph-Basa Based Representations in Pattern Recognition, 2015b.
I. Rocco, M. Cimpo, R. Arandjelović, A. Torii, T. Pajdla, and J. Sivic. Neighbourhood consensus networks. In NeurIPS, 2018.
E. Rodolà, L. Cosmo, M. M. Bronstein, A. Torsello, and D. Cremers. Partial functional correspon- dence. Computer Graphics Forum, 36(1), 2017.
A. Sanfeliu and K. S. Fu, A distance measure between attributed relational graphs for pattern recog- nition. IEEE Transactions on Systems, Man, and Cybernetics, 13(3), 1983.
Sattler, B. Leibe, and Kobbelt. SCRAMSAC: Improving RANSAC's efficiency with a spatial consistency filter. In ICCV, 2009.
M. Schlichtkrull, T. N. Kipf, P. Bloem, R. van den Berg. Titov, and M. Welling. Modeling relational data with graph convolutional networks. In ESWC, 2018.
C. Schmid and R. Mohr. Local grayvalue invariants for image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(5), 1997.
R. Sharan and T. Ideker. Modeling cellular machinery through biological network comparison. Nature Biotechnology, 24(4), 2006.
K. Simonyan and Zisserman. Very deep convolutional networks for large-scale image recogni- tion. In ICLR, 2014.
R. Singh, J. Xu, and Berger. Global alignment of multiple protein interaction networks with application to functional orthology detection. In National Academy of Sciences, 2008
R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2), 1967.
J. Sivic and A. Zisserman. Video Google: A text retrieval approach object matching in videos. In ICCV, 2003.
N. Srivastava, G. E. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15, 2014.
M. Stauffer, T. Tschachtli, A. Fischer, and K. Riesen. A survey on applications of bipartite graph edit distance. In Graph-Based Representations in Pattern Recognition, 2017.
Z. Sun, W. Hu, and C. Li. Cross-lingual entity alignment via joint In ISWC, 2017.
embedding.
14

---

Published as a conference paper at ICLR 2020
Z. Sun, W. Hu, Q. Zhang, and Y. Qu. Bootstrapping entity alignment with knowledge graph embed- ding. ICCAI, 2018.
P. Swoboda, C. Rother, H. A. Ahljaija, D. Kainmueller, and B. Savchynskyy. A study of lagrangean decompositions and dual ascent solvers for graph matching. In CVPR, 2017.
G. Tinhofer. A note on compact graphs. Discrete Applied Mathematics, 30(2), 1991.
S. Umeyama. An eigendecomposition approach weighted graph matching problems. IEEE Trans- actions on Pattern Analysis and Machine Intelligenee 10(5), 1988.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention net- works. In ICLR, 2018.
M. Vento and P. Foggia. Graph matching techniques for computer vision. Graph-Based Methods in Computer Vision: Developments and Applications, 1, 2012.
Wang, N. Xue, Y. Zhang, G. Xia, and M. Pelillo. A functional representation for graph matching. IEEE Transactions Pattern Analysis and Machine Intelligence, 2019a.
R. Wang. J. Yan, and X. Yang. Learning combinatorial embedding networks for deep graph match- ing. In ICCV, 2019b.
Y. Wang and M. Solomon. Deep closest point: Learning representations for point cloud registra- tion. In ICCV, 2019.
Z. Wang, Q. Lv, X. Lan, and Zhang. Cross-lingual knowledge graph alignment via graph convo- lutional networks. In EMNLP. 2018.
B. Weisfeiler and A. A. Lehman. A reduction of graph to canonical form and an algebra arising during this reduction. Nauchno- Teccinc-Techniiheskkayaa Informatiia, 2(9), 1968.
Y. Wu, X. Liu, Y. Feng, Z. Wang, R. Yan, and D. Zhao. Relation-awan entity alignment for hetero- geneous knowledge graphs. IJCAI, 2019.
H. Xu, D. Luo, and L. Carin. Scalable Gromov-Wasserstin learning for graph partitioning and matching. CoRR, abs/1905.07644 2019a.
H. Xu, D. Luo, H. Zha, and L. Carin. Grosev-wasserstein learning for graph matching and node embedding. In ICML., 2019b.
K. Xu, C. Li, Tian, T. Sonobe, Kawarabayashi, and Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
K. Xu, W. Hu, Leskovee, and Jegelka. How powerful are graph neural networks? In ICLR, 2019c.
K. Xu, L. Wang, M. Yu, Y. Feng, Y. Song. Z. Wang, and D. Yu. Cross-lingual knowledge graph alignment via graph matching neural network. In ACI, 2019d.
J. Yan, X. C. Yin, W. Lin, C. Deng, H. Zha, and X. Yang. A short survey of recent advances in graph matching. In JCMR, 2016.
A. Zanfir and C. Sminchisescu. Deep learning of graph matching. In CVPR, 2018.
M. Zaslavskiy, F. Bach, and J. P. Vert. A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31())), 2009.
H. Zhang, S.and Tong, FINAL: fast attributed network alignment. In SIGKDD, 2016.
J. Zhang and S. Philip. Multiple anonymized social networks alignment. In ICDM, 2015,
W. Zhang, K. Shu, H. Liu, and Y. Wang. Graph neural networks for user identity linkage. CoRR, abs/1903.02174, 2019a.
15

---

Published as a conference paper at ICLR 2020
Y. Zhang, A. Prügel-Bennett and J. Hare. Learning representations of sets through optimized per- mutations. ICLR, 2019b.
Z. Zhang and W. S. Lee. Deep graphical feature learning for the feature matching problem. In ICCV, 2019.
Z. Zhang, Y. Xiang, L. Wu, Xue, and A. Nehorai. KerGM: Kernelized graph matching. In NeurIPS, 2019c.
F. Zhou and F. De la Torre. Factorized graph matching, In CVPR, 2016.
J. Y. Zhu, T. Park, P. Isola, and A. A. Efros. Unpaired image-to-imas translation using eycle- consistent adversarial networks. In ICCV, 2017.
Q. Zhu, X. Zhou, J. Wu, J. Tan, and L. Guo. Neighborhoodd-wware attentional representation for multilingual knowledge graphs. In I/CAI, 2019.
16

---

Published as a conference paper at ICLR 2020
A OPTIMIZED GRAPH MATCHING CONSENSUS ALGORITHM
Our final optimized algorithm is given in Algorithm
Algorithm 1 Optimized graph matching consensus algorithm
Input: g. (V,, A,, x., E.). 9 = (V,. A,, X,, Ex), hidden node dimensionality d, sparsity parameter k, number of consensus iterations L, number of random functions
Output: Sparse soft correspondence matrix ((L) e [0, 1
with k [V&] non-zero entries
H. Vo (X, Ag, E.)
Compute node embeddings H3 E R V.|x
H. Ve, (X,, A., Ex)
b. Compute node embeddings H. E R > Local feature matching
( + H,H,
( t Lop (S (0))
> Sparsify to top l candidates Vi E {1,.... D&1}
for l (l..... L) do
D L E {I, I [(ee)))
S s(t-1) - softmax ($ (1)
Normalize scores vi E {1,.... V.1
1, R 10,
> Sample random node function R E R
R ( S1-1) R
Map random node functions R from Go to G Distribute function R on G. >> Distribute function R on Ge Compute neighborhood consensus measure Perform trainable correspondence update
O, - oz R Agg E.)
O, + v (R() As, Ee)
d,j 0 (8) (1)
jj
S/ + S(1 ((1-1)
((()
+ Lo (di,) 1/
end for
s(L) f softmax (8(1))
Normalize scores Vi E {l,..., D71
1.
return S(L)
B PROOF FOR THEOREM
Proof. Since Lo is permutation equivariant, it holds for any node feature matrix X, E RIV. that L ee SS X,
5: S A,S) = S Lo, [x,, A.). With X, S X, and A, S A,S, follows that
O, vg XX,, A.) = Ve (S X,, T A,S) = S V (X,, A.) = ST...
Hence, it shows that o((0) (S Ox)))) =00
(1) for any node i V., resulting in di,r(1) ō.
x())
C PROOF FOR THEOREM?
Proof. Let be dr,; = =0(0) - σ(0) = Ô. Then, the T- T-layered GNN Le maps both T-hop neighbor-
hoods around nodes É V, and j E V; to the same vectorial representation:
Vos (1.
(+) (o.A))))
(,, ( A NoWw =
(4) (10)
Because L is as powerful as the WL heuristic in distinguishing graph structures (Xu et al. 2019c
Morris et al. 2019) and is operating injective node colorings I VI, it has the power to distinguish
any graph structure from G. (+) (Wr(1), I VVl (+)
(r(o.." (r)) ef (Murphy et al.
2019
Since a.(0) holds information about every node in (.)) it necessarily holds that G. (i)
(() in case 5. = 0
(t) where > denotes the labeled graph isomorphism relation. Hence,
there exists an isomorphism P E {0, 10 (] ( between (.N)r((ii and G.(NG such that | (o). P(S Ips, )NCO)) and A (8) (o) ( N PT
(1)
(11)
With Tia being the identity matrix, follows that |V. (1). = PST Na)." Furthermore, holds
that ( PST (0 when reducing I (f) to its column-wise non-zero entries. It follows that (NT())NT)) P is permutation matrix describing an isomorphism.
[V.l
17

---

Published as a conference paper at ICLR 2020
Table 5:
Hits @
(%) on the PASCALVOC dataset with Berkeley keypoint annotations.
Method
Acro like Bird Boat Bottle
Bas Car Cat Chair
Cow
Table
Dog
Horse
M-Bike
Person Plant Sheep
Sofa
Train
TV Mean
iotropicc
AX
L
10
45.9
60.5
49.0
59.7
72.8
80.9
77.4
67.2
34,1
56.3
80.4
59.5
68.5
53.9
48.6
75.5
60.8
91.5
81.8
80.3
65.4
2, GNN
46.5
63.7
54.9
60.9
79.4
84.1
76.4
68.3
38.5
61.5
80.6
59.7
69.8
58.4
54.3
76.4
64.5
95.7
87,9
81.3
68.1
L =0
50.1
654
55.7
65.3
80.0
83.5
78.3
69.7
34.7
60.7
704
59,9
70,0
62.2
96.1
80.2
70.3
84.3
68.3
Table 6: Hits @ 1 (%) on the DBP15K dataset.
Method
ZH-EN
EN-
JA-EE
EN-+JA
FR++EN
EN-+FR
L = 0
67.59
64.38
71.95
68.88
83.36
82.16
V 02 = AX
I. 1= 10
71.61
68.52
77.18
76.53
85.69
85.96
Vo GNN
I.
80.12
76.77
84.80
81.09
93.34
91.95
Moreover, if arggaaxxx s.. Ō for all i Vs, it directly follows that S is holding submatrices de- scribing isomorphisms between any T-hop subgraphs around i E V, and argmax S, E V2 Assume there exists nodes i, E V. that map to the same node j = argmax S., = argmax Sv.: E V2. o(()) which contradicts the injectivity requirements of AGGREGATE!!) and UPDATE for all E (1....,77 T) Hence, S must be itself permutation matrix describing an isomorphism between 9, and Gt.
follows that o.(0) = o
D COMPARISON TO THE GRADUATED ASSIGNMENT ALGORITHM
As stated in Section 3.3 our algorithm can be viewed as a generalization the graduated assign- ment algorithm (Gold & Rangarajan (996) extending it by trainable parameters. To evaluate the impact a trainable refinement procedure, we replicated the experiments Sections 4.2 and 4.4 by implementing V e, via a non-trainable, one-layer GNN instantiation D (X,
AX
The results in Tables 5 and 6 show that using trainable neural networks Va, consistently improves upon the results of using the fixed-function message passing scheme. While it is difficult to encode meaningful similarities between node and edge features a fixed funcctinn pipeline, our approach is able to learn how to make use of those features to guide the refinement procedure further. In addition, it allows us to choose from a variety of task-dependent GNN operators, e.g., for learn- ing geometric/edge conditioned patterns for fulfilling injectivity requirements. The theoretical expressivity discussed in Section could even be enhanced by making use of higher-order GNNs, which we leave for future work.
E ROBUSTNESS TOWARDS NODE ADDITION OR REMOVAL
To experimentally validate the robustness of our approach towards node addition (or removal), conducted additional synthetic experiments in a similar fashion to Xu et al. (2019b). We form graph-pairs by treating an Erdös & Rényi graph with [V,] (50, 100] nodes and edge probability {0.1, 0.2) as our source graph G.. The target graph G, is then constructed by first adding 9% noisy nodes the source graph, i.e., |v] (1 + 9%) nodes and all other nodes based on the edge probability afterwards. We use the same network architecture and training procedure as described in Section 4.1
) V.l. and generating edges between these
Figure 3 visualizes the Hits @1 for different choices of [V1l and (..0, 0.5). 0.3,
As one can see, our consensus stage is extremely robust to the addition or removal nodes while the first stage alone has major difficulties in finding the right matching. This can be explained by the fact that unmatched nodes do not have any influence on the neighborhood consensus error since those nodes do not obtain color from the functional map given by S. Our neural architecture is able to detect and gradually decrease any false positive influence of these nodes in the refinement stage.
18

---

Published as a conference paper at ICLR 2020
softmax )
softmax (alimaxx(S( ((()
100
100
Hits@1 (5)
Hits@1 (%)
60
8
80
10
20
30
30 50
0
10
20
30
10
50
Node additions q (%6
Node adkitions 9 (%)
(a) [&] 50, p = 0.2
(b) [
100, p 0.1
Figure 3: The performance of our method on synthetic data with node additions.
F RELATED WORK I
Identifying correspondences between the nodes of two graphs is a problem arising in various do- mains and has been studied under different terms. In graph theory, the combinatorial maximum common subgraph isomorphism problem is studied, which asks for the largest graph that is con- tained subgraph in two given graphs. The problem is NP-hard in general and remains even in trees (Garey & Johnson 1979) unless the common subgraph is required to be connected (Matula) 1978 Morcover, most variants of the problem are difficult approximate with theoretical guaran- tees (Kann 1992). We refer the reader to the survey by Kriege et al. (2019h) for overview of the complexity results noting that exact polynomial time algorithms are available for specific problem variants only that are most relevant in cheminformaties.
Fundamentally different techniques have been developed in bioinformatics and computer vision, where the problem is commonly referred to as network alignment or gruph matching. In these areas large networks without any specific structural properties are common and the studied techniques non-exact. In graph matching, for two graphs of order n with adjacency matrix A, and A,, respectively, typically the function
|A, - S ATA = |A.
1 2 Σ
(12)
LY JO'EV.
is to be minimized, where S E P with P the set of n x permutation matrices and ||| Eipev A2,- denotes the squared Frobenius norm. Since the first two terms of the right-hand side do not depend on S, minimizing Equation T2 is equivalent in terms of optimal solutions to the problem of Equation ( We briefly summarize important related work in graph matching and refer the reader to the recent survey by Yan et al. (2016) for a more detailed discussion. There is a long line of research trying to minimize Equation 112 for S E [0, 1 1 by a Frank- Wolfe type algo- rithm (aggii 2013) and finally projecting the fractional solution to P (Gold & Rangarajan [996 Zaslavskiy et al. 2009 Leordeanu al.) 2009 Egozi al. 2013 Zhou & De la Torre 2016). How- ever, the applicability of relaxation and projection is still poorly understood and only few theoretical results exist (Aflalo et al. 2015 Lyzinski et al.) 2016). A classical result by Tinhofer (1991) states that the WL heuristic distinguishes two graphs G. and G, if and only if there is no fractional S such that the objective function in Equation (12) takes 0. Kersting et al.) (2014) showed how the Frank-Wole algorithm can be modified to obtain the WL partition. Atlalo et al. (2015) proved that the standard relaxation yields correct solution for particular class of asymmetric graphs. which can be characterized by the spectral properties of their adjacency matrix. Finally, [ennoo & Ioanni- dis (2018) studied various relaxations, their complexity and properties. Other approaches to graph matching exist, e.g., based on spectral relaxations (Umeyamal 1988 Leordeanu & Hebert (005) or random walks (Gori et al. (2055). The problem of graph matching closely related to the no- toriously hard quadratic assignment problem (QAP) (Zhou & De la Torre, 2016), which has been studied in operations research for decades. Equation (1) can be directly interpreted as Koopmans- Beckmann's 's QAP. The more recent literature graph matching typically considers weighted version, where node and edge similarities are taken into account. This leads to the formulation as Lawler's QAP, which involves affinity matrix of size n² x n² and is computational demanding.
19

---

Published as a conference paper at ICLR 2020
Zhou & De la Torr (2016) proposed factorize the affinity matrix into smaller matrices and in- corporated global geometric constraints. Zhang et al. (2019c) studied kernelized graph matching, where the node and edge similarities are kernels, which allows to express the graph matching prob- lem again as Knopmans--eekkaant 's QAP in the associated Hilbert space. Inspired by established methods for Maximum-AA-Pssterion (MAP) inference in conditional random fields, [Swohoda et al. (211)) studied several Lagrangean decompositions of the graph matching problem, which are solved by dual ascent algorithms also known as message passing. Specific message passing schedules and update mechanisms leading to state-of-te af-tthe-rt performance in graph matching tasks have been iden- tified experimentally. Recently, functional representation for graph matching has been proposed as a generalizing concept with the additional goal to avoid the construction of the affinity matrix (Wang) et al. 2019a).
Graph edit distance. related concept studied in computer vision is the graph edit distance, which measures the minimum cost required to transform a graph into another graph by adding,
deleting and substituting vertices and edges. The idea has been proposed for pattern recognition tasks more than 30 years ago (Sanfeliu & Ful 1983). However, its computation is NP- NP-hard, since it
generalizes the maximum common subgraph problem (Bunke) 1997). Moreover, it is also closely related the quadratic assignment problem (Bougleux et al. 2017). Recently several elaborated exact algorithms for computing the graph edit distance have been proposed (Gouda & Hassaan 2016 Lerouge et al. 2017; Chen al.] 2019). but are still limited to small graphs. Therefore, heuristics based on the assignment problem have been proposed (Riesen & Bunnee (0099 and are widely used in practice (Staufter et al., 2017). The original approach requires cubic running time, which can be reduced to quadratic time using greedy strategies (Riesen et al., 2015a b), and even linear time for restricted cost functions (Kriege et al. 2019a).
Network aligmment. The problem of network alignment typically is defined analogously to Equa- tion ( where in addition a similarity function between pairs of nodes is given. Most algorithms follow a two step approach: First, an n x n node-to-node similarity matrix M is computed from the given similarity function and the topology of the two graphs. Then, in the second step, an alignment computed by solving the assignment problem for M. (Singh et al. (2008) proposed ISORANK, which is based on the adjacency matrix of the product graph K A. = X A. of G. and G.. where @ denotes the Kronecker product. The matrix M is obtained by applying PAGERANK (Page et al.) 1999) using normalized version of K as the GOOGLE matrix and the node similarities as the personalization vector. Kollias et al.] (2012) proposed an efficient approximation of ISORANK by decomposition techniques avoid generating the product graph of quadratic size. Zhang (2016) present an extension supporting vertex and edge similarities and propose its computation using non- exact techniques. Klau (2009) proposed to solve network alignment by linearizing the quadratic optimization problem to obtain an integer linear program, which is then approached via Lagrangian relaxation. Bayati al. (2013) developed message passing algorithm for sparse network align- ment, where only small number of matches between the vertices of the two graphs are allowed.
The techniques briefly summarized above aim to find an optimal correspondence according to a clearly defined objective function. In practical applications. it is often difficult to specify node and edge similarity functions. Recently, it has been proposed to learn such functions for a specific task, e.g., in form of cost model for the graph edit distance (Cortés et al.] 2019). A more principled approach has been proposed by Caetano et al. (2009) where the goal is to learn correspondences.
G RELATED WORK II
The method presented in this work is related to different lines of research. Deep graph matching procedures have been investigated from multiple perspectives, e.g., by utilizing local node feature matchings and cross gross- embeddings (Li al. 2019). The idea of refining local feature matchings by enforcing neighborhood consistency has been relevant for several years for matching in images (Sattler et al. 2009). Furthermore, the functional maps framework aims to solve similar problem for manifolds (Halimi et al. 2019).
Deep graph matching. Recently, the problem of graph matching has been heavily investigated in deep fashion. For example, Zantir & Sminchisescuj (2018); Wang et al. (0019)) Zhang & Lee
20

---

Published as a conference paper at ICLR 2020
2019) develop supervised deep graph matching networks based displacement and combinato- rial objectives, respectively. Zanffr& & Sminchisescu (2018) model the graph matching affinity via differentiable, but unlearnable spectral graph matching solver (Leordeanu & Hebert 2005). In contrast, our matching procedure is fully-learnable. Wang et al. (2019b) use wode-wise features in combination with dense node-to-node cross-graph affinities, distribute them in local fashion, and adopt sinkhorn normalization for the final task of linear assignment. Zhang & Leel (2019) propose compositional message passing algorithm that maps point coordinates into a high-dimensional space. The final matching procedure is done by computing the pairwise inner product between point embeddings. However, neither of these approaches can naturally resolve violations of inconsistent neighborhhodd assignments as we do in our work.
Xu al. 2019b) tackles the problem of graph matching by relating it to the Saamoo--asssestein discrepancy (Peyré et al. (2016). In addition, the optimal transport objective is enhanched by simul- taneously learning node embeddings which shall account for the noise in both graphs. a follow-up work, Xu et al. (2019a) extend this concept to the tasks of multi-graph partioning and matching by learning a Gromov- Wasserstein barycenter. Our approach also resembles the optimal transport be- tween nodes, but works in supervised fashion for sets of graphs and is therefore able to generalize to unseen graph instances.
In addition, the task of network alignment has been recently investigated from multiple perspec- tives. Derr et al. (2019) leverage CYCLEGANS (Zhu et al. 2017) to align NODE2 embeddings the nearest neighbor in the embedding space. Zhang et al. (2019a) design deep graph model based on global and local network topology preservation as auxiliary tasks. [Heimann et al. (2018) utilize fast, but purely local and greedy matching procedure based on local node embedding similarity.
(Grover & Leskovec 2016) and find matchings based
Furthermore, Bai et al. (2019) use shared graph neural networks to approximate the graph edit distance between two graphs. Here. a nion-difeerentiable) histogram of correspondence scores is used fine-tune the output of the network. In a fpp work.[Bai al. (2018) proposed order the correspondence matrix in -erct fashion and to process it further with the help of traditional CNNs. Both approaches only operate on local node embeddings, and are hence prone to match correspondences inconsistently.
Intra- and inter-graph message passing, The concept of enhanching intra-graph node embed- dings by inter-graph node embeddings has been already heavily investigated in practice (Li et al., 2019 Wang et al., 2019b Xu et al. 2019d). Li et al. (2019) and Wang et al. (2019b) enhance the GNN operator by not only aggregating information from local neighbors, but also from similar embeddings in the other graph by utilizing a cross-graph matching procedure. [uu et al. (2019d) leverage alternating GNNs to propagate local features of one graph throughout the second graph. Wang & Solomon 2019) tackle the problem of finding unknown rigid motion between point clouds by relating it to point cloud matching problem followed by a differentiable SVD module. Intra-graph node embeddings are passed via Transformer module before feature matching based on inner product similarity scores takes place. However, neither of these approaches is designed to achieve consistent matching, due to only operating on localized node embeddings which are alone not sufficient to resolve ambiguities in the matchings. Nonetheless, we argue that these methods can be used strengthen the initial feature matching procedure, making our approach orthogonal to improvements in this field.
Neighborhood consensus for image matching. Methods to obtain consistency of correspon- dences in local neighborhoods have rich history in computer vision, dating back several years (Sattler et al., 2009; Sivic & Zisserman 2003] [Schmid & Mohr 1997). They are known for heavily improving results of local feature matching procedures while being computational efficient. Re- cently, a deep neural network for neighborhood consensus using 4D convolution was proposed (Rocco et al. 2018). While it is related to our method, the 4D convolution can not be efficiently transferred to the graph domain directly, since it would lead to applying a GNN on the product graph with Onn2) nodes and (nz²) edges. Our algorithm also infers errors for the (sparse) product graph but performs the necessary computations on the original graphs.
Functional maps. The functional maps framework was proposed to provide a way to define con- tinuous maps between function spaces on manifolds and is commonly applied to solve the task of
21

---

Published as a conference paper at ICLR 2020
Table 7: Statistics of the WILLOW- OBJECTCLASS dataset.
Table Statistics of the DBP15K dataset.
Datasels
Entities
Relation types
Relations
Category
Graphs
Keypoints
Edges
Chinese English
19388
1701
70414
ZH++EN
3024
95.142
Face
108
10
21 22
Motorbike
40
10
21 22
JA++E
Japanese English
Car
40
10
18 21
19
2452
93484
Duck
50
10
19 - 21
French English
19661
903
105
FR++EN
Winebottle
66
10
19 - 22
19993
2111
115722
Table 9: Statistics of the PASCALVOC dataset with Berkeley annotations.
Category
Train graphs
Test graphs
Keypoints
Edges
Category
Train graphs
Test graphs
Keypoints
Edges
Aeroplane
Dininglable
Blcycle
210
53
2
11
26
Dog
608
147
1- 16
0 41
Bird
613
117
1- 12
0
30
Horse
217
45
2 16
1- 38
Boat
411
1-
25
Motorbike
234
1-10
0
Bottle
120
539
156
1-19
Bus
288
52
1 1-8
0
17
Pottedplant
429
99
1-6
0 11
Car
522
160
1- 13
0
27
Sheep
338
73
1-16
0 39
Sofa
Chair
298
1-
23
Train
166
1-6
10
Cow
257
55
1- 16
40
TV Monitor
374
90
1-8
17
3D shape correspondence (Osjanikov et al. 2012 Litany et al., 2017 Rodolà et al., 2017 Hal-
iii et al. 2019). Recently, similar approach was presented to find functional correspondences between graph function spaces (Wang et al. 2019a). The functional map is established by using a low-dimensional basis representation, e.g., the eigenbasis of the graph Laplacian as generalized Fourier transform. Since the basis is usually truncated to the k vectors with the largest eigenvalues, these approaches focus on establishing global correspondences. However, such global methods have the inherent disadvantage that they often fail to find partial matchings due to the domain-dependent eigenbasis. Furthermore, basis computation has to approximated in order to scale to large inputs.
H DATASET STATISTICS
We give detailed descriptions of all datasets used in experiments, ef Tables 7
8 and 10
I QUALITATIVE KEYPOINT MATCHING RESULTS
Figure visualizes qualitative examples from the task of keypoint matching the WILLOW-OBIES OWW-OBBECTLLSSS dataset. Examples were selected as follows: Figure 4(a) (b) and (c) show examples where the initial feature matching procedure fails, but where refinement proce- dure is able to recover all correspondences succesfully. Figure ((d) visualizes a rare failure case. However, while the initial feature matching procedure maps most of the keypoints the same tar- get keypoint, our refinement strategy still able to succesfully resolve this violation. In addition, note that the target image contains wrong labels, e.g., the eye of the duck, so that some keypoint mappings are mistakenly considered to be wrong.
22

---

Published as a conference paper at ICLR 2020
Table 10: Statistics of the PASCALPF dataset.
Category
Graphs
Pairs
Keypoints
Edges
Category
Graphs
Pairs
Keypoints
Edges
Acroplane
69
69
9
16
72
128
Diningtable
38
38
8
12 56
Bicycle
133
133
10- I1
80
88
Dog
106
106
5- 15
20
120
Bird
50
50
Horse
39
39
128
Boat
28
28
4-9
Motorbike
Bottle
42
42
4-8
12
56
Person
56
56
10 17
80 136
Bus
140
140
4-8
12
56
Pottedplant
35
35
4 6
12 30
Car
84
84
4-
12 88
Sheep
5 7
20 42
Cat
5-16
128
Sofa
59
59
Chair
59
59
Train
88
88
Cow
15
15
5
16
20
128
TV Monitor
65
65
6
12 30
S
S
0
S
S
(a) Motorbike
(b) Car
SOO)
S
S(L)
S
(c) Duck
(d) A rare failure
Figure 4: Qualitative examples from the HILLLO-OBJECTCL..E dataset. Images on the left represent the source, whereas images on the right represent the target. For each example, we visual- ize both the result of the initial feature matching procedure (10) (top) and the result obtained after refinement (L) (bottom).
23


Reviews:
[{"review_id": "Syg85NKpYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 suggests a framework for answering graph matching questions consisting of local node embeddings with a message passing refinement step.\n\nThe paper has well written text, offers what appear to be nice experiments validating the method and discusses its own limitations.\n\nI am giving a weak accept.  \n\nI the weak accept is my reflection of my inability to provide useful feedback.  This is also out of domain for me and I am not a useful reviewer for this paper.\n\nAs a general comment, I will say that the paper adopts a highly mathematical style that will be off putting to many readers.  Many of the expressions are 'high entropy'  For instance, the embedding network is given as $\\mathbf{\\Psi}_{\\theta_1}$ throughout.  This is seven levels of typographical distinction for the main character of the story.  This is a (1) bold (2) capital (3) Greek letter with a (4) subscript that is (5) greek with a (6) subscript that is (7) numeric.  I understand that each of these levels of distinction has a purpose and a meaning, but it is also arguably a much richer designation that is necessary.  Generally the paper feels like this, as if its being too unnecessarily specific.  Personally I found the paper rather difficult to read and decompose, which I believe does count against the paper.  The overly specific nature of paper will cut into its potential readership strongly.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HkgactQu9B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 proposed a message passing neural network-based graph matching methods. The overall framework can be viewed as a graph siamese network, where two set of points are passing through the same graph neural network, and then two new embeddings are generated. Using the two embedding the similarity between points can be computed and then the final matching can be generated. \n\nThe overall structure of this paper is similar to [1] and [2], the authors should discuss the difference of the proposed with these two papers, if it is possible, the authors may try to compare with these two methods in experiments. Currently, I think the main contribution of the paper should be the new message-passing scheme (in Sec. 3.2). However, from the current experiment, I can not see if the performance improvement is from the new message-passing scheme.\n\nIn fact, the message passing scheme is also related to the dual decomposition framework, which is previously used in the graph matching area. For example, in [3], a message-passing algorithm derived from dual decomposition is used to solve the graph matching problem. The authors may also consider add some discussion the difference between message-passing derived from dual decomposition and the message passing in the graph neural network.\n\n==================================== After Revision ==============================================\nIn the new experiment, the authors proved that the new message-passing scheme (i.e. the consensus stage) in Sec 3.2 can successfully improve the performance by refining original assignment. Thus I modify the score to weak accept.\n\n\n[1] Wang, Yue, and Justin M. Solomon. \"Deep Closest Point: Learning Representations for Point Cloud Registration.\", ICCV 2019,\n[2] Zhen Zhang, and Wee Sun Lee. \"Deep Graphical Feature Learning for the Feature Matching Problem.\", ICCV 2019\n[3] Paul Swoboda et. al. \"A study of Lagrangean decompositions and dual ascent solvers for graph matching.\", CVPR 2017", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkg1F6tZ5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 proposes a two-stage GNN-based architecture to establish correspondences between two graphs. The first step is to learn node embeddings using a GNN to obtain soft node correspondences between two graphs. The second step is to iteratively refine them using the constraints of matching consensus in local neighborhoods between graphs. The overall refining process resembles the classic graph matching algorithm of graduated assignment (Gold & Rangarajan, 1996), but generalizes it using deep neural representation. Experiments show that the proposed algorithm performs well on real-world tasks of image matching and knowledge graph entity alignment.\n\nThe paper is interesting and has some good potential but lacks some important evaluations and analyses. My main concerns are as follows. \n\n1) The consensus in the second stage is crucial? \nAs the title shows, the main technical contribution lies in the second stage of consensus inducing. But, for the real tasks, in the experiments, the gain by the second stage is not significant or often negligible (L=0 vs. L=10 or 20  in Table 1,2,3). The results of the first stage (L=0) already give better results than all the baselines in many cases, so that most gains appear to come from the usage of GNNs for representation. This makes the major contribution of this work less significant.  I hope the authors justify this. And, I guess that's maybe because the consensus information may also be induced in the first stage by matching nodes with relational presentations learned using a GNN. To see this, the authors may run the second stage only without the first stage. \n\n2) Comparison to the graduated assignment (GA) process\nAs discussed in 3.3, the proposed neighborhood consensus can be viewed as a generalization of GA of Eq.6 with trainable neural modules. But, it's not actually shown what is the gain by this generalization. This needs to be shown experimentally by substituting the second stage by GA process.  \n\n3) Robustness to node addition or removal. \nAll the experiments look assuming only edges are varied. Is this algorithm robust to node addition or removal, occurring in many practical graph matching problems? This needs to be also discussed.   \n\n======================================\n\nThe rebuttal succeeds in addressing most of my concerns so that I upgrade my initial rating to weak accept. I hope all the points in the rebuttal are included in the final manuscript. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed an end-to-end network architecture for graph matching problems, where first a GNN is applied to compute the initial soft correspondence, and then a message passing network is applied to attempt to resolve structural mismatch. The reviewers agree that the second component (message passing) is novel, and after the rebuttal period, additional experiments were provided by the authors to demonstrate the effectiveness of this. Overall this is an interesting network solution for graph-matching, and would be a worthwhile addition to the literature.
Decision: Accept (Poster)