グラフってこんなにすごい！深層学習との融合をレビュー
3つの要点
✔️ GNNの表現力の強さから、急速にアプリケーションが進んでいる。
✔️ GNNの柔軟かつ複雑な構造への、従来深層学習手法の展開についてのレビュー
✔️ 一方で、深層学習に共通、グラフに固有の課題も継続中
Graph Neural Networks: A Review of Methods and Applications
written by Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, Maosong Sun
(Submitted on 20 Dec 2018 (v1), last revised 9 Apr 2021 (this version, v5))
Comments: Published on AI Open 2021
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)
code：
はじめに
「グラフ」については、まだ耳慣れない方も多いのではないかと思います。筆者も最近多変量時系列関係の論文を読み漁っているうちに、グラフが大きな役割を果たしていることに気づかされました。
グラフ理論そのものは、ケーニヒスベルクの七つの橋など一筆書き問題にオイラーが導入したのが始まりとされ、路線図、プロジェクト進捗計画のPERT図、分子構造解析、言語学、四色問題、Webトラフィック解析など幅広く応用されている分野です。日経新聞に紹介されたフェイクニュースの解析では、グラフ構造に着目されました。右がフェイクニュースです。
日本経済新聞記事: フェイクの姿が見えた SNS蝕む誤情報のすみか
定義を見ると、グラフとは対象（ノード）とその間の関係（エッジ）で表現されるデータ構造です。
Note: 繋がりを可視化する グラフ理論入門
従来深層学習では、個々のデータの集まり（ベクトル）や、格子状に配列されたデータ（画像）、逐次データ（テキスト、音声）を主に取り扱ってきましたが、世の中のいろいろな現象、データを対象とすると表現力が不足し、グラフ理論を取り込み発展させることは自然な流れだったのではないかと推測します。
例えば、多変量時系列においてグラフを核にしたGNN(Graph Neural Network)モデルが多く出てきています。その他にも、社会科学、自然科学、知識グラフなど多くの分野でグラフ形態の機械学習がますます注目を浴びてきています。表現力について具体的には、Fig. 1でCNNの場合には、グリッドで区切った局所的なデータを処理し、数層のCNNを重ねたうえで”猫”の全体像を把握できます。一方で、グラフではユークリッド距離は関係なく、”猫”に関係するデータ点を結合してデータ集合として取り扱うことができます。
もう一つの特徴は、表現学習です。低次元のベクトルで、ノード、エッジ、サブグラフを表すことができます。グラフ分析の領域では、機械学習の従来手法では手作業による特徴値の設定に頼りますが、グラフ組み込み手法では学習することができます。DeepWalk, Skipgram model, node2vec, LINE, TADWなどが、その例です。しかし、欠点もあり、ノード間でパラメータ共有されないことから非効率であり、直接組み込みは一般化能力に欠けます。このような観点から、各種のGNN形態が提案されており、工夫の経緯がこの論文で概観されています。最近のトレンドを感じてみてください。
本文に入る前に、グラフを数学的に取り扱うための行列表現について説明します。隣接行列Aは、ノード間に接続関係があるかどうかを表現します。次数行列Dは、それぞれのノードにいくつのエッジが繋がっているかを表現します。ラプラシアン行列は、これらを合わせて表現したもので、L=D-Aです。ラプラシアン行列を正規化した正規化ラプラシアン行列が実際には使用されます。複雑に見えますが、実装例を見ると意外と簡単です。
正規化ラプラシアン行列
Wikipedia: ラプラシアン行列
本論文の構成は次の通りです。
- 一般的なGNN設計のパイプライン（手順）について
- 計算モジュールの実体化
- グラフのタイプとスケールに関する変型
- 学習設定に関する変型
- 設計の例
- 理論的、経験的分析
- 主なアプリケーション
- ４つの未解決の問題
3.にて多くの形態が紹介されます。原論文が25ページあるため、少し長文になりますが、お付き合いください。
GNN 一般的な設計パイプライン
まず、設計者の観点から見てみましょう。グラフはG=(V, E)と表記します。ここで、VのサイズNはノードの数です。Eのサイズ$N^e$はエッジの数 、Aは隣接行列です。グラフの表現学習には、ノードvの隠れ状態、出力ベクトル$h_v, o_v$を用います。Table 1は本論文で用いられる表記です。
グラフの構造
グラフの構造はアプリケーションの中から見つけ出します。通常2つのシナリオがあり、構造的シナリオと非構造シナリオです。前者では、例えば分子構造、物理システムなどアプリケーションの持つ構造を明示的に表現します。後者では、例えば言葉、画像の場合、最初全結合でモデルを作成し、その後、最適化を行います。
グラフ型とスケール
続いてグラフの型と、スケールを決めます。複雑な型を持ったグラフは、そのノードと接続関係により多くの情報を持つことができます。
・有向／無向グラフ
有向グラフでは、すべてのエッジは方向を持っています。無向グラフでのエッジは、2方向エッジとみなすこともできます。
・同種／異種グラフ
同種グラフでは、すべてのノード、エッジが同じタイプです。
・静的／動的グラフ
入力特徴値やグラフの結合が時間が経つにつれ変化する場合、動的グラフとみなします。
スケールについては、明確な分類基準はありません。ここでは、隣接行列、やグラフ・ラプラシアンが処理デバイスに保存することができない規模を大規模とみなし、何らかのサンプリング手法が必要としています。
損失関数
タスクタイプと学習設定により損失関数を決めます。
・ノードレベル
ノードにフォーカスします。ノード分類、ノード回帰、ノードクラスタリングなどを含みます。
・エッジレベル
エッジタイプを分類するエッジ分類と、2つの与えられたノード間にエッジが存在するか予測するリンク予測です。
・グラフレベル
グラフの分類、回帰、クラスタリングです。いずれも、グラフ表現を学習するモデルが必要です。
教師データの観点からは、通常の機械学習のすべてのタイプが存在します。「教師あり」、「半教師あり」、「教師なし」です。「半教師あり」学習では、学習用に少数のラベル付きノードと、大量のラベルなしノードを用意します。テスト段階では、Transductive設定ではラベルなしのノードを与えてラベルを予測するモデルが必要です。一方、帰納的(inductive)設定では、新しくラベルなしのノードを用意し推論します。最近では、Transductive-inductive混合スキームも導入されています。
計算モジュール
共通して用いられる計算モジュールは、伝播モジュール、サンプリングモジュール、プーリングモジュールです。これらを組み合わせて、典型的なGNNはFig. 2の中間部分のように設計されます。表現力を上げるため、通常多層構造がとられます。この一般形に合わないモデルもあります。
計算モジュールの実体化
Fig. 3の分類に従って、計算モジュールの形態による各種GNNについて紹介します。
伝播モジュール - 畳み込み
畳み込み演算を一般化し、グラフに適用するには、スペクトラルアプローチと空間的(statial)アプローチの２つがあります。
・スペクトラル
スペクトラム空間へのフーリエ変換、そして逆フーリエ変換は次のように表記されます。
$U$は、正規化グラフラプラシアンの固有ベクトル行列です。
畳み込み演算子は、次のように定義されます。
対角行列$g_w$を使って、スペクトラル手法の基本関数は次のように表されます。フーリエ変換し、フィルタ$g_m$を施し、逆フーリエ変換する手順です。
各種の$g_w$を用いる代表的なスペクトラル手法は次の通りです。
Spectral Networkは、対角行列$g_w = diag(w)$をフィルタとして用います。計算効率が悪いとされています。
ChebNetは、これに対して、cos(x)の累乗の多項式チェビシェフ多項式をk次で打ち切った$g_m$を提案しています。
GCN (Graph Convolution Networks)は、上式をさらにk=1までで打ち切り、オーバーフィッティング問題を軽減しています。さらに簡素化して次のようになります。これは、次のセクションで説明する空間的アプローチの始まりになっています。Hは畳み込み行列、Xは入力行列、Wはパラメータです。
AGCN(Adaptive Graph Convolution Network)は、暗示的な関係を学習しようとする方法で、残留グラフラプラシアンをもともとのラプラシアンに足し合わせます。分子や化学化合物について、効率的と示されています。
DGCN(Dual Graph Convolution Network)は、局所的関係性と、大域的関係性の両方を捉えます。GCNのコンボリューションネットワークと、隣接行列をPPMI(positive pointwise mutual information)行列で置き換えた次のネットワークを使用します。$A_p$はPPMI行列、$D_p$はこれに対応する次数行列です。
GWNN(Graph wavelet neural network)は、グラフフーリエ変換の代わりにグラフウェーブレット変換$\psi _s$を用います。利点は、行列分解を行うことなくウェーブレットが求められること、グラフウェーブレットは疎で局在化しており、結果の説明性が高いことです。
スペクトラルアプローチによる手法は、理論的な裏付けが明確ですが、フィルタがグラフ構造に依存しているため、他のグラフ構造には適用できないという問題があります。
・基本空間的アプローチ
空間的アプローチは、グラフのトポロジー（ここでは接続形態）に基づき直接畳み込みを定義します。主なチャレンジは、異なるサイズの隣接に対しての畳み込み演算子の定義と、局所不変量を維持することです。
Neural FPsは、度数の異なるノードに対して異なる重み行列を用います。大規模なグラフは扱いにくいという欠点があります。化学化合物に対して性能評価しています。
DCNN(Diffusion convolution neural network)は、ノードの隣接関係を遷移行列（あるいは確率行列）で定義します。ノード、グラフ、エッジの分類に用いられます。
PACHY-SANは、各ノードに対し、きっちりkノードの隣接関係を抽出し、正規化します。通常の畳み込みの受容野の役割をします。
LGCN(Learnable graph convolutional network)は、隣接行列のmaxプーリングでtop-k特徴値を抽出して1D CNNを適用して隠れた表現により隠れ層を計算します。
GraphSAGEは、一般帰納的フレームワーク、ノードの局所隣接から特徴値を集めます（アグリゲーター）。3種のアグリゲーターが提案されています。平均、LSTM, プーリングです。
・アテンション・ベース
GAT(Graph attention network)は、多変量時系列にも適用されています(MTAD-GAT)。隣接ノードとの間のアテンション、さらにセルフアテンションを組み込みます。また、マルチヘッドアテンションも使用されています。
GaAN(Gated attention network)でも同様にマルチヘッドアテンションを用いています。GATと異なり、それぞれのアテンションヘッドの重要度を変えられるようになっています。
・空間的アプローチの一般的なフレームワーク
異なるモデルを一つのフレームワークに集積する提案です。
MoNet(Mixture model network)は、多様体(manifolds)やグラフのような非ユークリッドドメインで畳み込み深層アーキテクチャーをデザインするフレームワークを提供しています。パッチのように局所的に演算子を適用します。この方法の新しいところは、それぞれの局所の特徴により異なる演算子を選択することです。このフレームワークの実体として定式化できる例には、多様体ではGCNN (Geodesic GNN), AGNN(Anisotropic GNN)などがあり、グラフではGGN, DGNNなどがあります。下図はFAUST human datasetでの比較です。色のついているところが誤差が発生している点で、一番下のMoNetは優れた結果を出しています。
MPNN(Message passing neural network)は、いくつかの古典的な手法の特性を抽出します。この手法は量子化学のために開発されました。2つのフェーズからなり、1つ目はメッセージ伝達、2つ目は読み出しです。メッセージ伝達では、隣接ノードよりメッセージを集め、アップデート関数を通して、隠れ変数を更新します。読み出しでは、読み出し関数を用いて隠れ変数から出力します。それぞれの関数の設定を変えることにより異なるモデルを実体化できます。
NLNN(Non-local neural network)は、古典的な非局所平均を一般化し、拡張します。非局所平均は、すべての時空間の点より重みづけした特徴値を計算し隠れ変数とします。セルフアテンションの統一形とみなすこともできます。演算子の定義は次の通りで、f, gの選択によりさまざまな形態をとることができます。
GN(Graph network)は、ノードレベル、エッジレベル、グラフレベルを学習します。多くの変形を一般化することができます。核となる計算ユニットはGN-blockと呼ばれ３つのアップデート関数$\varphi$と、3つの集約関数$\rho$からなります。
伝播モジュール - 再帰
ここまでの畳み込み層では異なる重みを使っていたのに対し、再帰層では同じ重みを共有します。
・収束ベース手法
GNN(Graph neural network)は、最初はこの手法を指していました。その後、より広い範囲のグラフニューラルネットワークを指すようになりました。混乱を避けるため、この論文では下線を引いてこの手法を区別しています。状態H、出力O、特徴値X、ノード特徴値$X_N$について、GNNの行列表記は、このようになります。
漸化式は次のようになります。
GNNの限界は、Fが収縮写像である必要があり、モデルの性能を制約します。またノード表現に着目すると固定点を用いることは情報量が少ないため適していません。
GraphSEN(Graph Echo State Network)は、エコーステートネットワークを一般化したものです。ESNのリザーバー層の特性により収束が担保されており、GNNより効率的です。
SSE(Stochastic Steady-state Embedding)は、やはりGNNの効率を改善しようとするもので、2段階の学習を提案します。アップデートステップでは、パラメータ化された演算子により各ノードの組み込みをアップデートし、写像ステップでは、制約に合わせて定常状態空間に写像します。
LP-GNN(Lagrangian Propagation GNN)は、学習タスクをラグランジュフレームワークでの制約最適化問題として定式化します。これにより固定点についての再計算を避けます。
・ゲートベース手法
一般の深層学習と同様、グラフについてもLSTM, GRUのようなゲート機構が適用されています。各手法の計算はTable 2にまとめられています。
GGNN(Gated graph neural network)は、GNNの制約を解放しようとするものです。GRUを用います。BPTTにより勾配計算します。各ノードの隠れ状態$h_N_\nu$は隣接ノードの情報を集めます。
Tree LSTMには、２つの拡張形Child-Sum Tree-LSTMとN-ary Tree-LSTMがあります。Tree構造のそれぞれの子に対し、忘却ゲートを持ちます。
Graph LSTMは、N-ary Tree-LSTMをグラフに適用した例です。
S-LSTM(Sentence LSTM)は、文をグラフに変換しGraph LSTMを用いて表現を学習します。
伝播モジュール - スキップ接続
グラフニューラルネットワークについても、層を深くして表現力を高めることが狙われていますが、ノイズの増加、過剰スムージングの問題が発生し、必ずしも性能は向上しません。そこで、一般の深層学習と同様スキップ接続が行われます。
Highway GCNは、層ごとのHighway Gateを用います。
JKN(Jump knowledge network)では、すべての中間層から最終層のそれぞれのノードに接続するJumpを適応的に選択します。
DeepGCNでは、ResNet, DenseNetのアイデアを借りて、勾配消失、過剰スムージングの問題を解決しています。
サンプリングモジュール
各層で、隣接ノードからのメッセージを集約していくと、層が重なると関係するノード数が急激に増加する「隣接爆発」の問題が発生します。この問題を軽減するために、サンプリングが行われます。
・ノード・サンプリング
GraphSAGEは、少数の隣接のみサンプリングします。
VR-GCNは、制御変数ベースの確率的近似方法です。受容野を一つ飛び(1-hop)隣接に制限します。
PinSAGEは、重要度にもとづくサンプリングを提案します。ランダムウォークにより平均訪問数のトップTに隣接ノードを制限します。
・層サンプリング
FastGCNでは各層の受容野を直接サンプリングします。
LADIES( LAyer-Dependent ImportancE Sampling)は、ノードの隣接結合からサンプリングをします。
・サブグラフ・サンプリング
ClusterGCNは、グラフをクラスタリングして、サブグラフをサンプリングします。
GraphSAINTは、ノードあるいはエッジを直接サンプリングしてサブグラフを形成します。
プーリングモジュール
Computer visionの手法と同じく、より一般的な特徴値を得るためにプーリングを適用します。
・直接プーリング
Simple Node Poolingは、ノードごとに、ノードの特徴値に対して、最大、平均、総和、アテンションの演算を行います。
Set2setは、MPNNの読み出し関数に用いられており、順序なし集合を取扱い、LSTMベース手法で順序不変量を生成します。
SortPoolingは、ノード組み込みをノードの構造的役割に従ってソートし、GNNに送ります。
・階層的プーリング
Graph Coarseningは、初期の手法で、ノードクラスタリングをプーリングとして用います。
ECC(Edge-Conditioned Convolution)は再帰的ダウンサンプリングを行います。ラプラシアンの最大固有値の極性によりグラフを2つの要素に分けます。
DiffPoolは、学習可能な階層的クラスタリングモジュールを用い、次のアサインメント行列$S^t$を用い、隣接行列を粗雑化します。
gPoolは、各ノードの写像スコアを学習するために写像ベクトルを用い、トップkのスコアからノードを選びます。
EigenPoolingは、ノード特徴値と局所構造を結合して使用します。局所的フーリエ変換によりサブグラフを抽出します。
SAGPool(Self Attention Graph Pooling)も、特徴値とトポロジーを合わせて使い、グラフ表現を学習します。セルフアテンションベースの手法を用います。
グラフ型・スケールについての変形
Fig.4に従って、グラフの型、スケールによる各種GNNを紹介します。
有向グラフ
無向グラフより情報量が多いです。例えば知識グラフではヘッド実体はテイル実体の親クラスです。エッジの方向は親子関係を表しています。順方向と逆方向のエッジを別々にモデリングすることも可能です。(DGP)
異種グラフ
・メタ・パス・ベース
メタ・パスは、経路のそれぞれの場所のノードのタイプを決める経路スキームです。訓練時は、ノードの順序として実体化します。メタ・パスの両端のノードを接続することにより、直接接続していなかった2つのノードの類似性を把握することができます。一つの異種グラフは、いくつかの同種グラフに還元することができるかもしれません。
HAN(Heterogeneous graph Attention Network)はメタ・パスベースの隣接ノードにアテンションをかけ、すべてのメタ・パススキームのもとに出力組み込みにセマンティックアテンションをかけ、ノードの最終表現を生成します。
MAGNN(Metapath Aggregated Graph Neural Network)は、メタ・パスの中間ノードを考慮に入れます。メタ・パスに沿って情報集約した後、関連するメタ・パスに沿ってアテンションを取ります。
GTN(Graph Transformer Networks)は、グラフの変形の手法を提案します。表現学習しながら接続されていないノード間の接続を定義します。
・エッジ・ベース
HGT(Heterogeneous Graph Transformer)は、メタ関係を2つの隣接ノードとその接続の型として定義します。異なるメタ関係には別のアテンション重み行列をアサインします。
HetGNN(Heterogeneous Graph Neural Network)は、異なるタイプの隣接ノードを、異なるサンプリング、特徴値エンコーディング、集約ステップで扱います。
・関係性グラフ
G2S(Graph-to-Sequence)はもともとのグラフを2つに分かれたグラフに変換します。続いて、GGNN, RNNを施し、グラフを文章に変換します。
R-GCN(Relational Graph Convolutional Networks )は、異なる種類のエッジの伝播に異なる重み行列をアサインします。パラメータ数を制限するために２つの制約を導入します。基本分解では、$W_r=\sum_{b=1}^B a_{rb} V_b$。ブロック対角分解では、低次行列集合に対して直接和を$W_r$と定義します。
・多重グラフ
mGCN(Multi-dimensional Graph Convolutional Networks)は、GNNの各層に一般の表現と、次元特有表現を導入しました。次元特有表現は一般表現から異なる写像行列により写像されます。そして集約され次の層の一般表現になります。
動的グラフ
DCRNN(Diffusion Convolutional Recurrent Neural Network), STGCN(Spatio-Temporal Graph Convolutional Networks)は、最初GNNの空間的情報を集め、出力は逐次データになります。
Structural-RNN, ST-GCN(Spatio-Temporal Graph Convolution)では、空間的、時間的メッセージを同時に集め、静的なグラフ構造を時間的接続に拡張します。
DGNN(Dynamic Graph Convolutional Networks)はGCNの各ノードの組み込み出力をLSTMに与えます。
EvolveGCN は、GCNの重みをRNNに与えて、真性のグラフ相互作用を捉えます。
他のグラフ型
・ハイパーグラフ
HGNN(Hypergraph Neural Networks)では、エッジは複数のノードとそれぞれの重みで結合します。
・極性グラフ
SGCN(Signed Graph Convolutional Network)は正のエッジと負のエッジの相互関係を、バランス理論を使って把握します。直観的には、友達の友達は友達、敵の敵は友達という関係です。
大規模グラフ
大規模グラフに対しての手法はサンプリングがその一つですが、他にPageRankで複数のGCN層を１つの伝播層に詰め込む、異なるサイズの畳み込みフィルタを事前計算する手法などがあります。
異なる学習設定のための変形
グラフ・オートエンコーダ
GAE/VGAEは最初にGCNを用いてノードをエンコードし、シンプルなエンコーダで隣接ノードを復元し、もともとの隣接ノードとの差を誤差として計算しました。
ARGA(Adversarially Regularized Graph Auto-Encoder)/ARVGAはGCNベースグラフ自己エンコーダにGANを適用しました。
MGAE(marginalized graph auto-encoder)は、周縁化ノイズ除去オートエンコーダを用いて頑強なノード表現をします。
GALAは、ラプラシアン円滑化の逆処理、ラプラシアンシャープニングを用いて、隠れ状態をデコードします。この方法は、GNN学習のオーバースムージングの問題を軽減します。
AGEは復元損失は、下流タスクに依存しないとして、ペアごとのノードの類似性を測定して適応学習を行います。
対照学習(Contrastive Learning)
対照学習は、教師なしグラフ表現学習のもう一つの流れです。
DGI(Deep Graph Informax)は、ノード表現とグラフ表現の相互情報を最大化します。
infographは、グラフレベル表現と、ノード、エッジ、トライアングルなどの異なるスケールでのサブ構造表現との間の相互情報を最大化することにより、グラフ表現学習を行います。
Multi-viewは、１次隣接行列とグラフ拡散の表現を対照学習します。
GNNの設計例
GPT-GNNを例にとって、GNNの設計過程を説明すると次のようになります。
1.グラフ構造を見つける
学術的知識グラフ、推奨システムのアプリケーションにフォーカスしています。推奨システムでは、ユーザ、アイテム、レビューがノード、それらの関係がエッジとして定義されます。
2.グラフタイプとスケールを決める
このタスクは、異種グラフにフォーカスします。ノード数は数百万あり、大規模異種グラフを取り扱うことになります。
3.損失関数を設計する
下流のタスクはすべてノードレベルなので、ノード表現の事前学習が必要です。事前学習では、ラベルデータはなく自己教師あり学習を設計します。ファインチューニングでは、それぞれのタスクのデータで訓練します。
4.計算モジュールを用いてモデルを構築する
伝播モジュールは畳み込み演算子HGT、サンプリングモジュールは特別に設計したHGTsampling、ノード表現を学習するのでプーリングモジュールは使われません。
GNNの分析
理論的観点
・グラフ信号処理
信号処理の観点から、ラプラシアンはローパスフィルタの効果があります。同類性仮説である、近くのノードは似ていると仮定される、を反映しています。
・汎化
汎化性能については、一部のGNNについてVC次元が証明されています。Gargらにより、ニューラルネットワークについてのRademacher限界に基づいて、より厳しい汎化限界が与えられています。GNNの安定性は、最大固有値に依存するとされています。アテンションはより大きくノイジーなグラフについてのGNNの汎化を助けています。
・表現性
Xuらは、GCN, GraphSAGEは、グラフ同型写像テストのアルゴリズムであるWeisfeiler-Lemanテストより表現力が劣ると示しています。Barseloらは、GNNは一階述語論理のフラグメントであるFOC2にはほとんど適合しないとしています。学習グラフのトポロジー的構造については、局所依存のGNN形態はグローバルなグラフ特性を学習することができないとしています。
・不変性
ノードの順序がないため、GNN出力組み込みは順列不変量、もしくは入力特徴値と同等です。
・変換性
パラメータ化はグラフと結びついていないので、性能保証の上グラフ間を変換することが示唆されています。
・ラベル効率
GNNの（半）教師あり学習には、性能を満足するために、非常に多くのラベル付きデータが必要になります。ラベル付けの効率を上げる手法が研究されており、高次のノード、不確定ノードなどの情報量が多いノードを選択すると劇的に効率が改善するとしています。
経験的観点
・評価
データ分割の仕方や、条件設定により、ランキングが変化したり、不適切な比較になるので注意が必要です。
・ベンチマーク
グラフ学習については、広く受け入れられるベンチマークは難しいです。ほとんどのノード分類データセットは３０００から２０，０００ノードしか含んでおらず、実世界のグラフよりは小規模です。実験手順も統一されていません。しかし、最近信頼のできるベンチマークが提供されるようになってきました。
アプリケーション
構造的シナリオ
・グラフ・マイニング
グラフ・マイニングには、サブグラフ・マイニング、グラフ・マッチング、グラフ分類、グラフ・クラスタリング、などがあります。グラフ・マッチングについては、計算の高度な複雑さが課題でしたが、GNNの登場によりニューラルネットワークを用いてグラフ構造を把握できるようになりました。グラフ・クラスタリングの最近の例では、良好なクラスタリングの特徴を研究し、スペクトラル・モジュラリティの最適化が提案され、良好なメトリックとなっています。
・物理
物理システムのシミュレーションはシステムの法則を学習するモデルを必要とします。対象をノードとして、ペアごとの相互関係をエッジとしてモデリングすることにより、システムはグラフとして単純化できます。例としては、粒子モデル、ロボットがあります。NRIは物体の軌道を入力し、明示的な相互関係グラフを推論します。Sanchezらはロボットの体と関節をエンコードするグラフネットワークを提案しました。強化学習と結合しています。
・化学、生物学
分子フィンガープリントでは、Neural PPsはGCNによりサブ構造特徴値ベクトルを計算、Kearnesらは明示的に原子ペアをそれぞれモデル化し、原子の相互作用を強調しています。
化学反応予測では、Graph Transformation Policy Networkが入力分子をエンコードし、ノードペア予測ネットワークで中間グラフを生成します。
タンパク質境界予測では、リガンドと受容体たんぱく質の表現をGCNで学習し、ペアごとの分類したり、多分解能アプローチにより局所、全体の特徴値を予測したりします。
生物医学エンジニアリング では、Protein-Protein Interaction Networkは乳がんの分類にグラフ畳み込みを用い、Zitnikらは多剤併用による副作用の予測モデルをGCNベースで作成しています。
・知識グラフ
知識グラフ(KG)は実世界のエンティティのコレクション、エンティティペアの関係性を表現します。R-GCNはメッセージ伝達ステップでの関係性に特化した変換を提案しています。Structure-Aware Convolution Networkでは、知識表現の改善のため、GCNエンコーダとGNNデコーダを結合しています。訓練データでは明示されていないエンティティを補完するタスク(KBC)におけるOOKB(Out-of knowledge-base)という課題について濱口らが、GNNを適用しています。
一方、Wangらは異なる言語間の知識グラフのアライメントに対してGGNを適用しています。OAGはこの課題に対してグラフアテンションネットワークを使用しています。Xuらは、この問題をグラフマッチング問題に置き換えています。
・生成モデル
社会的交流モデリング、新化学物質の探索、知識グラフの構築などで生成モデルの関心が高まっています。NetGANは、ランダムウォークでグラフを生成します。GraphRNNでは、各ノードの隣接ベクトルをステップバイステップで生成することにより隣接行列を生成します。GraphAFはグラフ生成を逐次決定過程として定式化しています。
逐次ではなく一括生成する方法も提案されています。MolGAN, Maらの手法などです。GCPN(Graph Convolutional Policy Network)は強化学習を用います。
・組み合わせ最適化
組み合わせ最適化はグラフ理論で有名な巡回セールスマン問題(TSP)や最小全域木などの問題です。Gasseらは、組み合わせ問題の状態を2部グラフで表現しエンコードにGCNを用いました。Satoらは、理論的な解析を行いました。GNNと分散局所アルゴリズムの結合を確立しました。さらに最適化解が最善でどこまでの近似比に到達できるかを示しました。特定の問題に特化したモデルも多く提案されています。
・交通ネットワーク
交通網はダイナミックであると同時に複雑な依存関係を持つため、予測はチャレンジングです。Cuiらは、GNN, LSTMを組み合わせ、時間的、空間的依存性を把握しました。STGCNは、空間的時間的畳み込みを行うST-Convブロックを用います。アテンションを用いる試みもあります。
・推奨システム
ユーザと物品の交流をグラフを用いてモデル化します。GC-MCが最初のモデルです。PinSageは計算量を減らすために2部グラフの重み付きサンプリング戦略を採用しています。GraphRecはSNS情報を利用します。Wuらの方法は、類似性と影響効果を２つのアテンションでモデリングします。
・その他の構造的アプリケーション
金融市場では、異なる株価の関係性をモデリングし、将来予測をします。他の市況指標にも用いられています。Software Defined Networksは、ルーティングに用いられます。Abstract Meaning Representaionは文章生成を行います。
非構造シナリオ
・画像
Few(Zero)-shot 画像分類において、GNNのアプローチはグラフによるより豊富な情報の活用です。1つは知識グラフを使用する方法、2つ目は画像間の類似性を用いる方法です。
画像理由付けでの典型的なタスクは、Visual Question Answering(VQA)です。Teneyらは、画像シーングラフと質問構文グラフを構築しまし、GGNNにより回答を予測しました。
意味セグメンテーションでは、LiangらはグラフLSTMを用い間隔ベースのスパーピクセルマップの形でグラフを作ることにより長期依存性と空間接続をモデリングしました。
・テキスト
文章分類では、グラフは連続しない、離れた単語間の意味を把握することができます。
シーケンスラベリングは観測変数のシーケンスにカテゴリーラベルを与えるものです。文章の中の変数をノードと考え、依存性をエッジとするとGNNの隠れ状態として、この問題を捉えられます。
機械翻訳でGNNが使われるのは、構文や意味情報の付与です。
関係性抽出では、文章グラフはノードは単語に対応、エッジには隣接関係、構文依存性、対話関係などを当てはめることができます。
イベント抽出は、文章の中からイベントを抽出します。
事実検証は、主張を裏付ける証拠を抽出します。
解決していない問題
・頑強性
ニューラルネットワークのファミリーとして、GNNも敵対的攻撃に脆弱です。グラフ構造に対する攻撃、防御についての研究が始まっています。包括的なレビューを参照してください。
・解釈性
GNNについてもブラックボックス性は強く、例示ベースでのモデルについての説明がいくつかあるだけです。
・グラフ事前学習
グラフについての事前学習は着手されたばかりです。それらの研究も課題設定、観点が異なり、まだまだ幅広い研究を必要とします。
・複雑なグラフ構造
実世界のアプリケーションに対し、グラフは柔軟性を持ち、複雑になります。動的グラフ、異種グラフは、ここでも紹介しましたが、さらに強力なモデルが求められています。
まとめ
とっつきにくい感のあるグラフベースのニューラルネットワークですが、MLP, CNNなどでは扱えない非定型、複雑なデータを取り扱うことができるため、ここ数年急激に研究、応用が進んでいます。深層学習やCV, NLP他のほとんどの手法がグラフベースに展開されていることが、このレビュー論文からわかります。
一方、深層学習に共通の、そしてグラフニューラルネットワークに固有の課題が残されており、さらなる研究が期待されています。ここで紹介した主なGNNモデルのソースコードへのリンクは論文の付録にあります。グラフ計算についてのフレームワークも整備されてきており、意外にシンプルに実装することができます。
この記事に関するカテゴリー
