-
Notifications
You must be signed in to change notification settings - Fork 0
/
03b_graph_matching.tex
97 lines (84 loc) · 6.6 KB
/
03b_graph_matching.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
\section{Graph Matching}
As described in \ref{section:related_work} Related Work, \cite{fey2020_update} have recently proposed a similar model, the Deep Graph Consensus (DGC), to predict soft matchings between nodes. They train on the negative log-likelihood between the soft matching and some ground truth matching (following \citealp{wang2019}). The final performance is measured by how often the row-wise maximum in the soft matching yields the correct match (Hits@1).
To show that it is advantageous to apply the Sinkhorn normalization to the kernel matrix instead of the cost matrix directly, we also run the keypoint matching experiment of \cite{fey2020_update} on the PASCALVOC dataset (\citealp{pascal2010}) with Berkeley annotations (\citealp{annotations2009}).
To align our model as much as possible with their work we use the same SplineCNN (\citealp{spline2018}) with the same embedding size and number of layers to generate node embeddings. We use $p=2$ for our norm (to avoid using additional parameters), and the no-BP variant of the cost matrix because the graphs are built such that every node in the first (source) graph has a match in the second (target) graph. Therefore, the network would only learn to predict 0’s for the additional values. This left us with only the learning rate and the regularization constant $\lambda$ to tune. For numeric stabilization we scaled the kernel matrix by the sum of all entries divided by the number of entries: $\text{reg}^l = \frac{\norm{C^l}_1}{\max(N_1,N_2)^2}$. We also implemented a consensus step. For a detailed comparison of the two models see \mbox{Appendix \ref{appendix:consensus}}.
In Table \ref{tab:ex2} we report results on the test set of the model with the best validation performance across 18 runs (3 trials, 2 learning rates, and 3 regularization constants), and compare these to the numbers reported by \cite{fey2020_update}. The table shows that using the kernel matrix and the inherent ability to tune the regularization constant improves the base model without consensus. The 3 percent points gain constitute over half of the gains made by the original consensus step. Unfortunately, applying the consensus step to our model was not successful. In fact, by adding our consensus step the performance drops slightly. We believe that the consensus step should be orthogonal to the gains due to the kernel matrix. However, so far, we were not able to improve upon the poor performance even after multiple tweaks to the cost matrix generation.
\begin{table}[ht]
\centering
\resizebox{\textwidth}{!}{\begin{tabular}{ccccccccccccccccccccccc}
\hline
\textbf{Method}& &\textbf{Aero}&\textbf{Bike}&\textbf{Bird}&\textbf{Boat}&\textbf{Bottle}&\textbf{Bus}&\textbf{Car}&\textbf{Cat}&\textbf{Chair}&\textbf{Cow}&\textbf{Table}&\textbf{Dog}&\textbf{Horse}&\textbf{M-Bike}&\textbf{Person}&\textbf{Plant}&\textbf{Sheep}&\textbf{Sofa}&\textbf{Train}&\textbf{TV}&\textbf{Mean} \\
\hline
DGC & L=0 &42.1&57.5&49.6&59.4&83.8&84.0&78.4&67.5&37.3&60.4&85.0&58.0&66.0&54.1&52.6&93.9&60.2&85.6&87.8&82.5&67.3\\
\hline
GDN & L=0&45.3&63.8&55.5&72.6&88.9&88.5&79.5&69.1&36.8&58.5&82.8&59.2&70.1&59.8&53.4&96.3&63.7&92.5&91.7&85.0&70.5\\
\hline
DGC & L=10&45.5&67.6&56.5&66.8&86.9&85.2&84.2&73.0&43.6&66.0&92.3&64.0&79.8&56.6&56.1&95.4&64.4&95.0&91.3&86.3&72.8\\
\hline
GDN & L=10&40.2&59.6&50.1&65.0&87.8&86.7&82.3&69.6&37.4&59.0&93.1&56.7&73.1&52.9&58.5&96.3&62.1&90.0&93.4&87.3&70.0\\
\hline
\end{tabular}}
\caption{Hits@1 (\%) on the PASCALVOC dataset with Berkeley keypoint annotations}
\label{tab:ex2}
\end{table}
% 0.4016 0.5957 0.5005 0.6497 0.8784 0.8669 0.8227 0.6962 0.3740 0.5895 0.9310 0.5673 0.7313 0.5288 0.5853 0.9634 0.6207 0.8955 0.9337 0.8725
% 0.7003
% "config" : {
% "alpha_vector" : true,
% "batch_size" : 512,
% "bp_dist_matrix" : false,
% "consensus_type" : "none",
% "dataname" : "pascal",
% "db_collection" : "gdn_match_report_test2",
% "device" : "cuda",
% "emb_dist_p" : 2,
% "gnn_type" : "spline",
% "graph_distance" : "matching",
% "learning_rate" : 0.01,
% "max_epochs" : 100,
% "model_type" : "gdn",
% "overwrite" : 45,
% "patience" : 5,
% "run" : 0,
% "seed" : 318116669,
% "sinkhorn_reg" : 0.1,
% "sparse_batching" : false
% },
% Epoch 13/99, train loss: 11.3083, hits@1: 0.7304 (5.90s)
% 2020-03-04 12:50:46 (INFO): Epoch 13/99, val 0.4341 0.5750 0.6551 0.6753 0.8093 0.7804 0.7854 0.6490 0.4232 0.6160 0.8913 0.6165 0.6332 0.6561 0.6108 0.9710 0.6804 0.6545 0.8833 0.8951
% 2020-03-04 12:50:46 (INFO): Epoch 13/99, val loss: 13.9017, hits@1: 0.6948 (3.39s)
% 2020-03-04 12:50:49 (INFO): Epoch 13/99, test 0.4533 0.6383 0.5547 0.7259 0.8890 0.8506 0.7945 0.6909 0.3682 0.5850 0.8276 0.5924 0.7071 0.5984 0.5341 0.9634 0.6371 0.9254 0.9171 0.8500
% 2020-03-04 12:50:49 (INFO): Epoch 13/99, test loss: 13.2461, hits@1: 0.7052 (3.38s)
% 0.4533 0.6383 0.5547 0.7259 0.8890 0.8506 0.7945 0.6909 0.3682 0.5850 0.8276 0.5924 0.7071 0.5984 0.5341 0.9634 0.6371 0.9254 0.9171 0.8500
% 0.7052
% "config" : {
% "alpha_vector" : true,
% "batch_size" : 512,
% "bp_dist_matrix" : false,
% "consensus_emb_size" : 128,
% "consensus_nlayers" : 10,
% "consensus_p_norm" : 777,
% "consensus_type" : "spline",
% "dataname" : "pascal",
% "db_collection" : "gdn_match_report_test2",
% "device" : "cuda",
% "emb_dist_p" : 2,
% "gnn_type" : "spline",
% "graph_distance" : "matching",
% "learning_rate" : 0.01,
% "max_epochs" : 100,
% "model_type" : "gdn",
% "overwrite" : 124,
% "patience" : 5,
% "run" : 0,
% "seed" : 147824079,
% "sinkhorn_reg" : 0.05,
% "sparse_batching" : false
% },
% 13/99, train loss: 22.2035, hits@1: 0.7305 (33.48s)
% 2020-03-04 14:03:46 (INFO): Epoch 13/99, val 0.3795 0.5732 0.6840 0.7226 0.8725 0.8210 0.7388 0.6151 0.4173 0.5593 0.9130 0.6505 0.6246 0.5844 0.6165 0.9574 0.6769 0.5864 0.9389 0.9244
% 2020-03-04 14:03:46 (INFO): Epoch 13/99, val loss: 29.4006, hits@1: 0.6928 (9.32s)
% 2020-03-04 14:03:56 (INFO): Epoch 13/99, test 0.4016 0.5957 0.5005 0.6497 0.8784 0.8669 0.8227 0.6962 0.3740 0.5895 0.9310 0.5673 0.7313 0.5288 0.5853 0.9634 0.6207 0.8955 0.9337 0.8725
% 2020-03-04 14:03:56 (INFO): Epoch 13/99, test loss: 27.7569, hits@1: 0.7003 (9.29s)\n
% 0.4016 0.5957 0.5005 0.6497 0.8784 0.8669 0.8227 0.6962 0.3740 0.5895 0.9310 0.5673 0.7313 0.5288 0.5853 0.9634 0.6207 0.8955 0.9337 0.8725
% 0.7003