2021 年にグラフ機械学習にはどのような新たなブレークスルーがあるでしょうか?マギル大学のポスドク研究員が分野の動向を整理

[[443041]]

今年ももうすぐ終わり、あと3日で2021年も終わりです。

さまざまなAI分野でも、毎年の総括や今後の展望が発表されるようになりましたが、今日はAI界隈でずっと人気のグラフ機械学習（Graph ML）についてお話しします。

2021 年、グラフ機械学習の分野では、数千の論文、多数の学術会議やワークショップが登場し、いくつかの大きな進歩が見られました。 2022年、グラフ機械学習の分野は何に重点を置くのでしょうか?

Mila 氏と、知識グラフとグラフニューラルネットワーク (GNN) を専門とするマギル大学の博士研究員 Michael Galkin 氏は、ブログ投稿で自身の見解を詳しく説明しました。この記事では、著者らがグラフ機械学習の構造化分析を実施し、この分野における主要な進歩と注目のトレンドに焦点を当てています。著者は、この記事がグラフ機械学習分野の研究者にとって良い参考資料となることを願っています。

この画像は ruDALL-E によって生成されました。

著者は主に以下の12の部分を詳細に整理しました。

グラフトランスフォーマー + 位置特徴
等変GNN
分子の生成モデリング
GNN + 組み合わせ最適化とアルゴリズム
サブグラフ GNN: 1-WL を超えて
スケーラブルで深層な GNN: 100 層以上
ナレッジグラフ
GNNでクールな研究をする
新しいデータセット、課題、タスク
コースと書籍
ライブラリとオープンソース
最新情報を入手する方法

グラフトランスフォーマー + 位置特徴

GNN は (通常はスパースな) グラフ上で動作しますが、グラフトランスフォーマー (GT) は、すべてのノードがグラフ内の他のすべてのノードに接続されている完全接続グラフ上で動作します。一方、N 個のノードを持つグラフでは、グラフの複雑さは O(N^2) です。一方、GT は、長距離メッセージングでよくある問題である、過度にスムーズではありません。完全に接続されたグラフとは、元のグラフからの実際のエッジと、完全に接続された変換から追加された偽のエッジがあり、それらを区別する必要があることを意味します。さらに重要なのは、ノードにいくつかの位置特徴を挿入する方法が必要であることです。そうしないと、GT は GNN を上回るパフォーマンスを発揮しません。

今年最も人気のある 2 つのグラフトランスフォーマーモデルは、SAN と Graphomer です。 Kreuzer、Beainiらが提案したSANは、ラプラシアン演算子の上位k個の固有値と固有ベクトルを使用します。 SAN はスペクトル特徴と入力ノード特徴を連結し、多くの分子タスクでスパース GNN よりも優れたパフォーマンスを発揮します。

Yingらが提案したGraphormerは空間特徴を使用します。まず、ノード機能によって中央エンコーディングが強化されます。次に、アテンションメカニズムには、ノード i とノード j 間の最短パス距離と、利用可能な最短パスに依存するエッジ機能エンコーディングという 2 つのバイアス項があります。

Graphomer が 2021 Graph ML グランドスラムを達成: OGB ラージチャレンジと Open Catalyst チャレンジで優勝

同変GNN

ジェフリー・ヒントンがこれほど高く評価した同値性のユニークな点は何でしょうか?

一般に、同値性はいくつかの変換群にわたって定義されます。たとえば、3D 回転は SO(3) 群を形成し、特殊直交は 3D で結合します。等変モデルは 2021 年に ML に旋風を巻き起こし、特にグラフ機械学習の多くの分子タスクにおいて画期的なものでした。分子に適用する場合、等価 GNN には追加のノード機能入力、つまり n 次元空間で回転/反射/変換される分子の物理座標の表現が必要です。

等変モデルでは、変換の順序にかかわらず、同じ最終状態に到達します。画像提供: Satorras、Hoogeboom、Welling

Satorras、Hoogeboom、Wellingは、メッセージの受け渡しと更新のステップに物理座標を追加する点で通常のGNNと異なる、E(n)等価GNNであるEGNNを提案しました。式3はメッセージmに相対距離の二乗を加算し、式4は位置特徴を更新します。 EGNN は、n 体系のモデリング、オートエンコーダーとして、また量子化学タスク (QM9 データセット) において素晴らしい結果を示しています。

通常の GNN との主な違い: 式 3 と 4 は、メッセージの受け渡しと更新の手順に物理座標を追加します。画像提供: Satorras、Hoogeboom、Welling

もう 1 つのオプションは、Klicpera、Becker、Günnemann が GemNet で行ったように、原子間の角度をマージすることです。これには、入力グラフをエッジグラフなどの線グラフに変換する必要がある場合があります。この場合、元のグラフのエッジは線グラフのノードになります。このようにして、角度を新しいグラフのエッジ機能として使用できます。

GemNet は、COLL、MD17、Open Catalyst20 などの分子動力学タスクで優れた結果を達成しました。明らかに、等変 GNN はまだ始まったばかりであり、2022 年にはさらに進歩が見られるでしょう。

分子の生成モデリング

2021 年、幾何学的ディープラーニングのおかげで、創薬分野全体が大きな飛躍を遂げました。創薬における多くの重要な課題の 1 つは、望ましい特性を持つ分子を生成することです (図)。この分野は広大であり、ここではモデルの 3 つの分野についてのみ説明します。

正規化されたフロー

Satorras、Hoogeboomらは、上記の等変フレームワークを適用して、位置と特徴を持つ3D分子を生成できるE(n)等変正規化フローを作成しました。

Shi、Luo らは、2D グラフィックが与えられた場合に 3D コンフォーマー (つまり、3D 構造) を生成する問題を研究しました。 ConfGF モデルは、原子座標の対数密度の勾配場を推定します。これらのフィールドは回転と平行移動に関して同変であり、著者らはこの同変特性を推定器に組み込む方法を考え出しました。コンフォーマーサンプリング自体は、アニールされたランジュバンキネティックサンプリングによって行われます。

RL メソッド

これらの方法は、「ビルディングブロック」を徐々に取り付けることで分子を生成する方法として、非常に非科学的な方法で説明されています。これらの方法は、建設プロセスをどのように規制するかに基づいて大まかに分類できます。

たとえば、ガオ、メルカド、コリーは、合成可能性、つまり分子が実際に実験室で作成できるかどうかに基づいて構築プロセスを条件付けています。これを実現するために、彼らはまず、構成要素の合成ツリー（一種のテンプレート）を作成する方法を学びました。

より一般的なフレームワークは、Mila と、Generative Flow Networks (GFlowNets) を導入した Yoshua Bengio 率いるスタンフォードチームによって提案されました。これを数文で要約するのは難しいです。まず、GFlowNet は、さまざまな候補をサンプリングしたい場合のアクティブラーニングケースに使用でき、サンプリング確率は報酬関数に比例します。さらに、チームの最近の NeurIPS’21 論文では、分子生成タスクにおける GFlowNet の有用性が実証されました。 Emmanuel Bengio のブログ投稿では、フレームワークについてより詳しく説明し、より多くの実験的証拠を提供しています: http://folinoid.com/w/gflownet/

GNN + 組み合わせ最適化とアルゴリズム

2021年は、この新興分野にとって大きな年になりそうです。

Xu らは ICLR'21 論文でニューラルネットワークの外挿を研究し、いくつかの印象的な結論に達しました。アルゴリズムのアライメントの概念に基づいて、著者らは GNN と動的プログラミング (DP) を適切にアライメントできることを示しています (下の図を参照)。実際、最短経路を見つけるための古典的なベルマンフォードアルゴリズムの反復と、GNN による情報の集約および組み合わせの手順を比較すると、多くの類似点が見つかります。

さらに、著者らは、特定の DP アルゴリズムをモデル化する場合、GNN に適切な集約関数を選択することが重要であることを示しています。たとえば、Bellman-Ford の場合、最小集約関数が必要です。著者のステファニー・イェゲルカは、2021年のディープラーニングと組み合わせ最適化ワークショップで、この研究の主な結果について詳細なプレゼンテーションを行いました: https://www.youtube.com/watch?v=N67CAjI3Axw

この分野をより包括的に紹介するためには、GNN における組み合わせ最適化を扱った、IJCAI'21 での Cappart らによる研究も取り上げる必要があります。この論文は、ニューラルアルゴリズム推論の最初の青写真を提示しました。これは後に、Veličković と Blundell による Patterns のポジションペーパーで説明されました。

このブループリントでは、ニューラルネットワークが埋め込み空間で一般的な離散アルゴリズムの実行を模倣し、強化する方法を説明します。エンコード、処理、デコードのアプローチでは、抽象的な入力（自然な入力から取得）がニューラルネットワーク（プロセッサ）によって処理され、その出力が抽象的な出力にデコードされ、その後、より自然なタスク固有の出力にマッピングされます。

たとえば、抽象的な入力と出力をグラフとして表現できる場合、GNN はプロセッサのネットワークになります。離散アルゴリズムの一般的な前処理手順は、問題についてわかっていることすべてを「距離」や「エッジ容量」などのスカラー量に変換し、そのスカラー量に対してアルゴリズムを実行することです。対照的に、ベクトル表現とニューラル実行では、プロセッサの最適化のためのバックプロパゲーションを追加することで、単純なスカラーではなく高次元の入力を簡単に有効にすることができます。

現在、このブループリントはどんどん採用され、NeurIPS'21 ではいくつかの素晴らしい作品が登場しました。 Xhonneux らは、転移学習を使用して学習したニューラルアクチュエータを新しいタスクに一般化できるかどうかを調査しました。Deac らは、強化学習におけるアルゴリズム推論と暗黙の計画の関係を発見しました。 2022年にはさらに関連性の高い研究が行われると信じています。

サブグラフ GNN: 1-WL を超えて

2020 年が GNN 表現力の 1-WL-landia から抜け出す最初の試みの年であったとすれば、2021 年は 1WL-landia を超える年となります。これらの接続は有用であることが証明されており、現在では、メッセージパッシングを単体複合体 (例: Bodnar、Frasca、Wang らによる MPSN ネットワーク、セルラー複合体 (Bodnar、Frasca らによる CW ネットワーク)) やサブグラフなどの高次構造に拡張する、強力で表現力豊かな GNN アーキテクチャがいくつか存在します。

スケーラビリティとディープGNN

2〜4 層の GNN を使用するときに、100 層を超えるディープ ResNet または大規模な Transformer を羨ましがるなら、2021 年に発表された 2 つの論文が朗報をもたらしました。1 つは 100〜1000 層の GNN を自由にトレーニングすることに関するもので、もう 1 つはほぼ一定のサイズでの近傍サンプリングに関するものです。

Liらは、非常に深いハイパーパラメータ化されたネットワークをトレーニングする際のGPUメモリ消費を削減するための2つの新しいメカニズムを提案しました。L層ネットワークの場合、O(L)をO(1)に削減します。著者らは、CV の可逆レイヤーまたは効率的な Transformer アーキテクチャ (Reformer など) を使用し、レイヤー間で重みを共有 (重みバンドル) して、最大 1000 レイヤーの GNN をトレーニングする方法を示しています。次の図は、GPU の需要に基づいたレイヤー数のスケーリングを示しています。

画像出典: Li らの論文「1000 層グラフニューラルネットワークのトレーニング」

Godwin らは、ループを使用して深層 GNN を学習する方法を提案しました。これは、メッセージパッシングステップをブロックに編成し、各ブロックに M 個のメッセージパッシングレイヤーを配置する方法です。次に、N 個のブロックがループ内に適用されます。つまり、複数のブロックが重みを共有することになります。メッセージパッシングレイヤーが 10 個、ブロックが 10 個ある場合、100 レイヤーの GNN が得られます。重要なコンポーネントの 1 つは、ノードとエッジの特徴を乱し、追加のノイズ除去損失を計算する、Noisy Nodes 正規化手法です。このアーキテクチャは分子タスクに適しており、研究チームは QM9 および OpenCatalyst20 データセットでも評価しました。

最後に、GNN を非常に大きなグラフに拡張したい場合、選択肢は 1 つだけ、つまりサブグラフをサンプリングすることです。通常、k ホップサブグラフをサンプリングすると、メモリコストと計算グラフサイズが指数関数的に増加します。

PyG の著者である Matthias Fey らは、履歴埋め込みとグラフクラスタリングを使用して一定時間で GNN をスケーリングするためのフレームワーク GNNAutoScale を作成しました。このアプローチでは、前処理中にグラフを B 個のクラスター (ミニバッチ) に分割して、クラスター間の接続を最小限に抑えます。その後、これらのクラスターでメッセージパッシングが実行され、フルバッチ設定と同様にパフォーマンスが向上し、メモリ要件が大幅に削減されます (約 50 倍小さい)。これにより、ディープ GNN と大規模なグラフを汎用 GPU に適合させることができます。

ナレッジグラフ (KG)

2021 年以前は、モデルは、帰納的バイアス、アーキテクチャ、トレーニングメカニズムに基づいて、トランスダクティブモデルとインダクティブモデルに明示的に分類されていました。言い換えれば、トランスダクティブモデルは目に見えないエンティティに適応する機会がなく、一方、インダクティブモデルは中規模から大規模のグラフでトレーニングするにはコストがかかりすぎます。 2021 年には、トランスダクティブ設定とインダクティブ設定の両方で使用できる 2 つの新しいアーキテクチャが利用可能になります。どちらのアーキテクチャもノード機能を必要とせず、トランスダクティブモードと同じようにインダクティブモードでトレーニングでき、実際の KG サイズに拡張できます。

1 つは、Zhu らによる Neural Bellman-Ford Network です。これは、古典的な Bellman-Ford を高レベルのフレームワークに一般化し、特定の演算子を使用してフレームワークをインスタンス化することで、他の古典的な方法 (Katz インジケーター、PPR、最大パスなど) を取得する方法を示しています。さらに重要なことは、この研究は、一般化されたベルマン・フォードが本質的にリレーショナル GNN アーキテクチャであることを示しています。 NBFNet はエンティティの埋め込みを学習しないため、モデルを未知のグラフに一般化できます。このモデルは、リレーショナルグラフと非リレーショナルグラフの両方でリンク予測タスクに優れたパフォーマンスを発揮します。 KG の適用において、NBFNet は 2019 年以降、FB15k-237 および WN18RR データセットに最大のパフォーマンス向上をもたらし、パラメータを 100 分の 1 に削減しました。

もう 1 つは、NLP のトークン化アルゴリズムにヒントを得た Galkin らによる新しい方法です。 KG に適用されると、NodePiece は各ノードを、上位 k 個の最も近いアンカーノードと、ノードの周囲の m 個の一意の関係タイプのセットとして表します。アンカーと関係タイプは、あらゆる下流タスク (分類、リンク予測、関係予測など) およびあらゆる帰納的/変換的設定で使用できるノード表現としてエンコードされます。 NodePiece 機能は、RotatE などの非パラメトリックデコーダーで直接使用したり、メッセージパッシングのために GNN に送信したりできます。このモデルは、帰納的リンク予測データセットで NBFNet と同等のパフォーマンスを実現し、大規模なグラフで高いパラメータ効率を示します。OGB WikiKG 2 の NodePiece モデルでは、浅いトランスダクションのみのモデルの 100 分の 1 のパラメータしか必要ありません。

GNNを使ってクールな研究をする

Huang、He らは ICLR'21 で、ラベル伝播を介してモデル予測を改善するためのシンプルな手順である Correct & Smooth を発表しました。この方法は、MLP のみと組み合わせることで、GNN を使用せず、はるかに少ないパラメータで最高スコアを達成し、OGB リーダーボードに登場します。現在、OGB ノード分類トラックのほぼすべてのトップモデルは、Correct & Smooth を使用して、より多くのポイントを圧縮します。

画像出典: Huang, He et al.

Knyazev らによる、フォワードパスにおけるさまざまなニューラルネットワークアーキテクチャのパラメータを予測する研究は、ML コミュニティに衝撃を与えました。モデルをランダムに初期化する代わりに、予測されたパラメータを使用しましたが、ランダムモデルよりも優れたパフォーマンスを発揮しました。

パラメータ予測は、実際にはグラフ学習タスクです。任意のニューラルネットワークアーキテクチャ (ResNet、ViT、Transformers) は、ノードが学習可能なパラメータを持つモジュール、ノード機能がそれらのパラメータ、ネットワークが多数のノードタイプ (線形層、畳み込み層など、著者は約 15 種類のノードタイプを使用) を持つ計算グラフとして表すことができます。パラメータ予測はノード回帰タスクです。計算グラフは GatedGNN を使用してエンコードされ、その新しい表現がデコーダーモジュールに送信されます。トレーニングのために、著者らは 100 万のアーキテクチャ (グラフ) を含む新しいデータセットを収集しました。このアプローチは、他の GNN を含むあらゆるニューラルネットワークアーキテクチャに適用できます。

未知のモデルのパラメータを予測するためのパイプライン。画像クレジット: Knyazev 他

DeepMind と Google は、道路ネットワークをスーパーセグメント化されたグラフとしてモデル化し、それに GNN を適用することで、Google マップの ETA の品質を大幅に向上させました。 Pinion らでは、タスクはノードレベルおよびグラフレベルの回帰として定義されています。とりわけ、著者らは、Google マップの規模でシステムを展開するために対処する必要がある多くの技術的課題について説明しています。 GNN を適用して、何百万ものユーザーが直面している現実の問題を解決します。

論文アドレス: https://arxiv.org/pdf/2108.11482.pdf

画像出典: Pinion et al.

いくつかの情報の概要

記事の最後で、著者はデータセット、コースや書籍、いくつかの実用的なライブラリなど、いくつかの関連資料を紹介しています。

Cora、Citeseer、Pubmed データセットの使用に慣れていない場合は、以下を検討してください。

OGB データセットには、ノード分類 (2 億 4,000 万ノード)、リンク予測 (Wikidata 全体、9,000 万ノード)、グラフ回帰 (400 万分子) タスク用の 3 つの非常に大きなグラフが含まれています。 KDD カップでは、優勝チームのほとんどが 10 ～ 20 個のモデルを組み合わせて使用しました。
Meta AI が開始した Open Catalyst NeurIPS'21 チャレンジでは、原子の位置を含む初期構造が与えられた場合に、その緩和状態のエネルギーを予測するという大規模な分子タスクが提供されます。このデータセットは膨大で計算負荷が高いが、主催者は GPU 予算が限られている小規模な研究室にとって使いやすい小型バージョンをリリースすることを示唆した。実際、Graphomer は OGB LSC と OpenCatalyst ’21 の両方で 1 位を獲得し、2021 年に Graph ML のグランドスラムを達成しました。
GLB 2021 では、Lim らが提案した非同質グラフ、Tsitsulin らが提案したグラフシミュレーション、Rozemberczki らが提案した時空間グラフなど、一連の新しいデータセットが導入されています。
NeurIPS'21 データおよびベンチマークトラックでは、新しいデータセットが導入されます。グラフ分類用の MalNet (平均グラフサイズは 15,000 ノード、35,000 エッジ)、3D 分子タスク用の ATOM3D、放射線レポートから情報を抽出するための RadGraph です。

Michael Bronstein、Joan Bruna、Taco Cohen、Petar Veličković による幾何学的深層学習に関するプロトタイプの書籍とコース。12 の講義と実践的なチュートリアルとワークショップが含まれています。