2020 年のグラフ機械学習の新しいトレンド

導入

2020 年はまだ始まったばかりですが、最新の研究論文ではグラフ機械学習 (GML) へのトレンドがすでに見られます。以下は、GML 2020 で何が重要かについての私の考えと、論文についての議論です。

[[314620]]

導入

この記事の目的は、グラフ ニューラル ネットワーク (GNN) などの GML の基本概念を紹介することではなく、トップクラスの科学会議で見られる最先端の研究を紹介することです。

GML分野では150件の論文が提出され、そのうち3分の1が採択されました。これは、受理された論文全体の約 10% に相当します。

私は GML の論文のほとんどを読んでいますが、2020 年の主なトレンドは次のとおりです。

1. GNN についてのより確固とした理論的理解を持つ。
2. 最新かつ最もクールな GNN アプリケーション。
3. ナレッジグラフはますます人気が高まっています。
4. グラフ埋め込みのための新しいフレームワーク

一つずつ見ていきましょう。

1. GNNの理論的理解を深める

この傾向は、GML 分野における成熟した従来のヒューリスティックなアプローチが新しい理論的ソリューションに置き換えられていることを示しているため、私は特に興奮しています。グラフ ニューラル ネットワークについてはまだ理解すべきことがたくさんありますが、GNN がどのように機能するかについては重要な結果がかなりあります。

まず、私のお気に入りの記事の 1 つ、「グラフ ニューラル ネットワークが学習できないこと: 深さと幅」から始めましょう。この論文は、技術的な簡潔さ、高い実用的影響、そして深い理論的洞察の間で見事なバランスを実現しています。

これは、GNN で一般的なグラフ問題 (サイクル検出、直径推定、頂点カバーなど) の解を計算できるようにするには、ノード埋め込みの次元 (ネットワークの幅、w) に層の数 (ネットワークの深さ、d) を掛けたものがグラフのサイズ n に比例する必要がある (つまり、dw = O(n)) ことを示唆しています。

したがって、現在の多くの GNN 実装では、グラフのサイズに比べて層の数 (多くの実装では約 2 ～ 5 層) と埋め込みの次元数 (約 100 ～ 1000 層) が十分に大きくないため、この条件を達成できません。一方、現在の環境では、ネットワークが大きすぎると計算ストレージコストが高くなりすぎるため、「効率的な」GNN をどのように設計すればよいのかという疑問が生じます。これは、将来解決する必要がある問題です。この論文は 80 年代の分散コンピューティング モデルからもインスピレーションを得ており、GNN が本質的に同じことを実行することを示しています。他にもたくさんの結果がありますので、ぜひチェックしてみてください。

同様に、Oono & Suzuki と Barcelo et al. による他の 2 つの論文でも GNN の威力が研究されました。 1 つ目は、グラフ ニューラル ネットワークの損失式であるノード分類のパワーです。これは次のことを示しています。

特定の重み条件下では、レイヤーの数が増えても、GCN はノード次数と接続コンポーネント (ラプラシアン スペクトルによって決定) 以外は何も学習しません。

この結果は、マルコフ過程が唯一の均衡に収束するというよく知られた特性を一般化したものであり、収束率は遷移行列の固有値によって決まります。

2 番目の論文「グラフ ニューラル ネットワークの論理的表現力」では、著者らは GNN とそれらがキャプチャできるノード分類子の種類との関係を示しています。一部の GNN には WL 同型性テストと同じ強力な機能があることはすでにわかっています。つまり、2 つのノードは、GNN によって同じに分類される場合にのみ、WL によって同じ色にされます。しかし、GNN は他の分類関数をキャプチャできるのでしょうか? たとえば、孤立した頂点がある場合にのみグラフのすべてのノードに true を割り当てるブール関数を考えてみましょう。 GNN はこのロジックを捉えることができるでしょうか? 直感的には、できません。GNN はメッセージ パッシング メカニズムであり、グラフの一部と別の部分 (2 つの接続されたコンポーネント) の間にリンクがない場合、2 つの部分間でメッセージは渡されません。したがって、推奨される簡単な修正方法は、すべての機能を更新するときに各ノードがグラフ内の他のすべてのノードに関する情報を持つように、近傍集約の後に読み出し操作を追加することです。

その他の理論的研究には、Hou らによる GNN におけるグラフ情報の使用の測定や、Srinivasan と Ribeiro による役割ベースと距離ベースのノード埋め込みの同等性の測定が含まれます。

2. GNNの新しいクールなアプリケーション

GNN が現実世界のタスクにどのように適用できるかを見るのも興味深いでしょう。今年のアプリケーションには、Javascript のバグ修正、ゲームのプレイ、IQ のようなテストへの回答、TensorFlow 計算グラフの最適化、分子生成、対話システムでの質問生成などが含まれていました。

HOPPITY: 学習グラフ変換により、プログラム内のバグを検出して修正します。コードは抽象構文木に変換され、その後 GNN によって前処理されてコード埋め込みが取得されます。アイデアは、初期状態のグラフを与え、複数回のグラフ編集演算子（ノードの追加または削除、ノードの値またはタイプの置き換え）を通じてグラフを変更することです。グラフのどのノードを変更する必要があるかを理解するために、グラフの埋め込みとこれまでの編集履歴を取得し、ノードを選択するポインター ネットワークを使用します。次に、グラフの埋め込みと編集のコンテキストも取得する LSTM ネットワークを使用してインペインティングが実行されます。著者らは GitHub コミットでこのアプローチを検証し、それほど一般的ではない他のベースラインに比べて大幅な改善を示しました。同様に、Wei らによる研究「LambdaNet: グラフニューラルネットワークを使用した確率的型推論」もそうです。著者らは、プログラム変数をノードとして含み、それらの間の関係（論理的制約（ブール型など）やコンテキスト制約（類似した変数名など）など）を含む型依存性ハイパーグラフを提案しています。次に、まず GNN モデルをトレーニングしてグラフ変数と可能なタイプの埋め込みを生成し、次にこれらの埋め込みを使用して最も可能性の高いタイプを予測します。実験では、LambdaNet は標準変数型 (例: ブール値) とユーザー定義型の両方で優れたパフォーマンスを発揮しました。

Wang らによる論文「多重グラフ ネットワークによる抽象図式的推論」では、GNN を使用して IQ のようなテスト (Raven Progressive Matrices (RPM) と Diagram Syllogism (DS)) で推論を実行する方法が示されています。 RPM タスクでは、マトリックスの各行に対してグラフが構成され、フィードフォワード モデルによってエッジ埋め込みが取得され、その後にグラフィカルな要約が表示されます。最後の行には 8 つの回答の可能性があるので、8 つの異なるグラフが作成され、各グラフが最初の 2 行と連結され、ResNet モデルを通じて IQ スコアが予測されます。

DeepMind の論文「計算グラフを最適化するための強化遺伝的アルゴリズム学習」では、TensorFlow 計算グラフの計算コストを最適化する RL アルゴリズムが提案されています。グラフは標準のメッセージ パッシング GNN によって処理され、グラフ内の各ノードのスケジュール優先度に対応する個別の埋め込みが生成されます。これらの埋め込みは遺伝的アルゴリズム BRKGA に入力され、各ノードでのデバイスの配置とスケジュールを決定します。モデルをトレーニングすることで、最適化された TensorFlow グラフの実際の計算コストが得られます。

GNN の他の興味深い応用としては、Shi らによる分子生成、Jiang らによるゲームプレイ、Chen らによる対話システムなどがあります。

3. ナレッジグラフの人気が高まっている

今年は知識グラフ推論に関する論文がかなりたくさんあります。本質的に、ナレッジグラフは事実を表現する構造化された方法です。一般的なグラフとは異なり、ナレッジ グラフでは、ノードとエッジには実際に、俳優の名前や映画の俳優など、何らかの意味があります (下の図を参照)。ナレッジ グラフに関する一般的な質問は、「2000 年以前にスティーブン スピルバーグのどの映画がオスカーを受賞しましたか?」などの複雑な質問に答えることです。これは、論理クエリ {Win(Oscar, V)∧Directed(Spielberg, V)∧ProducedBefore(2000, V)}} に変換できます。

Ren らによる論文「Query2box: Box Embeddings を使用したベクトル空間での知識グラフの推論」このアプローチでは、新しい長方形のボックス構造があるため、自然な交差演算、つまり ∧ 結合を実行できます。ただし、結合、つまり分離を作成することは、重複しない領域が生じる可能性があるため、それほど簡単ではありません。さらに、埋め込みを使用してクエリを正確にモデル化するには、VC 次元で測定された埋め込み間の距離関数の複雑さが、グラフ内のエンティティの数に比例する必要があります。代わりに、選言クエリを DNF 形式に置き換える便利なトリックがあります。この形式では、結合は計算グラフの最後でのみ発生し、各サブクエリの単純な距離計算に実質的に削減されます。

同じテーマで、Wangらは数値エンティティとルールを使用する論文「ナレッジグラフにおける数値ルールの微分可能学習」*を提案しました。 *たとえば、ナレッジ グラフ内の引用については、 influences(Y,X) ← colleagueOf(Z,Y) ∧ supervisorOf(Z,X)∧ hasCitation>(Y,Z) というルールを設定できます。つまり、学生 X は同じ指導者 Z のクラスメート Y の影響を受けており、この Z にはより多くの引用があります。ルールの右側にある各関係は行列として表すことができ、欠落しているリンクを見つけるプロセスは、関係とエンティティ ベクトルの連続的な行列乗算として表すことができます。このプロセスはルール学習と呼ばれます。行列の構築方法により、ニューラルメソッドはcolleagueOf(Z,Y)などのカテゴリルールでのみ機能します。著者らの貢献は、hasCitation>(Y,Z) や否定演算子などの数値ルールを効率的に処理する新しい方法であり、実際にはそのような行列を明示的に実現する必要がないことを示しており、これにより実行時間が大幅に短縮されます。

機械学習、そして今年の GML におけるもう一つの繰り返しテーマは、既存のモデルの再評価と、公平な設定でのそれらのパフォーマンスです。 Ruffinelli らによるこの論文「You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings」が示すように、新しいモデルのパフォーマンスは、損失関数の形式、正規化子、サンプリング スキームなど、実験トレーニングの「細かい」詳細に左右されることがよくあります。大規模なアブレーション研究において、著者らは、RESCAL モデルなどの古い方法では、ハイパーパラメータを適切に調整するだけで SOTA パフォーマンスを達成できることを観察しました。

この分野には他にも興味深い記事がたくさんあります。 Allen らは、モデルが Wikipedia グラフ上で特定のクエリに答える推論パスをどのように取得できるかを示しました。 Tabacof 氏と Costabello 氏は、グラフ埋め込みモデルの確率的キャリブレーションという重要なトピックについて触れました。彼らは、シグモイド関数を使用して対数を変換し確率を取得する、現在人気の埋め込みモデルである TransE と ComplEx はどちらも調整が不十分であり、つまり事実の存在を過小予測または過剰予測していると指摘しました。彼らの方法は、負のサンプルとして不良なトリプレットを生成することに依存していますが、プラットスケーリングや等方回帰などの既知の方法では、これらの負のサンプルを使用して確率を調整します。

4. グラフ埋め込みのための新しいフレームワーク

グラフ埋め込みはグラフ機械学習における長年のトピックであり、今年はグラフ表現をどのように学習すべきかについていくつかの新しい視点がありました。

Deng らによる「GraphZoom: 正確でスケーラブルなグラフ埋め込みのためのマルチレベルスペクトルアプローチ」の基本的な考え方は、まず元のグラフを小さなグラフに簡略化して、ノード埋め込みをすばやく計算できるようにし、次に元のグラフの埋め込みを復元するというものです。まず、元のグラフは、属性の類似性に基づいて追加のエッジで拡張されます。これは、ノードの k 近傍間のリンクに対応します。次に、ローカルスペクトル法を使用して各ノードを低次元空間に投影し、クラスターにクラスタリングすることでグラフを粗くします。ディープステッピングやディープグラフ情報マイニングなどの任意の教師なしグラフ埋め込み方法では、小さなグラフ上のノード埋め込みを取得できます。最後のステップでは、結果のノード埋め込み（基本的にはクラスターの埋め込みを表す）が、スムージング演算子を使用して反復的にブロードキャストされ、異なるノードが同じ埋め込みを持つことを防ぎます。実験では、GraphZoom フレームワークは、node2vec および DeepWalk メソッドに比べて驚異的な 40 倍の高速化と 10% 高い精度を達成しました。

グラフ分類問題の研究成果については詳細な分析を行った論文が数多くあります。 Errica らによる「グラフ分類のためのグラフ ニューラル ネットワークの公平な比較」は、この問題に関する GNN モデルの公平な再評価です。この記事では、グラフのトポロジを利用せず (ユーザー ノードの機能を集約)、SOTA GNN に匹敵するパフォーマンスを発揮するシンプルなベースラインが示されています。この驚くべき現象は、2015年以前にOrlovaらによって発表されていたようですが、多くの読者を獲得しませんでした。この作業の素晴らしい成果は、PyTorch-Geometric の一般的なデータセットとコード ベンチマークで公正な SOTA を達成したことです。私たちの研究「グラフ データ セットにおける同型性バイアスの理解」では、MUTAG や IMDB などの一般的なデータセットでは、ノードの属性を考慮しても多くのグラフに同型コピーがあることがわかりました。さらに、これらの同型グラフにはさまざまなターゲット ラベルが存在するため、当然、分類器にラベル ノイズが発生します。これは、モデルのパフォーマンスを向上させるために、利用可能なすべてのネットワーク メタ情報 (ノード属性やエッジ属性など) を使用することの重要性を示しています。別の研究「強力なグラフ ニューラル ネットは必要か? グラフ分類の分析」では、Chen らは、非線形近傍集約関数を、近傍の次数とグラフ プロパティの伝播を含む線形部分に置き換えても、モデルのパフォーマンスが低下しないことを示しています。これは、多くのグラフ データセットは分類にとって簡単ではないという以前の説明と一致しており、このタスクに適した検証フレームワークの問題を提起しています。

要約する

優れたカンファレンスへの投稿率が増加していることから、2020 年には GML 分野で多くの興味深い結果が期待できます。この分野では、グラフ上のディープラーニングのヒューリスティックな応用から、より合理的なアプローチやグラフィカル モデルの範囲に関する基本的な疑問へと移行が見られました。 GNN はグラフで表現できる多くの実用的な問題を解決する上で役立ちますが、一般的には、GML はグラフ理論と機械学習の交差点の表面をかすめただけであり、今後の結果に注目し続けるべきであると思います。