LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN

グラフニューラルネットワーク（GNN）の仕組みを、友人たちにヒントをささやき合うことで謎解きを教える方法で説明しようとしている場面を想像してみてください。これは、本質的にGNNがどのように機能するかと同じです。コンピュータサイエンスの世界では、「グラフ」とは単なる接続の地図（例えば、人々が点であり、友情が線であるソーシャルネットワークのようなもの）を指します。GNNは、これらの線に沿って情報を層（レイヤー）ごとに伝達することで、全体像を理解するように学習する賢いプログラムです。

しかし、この「ささやきゲーム」には2つの厄介な不具合があります。第一に、「オーバー・スムーシング（過度な平滑化）」です。大きな円の中で何度も秘密をささやき続けると、最終的に全員が全く同じ内容を聞くことになり、個々のユニークな詳細が洗い流されてしまい、誰が何を言ったのか判別できなくなります。第二に、「オーバー・スクワッシング（過度な押し潰し）」です。巨大で複雑な物語を、狭くて細い廊下に無理やり押し込んで反対側へ伝えようとしている状況を想像してください。経路が混雑しすぎたり長すぎたりするために、情報は押し潰され、歪められ、あるいは完全に失われてしまいます。科学者たちは、仮想ノード（想像上のスーパーフレンド）を追加して、遠く離れた部分を瞬時に接続し、スピードアップさせることで、これらの不具合を修正しようと長年試みてきました。しかし、最大の疑問は常に「どの友人にその超能力を与えるべきか？」ということでした。通常、研究者たちはただ推測したり、何通りかのルールを試してどれが最も上手くいくかを見てきました。

この論文は、この「推測するゲーム」を解決するための、巧妙で新しいツールであるLEED（Local Embedding Evolution Distance：局所的埋め込み進化距離）を紹介しています。LEEDを、グループの中でメッセージが伝わるにつれて、一人ひとりの「声」（データの表現）がどのように変化しているかを正確に聞き取る、超高感度なマイクロフォンだと考えてください。群衆全体を見て全員の声が同じになっているかどうかを見るのではなく、LEEDは一人ひとりにズームインし、誰がノイズの中に埋もれているか、あるいは誰がボトルネックに陥っているのかを見極めます。著者らは、LEEDを用いて最も重要な「クリティカル・ノード（決定的な節点）」を選び出し、それらを仮想的なスーパーフレンドにすることで、グループの個性を失わせることなく、スクワッシングの問題を解決できることを発見しました。彼らの実験による6つのデータセットを用いた結果は、この新しい手法が、従来の推測ゲームよりも優れた学習を実現することを証明しました。つまり、会話の詳細に注意深く耳を傾けることが、システム全体を修復する鍵であるということです。

ささやきのネットワークの物語

これらのデジタルネットワークの魔法について、さらに深く掘り下げてみましょう。グラフニューラルネットワークを、単なるおどけた歌ではなく、分子、引用、あるいは社会的つながりに関する複雑なデータを回す、大規模な「伝言ゲーム」として考えることができます。標準的なゲームでは、あまりに多くの人を経由してメッセージを伝えると、内容はめちゃくちゃになります。GNNにおいても、情報をあまりに多くの層（レイヤー）に通すと、各ノード（点）のユニークな特徴がぼやけ始め、すべてが同一に見えてしまいます。これがオーバー・スムーシングです。クラス全員が全く同じ制服を着て、全く同じキャッチフレーズを口にするようになったら、親友と知らない人の区別がつかなくなるのと同じです。

そして、その反対の問題があります。それがオーバー・スクワッシングです。これは、巨大なグラフの片側から反対側へメッセージを送る必要があるものの、その経路が狭い場合に起こります。50ページの書簡を、ポストカードしか入らない小さな郵便口に無理やり通そうとしている状況を想像してください。情報は詰め込まれ、押し潰され、歪んでしまいます。グラフの用語では、これは「ボトルネック」において発生します。つまり、単一のノードや少数のエッジが、ネットワークの遠く離れた部分からの膨大なトラフィックを運ばなければならない場所のことです。

これらの問題を解決するために、科学者たちは仮想ノードを追加することを試みてきました。これらを「スーパーコネクター」や「テレポーター（瞬間移動装置）」と考えてください。もし全員とつながっている魔法の友人を加えたなら、メッセージは元のグループの長く曲がりくねった経路を通る必要はなく、テレポーターに飛び乗り、目的地へとジャンプすることができます。これは経路を短縮することで、スクワッシングの問題を解決します。しかし、ここに落とし穴があります。もし間違った人物をテレポーターに選んだり、あるいは追加しすぎたりすると、誤って「オーバー・スムーシング」の問題を悪化させてしまうかもしれません。全員の声が速すぎるスピードで同じになってしまう可能性があるのです。

長い間、研究者たちは「最も友達が多いのは誰か？」（次数）や「最短経路に最も多く関わっているのは誰か？」（媒介中心性）といった、古風なルールを用いてこれらの特別なノードを選んできました。彼らはこれらのルールのいくつかを試し、実験を実行し、どれが最も良いスコアを出したかを確認してきました。それは、どの鍵が実際に合うのかを知ることなく、巨大なキーチェーンにあるすべての鍵をテストして、最適な鍵を探そうとするようなものでした。

LEED：探偵の拡大鏡

この論文の著者であるキリアン・クレサン（Killian Cressant）とペドロ・B・ヴェローゾ（Pedro B. Velloso）は、推測をやめることにしました。彼らは、LEED（Local Embedding Evolution Distance）と呼ばれる新しい指標を構築しました。LEEDは、グラフ全体を見て物事がぼやけているかどうかを見るのではなく、あらゆるノードに対する「拡大鏡」として機能します。それは、ネットワークの各層を通過する際に、各ノードの「エンベディング（埋め込み）」（自分自身の内部表現）がどのように進化するかを正確に追跡します。

ここが巧妙な点です。LEEDは単にノードとその隣接ノードとの間の距離を測定するのではなく、ネットワークが情報を処理する方法を模倣した変換後の、隣接ノードへの最小距離を測定します。これは、ある生徒の回答が隣の生徒の回答と似すぎていないかをチェックするようなものですが、特に「最も近い一致」に注目することで、彼らが互いにコピーし始めていないかを確認する作業です。

これによって、LEEDは二つのことを同時に見抜くことができます：

1. 誰が迷子になっているのか？（他の全員と似すぎてしまい、オーバー・スムーシングを示唆しているノード）
2. 誰がボトルネックなのか？（情報の伝達に苦労しており、オーバー・スクワッシングを示唆しているノード）

論文では、これら二つの問題は実は表裏一体であると論じています。一方を解決しようとする際、もう一方を考慮せずに進めることはできません。スクワッシングを解決するために接続を増やしすぎると、すべてを滑らかにしすぎてしまう（スムーシングしてしまう）可能性があります。LEEDは、グループのユニークさを壊すことなく、流れを改善するために、どのノードが仮想ノードになるべきかという「クリティカル・ノード」を見つけ出すことができます。

実験：新しい戦略のテスト

新しい探偵ツールが実際に機能するかどうかを確認するため、著者らは一連の実験を行いました。彼らは6つの異なるデータセット（化学構造や生物学的データであるMUTAG、ENZYMES、PROTEINSなど）を用い、彼らの手法を従来のノード選択法と比較しました。

彼らは、LEEDを用いてクリティカル・ノードを選択する彼らのアプローチを、既存の2つの人気のある手法と比較しました：

• LVN (Local Virtual Nodes): グラフに小さな仮想ノードのグループを追加する手法。
• PANDA: 特定のノードのサイズを拡張して、より多くの情報を保持させる手法。

かつては、これらの手法は「次数（Degree）」や「PageRank」、「媒介中心性（Betweenness）」といった既存の「中心性」ルールを試行錯誤する必要がありました。それは、どのルールが各データセットに最適かを試していくプロセスでした。著者らは、それらすべての古いルールを、たった一つのLEEDに置き換えました。

結果は有望でした。実験において、LVN-LEEDの組み合わせは、データセット全体で最高の平均パフォーマンスを達成しました。例えば、MUTAGデータセットでは、標準的なGCN（基本的なモデル）の精度は約**74.75%でしたが、LVN-LEEDモデルは83.33%**に達しました。ENZYMESでは、その改善はさらに顕著で、29.08%から31.09%（特定のテストではさらに高い数値）へと上昇しました。

著者らは、従来のメソッドも時にはうまく機能したが、多くのチューニングを必要としたと指摘しています。一方で、LEEDは、多くのルールをテストすることなく、一貫して良好に機能しました。これは、データの局所的な進化に焦点を当てることで、ネットワークをより良く「呼吸」させるための正しいノードを見つけられることを示唆しています。

論文が述べていること（および述べていないこと）

この論文が実際に何を証明しているのかを理解することが重要です。著者らは、LEEDが（ディリクレ・エネルギーのような）従来のグローバルなエネルギー尺度よりも、局所的な詳細を見ることができるため、より情報量の多い診断ツールであることを示しています。また、LEEDを使用してノードを選択することが、ランダムな選択や標準的な中心性尺度を使用する場合と比較して、特定の実験においてより優れたパフォーマンスにつながることも実証しています。

しかし、論文はこれがあらゆる問題に対する魔法の杖であると主張しているわけではないことにも注意を払っています。彼らは、自らの結果が特定のデータセットに基づくシミュレーションと実験に基づいていることを明示しています。例えば、明確なノード特徴を持たないデータセット（COLLABなど）では、改善がそれほど劇的ではなかったことや、PANDAフレームワークを用いたケースでは、パフォーマンスがわずかに低下したこと（ただし有意な差ではない）を指摘しています。これは、LEEDが強力な新しいツールではあるものの、見ているデータの種類に応じて調整が必要かもしれないことを示唆しています。

また、著者らは、自分たちが特定のネットワーク・アーキテクチャ（GCN）に焦点を当てたこと、そしてまだ探索すべき領域が多く残されていることも指摘しています。今後の研究では、LEEDが他のタイプのネットワークでどのように機能するか、あるいはグラフを再配線するためのよりスマートな方法を設計するためにどのように活用できるかを探求できるだろうと考えています。彼らは、オーバー・スムーシングの問題を永遠に解決したと主張しているのではなく、それを捉えるためのより鋭いレンズと、それを修正するためのより良い方法を提示したのです。

まとめ

結局のところ、この論文は「より良く耳を傾けること」についての物語です。長年、科学者たちは、どの友人にスーパーパワーを与えるべきかを推測することで、グラフニューラルネットワークの「伝言ゲーム」を修正しようとしてきました。この論文の著者たちは、メッセージがどこで失われ、どこで全員の声が同じになり始めているのかを正確に把握するために、すべてのささやきに耳を傾けるツール、LEEDを構築しました。このツールを使って正しい「仮想ノード」を選ぶことで、ネットワークがより速く、より正確に学習できることを彼らは示しました。これは、時として大きな問題を解決するために必要なのは、より大きなハンマーではなく、詳細をより良く見るためのより優れた方法であるということを思い出させてくれます。