---
# System prepended metadata

title: 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に対応しているので、おそらくノードの一致情報を表すデータのようだ。