# Deep Graph Matching under Quadratic Constraint

Quankai Gao1 Fudong Wang1 Nan Xue1 Jin-Gang Yu2 Gui-Song Xia1
1Wuhan University  Wuhan  China.
2South China University of Technology  Guangzhou  China.
{quankaigao, fudong-wang, xuenan<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Recently, deep learning based methods have demonstrated promising results on
the graph matching problem, by relying on the descriptive capability of deep
features extracted on graph nodes. However, one main limitation with existing
deep graph matching (DGM) methods lies in their ignorance of explicit
constraint of graph structures, which may lead the model to be trapped into
local minimum in training. In this paper, we propose to explicitly formulate
pairwise graph structures as a quadratic constraint incorporated into the DGM
framework. The quadratic constraint minimizes the pairwise structural
discrepancy between graphs, which can reduce the ambiguities brought by only
using the extracted CNN features. Moreover, we present a differentiable
implementation to the quadratic constrained-optimization such that it is
compatible with the unconstrained deep learning optimizer. To give more
precise and proper supervision, a well-designed false matching loss against
class imbalance is proposed, which can better penalize the false negatives and
false positives with less overfitting. Exhaustive experiments demonstrate that
our method achieves competitive performance on real-world datasets.

††The study of this paper is funded by the National Natural Science Foundation
of China (NSFC) under grant contracts No.61922065, No.61771350 and
No.41820104006 and 61871299. It is also supported by Supercomputing Center of
Wuhan University.†† Corresponding author: Gui-Song Xia
(guisong.xia@whu.edu.cn).

##  1 Introduction

Graph matching aims to find an optimal one-to-one node correspondence between
graph-structured data, which has been widely used in many tasks [3, 6, 9, 14,
20, 37]. By integrating the similarity between nodes and edges in a
combinatorial fashion, graph matching is often mathematically formulated as a
quadratic assignment problem (QAP) [29]. QAP is known to be NP-hard [16], and
various approximation techniques [25, 26, 28, 34] have been proposed to make
it computationally tractable.

(a) DGM without quadratic constraint

(b) DGM with quadratic constraint (our method)

Figure 1: Deep graph matching with/without quadratic constraint. Matching
results are in left and the predicted (black) v.s. the ground truth (red)
correspondence matrices are in right. Figure 2: Overview of our proposed
architecture for deep graph matching under quadratic constraint. Node
attributes consisting geometric prior and deep features are refined to build
the initial node affinity matrix, which is followed by a Sinkhorn layer and
then further optimized under quadratic constraint (QC). Loss between the
prediction and the ground truth (GT) is calculated by the proposed false
matching loss (FM-Loss).

Until recently, deep graph matching (DGM) methods give birth to many more
flexible formulations [13, 32, 39, 45] besides traditional QAP. DGM aims to
learn the meaningful node affinity by using deep features extracted from
convolutional neural network. To this end, many existing DGM methods [32, 39,
45] primarily focus on the feature modeling and refinement for more accurate
affinity construction. The feature refinement step is expected to capture the
implicit structure information [39] encoded in learnable parameters. However,
nodes with similar deep features are hard to distinguish from each other in
deep graph matching, while their structure contexts may be very different.
Moreover, the implicit structure information is not specific enough, which is
insufficient to clearly represent the structural discrepancy over graphs
(e.g., Fig. 1(a)).

In traditional graph matching, it is common to incorporate pairwise structures
into the formulation to enhance matching accuracy [25], which inspired us to
consider quadratic structural constraint in deep graph matching to maximize
the adjacency consensus and achieve global consistency. More precisely, we use
the pairwise term of Koopmans-Beckmann’s QAP [29] as our quadratic constraint
to minimize the adjacency discrepancy of graphs to be matched (e.g., Fig.
1(b)). To this end, we present a modified Frank-Wolfe algorithm [23], which is
a differentiable optimization scheme w.r.t. learnable parameters in our model
and the relaxed Koopmans-Beckmann’s QAP.

Another important issue of deep graph matching is class imbalance. Concretely,
the result of a graph matching task is usually represented as a permutation
matrix, where only a small portion of the entries take the value of one
representing the pairs to be matched while the rest are zero-valued, leading
to the imbalance between matched and unmatched entries. In case of such class
imbalance, it will be problematic to establish the loss function between
predicted matching matrices and ground truth matrices by using the
conventional cross-entropy-type loss functions (see Section 3.4 for details).
To our best knowledge, there is no loss function specifically designed for
deep graph matching to take care of the class imbalance issue so far. To this
end, we design a novel loss function for deep graph matching, called False
Matching Loss, which will be experimentally shown to be better for dealing
with class imbalance and overfitting in compared with previous works.

Our main contributions are highlighted as follows:

  * -

We explicitly introduce quadratic constraint with our constructed geometric
structure into deep graph matching, which can further revise wrong matches by
minimizing structure discrepancy over graphs.

  * -

We present a differentiable optimization scheme in training to approach the
objective such that it is compatible with the unconstrained deep learning
optimizer.

  * -

We propose a novel loss function focusing on false matchings, i.e. false
negatives and false positives, to better lead the parameter update against
class imbalance and overfitting.

##  2 Preliminaries and Related Work

For better understanding, this section will revisit some preliminaries and
related works on both traditional combinatorial graph matching and deep graph
matching.

###  2.1 Combinatorial graph matching

Graph matching aims to build the node-to-node correspondence between the given
two graphs $\mathcal{G}_{A}=\\{V_{A},E_{A}\\}$ with $|V_{A}|=n$ and
$\mathcal{G}_{B}=\\{V_{B},E_{B}\\}$ with $|V_{B}|=m$, where $V$ we denote as
the set of nodes and $E$ as the set of edges. By denoting $\mathbf{X}$ as the
correspondence matrix indicating the matching between two graphs
$\mathcal{G}_{A}$ and $\mathcal{G}_{B}$, i.e., $X_{ij}=1$ means the $i$-th
node in $V_{A}$ matches to the $j$-th node in $V_{B}$, $X_{ij}=0$ otherwise,
one well-known form of graph matching with combinatorial nature can be written
as:

$\displaystyle\min_{\mathbf{X}}\quad||\mathbf{A}-\mathbf{XBX}^{T}||^{2}_{F}-{\rm
tr}(\mathbf{X}^{T}_{u}\mathbf{X})$ (1)
$\displaystyle\mathbf{X}\in\\{0,1\\}^{n\times
m},\mathbf{X1}_{n}=\mathbf{1}_{m},\mathbf{X}^{T}\mathbf{1}_{n}\leq\mathbf{1}_{n}$

where $\mathbf{A}\in\mathbb{R}^{n\times n}$, $\mathbf{B}\in\mathbb{R}^{m\times
m}$ are adjacency matrices encoding the pairwise information of edges in
graphs $\mathcal{G}_{A}$ and $\mathcal{G}_{B}$, respectively.
$\mathbf{X}_{u}\in\mathbb{R}^{n\times m}$ measures the node similarities
between two graphs. $||\cdot||_{F}$ is the Frobenius norm. Generally, Eq. (1)
can be cast as a quadratic assignment problem called Koopmans-Beckmann’s QAP
[29]. One can find more details in [43].

In the previous works [15, 38, 47] following this combinatorial graph matching
formulation, the node similarity $\mathbf{X}_{u}$ and adjacency matrices
$\mathbf{A},\mathbf{B}$ are usually calculated with some specifically designed
handcrafted features like SIFT [30], Shape Context [2], etc. And then they
will solve the objective functions (e.g., Eq. (1)) with different discrete or
continuous constrained-optimization algorithms [8, 38, 10, 44]. Until
recently, the deep learning based graph matching framework has been developed
consisting of learned features and unconstrained optimizer, which will be
detailed in next section.

###  2.2 Deep graph matching

Feature extraction. Recently, many works [13, 39, 41, 45, 32] on deep graph
matching have been proposed to take advantages of the descriptive capability
of high-dimensional deep features as node or edge attributes, which can
collect visual information of background images. As a basic setting of these
works, the output of CNN layers ${\rm relu4\\_2}$ and ${\rm relu5\\_1}$ are
commonly used, denoted as $\mathbf{U}\in\mathbb{R}^{n\times d}$ and
$\mathbf{F}\in\mathbb{R}^{n\times d}$,

U $\displaystyle={\rm align}({\rm CNN_{relu4\\_2}}(I),V)$ (2) F
$\displaystyle={\rm align}({\rm CNN_{relu5\\_1}}(I),V)$ (3)

where $I$ denotes the input image and $V$ denotes the annotated keypoints. CNN
here is a widely used architecture VGG16 [35] initially pretrained on the
ImageNet [33]. ”align” in Eq. (2) and Eq. (3) is bi-linear interpolation to
approximately assign the output features of a convolution layer to the
annotated keypoints on the input image pairs.

Feature modeling and refinement. Since the extracted raw features are
independent with the graph structure, various refinement strategies on the raw
features are adopted in deep graph matching trying to implicitly utilize the
information of graph structure. As a typical example of non-Euclidean data, a
graph with its node and edge attributes can be processed by graph
convolutional network (GCN) [21] under the message passing scheme to update
its attributes. Each node attribute is updated by aggregating its adjacency
node attributes so that GCN is expected to implicitly capture the structure
contexts of each node to some extent. There are also some works [32, 45] using
unary node features to model pairwise edge features for matching.

Differentiable optimization. Deep graph matching asks for the model fully-
differentiable so that many combinatorial solvers and methods (e.g., Hungarian
algorithm [22] and IPFP [26]) are not recommended. Thus, various relaxation
approaches become popular, which refer to the recent progress [32, 39, 42].

Under these settings, deep graph matching can be reformulated as maximizing
the node affinity based on the extracted features.

Loss function for deep graph matching. Though many works about deep graph
matching have been proposed, there are few thorough discussions about loss
functions. The prototype of cross entropy loss has been widely used in deep
graph matching, e.g. permutation loss [39] and its improved version [45].
Instead of directly calculating the linear assignment cost, GMN [46] uses
“displacement loss” measuring pixel-wise offset on the image but is shown to
have a weaker supervision than cross entropy loss [39]. However, none of the
existing works consider the class imbalance that naturally exists in deep
graph matching. Besides, overfitting and gradient explosion are always
conspicuous on models trained with cross-entropy-type loss functions. For the
above reasons, we propose a novel loss function specifically designed for deep
graph matching, which not only considers numerical issue but also shows
promising performance against overfitting and class imbalance.

##  3 DGM under Quadratic Constraint

We briefly demonstrate our method overview here. As shown in Fig. 2, given the
input two images with detected or annotated keypoints as graph nodes, we
firstly adopt the CNN features and the coordinates of keypoints to calculate
both the initial node attributes and the pairwise structural context as
weighted adjacency matrices. By this end, we establish graphs with structural
attributes, based on which we explicitly use the weighted adjacency matrices
to construct the quadratic constraint, and design a differentiable
constrained-optimization algorithm to achieve compatibility with the deep
learning optimizer. Since the quadratic constrained-optimization is non-convex
and needs a proper initialization, we update the node attributes with weighted
adjacency matrices through a GCN module and a differentiable Sinkhorn layer
[1, 36] respectively, to obtain a node affinity matrix between two graphs as
the initialization. Finally, the solved optimum will be compared with the
ground truth by the proposed false matching loss, which addresses the issue of
class imbalance to achieve better performance.

###  3.1 Geometric structure for DGM

Unary geometric prior  Since our work doesn’t focus on deep feature
extraction, we follow the previous deep graph matching works to use CNN
features described in Eq. (2) and Eq. (3). Moreover, features from different
layers of CNN are expected to incorporate both the local and global semantic
information of images, we concatenate $\mathbf{U}$ and $\mathbf{F}$ together
as $\mathbf{P}_{r}={\rm cat}(\mathbf{U};\mathbf{F})$ to be the initial node
attributes of two graphs.

Since the extracted raw features associated to nodes only have visual
information of local patches, to make raw node attributes more discriminative,
we add the the normalized 2D Cartesian coordinate
$[\hat{\mathbf{x}},\hat{\mathbf{y}}]$ of each node as $\mathbf{P}={\rm
cat}(\mathbf{P}_{r};[\hat{\mathbf{x}},\hat{\mathbf{y}}])$, which provides a
unary geometric prior that can better describe the locations of nodes as a
complement to the CNN features.

Pairwise structural context  In deep graph matching, the graph construction is
usually based on node coordinates and never consider the visual meaningful
features of the background image. For this reason, we introduce deep feature
weighted adjacency matrices $\mathbf{A}_{D}$ and $\mathbf{B}_{D}$ of the two
graphs to learn more proper relations among graph nodes, which are defined as

$\mathbf{A}_{D}=f(\mathbf{P_{A}})\odot\mathbf{A},\quad\mathbf{B}_{D}=f(\mathbf{P_{B}})\odot\mathbf{B}$
(4)

where $\mathbf{A}\in\mathbb{R}^{n\times n},\mathbf{B}\in\mathbb{R}^{m\times
m}$ are the binary adjacency matrices built on coordinates of nodes in two
graphs,
$\mathbf{P}_{A}\in\mathbb{R}^{n\times(d+2)},\mathbf{P}_{B}\in\mathbb{R}^{m\times(d+2)}$
are the above-mentioned node attributes of two graphs, $\odot$ denotes
element-wise product. $f(\mathbf{P})$ can be various commutative function and
here we use a linear kernel $f_{i,j}=\mathbf{p}^{T}_{i}\mathbf{p}_{j}$ for
simplicity, where $\mathbf{p}_{i}$ is the $i$-th row of $\mathbf{P}$. As
illustrated in Fig. 3, the geometric meaning of the function $f$ is related to
the cosine of the angle between two normalized node attributes, which can be
detailed as
cos$\theta_{ij}=\frac{\left<\mathbf{p}_{i},\mathbf{p}_{j}\right>}{|\mathbf{p}_{i}||\mathbf{p}_{j}|}=\frac{1}{\sqrt{3}}\frac{1}{\sqrt{3}}\left<\mathbf{p}_{i},\mathbf{p}_{j}\right>=\frac{1}{3}\mathbf{p}^{T}_{i}\mathbf{p}_{j}$.
By this definition, each element of $\mathbf{A}_{D}$ and $\mathbf{B}_{D}$
represents the feature distance between the corresponding nodes while
preserving the topology constraints provided by $\mathbf{A}$ and $\mathbf{B}$.

Figure 3: Illustration of the geometric relationship between two nodes and
their edge connection in attribute space. Normalized attributes of nodes are
represented as coloured squares.

Attributes fusion with GCN There are many convolutional architectures [12, 48]
for processing irregular data. As a typical example of non-Euclidean data, a
graph with its node and edge attributes can be processed by GCN under the
message passing scheme to update its attributes. Each node attribute is
updated by aggregating its adjacency node attributes so that GCN is expected
to capture the structure contexts of each node in an implicit way. With the
above interpretation, we adopt GCN that incorporates both update from
neighbors and self-update, which can be written as:

$\textbf{P}^{l+1}=\sigma(\textbf{A}_{D}\textbf{P}^{l}\textbf{W}^{l}_{r}+\textbf{P}^{l}\textbf{W}^{l}_{s})$
(5)

where $\mathbf{W}^{l}_{r},\mathbf{W}^{l}_{s}\in\mathbb{R}^{(d+2)\times(d+2)}$
denote learnable parameters of GCN at $l$-th layer. $\sigma$ is the activation
function. The updated attributes $\mathbf{P}^{l+1}$ is then used to update
$\mathbf{A}_{D}$ and $\mathbf{B}_{D}$ by Eq. (4).

Node affinity  Since we have the refined attributes of two graphs, the node
affinity $\mathbf{K}^{l}_{p}\in\mathbb{R}^{n_{A}\times n_{B}}$ at $l$-th
iteration can be built by a learnable metric:

$\mathbf{K}^{l}_{p}={\rm exp}\\{{\mathbf{P}^{l}_{A}\textbf{W}^{l}_{{\rm
aff}}{\mathbf{P}^{l}_{B}}^{T}}\\}$ (6)

where $\mathbf{W}^{l}_{{\rm aff}}$ is a matrix containing learnable
parameters. We then adopt Sinkhorn layer taking $\mathbf{K}^{l}_{p}$ to the
set of doubly-stochastic matrices $\mathcal{D}$, which is the convex hull of
the set of permutation matrices $\mathcal{P}$.

###  3.2 Quadratic constraint for DGM

To explicitly utilize the information of graph structures, we formulate the
objective as to minimize the pairwise structure discrepancy between the graphs
to be matched. As Eq. (1), Koopmans-Beckmann’s QAP explicitly involves the
second-order geometric context in its pairwise term and the optimal solution
will minimize the two terms simultaneously. The learnable metric
$\mathbf{K}^{l}_{p}$ we obtained from Eq. (6) is considered as the initial
point of $\mathbf{X}$, i.e., $\mathbf{X}_{0}=\mathbf{K}^{l}_{p}$. We rewrite
Eq. (1) as:

$\min_{\mathbf{X}}g(\mathbf{X})=\min_{\mathbf{X}}||\mathbf{A}_{D}-\mathbf{X}\mathbf{B}_{D}\mathbf{X}^{T}||^{2}_{F}-{\rm
tr}({\mathbf{X}_{u}}^{T}\mathbf{X})$ (7)

Input: Nodes of graph pairs $V_{s}$; two input images $I_{s}$, where $s$=A, B;
the ground truth $\mathbf{X}^{*}$; initial parameters
$\mathbf{W}=\\{\mathbf{W}^{l}_{r},\mathbf{W}^{l}_{s},\mathbf{W}^{l}_{aff}\\}$

Output: prediction $\mathbf{X}_{P}\in\mathcal{P}$

//feature extraction and alignment

$\mathbf{U}_{s}~{}\leftarrow\text{align}(\text{CNN}_{{\text{relu4}}\\_2}(I_{s}),V_{s})$;

$\mathbf{F}_{s}~{}\leftarrow\text{align}(\text{CNN}_{{\text{relu5}}\\_1}(I_{s}),V_{s})$;

//node attributes

$\mathbf{P}_{s}$ $\leftarrow$ ${\rm
cat}(\mathbf{U}_{s};\mathbf{F}_{s};[\hat{\mathbf{x}}_{s},\hat{\mathbf{y}}_{s}])$;

$\textbf{Training stage}:$

for  _epoch $k\leq n$_ do

$\mathbf{P}^{l}_{s}$ $\leftarrow$ ${\rm
GCN}((\mathbf{A}_{D})_{s},\mathbf{P}^{l-1}_{s})$;

($\mathbf{A}^{l}_{D})_{s}$ $\leftarrow$
$f(\mathbf{P}^{l}_{s})\odot\mathbf{A}_{s}$;

$\mathbf{K}^{l}_{p}$ $\leftarrow$ ${\rm
exp}\\{\mathbf{P}^{l}_{A}\mathbf{W}^{l}_{{\rm
aff}}{\mathbf{P}^{l}_{B}}^{T}\\}$;

$\mathbf{X}$ $\leftarrow$ $\mathbf{K}^{l}_{p}$;

for  _iter = 1: $m_{1}$_ do

for  _k = 1: $m_{2}$_ do

$\mathbf{y}$ $\leftarrow$ $\arg\min\limits_{\mathbf{y}}\nabla
g(\mathbf{X})^{T}\mathbf{y}$;

//$f_{\mathcal{D}}$ is Sinkhorn normalization

$\mathbf{s}$ $\leftarrow$ $f_{\mathcal{D}}(\mathbf{y})$;

$\overline{\mathbf{X}}$ $\leftarrow$
$\mathbf{X}-\epsilon_{k}(\mathbf{X}-\mathbf{s})$;

end for

$\mathbf{X}$ $\leftarrow$ $f_{\mathcal{D}}(\overline{\mathbf{X}})$;

end for

$\mathbf{W}$ $\leftarrow$ $L_{fm}$($\mathbf{X}$, $\mathbf{X}^{\rm GT}$),
$\mathbf{W}$;

end for

$\textbf{Inference stage}:$

$\mathbf{X}_{P}$ $\leftarrow$ $\mathbf{X}$;

for  _iter = 1:m_ do

repeat

$\mathbf{y}$ $\leftarrow$ $\arg\min\limits_{\mathbf{y}}\nabla
g(\mathbf{X}_{P})^{T}\mathbf{y}$;

//$f_{\mathcal{P}}$ is Hungarian algorithm

$\mathbf{s}$ $\leftarrow$ $f_{\mathcal{P}}(\mathbf{y})$;

$\overline{\mathbf{X}}_{P}$ $\leftarrow$
$\mathbf{X}_{P}-\epsilon_{k}(\mathbf{X}_{P}-\mathbf{s})$;

until  _$\mathbf{X}_{P}$ converges_;

$\mathbf{X}_{P}$ $\leftarrow$ $f_{\mathcal{P}}(\overline{\mathbf{X}}_{P})$;

end for

Algorithm 1 DGM under Quadratic Constraint

We specify unary affinity matrix $\mathbf{X}_{u}$ as the obtained node
affinity matrix $\mathbf{K}^{l}_{p}$ in both the training stage and the
inference stage.

Due to the paradox between the combinatorial nature of QAP formulation and the
differentiable requirement of deep learning framework, we consider a relaxed
version of Eq. (7): $\mathbf{X}\in[0,1]^{n_{A}\times
n_{B}},\mathbf{X1}_{n_{B}}=1,\mathbf{X}^{T}\mathbf{1}_{n_{A}}\leq\mathbf{1}_{n_{A}}$.
The value of $\mathbf{X}$ is continuous and satisfies normalization
constraints at the same time. By minimizing the objective function, the
solution will close to the ground truth in the direction of minimizing the
adjacency inconsistency.

###  3.3 Quadratic constrained-optimization

We adopt a differentiable Frank-Wolfe algorithm [23] for $g(\mathbf{X})$ to
obtain an approximate solution:

$\displaystyle\mathbf{y}_{k}$ $\displaystyle=\arg\min_{\mathbf{y}}\nabla
g(\mathbf{X}_{k})^{T}\mathbf{y}$ (8) $\displaystyle\mathbf{s}$
$\displaystyle=f_{proj}(\mathbf{y}_{k})$ (9)
$\displaystyle\bar{\mathbf{X}}_{k+1}$
$\displaystyle=\mathbf{X}_{k}-\epsilon_{k}(\mathbf{X}_{k}-\mathbf{s})$ (10)
$\displaystyle\mathbf{X}_{k+1}$
$\displaystyle=f_{proj}(\bar{\mathbf{X}}_{k+1})$ (11)

where $\epsilon_{k}$ is a parameter representing the step size. Usually, we
set $\epsilon_{k}=\frac{2}{k+2}$ [18] in implementation. In training stage,
$f_{proj}$ in Eq. (9) and Eq. (11) is the Sinkhorn layer to project the
positive variable into the set of doubly stochastic matrices $\mathcal{D}$,
while $f_{proj}$ is the Hungarian algorithm in the inference stage for
obtaining a discrete solution. We write down the gradient of $g(\mathbf{X})$
as:

$\nabla
g\left(\mathbf{X}\right)=-2[\mathbf{U}^{T}\mathbf{XB}^{l}_{D}+\mathbf{U}{\mathbf{XB}^{l}_{D}}^{T}]-\mathbf{X}_{u}$
(12)

where $\mathbf{U}=\mathbf{A}^{l}_{D}-\mathbf{XB}^{l}_{D}\mathbf{X}^{T}$. In
training stage, the variable $\mathbf{X}$ is associated with the learnable
parameters
$\mathbf{W}=\\{\mathbf{W}^{l}_{r},\mathbf{W}^{l}_{s},\mathbf{W}^{l}_{aff}\\}$
and every iteration of Frank-Wolfe algorithm is actually going with the
parameters fixed before backpropagation [17]. From Eq. (10) and Eq. (11),
$\mathbf{X}_{k+1}$ is differentiable with respect to $\mathbf{X}_{k}$ so
$\mathbf{X}_{k+1}$ is differentiable with respect to
$\mathbf{X}_{0}=\mathbf{K}^{l}_{p}$ by the recursive relations:

$\displaystyle\mathbf{X}_{k+1}=f_{r}(\mathbf{X}_{k})=f_{r}\circ
f_{r}(\mathbf{X}_{k-1})=...=f_{r}^{k}(\mathbf{X}_{0})$ (13)

where $f_{r}(\mathbf{X})\triangleq
f_{proj}(\mathbf{X}-\epsilon_{k}(\mathbf{X}-\mathbf{s}))$ is a differentiable
function w.r.t. $\mathbf{X}$ in training stage. Since the goal of the
optimization is to utilize the information of the pairwise term in Eq. (7),
only few iterations roughly approaching to a local minimum in training stage
can fulfill our purpose. Though there is no guarantee of global minimum, it is
actually not necessary because the pairwise term will be noisy with outliers
and the global minimum may not be the desired matching. Besides, few
iterations in training stage encourage the model to learn a relatively short
path to approximate the object so that it is easier to convergence within
fewer iterations in inference stage.

###  3.4 False-matching loss

Class imbalance. The elements of correspondence matrix can be divided into two
classes with clear different meaning, one of which represents matched pairs
and the other represents unmatched pairs. Given two graphs with equal number
of nodes $n$, there are $n$ elements of correspondence matrix are 1 while the
rest $n^{2}-n$ are 0. Under the constraint of one-to-one matching, the
unmatched pairs clearly take the majority. Though the values of the soft
correspondence matrix are all between 0 and 1, the two classes should be
separately treated in the calculation of loss during training.

The cross-entropy-type loss functions such as permutation loss [39] and its
improved version [45] achieve the state-of-the-art performance. This type of
loss functions directly measures the linear assignment cost between the ground
truth $\mathbf{X}^{*}\in\\{0,1\\}^{n\times n}$ and the prediction
$\mathbf{X}\in[0,1]^{n\times n}$ like

$\displaystyle
L_{ce}=-\sum_{i,j}\mathbf{X}^{*}_{ij}\log\mathbf{X}_{ij}+(1-\mathbf{X}^{*}_{ij})\log(1-\mathbf{X}_{ij})$
(14)

with $i\in\mathcal{G}_{A}$, $j\in\mathcal{G}_{B}$. Cross entropy loss does not
consider the class imbalance in deep graph matching because the vast majority
of $\mathbf{1-X}$ are preserved by multiplying $\mathbf{1-X^{*}}$ while at
most $n$ elements of $\mathbf{X}$ are kept by multiplying $\mathbf{X^{*}}$.
Similarly, cross entropy loss with Hungarian attention [45] can not solve this
issue either and the so called Hungarian attention in loss function brings
discontinuity in learning.

Figure 4: An illustration of the work flow about our proposed false matching
loss. We take both the false positive and false negative of the predicted
doubly stochastic matrix into consideration. $\alpha$ and $\beta$ are two
parameters to weight the two terms.

Numerical stability. Since the optimization of deep learning is unconstraint,
the local minimum with bad properties can not be avoid. Once a bad case or a
bad local minimum occurs, e.g. at least one element of the prediction
$\mathbf{X}$ approaches to 0 while the corresponding element of the ground
truth $\mathbf{X}^{*}$ is 1, the cross-entropy-type loss will be invalid.
Though permutation loss with Hungarian attention mechanism is more focus on a
specific portion of the prediction $\mathbf{X}$, it only works without severe
bad cases either. Even with gradient clipping, overfitting is still a problem
to be addressed.

(a) cross entropy loss $L_{ce}$

(b) false matching loss $L_{fm}$

Figure 5: Comparison between cross entropy loss and false matching loss on a
toy example, where $\mathbf{X}\in\mathbb{R}^{1\times 3}$ and
$\mathbf{X}^{*}=(0,0,1)$. We mark the three extreme points of $\mathbf{X}$:
$\mathbf{A}=(0,0,1)$, $\mathbf{B}=(0,1,0)$ and $\mathbf{C}=(1,0,0)$. A cooler
color means a smaller value. The comparison shows that false matching loss has
a higher value than cross entropy loss when it close to the ground truth.
Besides, false matching loss has a high but limited value when $\mathbf{X}$
close to the extreme points, which are the bad cases for cross entropy loss
and make the loss function output infinite values. The curve of cross entropy
loss on points between $\mathbf{B}$ and $\mathbf{C}$ are below the red line
connected to $\mathbf{B}$ and $\mathbf{C}$, while the curve of false matching
loss coincides with the red line.

Facing the problems above, we propose a new loss function called false
matching loss:

$\displaystyle
L_{fm}=\underbrace{e^{\alpha\sum_{i,j}\left[\mathbf{X}\odot(\mathbf{1}-\mathbf{X}^{*})\right]_{ij}}}_{L_{+}}+\underbrace{e^{\beta\sum_{i,j}\left[\mathbf{X}^{*}\odot(\mathbf{1}-\mathbf{X})\right]_{ij}}}_{L_{-}}$
(15)

where $i\in\mathcal{G}_{A}$, $j\in\mathcal{G}_{B}$. $L_{+}$ and $L_{-}$ of our
false matching loss penalize false positive matches and false negative
matches, which are the main indexes describing the false matchings in
statistics. To address the issue of class imbalance, we draw on the experience
of focal loss [27] and take two hyperparameters $\alpha$ and $\beta$ for
weighting.

As illustrated in Fig. 5, false matching loss is more smooth and always has a
relatively large value than cross entropy loss even when the prediction
$\mathbf{X}$ is close to the ground truth. While on extreme points that are
away from the ground truth, false matching loss will have more proper outputs
(high but limited). Besides, the values of cross entropy loss on points
between $\mathbf{B}$ and $\mathbf{C}$ are lower than that on $\mathbf{B}$ and
$\mathbf{C}$, which is not proper because points between $\mathbf{B}$ and
$\mathbf{C}$ are still far away from the ground truth.

Our method is summarized in Algorithm 1.

##  4 Experiments and Analysis

In this section, we evaluate our method on two challenging datasets. We
compare the proposed method with several state-of-the-art deep graph matching
methods: GLMNet [19], PCA [39], NGM [40], ${\rm CIE_{1}}$ [45], GMN [46],
LCSGM [42] and BB-GM [32]. To compare the proposed false matching loss with
the previous work: permutation loss with Hungarian attention [45], we follow
[45] to implement the loss function for the source code is not publicly
available. Given graphs with $n$ nodes, the matching accuracy is computed as

$\displaystyle{\rm accuracy}=\frac{1}{n}\sum_{i,j}[\mathbf{X}^{*}\odot{\rm
Hungarian}(\mathbf{X})]_{ij}$ (16)

Stochastic gradient descent (SGD) [4] is employed as the optimizer with an
initial learning rate $10^{-3}$. In our false matching loss, we set $\alpha=2$
and $\beta=0.1$. In our optimization step, we set the number of iterations
$m_{1}=3$ and $m_{2}=5$ for the consideration of both computational efficiency
and convergence.

Since the feature refinement step is not limited to Eq. (5), we additionally
deploy another novel architecture SplineCNN [12] to replace Eq. (5) as a
comparision with [32]. Thus, two versions of our method are provided: qc-
DG${\rm M}_{1}$ and qc-DG${\rm M}_{2}$. In qc-DG${\rm M}_{1}$, the node
attributes are refined by a two-layer GCN as Eq. (5) with ReLU [31] activation
function. While in qc-DG${\rm M}_{2}$, the refinement step is done by a two-
layer SplineCNN [12] with max aggregation. In our implementation, all the
input graphs are constructed by Delaunay triangulation. Specifically for GMN
[46], two input graphs are constructed by fully-connected topology and
Delaunay triangulation respectively. While ${\rm GMN_{D}}$ is another version
of GMN that two input graphs are both constructed by Delaunay triangulation.

###  4.1 Results on Pascal VOC Keypoints

Pascal VOC dataset [11] with Berkeley annotations of keypoints [5] has 20
classes of instance images with annotated keypoints. There are 7,020 annotated
images for training and 1,682 for testing. Before training, each instance is
cropped around its bounding box and is re-scaled to $256\times 256$ as the
input for VGG16. We follow the previous works to filter the truncated,
occluded and difficult images. The training process will be performed on all
20 classes. Because of the large variation of pose, scale, and appearance,
Pascal VOC Keypoints is considerably a challenging dataset.

Method | aero | bike | bird | boat | bottle | bus | car | cat | chair | cow | table | dog | horse | mbike | person | plant | sheep | sofa | train | tv | Mean
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
GMN [46] | 35.5 | 50.0 | 52.2 | 45.2 | 75.5 | 69.1 | 59.0 | 61.1 | 34.4 | 51.9 | 66.4 | 53.4 | 53.9 | 50.7 | 31.1 | 75.8 | 59.2 | 47.9 | 86.1 | 89.6 | 57.4
${\rm GMN_{D}}$ [46] | 40.8 | 57.1 | 56.2 | 48.2 | 75.5 | 71.6 | 64.1 | 63.3 | 36.3 | 54.3 | 50.2 | 57.6 | 60.3 | 55.4 | 35.5 | 85.2 | 62.7 | 51.8 | 86.5 | 87.4 | 60.0
qc-GMN | 37.3 | 52.2 | 54.3 | 47.2 | 76.4 | 70.4 | 61.2 | 61.7 | 34.5 | 53.1 | 69.1 | 55.4 | 56.0 | 52.4 | 31.6 | 77.3 | 59.7 | 49.1 | 87.4 | 89.7 | 58.8
PCA [39] | 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 | 86.7 | 90.9 | 63.8
qc-PCA | 42.5 | 58.5 | 66.1 | 51.3 | 79.6 | 78.2 | 65.8 | 68.7 | 35.1 | 66.8 | 65.6 | 62.5 | 62.1 | 63.1 | 45.1 | 80.7 | 67.7 | 59.1 | 87.0 | 91.1 | 64.8
PCA-H [39] | 50.8 | 61.7 | 62.6 | 56.4 | 80.0 | 75.6 | 72.4 | 74.0 | 38.5 | 64.3 | 49.9 | 63.8 | 65.2 | 63.5 | 46.0 | 78.5 | 68.0 | 41.5 | 82.2 | 90.8 | 64.3
PCA-F | 50.0 | 66.7 | 61.8 | 55.1 | 81.5 | 75.5 | 70.1 | 70.4 | 39.7 | 64.8 | 60.3 | 65.5 | 67.6 | 64.2 | 45.6 | 84.4 | 68.6 | 56.5 | 88.7 | 91.1 | 66.3
NGM [40] | 50.8 | 64.5 | 59.5 | 57.6 | 79.4 | 76.9 | 74.4 | 69.9 | 41.5 | 62.3 | 68.5 | 62.2 | 62.4 | 64.7 | 47.8 | 78.7 | 66.0 | 63.3 | 81.4 | 89.6 | 66.1
GLMNet [19] | $\bf{52.0}$ | 67.3 | 63.2 | 57.4 | 80.3 | 74.6 | 70.0 | 72.6 | 38.9 | 66.3 | $\bf{77.3}$ | 65.7 | 67.9 | 64.2 | 44.8 | 86.3 | 69.0 | 61.9 | 79.3 | 91.3 | 67.5
LCSGM [42] | 46.9 | 58.0 | 63.6 | $\bf{69.9}$ | $\bf{87.8}$ | 79.8 | 71.8 | 60.3 | $\bf{44.8}$ | 64.3 | 79.4 | 57.5 | 64.4 | 57.6 | $\bf{52.4}$ | $\bf{96.1}$ | 62.9 | 65.8 | $\bf{94.4}$ | 92.0 | 68.5
${\rm CIE_{1}}$-H [45] | 51.2 | $\bf{69.2}$ | $\bf{70.1}$ | 55.0 | 82.8 | 72.8 | 69.0 | $\bf{74.2}$ | 39.6 | 68.8 | 71.8 | $\bf{70.0}$ | $\bf{71.8}$ | 66.8 | 44.8 | 85.2 | $\bf{69.9}$ | 65.4 | 85.2 | $\bf{92.4}$ | 68.9
qc-DG${\rm M}_{1}$(ours) | 48.4 | 61.6 | 65.3 | 61.3 | 82.4 | 79.6 | 74.3 | 72.0 | 41.8 | $\bf{68.8}$ | 65.0 | 66.1 | 70.9 | 69.6 | 48.2 | 92.1 | 69.0 | 66.7 | 90.4 | 91.8 | 69.3
qc-DG${\rm M}_{2}$(ours) | 49.6 | 64.6 | 67.1 | 62.4 | 82.1 | $\bf{79.9}$ | $\bf{74.8}$ | 73.5 | 43.0 | 68.4 | 66.5 | 67.2 | 71.4 | $\bf{70.1}$ | 48.6 | 92.4 | 69.2 | $\bf{70.9}$ | 90.9 | 92.0 | $\bf{70.3}$

Table 1: Accuracy (%) of 20 classes and average accuracy on Pascal VOC. Bold
numbers represent the best performing of the methods to be compared. Method
with “-H” and “-F” denotes it with permutation loss with Hungarian attention
and false matching loss, respectively. Suffix “-QC” denotes the method with
the proposed quadratic constraint.

Method | aero | bike | bird | boat | bottle | bus | car | cat | chair | cow | table | dog | horse | mbike | person | plant | sheep | sofa | train | tv | Mean
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
BB-GM-Max [32] | 35.5 | 68.6 | 46.7 | 36.1 | 85.4 | 58.1 | 25.6 | 51.7 | 27.3 | 51.0 | 46.0 | 46.7 | 48.9 | 58.9 | 29.6 | 93.6 | 42.6 | 35.3 | 70.7 | 79.5 | 51.9
BB-GM [32] | 42.7 | 70.9 | 57.5 | 46.6 | 85.8 | 64.1 | 51.0 | 63.8 | 42.4 | 63.7 | 47.9 | 61.5 | 63.4 | 69.0 | 46.1 | 94.2 | 57.4 | 39.0 | 78.0 | 82.7 | 61.4
qc-DGM1 (ours) | 30.1 | 59.1 | 48.6 | 40.0 | 79.7 | 51.6 | 32.4 | 55.4 | 26.1 | 52.1 | 47.0 | 50.1 | 56.8 | 59.9 | 27.6 | 90.4 | 50.9 | 33.1 | 71.3 | 78.8 | 52.0
qc-DGM2 (ours) | 30.9 | 59.8 | 48.8 | 40.5 | 79.6 | 51.7 | 32.5 | 55.8 | 27.5 | 52.1 | 48.0 | 50.7 | 57.3 | 60.3 | 28.1 | 90.8 | 51.0 | 35.5 | 71.5 | 79.9 | 52.6

Table 2: F1 score (%) of matching and mean over 20 classes on Pascal VOC.

Experimental results on 20 classes are given in Table 1. Since the peer work
[32] suggests to compare F1 score (the harmonic mean of precision and recall)
on the dataset without intersection filtering, we provide F1 score of our
method to compare with BB-GM [32] and its ablation BB-GM-Max as shown in Table
2.

To show the robustness of the deep graph matching models against outliers, we
add outliers to the original set of keypoints. The 2D Cartesian coordinates of
the outliers are generated by Gaussian distribution $\mathcal{N}(0,10)$. The
outliers exist only in inference stage to challenge the model trained on the
clean data (without outliers). This robustness test is more challenging than
that on synthetic graphs because all the inliers and outliers have their
extracted CNN features and thus, more close to the real-world scenes.
Experimental results are shown in Fig. 6. With our quadratic constraint, the
improvement of overall accuracy is witnessed on the clean data and the
robustness of deep graph matching models have been significantly improved
against outliers.

By comparing PCA and qc-PCA or GMN and qc-GMN in Table 1, the effectiveness of
our quadratic constraint is shown to be general and the matching accuracy is
improved over all 20 classes by considering our quadratic constraint.

Method | face | mbike | car | duck | wbottle | Mean
---|---|---|---|---|---|---
HARG-SSVM [7] | 91.2 | 44.4 | 58.4 | 55.2 | 66.6 | 63.2
GMN [46] | 98.1 | 65.0 | 72.9 | 74.3 | 70.5 | 76.2
${\rm GMN_{D}}$ | 100.0 | 82.4 | 84.4 | 84.0 | 91.2 | 88.4
qc-GMN | 100.0 | 65.7 | 75.3 | 81.1 | 90.5 | 82.5
PCA [39] | 100.0 | 76.7 | 84.0 | 93.5 | 96.9 | 90.2
qc-PCA | 100.0 | 83.3 | 87.3 | 93.8 | 97.1 | 92.3
PCA-H [39] | 100.0 | 76.9 | 88.9 | 89.7 | 92.9 | 89.7
PCA-F [39] | 100.0 | 78.4 | 86.8 | 93.2 | 97.2 | 91.1
NGM [40] | 99.2 | 82.1 | 84.1 | 77.4 | 93.5 | 87.2
GLMNet [19] | 100.0 | 89.7 | 93.6 | 85.4 | 93.4 | 92.4
LCSGM [42] | 100.0 | 99.4 | 91.2 | 86.2 | 97.9 | 94.9
${\rm CIE_{1}}$-H [45] | 100.0 | 90.0 | 82.2 | 81.2 | 97.6 | 90.2
BB-GM [32] | 100.0 | 99.2 | 96.9 | 89.0 | 98.8 | 96.8
qc-DG${\rm M}_{1}$(ours) | 100.0 | 95.0 | 93.8 | 93.8 | 97.6 | 96.0
qc-DG${\rm M}_{2}$(ours) | 100.0 | 98.8 | 98.0 | 92.8 | 99.0 | 97.7
Table 3: Accuracy (%) of 5 classes and the average on Willow Object Class.

Figure 6: Robustness analysis against outliers on Pascal VOC (a) and Willow
Object Class (b). Method with “+” means with quadratic constraint while “-”
means without quadratic constraint.

Figure 7: Matching examples on Pascal VOC and Willow Object Class. Nodes with
the same color indicate the correspondence of a graph pair. All the visualized
graphs are constructed by Delaunay triangulation in yellow.

###  4.2 Results on Willow Object Class

Willow Object Class dataset [7] contains 5 classes with 256 images in total.
Three classes (face, duck and wine bottle) of the dataset are from Caltech-256
and the rest two classes (car and motorbike) are from Pascal VOC 2007. We
resize all the image pairs to 256$\times$256 for VGG16 backbone and crop the
images around the bounding box of the objects. The variations of the pose,
scale, background and illumination of the images on Willow Object Class are
small, and thus, graph matching tasks on this dataset are much more easier.

As shown in Table 3, the proposed method achieves the state-of-the-art
performance. Comparing the methods with and without quadratic constraint (PCA
and qc-PCA or GMN and qc-GMN), the performance improvements on Willow dataset
are more prominent than those on Pascal VOC, which because the structure
variations of graph pairs on the easier dataset are relatively small and
quadratic constraint contributes to matching more soundly. Since BB-GM adopts
SplineCNN to refine the features, we provide qc-DG${\rm M}_{2}$ for fair
comparison, which has a higher overall accuracy.

###  4.3 Further study

Table 4 shows the usefulness of the proposed components. CNN feature vector of
each node has d=1024 dimensions, which are supposed to be better than the two-
dimensional coordinates but the geometric prior encoded in coordinates
provides a more precise description of graph nodes. By simply combining the
unary geometric prior with the extracted CNN features, the matching accuracy
is improved, which supports our point of view, i.e., CNN features are indeed
useful but not discriminative enough to depict pixel-wise graph nodes.

Quadratic constraint. There are various forms of quadratic constraint that are
not limited to ours. Global affinity matrix $\mathbf{K}$ is constrainted by
graph incidence matrices in the factorized form of Lawler’s QAP [24, 47],
which can be considered as another form of quadratic constraint adopted in
GMN. As shown in Table 1 and Table 3, GMN performs significantly worse than
${\rm GMN_{D}}$ on both two datasets by replacing similar graph topology with
the completely different one, while the extracted deep features of both
settings remain the same. This implies the main limitation of quadratic
constraint, i.e., only graphs with similar topology contribute to matching.
Besides, the fact shows the independent relationship between the graph
structure and raw deep features for the change of graph topology can not be
reflected by raw deep features (before being refined).

Figure 8: Accuracy/loss vs. training epoch on Pascal VOC. As the training
goes, the loss functions try to drag the output to binary and the local
minimum with bad properties makes the cross-entropy-type loss explosion. Since
the accuracy will be very close to 0 after gradient explosion, we truncate the
descending curves and keep them unchanged for better visualization.

False-matching loss vs. cross entropy loss. The two main loss functions to be
compared with ours are permutation loss [39] and permutation loss with
Hungarian attention [45]. We report accuracy/loss with training epoch in Fig.
8. In experiments, the model with cross-entropy-type loss functions (Loss-P
and Loss-H) always encounter the bad cases leading to gradient explosion in
training stage, while our false matching loss (Loss-F) can avoid this issue.
Besides, false matching loss is shown to do better against overfitting than
the compared two loss functions.

| raw
---
attributes
| unary
---
geomteric prior
| pairwise
---
structure context
| QC
---
optimization
accuracy
$\surd$ | $\surd$ | $\surd$ | $\surd$ | 69.3
$\surd$ | $\surd$ | $\surd$ |  | 68.5
$\surd$ | $\surd$ |  |  | 68.3
$\surd$ |  |  |  | 67.8
Table 4: Ablation study of qc-DG${\rm M}_{1}$ on Pascal VOC. The component
been adopted is marked by a tick. “QC optimization” is quadratic constrained-
optimization.

##  5 Conclusion

In this work, we explicitly introduce quadratic constraint of graph structure
into deep graph matching. To this end, unary geometric prior and pairwise
structural context are considered for objective construction and a
differentiable optimization scheme is provided to approach the problem.
Moreover, we focus on class imbalance that naturally exists in deep graph
matching to propose our false matching loss. Experimental results show the
competitive performance of our method. In future work, we plan to seek a more
general form of quadratic constraint to the learning-based optimization for
better matching.

## References

  * [1] Ryan Prescott Adams and Richard S Zemel.  Ranking via sinkhorn propagation.  arXiv preprint arXiv:1106.1925, 2011.
  * [2] Serge Belongie, Jitendra Malik, and Jan Puzicha.  Shape matching and object recognition using shape contexts.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(4):509–522, 2002.
  * [3] Alexander C Berg, Tamara L Berg, and Jitendra Malik.  Shape matching and object recognition using low distortion correspondences.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, volume 1, pages 26–33. IEEE, 2005.
  * [4] Léon Bottou.  Large-scale machine learning with stochastic gradient descent.  In Proceedings of COMPSTAT’2010, pages 177–186. Springer, 2010\.
  * [5] Lubomir Bourdev and Jitendra Malik.  Poselets: Body part detectors trained using 3d human pose annotations.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1365–1372. IEEE, 2009.
  * [6] William Brendel and Sinisa Todorovic.  Learning spatiotemporal graphs of human activities.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(9):1774–1789, 2016.
  * [7] Minsu Cho, Karteek Alahari, and Jean Ponce.  Learning graphs to match.  In Proceedings of the IEEE International Conference on Computer Vision, pages 25–32, 2013.
  * [8] Minsu Cho, Jian Sun, Olivier Duchenne, and Jean Ponce.  Finding matches in a haystack: A max-pooling strategy for graph matching in the presence of outliers.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2083–2090, 2014.
  * [9] Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento.  Thirty years of graph matching in pattern recognition.  International Journal of Pattern Recognition and Artificial Intelligence, 18(03):265–298, 2004.
  * [10] Amir Egozi, Yosi Keller, and Hugo Guterman.  A probabilistic approach to spectral graph matching.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1):18–27, 2012.
  * [11] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman.  The pascal visual object classes (voc) challenge.  International Journal of Computer Vision, 88(2):303–338, 2010.
  * [12] Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller.  Splinecnn: Fast geometric deep learning with continuous b-spline kernels.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 869–877, 2018.
  * [13] Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege.  Deep graph matching consensus.  arXiv preprint arXiv:2001.09621, 2020.
  * [14] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi.  Exact combinatorial optimization with graph convolutional neural networks.  In Proceedings of the Advances in Neural Information Processing Systems, pages 15580–15592, 2019.
  * [15] Steven Gold and Anand Rangarajan.  A graduated assignment algorithm for graph matching.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(4):377–388, 1996.
  * [16] Juris Hartmanis.  Computers and intractability: a guide to the theory of np-completeness.  Siam Review, 24(1):90, 1982.
  * [17] Catalin Ionescu, Orestis Vantzos, and Cristian Sminchisescu.  Training deep networks with structured layers by matrix backpropagation.  arXiv preprint arXiv:1509.07838, 2015.
  * [18] Martin Jaggi.  Revisiting frank-wolfe: Projection-free sparse convex optimization.  In Proceedings of the International Conference on Machine Learning, number CONF, pages 427–435, 2013.
  * [19] Bo Jiang, Pengfei Sun, Jin Tang, and Bin Luo.  Glmnet: Graph learning-matching networks for feature matching.  arXiv preprint arXiv:1911.07681, 2019.
  * [20] Hao Jiang, X Yu Stella, and David R Martin.  Linear scale and rotation invariant matching.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(7):1339–1355, 2010.
  * [21] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [22] Harold W Kuhn.  The hungarian method for the assignment problem.  Naval Research Logistics Quarterly, 2(1-2):83–97, 1955.
  * [23] Simon Lacoste-Julien and Martin Jaggi.  On the global linear convergence of frank-wolfe optimization variants.  In Proceedings of the Advances in Neural Information Processing Systems.
  * [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.  In Proceedings of the IEEE International Conference on Computer Vision, volume 2, pages 1482–1489. IEEE, 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, pages 1114–1122. Citeseer, 2009.
  * [27] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In Proceedings of the IEEE International Conference on Computer Vision, pages 2980–2988, 2017.
  * [28] Zhi-Yong Liu, Hong Qiao, Xu Yang, and Steven CH Hoi.  Graph matching by simplified convex-concave relaxation procedure.  International Journal of Computer Vision, 109(3):169–186, 2014\.
  * [29] Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, and Tania Querido.  A survey for the quadratic assignment problem.  European Journal of Operational Research, 176(2):657–690, 2007\.
  * [30] David G Lowe.  Distinctive image features from scale-invariant keypoints.  International Journal of Computer Vision, 60(2):91–110, 2004.
  * [31] Vinod Nair and Geoffrey E Hinton.  Rectified linear units improve restricted boltzmann machines.  In Proceedings of the International Conference on Machine Learning, 2010.
  * [32] Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, and Georg Martius.  Deep graph matching via blackbox differentiation of combinatorial solvers.  arXiv preprint arXiv:2003.11657, 2020.
  * [33] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  International Journal of Computer Vision, 115(3):211–252, 2015\.
  * [34] Christian Schellewald, Stefan Roth, and Christoph Schnörr.  Evaluation of convex optimization techniques for the weighted graph-matching problem in computer vision.  In Joint Pattern Recognition Symposium, pages 361–368. Springer, 2001.
  * [35] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [36] Richard Sinkhorn and Paul Knopp.  Concerning nonnegative matrices and doubly stochastic matrices.  Pacific Journal of Mathematics, 21(2):343–348, 1967.
  * [37] Richard Szeliski.  Computer vision: algorithms and applications.  Springer Science & Business Media, 2010.
  * [38] F. D. Wang, N. Xue, Y. Zhang, G. S. Xia, and M. Pelillo.  A functional representation for graph matching.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(11):2737–2754, 2020.
  * [39] 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, pages 3056–3065, 2019.
  * [40] 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.
  * [41] Runzhong Wang, Junchi Yan, and Xiaokang Yang.  Combinatorial learning of robust deep graph matching: an embedding based approach.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020\.
  * [42] 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, pages 7568–7577, 2020.
  * [43] Junchi Yan, Xu-Cheng Yin, Weiyao Lin, Cheng Deng, Hongyuan Zha, and Xiaokang Yang.  A short survey of recent advances in graph matching.  In Proceedings of the 2016 ACM on International Conference on Multimedia Retrieval, pages 167–174, 2016.
  * [44] Junchi Yan, Chao Zhang, Hongyuan Zha, Wei Liu, Xiaokang Yang, and Stephen M Chu.  Discrete hyper-graph matching.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1520–1528, 2015.
  * [45] Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li.  Learning deep graph matching with channel-independent embedding and hungarian attention.  In Proceedings of the International Conference on Learning Representations, volume 20, 2020.
  * [46] Andrei Zanfir and Cristian Sminchisescu.  Deep learning of graph matching.  In Proceedings of the IEEE Conference on Computer Vision and Pattern recognition, pages 2684–2693, 2018.
  * [47] Feng Zhou and Fernando De la Torre.  Factorized graph matching.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(9):1774–1789, 2015.
  * [48] Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun.  Graph neural networks: A review of methods and applications.  arXiv preprint arXiv:1812.08434, 2018.


# GLocal-K: Global and Local Kernels
for Recommender Systems

Soyeon Caren Han<EMAIL_ADDRESS>The University of SydneyAustralia ,
Taejun Lim<EMAIL_ADDRESS>The University of SydneyAustralia ,
Siqu Long<EMAIL_ADDRESS>The University of SydneyAustralia ,
Bernd Burgstaller<EMAIL_ADDRESS>Yonsei UniversityRepublic of Korea
and  Josiah Poon<EMAIL_ADDRESS>The University of SydneyAustralia

(2021)

###### Abstract.

Recommender systems typically operate on high-dimensional sparse user-item
matrices. Matrix completion is a very challenging task to predict one’s
interest based on millions of other users having each seen a small subset of
thousands of items. We propose a Global-Local Kernel-based matrix completion
framework, named GLocal-K, that aims to generalise and represent a high-
dimensional sparse user-item matrix entry into a low dimensional space with a
small number of important features. Our GLocal-K can be divided into two major
stages. First, we pre-train an auto encoder with the local kernelised weight
matrix, which transforms the data from one space into the feature space by
using a 2d-RBF kernel. Then, the pre-trained auto encoder is fine-tuned with
the rating matrix, produced by a convolution-based global kernel, which
captures the characteristics of each item. We apply our GLocal-K model under
the extreme low-resource setting, which includes only a user-item rating
matrix, with no side information. Our model outperforms the state-of-the-art
baselines on three collaborative filtering benchmarks: ML-100K, ML-1M, and
Douban.

Recommender Systems, Matrix Completion, Kernel Methods

††journalyear: 2021††copyright: acmcopyright††conference: Proceedings of the
30th ACM International Conference on Information and Knowledge Management;
November 1–5, 2021; Virtual Event, Australia.††booktitle: Proceedings of the
30th ACM Int’l Conf. on Information and Knowledge Management (CIKM ’21),
November 1–5, 2021, Virtual Event, Australia††price: 15.00††isbn:
978-1-4503-8446-9/21/11††doi: 10.1145/3459637.3482112††ccs: Information
systems Recommender systems††ccs: Theory of computation Kernel methods

##  1\. Introduction

Collaborative filtering-based recommender systems focus on making a prediction
about the interests of a user by collecting preferences from large number of
other users. Matrix completion(Candès and Recht, 2009) is one of the most
common formulation, where rows and columns of a matrix represent users and
items, respectively. The prediction of users’ ratings in items corresponds to
the completion of the missing entries in a high-dimensional user-item rating
matrix. In practice, the matrix used for collaborative filtering is extremely
sparse since it has ratings for only a limited number of user-item pairs.

Traditional recommender systems focus on generalising sparsely observed matrix
entries to a low dimensional feature space by using an autoencoder(AE)(Zhang
et al., 2020). AEs would help the system better understand users and items by
learning the non-linear user-item relationship efficiently, and encoding
complex abstractions into data representations. I-AutoRec(Sedhain et al.,
2015) designed an item-based AE, which takes high-dimensional matrix entries,
projects them into a low-dimensional latent hidden space, and then
reconstructs the entries in the output space to predict missing ratings.
SparseFC(Muller et al., 2018) employs an AE whose weight matrices were
sparsified using finite support kernels. Inspired by this, GC-MC(Berg et al.,
2018) proposed a graph-based AE framework for matrix completion, which
produces latent features of user and item nodes through a form of message
passing on the bipartite interaction graph. These latent user and item
representations are used to reconstruct the rating links via a bilinear
decoder. Such link prediction with a bipartite graph extends the model with
structural and external side information. Recent studies (Rashed et al., 2019;
Strahl et al., 2020; Ugla et al., 2020) focused on utilising side information,
such as opinion information or attributes of users. However, in most real-
world settings (e.g., platforms and websites), there is no (or insufficient)
side information available about users.

Instead of considering side information, we focus on improving the feature
extraction performance for a high-dimensional user-item rating matrix into a
low-dimensional latent feature space. In this research, we apply two types of
kernels that have strong ability in feature extraction. The first kernel,
named “local kernel”, is known to give optimal separating surfaces by its
ability to perform the data transformation from high-dimensional space, and
widely used with support vector machines(SVMs). The second kernel, named
“global kernel” is from convolutional neural network(CNN) architectures. The
more kernel with deeper depth, the higher their feature extraction ability.
Integrating these two kernels to have best of both worlds successfully extract
the low-dimensional feature space.

With this in mind, we propose a Global-Local Kernel-based matrix completion
framework, called GLocal-K, which includes two stages: 1) pre-training the
auto-encoder using a local kernelised weight matrix, and 2) fine-tuning with
the global kernel-based rating matrix. Note that our evaluation is under an
extreme setting where no side information is available, like most real-world
cases. The main research contributions are summarised as follows: (1) We
introduce a global and local kernel-based auto encoder model, which mainly
pays attention to extract the latent features of users and items. (2) We
propose a new way to integrate pre-training and fine-tuning tasks for the
recommender system. (3) Without using any extra information, our GLocal-K
achieves the smallest RMSEs on three widely-used benchmarks, even beating
models augmented by side information.

Figure 1. The GLocal-K architecture for matrix completion. (1) We pre-train
the AE with the local kernelised weight matrix. (2) Then, fine-tune the
trained AE with the global kernel-based matrix. The fine-tuned AE produces the
matrix completion result.

##  2\. GLocal-K

Figure 1 depicts the architecture of our proposed GLocal-K model, which
applies two types of kernels in two stages respectively: pre-training (with
the local kernelised weight matrix) and fine-tuning (with the global-kernel
based matrix)111The idea of our pre-training and fine-tuning is different from
transfer learning.. Note that we pre-train our model to make dense connections
denser and sparse connections sparser using a finite support kernel, and fine-
tune with the rating matrix. This matrix is produced from a convolution kernel
by reducing the data dimension and producing a less redundant but small number
of important feature sets. In this research, we mainly focus on a matrix
completion task, which is conducted on a rating matrix
$R\in\mathbb{R}^{m\times n}$ with $m$ items and $n$ users. Each item $i\in
I=\\{1,2,...,m\\}$ is represented by a vector
$r_{i}=(R_{i1},R_{i2},...,R_{in})\in\mathbb{R}^{n}$.

###  2.1. Pre-training with Local Kernel

Auto-Encoder Pre-training
We first deploy and train an item-based AE, inspired by (Sedhain et al.,
2015), which takes each item vector $r_{i}$ as input, and outputs the
reconstructed vector ${r}^{\prime}_{i}$ to predict the missing ratings. The
model is represented as follows:

(1) ${r}^{\prime}_{i}=f(W^{(d)}\cdot g(W^{(e)}\ r_{i}+b)+{b}^{\prime}),$

where $W^{(e)}\in\mathbb{R}^{h\times m}$ and $W^{(d)}\in\mathbb{R}^{m\times
h}$ are weight matrices, $b\in\mathbb{R}^{h}$ and
${b}^{\prime}\in\mathbb{R}^{m}$ are bias vectors, and $f(\cdot)$ and
$g(\cdot)$ are non-linear activation functions. The AE deploys an auto-
associative neural network with a single $h$-dimensional hidden layer. In
order to emphasise the dense and sparse connection, we reparameterise weight
matrices in the AE with a radial-basis-function(RBF) kernel, which is known as
Kernel Trick(Giannakopoulos et al., 2008).

Local Kernelised Weight Matrix
The weight matrices $W^{(e)}$ and $W^{(d)}$ in Eq. (1) are reparameterised by
a 2d-RBF kernel, named local kernelised weight matrix. The RBF kernel can be
defined as follows:

(2) $K_{ij}(U,V)=\text{max}(0,\ 1-\left\|u_{i}-v_{j}\right\|_{2}^{2}),$

where $K(\cdot)$ is a RBF kernel function, which computes the similarity
between two sets of vectors $U$, $V$. Here, $u_{i}\in U$ and $v_{j}\in V$. The
kernel function can represent the output as a kernel matrix LK (see Figure 1),
in which each element maps to 1 for identical vectors and approaches 0 for
very distant vectors between $u_{i}$ and $v_{j}$. Then, we compute a local
kernelised weight matrix as follows:

(3) ${W}^{\prime}_{ij}=W_{ij}\cdot K_{ij}(U,V),$

where ${W}^{\prime}$ is computed by the Hadamard-product of weight and kernel
matrices to obtain a sparsified weight matrix. The distance between each
vector of $U$ and $V$ determines the connection of neurons in neural networks,
and the degree of sparsity is dynamically varied as vectors are being changed
at each step of training. As a result, applying the kernel trick to weight
matrices enables regularising weight matrices and learning generalisable
representations.

###  2.2. Fine-tuning with Global Kernel

Global kernel-based Rating Matrix
We fine-tune the pre-trained auto encoder with the rating matrix, produced by
the global convolutional kernel. Prior to fine-tuning, we firstly describe how
the global kernel is constructed and applied to build the global kernel-based
rating matrix. The entire construction procedure can be defined as follows:

(4) $\mu_{i}=\text{avgpool}({r}^{\prime}_{i})$ (5)
$GK=\sum_{i=1}^{m}\mu_{i}\cdot k_{i}$ (6) $\hat{R}=R\otimes GK$

As shown in Figure 1, the decoder output of the pre-trained model is the
matrix that includes initial predicted ratings in the missing entries, and
passed to pooling. With item-based average pooling, we summarise each item
information in the rating matrix. Eq. (4) shows the reconstructed item vector
$\hat{r}_{i}$ from the decoder output matrix $R^{\prime}$ is passed to
pooling, and interpreted as item-based summarisation. Let
$M=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}\in\mathbb{R}^{m}$ be the pooling result,
which plays a role as the weights of multiple kernels
$K=\\{k_{1},k_{2},...,k_{m}\\}\in\mathbb{R}^{m\times t^{2}}$. In Eq. (5),
these kernels are aggregated by using an inner product. The result can be
dynamically determined by different weights and different rating matrices so
that it can be regarded as the rating-dependent mechanism. Then, the
aggregated kernel $GK\in\mathbb{R}^{t\times t}$ is used as a global
convolution kernel. We apply a global kernel-based convolution operation to
the user-item rating matrix for global kernel-based feature extraction. In Eq.
(6), $\hat{R}$ is the global kernel-based rating matrix, which is used as
input for fine-tuning, and $\otimes$ denotes a convolution operation.

Auto-Encoder Fine-tuning
We then explore how the fine-tuning process works. The global kernel-based
rating matrix $\hat{R}$ is used as input for fine-tuning. It takes weights of
a pre-trained AE model and makes an adjustment of the model based on the
global kernel-based rating matrix, as depicted in Figure 1. The reconstructed
result from the fine-tuned AE corresponds to the final predicted ratings for
matrix completion in recommender system.

##  3\. EXPERIMENTS

###  3.1. Datasets

We conduct experiments on three widely used matrix completion benchmark
datasets: MovieLens-100K (ML-100K), MovieLens-1M (ML-1M) and Douban (density
0.0630 / 0.0447 / 0.0152). These datasets comprise of
($100\text{\,}\mathrm{\kilo}$ / $1\text{\,}\mathrm{}$ /
$136\text{\,}\mathrm{\kilo}$) ratings of (1,682 / 3,706 / 3,000) movies by
(943 / 6,040 / 3,000) users on a scale of $r\in\\{1,2,3,4,5\\}$. For ML-100K,
we use the canonical u1.base/u1.test train/test split. For ML-1M, we randomly
split into 90:10 train/test sets. For Douban, we use the preprocessed subsets
and splits provided by Monti et al. (2017).

###  3.2. Baselines

We compare the RMSE with the eleven recommendation baselines: (1) LLORMA(Lee
et al., 2016) is a matrix factorization model using local low rank sub-
matrices factorization. (2) I-AutoRec(Sedhain et al., 2015) is a auto-encoder
based model considering only the user or item embeddings in the encoder. (3)
CF-NADE(Zheng et al., 2016) replaces the role of the restricted Boltzmann
machine (RBM) with the neural auto-regressive distribution estimator (NADE)
for rating reconstruction. (4) GC-MC(Berg et al., 2018) is a graph-based AE
framework that applies GNN on the bipartite interaction graph for rating link
reconstruction. We consider GC-MC with side information as (5) GC-MC+Extra.
(6) GraphRec(Rashed et al., 2019) is a matrix factorization utilizing graph-
based features from the bipartite interaction graph. We consider GraphRec with
side information as (7) GraphRec+Extra. (8) GRAEM(Strahl et al., 2020)
formulates a probabilistic generative model and uses expectation maximization
to extend graph-regularised alternating least squares based on additional side
information (SI) graphs. (9) SparseFC(Muller et al., 2018) is a neural network
in which weight matrices are reparameterised in terms of low-dimensional
vectors, interacting through finite support kernel functions. This is
technically equivalent to the local kernel of GLocal-K. (10) IGMC(Zhang and
Chen, 2020) is similar to GCMC but applies a graph-level GNN to the enclosing
one-hot subgraph and maps a subgraph to the rating in an inductive manner.
(11) MG-GAT(Ugla et al., 2020) uses attention mechanism to dynamically
aggregate neighbor information of each user (item) for learning latent
user/item representations.

###  3.3. Experimental Setup

We use two 500-dimensional hidden layers for AE and 5-dimensional vectors
$u_{i}$, $v_{j}$ for the RBF kernel. For fine-tuning, we use a single
convolution layer with a 3x3 global convolution kernel. Inspired by (Sedhain
et al., 2015), we train our model using the L-BFGS-B optimiser to minimise
regularised squared errors, where $L_{2}$ regularisation is applied with
different penalty parameters $\lambda_{2}$, $\lambda_{s}$ for weight and
kernel matrices respectively. Based on validation results, we choose the
following settings for (ML-100K / ML-1M / Douban). (1) L-BFGS-B: $maxiter_{p}$
= (5 / 50 / 5), $maxiter_{f}$ = (5 / 10 / 5)222maxiter is maximum number of
iterations (p=pre-training, f=fine-tuning)., (2) $L_{2}$ regularisation:
$\lambda_{2}$ = (20 / 70 / 10), $\lambda_{s}$ = (.006 / .018 / .022). We
repeat each experiment five times and report the average RMSE results.

##  4\. Results

###  4.1. Overall Performance

Table 1. RMSE test results on three benchmark datasets. The column Extra. represents whether the model utilises any side information. All RMSE results are from the respective papers cited in the first column, and the best results are highlighted in bold. Model | Extra. | ML-100K | ML-1M | Douban
---|---|---|---|---
LLORMA(Lee et al., 2016) | - | - | 0.833 | -
I-AutoRec(Sedhain et al., 2015) | - | - | 0.831 | -
CF-NADE(Zheng et al., 2016) | - | - | 0.829 | -
GC-MC(Berg et al., 2018) | - | 0.910 | 0.832 | -
GC-MC+Extra.(Berg et al., 2018) | O | 0.905 | - | 0.734
GraphRec(Rashed et al., 2019) | - | 0.904 | 0.843 | -
GraphRec+Extra.(Rashed et al., 2019) | O | 0.897 | 0.842 | -
GRAEM(Strahl et al., 2020) | O | 0.917 | - | 0.732
SparseFC(Muller et al., 2018) | - | 0.895 | 0.824 | 0.730
IGMC(Zhang and Chen, 2020) | - | 0.905 | 0.857 | 0.721
MG-GAT(Ugla et al., 2020) | O | 0.890 | - | 0.727
GLocal-K (ours) | - | 0.890 | 0.822 | 0.721

We first evaluated our GLocal-K model on ML-100K (u1.base/u1.test split)/-1M
datasets and compare with the baseline models. The RMSE test results are
provided in Table 1. It can be easily observed from both GC-MC and GraphRec
that incorporate side information improves the recommendation performance,
e.g., the error rate of GC-MC+Extra. and GraphRec+Extra. reduce by 0.001 and
0.007 respectively on ML-100K via side information inclusion. Similar to GC-
MC, IGMC also learns graph-structural relations from the bipartite user-item
interaction graph derived from the rating matrix using GNN but outperforms GC-
MC+Extra. by focusing on one-hot sub-graphs with inductive matrix completion.
GRAEM focuses on additional graph SI and MG-GAT uses auxiliary information to
represent user-user and item-item graph relations. Different from those models
above, the first three models in the table use only the rating matrix
structure and achieve better results on ML-1M. Our proposed GLocal-K also
draws on the rating matrix structure and uses no extra information,
outperforming all the baseline models above on three datasets, including those
with additional side information, which illustrates the efficacy of combining
the local-global kernels for recommendation tasks. Moreover, SparseFC also
achieves higher accuracy than those baseline models on three datasets except
for MG-GAT, showing the benefits of proper kernel-approximations of the weight
matrix. Our GLocal-K surpasses SparseFC, further illustrating the
effectiveness of a global kernel that learns to refine and extract the
relevant information from the sparse data matrix.

###  4.2. Cold-start Recommendation

Figure 2. Performance comparison w.r.t. different sparsity levels on ML-100K
and Douban datasets.

We varied the training ratio from 0.2 to 1.0 and compared the RMSE test
results with SparseFC on ML-100K and Douban in Figure 2. It can be seen that
both models on the two datasets demonstrate a similar overall trend: the error
rate increases as the training size decreases, which complies with
conventional expectation. More specifically, with training ratios of 0.4-1.0,
GLocal-K outperforms SparseFC by a merely constant gap on both ML-100K and
Douban. This illustrates the superior effectiveness of cooperation by local
and global kernels of GLocal-K. In addition, when training size reduces from
0.4 to 0.2 on Douban, the error rate of SparseFC deviates from the previous
curve and goes up dramatically while GLocal-K still rises at a stable rate as
on ML-100K. This implies that the global kernel can deal with scarce data via
feature extraction.

###  4.3. Effect of Pre-training

Figure 3. Performance comparison w.r.t. the number of pre-training epochs on
three benchmark datasets.

We explored the optimal number of epochs for pre-training on ML-100K, ML-1M
and Douban. The RMSE results for the three datasets using pre-training epochs
from 0 (i.e., no pre-training) to 60 are provided in Figure 3. These three
datasets represent similar bowl-shaped curves. The RMSE first keeps decreasing
as the pre-training epoch increases from 0, indicating that pre-training
benefits GLocal-K to achieve better performance on all three datasets. Then
the RMSE starts to go up again after reaching its optimum at 30 epochs for
ML-100K and 20 epochs for both ML-1M and Douban. Referring to the dataset
statistics, we surmise that having more item numbers with lower density may
lead to less pre-training for optimal performance.

###  4.4. Effect of Global Convolution Kernel

Table 2. Performance comparison of RMSE test results of Global Kernel w.r.t. (1) different convolution kernel sizes, (2) different numbers of convolution layers and (3) different kernel aggregation mechanisms on three benchmark datasets. The best results are highlighted in bold. | ML-100K | ML-1M | Douban
---|---|---|---
Kernel size |  |  |
3x3 | 0.890 | 0.822 | 0.721
5x5 | 0.891 | 0.823 | 0.723
7x7 | 0.891 | 0.823 | 0.723
# Conv layers |  |  |
1 | 0.890 | 0.822 | 0.721
2 | 0.893 | 0.827 | 0.725
3 | 0.897 | 0.848 | 0.732
Agg. mechanism |  |  |
Element-wise | 0.894 | 0.822 | 0.730
Weighted | 0.890 | 0.822 | 0.721

To explore the effectiveness of the global kernel-based convolution with in-
depth analysis, we first tried multiple kernel sizes and convolution layers.
The RMSE results on the three datasets are presented in Table 2. It can be
seen from Table 2 that using 3x3 sized kernel achieves the best performance on
all three datasets and the error rate goes up as the size increases to 5x5 or
7x7. It implies that focusing on more local features with smaller kernel size
might be more effective for extracting generalizable patterns over the whole
data matrix. Moreover, Table 2 shows an incremental performance degradation
when the conv layer increases from 1 to 3, indicating a single convolution
layer is enough and optimal for feature extraction. In addition, we also
explored two variants of kernel aggregation mechanisms: (1) integrating
multiple kernels based on the weights and (2) aggregating via pure element-
wise average. As shown in Table 2, weight-based aggregation reduces RMSE by
0.004 and 0.009 on ML-100K and Douban while achieving similar performance on
ML-1M. Overall, it can be seen that using feature-indicative weights to
aggregate the kernels is more effective than purely applying element-wise
averages.

##  5\. Conclusion

In this paper, we introduced GLocal-K for recommender systems, which takes
full advantage of both a local kernel at the pre-training stage and a global
kernel at the fine-tuning stage for capturing and refining the important
characteristic features of the sparse rating matrix under an extremely low
resource setting. We demonstrate RMSE on three benchmark datasets:
MovieLens-100k/-1M and Douban, outperforming numerous baseline approaches. In
particular, we highlighted the effectiveness of our global kernel for exerting
scarce data by evaluating the cold-start recommendation. It is hoped that our
Global-K gives some insight into the future integration of both kernels for
high-dimensional sparse matrix completion with no side information.

## References

  * (1)
  * Berg et al. (2018) Rianne van den Berg, Thomas N Kipf, and Max Welling. 2018\.  Graph convolutional matrix completion.  _KDD Deep Learning Day_ (2018).
  * Candès and Recht (2009) Emmanuel J Candès and Benjamin Recht. 2009.  Exact matrix completion via convex optimization.  _Foundations of Computational mathematics_ 9, 6 (2009), 717–772.
  * Giannakopoulos et al. (2008) Theodoros Giannakopoulos, Aggelos Pikrakis, and Sergios Theodoridis. 2008.  A novel efficient approach for audio segmentation. In _2008 19th International Conference on Pattern Recognition_. IEEE, 1–4.
  * Lee et al. (2016) Joonseok Lee, Seungyeon Kim, Guy Lebanon, Yoram Singer, and Samy Bengio. 2016.  LLORMA: Local Low-Rank Matrix Approximation.  _Journal of Machine Learning Research_ 17, 15 (2016), 1–24.
  * Monti et al. (2017) Federico Monti, Michael M Bronstein, and Xavier Bresson. 2017\.  Geometric matrix completion with recurrent multi-graph neural networks. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_. 3700–3710.
  * Muller et al. (2018) Lorenz Muller, Julien Martel, and Giacomo Indiveri. 2018\.  Kernelized synaptic weight matrices. In _International Conference on Machine Learning_. PMLR, 3654–3663.
  * Rashed et al. (2019) Ahmed Rashed, Josif Grabocka, and Lars Schmidt-Thieme. 2019\.  Attribute-aware non-linear co-embeddings of graph features. In _Proceedings of the 13th ACM Conference on Recommender Systems_. 314–321.
  * Sedhain et al. (2015) Suvash Sedhain, Aditya Krishna Menon, Scott Sanner, and Lexing Xie. 2015.  Autorec: Autoencoders meet collaborative filtering. In _Proceedings of the 24th international conference on World Wide Web_. 111–112.
  * Strahl et al. (2020) Jonathan Strahl, Jaakko Peltonen, Hirsohi Mamitsuka, and Samuel Kaski. 2020.  Scalable probabilistic matrix factorization with graph-based priors. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 5851–5858.
  * Ugla et al. (2020) A Ugla, Dhuha J Kamil, Hassan J Khaudair, et al. 2020\.  Interpretable Recommender System With Heterogeneous Information: A Geometric Deep Learning Perspective.  _International Journal of Mechanical and Production Engineering Research and Development (IJMPERD)_ 10, 3 (2020), 2411–2430.
  * Zhang et al. (2020) Guijuan Zhang, Yang Liu, and Xiaoning Jin. 2020.  A survey of autoencoder-based recommender systems.  _Frontiers of Computer Science_ 14, 2 (2020), 430–450.
  * Zhang and Chen (2020) Muhan Zhang and Yixin Chen. 2020.  Inductive Matrix Completion Based on Graph Neural Networks. In _International Conference on Learning Representations_.
  * Zheng et al. (2016) Yin Zheng, Bangsheng Tang, Wenkui Ding, and Hanning Zhou. 2016\.  A neural autoregressive approach to collaborative filtering. In _International Conference on Machine Learning_. PMLR, 764–773.