2020年に注目を集めるグラフ機械学習の研究動向とは？

[[314165]]

この記事はLeiphone.comから転載したものです。転載する場合は、Leiphone.com公式サイトにアクセスして許可を申請してください。

2019年は間違いなくグラフ機械学習（GML）が非常に人気になる年です。あらゆる学会においてグラフニューラルネットワークの会場は常に満員です。

2019年にグラフ機械学習の研究が急激に人気になった理由は、ディープラーニングがこれまでユークリッド空間のデータで大きな成功を収めてきたものの、多くの実用的な応用シナリオのデータは非ユークリッド空間から生成されることが多いためです。

Alibaba Damo Academyは2019年に次のように述べています。「純粋なディープラーニングは成熟しており、ディープラーニングと組み合わせたグラフ研究は、エンドツーエンドの学習と帰納的推論を組み合わせ、ディープラーニングでは処理できない関係推論や説明可能性などの一連の問題を解決することが期待されています。」

過去 1 年間、グラフ 機械学習は活発な発展を遂げており、主要なトップ カンファレンスでのグラフ 機械学習の人気からもそれがわかります。

新年に入って1か月が経ちましたが、グラフ機械学習の人気は2020年も続くのでしょうか?どのような新しい研究動向が生まれるのでしょうか? 4月にエチオピアで開催されるICLR2020は、こうした問題をよく反映した会議となるでしょう。

このカンファレンスは、ディープラーニングの三大巨頭のうちの2人、Yoshua Bengio氏とYann LeCun氏によって設立され、ディープラーニングのあらゆる側面における最先端の研究に焦点を当てることを目的としています。

ICLR 2020では、グラフ機械学習に関連する投稿が150件あり、そのうち約3分の1が採択されました。これもグラフ機械学習が依然として人気があることを示しています。

2020 年のグラフ機械学習の研究動向を把握するために、これらの論文を理論、アプリケーション、ナレッジグラフ、グラフ埋め込みに分けてみるのもよいでしょう。

注：記事に記載されている論文については、Leifeng.comのWeChatパブリックアカウント「AI Technology Review」をフォローし、バックグラウンドで「2020 GML Trends」と返信するとダウンロードできます。

1. GNNの理論的知識がより強固になる

現状から判断すると、グラフ機械学習の分野は成熟への道をどんどん進んでいますが、グラフニューラルネットワークにはまだ改善の余地がたくさんあります。グラフ ニューラル ネットワークは過去 1 年間にわたって継続的に改良され、多くの理論的研究が行われてきました。2020 年の予測を行う前に、まずグラフ ニューラル ネットワークの重要な理論的成果を簡単に確認してみましょう。

グラフニューラルネットワークが学習できないもの: 深さと幅

https://openreview.net/forum?id=B1l2bp4YwS

スイス連邦工科大学ローザンヌ校のアンドレアス・ルーカスによるこの論文は、その影響力、簡潔さ、理論的理解の深さの点で、間違いなく模範的な論文です。

これは、GNN を使用して一般的なグラフの問題を計算する場合、ノード埋め込みの次元 (ネットワークの幅、w) とレイヤーの数 (ネットワークの深さ、d) の積がグラフのサイズ n に比例するはずであることを示しています。つまり、dW = O(n) です。

しかし、現実には、現在の GNN の実装の多くは、グラフのサイズに比べて層の数と埋め込みのサイズが十分に大きくないため、この条件を満たすことができません。一方、大規模なネットワークは実際には適していないため、効果的な GNN をどのように設計するかという疑問が生じ、これは研究者の今後の研究の焦点でもあります。この論文は 1980 年代の分散コンピューティング モデルからもインスピレーションを得ており、GNN が本質的に同じことを行っていることを示していることにも注目すべきです。

この記事には貴重な結論も多数含まれているため、原文を読むことを強くお勧めします。 Leiphone.comのWeChat公開アカウント（公開アカウント：Leiphone.com）「AI Technology Review」をフォローし、「2020 GML Trends」と返信すると、論文をダウンロードできます。

同様に、他の 2 つの論文では、Oono らが GNN の機能を研究しました。最初の記事は「グラフ ニューラル ネットワークはノード分類で表現力を失う」、2 番目の記事は「グラフ ニューラル ネットワークの論理表現」です。

グラフニューラルネットワークはノード分類の表現力が指数関数的に低下

https://openreview.net/forum?id=S1ldO2EFPR 翻訳元

この論文では、「特定の条件付き重みが与えられた場合、レイヤーの数が増えると、GCN はノード次数と接続コンポーネント以外のものを学習できない」ことを示しています。この結果は、「マルコフ過程は一意の平衡点に収束する」という特性を拡張し、収束率が転送行列の固有値によって決定されることを示しています。

グラフニューラルネットワークの論理的表現力

https://openreview.net/pdf?id=r1lZ7AEKvB

この論文では、GNN とノード分類器タイプの関係を示します。これまで、GNN は WL 同型性テストと同じくらい強力であることを確認しました。しかし、GNN は他の分類機能も取得できるのでしょうか?直感的には、これは不可能です。なぜなら、GNN はメッセージ パッシング メカニズムであり、グラフの一部と別の部分の間にリンクがない場合、2 つの部分の間でメッセージを渡すことができないからです。

したがって、この論文では、近傍集約の後に読み出し操作を追加して、すべての機能を更新するときに各ノードがグラフ内の他のすべてのノードと接続されるようにするという単純な解決策を提案しています。

他にも、グラフ情報を使用して GNN を測定する Hou らの研究など、多くの理論的研究があります。また、Srinivasan と Ribeiro によって提案された役割ベースのノード埋め込みと距離ベースのノード埋め込みの同等性についての議論。

論文のリンクは次のとおりです。

グラフニューラルネットワークにおけるグラフ情報の利用の測定と改善

https://openreview.net/forum?id=rkeIIkHKvS

位置ノード埋め込みと構造グラフ表現の同値性についてhttps://openreview.net/forum?id=SJxzFySKwH

2. 新しいクールなアプリケーションが続々と登場

過去 1 年間で、GNN はいくつかの実用的なタスクに適用されてきました。たとえば、ゲームのプレイ、IQ テストの回答、TensorFlow 計算グラフの最適化、分子生成、対話システムでの質問生成に適用されたプログラムがあります。

HOPPITY: グラフ変換を学習してプログラムのバグを検出し修正する

https://openreview.net/pdf?id=SJeqs6EFvB

この論文では、著者らは JavaScript コードのエラーを同時に検出して修正する方法を提案しました。具体的な操作は、コードを抽象構文木に変換し、GNN に前処理を実行させてコード埋め込みを取得し、複数回のグラフ編集演算子 (ノードの追加または削除、ノードの値またはタイプの置き換え) を通じて変更することです。グラフのどのノードを修正する必要があるかを理解するために、著者らは、グラフ埋め込みを採用し、LSTM ネットワークを使用して修復するノードを選択するポインター ネットワークを使用しました。もちろん、LSTM ネットワークはグラフの埋め込みやコンテキスト編集も受け入れます。

LambdaNet: グラフニューラルネットワークを使用した確率的型推論

https://openreview.net/pdf?id=Hkx6hANtwH

同様のアプリケーションは上記の論文にも反映されています。テキサス大学オースティン校の著者らは、Python や TypeScript などの言語で変数の型を推論する方法を調査しました。具体的には、著者らは、プログラム変数をノードとして含み、それらの間の関係（論理関係、コンテキスト制約など）を示す型依存性ハイパーグラフを提示し、次に、GNN モデルをトレーニングしてグラフと可能な型変数の埋め込みを生成し、尤度に基づいて予測を行います。

多重グラフネットワークによる抽象図式推論

https://openreview.net/pdf?id=ByxQB1BKwH

IQ テストの応用では、上記の論文では、GNN が Raven のテスト (RPM) や図式三段論法 (DS) などの IQ テストを実行する方法を示しています。具体的には、RPM タスクでは、行列の各行がグラフを形成し、フィードフォワード モデルを通じてエッジ埋め込みが取得され、その後グラフが要約されます。最後の行には 8 つの回答の可能性があるので、8 つの異なるグラフが作成され、各グラフが最初の 2 行と連結され、ResNet モデルを通じて IQ スコアが予測されます。次の図に示すように:

出典: https://openreview.net/pdf?id=ByxQB1BKwH

計算グラフを最適化するための強化遺伝的アルゴリズム学習

https://openreview.net/pdf?id=rkxDoJBYPBDeepMind

上記の論文では、TensorFlow 計算グラフのオーバーヘッドを最適化するための RL アルゴリズムが提案されています。グラフは最初に標準の GNN によって処理され、次にグラフ内の各ノードのスケジュール優先度に対応する離散化された埋め込みが生成されます。最後に、埋め込みはモデル トレーニング用の遺伝的アルゴリズム BRKGA に送られ、結果として得られる TensorFlow グラフの実際の計算オーバーヘッドが最適化されます。遺伝的アルゴリズムによって各ノードのレイアウトとスケジュールが決定されることは注目に値します。

同様の優れたアプリケーションとしては、Chence Shi による分子構造生成、Jiechuan Jiang によるゲームプレイ、Yu Chen によるゲームプレイなどがあります。

論文のリンクは次のとおりです: グラフ畳み込み強化学習

https://openreview.net/forum?id=HkxdQkSYDB

自然な質問生成のための強化学習ベースのグラフ-シーケンスモデル

https://openreview.net/forum?id=HygnDhEtvr

3. ナレッジグラフはより普及する

今年の ICLR カンファレンスでは、知識グラフ推論に関する論文が数多く発表されました。

ナレッジグラフの例 (出典: https://arxiv.org/abs/1503.00759)

本質的に、ナレッジグラフは事実を表現する構造化された方法です。一般的なグラフとは異なり、ナレッジグラフのノードとエッジには、俳優の名前や映画のタイトルなど、実際に特定の意味があります。ナレッジ グラフの一般的な問題は、「2000 年以前にアカデミー賞を受賞したスピルバーグの映画はどれですか?」などの複雑な質問にどのように答えるかということです。この質問は、次のように論理クエリ言語に変換されます。
∨ {Win(オスカー、V) ∧ Directed(スピルバーグ、V) ∧ ProducedBefore(2000、V) } Query2box:

ボックス埋め込みを使用したベクトル空間での知識グラフの推論

https://openreview.net/forum?id=BJgr4kSFDS

Query2Box 推論フレームワーク スタンフォード大学の Hongyu Ren らの研究では、クエリを単一の点 (長方形のボックス) としてではなく、潜在空間に埋め込むことが提案されました。

QUERY2BOX の 2 つの演算と距離関数の幾何学的例 このアプローチにより、交差演算 (つまり、結合 ∧) を自然に実行して、新しい長方形のボックスを取得できるようになります。ただし、結合演算（つまり、分離∨）は、重複しない領域を生成する可能性があるため、それほど単純ではありません。

さらに、埋め込みを使用してすべてのクエリを正確にモデル化するには、埋め込み間の距離関数の複雑さ (VC 次元で測定) がグラフ内のエンティティの数に比例します。

ただし、論理和 (∨) クエリを DNF 形式に変換する良い方法があります。この場合、結合演算はグラフ計算の最後にのみ実行されるため、各サブクエリの距離計算を効果的に削減できます。

ナレッジグラフにおける数値ルールの微分学習

https://openreview.net/forum?id=rJleKgrKwSCMU の Po-Wei

同様の論文で、Wangらはデジタルエンティティとルールを処理する方法を提案しました。

Citation KG の例 たとえば、Citation KG では、次のようなルールを設定できます: influences(Y,X) ← colleagueOf(Z,Y) ∧ supervisorOf(Z,X)∧ hasCitation>(Y,Z) これは、学生 X が指導者 Z の同僚 Y の影響を受けている典型的なケースです (Y の引用率は高くなります)。

このルールの右側にある各関係は行列として表すことができ、欠落しているリンクを見つけるプロセスは、関係とエンティティ ベクトルの連続行列積として表すことができます。このプロセスは、ルール学習と呼ばれます。行列の構築方法により、ニューラル ネットワーク アプローチは分類ルール colleagueOf(Z,Y) でのみ機能します。

著者らの貢献は、斬新なアプローチを通じて、実際にはこれらの行列を明示的に表現する必要がないことを実証し、それによってhasCitation>(Y,Z)や否定などの数値ルールを効率的に処理し、実行時間を大幅に短縮できることです。

老犬にも新しい芸を教えることは可能です!

知識グラフ埋め込みのトレーニングについてhttps://openreview.net/forum?id=BkxSmlBFvr

今年、グラフニューラルネットワーク（または機械学習）で頻繁に登場した研究の方向性は、既存のモデルの再評価と公平な環境での評価です。

上記の記事もその 1 つです。彼らの研究によると、新しいモデルのパフォーマンスは、損失関数の形式、正則化子、サンプリング スキームなど、実験トレーニングにおける「小さな」詳細に左右されることが多いことが示されています。

大規模なアブレーション研究において、著者らは、古い方法 (RESCAL モデルなど) のハイパーパラメータを適切に調整することで SOTA パフォーマンスを達成できることを観察しました。 もちろん、この分野には他にも興味深い研究がたくさんあります。Allen らは、単語埋め込みに関する最新の研究に基づいて、関係とエンティティの学習された表現の潜在空間をさらに調査しました。浅井らは、モデルがWikipediaグラフ上で特定のクエリに答える推論パスをどのように取得できるかを示しました。

Tabacof 氏と Costabello 氏は、グラフ埋め込みモデルの確率較正における重要な問題について議論しました。彼らは、現在人気の埋め込みモデルである TransE と ComplEx (ロジット関数をシグモイド関数に変換して確率を取得する) は両方とも較正が誤っており、つまり、事実の存在を過小予測または過剰予測していると指摘しました。

論文のリンクは次のとおりです: 知識グラフ表現の理解について

https://openreview.net/forum?id=SygcSlHFvS

質問応答のための Wikipedia グラフ上の推論パスの取得の学習

https://openreview.net/forum?id=SJgVHkrYDH

ナレッジグラフ埋め込みモデルの確率較正

https://openreview.net/forum?id=S1g8K1BFwS

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

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

GraphZoom: 正確でスケーラブルなグラフ埋め込みのためのマルチレベルスペクトルアプローチ

https://openreview.net/forum?id=r1lGO0EKDH

コーネル大学の Chenhui Deng らは、教師なし埋め込み法によるあらゆるノード分類問題に適用できる、実行時間と精度を向上させる方法を提案しました。 この記事の基本的な考え方は、まず元のグラフを小さなグラフに簡略化してノード埋め込みをすばやく計算できるようにし、次に元のグラフの埋め込みを復元することです。

最初に、元のグラフは、属性の類似性に基づいて追加のエッジで拡張されます。これは、ノードの k 個の最も近い隣接ノード間のリンクに対応します。 次に、ローカル スペクトル法を使用して各ノードを低次元空間に投影し、それらをクラスターにクラスタリングすることで、グラフが粗くなります。任意の教師なしグラフ埋め込み方法 (DeepWalk、Deep Graph Infomax など) を使用すると、小さなグラフ上のノード埋め込みを取得できます。 最後のステップでは、結果として得られるノード埋め込み（本質的にはクラスターの埋め込みを表す）がスムージング演算子を使用して反復的にブロードキャストされ、異なるノードが同じ埋め込みを持つことを防ぎます。 実験では、GraphZoom フレームワークは、node2vec や DeepWalk と比較して驚異的な 40 倍の高速化と 10% の精度向上を達成しました。

グラフ分類のためのグラフニューラルネットワークの公平な比較

https://openreview.net/forum?id=HygDF6NFPB

グラフ分類問題の研究成果については詳細な分析を行った論文が数多くあります。ピサ大学の Federico Errica らは、グラフ分類の問題に関して GNN モデルを再評価しました。

彼らの研究によると、グラフのトポロジを活用せず（ノード機能のみを集約する）、単純なベースラインでも SOTA GNN に匹敵するパフォーマンスを達成できることが示されています。実際、この驚くべき発見は2015年にオルロバらによって発表されましたが、広く注目されることはありませんでした。

グラフデータセットにおける同型性バイアスの理解

https://openreview.net/forum?id=rJlUhhVYvSSkolkovo

科学技術研究所の Ivanov Sergey 氏らは、MUTAG や IMDB などの一般的なデータセットでは、ノード属性を考慮しても多くのグラフに同型コピーが存在することを研究で発見しました。さらに、これらの同型グラフの多くは異なるターゲット ラベルを持ち、当然ながら分類器にラベル ノイズが導入されます。これは、モデルのパフォーマンスを向上させるには、ネットワーク内の利用可能なすべてのメタ情報 (ノードまたはエッジ属性など) を活用することが非常に重要であることを示唆しています。

強力なグラフニューラルネットは必要か？グラフ分類の分析

https://openreview.net/forum?id=BJxQxeBYwH

もう一つの研究は、UCLA の Sun Yizhou 氏のチームによる研​​究です。この研究では、元の非線形最近傍集約関数の代わりに線形最近傍集約関数を使用した場合、モデルのパフォーマンスが低下しないことを示しています。これは、「グラフ データセットは分類にほとんど影響を与えない」というこれまでの一般的な考えとは反対です。同時に、この作業では、このようなタスクに適した検証フレームワークをどのように見つけるかという問題も提起されます。