deep-graph-matching-consensusの調査

### 目標 Deep Graph Matching Consensus（DGMC）のGithub公開コード（https://github.com/rusty1s/deep-graph-matching-consensus ）を、FlatMapの隣接行列で扱えるようにするため、コード中で扱われるデータの入出力について調査する ### 調査結果 #### 調査したデータセット PascalVOCなど、画像を使ったデータセットではなく、DBP15kという、言語の対応関係を知識グラフにしたデータセットについて調査を行った。（画像データが元となるグラフマッチングだと、物体の物理的な位置座標がデータに必要なため、今回のタスクには合わないと判断した） DBP15kは、以下のようなデータセットである "DBP15k contains four language-specific KGs that are respectively extracted from English (En), Chinese (Zh), French (Fr) and Japanese (Ja) DBpedia, each of which contains around 65k-106k entities. Three sets of 15k alignment labels are constructed to align entities between each of the other three languages and En." ### 入力情報 DGMCの論文中では、問題設定を以下のように設定している。 ![](https://hackmd.io/_uploads/SkMApgrKn.png) グラフGを準備し（そこにはノードνと隣接行列A、ノード特徴量Xとエッジ特徴量Eがあるとする） SourceグラフG_sと、TargetグラフG_tを対応させる（一致させる）問題を解くというもの。 one-to-one mappingとも言うらしい、つまり基本的には、ノードとノードのマッチング問題を解くとも言える。これはプログラム上ではhttps://github.com/rusty1s/deep-graph-matching-consensus/blob/master/examples/dbp15k.py　のl27に当たり、 l27はhttps://pytorch-geometric.readthedocs.io/en/latest/_modules/torch_geometric/datasets/dbp15k.html#DBP15K　のprocess関数を呼び出している。そこでは ``` g1_path = osp.join(self.raw_dir, self.pair, 'triples_1') x1_path = osp.join(self.raw_dir, self.pair, 'id_features_1') g2_path = osp.join(self.raw_dir, self.pair, 'triples_2') x2_path = osp.join(self.raw_dir, self.pair, 'id_features_2') x1, edge_index1, rel1, assoc1 = self.process_graph( g1_path, x1_path, embs) x2, edge_index2, rel2, assoc2 = self.process_graph( g2_path, x2_path, embs) ``` と記載されていて、グラフ情報を、DBP15kのデータセットのうち、triples_1, triples_2から取り出し、ノード情報を、id_features_1, id_features_2から取り出していることがわかる。それぞれのファイルの内容を見てみると、id_featuresには ``` 0 Allianz Riviera 1 José Mario Vas 2 Free Software Foundation 3 Malmö FF 4 Rajendra · Bikram · Shaha 5 Dream Evil 6 Felix Grandy ``` 各ノードIDに対応する情報が入っていて tiplesには ``` 21964 768 9781 2241 537 4105 9366 414 102 23709 824 6997 6200 90 6314 3390 369 4038 2232 339 7968 ``` 各行が、三角形（グラフで言うと最短閉路）を構成しているノードIDを記録している。これらの情報から、ノード情報及びエッジの情報にprocess_graph関数で整理し、データ化している。この時、0 Allianz Rivieraのように、そのまま文字を情報量として使うことはできないので、Word2Vecのような埋め込みデータを使って、単語情報を特徴量に変換しておく、これが、DBP15kだと、あらかじめ、sub.glove.300dというファイルに単語を300次元に埋め込んだ場合のベクトルが記録されている。 ``` the -0.20838 -0.14932 -0.017528 -0.028432 -0.060104 -0.2646 -4.1445 0.62932 0.33672 -0.43395 0.39899 -0.19573 0.13977 -0.021519 0.37823 -0.5525 -0.1123 -0.0081443 0.29059 0.066817 0.10465 -0.086943 -0.048983 -0.26757 -0.47038 0.27469 0.069245 -0.027967 -0.19719 0.016749 -0.29681 0.17838 0.058374 -0.24806 0.085846 0.35043 0.049157 -0.16431 0.50012 -0.18053 0.31422 0.10671 0.031852 0.074278 0.27956 0.080317 0.05478 -0.30349 -0.43215 0.32417 0.40856 0.36192 0.13445 -0.12933 0.11331 -0.15755 0.35755 0.30463 -0.098488 0.012032 0.45581 0.37101 0.1427 -0.43329 -0.10869 0.49849 0.54455 0.44352 0.31804 0.022171 -0.41186 -0.025428 0.21062 -0.3583 0.22028 -0.55391 -0.035364 -0.053998 0.32172 -0.51928 -0.27427 -0.45214 -0.329 -0.48519 0.52966 0.0041434 -0.1718 -0.18748 -0.24365 -0.060786 0.050733 -0.21335 0.27627 0.42745 0.011461 -0.29794 -3.2881 -0.39842 0.16796 -0.12894 0.0020005 0.45613 0.15215 0.15364 -0.21281 -0.25339 0.28955 -0.57817 -0.6074 0.10301 0.28324 0.21506 -0.042325 0.40479 -0.20579 -0.011674 0.26092 -0.15402 0.057961 -0.058576 -0.41974 0.52015 0.15074 -0.088039 -0.14446 -0.17074 0.083752 -0.25708 0.16362 0.14795 -0.059821 0.034473 -0.14534 -0.17965 0.076303 0.33354 -0.14434 0.17618 0.45345 0.15262 -0.0751 0.27592 0.081456 0.30738 -0.072327 0.10706 -0.35581 -0.02669 0.61236 0.70829 -0.28945 -0.024637 0.01189 -0.091899 -0.27272 -0.10157 0.44713 0.092418 -0.10711 -0.015552 0.12822 0.22256 -0.069059 0.29927 -0.10913 0.1618 0.14796 0.1136 0.26634 0.010832 0.071946 0.16973 -0.22769 0.322 -0.083748 0.65269 0.068244 -0.32687 0.31782 0.17035 0.79803 -0.19194 -0.16485 -0.32437 0.079105 -0.35672 -0.26786 -0.24786 0.70512 -0.11909 0.16256 -0.43259 -0.050078 0.050232 -0.1145 -0.041885 0.47866 0.012767 0.19642 0.26196 -0.29425 0.089615 -0.17736 -0.22448 0.22624 0.16749 0.05577 0.14399 0.2158 0.33819 0.23459 0.15826 -0.2856 0.24199 0.11018 0.38164 -0.2984 -0.20169 0.2695 0.11186 -0.21006 -0.04207 0.016507 -0.22866 -3.3882 0.29204 -0.088358 -0.014966 -0.25225 -0.11503 0.036337 -0.14817 0.04622 -0.073466 -0.13866 0.23612 0.033882 0.29495 -0.61234 0.20289 -0.42091 0.37767 0.03626 0.21708 0.12561 -0.21682 -0.0037997 -0.17791 -0.26431 0.31678 -0.051229 0.049269 -0.12622 -0.10117 0.017246 -0.02195 -0.1982 0.03725 -0.16791 -0.055459 0.5767 0.059123 0.22931 0.064201 0.27424 -0.37129 -0.091375 -0.071342 -0.037218 -0.012668 -0.017976 -0.42622 -0.10095 0.044992 -0.090225 0.22915 0.1861 0.36366 -0.20676 -0.33037 0.47302 0.2338 0.079306 0.21083 0.21013 0.15275 0.080873 -0.33013 -0.17181 -0.07017 -0.041244 -0.46182 0.027903 0.54657 -0.25894 0.39515 0.26144 -0.54066 0.21199 -0.0094357 ``` たとえば上のような感じで、theという単語を300次元のベクトルに埋め込んでいる。これは埋め込みに使用したモデルがGloVeなので、sub.glove.300dというファイル名になっている。ここまでの手順をまとめると * ノード特徴量は、単語埋め込みをあらかじめ行ったファイルを読んで、ノード特徴を表すファイルをx1という変数に記録する。 * エッジ情報は、tripleという最小閉路を記録したデータから、エッジの情報がわかるようにしている * その時に呼び出している関数は、self.process_graph(g1_path, x1_path, embs)、g1_pathは閉路の情報、x1_pathはノード特徴量、embsは単語を300次元に変換するためのファイル最後に、データをSource、Targetそれぞれ別の変数に保存するようにしている。 ``` data = Data(x1=x1, edge_index1=edge_index1, rel1=rel1, x2=x2, edge_index2=edge_index2, rel2=rel2, train_y=train_y, test_y=test_y) ``` #### モデルへの入力 dataの成形が終わると、ノード特徴量と、エッジの一覧を出したデータができるので、実際にモデルに投入する。実際には、グラフそのものの一致度を計算するのではなくて、それぞれのグラフをGraph Convolution Networkに入力して、GCNから出力されるHをマッチングに用いるようだ、論文中では、アルゴリズム表の、最初のψの部分に当たる。 ![](https://hackmd.io/_uploads/HJYZwbBYn.png) プログラム上では、 ``` psi_1 = RelCNN(data.x1.size(-1), args.dim, args.num_layers, batch_norm=False, cat=True, lin=True, dropout=0.5) psi_2 = RelCNN(args.rnd_dim, args.rnd_dim, args.num_layers, batch_norm=False, cat=True, lin=True, dropout=0.0) model = DGMC(psi_1, psi_2, num_steps=None, k=args.k).to(device) ... _, S_L = model(data.x1, data.edge_index1, None, None, data.x2, data.edge_index2, None, None, data.train_y) ``` にあたる。ここで、modelの関数をみると、forwardの中で行われている処理では、 ``` o_s = self.psi_2(r_s, edge_index_s, edge_attr_s) o_t = self.psi_2(r_t, edge_index_t, edge_attr_t) o_s, o_t = to_dense(o_s, s_mask), to_dense(o_t, t_mask) D = o_s.view(B, N_s, 1, R_out) - o_t.view(B, 1, N_t, R_out) S_hat = S_hat + self.mlp(D).squeeze(-1).masked_fill(~S_mask, 0) S_L = masked_softmax(S_hat, S_mask, dim=-1)[s_mask] return S_0, S_L ``` とあって、二つのGCNから出てきたo_sとo_tをアルゴリズムの表の通りに処理している。結果として出力されるのは、 ``` y (LongTensor, optional): Ground-truth matchings of shape :obj:`[2, num_ground_truths]` ``` と同じ次元の出力で、yには ``` 0 10500 1 0 20620 0 0 32221 0 0 33225 0 0 18267 0 0 33480 0 0 32525 0 0 11950 0 0 12809 0 0 16914 0 0 37530 0 0 17705 0 0 20769 0 0 16620 0 0 12015 0 0 36013 0 0 11129 0 0 37982 0 0 35364 0 0 34803 0 1 35648 0 1 33469 0 1 17493 0 1 19107 0 1 31141 0 1 18793 0 1 12926 0 1 10501 1 ``` というデータをhttps://pytorch-geometric.readthedocs.io/en/latest/_modules/torch_geometric/datasets/dbp15k.html#DBP15K にあるprocess_yという関数で教師データに変換している。この教師信号が良くわからない（タスクの説明があまりない）ので、ノード単位なのか、グラフ単位に対する教師なのかが不明。ただし、前述したid_featuresをみると、左側がid_features1で、右がid_features2に対応しているので、おそらくノードの一致情報を表すデータのようだ。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.