糞糞糞ネット弁慶

読んだ論文についてメモを書きます.趣味の話は http://repose.hatenablog.com

300 万ノード 1 億エッジからなる日本語版 Wikipedia のリンク構造から学習した見出し語の node2vec (分散表現) を公開しました

タイトルの通りです.Wikipedia 本文を用いた埋め込みは

がありますが,リンク情報を用いた埋め込みは見かけなかったので公開します.このデータが誰かの何かの役に立てば幸いです.

ダウンロードリンク

2 種類のファイルを用意しました.

手法

グラフ埋め込み (Graph Embedding) はノードとエッジからなるグラフデータを入力とし,ノードごとの埋め込み表現 (分散表現, Embedding) を得る手法です.グラフからなんらかの手法でサンプリングを行うことで,順序のあるノードの系列を複数生成し,これを文とみなした上で Skip-Gram with Negative-Sampling を用いてノードに対する分散表現を計算する,というのが現状の僕の理解です.一昨年から自分の中で注目している分野です.

今回は Jure らによって提案された node2vec (node2vec: Scalable Feature Learning for Networks, KDD 2016) を使います.node2vec の説明は元論文を読むか, nzw さんによる node2vec: Scalable Feature Learning for Networks を参照してください.

データ

2019 年 1 月 21 日時点における日本語版 Wikipedia のリンク構造を用います.Wikimedia Downloads に公開されている

  • jawiki-latest-pagelinks.sql.gz : リンク構造が格納されたファイル
  • jawiki-latest-page.sql.gz : ページ ID とそのタイトルが格納されたファイル

の二つを用いることで,日本語版 Wikipedia に存在するすべてのリンク関係のうち,リンク先のページにタイトルが振られているものを全て残しています.

細かい話をすると,jawiki-latest-pagelinks.sql.gz におけるリンク構造は「ページ ID (from_id と呼びましょう)」から「ページタイトル (to_title と呼びましょう)」への形式で記述されているため,to_title に対応するページ ID を jawiki-latest-page.sql.gz から見つけなければなりません.しかし,これらのファイルには

  • from_id に対応するタイトルが jawiki-latest-page.sql.gz に存在しない
  • to_titlejawiki-latest-page.sql.gz に存在しない

といったよくわからない状態が発生します.前者については from_id を新たなタイトルとして扱い,後者についてはそのエッジおよびノードを削除しました.

結果的に,ノード数 3,361,556 件 (ユニークタイトル数 2,953,052 件)*1,エッジ数 118,369,335 本の重み無し有向グラフを構築しました.

構築においては MySQL のダンプファイルを一度データベースにインポートするのではなく, jamesmishra/mysqldump-to-csv: A quickly-hacked-together Python script to turn mysqldump files to CSV files. Optimized for Wikipedia database dumps. を用いて(一部改変して) TSV ファイルに変換しました.これは便利.また作業の都合上,"!'\ といった記号を全てタイトルから削除しています.

計算

実装は Jure らによる実装 (snap-stanford/snap: Stanford Network Analysis Platform (SNAP) is a general purpose network analysis and graph mining library.) を用いました.

計算環境は Google Compute Engine を用いました.特に今回の計算は,

  • コア数が増えれば増えるほど計算が早くなる実装である
  • メモリを非常に消費する (450GB 程度)

といったことから vCPU x 96 / メモリ 624 GB という高スペックなマシン (n1-highmem-96) を使用しました.このマシンは 1 時間あたりの費用が $3.979 と比較的高額ですが,これまで利用していなかった $300 のクレジットがあったので 10 時間ほどかかりましたがどうにか自腹を切らずに済みました.ありがとう Google

デフォルトのパラメータではなぜかすべての値が -nan になってしまうため,# of negative sampling を 4 に,SGD の初期学習率を 0.01 としました (snap-adv/word2vec.h にハードコードされています.引数で変更できるようにしてほしい.).その他のパラメータは node2vec の実装のデフォルト値を設定しています.

得られた埋め込みはどうか

では,得られた埋め込みを使ってみましょう.

jawiki_n2v.w2v_c_formatword2vec C format で記載しているのでそのまま gensim で読み込むことができます.

>>> import gensim
>>> model = gensim.models.KeyedVectors.load_word2vec_format("./jawiki_n2v.w2v_c_format")
>>> model.most_similar("大久保瑠美", topn=3)
[('高橋李依', 0.9941796064376831), ('阿澄佳奈', 0.99155592918396), ('斉藤壮馬', 0.9913237690925598)]
>>> model.most_similar("乃木坂46", topn=3)
[('欅坂46', 0.9911350607872009), ('生駒里奈', 0.9882588386535645), ('シュートサイン', 0.9879196882247925)]
>>> model.most_similar("新宿駅", topn=3)
[('池袋駅', 0.9909403324127197), ('渋谷駅', 0.9906771779060364), ('上野駅', 0.989866316318512)]
>>> model.most_similar("アボカド", topn=3)
[('デヒドロアスコルビン酸', 0.9737377166748047), ('ビタミンB2', 0.9736371636390686), ('ルテイン', 0.9733775854110718)]
>>> model.most_similar("バナナ", topn=3)
[('キャッサバ', 0.9832699298858643), ('ヤムイモ', 0.9814094305038452), ('パパイア', 0.9809246063232422)]

なんとなく本文から学習された埋め込みと違う結果になっていることがわかります. 特に「バナナ」では果物ではなく,「主食」という意味合いでキャッサバやヤムイモが類似していることがわかります.面白いですね.

*1:なぜユニークカウントをしているかというと,異なる namespace に所属している同じタイトルが異なるノードとして扱っているためです.