Blog

2020.01.06

Research

【ICLR2020採択論文】グラフニューラルネットワークは頂点識別問題のための「情報」を指数的に失う

Kenta Oono

Engineer

図1:グラフニューラルネットの1層に対応する変換を力学系として表現した図.点線は「頂点識別問題のための情報が少ない」状態に対応する.定理の仮定を満たす場合(左図)は1層の変換で,各点は点線に一様に近づくが,そうでない場合(右図) 場所によっては点線から遠ざかることがある.本論文より引用.

はじめに

エンジニアの大野です.現在私はPFNに勤めながら,大学院博士課程に在籍し,深層学習の理論研究を行なっています(いわゆる社会人博士です).今年4月にエチオピアのアディスアベバで開催されるICLR2020に大学での研究論文が採択されました.ありがたいことに研究成果を高く評価していただき,本論文はspotlight(全投稿論文中の4.2%)に選ばれています (*1).本エントリではその論文の概要を紹介します.詳細は以下の論文をご覧ください.

Kenta Oono and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. InInternational Conference on Learning Representations (ICLR), 2020, to appear, 論文リンク

本論文の概要

本論文では,経験的に知られていたOver-smoothing (*2)と呼ばれる現象に理論的な説明を与えることで,グラフニューラルネットワーク(以下グラフNNと書きます)の表現能力のある種の限界を示しました (*3).具体的には以下の3点がポイントです(正確なステートメントは元論文をご参照ください).

  • 適当な条件の下で,最もポピュラーなグラフNNであるGCN [2]は,層数を無限にする極限において,頂点識別問題 (*4)を解くための「情報」を指数関数的に失うことを示した.
  • ランダムグラフ(具体的にはErdos-Renyiグラフ)がある程度密(つまり枝が多い)かつ頂点数が多い時には,この条件を高確率で満たしてしまうことを示した.
  • 得られた定理をもとに,グラフNNの重みの正規化方法を提案し,実データ(引用ネットワーク)でその効果を示した.

これらの結果は,多層パーセプトロンや畳み込みニューラルネットワークなどとは異なり,多層にしたり,層間に非線形な活性化関数を挟んだりしても,グラフNNの表現能力を向上させることができないような状況が存在することを示しています.

Over-smoothing

グラフNNはその名の通り,グラフ構造を持つデータ(化合物,関係データ,コンピュータビジョンのシーングラフなど)の解析に利用される深層学習モデルです.[2]によると,今回のICLR2020ではグラフニューラルネットワークだけで30本程度の論文が採択されていることからもわかるように,深層学習研究のホットトピックの一つです.しかし,様々なタスクにおいてグラフNNを多層にしても予測精度が向上しない実験結果が報告されています.例えばKipfらは,論文の出現単語と引用関係から論文のジャンルを当てるタスクに著者らが提案するGCNを用いた場合,層数を8層から10層程度とすると精度が劣化することを報告しています [1].Liらは,グラフNNの層数を増やすと,グラフの頂点上の特徴ベクトルが互いに類似したものとなる現象を起こすことを実験的に示しました [3].Liらはこの現象をOver-smoothingと呼び,グラフNNの精度劣化の一因であることを示唆しています.

図2:Over-smoothingの例.1層から5層のグラフNN(GCN)の出力の可視化(1点が1サンプルを表す).層数が増えるほど,ノードの特徴ベクトルが似通ったものになっている.[3]より引用.

本論文の貢献

本論文では,適当な条件を満たすGCNの出力が,層数に関して指数関数的に「連結成分と次数の情報しか持たない」状態に近づくことを示しました.「連結成分と次数の情報しかもたない」状態とは,グラフ上の2頂点が同じ次数(隣接している頂点の数)で,かつ,同じ連結成分に属しているならば,2頂点の出力ベクトルが同一であること意味します.頂点の違いを区別するための情報が限られているという意味で,この主張は一種のOver-smoothing現象と解釈できます.活性化関数を持たないグラフNN(線形グラフNNとも呼ばれます)において,このようなOver-smoothingを理論的に説明する試みはいくつかの既存研究でなされていました(有限状態のマルコフ連鎖の収束と似たような解析を行います.例えば,[3, 4, 5]などを参照してください).本論文では非線形関数であるReLUを活性化関数として挟んだとしても,Over-smoothingを起こしてしまうこと,すなわち,非線形変換が表現能力を向上できないことを示しました.

今回導いたOver-smoothingを起こすための十分条件は,グラフの形(グラフラプラシアンのスペクトル)とグラフNNの重みのスケールによって特徴づけられます.論文では最も単純な具体例として,ランダムグラフの一種であるErdos-Renyiグラフにおいて,いつこの条件を満たすかを具体的に導きました.その結果,グラフがある程度密(かつある程度大きい)な場合には,多くのGCNがこの条件を満たしてしまうことがわかりました.このことは「密なグラフ上の頂点識別問題には,グラフNNは有効ではない」という仮説,さらにアグレッシブには「現実的な問題でグラフNNがうまくいっているのはグラフが疎だからではないか」という仮説を示唆しています.これらの仮説を念頭に置いて,本論文ではグラフニューラルネットワークの重みを正規化する方法を提案し,引用ネットワーク(を少し加工したグラフ)において提案方法の有効性を示しました.

図3:重みの正規化のスケールが頂点識別問題の精度に与える効果.グラフニューラルネットワークの重みをグラフのトポロジーに応じて適切にスケーリングすることで,引用ネットワークでの頂点識別問題の精度が向上した.本論文より引用.

まとめ

本エントリでは,ICLR2020に採択されたグラフNNの表現能力解析に関する論文を紹介しました.グラフNNはこの2, 3年で応用事例が急速に増加していますが,多層パーセプトロンや畳み込みニューラルネットワークのような古典的な深層学習モデルに比べると,その理論的側面は未知の部分が多いです.理論研究が進むことで「グラフNNはどんなタスクが解けて,(さらに重要なことは)どんなタスクが解けないのか」が今後より明らかになると考えています.学習理論の観点からは,前回の私のブログエントリ [6]でも紹介したように,グラフNNの最適化や汎化性能の解析が今後なされると予想しています.
ICLR2020は初めてアフリカで開催されます.機械学習の国際学会は欧米で開催されることが多く,今回エチオピアでICLR開催されるのは,機械学習のコミュニティにとってとても意義深いことだと考えています.私自身アフリカ大陸に行くのは初めてで今から楽しみにしています.

脚注

  1. 今回のICLRでは全投稿論文2594本のうち,687本が採択されました.会議では採択論文は基本的にはポスター形式での発表ですが,そのうち48本(全投稿論文中1.8%)はそれに加えて10分間(long talk), 108本(4.2%)は4分間(spotlight talk)の口頭発表を行います.
  2. 調べた範囲ではOver-smoothing邦訳は定まっていないと思います.あえて訳すならば過平滑化でしょうか?
  3. 論文では,グラフNNに限らないもう少し一般的な問題設定を考えて,GCNがその問題設定に当てはまることを示しています.
  4. 頂点識別問題(node classification task)とは,グラフを一つ固定し,グラフ上の頂点の性質を予測する問題を考える.論文を頂点,引用・被引用関係を枝とする引用ネットワークでの論文カテゴリ推定の問題は頂点分類問題の一例です.

参考文献

[1] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
[2] naganandy, Graph-based deep learning literature, 2019年12月26日取得, https://github.com/naganandy/graph-based-deep-learning-literature
[3] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence (AAAI), 2018.
[4] Jiawei Zhang, Lin Meng. GResnet: Graph residuals for reviving deep graph neural nets from suspended animation. arXiv preprint arXiv:1909.05729, 2019.
[5] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in GNNs. In International Conference on Learning Representations, 2020, to appear.
[6] 大野健太, 深層学習モデルを用いたノンパラメトリック回帰問題に関する最近の研究, 2019年12月26日取得, https://tech.preferred.jp/ja/blog/deep-nonpara-regression/

 

  • Twitter
  • Facebook