PA-GM: Position-Aware Learning of Embedding Networks for Deep Graph Matching

In this paper, we denote a graph by the triple $\mathcal{G}=(V,A,X)$ which consists of a finite set of nodes $V$, an adjacency matrix $A$, and a set of node attributes $X$ extracted from images using CNN-based models[9, 10]. We construct a vector $\mathbf{v}\in\{0,1\}^{nm\times 1}$ to indicate the match of vertices in the source graph $\mathcal{G}_{s}=(V_{s},A_{s},X_{s})$ and the target graph $\mathcal{G}_{t}=(V_{t},A_{t},X_{t})$. The vector has elements $\mathbf{v}_{i,j}=1$ if vertex $i\in V_{s}$ is matched to vertex $j\in V_{t}$, and $\mathbf{v}_{i,j}=0$ if otherwise. It is worth noting that all the vertex matches are subject to one-to-one mapping constraints $\sum_{j\in V_{t}}\mathbf{v}_{i,j}=1\;\forall i\in V_{s}$ and $\sum_{i\in V_{s}}\mathbf{v}_{i,j}\leq 1\;\forall j\in V_{t}$. Furthermore, we construct a square symmetric positive matrix $M\in\mathbb{R}^{nm\times nm}$ as the affinity matrix, to encode the edge-to-edge affinity between two graphs in the off-diagonal elements. In this way, the two-graph matching between $\mathcal{G}_{s}$ and $\mathcal{G}_{t}$ can be formulated as an edge-preserving, quadratic assignment programming (QAP) problem [11]:

where $\mathbf{v}\in\{0,1\}^{nm\times 1}$ and $M\in\mathbb{R}^{nm\times nm}$. The goal of graph matching is to establish a correspondence between two attributed graphs, which minimizes the sum of local and geometric costs of assignment between the vertices of the two graphs.

Pixels at neighboring positions in the image convey similar semantic information, therefore we need to distinguish them to resolve matching ambiguities. Here, we refer to the nodes used as reference positions named as anchors and propose an effective strategy to construct an anchor set $P$ consisting of all nodes in the graph, denoted by $P=V$, serving as a stable reference for all nodes. To combine information from the nodes and the anchors, we design the information aggregation mechanism as is shown in Fig.3.

Considering that the amount of effective information transmission to the nodes by the anchors with different relative distances is different, we first compute a relative position coefficient $q_{v,u}$ between a pair of nodes $v$ and $u$ as:

where $d_{v,u}$ is the shortest path distance between the two nodes. In practice, to effectively reduce the time complexity of calculating the shortest path and also to reduce interference from those anchor points that are distant from the node under consideration, we demand that the maximum shortest path distance does not exceed the ceiling value $r$. Otherwise, the value of the coefficient is set to infinity. We continue to compute the information aggregation function $I(v,u)^{(l)}$ for the $l$-th layer between node $v$ and $u$ as:

where $h_{v}^{(l-1)}$ and $h_{u}^{(l-1)}$ are the feature representation and position representation in the $(l-1)$-th layer, and are combined through the message aggregation function. We further aggregate the information from all node-anchor pairs to obtaining a new representation in a high dimensional space using the non-linear variation. This hidden representation can be computed using the update

where AGG is typically a permutation-invariant function (e.g., sum), and $W^{(l)}$ is a learnable weight vector for the $l$-th layer.

Utilizing the proposed position-aware node embedding, the proposed scheme encodes each node with position information into a high-level embedding space. In this way, we can simplify the second-order affinity matrix of paired graphs to a be a linear one with position-aware learning of the embedding. With the final hidden representation of the source graph $H_{s}\in\mathbb{R}^{n*F^{\prime}}$ and the target graph $H_{t}\in\mathbb{R}^{m*F^{\prime}}$ to hand, we can obtain a soft correspondence between these graphs with a node-wise affinity matrix through the inner product of the embeddings of the two graphs being matched. Specifically, to satisfy the condition that the original graph maps injectively onto the target graph, we apply the Sinkhorn normalization [12] to obtain rectangular doubly-stochastic correspondence matrices.

We further employ the cross-entropy loss function as the permutation loss between the predicted permutation matrix and the ground truth:

where $\mathbf{S}^{gt}$ is the ground truth permutation matrix. Consequently, the cross-entropy loss based on linear allocations can be learned end-to-end no matter the number of nodes and edges in the graph.

Dataset. We use the Willow Object Class [13], consisting of 9963 images in total and is used as a benchmark by many methods to measure the accuracy of image classification and recognition algorithms. And IMC-PT-SparseGM [14] datasets, containing 16 object categories and 25061 images, which gather from 16 tourist attractions around the world. https://www.di.ens.fr/willow/research/graphlearning/.

Implementation Details. The experiments are conducted using two GeForce GTX 1080 Ti GPUs. We employ a batch size of 8 in training and evaluate the results of our method after 2000 epochs for each iteration. We employ the Adam [15] optimizer to train our models with a learning rate of $1\times 10^{-4}$. To overcome the over-smoothing problem common to graph neural network models, we adopt a two-layer graph embedding and restrict the degree of smoothing in our experiments.

Metrics. We evaluate the graph matching capacity of the proposed method using the matching accuracy, which is defined by $accuracy=\sum{{\rm{AND}}(S_{i,j},{S_{i,j}^{gt}})/N}$ from [8, 16]. Note that $S_{i,j}$ is the element of the predicted permutation matrix representing the correspondence matching of node $i$ and node $j$ from two different graphs. Similarly, $S_{i,j}^{gt}$ is the correspondence of the ground truth between two nodes, and $N$ is the number of matching node pairs.

Table 1 and Table 2 report the overall comparison of the performance results for graph matching accuracy. The CIE-H method excels on the M-bike and W-bottle classes of the Willow ObjectClass dataset, while our method scores highest in the two categories of accuracy, and the average accuracy. By successfully incorporating the position information, our model achieves excellent results in the average accuracy of Willow ObjectClass and IMC-PT-SparseGM datasets. Based on these results, it can be concluded that our method performs well on graph matching compared with existing methods.

To assess the robustness and generalization ability of our method on the different object categories, we further conduct the cross-category generalization study. Specifically, we train each of the five classes separately, and then test the generalization ability of the validation model for all five classes with the separate training classes. Comparing the elements of Fig. 4, it is clear that the generalization ability of the model framework that incorporates position information is superior to the alternative methods. In addition, the matching accuracy for face data is generally rather large. This may be related to the relatively simple background of the data and less interference from noise.