# Topological phase transitions in strongly correlated systems: application to
Co3Sn2S2

V. Yu. Irkhin<EMAIL_ADDRESS>Yu. N. Skryabin  M. N. Mikheev
Institute of Metal Physics, 620108 Ekaterinburg, Russia

###### Abstract

The topological transition in the strongly correlated half-metallic
ferromagnetic compound Co3Sn2S2 from Weyl semimetal (including chiral massless
fermions) to a non-magnetic state is treated. This transition goes with a
change in topological invariant, and is accompanied by a non-topological
transition from saturated ferromagnetic to paramagnetic state, the minority
Fermi surface being transformed from ghost (hidden) to real. A corresponding
description is given in terms of slave fermion representation for the
effective narrow-band Hubbard model. The system Co3Sn2S2 provides a bright
example of coexistence of non-trivial topology and strong low-dimensional
ferromagnetism. A comparison is performed with other compounds where
frustrations result in formation of a correlated paramagnetic state.

##  1 Introduction

Recently, the layered kagome lattice compound Co3Sn2S2 has been a subject of
numerous experimental [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] and
theoretical [14, 15] investigations. In particular, giant topological
anomalous Hall effect was observed in this system [3, 6, 8]. Its electronic
structure contains Weyl points, Fermi arcs and nodal rings (Fig. 1), which
play an important role in the anomalous Hall effect [3, 8, 14].

Single-crystal experimental data on the Co3InxSn2-xS2 kagome system [18] show
that these systems have an almost two-dimensional itinerant magnetism and a
chiral spin state; in addition, a strongly correlated state with a high
electronic heat capacity is formed. The important role of correlations is
confirmed by a considerable enhancement of $\gamma T$-linear specific heat
even in the ferromagnetic phase [19, 18], especially at approaching the
magnetic-nonmagnetic critical point somewhat below $x=1$. At $x=1$, $\gamma$
vanishes, but strongly increases with further increasing $x$ [18].

The ferromagnetism in Co3Sn2S2 breaks time-reversal $T$-symmetry and is
necessary for the existence of topological Weyl points. The strongly
correlated metallic state in this system emerges as a result of magnetic
fluctuations. Above $T_{C}$, intrinsic magnetic field disappears, the Weyl
points annihilate and the Dirac points acquire a gap. This restores
$T$-symmetry and eliminates the topological behavior.

Figure 1: Schematic energy spectra for the Dirac semimetal (a), Weyl semimetal
(b), and nodal line semimetal (c), according to Refs.[16, 17].

A similar, but quantum transition occurs with disappearance of ferromagnetism
in the Co3InxSn2-xS2 system at the hole doping [6, 14]. The doping shifts the
Weyl nodes away from the Fermi level. For small doping, the nodal rings are
located around the Fermi energy, and for $x\sim 0.2$, the nodal lines
surrounding the L point in the Brillouin zone cross the Fermi surfaces (Fig.
2). With further increasing $x$, the nodal lines are split into two rings as
with the annihilation of Weyl points in the presence of the spin-orbit
coupling (the role of the latter is discussed in detail in Ref. [12]). For
$x>0.6$, the nodal lines are located far from the Fermi level, resulting in
the small Berry curvature on the whole Fermi surfaces [14]. At $x=1$ the
system becomes insulating [6]. According to [18], this anomalous nonmetallic
state may originate from the Fermi energy tuning through a Dirac point.

Figure 2: Schematic Fermi surfaces (solid green lines) for Co3Sn2S2 in the
$k_{x}-k_{z}$ plane at $k_{y}=0$ according to Ref.[14]. The thin black solid
line shows the nodal lines in the absence of spin-orbit coupling for (a)
$x=0.2$ and (b) $x=0.4$. The upper and lower triangles on the nodal lines in
(a) stand for the Weyl points with topological charges $+1$ and $-1$ in the
presence of spin-orbit coupling.

In the present work we treat the model picture of correlated half-metallic
ferromagnetism in Co3Sn2S2 and provide a description of these transitions
within the topological classification [20, 21, 22].

##  2 Half-metallic ferromagnetism and Weyl points in the effective Hubbard
model

The half-metallic ferromagnetism of Co3Sn2S2 occurs in the partially filled Co
3$d_{x^{2}-y^{2}}$ band which crosses the Fermi level. The itinerant magnetism
cannot be fully described by a simple one-electron approach including band
splitting. In particular, the persistence of local moments from in the Curie
Weiss susceptibility suggests a many-body correlated behavior [15]. The
associated moment of 1$\mu_{B}$ is spread over three Co atoms, in agreement
with the 0.33$\mu_{B}$ per Co magnetic moment from first-principle
calculations and the experimental moment which is slightly less than
1$\mu_{B}$/f.u. The configuration with five electrons and one hole results in
a spin-1/2 ferromagnetic state. This enables one to formulate a local Hubbard
model for the three Co atom cluster [15].

According to [15], across the magnetic transition, Co3Sn2S2 evolves from a
Mott ferromagnet to a correlated metallic state. In fact, the “Mott
ferromagnet” is a half-metallic ferromagnetic state, so that we have a partial
Mott transition in the minority spin subband. The physical reason of half-
metallic ferromagnetism in a wide doping region is the presence of Van Hove
singularity at the Fermi level, which is connected with quasi-two-dimensional
kagome structure (see Fig.2 in Ref. [14]). First-principle calculations [14]
and experimental data [6, 18] demonstrate that the doping in Co3InxSn2-xS2
system preserves half-metallic ferromagnetism with a linearly decreasing
magnetic moment.

The picture of half-metallic ferromagnetism can be qualitatively described by
the simplest narrow-band Hubbard model with large on-site repulsion $U$. In
this model, doubly occupied states (doubles) are absent owing to the Hubbard
splitting, but states with both spin projections are still present. Thus the
situation is different from the Stoner model where spin splitting becomes
infinitely large. The corresponding Hamiltonian reads

$\mathcal{H}_{\mathrm{H}}=\sum_{ij\sigma}t_{ij}\tilde{c}^{\dagger}_{i\sigma}\tilde{c}_{j\sigma}$
(1)

where

$\tilde{c}^{\dagger}_{i\sigma}=X_{i}(0,\sigma)=|i0\rangle\langle i\sigma|$ (2)

are the Hubbard projection operators describing motion of holes in the
correlated state on the background of magnetic moments. We can use the slave
fermion representation

$X_{i}(0,\sigma)=f_{i}^{\dagger}b_{i\sigma},\,X_{i}(+,-)=b^{\dagger}_{i\uparrow}b_{i\downarrow},$
(3)

where $f_{i}$ are fermions and $b_{i\sigma}$ are Schwinger boson operators
(cf. [23, 24]), so that

$\sum_{\sigma}b^{\dagger}_{i\sigma}b_{i\sigma}+f_{i}^{\dagger}f_{i}=1.$ (4)

In the saturated ferromagnetic state the $b_{i\uparrow}$ boson is condensed,
$\langle b_{i\uparrow}\rangle\simeq 1$, and $b_{i\downarrow}$ becomes magnon
annihilation operator.

Consider the hole Green’s functions for a saturated ferromagnet in the
representation (3).

$G_{\mathbf{k}\sigma}(E)=\langle\langle
X_{\mathbf{k}}(\sigma,0)|X_{\mathbf{-k}}(0,\sigma)\rangle\rangle_{E}.$ (5)

The spin-up (majority) states propagate freely on the background of strong
ferromagnetic ordering,

$G_{\mathbf{k}\uparrow}(E)=(E-t_{\mathbf{k}})^{-1}$ (6)

with $t_{\mathbf{k}}$ the bare band spectrum. For our system, these possess an
exotic spectrum of chiral Weyl fermions in the internal field owing to
ferromagnetic ordering of local moments. This just leads to unusual
topological properties.

The spin down (minority) Green’s function in the leading approximation is
obtained as a convolution of the Green’s functions for free fermions and
bosons, so that

$G_{\mathbf{k}\downarrow}(E)=\sum_{\mathbf{q}}\frac{N_{B}(\omega_{\mathbf{q}})+f(t_{\mathbf{k}+\mathbf{q}})}{E-t_{\mathbf{k}-\mathbf{q}}+\omega_{\mathbf{q}}}$
(7)

where $N_{B}(\omega)$ and $f(E)$ are the Bose and Fermi functions,
$\omega_{\mathbf{q}}$ is the magnon spectrum. Similar results for a Hubbard
ferromagnet were obtained earlier in the many-electron representation of
X-operators [25, 26], the analogy with Anderson’s spinons [27] being
discussed.

The Green’s function (7) has a purely non-quasiparticle nature. Because of
very weak $\mathbf{k}$-dependence of the corresponding distribution function
the non-quasiparticle (incoherent) states do not carry current. As demonstrate
more exact calculations [26], at small doping the spin down Green’s function
(3) has no poles above the Fermi level of holes $E_{F}$, so that the above
conclusions are not changed. However, with increasing doping, it can acquire a
spin-polaron pole above $E_{F}$, and the half-metallic ferromagnetism is
destroyed (Fig.3).

Figure 3: Schematic picture of the density of states in the narrow-band
Hubbard model illustrating the doping-induced Lifshitz transition, the data
are from Ref. [29]. Dashed line is the bare (and also spin-up) density of
states, solid and dot-dashed lines are the spin-down densities of states for
the half-metallic and usual ferromagnetic states.

Despite such unusual properties, the minority states cannot be fully
neglected. In fact, their number is equal to the number of majority states
$n_{0}$ owing to the sum rule

$\sum_{\mathbf{k}}\langle
X_{\mathbf{-k}}(0,\sigma)X_{\mathbf{k}}(\sigma,0)\rangle=\langle
X_{i}(0,0)\rangle=n_{0}$ (8)

for both projections $\sigma$ (which is satisfied in the approximation (7)),
so that the current carriers (Hubbard’s holes) are in a sense spinless (see
Fig.3: the corresponding areas below the Fermi level determining the
occupations numbers are nearly equal). The minority states in the ground state
are absent at the Fermi surface and occur there at finite temperatures owing
to thermal magnon excitations. The physics does not qualitatively change in
the case of finite Hubbard $U$, since the doubles are automatically eliminated
in the saturated half-metallic state [26].

The description of the transition to the half-metallic state (vanishing of the
quasiparticle residue for one spin projection) is similar to that of the Mott
transition in the paramagnetic Hubbard model [28]. Here, the Fermi surface
becomes ghost (hidden) after the metal-insulator transition in the insulating
(Mott) phase, and the fractionalization of electron states occurs, including
spin-charge separation into a neutral fermion (spinon) and charged boson
(holon). Our situation can be described as a partial Mott transition in the
minority spin subband, cf. the discussion of the orbital-selective Mott
transition [30].

The electron states in a strongly correlated system need not to have purely
quasiparticle nature. They can be described by both poles and branch cuts of
the Green’s function. For minority states, the quasiparticle residue $Z$ is
completely suppressed, which means formation of the energy gap and takes
place, e.g., for the Mott transition [20]. The violation of the standard
Fermi-liquid picture can be described in terms of the formation of the
Luttinger surface which is the surface of zeros of the electron Green’s
function.

The Lifshitz transitions with vanishing quasiparticle poles can be viewed as
quantum phase transitions with a change of the topology of the Fermi surface,
but without symmetry breaking. Indeed, the Fermi surface itself is the
singularity in the Green’s function, which is characterized by topological
invariant $N_{1}$ and topologically protected: it is the vortex line in the
frequency-momentum space [20, 21]. In the gapped phase, usual Fermi surface
does not exist, but its topology is preserved if we take into account the
Luttinger contribution. Then the Luttinger theorem (the conservation of the
volume enclosed by the Fermi surface) is still valid [20]. Thus the Fermi
surface becomes ghost (hidden) in the Mott phase for both spin projections and
in our half-metallic situation for minority states, since the Fermi level lies
in the corresponding gap.

On the contrary, the transition with disappearance of the Weyl points is
essentially topological: topological invariants are changed. In the Weyl
semimetal phase, the Weyl points have topological charges $N_{3}=+1$ and $-1$
and annihilate in the critical Dirac semimetal. Further on, in the normal
paramagnetic state the topology owing to the Berry curvature vanishes. Thus
the conservation law for the topological charge [20] is fulfilled. In the
insulator case, we have a transition from topological to normal insulator with
restoring time-reversal symmetry. A still more complicated situation occurs in
the case of Chern insulators with a change of the Chern number [31, 7, 32].

At the hole doping in the Co3InxSn2-xS2 system, suppression of ferromagnetism
is also accompanied with decreasing the Berry curvature, and in the
paramagnetic phase both the Weyl points and nodal rings vanish [14].

##  3 Discussion

As stated in Ref. [15], the topological properties and strong correlations in
Co3Sn2S2 are intricately linked, so that one cannot be adequately considered
without the other. The scanning tunnelling microscopy data in Co3Sn2S2
demonstrated a pronounced peak at the Fermi level, which was identified as
arising from the kinetically frustrated kagome flat band [9]. The occurrence
of an electronic band connecting the two Weyl cones and flattened by
electronic correlations was demonstrated in Ref. [10], the Coulomb-interaction
strength being estimated as $U\sim 4$ eV.

The electron correlations in pyrochlore iridates $R_{2}$Ir2O7 were discussed
by first-principle calculations in Ref. [33]. Depending on the strength of
correlations $U$, a Mott insulating phase with a magnetic structure or Weyl
semimetal phase with Weyl points at the Fermi energy were treated. A variety
of phases ranging from normal metal at small $U$ to Weyl semimetal at
intermediate $U\sim$ 1.5 eV and Mott insulating phase at $U$ above 2 eV with
non-collinear magnetic all-in/all-out ordering were predicted. The giant
anomalous Hall effect is observed in Nd2Mo2O7, a pyrochlore ferromagnet with
geometrically frustrated lattice structure, is mostly due to the spin
chirality and the associated Berry phase originating from the Mo spin tilting
[34]. However, the situation in pyrochlores with strong spin-orbit coupling
differs from half-metallic ferromagnetism.

We have demonstrated that in the half-metallic ferromagnetic state Hubbard
correlations do not result in narrowing of bare bands for majority states, but
in the paramagnetic state the situation changes: we come to the regime of
narrow correlated bands for both spin projections. These may be characterized
either by strongly renormalized quasiparticle residue, or even by a non-Fermi-
liquid (e.g., marginal Fermi-liquid [28]) behavior. Besides absence of
$T$-breaking internal magnetic field in the paramagnetic phase, this can be
important for vanishing of topological effects.

Since magnetic frustration effects in the kagome lattice should play a role,
the magnetic structure of Co3Sn2S2 is to be discussed in more detail.
According to [13], at finite temperatures this includes the out-of-plane
ferromagnetism, in-plane antiferromagnetism, and hidden phases. A metastable
magnetic phase exists in some interval $T_{com}<T<T_{C}$. The corresponding
values of transition temperatures are $T_{C}=182$ K, $T_{N}=177$ K, and
$T_{com}=150$ K. The out-of-plane magnetization of Co3Sn2S2-xSex demonstrates
a first-order phase transition, which may again indicate strong half-metallic
magnetism. This may also important for a combined description of the non-
topological ferromagnetic and topological transitions. A possibility of a
chiral spin state is discussed in [18].

From the $\mu$SR measurements, the ground ferromagnetic state with moment
along c axis exists in Co3Sn2S2 below $T^{*}_{C}$ = 90 K, and a coexistence of
the ferromagnetic order and an in-plane 120∘ antiferromagnetic order was
proposed at $T>T^{*}_{C}$ [11] (see, however, Ref.[35]). The antiferromagnetic
volume fraction grows with increasing temperature and dominates around 170 K,
before it disappears at $T_{C2}=172$ K. Above $T_{C2}$, the sample has the
small volume fraction with the out-of-plane ferromagnetic order, the rest of
the volume being occupied by the paramagnetic state up to $T_{C1}=177$ K. The
temperature-dependent magnetic fraction shows a rather sharp transition
between the paramagnetic and magnetic states with the coexistence of their
regions in the interval $T_{C2}<T<T_{C1}$.

Thus, although frustrations in Co3Sn2S2 seem to be important, they turn out to
be insufficient for formation of a paramagnetic spin-liquid-like state. The
situation seems to be different for the correlated kagome systems YCr6Ge6 [36]
and Na2/3CoO2 [37] without magnetic ordering.

Besides pyrochlores, comparison can be made with other three-dimensional
systems. Two topological Weyl cones with band crossing points were identified
around the X point for the Heusler alloy Co2MnGe, which can induce large
anomalous Hall effect owing to the Berry flux in the half-metallic ferromagnet
structure [38].

To conclude, Co3Sn2S2 provides a bright example of coexistence of non-trivial
topology and half-metallic ferromagnetism in a quasi-two-dimensional system.
Both these factors are important for non-usual phase transitions and anomalies
of electronic properties, including giant anomalous Hall effect.

The authors are grateful to A. V. Zarubin for the help in preparing the
manuscript. The research was carried out within the state assignment of FASO
of Russia (theme “Flux” No AAAA-A18-118020190112-8 and theme “Quantum” No.
AAAA-A18-118020190095-4).

## References

  * [1] Q. Wang, Y. Xu, R. Lou, Zh. Liu, M. Li, Y. Huang, D. Shen, H. Weng, Sh. Wang, H. Lei, Nature Comm. 9, 3681 (2018).
  * [2] Q. Xu, E. Liu, W. Shi, L. Muechler, J. Gayles, C. Felser, and Y. Sun, Phys. Rev. B 97, 1 (2018).
  * [3] E. Liu, Y. Sun, N. Kumar, L. Muechler, A. Sun, L. Jiao, Sh.-Y. Yang, D. Liu, A. Liang, Q. Xu, J. Kroder, V. Seuss, H. Borrmann, Ch. Shekhar, Zh. Wang, Ch. Xi, W. Wang, W. Schnelle, S. Wirth, Y. Chen, S. T. B. Goennenwein and C. Felser, Nature Phys. 14, 1125 (2018).
  * [4] D. F. Liu, A. J. Liang, E. K. Liu, Q. N. Xu, Y. W. Li, C. Chen, D. Pei, W. J. Shi, S. K. Mo, P. Dudin, T. Kim, C. Cacho, G. Li, Y. Sun, L. X. Yang, Z. K. Liu, S. S. P. Parkin, C. Felser, and Y. L. Chen, Science 365, 1282 (2019).
  * [5] L. Jiao, Q. Xu, Y. Cheon, Y. Sun, C. Felser, E. Liu, and S. Wirth, Phys. Rev. B 99, 1 (2019).
  * [6] H. Zhou, G. Chang, G. Wang, X. Gui, X. Xu, J.-X. Yin, Z. Guguchia, S. S. Zhang, T.-R. Chang, H. Lin, W. Xie, M. Z. Hasan, Sh. Jia, Phys. Rev. B101, 125121 (2020).
  * [7] L. Muechler, E. Liu, J. Gayles, Q. Xu, C. Felser, Y. Sun, Phys. Rev. B 101, 115106 (2020).
  * [8] M. Tanaka, Y. Fujishiro, M. Mogi, Y. Kaneko, T. Yokosawa, N. Kanazawa, S. Minami, T. Koretsune, R. Arita, S. Tarucha, M. Yamamoto, and Y. Tokura, Nano Lett. 20, 7476 (2020).
  * [9] J.-X. Yin, S. S. Zhang, G. Chang, Q. Wang, S. S. Tsirkin, Z. Guguchia, B. Lian, H. Zhou, K. Jiang, I. Belopolski, N. Shumiya, D. Multer, M. Litskevich, T. A. Cochran, H. Lin, Z. Wang, T. Neupert, Sh. Jia, H. Lei and M. Z. Hasan, Nature Physics 15, 443 (2019).
  * [10] Y. Xu, J. Zhao, C. Yi, Q. Wang, Q. Yin, Y. Wang, X. Hu, L. Wang, E. Liu, G. Xu, L. Lu, A. A. Soluyanov, H. Lei, Y. Shi, J. Luo, and Z. Chen, Nat. Commun. 11, 3985 (2020).
  * [11] Z. Guguchia, J. A. T. Verezhak, D. J. Gawryluk, S. S. Tsirkin, J.-X. Yin, I. Belopolski, H. Zhou, G. Simutis, S.-S. Zhang, T. A. Cochran, G. Chang, E. Pomjakushina, L. Keller, Z. Skrzeczkowska, Q. Wang, H. C. Lei, R. Khasanov, A. Amato, S. Jia, T. Neupert, H. Luetkens, and M. Z. Hasan, Nat. Commun. 11, 559 (2020).
  * [12] D. F. Liu, E. K. Liu, Q. N. Xu, J. L. Shen, Y. W. Li, D. Pei, A. J. Liang, P. Dudin, T. K. Kim, C. Cacho, Y. F. Xu, Y. Sun, L. X. Yang, Z. K. Liu, C. Felser, S. S. P. Parkin, Y. L. Chen, arXiv:2103.08113.
  * [13] D.-H. Shin, J.-H. Jun, S.-E. Lee, M.-H. Jung, arXiv:2105.03892.
  * [14] Y. Yanagi, J. Ikeda, K. Fujiwara, K. Nomura, A. Tsukazaki, M.-T. Suzuki, Phys. Rev. B 103, 205112 (2021).
  * [15] A. Rossi, V. Ivanov, S. Sreedhar, A. L. Gross, Z. Shen, E. Rotenberg, A. Bostwick, Ch. Jozwiak, V. Taufour, S. Y. Savrasov, I. M. Vishik, Phys. Rev. B 104, 155115 (2021).
  * [16] M. Koshino and I. F. Hizbullah, Phys. Rev. B 93, 045201 (2016).
  * [17] N.P. Armitage, E. J. Mele, A. Vishwanath, Rev. Mod. Phys. 90, 15001 (2018).
  * [18] M. A. Kassem, PhD Dissertation (Kyoto Univ., 2016).
  * [19] W. Schnelle, A. Leithe-Jasper, H. Rosner, F. M. Schappacher, R. Poettgen, F. Pielnhofer, and R. Weihrich, Phys. Rev. B 88, 144404 (2013).
  * [20] G. E. Volovik, Phys. Usp. 61, 89 (2018).
  * [21] G. E. Volovik, Lect. Notes Phys. 718, 31, 2007; arXiv:cond-mat 0601372.
  * [22] K. Zhang and G. E. Volovik, JETP Lett.105, 519 (2017).
  * [23] C. L. Kane, P. A. Lee, N. Read, Phys. Rev. B39, 6880 (1989).
  * [24] V. Yu. Irkhin, Yu. N. Skryabin, JETP Lett. 106, 167 (2017).
  * [25] V. Yu. Irkhin and M. I. Katsnelson, Sov. Phys. - Solid State 25, 1947 (1983).
  * [26] V. Yu. Irkhin and M.I. Katsnelson, J. Phys.: Cond. Mat. 2, 7151 (1990).
  * [27] P. W. Anderson, Int. J. Mod. Phys. B4, 181 (1990).
  * [28] T. Senthil, Phys. Rev. B 78, 045109 (2008).
  * [29] V. Yu. Irkhin, A. V. Zarubin, Phys. Rev. B 70, 035116 (2004).
  * [30] M. Vojta, Rep. Prog. Phys. 81, 064501 (2018).
  * [31] M. Z. Hasan, C. L. Kane, Rev. Mod. Phys. 82, 3045 (2010).
  * [32] V. Yu. Irkhin, Yu. N. Skryabin, J. Exp. Theor. Phys. 133, 116 (2021).
  * [33] X. Wan, A. M. Turner, A. Vishwanath, and S. Y. Savrasov, Phys. Rev. B 83, 205101 (2011).
  * [34] Y. Taguchi, H. Oohara, N. Yoshizawa, Y. Nagaosa, and Y. Tokura, Science 291, 2573 (2001).
  * [35] J.-R. Soh, Ch. J. Yi, I. Zivkovic, N. Qureshi, A. Stunault, B. Ouladdiaf, J. A. Rodríguez-Velamazán, Y. Shi, A. T. Boothroyd, arXiv:2110.00475.
  * [36] T. Y. Yang, Q. Wan, Y. H. Wang, M. Song, J. Tang, Z. W. Wang, H. Z. Lv, N. C. Plumb, M. Radovic, G. W. Wang, G. Y. Wang, Z. Sun, R. Yu, M. Shi, Y. M. Xiong, N. Xu, arXiv:1906.07140 (2019).
  * [37] I.F. Gilmutdinov, R. Schoenemann, D. Vignolles, C. Proust, I.R. Mukhamedshin, L. Balicas, H. Alloul, arXiv:2101.05252.
  * [38] T. Kono, M. Kakoki, T. Yoshikawa, X. Wang, K. Goto, T. Muro, R. Y. Umetsu, A. Kimura, Phys. Rev. Lett. 125, 216403 (2020).


# Joint Deep Multi-Graph Matching and 3D Geometry Learning
from Inhomogeneous 2D Image Collections

Zhenzhang Ye, Tarun Yenamandra, Florian Bernard, Daniel Cremers
Technical University of Munich
{zz.ye, tarun.yenamandra, f.bernard<EMAIL_ADDRESS>
###### Abstract

Graph matching aims to establish correspondences between vertices of graphs
such that both the node and edge attributes agree. Various learning-based
methods were recently proposed for finding correspondences between image key
points based on deep graph matching formulations. While these approaches
mainly focus on learning node and edge attributes, they completely ignore the
3D geometry of the underlying 3D objects depicted in the 2D images. We fill
this gap by proposing a trainable framework that takes advantage of graph
neural networks for learning a deformable 3D geometry model from inhomogeneous
image collections, i.e. a set of images that depict different instances of
objects from the same category. Experimentally we demonstrate that our method
outperforms recent learning-based approaches for graph matching considering
both accuracy and cycle-consistency error, while we in addition obtain the
underlying 3D geometry of the objects depicted in the 2D images.

Previous approach [55] Our proposed approach Sparse non-rigid geometry 3D
reconstruction

Figure 1: We consider a deep graph matching approach for bringing 2D image key
points into correspondence. Left: Existing deep graph matching methods
completely ignore the underlying 3D geometry of the 3D objects depicted in the
2D images. In addition, they lead to cycle errors, as shown by the red line.
Middle: Our method obtains the underlying 3D geometry from a collection of
inhomogeneous 2D images (indicated by the coloured points and the bike sketch
in the centre), while at the same time guaranteeing cycle consistency. Right:
To model nonlinear 3D object deformations, we infer coarse 3D geometry and in
addition use a 3D deformation module to refine the underlying 3D geometry
based on the 2D image key point observations.

##  1 Introduction

Graph matching is a widely studied problem in computer vision, graphics and
machine learning due its universal nature and the broad range of applications.
Intuitively, the objective of graph matching is to establish correspondences
between the nodes of two given weighted graphs, so that the weights of
corresponding edges agree as well as possible. Diverse visual computing tasks
fit into the generic graph matching framework. In this work we focus in
particular on the task of matching 2D key points defined in images, which has
a high relevance for 3D reconstruction, tracking, deformation model learning,
localisation, and many more. In this case, a graph is constructed for each
image by using the key points as graph nodes, and by connecting neighbouring
key points with edges, according to some suitable neighbourhood criterion. The
edges typically contain information about geometric relations, such as the
Euclidean distance between nodes in the simplest case.

Image key point matching was traditionally addressed based on finding nearest
neighbours between feature descriptors such as SIFT [33], SURF [3] or learned
features [23]. A downside to this approach is that the geometric relation
between the key points are completely ignored, which is in particular
problematic if there are repetitive structures that lead to similar feature
descriptors. Instead, we can use a graph matching formulation to establish
correspondences between key points while taking into account geometric
relations between points. Yet, the sequential nature of first computing
features and then bringing them into correspondence may lead to sub-optimal
results, since both tasks are solved independently from each other – despite
their mutual dependence. More recently, several deep learning-based graph
matching methods have been proposed that learn task-specific optimal features
while simultaneously solving graph matching in an end-to-end manner [58, 51,
55, 41]. While such deep graph matching approaches lead to state-of-the-art
results in terms of the matching accuracy, they have profound disadvantages,
particularly in the context of 2D key point matching in image collections. On
the one hand, most existing approaches only consider the matching of pairs of
images, rather than the entire collection. This has the negative side-effect
that so-obtained matchings are generally not cycle-consistent, i.e. matching
image A via B to C may be different than matching image A directly to C. To
circumvent this, there are approaches that use a post-processing procedure
[52] to establish cycle consistency based on permutation synchronisation [6,
37]. Yet, they do not directly obtain cycle-consistent matchings but rather
achieve it based on post-processing. On the other hand, and perhaps more
importantly, approaches that use graph matching for 2D image key point
matching have the strong disadvantage that the underlying 3D structure of the
objects whose 2D projections are depicted in the images is not adequately
considered. In particular, the spatial relations in the 2D image plane are
highly dependent on the 3D geometric structure of the object, as well as on
the camera parameters. Hence, learning graph features directly based on the
image appearance and/or 2D image coordinates is sub-optimal, at best, since
the neural network implicitly needs to learn the difficult task of reasoning
about the underlying 3D structure.

In this work we address these issues by proposing a deep multi-graph matching
approach that simultaneously learns the 3D structure of objects. We summarise
our main contributions as follows:

  * •

For the first time we propose a solution for jointly considering deep multi-
graph matching and inferring sparse 3D geometry from inhomogeneous 2D image
collections, see Fig. Joint Deep Multi-Graph Matching and 3D Geometry Learning
from Inhomogeneous 2D Image Collections.

  * •

To effectively deal with the inhomogeneity of the image collection, in which
different instances of objects of the same category are present (e.g.
different types of bikes as shown in Fig. Joint Deep Multi-Graph Matching and
3D Geometry Learning  from Inhomogeneous 2D Image Collections), we introduce a
novel deformable 3D model that we directly learn from the image collection
based on a graph neural network.

  * •

Rather than performing pairwise image-to-image matching, we consider an image-
to-deformable-3D-model matching formulation that by construction guarantees
cycle consistency.

  * •

Our approach substantially outperforms the previous state of the art in
learning-based graph matching approaches considering accuracy and cycle error
simultaneously.

##  2 Related Work

In the following we summarise the works that we consider most relevant to our
approach. For a more detailed background on image key point matching we refer
interested readers to the recent survey paper [34].

Feature-Based Matching. Feature descriptors extracted from images at key point
locations, e.g. based on SIFT [33], SURF [3], or deep neural networks [23],
are often used for image matching. In order to bring extracted features into
correspondence, commonly a nearest neighbour strategy [4] or a linear
assignment problem (LAP) [13] formulation are used. However, these methods
suffer from the problem that geometric relation between the key points in the
images are not taken into account.

Graph Matching and Geometric Consistency. Geometric relations can be taken
into account by modelling feature matching as graph matching problem. Here,
the image key points represent the graph nodes, and the edges in the graph
encode geometric relations between key points (e.g. spatial distances).
Mathematically, graph matching can be phrased in terms of a quadratic
assignment problem [24, 38, 30, 13]. There are many existing works for
addressing the graph matching problem in visual computing, including [17, 61,
45, 18, 5, 45]. A drawback of these approaches is that they mostly rely on
handcrafted graph attributes and/or respective graph matching cost functions
based on affinity scores. In [59], a learned-based approach that directly
obtains affinity scores from data was introduced. More recently, the
differentiation of the power iteration method has been considered in a deep
graph matching approach [58]. A more general blackbox differentiation approach
was introduced in [41]. Various other deep learning approaches have been
proposed for graph matching [28, 20], and some approaches also address image
key point matching [51, 60, 55]. In this case, optimal graph features are
directly learned from the image appearance and/or 2D image coordinates, while
simultaneously solving graph matching in an end-to-end manner. Although these
methods consider geometric consistency, they are tailored towards matching a
pair of graphs and thus lead to cycle-inconsistent matchings when pairwise
matchings of more than two graphs are computed.

Synchronisation and Multi-Matching. Cycle-consistency is often obtained as a
post-processing step after obtaining pairwise matchings. Methods that
establish cycle consistency in the set of pairwise matchings are commonly
referred to as permutation synchronisation methods [37, 62, 35, 6, 8]. There
are also methods for directly obtaining cycle-consistent multi-matchings [49,
50, 7]. Recently, permutation synchronisation has also been considered in a
deep graph matching framework, where a separate permutation synchronisation
module is utilised to generalise a two-graph matching approach to the matching
of multiple graphs [52]. However, when applying such multi-matching approaches
to image key point matching they have the significant shortcoming that they
ignore the underlying 3D geometry of the 2D points. This makes it extremely
difficult to establish correct matchings across images, which after all depict
2D projections of 3D objects in different poses, possibly even under starkly
varying perspective projections.

3D Reconstruction. Obtaining 3D geometric information from 2D data is a widely
studied problem known as 3D reconstruction. When relying on a monocular input
only, 3D reconstruction is generally an ill-posed problem. To circumvent this,
statistical 3D models [9, 32, 39] are commonly used as priors in such
reconstruction tasks. Reconstruction from a single image or video using a
deformable 3D prior has for example been achieved by fitting a 3D morphable
model of a specific object class such as humans bodies, faces, or cars, and
then finding the parameters of the model that best explain the image [47, 10,
53]. However, the availability of a suitable 3D prior is a rather strong
assumption.

Video-based methods are able to utilise temporal information and temporal
consistency constraints to reconstruct dynamic scenes. For the specific object
class of faces, recently a method was proposed that is able to simultaneously
learn a 3D face prior model while performing 3D reconstruction [46]. There are
also some methods that do not assume explicit 3D prior models, but they
exploit different geometric and photometric properties of 3D shapes to
reconstruct 3D information from images [21, 48, 56].

An alternative to address the ill-posedness of single-view reconstruction is
to consider multiple views. Traditional static scene reconstruction methods
use a collection of images from one or many cameras to match the images,
obtain camera parameters, and reconstruct an object [43, 42, 1].

More recent methods for multi-view reconstruction assume camera parameters and
use self-supervised learning based on a neural renderer to reconstruct static
and dynamic objects with novel 3D representations [36, 40, 31, 44]. A downside
of multi-view reconstruction methods is that they require many different
images of the same object, which is often hard to obtain and unavailable in
existing datasets.

Contrary to existing approaches, we simultaneously solve deep multi-graph
matching and infer sparse 3D geometry fromi nhomogeneous 2D image collections.
In particular, our approach obtains cycle-consistent multi-matchings and does
not rely on a hand-crafted template or any other prior 3D model.

##  3 Problem Formulation & Preliminaries

Symbol | Meaning
---|---
$N$ | number of graphs/images
$m_{j}$ | number of vertices in $j$-th graph $\mathcal{G}_{j}$
$d$ | number of vertices in universe graph $\mathcal{U}$
$X_{jk}$ | pairwise matching between $\mathcal{G}_{j}$ and $\mathcal{G}_{k}$
$X_{j}$ | matching between $\mathcal{G}_{j}$ and $\mathcal{U}$
$U$ | homogeneous coordinates of universe points
$\mathcal{V}_{j}$ | homogeneous coordinates of pixels in $j$-th image
$j,k,l$ | indices used to refer to images and graphs
$i$ | index used to refer to the $i$-th point

Table 1: Overview of our notation.

In this section we summarise how to achieve cycle-consistency for multiple
graph matching by utilising the notion of universe points. In order to
explicitly construct such universe points, we formalise it as a sparse
reconstruction of the 3D key points from multiple 2D images.

###  3.1 Multi-Matching and Cycle Consistency

Given is the set $\\{\mathcal{G}_{j}\\}_{j=1}^{N}$ of $N$ undirected graphs,
where each graph $\mathcal{G}_{j}=(\mathcal{V}_{j},\mathcal{E}_{j})$ comprises
of a total of $m_{j}$ nodes $\mathcal{V}_{j}=\\{v_{1},\dots,v_{m_{j}}\\}$ and
a total of $n_{j}$ edges $\mathcal{E}_{j}=\\{e_{1},\dots,e_{n_{j}}\\}$ that
connect pairs of nodes in $\mathcal{V}_{j}$. We assume that each node
represents an image key point, and that the node $v_{i}\in\mathbb{R}^{2}$ is
identified with the respective 2D image coordinates. The pairwise graph
matching problem is to find a node correspondence
$X_{jk}\in\mathbb{P}_{m_{j}m_{k}}$ between $\mathcal{G}_{j}$ and
$\mathcal{G}_{k}$. Here, $\mathbb{P}_{m_{j}m_{k}}$ is the set of
$(m_{j}{\times}m_{k})$-dimensional partial permutation matrices.

Let $\mathcal{X}=\\{X_{jk}\in\mathbb{P}_{m_{j}m_{k}}\\}_{j,k=1}^{N}$ be the
set of pairwise matching between all graphs in
$\\{\mathcal{G}_{j}\\}_{j=1}^{N}$. The set $\mathcal{X}$ is said to be cycle-
consistent if for all $j,k,l\in\\{1,\dots,N\\}$, the following three
properties hold [22, 49, 6]:

  1. 1.

$X_{jj}=\mathbb{I}_{m_{j}}$, where $\mathbb{I}_{m_{j}}$ denotes the identity
matrix of size $m_{j}$.

  2. 2.

$X_{jk}=X_{kj}^{T}$.

  3. 3.

$X_{jk}X_{kl}\preceq X_{jl}$ (element-wise).

When solving multi-graph matchings in terms of pairwise matching, cycle
consistency is desirable since it is an intrinsic property of the (typically
unknown) ground truth matching. Rather then explicitly imposing the above
three constraints, it is possible to achieve cycle consistency by representing
the pairwise matching in terms of a universe graph [22, 49, 6]:

###### Lemma 1

The set $\mathcal{X}$ of pairwise matchings is cycle-consistent, if there
exists a collection
$\\{X_{j}\in\mathbb{P}_{m_{j}d}:X_{j}\mathbf{1}_{d}=\mathbf{1}_{m_{j}}\\}_{j=1}^{N}$
such that for each $X_{jk}\in\mathcal{X}$ it holds that
$X_{jk}=X_{j}X_{k}^{T}$.

Here, the $X_{j}$ can be considered as the pairwise matching between the graph
$\mathcal{G}_{j}$ and a universe graph $\mathcal{U}=(\mathcal{V},\mathcal{E})$
with similar definition to $\mathcal{G}_{j}$, where
$\mathcal{V}=\\{u_{1},\dots,u_{d}\\}$ denote the universe points and
$\mathcal{E}=\\{e_{1},\dots,e_{n}\\}$ the universe edges. Intuitively, the
universe graph can be interpreted as assigning each point in $\mathcal{G}_{j}$
to exactly one of the $d$ universe points in $\mathcal{U}$. Therefore, rather
than modelling the cubic number of cycle consistency constraints on
$\\{\mathcal{G}_{j}\\}_{j=1}^{N}$ explicitly, we use an object-to-universe
matching formulation based on the $\\{X_{j}\\}_{j=1}^{N}$.

###  3.2 3D Reconstruction

Though the idea of the universe graph is a crucial ingredient for
synchronisation approaches [37, 22, 6], the universe graph is never explicitly
instantiated in these methods. That is because it is merely used as an
abstract entity that must exist in order to ensure cycle consistency in multi-
matchings. Considering that the graphs in this work come from image
collections, we assume that the nodes $u_{i}\in\mathbb{R}^{3}$ of the universe
graph represent 3D points, which will allow us to address their explicit
instantiation based on multiple-view geometry.

We denote the homogeneous coordinate representation of the universe point
$u_{i}\in\mathbb{R}^{3}$ (represented in world coordinates) as
$U_{i}=(u_{i},1)\in\mathbb{R}^{4}$. Its projection onto the $j$-th image
plane, denoted by $\mathcal{V}_{ij}=(v_{ij},1)\in\mathbb{R}^{3}$, is given by

$\mathcal{V}_{ij}=\lambda_{ij}K_{j}\underbrace{\left(\begin{matrix}1&0&0&0\\\
0&1&0&0\\\
0&0&1&0\end{matrix}\right)}_{\Pi_{0}}\underbrace{\left(\begin{matrix}R_{j}&T_{j}\\\
0&1\end{matrix}\right)}_{g_{j}}U_{i}.$ (1)

Here, $g_{j}$ represents the world-to-camera space rigid-body transformation
comprising of the rotation $R_{j}\in\mathbb{R}^{3\times 3}$ and the
translation $T_{j}\in\mathbb{R}^{3}$, $\Pi_{0}$ is the canonical projection
matrix, $K_{j}\in\mathbb{R}^{3\times 3}$ is the intrinsic camera matrix, and
$\lambda_{ij}\in\mathbb{R}$ is the scale parameter. For brevity, we define the
general projection matrix $\Pi_{j}=K_{j}\Pi_{0}g_{j}$. Let
$U\in\mathbb{R}^{4\times d}$ be the stacked universe points in homogeneous
coordinates, let $\mathcal{V}_{j}\in\mathbb{R}^{3\times d}$ be the respective
projection onto the $j$-th image plane $j$, and let
$\Lambda_{j}=\operatorname{diag}(\lambda_{1j},\ldots,\lambda_{dj})\in\mathbb{R}^{d\times
d}$ be the diagonal matrix with the $\lambda_{ij}$ on its diagonal. The matrix
formulation of Eq. (1) is

$\mathcal{V}_{j}=\Pi_{j}U\Lambda_{j}.$ (2)

Once we have a collection of $N$ images of different objects from the same
category (not necessarily the same object instance, e.g. two images of
different bicycles), reconstructing the universe points $U$ can be phrased as
finding the minimiser of the least-squares problem

$\displaystyle\operatorname{arg\,min}_{U}\sum_{j=1}^{N}||\Pi_{j}U\Lambda_{j}-\mathcal{V}_{j}||_{F}^{2}.$
(3)

Note that in practice the variables $U,\\{\Lambda_{j}\\}$ and $\\{\Pi_{j}\\}$
are generally unknown, so that without further constraints this is an under-
constrained problem. In the next section, we will elaborate on how we approach
this.

Figure 2: Overview of our algorithm. Given an image with features, we predict
the corresponding features in 3D as a combination of universe 3D points and
deformations. The universe 3D points are learned during training for a given
class of objects, while the deformations are predicted per image. We create
edges for among the 2D and 3D features and find a matching between the two
graphs using a graph matching network. Since the matchings are between
universe points and images, our algorithm is cycle consistent.

##  4 Proposed Method

Our learning framework consists of four main components. The first two
components have the purpose to obtain 3D universe points, along with a
deformation of these 3D points representing the underlying 3D structure of the
2D key points in the $j$-th image. The purpose of the other two components is
to predict the matching between the 2D points of $\mathcal{G}_{j}$ and the 3D
points of $\mathcal{U}$. Thus, rather than learning pairwise matchings between
$\mathcal{G}_{j}$ and $\mathcal{G}_{k}$, we utilise an object-to-universe
matching formulation. Therefore, the underlying 3D structure and cycle-
consistent multi-matchings are both attained by our method. The whole pipeline
is illustrated in Fig. 2 and comprises the following four main components:

  1. 1.

Learnable 3D Universe Points: the 2D key points
$\\{\mathcal{V}_{j}\\}_{j=1}^{N}$ of all images in the collection are used to
reconstruct the 3D universe points $U$ by incorporating a reconstruction loss
that approximates Eq. (3).

  2. 2.

Deformation Module: the retrieved universe points $U$ are static and therefore
they cannot accurately model the geometric variability present in different
instances of an object from the same category (e.g. different bicycles). To
address this, the universe points are non-linearly deformed by the deformation
module that takes the 2D points and the (learned) 3D universe points as input.

  3. 3.

Assignment Graph Generation: by connecting the 2D points and universe points,
respectively, the 2D graph and the 3D universe graph are constructed. The
assignment graph is then constructed as the product of these two graphs.

  4. 4.

Graph Matching Network: a graph matching network performs graph convolutions
on the assignment graph, and eventually performs a binary node classification
on the assignment graph representing the matching between the 2D graph and the
universe graph.

###  4.1 Learnable 3D Universe Points

As discussed in Sec. 3.2, the universe points can be retrieved by minimising
(3). This problem, however, is generally under-determined, since
$U,\\{\Lambda_{j}\\}$ and $\\{\Pi_{j}\\}$ in (3) are generally unknown in most
practical settings. Additionally, although all objects share a similar 3D
geometry, the nonlinear deformations between different instances are
disregarded in (3). Thus, instead of an exact solution we settle for an
approximation that we later refine in our pipeline. To this end, we assume a
weak perspective projection model, i.e. all universe points are assumed to
have the same distance from the camera. With this condition, the diagonal of
$\Lambda_{j}$ is constant and can absorbed into $\Pi_{j}$. This leads to the
least-squares problem

$\operatorname{arg\,min}_{U}\sum_{j=1}^{N}||\Pi_{j}U-\mathcal{V}_{j}||_{F}^{2},$
(4)

which can be solved in an end-to-end manner during neural network training
based on commonly used ‘backpropagable’ pseudo-inverse implementations. The
variable $\Pi_{j}$ can be written as $\Pi_{j}=\mathcal{V}_{j}U^{+}$ where
$U^{+}$ is the right pseudo-inverse that satisfies $UU^{+}=\mathbb{I}_{4}$.
Therefore, we introduce the reconstruction loss

$\mathcal{L}_{\text{rec}}=\frac{1}{N}\sum_{j=1}^{N}||\mathcal{V}_{j}U^{+}U-\mathcal{V}_{j}||^{2}_{F}.$
(5)

###  4.2 Deformation Module

The universe points retrieved in the previous step are static, meaning that
they can only reflect the rough geometric information of the underlying 3D
object, but that they are unable to accurately represent finer-scale
variations between different instances of the same object category.

Thus, we introduce the deformation module to learn an additional nonlinear
deformation.

This modules takes the universe points $U$ and the 2D points $\mathcal{V}_{j}$
as input. As shown in the bottom left of Fig. 2, $\mathcal{V}_{j}$ is passed
to a 2D Point encoder. The encoder first performs a nonlinear feature
transform of all input points based on multi-layer perceptron (MLP), and then
performs a max pooling to get a global feature representing the input object.
As can be seen in the top left in Fig. 2, an MLP is utilised to perform a
nonlinear feature transform for each of the 3D points in $U$. Each 3D point
feature is then concatenated with the same global feature from the 2D Point
Encoder. The concatenated per 3D point features are fed into an MLP to compute
the motion of each point. The output is a set of per-point offsets
$S\in\mathbb{R}^{3\times d}$ that are added to $U$ to generate the deformed 3D
universe points. The computation of the per-point offsets is summarised as

$\displaystyle S_{j}$
$\displaystyle=\text{MLP}\left(\text{MLP}(U)\circ\text{Encoder}(\mathcal{V}_{j})\right),$
(6)

where $\circ$ represents the concatenation operation.

Similarly as for the reconstruction loss, the projection of the deformed
universe points onto the image plane should be close to the observed 2D
points. Additionally, since the static 3D universe points should reflect the
rough geometry of the underlying 3D object, the offset $S_{j}$ should be
small. Therefore, we introduce the deformed reconstruction loss and the offset
regulariser as

$\displaystyle\mathcal{L}_{\text{def}}$
$\displaystyle=\frac{1}{N}\sum_{j=1}^{N}||\mathcal{V}_{j}(U{+}S_{j})^{+}(U{+}S_{j})-\mathcal{V}_{j}||^{2}_{F},\text{
and}$ (7) $\displaystyle\mathcal{L}_{\text{off}}$
$\displaystyle=||S_{j}||^{2}_{F}.$ (8)

###  4.3 Assignment Graph Generation

To obtain graphs from the 2D points and the deformed 3D universe points,
respectively, we apply the Delaunay algorithm [11] to generate edges, see Fig.
2.

Moreover, we define the attribute of each edge as the concatenation of the
respective coordinates of the respective connecting points.

Once the 3D universe graph $\mathcal{U}$ and the 2D graph $\mathcal{G}_{j}$
are generated, we construct the assignment graph $\mathcal{G}^{A}_{j}$ as the
product graph of $\mathcal{U}$ and $\mathcal{G}_{j}$ following [25]. To be
more specific, the nodes in $\mathcal{G}^{A}_{j}$ are defined as the product
of the two node sets $\mathcal{V}_{j}$ and $\mathcal{V}$ of $\mathcal{G}_{j}$
and $\mathcal{U}$, respectively, i.e.
$\mathcal{V}^{A}_{j}=\\{v_{jk}:v_{jk}=(v_{j},u_{k})\in\mathcal{V}_{j}\times\mathcal{V}\\}$.
The edges in $\mathcal{G}^{A}_{j}$ are built between nodes $v_{jk}$,
$v_{mn}\in\mathcal{V}^{A}_{j}$ if and only if there is an edge between $v_{j}$
and $v_{m}$ in $\mathcal{E}_{j}$, as well as between $u_{k}$ and $u_{n}$ in
$\mathcal{E}$. The attribute of each node and edge in $\mathcal{G}^{A}_{j}$ is
again the concatenation of the attribute of corresponding nodes and edges in
$\mathcal{G}_{i}$ and $\mathcal{U}$, respectively.

###  4.4 Graph Matching Network

The graph matching problem is converted to a binary classification problem on
the assignment graph $\mathcal{G}^{A}$. For example, an assignment graph is
shown on the top right of Fig. 2. Classifying nodes $\\{1c,2b,3a\\}$ as
positive equals to matching point $1$ to $c$, $2$ to $b$ and $3$ to $a$, where
numeric nodes correspond to the 2D graph, and alphabetic nodes correspond the
3D universe graph.

The assignment graph is then passed into the graph matching network [55],
which encodes the attributes of the assignment graph into a latent
representation. This is achieved by alternatingly applying edge convolutions
and node convolutions. The edge convolution assembles the attributes of the
connected nodes, while the node convolution aggregates the information from
its adjacent edges and updates the attributes of each node. The overall
architecture is based on the graph network from [2].

Car (Willow Dataset) | Duck (Willow Dataset)
---|---
|  |  |  |  |  |  |
Bicycle (Pascal VOC Dataset) | Cow (Pascal VOC Dataset)
|  |  |  |  |  |  |
Figure 3: Qualitative results of the proposed method on the Willow Dataset and
Pascal VOC Dataset. It can be seen that our method achieves accurate results
for non-deformable objects of different types (car, bike), and that it
achieves still reasonable results for different instances of articulated
objects (duck, cow).

###  4.5 Loss Function

Similarly as existing deep graph matching approaches, we train our network in
a supervised way based on the ground-truth matching matrix $X_{j}^{\text{gt}}$
between $\mathcal{G}_{j}$ and $\mathcal{U}$. To this end, we adopt the mean
squared loss to compute a matching loss

$\mathcal{L}_{\text{match}}=\frac{1}{N}\sum_{j=1}^{N}||X_{j}^{\text{gt}}-X_{j}||^{2}.$
(9)

Furthermore, one-to-one matching is a reasonable prior for graph matching,
which was already adopted in previous work [54, 55]. To include a one-to-one
matching soft-constraint, we first convert the predicted permutation matrix
$X_{j}$ to a binary node label matrix $Y_{j}\in\\{0,1\\}^{m_{j}d\times 2}$
that we define as

$Y_{j}=\begin{pmatrix}1{-}\text{vec}(X_{j}),\text{vec}(X_{j})\end{pmatrix}.$
(10)

Here, $\text{vec}(X_{j})$ is the vectorisation of $X_{j}$. We can compute the
corresponding index vector $y_{j}\in\\{0,1\\}^{m_{j}d}$ defined as

$(y_{j})_{i}=\operatorname{arg\,max}_{k\in\\{1,2\\}}(Y_{j})_{ik}.$ (11)

By leveraging the auxiliary matrix $B\in\\{0,1\\}^{(m_{j}+d)\times m_{j}d}$
and the ground-truth permutation matrix $X_{j}^{\text{gt}}$ [54], the one-to-
one matching regularisation is

$\mathcal{L}_{\text{reg}}=||B(y-\text{vec}(X_{j}^{\text{gt}}))||^{2}.$ (12)

The total loss that we minimise during training is

$\displaystyle\mathcal{L}=$
$\displaystyle~{}\omega_{\text{m}}\mathcal{L}_{\text{match}}+\omega_{\text{d}}\mathcal{L}_{\text{def}}+\omega_{\text{r}}\mathcal{L}_{\text{rec}}+\omega_{\text{o}}\mathcal{L}_{\text{off}}+\omega_{\text{reg}}\mathcal{L}_{\text{reg}}.$
(13)

###  4.6 Training

We train a single network that is able to handle multiple object categories at
the same time. To this end, we learn separate 3D universe points for each
category, and in addition we introduce a separate learnable linear operator
for each category that is applied to the global feature obtained by the 2D
Point Encoder. The linear operator has the purpose to transform the generic
global feature to a category-specific representation, and also helps in
resolving ambiguities between categories with objects that are somewhat
similar (e.g. cat and dog).

In practice, we apply a warm start for learning the universe points
$\mathcal{U}$, which are randomly initialised for each category. To this end,
at the beginning of the training, $\omega_{\text{r}}$ is set to 1 and all
other weights are 0. After a certain number of iterations, 4k in our setting,
we replace the reconstruction loss $\mathcal{L}_{\text{rec}}$ by the deformed
reconstruction loss $\mathcal{L}_{\text{def}}$ by setting $\omega_{r}=0$ ,
$\omega_{\text{m}}=1.0$, $\omega_{\text{d}}=0.5$, $\omega_{\text{o}}=0.05$ and
$\omega_{\text{reg}}=0.1$ (in all our experiments). The batch size is 16 and
the number of iterations after warm start is 150k. The learning rate is
$0.008$ and scheduled to decrease exponentially by 0.98 after each 3k
iterations.

##  5 Experiments

In the following, we evaluate our method in various settings. We compare our
method to different state-of-the-art methods on two datasets, and we evaluate
our deformation module based on a dataset of 3D objects. Additional results
can be found in the supplementary material.

###  5.1 Comparisons to State of the Art

For the comparison experiments, we follow the testing protocol that was used
in CSGM [55]. In the following, we summarise the experimental setting for each
dataset and discuss our results. Parts of the matching results are visualised
in Fig. 3

####  5.1.1 Willow Dataset

We simultaneously train our model for all categories of the Willow dataset
[14]. The dataset consists of images from $5$ classes, car, duck, face,
motorbike, and wine bottle. It is compiled from Caltech-256 and Pascal VOC
2007 datasets, and it consists of more than $40$ images per class with $10$
manually labelled distinctive features each.

To compare our method against existing methods, we use the same training/test
split as in CSGM [55]. For training, $20$ images are randomly chosen from each
class and the rest are used for testing. For non-learning based methods, the
affinity matrix is constructed using the appearance similarity of SIFT
descriptors [33] as done in [54]. Delaunay triangulation is applied to build
graph edges. Each edge $(k,l)\in\mathcal{E}_{j}$ requires two features
$w_{kl}$ and $\theta_{kl}$, where $w_{kl}$ is the pairwise distance between
the connected nodes $v_{k}$ and $v_{l}$, and $\theta_{kl}$ is the absolute
angle between the edge and the horizontal line with
$0\leq\theta_{kl}\leq\pi/2$. The edge affinity between edges $(k,l)$ in
$\mathcal{G}_{1}$ and $(a,b)$ in $\mathcal{G}_{2}$ is computed as
$e_{(k,a),(l,b)}=\text{exp}(-(|w_{kl}-w_{ab}|+|\theta_{kl}-\theta_{ab}|)/2)$.

In our method, we use the 2D key point coordinates as attributes of nodes in
$\mathcal{G}_{i}$, while the nodes in $\mathcal{U}$ have the 3D coordinates of
the (learned) universe points as attributes. The attributes of edges are the
concatenation of the coordinates of connected nodes. The attribute of nodes
and edges in the assignment graph is described in Sec. 4.3.

| car | duck | face | motor. | wine. | avg. acc. | cyc.-cons.
---|---|---|---|---|---|---|---
IPFP [26] | 74.8 | 60.6 | 98.9 | 84.0 | 79.0 | 79.5 | ✗
RRWM [15] | 86.3 | 75.5 | 100 | 94.9 | 94.3 | 90.2 | ✗
PSM [19] | 88.0 | 76.8 | 100 | 96.4 | 97.0 | 91.6 | ✗
GNCCP [29] | 86.4 | 77.4 | 100 | 95.6 | 95.7 | 91.0 | ✗
ABPF [54] | 88.4 | 80.1 | 100 | 96.2 | 96.7 | 92.3 | ✗
HARG [14] | 71.9 | 72.2 | 93.9 | 71.4 | 86.1 | 79.1 | ✗
GMN [58] | 74.3 | 82.8 | 99.3 | 71.4 | 76.7 | 80.9 | ✗
PCA [51] | 84.0 | 93.5 | 100 | 76.7 | 96.9 | 90.2 | ✗
CSGM [55] | 91.2 | 86.2 | 100 | 99.4 | 97.9 | 94.9 | ✗
Ours | 98.8 | 90.3 | 99.9 | 99.8 | 100 | 97.8 | ✓

Table 2: Matching accuracy on the Willow dataset. Our method beats the
previous state of the art and achieves the best average accuracy.

Table 2 shows the accuracy of our method compared to other methods on the
Willow dataset. It can be seen that on an average, our method achieves an
accuracy of $97.8\%$, outperforming other methods by at least $2.9\%$, while
also being able to reconstruct the 3D structure of objects, see Fig. Joint
Deep Multi-Graph Matching and 3D Geometry Learning  from Inhomogeneous 2D
Image Collections. In the car category, our method outperforms the others
noticeably. Additionally, although there is non-rigid motion in the duck
category that is cause by articulation, our method can still achieve a
reasonable accuracy. Further, our method is the only one that can guarantee
cycle-consistent matchings thanks to the object-to-universe matching
formulation.

####  5.1.2 Pascal VOC Keypoints Dataset

The Pascal VOC Keypoints dataset [12] contains $20$ categories of objects with
labelled key point annotations. The number of key points varies from 6 to 23
for each category. Following [55], we use $7020$ images for training and
$1682$ for testing. The accuracy computations are the same as described in
Sec. 5.1.1.

| aero | bike | bird | boat | bottle | bus | car | cat | chair | cow | table | dog | horse | mbike | person | plant | sheep | sofa | train | tv | avg. acc. | cyc.-cons.
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
GMN [58] | 31.9 | 47.2 | 51.9 | 40.8 | 68.7 | 72.2 | 53.6 | 52.8 | 34.6 | 48.6 | 72.3 | 47.7 | 54.8 | 51.0 | 38.6 | 75.1 | 49.5 | 45.0 | 83.0 | 86.3 | 55.3 | ✗
PCA [51] | 40.9 | 55.0 | 65.8 | 47.9 | 76.9 | 77.9 | 63.5 | 67.4 | 33.7 | 65.5 | 63.6 | 61.3 | 68.9 | 62.8 | 44.9 | 77.5 | 67.4 | 57.5 | 86.7 | 90.9 | 63.8 | ✗
CSGM [55] | 46.9 | 58.0 | 63.6 | 69.9 | 87.8 | 79.8 | 71.8 | 60.3 | 44.8 | 64.3 | 79.4 | 57.5 | 64.4 | 57.6 | 52.4 | 96.1 | 62.9 | 65.8 | 94.4 | 92.0 | 68.5 | ✗
Ours | 41.1 | 64.7 | 64.9 | 64.6 | 94.5 | 79.3 | 69.9 | 56.6 | 66.0 | 68.6 | 69.5 | 56.8 | 53.6 | 67.2 | 57.3 | 98.3 | 54.2 | 58.8 | 86.3 | 69.7 | 67.1 | ✓

Table 3: Results on Pascal VOC Keypoints dataset [12]. Note that in terms of
accuracy we achieve comparable results to the previous state of the art method
CSGM [55], while we are the only one that additionally achieves cycle
consistency.

We randomly sample from the training data to train our model. In Table 3 it
can be seen that in terms of matching accuracy our method is almost on par
with the previous state of the art [55]. Moreover, if a key point point is not
visible in both images that are considered for obtaining the pairwise
matching, the other methods discard this point and merely aim to find
correspondences between key points common in both images. This procedure is
not necessary for our method because the universe graph contains all possible
key points in one category. Additionally, unlike any earlier methods, our
method achieves cycle-consistent matchings, and also infers 3D geometry. We
emphasise that accuracy alone is not a fully descriptive measure of
performance, since the ground truth matchings must be cycle-consistent.

Figure 4: Illustration of 3D universe points obtained from 2D projections of
D3DFACs heads. Left: the coarse 3D universe points (error to ground truth:
0.3388). Right: the 3D universe points after refinment via our deformation
module (error to ground truth: 0.0905).

###  5.2 3D Geometry and Deformation Evaluation

As our network learns 3D universe points along with a nonlinear deformation
model, we evaluate our 3D deformation model by training it on samples from the
3D head dataset D3DFACs [16, 27]. We use a similar pre-processing pipeline as
in i3DMM [57] to obtain $8$ facial landmarks on each head in the dataset. We
refer interested readers to [57] for more details. Please note that the
landmarks are all in correspondence, as we use a template-registered dataset
[27]. For our evaluation, we compute 2D projections of the 3D landmarks using
a pinhole camera model and randomly sampled rotations and translations.

The goal of this experiment is to show that reconstructed 3D universe points
are plausible, and that our deformation module is indeed useful for model
nonlinear deformations. As shown in Fig. Joint Deep Multi-Graph Matching and
3D Geometry Learning  from Inhomogeneous 2D Image Collections (right) and Fig.
4, the learned 3D universe points (before applying the deformation module) can
only reflect rough 3D geometry. Subsequently, the deformation module is able
to refine the 3D universe points. The average error between the ground truth
3D points and the obtained 3D universe points are 0.356 before the deformation
module, and 0.148 after the deformation module, confirming the merits of the
deformation module. Although the reconstructed 3D geometry is not perfect,
considering that we are inferring 3D geometry from multiple images that depict
different instances of an object, we believe the obtained results clearly
confirm the utility of our approach.

##  6 Conclusion

We have introduced a novel graph neural network approach that jointly learns
multi-graph matching and 3D geometry from an inhomogeneous image collection.
For the first time, we achieve several favourable properties simultaneously:
Our matchings are guaranteed to be cycle-consistent, which is an important
property since the (unknown) ground truth matchings are cycle-consistent. Our
approach does not rely on the availability of an initial 3D geometry model, so
that we can train it on virtually any object category, as opposed to object-
specific approaches that are for example tailored towards faces only [47].
Instead, during training we learn a (sparse) deformable 3D geometric model
directly from 2D image data. Moreover, our methods merely requires multiple
images of _different object instances_ of the same category. This is in
contrast to typical multi-view reconstruction approaches that require multiple
images of the _same object_ from different views. We believe that the joint
consideration of deep graph matching and 3D geometry inference will open up
interesting new research directions and that our approach may serve as
inspiration for follow-up works on matching problems, 3D reconstruction, 3D
deformation model learning, and many more.

## References

  * [1] Sameer Agarwal, Yasutaka Furukawa, Noah Snavely, Ian Simon, Brian Curless, Steven M. Seitz, and Richard Szeliski.  Building rome in a day.  Communications of the ACM, 54(10):105–112, Oct. 2011.
  * [2] Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al.  Relational inductive biases, deep learning, and graph networks.  arXiv preprint arXiv:1806.01261, 2018.
  * [3] Herbert Bay, Andreas Ess, Tinne Tuytelaars, and Luc Van Gool.  Speeded-up robust features (surf).  Computer Vision and Image Understanding, 110(3):346–359, 2008.  Similarity Matching in Computer Vision and Multimedia.
  * [4] Jon Louis Bentley.  Multidimensional binary search trees used for associative searching.  Communications of the ACM, 18(9):509–517, Sept. 1975.
  * [5] Florian Bernard, Christian Theobalt, and Michael Moeller.  Ds*: Tighter lifting-free convex relaxations for quadratic matching problems.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [6] Florian Bernard, Johan Thunberg, Jorge Goncalves, and Christian Theobalt.  Synchronisation of partial multi-matchings via non-negative factorisations.  Pattern Recognition, 92, 03 2018.
  * [7] Florian Bernard, Johan Thunberg, Paul Swoboda, and Christian Theobalt.  HiPPI: Higher-order projected power iterations for scalable multi-matching.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019.
  * [8] Tolga Birdal and Umut Simsekli.  Probabilistic permutation synchronization using the riemannian structure of the birkhoff polytope.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [9] Volker Blanz and Thomas Vetter.  A morphable model for the synthesis of 3d faces.  In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques, USA, 1999.
  * [10] Federica Bogo, Angjoo Kanazawa, Christoph Lassner, Peter Gehler, Javier Romero, and Michael J. Black.  Keep it SMPL: Automatic estimation of 3D human pose and shape from a single image.  In European Conference on Computer Vision (ECCV). Springer International Publishing, 2016.
  * [11] Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Lévy.  Polygon Mesh Processing.  CRC press, 2010.
  * [12] Lubomir D. Bourdev and Jitendra Malik.  Poselets: Body part detectors trained using 3d human pose annotations.  Proceedings of the IEEE International Conference on Computer Vision (ICCV), pages 1365–1372, 2009.
  * [13] Rainer Burkard, Mauro Dell’Amico, and Silvano Martello.  Assignment Problems: Revised Reprint.  Society for Industrial and Applied Mathematics, 2012.
  * [14] Minsu Cho, Karteek Alahari, and Jean Ponce.  Learning graphs to match.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2013.
  * [15] Minsu Cho, Jungmin Lee, and Kyoung Mu Lee.  Reweighted random walks for graph matching.  In European Conference on Computer Vision (ECCV), 2010.
  * [16] Darren Cosker, Eva Krumhuber, and Adrian Hilton.  A facs valid 3d dynamic action unit database with applications to 3d dynamic morphable facial modeling.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2011.
  * [17] Timothee Cour, Praveen Srinivasan, and Jianbo Shi.  Balanced Graph Matching.  Advances in Neural Information Processing Systems, 2006.
  * [18] Nadav Dym, Haggai Maron, and Yaron Lipman.  Ds++: A flexible, scalable and provably tight relaxation for matching problems.  ACM Transactions on Graphics, 36(6), Nov. 2017.
  * [19] Amir Egozi, Yosi Keller, and Hugo Guterman.  A probabilistic approach to spectral graph matching.  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 35(1):18–27, 2012.
  * [20] Matthias Fey, Jan E. Lenssen, Christopher Morris, Jonathan Masci, and Nils M. Kriege.  Deep graph matching consensus.  In International Conference on Learning Representations (ICLR), 2020\.
  * [21] Justin Johnson Georgia Gkioxari, Jitendra Malik.  Mesh r-cnn.  Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019.
  * [22] Qi-Xing Huang and Leonidas Guibas.  Consistent shape maps via semidefinite programming.  In Computer Graphics Forum, volume 32, 2013.
  * [23] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton.  Imagenet classification with deep convolutional neural networks.  In Advances in Neural Information Processing Systems (NeurIPS), 2012\.
  * [24] Eugene L. Lawler.  The quadratic assignment problem.  Management Science, 9(4):586–599, 1963.
  * [25] Marius Leordeanu and Martial Hebert.  A spectral technique for correspondence problems using pairwise constraints.  2005\.
  * [26] Marius Leordeanu, Martial Hebert, and Rahul Sukthankar.  An integer projected fixed point method for graph matching and map inference.  In Advances in Neural Information Processing Systems (NeurIPS). Citeseer, 2009.
  * [27] Tianye Li, Timo Bolkart, Michael J. Black, Hao Li, and Javier Romero.  Learning a model of facial shape and expression from 4D scans.  ACM Transactions on Graphics, 36(6):194:1–194:17, 2017.
  * [28] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli.  Graph matching networks for learning the similarity of graph structured objects.  In International Conference on Machine Learning (ICML). PMLR, 2019\.
  * [29] Zhi-Yong Liu and Hong Qiao.  Gnccp—graduated nonconvexity and concavity procedure.  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 36(6):1258–1267, 2013.
  * [30] Eliane Loiola, Nair Abreu, Paulo Boaventura-Netto, Peter Hahn, and Tania Querido.  A survey of the quadratic assignment problem.  European Journal of Operational Research, 176:657–690, 01 2007\.
  * [31] Stephen Lombardi, Tomas Simon, Jason Saragih, Gabriel Schwartz, Andreas Lehrmann, and Yaser Sheikh.  Neural volumes: Learning dynamic renderable volumes from images.  ACM Transactions on Graphics, 38(4):65:1–65:14, July 2019.
  * [32] Matthew Loper, Naureen Mahmood, Javier Romero, Gerard Pons-Moll, and Michael J. Black.  SMPL: A skinned multi-person linear model.  ACM Transactions on Graphics, 34(6):248:1–248:16, Oct. 2015.
  * [33] David Lowe.  Distinctive image features from scale-invariant keypoints.  International Journal of Computer Vision, 60:91–, 11 2004.
  * [34] Jiayi Ma, Xingyu Jiang, Aoxiang Fan, Junjun Jiang, and Junchi Yan.  Image matching from handcrafted to deep features: A survey.  International Journal of Computer Vision, 129(1):23–79, 2021.
  * [35] Eleonora Maset, Federica Arrigoni, and Andrea Fusiello.  Practical and Efficient Multi-View Matching.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017.
  * [36] Ben Mildenhall, Pratul P. Srinivasan, Matthew Tancik, Jonathan T. Barron, Ravi Ramamoorthi, and Ren Ng.  Nerf: Representing scenes as neural radiance fields for view synthesis.  In European Conference on Computer Vision (ECCV), 2020.
  * [37] Deepti Pachauri, Risi Kondor, and Vikas Singh.  Solving the multi-way matching problem by permutation synchronization.  In Advances in Neural Information Processing Systems (NeurIPS). Curran Associates, Inc., 2013.
  * [38] Panos Pardalos, Franz Rendl, and Henry Wolkowitz.  The quadratic assignment problem: A survey and recent developments. quadratic assignment and related problem.  DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, pages 1–42, 1994.
  * [39] Jeong Joon Park, Peter Florence, Julian Straub, Richard Newcombe, and Steven Lovegrove.  Deepsdf: Learning continuous signed distance functions for shape representation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [40] Keunhong Park, Utkarsh Sinha, Jonathan T. Barron, Sofien Bouaziz, Dan B. Goldman, Steven M. Seitz, and Ricardo Martin-Brualla.  Deformable neural radiance fields.  arXiv preprint arXiv:2011.12948, 2020.
  * [41] 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 European Conference on Computer Vision (ECCV). Springer, 2020\.
  * [42] Johannes Lutz Schönberger and Jan-Michael Frahm.  Structure-from-motion revisited.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
  * [43] Johannes Lutz Schönberger, Enliang Zheng, Marc Pollefeys, and Jan-Michael Frahm.  Pixelwise view selection for unstructured multi-view stereo.  In European Conference on Computer Vision (ECCV), 2016.
  * [44] Vincent Sitzmann, Michael Zollhöfer, and Gordon Wetzstein.  Scene representation networks: Continuous 3d-structure-aware neural scene representations.  In Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * [45] Paul Swoboda, Carsten Rother, Hassan Abu Alhaija, Dagmar Kainmüller, and Bogdan Savchynskyy.  Study of lagrangean decomposition and dual ascent solvers for graph matching.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
  * [46] Ayush Tewari, Florian Bernard, Pablo Garrido, Gaurav Bharaj, Mohamed Elgharib, Hans-Peter Seidel, Patrick Pérez, Michael Zöllhofer, and Christian Theobalt.  Fml: Face model learning from videos.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [47] Ayush Tewari, Michael Zollöfer, Hyeongwoo Kim, Pablo Garrido, Florian Bernard, Patrick Perez, and Theobalt Christian.  MoFA: Model-based Deep Convolutional Face Autoencoder for Unsupervised Monocular Reconstruction.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017.
  * [48] Eno Toeppe, Claudia Nieuwenhuis, and Daniel Cremers.  Volume constraints for single view reconstruction.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Portland, USA, 2013.
  * [49] Roberto Tron, Xiaowei Zhou, Carlos Esteves, and Kostas Daniilidis.  Fast multi-image matching via density-based clustering.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017.
  * [50] Qianqian Wang, Xiaowei Zhou, and Kostas Daniilidis.  Multi-image semantic matching by mining consistent features.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [51] Runzhong Wang, Junchi Yan, and Xiaokang Yang.  Learning combinatorial embedding networks for deep graph matching.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019.
  * [52] Runzhong Wang, Junchi Yan, and Xiaokang Yang.  Neural graph matching network: Learning lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching.  arXiv preprint arXiv:1911.11308, 2019.
  * [53] Rui Wang, Nan Yang, Joerg Stueckler, and Daniel Cremers.  Directshape: Photometric alignment of shape priors for visual vehicle pose and shape estimation.  In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2020.
  * [54] Tao Wang, Haibin Ling, Congyan Lang, and Songhe Feng.  Graph matching with adaptive and branching path following.  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 40(12):2853–2867, 2018.
  * [55] Tao Wang, He Liu, Yidong Li, Yi Jin, Xiaohui Hou, and Haibin Ling.  Learning combinatorial solver for graph matching.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [56] Shangzhe Wu, Christian Rupprecht, and Andrea Vedaldi.  Unsupervised learning of probably symmetric deformable 3d objects from images in the wild.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [57] T Yenamandra, A Tewari, F Bernard, HP Seidel, M Elgharib, D Cremers, and C Theobalt.  i3dmm: Deep implicit 3d morphable model of human heads.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2021.
  * [58] Andrei Zanfir and Cristian Sminchisescu.  Deep learning of graph matching.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [59] Quanshi Zhang, Xuan Song, Xiaowei Shao, Huijing Zhao, and Ryosuke Shibasaki.  Learning graph matching: Oriented to category modeling from cluttered scenes.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2013.
  * [60] Zhen Zhang and Wee Sun Lee.  Deep graphical feature learning for the feature matching problem.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019.
  * [61] Feng Zhou and Fernando De la Torre.  Factorized Graph Matching.  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 38(9):1774–1789, 2016.
  * [62] Xiaowei Zhou, Menglong Zhu, and Kostas Daniilidis.  Multi-image matching via fast alternating minimization.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2015.

##  Appendix A Ablation Study

To confirm the importance of the individual components of our approach we
conducted an ablation study. To this end we evaluate the accuracy on the
Pascal VOC dataset in cases where we omit individual terms of the loss
function, omit the warm start for learning the universe points $\mathcal{U}$,
and omit deformation module, see Table 4.

When we omit the one-to-one matching regulariser by setting
$\omega_{\text{reg}}$ to 0, the matching accuracy is depressed substantially.
When we do not conduct a warm start for finding initial universe points, the
matching accuracy deteriorates. Similarly, the matching accuracy lowers
without the use of our deformation module. Further, the offset regularisation
and the deformed reconstruction loss can refine the universe points for each
object, which brings a better matching accuracy as shown in the last two
experiments. Overall, the accuracy is highest when using all components
together.

##  Appendix B Cycle Consistency

We further provide quantitative evaluations of the cycle consistency on the
Pascal VOC dataset, as shown in Table 5. We quantify in terms of the cycle
consistency score, which is computed as follows:

  1. 1.

Given three graphs $\\{\mathcal{G}_{j}\\}$, $\\{\mathcal{G}_{k}\\}$ and
$\\{\mathcal{G}_{l}\\}$, we use the trained network to predict $X_{jk}$,
$X_{jl}$ and $X_{kl}$.

  2. 2.

We compute the composed pairwise matching between $\\{\mathcal{G}_{k}\\}$ and
$\\{\mathcal{G}_{l}\\}$ by $X^{\prime}_{kl}=X_{jk}^{T}X_{jl}$.

  3. 3.

We denote the number of points that $X^{\prime}_{kl}$ equals to $X_{kl}$ as
$m_{\text{cycle}}$ and the number of points in $X_{kl}$ as $m_{kl}$. The cycle
consistency score is then computed as

$\text{cycle consistency score}=100\times\frac{m_{\text{cycle}}}{m_{kl}}\%.$
(14)

Note that in this case, we only consider the common points that are observed
in $\\{\mathcal{G}_{j}\\}$, $\\{\mathcal{G}_{k}\\}$ and
$\\{\mathcal{G}_{l}\\}$.

Loss | Avg. acc.
---|---
$\omega_{\text{reg}}=0$ | 58.11
w/o warm start | 58.49
w/o deformation module | 60.33
$\omega_{\text{o}}=0$ | 64.19
$\omega_{\text{d}}=0$ | 64.81
Ours | 67.1
Table 4: Matching accuracy on the Pascal VOC dataset with the variants on
regularisation terms or training strategies.  PCA [51]CSGM [55]Ours$0$ %$20$
%$40$ %$60$ %$80$ %$100$ %matching accuracycycle consistency score Figure 5:
The average matching accuracy and cycle consistency score of three learning-
based methods on Pascal VOC dataset.

| aero | bike | bird | boat | bottle | bus | car | cat | chair | cow | table | dog | horse | mbike | person | plant | sheep | sofa | train | tv | Avg.
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
PCA [51] | 40.92 | 15.48 | 44.91 | 45.30 | 14.55 | 41.83 | 55.97 | 42.97 | 35.99 | 44.30 | 41.59 | 49.10 | 43.68 | 33.33 | 35.04 | 24.67 | 53.93 | 45.87 | 44.00 | 29.39 | 39.19
CSGM [55] | 49.08 | 51.50 | 60.13 | 67.84 | 81.13 | 80.36 | 67.40 | 57.10 | 51.26 | 61.42 | 56.16 | 55.28 | 61.61 | 54.17 | 54.57 | 96.84 | 60.71 | 58.30 | 96.6 | 93.60 | 65.75
Ours | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100

Table 5: Cycle consistency scores (in percent) of three learning-based methods
on the Pascal VOC Keypoints dataset. Our method is the only one that
guarantees cycle consistency for all categories.

In Fig. 5, we show the average matching accuracy and cycle consistency score
of our method and compare it with PCA [51] and CSGM [55]. It is clear that our
method can achieve comparable accuracy and the best cycle consistency at the
same time.

##  Appendix C More Deformation Results

We provide more qualitative results for our deformation module, see Fig. 6. As
shown in the figure, the deformation module is able to refine the 3D universe
points. Although 3D reconstructions are not perfect, we can observe that they
represent the overall 3D structure well, and are thus valuable for matching
respective key points.

$\mathcal{G}$ |  Right View |  Front View |  Left View |  $\mathcal{G}$ |  Right View |  Front View |  Left View
---|---|---|---|---|---|---|---
Ground Truth |  |  |  |  Universe Points |  |  |
Case 1 |  |  |  |  Case 2 |  |  |
Case 3 |  |  |  |  Case 4 |  |  |
Case 5 |  |  |  |  Case 6 |  |  |
Case 7 |  |  |  |  Case 8 |  |  |
Figure 6: Qualitative results of deformation module. The top-left part shows
the ground truth points on a reference shape, and the top-right part shows the
universe points before the deformation module is applied. The remaining parts
show individual cases, where it can be seen that the deformation module
adequately deforms the universe points (top right), and that it is able to
approximate the overall 3D geometry of the face well.