二重連結性に着目しグラフニューラルネットワークの性能を大幅向上
3つの要点
✔️ グラフニューラルネットワーク（GNN）で注目されてこなかったグラフの二重連結性の表現力に着目
✔️ 既存GNNは二重連結性の表現力が低いことを発見
✔️ 二重連結性に関し完全な表現力を持ち、Transformerベースで高速なGNNとしてGraphormer-GDを提案
RETHINKING THE EXPRESSIVE POWER OF GNNS VIA GRAPH BICONNECTIVITY
written by Bohang Zhang, Shengjie Luo, Liwei Wang, Di He
(Submitted on Submitted on 23 Jan 2023 (v1), last revised 11 Feb 2024 (this version, v3))
Comments: Extended from ICLR 2023 Outstanding Paper; 60 pages, 12 figures. Fix typos in the previous version
Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)
code：
本記事で使用している画像は論文中のもの、紹介スライドのもの、またはそれを参考に作成したものを使用しております。
はじめに
グラフニューラルネットワーク（GNN）は2005年に初めてGoriとScarcelliによって、提案されました。グラフは、頂点（ノード）と頂点同士をつなぐ辺（エッジ）で表される関係です。GNNの目的は、与えられたデータのグラフ構造に従って、各ノードの近傍ノードの特徴量を集約した特徴量を学習することです。
学習した特徴量に基づいて、たとえば、各ノードに与えられたラベルを予測します。GNNを用いることで、グラフ上での近接性に基づいてノードの未知ラベルもうまく推測しやすいという効果があります。
しかし、与えられたデータのグラフ構造に従って、各ノードの近傍ノードの特徴量をどう集約するかによって、グラフ構造の違いを反映できない特徴量を学習してしまうことがあります。
要するに、異なるグラフ構造に従って特徴量を学習した場合に、異なる特徴量が学習されてほしいというのが期待ですが、GNNの種類によっては、違うグラフ構造に基づいて特徴量を学習しているのに、結果得られる特徴量が同一のものになってしまうことがあり得ます。
このようなGNNのグラフの表現力に関して、比較対象として良く取り上げられるものがWeisfeiler-Lehman test（WLテスト）です。WLテストはある2つのグラフが同型であるかを判定するテストです。同型であるとは、グラフのノードの順列が異なっているだけで、グラフの接続の仕方が同じであるということです。グラフのノードを識別する番号のつけ方だけ異なっているということです。
WLテストは、このグラフの同型性を判定するために1968年に提案された古典的な方法です。ある規則に従って、グラフのノードの色を塗り分けていった場合に、色のヒストグラムが同一になるグラフは同型と判断するようなテストです。ノード数と次数が同じグラフは同型とみてしまうという欠点はありますが、高速で強力な判定方法とされています。
WLテストと同等以上にグラフの同型性を正しく判定できる特徴量が学習可能かを検討したGNNの研究は多くありますが、グラフの二重連結性に着目したGNNの研究はありません。
対して、今回紹介する論文では、グラフの二重連結性に着目しています。既存のGNN手法のグラフの二重連結性の表現力を調査し、ほとんどの手法がグラフの二重連結性に関する表現力に乏しいことを発見しました。
さらに、グラフの二重連結性に関する表現力が高く、Transformerベースで計算効率の高いGNNとして、Graphormer-GDを提案しています。これにより、実問題のベンチマークでも高い性能を発揮しています。この論文は、ICLR 2023のOutstanding Paperに選ばれた論文です。
では、グラフの二重連結性、ＷLテスト、GD-WL、Graphormer-GDとその評価結果を説明します。
グラフの二重連結性
今回紹介する論文では、グラフの二重連結性に着目していると説明しましたが、そもそもグラフが二重連結性を持つとはどういうことでしょうか？
グラフの二重連結性とは、あるグラフからある一つのノード（あるいはエッジ）を除いても、そのグラフの連結性（グラフのあるノードからエッジを伝って、すべてのノードに辿り着けるようなグラフ）が保持されるようなグラフを指します。
ノードを除いても満たされる場合はノード二重連結性、エッジを除いても満たされる場合は、エッジ連結性と特に呼ばれます。
逆に、あるグラフのあるノードを取り除くと連結性を失う場合、そのノードはカットノードと呼ばれます。あるエッジを取り除くと連結性を失う場合は、そのエッジはカットエッジと呼ばれます。
カットノード、カットエッジの例を図1に示します。
図1の(a)が元のグラフを示します。図1の(b)に示される赤いエッジがカットエッジです。このカットエッジを取り除くと、グラフの連結性が失われます。図1の(c)の橙色で縁取られたノードがカットノードです。このノードを取り除くとグラフの連結性は失われます。
グラフの二重連結性自体は、グラフ理論としては昔から注目されてきた性質です。応用的にも、たとえば、通信ネットワークの場合、通信ネットワーク上のどこかの機器が一つ壊れてしまった際、通信が途絶えると困ってしまいます。よって、カットノードがないような通信ネットワークを作らなければなりません。そういった意味で、実世界でも重要な性質になりえます。
このようなグラフの二重連結性が重要な特徴量になる予測タスクに対して、グラフの二重連結性を表現できないGNNを使うと、予測精度が大幅に低下してしまうと予想されます。
WLテスト（色調整アルゴリズム）
WLテストにもいろいろな種類がありますが、最も基本的な1次のWLテストについて説明し、その課題として二重連結性がうまく識別できないことを説明します。
１次のWLテスト
1次のWLテストは色調整（color refinement）アルゴリズムとも呼ばれます。
まずノードに色がついていなければ、自明な色で初期化をします。たとえば、グラフが分子構造とすれば、原子をノード、原子と原子の結合をエッジとみなしたとき、異なる原子名に異なる色を与えるような初期化です。
次に、各ノードについて、自分自身の色と、自分の一つ隣の近傍ノードの色の多重集合（同じ要素を複数含んでもよい集合）のペアを作ります。各ノードが持つぺア（自分自身の色, 近傍の色の多重集合）について、ユニークなペアに一対一対応の今までと異なる色を付けます。これを繰り返していき、調整前の色と調整後の色が変わらなくなったら、処理終了です。
2つのグラフについて、終了時のグラフの色のヒストグラムを比較し、同じであれば同型のグラフ、そうでなければ非同型のグラフと判定します。
1次のＷLテストによる二重連結性の識別性
GNNの表現力を考察する上で、二重連結性に着目する一つの理由は、1次のWLテストでは、二重連結性を識別できないケースがあるからです。
図2に示すように二重連結性を持つグラフの同型性を1次のWLテストは識別できない例が存在します。
図2は、1行目のグラフが二重連結性を持ったグラフで、赤で縁取られたノードがカットノード、赤線はカットエッジです。2行目のグラフは二重連結性を持たないグラフです。(a)~(d)の各列のグラフ同士を比較すると、接続の仕方が違います。つまり、非同型のグラフです。しかし、WLテストとしては、色のヒストグラム（各色の出現回数）が同じであるので、WLテストでは同型と誤判定されてしまっています。
このように、単純なWLテストでは、二重連結性を十分表現できないので、二重連結性を持つグラフを表現できるWLテストが望まれます。
提案のWLテスト GD-WL
本論文では、WLテストにおいて、ノード間の距離情報を用いると、二重連結性の表現力を持つようになることを数学的に証明しています。ノード間の一般化した距離指標を用いた色調整アルゴリズムが本論文で提案された新しいアルゴリズムです。
GD-WLでは、ノードvの”ペアの多重集合"（(v,u)の距離,uの色) u∈[グラフのノード集合]について、ユニークな"ペアの多重集合"にユニークな色を与えて更新します。
GD-WLにおける(v,u)の距離として、最短パス距離を使った場合をSPD-WLと呼ぶことにします。最短パス距離とは、ノードvからノードuに行くまでに必要な最短のエッジ通過数です。SPD-WLは、エッジ二重連結性に関しては、完全な識別性があると本論文では証明しています。ノード二重連結性に対する完全な識別性はなく、図2(c)の列の2つのグラフを識別できません。
一方で、エッジの二重連結性に関しては、抵抗距離を使った場合（RD-WL）、ノード二重連結性に関して、完全な識別性があると本論文では証明しています。抵抗距離は、グラフを電気回路とみなし、エッジを1オームの抵抗としたときに、ノードvからノードuまでの実効的な抵抗の大きさを距離とみなしたものです。
このように、距離指標を変えれば、エッジ二重連結性、ノード二重連結性はともに識別可能になるので、GD-WLでは、SPD-WLとRD-WLを両方用いることで二重連結性の完全な識別が可能となります。
ただし、PD-ＷL, RD-ＷLを同時に使ったGD-WLを用いた場合にも、同型性判定をできないグラフは存在します。これらを図3に示します。
図3の(a)は、SPD-WLでグラフの識別に失敗するが、RD-WLはグラフの識別に成功する例、図3の(b)はSPD-WL、RD-WLどちらもグラフの識別に失敗する例です。
提案のGNN Graphormer-GD
GD-WLの実装は、Transformerのマルチヘッドアテンションにノード間距離情報を組み込めばできます。GD-WLはTransfomerの並列処理を活用し効率的な計算が可能です。Transformerをグラフニューラルネットワークに応用した既存研究にGraphormerがあり、それにちなんで、本提案手法はGraphormer-GDと名付けられています。
Graphormer-GDの評価結果
本論文で提案されたGNNであるGraphormer-GDの評価結果を説明します。
カットノード、カットエッジの検出タスク
カットノード、カットノードを検出するタスクの評価結果を表1に示します。
既存のGNN(GCN～Graphormer)は85%以下の精度であるのに対して、Graphormer-GDは圧倒的な精度100%を達成しています。二重連結性に関し、既存のグラフニューラルネットワークの表現力の欠落を確認できます。
また、理論通り、提案のGraphormer-GDでは、抵抗距離を取り除くと（w/o. Resistance Distance）、ノードの二重連結性の検出精度が悪化していることが確認できます。
実問題ベンチマークでの評価
実問題のベンチマークとして分子グラフから化学的な特性を予測するZINCと呼ばれるデータセットで精度評価を行いました。
Ｇraphormer-GDのスケーラビリティを確認するため、ZINCの一部のデータからなるZINC-Subset(1万2000個の分子グラフ)とすべてのデータからなるZINC-Full（25万個の分子グラフ）でそれぞれ評価した結果を表2に示します。
表2のParamsはＧNNのモデルパラメータ数です。公平性のため、提案のGraphormere-GDのモデルパラメータ規模は、他手法と同程度の規模にしています。
表2のTest MAE（平均絶対値誤差）が低いほど予測精度が高いですが、GD-WLは表2の既存手法に比べ一番精度が高いと言えます。
これまで着目されてこなかった二重連結性の識別性を上げることで、GNNの性能を向上できました。
表2のTimeは訓練エポック単位の訓練時間ですが、GD-WLは表2の他手法と同程度の処理時間で済むことが分かります。
以上から、GD-WLは、精度と速度を両立していることが分かります。
おわりに
今回紹介した論文では、GNNの表現力に関して、これまで着目されてこなかったグラフの二重連結性の表現力を向上することで、GNNの性能が向上することが示されました。
GNNの表現力と関連して語られることの多いWLテストでは、グラフの二重連結性を識別できないケースがあることを示し、WLテストの改良が必要なことを示しました。
ノード間の距離情報を使ったWLテストとして、GD-WLを提案し、二重連結性を識別できるようになることを示しました。
さらに、既存のTransformerベースのGNN手法に習ってシンプルにGD-WLが実装できることを示し、Graphormer-GDとして提案しました。
Graphormer-GDは、二重連結性を検出するタスクで圧倒的な性能を示し、実世界のベンチマーク問題でも、既存手法に比べ、最良の精度を達成しました。
AIのトップカンファレンスであるICLR2023のOutstanding Paperに選ばれた論文だけのことはあり、理論と実践を兼ね備えた非常に重厚な論文でした。付録を含めると、60ページもの枚数になります。証明も多数、イラストレーションも多数、比較対象の既存手法も多数。提案の可能性と限界、拡張性まで抜かりなく追究されています。強い興味、探求心に動機づけられた論文に思えました。
今回紹介した論文は北京大学が発表した論文です。近年、NeurIPSの採択論文の5割が中国出身の研究者によるものという話も聞きます。中国の高い研究力を感じさせられました。第一著者は、School of the Gifted Youngの出身のようで、詳しくは調べていませんが、この字面からすれば、中国の天才がAIの研究に集まっているのかもしれません。
この記事に関するカテゴリー
