「グラフ機械学習 @ ICML 2023」

Graph Machine Learning @ ICML 2023

グラフ機械学習の最新情報は？

最新の進展と注目トレンド、2023年8月版

素晴らしいビーチと熱帯のハワイの風景🌴にもかかわらず、勇敢な科学者たちはホノルルで開催された国際機械学習会議に出席し、最新の研究成果を発表しました！私たちのお気に入りのグラフ機械学習の領域で何が新しいのか見てみましょう。

この投稿を退屈にならないようにするために、ホノルル周辺で写真を撮りました📷

目次（クリック可能）：

1. グラフトランスフォーマー：より疎で高速、かつ有向
2. 理論：GNNのVC次元、オーバースクワッシングの詳細
3. 新しいGNNアーキテクチャ：遅延とハーフホップ
4. 生成モデル：分子の安定した拡散、離散拡散
5. 幾何学的学習：幾何学的WL、クリフォード代数
6. 分子：2D-3D事前学習、MDの不確実性推定
7. 材料とタンパク質：タンパク質のためのCLIP、Ewaldメッセージパッシング、同変性拡張
8. クールな応用：アルゴリズム的推論、帰納的KG完全、質量スペクトルのためのGNNs
9. 結論の部分のミーム

グラフトランスフォーマー：より疎で高速、かつ有向

私たちは約1年前にGraphGPSを発表し、そのフレームワークに基づいてさまざまなICMLの論文が構築され、GTの機能がさらに拡張されているのを見ることは喜ばしいです。

➡️ Exphormer（Shirzad、Velingker、Venkatachalamら）は、GTにグラフを基にしたスパースなアテンションの欠落部分を追加します。BigBirdやPerformer（元々はシーケンス用に設計されたもの）ではなく、Exphormerのアテンションは1ホップエッジ、仮想ノード（グラフのすべてのノードに接続されたノード）、そしてエクスパンダーエッジの素晴らしいアイデアに基づいて構築されます。エクスパンダーグラフは定数次数を持ち、完全に接続されたグラフを近似することが示されています。これらのすべてのコンポーネントを組み合わせると、アテンションのコストはO(V+E)となり、GraphGPSをほとんどすべての場所で上回り、最大160,000ノードの非常に大きなグラフにスケールすることができます。ExphormerがGTの標準的なスパースアテンションメカニズムになる可能性は十分にあるでしょう👏。

• 「Juliaプログラミング言語の探求：MongoDB」
• 大規模言語モデルは、ビデオからの長期行動予測に役立ちますか？AntGPTをご紹介します：ビデオベースの長期行動予測タスクにおいて大規模言語モデルを組み込むためのAIフレームワークです
• 「IBM、HuggingFace、そしてNASAがWatsonx․ai Foundation Modelをオープンソース化 NASA初の公開可能なAI基盤モデルであり、HuggingFace上で最大の地理空間モデル」

➡️ グラフトランスフォーマーと同時に、エクスパンダーグラフは既に任意のMPNNアーキテクチャのパフォーマンスを向上させるために使用できることが示されています。これはDeac、Lackenby、VeličkovićによるExpander Graph Propagationで示されています。

同様に、Caiらは、仮想ノードを持つMPNNが線形のPerformerのようなアテンションを近似できることを示しています。したがって、古典的なGCNやGatedGCNに仮想ノードを組み込んだ場合でも、長距離グラフタスクでほぼSOTAのパフォーマンスを示すことができます（私たちは昨年、GNNとGTの長距離能力を測定するためにLGRBベンチマークを公開しました）。

➡️ ビジョンモデルに触発されたGTのいくつかのパッチベースのサブサンプリング手法：Heらによる「グラフへのViT/MLP-Mixerの一般化」は、入力をいくつかのパッチに分割し、各パッチをGNNでトークンにエンコードし、トランスフォーマーをそのトークンに対して実行します。

「GOAT」（江原らによる）では、ノードの特徴量がK-Meansを用いてKクラスタのコードブックに射影され、各ノードのサンプルされた3ホップ近傍がコードブックに対してアテンションを行います。GOATは1層のモデルであり、数百万のノードを持つグラフにスケーリングされます。

「Directed graphs」（Geislerらによる）もトランスフォーマーの愛を受けました。Geislerらによる「Transformers Meet Directed Graphs」では、非対称な隣接行列を持つ有向グラフのためのラプラシアンの一般化であるマグネティック・ラプラシアンが紹介されています。マグネティック・ラプラシアンの固有ベクトルは、トランスフォーマーの強力な入力特徴量となり、OGB Code2グラフ特性予測データセットで新たなSOTAを大幅に上回る結果を実現します！

さらに、「GRIT」（馬、林らによる）はコミュニティ標準のZINCデータセットで新たなSOTA GTを実現しました。GRITでは、完全なd次元ランダムウォーク行列である相対ランダムウォーク確率（RRWP）をエッジの特徴量としてアテンション計算に取り入れています（比較すると、人気のあるRWSE特徴量はこの行列の対角要素に過ぎません）。RRWPは最短経路距離特徴量よりも強力であり、ZINCで0.059のMAE（GraphGPSの0.070から改善）という記録的な低値を達成します。GRITは他のベンチマークでもしばしばGPSを上回ります。同様に、Eliasofらはランダムとスペクトル特徴量を組み合わせた位置エンコーディングのアイデアを提案し、RWSEよりも優れた結果を出していますが、GTでは試されていません。

Theory: GNNのVC次元について、オーバースクウォッシングについての詳細な調査

VC次元はモデルの容量と表現力を測る指標です。古典的な機械学習アルゴリズムについてはよく研究されていますが、驚くべきことにGNNの研究にはまだ応用されていませんでした。「WL meet VC」（Morrisらによる）では、WLテストとVC次元の関連性がついに解明されました。VC次元はGNNの重みのビット長によって制約されることがわかりました。つまり、float32の重みはVC次元32を意味します。さらに、VC次元は与えられたタスクの一意のWL色の数に対数的に依存し、深さと層の数に多項式的に依存します。これは素晴らしい理論的な結果であり、ぜひ一読することをお勧めします！

🍊🖐️ オーバースクウォッシング効果は、近隣ノードからメッセージを詰め込む際に情報の損失が発生するというMPNNの一般的な問題であり、その適切な対処方法についてはまだ完全に理解されていません。今年はこのテーマに関連する論文が3つありました。おそらく最も基礎的なものは、Di Giovanniらによる研究で、MPNNの幅、深さ、およびグラフのトポロジーがオーバースクウォッシングにどのように影響するかを説明しています。

幅が助けになる（ただし汎化の問題がある）、深さは本当に助けにならず、グラフのトポロジー（ノード間の通過時間によって特徴付けられる）が最も重要な役割を果たします。グラフの再配線戦略（空間的またはスペクトル的な特性に基づくエッジの追加と削除）によって通過時間を短縮することができます。実際、この研究のフォローアップワークでは、オーバースクウォッシングといくつかのMPNNの特性に関する不可能性の文をさらに詳しく導き出しています。ぜひ読んでみることをおすすめします！

➡️ 有効な抵抗は空間的な再配線戦略の一例であり、Blackらはそれを詳細に研究しています。Ricciフローに基づく再配線はグラフの曲率と共に機能し、Nguyenらによる研究でさらに詳しく調査されています。

➡️ サブグラフGNNはまだ注目を集めています：2つの作品（Zhang、Feng、DuなどとZhou、Wang、Zhang）は、最近提案されたサブグラフGNNの表現能力の階層とその1次および高次のWLテストとの関係を同時に導出しています。

新しいGNNアーキテクチャ：遅延とハーフホップ

GCNやGATのさらなる変種に飽きた場合、任意のGNNと組み合わせて機能するいくつかの新しいアイデアがあります：

⏳ 理論セクションで知っているように、再配線は過度の押し潰しに対抗するのに役立ちます。 Gutteridgeら は「DRew：遅延を伴う動的なリワイヤードメッセージパッシング」というものを紹介しており、後のGNNレイヤーでグラフを徐々に密にすることで、長距離のノードが以前のノードの元の状態（元のDRew）を参照するか、遅延に基づいてスキップ接続が追加されます（vDRewバージョン）。例えば（🖼️👇）、vDRew遅延メッセージパッシングでは、レイヤー0の開始ノードはレイヤー1の2ホップ近傍ノードにその状態を表示し、レイヤー2の3ホップ近傍ノードにその状態を表示します。 DRewは、バニラGNNが長距離タスクを実行する能力を大幅に向上させます。実際、DRewを有効にしたGCNは、Long Range Graph BenchmarkのPeptides-funcデータセットで現在のSOTAです。

🦘 もう1つの素晴らしいアイデアはAzabouらによるもので、特別な接続パターンを持つ各エッジに新しい遅いノードを挿入してメッセージパッシングを遅くすることです。遅いノードは異種性ベンチマークでバニラGNNの性能を大幅に改善し、同じオリジナルグラフの異なる位置に遅いノードを配置してビューを作成することで、自己教師あり学習にも遅いノードを使用することが可能です。 HalfHopはパフォーマンスを向上させるための自明なSSLコンポーネントであり、多くのGNNライブラリの標準スイートに含まれるべきです。

生成モデル – 分子の安定した拡散、離散的な拡散

➡️ 拡散モデルは、特徴空間（元のDDPMのような画像生成のピクセル空間など）または潜在空間（事前学習されたエンコーダによって生成された特徴に対してガウスノイズを追加することなど）で機能する可能性があります。特徴空間では、特徴空間の対称性と同値性を尊重するノイズ処理を設計する必要があります。潜在空間では、ノイズを特徴に加えるだけです。ほとんどの3D分子生成モデルは特徴空間で機能します（先駆的なEDMのようなもの）、そしてXuらの新しいGeoLDMモデル（著名なGeoDiffの著者）は、3D分子生成のための潜在拡散を定義する最初のモデルです。つまり、EGNNオートエンコーダをトレーニングした後、GeoLDMは標準的なガウス分布からノイズをサンプリングするノイズ除去目的でトレーニングされます。GeoLDMはEDMや他の非潜在拡散手法に比べて著しい改善をもたらします。

➡️ 非幾何グラフ（隣接性とおそらくカテゴリカルなノードの特徴のみを持つ）の領域では、DiGress（ICLR’23）によって開拓された離散グラフ拡散が最も適用可能なオプションのようです。ChenらはEDGEという、ノードの次数分布によってガイドされる離散拡散モデルを提案しています。DiGressとは異なり、EDGEでは最終的なターゲットグラフはエッジのない非連結グラフであり、前方ノイズモデルはベルヌーイ分布を介してエッジを削除し、逆のプロセスでは最新のアクティブなノードにエッジを追加します（アクティブなノードとは、前のステップで次数が変化したノードのことです）。次数ガイダンスによって導入される疎な性質のおかげで、EDGEは4kノードおよび40kエッジまでのかなり大きなグラフを生成することができます！

➡️ 最後に、Weilbachらによる「Graphically Structured Diffusion Models」は、連続的な生成モデルと確率的グラフィカルモデルのギャップを埋めるもので、興味のある問題に特定の構造を導入します。これらの問題はしばしば組合せ的な性質を持っています。その中心的なアイデアは、問題の構造を注意マスクとしてエンコードし、変換器エンコーダの注意計算にこのマスクを使用することです（位置埋め込みを使用しない限り、入力トークンの順列に対して同変性を持ちます）。GSDMは、バイナリ連続行列分解、ブール回路、数独の生成、およびソートなどに対応することができます。特に楽しいのは、この論文が🙃で書かれていることです。

幾何学的学習：幾何学的WL、クリフォード代数

幾何学的深層学習が繁栄しています！興味深い論文がたくさん発表されましたが、この投稿ではいくつかを紹介します。

➡️ 幾何学的WLは、Joshi、Bodnarらによる研究でついに登場しました。幾何学的WLは、幾何学的特徴（座標や速度など）を持つWLテストの概念を拡張し、k次元GWLまでの表現能力の階層を導出します。キーポイント：1️⃣ 同変モデルの方が不変モデルより表現能力が高い（ただし、完全に接続されたグラフでは差がなくなる）、2️⃣ 特徴のテンソル次元は表現能力を向上させる、3️⃣ 特徴のボディオーダーは表現能力を向上させる（画像を参照👇）。つまり、球面＞直交座標＞スカラー、および多体相互作用＞距離のみです。この論文では、最初の原理からほとんどのSOTAモデルを導出して実装できる素晴らしい学習ソースであるGeometric GNN Dojoも紹介されています！

➡️ ベクトル以上の要素を考慮するため、RuheらはGeometric Clifford Algebra Networks（GCANs）を導出します。クリフォード代数は、バイベクトル、トライベクトル、および（一般的には）多ベクトルを介した高次相互作用を自然にサポートします。キーポイントは、あらゆる直交変換を超平面上の反射に分解できるとするCartan-Dieudonnéの定理であり、幾何代数はデータをPin(p,q,r)グループの要素として表現します。GCANsは、線形層、正規化、非線形性の概念を導入し、これらがニューラルネットワークでパラメータ化される方法も示しています。実験には、流体力学とナビエ・ストークス方程式のモデリングが含まれています。

実際、既にクリフォード同変ニューラルネットワークを紹介する続編が存在します – クリフォード代数の基礎やCliffordLayersをサポートする最新の論文については、Microsoft Researchによってサポートされています。

💊 同変GNN（EGNN）は、幾何学的なDLのアスピリンであり、ほとんどのタスクに適用され、多くの改良が見られています。 Eijkelboom et alは、EGNNを単体複合体などの高次元構造（すなわち、単体複体）で動作する単体複合体ネットワークと結婚させ、EMPSNを作り出しました。これは、幾何学的および位相的な特徴を組み合わせた最初の例であり、大きな改善の可能性を持っています！最後に、PassaroとZitnickは、SO（3）畳み込みをSO（2）に減らすための洗練されたトリックを導き出し、数学的な同等性の保証を提供します 👀。この発見により、OpenCatalystなどの大規模データセットで幾何学的モデルをスケーリングアップすることが可能となり、すでにEquiformer V2に適用され、近々他の多くの幾何学的モデルのライブラリにも導入される予定です 😉

分子：2D-3Dプレトレーニング、MDにおける不確実性推定

➡️ Liu、Duらは、分子データの2D-3Dプレトレーニングのための新しいフレームワークMoleculeSDEを提案しています。標準のコントラスティブロスに加えて、著者らは2D -> 3Dおよび3D -> 2D入力の再構築を行う2つの生成的コンポーネントを追加しています。これはスコアベースの拡散生成によるものです。GINおよびSchNetを2Dおよび3Dモデルとして使用し、MoleculeSDEはPCQM4M v2で事前学習され、ダウンストリームの微調整タスクで優れたパフォーマンスを発揮します。

➡️ Wollschlägerらは、分子動力学および力場におけるGNNの不確実性推定に関する包括的な研究を行っています。物理学に基づいた重要な原則と応用に焦点を当て、著者らは任意の幾何学的GNNに対するガウス過程ベースの拡張機能である局所化されたニューラルカーネルを提案しています（SchNet、DimeNet、およびNequIPで試されました）。多くの場合、LNKの推定値は、複数のモデルをトレーニングする必要があるコストのかかるアンサンブルと同等かそれ以上の性能を発揮します。

材料とタンパク質：タンパク質のためのCLIP、Ewaldメッセージパッシング、同変拡張

CLIPとその派生物は、テキストから画像へのモデルで標準的なステープルとなりました。テキストからタンパク質へも同じことができるでしょうか？はい！

➡️ Xu、Yuanらは、テキストタンパク質記述（PubMedBERTを介した）とタンパク質配列（ESMを介した）の共通表現を学習するためのProtSTフレームワークを提案しています。コントラスティブロスに加えて、ProtSTには多モーダルマスク予測目的もあります。たとえば、テキストとタンパク質配列のトークンの15％をマスキングし、それらを共通の潜在表現に基づいて予測し、シーケンスまたは言語単体に基づくマスク予測ロスもあります。さらに、著者らは550Kのアラインされたタンパク質配列-記述ペアを持つ新しいProtDescribeデータセットを設計しました。 ProtSTは、PEERベンチマークの多くのタンパク質モデリングタスクで優れたパフォーマンスを発揮します。タンパク質の機能注釈や局在化だけでなく、テキスト記述からのゼロショットタンパク質検索も可能です（以下の例を参照）。ProtSTは、多くのタンパク質生成モデルのバックボーンとして明るい未来を持つ可能性があります 😉

実際に、ICMLにはLinとAlQuraishiによるGENIEやYim、Trippe、De Bortoli、MathieuなどによるFrameDiffなど、テキストの説明にまだ依存していない複数のタンパク質生成の研究があります。したがって、ProtSTを組み込むことは明らかにパフォーマンス向上につながります📈。

⚛️ 分子上のMPNNは、長距離相互作用のモデリングを妨げる厳密な局所性バイアスを持っています。KosmalaらはEwaldメッセージパッシングを導出し、相互作用ポテンシャルを短距離と長距離の項に分解するEwald和を適用しています。短距離相互作用は任意のGNNでモデリングされ、長距離相互作用は新しく、3Dフーリエ変換とフーリエ周波数上でのメッセージパッシングによってモデリングされます。この長距離項は非常に柔軟で、結晶や分子のような周期的および非周期的なシステムをモデル化するためにSchNet、DimeNet、またはGemNetのような任意のネットワークに適用できます。このモデルはOC20とOE62のデータセットで評価されました。詳細については、Arthur KosmalaによるLOG2読書グループの1時間のトークをご覧ください！

同様のアイデアは、LinらによるPotNetで3D結晶にEwald和を使用しています。ここでは、長距離の接続は不完全なベッセル関数でモデリングされています。PotNetはMaterials ProjectデータセットとJARVISで評価されました。これらの2つの論文を読むことで、Ewald和が多くの結晶に関連するタスクにもたらす利点を理解することができます😉

➡️ 結晶と分子に等変換を持たせるためのGNNのさらなるアプローチは、Duval、SchmidtなどによるFAENetで示されています。一般的な方法は、特定の対称性と等変性をGNNアーキテクチャに直接組み込むことです（例：EGNN、GemNet、Ewaldメッセージパッシング）。これは安全ですが計算コストが高い方法です（特に球面調和関数やテンソル積の場合）。もう1つのオプションは、ビジョンでよく使用される方法であり、同じ入力の多くの拡張を表示し、モデルは最終的に拡張における同じ不変性を学習するべきです。著者らは2番目の方法を選び、不変または等変な拡張（たとえばエネルギーや力のための拡張）を厳密にサンプリングする方法を設計しています。そのため、データ拡張パイプラインには、2D / 3Dの入力を共分散行列のPCAに基づいて正準表現に射影する手順が含まれ、そこから回転を一様にサンプリングすることができます。

提案されたFAENetは、距離のみを使用する単純なモデルであり、確率的フレーム平均データ拡張を使用して非常に良いパフォーマンスを示し、6-20倍高速です。結晶構造にも適用できます！

クールな応用: アルゴリズム的推論、帰納的な知識グラフ補完、質量スペクトルのGNN

このセクションのいくつかの論文は上記のいずれにも属さないが、それでも注目に値するものです。

➡️ 「因果関係の正則化を用いたニューラルアルゴリズム的推論」（Bevilacquaらによる）は、グラフ学習における一般化の問題を扱っています。テスト時の大きな入力に対するOOD一般化を研究する中で、著者らはあるステップで同じ計算を行うさまざまな入力が存在することに気付きました。同時に、これは一部の入力が結果に影響を与えない（あるべきでない）ことを意味します。この仮定に基づき、意味のあるステップを予測結果に影響を与えない一連のステップよりも好む自己教師あり目的（Hint-ReLIC）を設計することが可能です。新しい目的は、多くのCLRS-30のタスクでパフォーマンスを90％以上のマイクロ-F1に大幅に向上させます。一般的なメッセージパッシングに同じ原理を活用し、他のグラフ学習タスクにおけるOOD転送を改善できるかどうかは興味深い問題です 🤔

ニューラルアルゴリズム的推論にさらに興味がある場合は、Knowledge and Logical Reasoningワークショップの論文集もチェックしてみてください。そこにはさらに多くの関連研究があります。

➡️ 「InGram: 関係グラフを用いた帰納的な知識グラフ埋め込み」（Leeらによる）は、ICML’23での知識グラフの論文の中でも非常に少ないものの1つのようです（私の検索による限りでは）。 InGramは、テスト時に見かけないエンティティや見かけない関係にも帰納的に一般化できる最初のアプローチの一つです。以前の帰納的なKGモデルでは、少なくともいくつかの形式で関係の埋め込みを学習する必要がありましたが、このパラダイムでは新しい見かけない関係をモデル化することは非自明です。InGramは、元の多関係グラフの上に関係タイプのグラフ（関係グラフ）を構築し、このグラフを基に関係の表現を学習します（GATを実行）。エンティティの表現はランダム初期化とGNNエンコーダによって得られます。エンティティと関係の表現を持つことで、スコアリング関数としてDistMultデコーダを適用します。見かけない関係のInGramは、見かけないエンティティのGraIL（ICML 2020）と同様に影響力がある可能性があります 😉。

🌈 「グラフニューラルネットワークを用いた高分解能質量スペクトルの効率的な予測」（Murphyらによる）は、質量スペクトルの予測という実際の物理問題に対するGNNのクールな応用です。主な発見は、質量スペクトルのほとんどの信号は、少数の成分（生成イオンおよび中性損失式）で説明できるということです。そして、訓練データからその成分の語彙を見つけることが可能です。したがって、この問題は、分子グラフが与えられた場合に、特定の質量スペクトルの値に対応する語彙からトークンを予測するグラフ分類（またはグラフプロパティ予測）としてフレーム化することができます。アプローチであるGRAFF-MSは、エッジの特徴を持つGINを用いた分子グラフ表現を構築し、Laplacian特徴（SignNetを介して）と共変量特徴を用いてプールします。ベースラインのCFM-IDと比較して、GRAFF-MSは、126時間かかるところを約19分で推論を実行し、はるかに高いパフォーマンスを達成します 👀。

最後のミームパート

2022年のミームはついにマイケル・ブロンシュタインに収束しました！

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!