グラフ上の組合せ最適化問題に対するアルゴリズムへの
Graph Neural Networks
を用いた枝刈りの導入
Introduction of Pruning Using Graph Neural Networks to
Algorithms for Combinatorial Optimization Problems on Graphs
中野 裕太
1 ∗吉岡 真治
1,2,3,4Yuta Nakano
1Masaharu Yoshioka
1,2,3,41
北海道大学大学院 情報科学院
1
Graduate School of Information Science and Technology, Hokkaido University
2
北海道大学大学院 情報科学研究院
2
Faculty of Information Science and Technology, Hokkaido University
3
北海道大学国際連携研究教育局ビッグデータ・サイバーセキュリティグローバルステーション
3
Global Station for Big Date and Cybersecurity, Global Institution for Collaborative
Research and Education, Hokkaido University
4
北海道大学創成研究機構化学反応創成研究拠点（WPI-ICReDD)
4
Institute for Chemical Reaction Design and Discovery (WPI-ICReDD), Hokkaido University
Abstract: There are many combinatorial optimization problems in graph analysis. However,
most of them are NP-hard and cannot be solved in a realistic time. Therefore, there are many studies to tackle these problems using machine learning methods, especially Graph Neural Net-works (GNN) recently. However, few studies focus on combining existing algorithms with machine learning methods to prune search states. In this paper, we proposed the pruning method using GNN for combinatorial optimization problems on graphs. We also discussed the characteristic of this pruning method using the maximum clique problem.
1
はじめに
モノとモノの関係を表現する離散構造の 1 つである グラフは，実世界の至るところに現れる．例えば，人 と人との関係を表すソーシャルネットワークに代表さ れるマクロな繋がりから，ある分子における原子同士 の結合関係を表す分子グラフといったミクロな繋がり まで，様々な関係性をグラフにより表すことができる． これらグラフ上における多くの問題が，ある制約条件 を満たす決定変数のうち，何らかの目的関数を最適に するものを求める問題である，組合せ最適化問題とし て扱うことができる．例えば，ソーシャルグラフにお いてお互いが見知った関係であるグループの最大サイ ズを求める問題（最大クリーク問題）や，分子グラフ において特定の官能基を部分グラフとして持つかどう かをチェックする問題（部分グラフ同型性判定問題）な どの多くの実用的な問題が存在する [7]． ∗連絡先： 北海道大学大学院 情報科学院 〒 060-0814 北海道札幌市北区北１４条西９丁目 E-mail: [email protected] しかし，グラフ上の組合せ最適化問題の多くは，計 算量クラスが NP 困難に属することが知られており， これらに対し候補解全てを探索するナイーブなアルゴ リズムを利用し，現実的な時間で最適解を求めること は困難である．そのため，問題の性質を利用した，よ り高速に動作する厳密アルゴリズムや近似アルゴリズ ム，ヒューリスティックな手法を利用し，現実的な時間 で厳密解や近似解を計算するアルゴリズムの研究も盛 んに行われている [17]． 一方，機械学習，特に深層学習を様々な分野へ応用 する研究が近年数多く行われており，画像認識や自然 言語処理といった分野において高い性能を持つモデル が多数提案されている [11]．これら他分野における実 績を踏まえ，組合せ最適化問題に対するアプローチと して，機械学習を利用する試みが増加している [2]．特 に，グラフ上の組合せ最適化問題に対しては，Graph Neural Networks（GNN）を用いたアプローチが多 く，例として，最大クリーク問題 [12] や，巡回セールス マン問題 [13] といった問題に対し研究が行われている． 人工知能学会研究会資料 SIG-FPAI-B902-05しかし，これらの深層学習を用いる研究では，既存 のアルゴリズムと組み合わせるという面からの研究は あまり行われていない．既存研究は，貪欲アルゴリズ ムにおける変数の選択基準を学習し解の質を向上させ るもの [12] や，解を直接計算するもの [13] が主であ る．いくつか，既存の厳密アルゴリズムと組み合わせ る研究が行われているものの，線形計画問題における 分枝限定法アルゴリズムの分枝基準を学習し高速化を 図る [5,6] といったものが主で，枝刈り部分への適用に 焦点を当てた研究は，我々が知る限り存在しない． そこで本稿では，グラフ上の組合せ最適化問題にお いて代表的な問題である，部分集合に関する問題を例 にとり，厳密解を求めるナイーブなアルゴリズムに対 して，GNN モデルによる予測値を利用した枝刈りを導 入することで，近似解を求める手法を提案する．また 具体的に最大クリーク問題を取り上げ，本手法の適用 例を示すとともに，計算機実験による有効性の検証を 行う． 本稿の構成は以下の通りである．初めに 2 節と 3 節 にて，本稿で扱うグラフ上の組合せ最適化問題，ならび に Graph Neural Networks について導入する．続く 4 節にて，提案する枝刈り方法の詳細を説明する． 5 節 にて，具体的に最大クリーク問題を取り上げ，提案し た枝刈り方法を実装し計算機実験を行い，提案手法の 特性について議論する．最後に 6 節にて，本稿全体の まとめを行う．
2
グラフ上の組合せ最適化問題
グラフ上の組合せ最適化最適化問題のほとんどは，以 下の 3 つに分類される [4]． 部分集合問題 グラフ上の頂点集合または辺集合の部分 集合 S のうち，ある目的関数 f (S) が最大となる もの，またはその値を求める問題．例えば頂点集 合に関して最大クリーク問題などが，辺集合に関 して巡回セールスマン問題などがある． 順列問題 グラフ上の頂点集合または辺集合に対する全 ての順列 π のうち，ある目的関数 f (π) が最大と なるもの，またはその値を求める問題．例えば， 最適線形配列問題 [14] などがある． 集合分割問題 グラフ上の頂点集合または辺集合に対す る全ての集合分割P のうち，ある目的関数 f(P) が最大となるもの，またはその値を求める問題． 例えば，頂点彩色問題 [7] などがある． ここで，最大クリーク問題や巡回セールスマン問題 など，多くのグラフ上の組合せ最適化問題が，頂点集合 または辺集合に対する部分集合問題に帰着される．そ のため本稿では，グラフ上の組合せ最適化問題のうち 部分集合問題に着目する．また，ある目的関数 f の最 大化問題が解ける場合，最小化問題を考える際には目 的関数の符号を反転することで同様の手順を用い解く ことができる．そのため本稿では，最大化問題のみを 考える．そして，辺集合の場合でも同様に考えること ができるため，本稿では頂点集合のみを考える． 本稿で扱う部分集合問題について定義 1 に示す． 定義 1（部分集合問題）入力 グラフ G = (V, E) 出力 ある制約条件 cond(G, S) を満たす S⊆ V のうち， ある目的関数 f (G, S) の最大値． cond(G, S) を 満たす S がない場合は−∞ を返す． この問題に対するナイーブなアルゴリズムとして，頂 点集合 V ={v1, v2, . . . , v|V |} のそれぞれの要素を v1か ら順番に，解に含める場合と含めない場合に分岐し計 算していくものが考えられる．個別の問題に対し枝刈 りなどが別途考えられ効率性は劣るものの，候補とな る部分集合全体を探索するアルゴリズムのため，定義 1 の形で表される任意の部分集合問題を解くことができ る．このアルゴリズムの疑似コードを Algorithm 1 に 示す．Algorithm 1 Solve(G = (V, E), S, i)
1: if i ==|V | + 1 then
2: if cond(G, S) then
3: return f (G, S)
4: else
5: return −∞
6: return max{Solve(G, S ∪ {vi}, i + 1), Solve(G, S, i + 1)} 外部から Solve(G,∅, 1) と呼び出すことで，解が計 算できる．また，このアルゴリズムの計算量について だが，ある Solve(G, S, i) は，2 つの Solve 関数を再 帰的に呼び出す．これは，i の値が 1 から|V | + 1 とな るまで，計|V | 回繰り返される．よって，このアルゴ リズムの計算量は，cond(G, S) や f (G, S) の計算が定 数時間で行えると仮定した場合，O(2|V |) となる．多く の問題において，cond(G, S) や f (G, S) は頂点数や辺 数の多項式時間で計算可能なため，Algorithm 1 の時 間計算量は，頂点サイズに対し指数的に増加する． 指数的に増加する時間計算量を抑えるために，効率 的に探索を行う手法である分枝限定法 [10] が存在する． これは，どの探索状態や変数について場合分けするか （分枝），ある探索状態をどのような条件で枝刈りする か（限定）の 2 点の基準を利用し，最適解を素早く探 索し，探索が不要な状態を効率よく枝刈りすることで 効率化を行っている．
ただし，分枝限定法におけるこれら基準の設定は，問 題に対し深い理解を持った専門家によるもの [16] がほ とんどである．近年の深層学習の枠組みにおいて，専 門家による特徴抽出やアルゴリズム開発に変わり，大 量のデータから，あるタスクの学習を通し，特徴抽出 と分析を同時に行う試みが多数行われており，特に画 像や音声，自然言語処理といった分野において高い性 能を発揮している．そこで本稿では，分枝限定法にお ける枝刈り基準を，グラフに対する深層学習モデルで ある GNN を利用し学習することに焦点を当てる．
3
Graph Neural Networks
Graph Neural Networks とは，2009 年に Scarselli ら により提案されたモデル [15] を皮切りにした，グラフ 構造を扱えるニューラルネットワークモデルの総称で ある． 化学や生物といった分野や実社会で現れる，分子グ ラフやソーシャルネットワークといったグラフデータ に対する，多くのグラフ分類・回帰タスクにおいて高 い精度を示していることから，基礎から応用まで幅広 い分野において研究が行われ，様々なモデルが提案さ れている [9, 19, 20]． 多くの GNN は，頂点に特徴ベクトルが付与された グラフに対し，更新する頂点の近傍頂点の特徴ベクト ル集合に対し，要素和や平均を取るといった畳み込み 処理を行うことで，各頂点の特徴ベクトルを更新して いき，一定回数更新後のグラフ全体の頂点特徴ベクト ルから，グラフ特徴ベクトルを生成する．こうして得 られたグラフ特徴ベクトルを利用し，別のニューラル ネットワークへ入力するなどにより，グラフ分類・回 帰タスクの学習（推論）を行う [19]． 本稿では，この学習により得られたモデルを GNN モ デルと呼ぶ．
4
Graph Neural Networks
を用
いた枝刈り
先程も述べたように，Algorithm 1 は，頂点数に対し 指数オーダーの時間計算量がかかってしまう．そこで 本節では，Solve 関数の再帰呼び出し回数を減らすた めに，ある学習済みの GNN モデルによる予測値を利 用した枝刈りを導入する．具体的には，Solve(G, S, i) の返り値を GNN により予測し，その値と現在の解候 補である S から計算できる解の下界とを比較し，枝刈 りを行うことで再帰的な計算回数を減らす． まず，Solve(G, S, i) の返り値について考える．これ は，U ⊆ {vi, vi+1, . . . , v|V |} のうち，f(G, S ∪ U) が最 大となるものを返す．つまり，S∪ {vi, vi+1, . . . , v|V |} で誘導される G の部分グラフの解の値を返しているこ ととなる．そのため GNN を，入力グラフに対し元の 部分集合問題の最適解の値を返すように学習を行うこ とで，Solve(G, S, i) の返り値の予測値を計算できる． 続いて，学習済みの GNN モデルがあるとし，ある Solve(G, S, i) にて枝刈りを行うことを考える．先述 の通り，S∪ {vi, vi+1, . . . , v|V |} で誘導される G の部 分グラフに対する，GNN モデルの予測値を考え，こ れを pred とする．ここで，分枝限定法における現在 の状態の上界（UB）を，pred + ε (ε ≥ 0) とする． また下界（LB）は，先程も述べたように，現在の S が cond(G, S) を満たす，つまり候補解となるときは f (G, S)，異なるときは−∞ とする．この時，通常の分 枝限定法における枝刈りと同様に，LB ≥ UB である 場合に，Solve(G, S, i) の返り値として LB を返すこと で枝刈りを行う． この枝刈りの利点として，出力される解の値が必ず 下界となることが保証されるという点がある．LB の 値は解の下界であるため，Solve 関数が出力する値が 常に解の下界で抑えられるためである． また，ε の値を大きく取る，つまり GNN モデルに よる予測値の信用度を下げ，安全に枝刈りを行うよう にすることで，枝刈りを組み込んだアルゴリズムが最 終的な解の精度が向上することが予期される．ただし， 同時に枝刈り回数も減少してしまうと考えられる． そして，この枝刈りは，他の部分集合問題に対する アルゴリズムに容易に適用可能である．最大クリーク 問題や巡回セールスマン問題といった，多くのグラフ 上の組合せ最適化問題に対し本枝刈り方法が利用可能 である．続く 5 節にて，よく知られている部分集合問 題の 1 つとして，最大クリーク問題に対し具体的に適 用し，計算機実験を行う． Algorithm 1 に枝刈りを導入した本手法の擬似コー ドを Algorithm 2 に示す．Algorithm 2 PruneSolve(G = (V, E), S, i)
1: if cond(G, S) then 2: return candans = f (G, S) 3: else 4: return candans =−∞ 5: if i ==|V | + 1 then 6: return candans 7: U B = pred + ε 8: LB = candans 9: if LB≥ UB then 10: return LB
11: return max{PruneSolve(G, S ∪ {vi}, i + 1),
5
実験
本節ではまず，最大クリーク問題と，本稿で用いる GNN である，Graph Isomorphism Network（GIN）に ついて取り上げる．続いて，この GIN の学習と枝刈り 方法の検証に用いるデータセットの生成方法について 説明し，実際に GIN を最大クリーク問題の解の値を回 帰するように学習させた結果を示す．最後に，提案し た枝刈り方法に対する計算機実験を行った結果を示し， 提案手法の特性について議論する．
5.1
最大クリーク問題
G = (V, E) のある頂点部分集合 S がクリークを形 成するということは，S に含まれる任意の頂点間に辺 e∈ E が存在することをいう．この時，最大クリーク 問題とは以下の問題である． 入力 無向グラフ G = (V, E)． 出力 クリークを形成する S⊆ V のうち，|S| の最大値． cond(G, S) を，G が S 上のクリークを形成するかを 判定する関数，f (G, S) = |S| とすることで，先程の Algorithm 1 を用い，この最大クリーク問題が解ける ことがわかる． 図 1 に具体例を示す．黒線により囲まれた部分が最 大クリークでありその大きさは 4 である．そのため，こ のグラフの最大クリーク問題の解は 4 となる． 図 1: グラフとその最大クリークの例5.2
Graph Isomorphism Network
今回，枝刈りに用いる GNN として，Xu らにより 提案された Graph Isomorphism Network (GIN) [19] を用いる．これは先述のフレームワーク [19] に則った GNN であり，近傍頂点の特徴ベクトルの和による畳込 み演算と，多層パーセプトロン（MLP）による畳み込 みを行った後の特徴ベクトルの変換により頂点の特徴 ベクトルの更新を繰り返していくモデルである．最終 的に，これら頂点の特徴ベクトルの和をグラフ特徴ベ クトルとする． また同時に Xu らにより，グラフ上における近傍頂点 の特徴ベクトルの和や平均をとるといった畳込み演算が， グラフ同型性を判定する Weisfeiler-Lehman Test [18] における操作と類似している点から，同型なグラフの 判別可能性において，デファクトスタンダードとなって いた Graph Convolutional Networks [9] といった GNN よりも，GIN の方が性能が良いという理論保証を行っ ている． グラフ上の組合せ最適化問題において，同型なグラ フに対する目的関数の値は一致する．そのため本稿で は，同型なグラフの判別可能性の観点から，最も性能 が良いとされている GIN を用いる．
5.3
データセットの生成
先述の GIN を学習させるために，グラフとその最大 クリーク問題の解のペアからなるデータセットが必要 となる．今回，Erd¨os-R´enyi モデル [3] を用い，頂点数 5 から 40 までそれぞれ 1000 個のグラフを生成，それ ぞれに対し Tomita らによるアルゴリズム [16] を利用 し最大クリーク問題の解を計算し，計 36000 個のペア からなる訓練用データセットを生成した． また同様に，それぞれの頂点数において 100 個のグ ラフを生成し，計 3600 個のペアからなる検証用データ セットを生成した． そして，提案した枝刈り方法の効果を検証するため のデータセットとして，Erd¨os-R´enyi モデルを利用し， 一様乱数により生成された 5 から 40 の間のランダムな 頂点数のグラフを 100 個生成し，テスト用データセッ トを生成した．5.4
枝刈りに用いる回帰モデルの生成
先程の GIN により生成されるグラフ特徴ベクトルを， バッチ正規化を導入した 3 層の MLP に入力し最終的 に 1 つの実数値を得るモデルを実装し，モデル全体を Adam [8] を用い 350Epoch 学習を行った． また，Optuna [1] によるハイパーパラメータサーチ を 50 回行い，GIN のレイヤー数，今回使用する MLP のレイヤー数と隠れユニットサイズ，Dropout 率，バッ チサイズを調節し，最適なモデルを今回用いた．設定 したハイパパラメータの値を表 1 に示す． 各 Epch における平均二乗誤差，平均絶対誤差の推移 を，図 2 と 3 に示す．点線が訓練データセット（train）， 実線が検証用データセット（validation）に対する結果 を表している．最終的に，検証用データに対する平均二 乗誤差が 0.3871，平均絶対誤差が 0.4033 となり，精度 よく学習できたといえる．この学習済みモデルを用い， 次の小節における枝刈りの有効性の検証実験を行う．表 1: 設定したハイパーパラメータの一覧 ハイパーパラメータ 値 バッチサイズ 538 GIN のレイヤー数 8 MLP のレイヤー数 4 MLP の隠れユニットサイズ 235 Dropout 率 0.003541 0 100 200 300 Epoch 0 20 40 60 80 MSE train validation 図 2: 平均二乗誤差の推移 0 100 200 300 Epoch 0 1 2 3 MAE train validation 図 3: 平均絶対誤差の推移
5.5
枝刈りの有効性の検証実験
テストデータセットを用い，提案手法による枝刈り の有効性を検証するために，最大クリーク問題におけ る Algorithm 1 と，枝刈りを導入した Algorithm 2 を Python3.7 にてそれぞれ実装し，関数呼び出し回数を 比較する実験を行う．また，Algorithm 2 は予測値の精 度についても見ることとする．ここで，グラフサイズ によっては莫大な時間がかかってしまうため，タイム アウトを 30 分に設定した． 実験結果を表 2 に示す．ε の値については，得られ る解が離散値であることを考慮し，ε = 0, 1 の 2 つの 条件で実行したが，先述の学習結果からわかるように GNN モデルの精度が良いため，ε = 0 の場合でも不適 切な枝刈りが起きず，ε = 1 の場合では安全側に見積 もり過ぎたためか，枝刈りが行われなかった．そのた め本稿では，ε = 0 の実験結果を紹介する． 結果を見るとわかるように，多くのグラフにおいて適 切に枝刈りが働いていることがわかる．枝刈りにより， 関数呼び出し回数が平均で 3 ％，多いものでは 13 ％程 度減少している．また，予測値と実際の解との平均絶 対誤差は 0 となり，間違った解を出力したものはなかっ た．これは，GNN モデルにより直接回帰する場合の平 均絶対誤差と比べ，かなり良い精度といえる． しかし，実行時間は平均して約 6500 倍増加してい る．この原因は，枝刈りを導入したアルゴリズムの実 行時間のほとんど，平均して 98 ％が GNN モデルによ る推論にかかる時間であるためである． 本研究では，不適切な枝刈りを避けるため，性能を 考慮した上で GIN を用いたが，GCN などの他のモデ ルと比較し推論に時間がかかるため，計算時間の増加 を招いてしまった．今後は，このモデルの精度と推論 時間，実行時間のトレードオフや，適切な ε の設定に ついて検討を行う必要がある．6
おわりに
本稿では，最近の機械学習を用いた組合せ最適化問 題へのアプローチにおいて行われていなかった，グラ フ上の組合せ最適化問題に対する既存アルゴリズムの 枝刈りという点に着目し，Graph Neural Networks に よる予測結果を利用した枝刈り方法について提案した． また具体的な問題として最大クリーク問題を取り上げ， 提案した枝刈り方法を実装し，計算機実験を行いその 有効性について検証した． 結果としては，多くのグラフにおいて枝刈りが行わ れ関数呼び出し回数が減少した．また，出力される解 の近似値の精度も非常に良い精度であり，提案手法が 有効であることがわかった．しかし，GNN モデルによ る推論に時間がかかってしまい，実行時間そのものは 改善せず逆に大きく増加してしまった． 今後の課題として，先述のモデル精度と計算時間，ε のトレードオフといった，提案手法における特性に関 し，比較実験などを通して詳細に検討していくことや， 推論用フレームワークの使用といったプログラム面で の高速化， 2 節において挙げた順列問題などへの枝刈 り方法の拡張などが考えられる．参考文献
[1] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In KDD’19, pp. 2623–2631, 2019. [2] Yoshua Bengio, Andrea Lodi, and Antoine
Prou-vost. Machine learning for combinatorial opti-mization: a methodological tour d’horizon. In
CoRR, 2018.
[3] P Erd¨os and A R´enyi. On random graphs, i. Q
Publicationes Math ematicae Debrecen, Vol. 6, p.
290, 1959.
[4] Fedor V. Fomin and Dieter Kratsch. Exact
Ex-ponential Algorithms. Texts in Theoretical
表 2: 枝刈り方法の検証実験の結果
Erd¨os-R´enyi データセット
実行できたグラフ数 30 (既存アルゴリズム:68) 枝刈りが行われたグラフ数 28 1 グラフあたりの枝刈り回数 103.9333 1 グラフあたりの関数呼び出し回数の減少率 0.0314 出力される解と真の解との平均絶対誤差 0 平均の実行時間増加率 6534.5686 実行時間のうち推論時間が占める割合 0.9868
[5] Maxime Gasse, Didier Ch´etelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact com-binatorial optimization with graph convolutional neural networks. In Advances in Neural
Infor-mation Processing Systems 32, pp. 15554–15566,
2019.
[6] He He, Hal Daum´e III, and Jason Eisner. Learn-ing to search in branch and bound algorithms. In
Advances in Neural Information Processing Sys-tems 27, pp. 3293–3301, 2014.
[7] Richard M. Karp. Reducibility among combina-torial problems. In Proceedings of a symposium
on the Complexity of Computer Computations,
pp. 85–103, 1972.
[8] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In
Interna-tional Conference on Learning Representations,
2015.
[9] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolu-tional networks. In Internaconvolu-tional Conference on
Learning Representations, 2017.
[10] Ailsa H. Land and Alison G. Doig. An auto-matic method for solving discrete programming problems. In 50 Years of Integer Programming
1958-2008 - From the Early Years to the State-of-the-Art, pp. 105–132. Springer, 2010.
[11] Yann LeCun, Yoshua Bengio, and Geoffrey Hin-ton. Deep learning. Nature, Vol. 521, No. 7553, pp. 436–444, 2015.
[12] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu-tional networks and guided tree search. In
Ad-vances in Neural Information Processing Systems 31, pp. 537–546, 2018.
[13] Marcelo O. R. Prates, Pedro H. C. Avelar, Hen-rique Lemos, Lu´ıs C. Lamb, and Moshe Y. Vardi. Learning to solve np-complete problems: A graph neural network for decision TSP. In The
Thirty-Third AAAI Conference on Artificial In-telligence, pp. 4731–4738, 2019.
[14] A. Quilliot and D. Rebaine. Exact and approx-imation algorithms for linear arrangement prob-lems. In 2014 Federated Conference on Computer
Science and Information Systems, pp. 493–500,
2014.
[15] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans.
Neural Networks, Vol. 20, No. 1, pp. 61–80, 2009.
[16] Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all maximal cliques and computa-tional experiments. Theor. Comput. Sci., Vol. 363, No. 1, pp. 28–42, 2006.
[17] Vijay V. Vazirani. Approximation algorithms.
Springer, 2001.
[18] Boris Weisfeiler and Andrei A Lehman. A re-duction of a graph to a canonical form and an algebra arising during this reduction.
Nauchno-Technicheskaya Informatsia, Vol. 2, No. 9, pp.
12–16, 1968.
[19] Keyulu Xu, Weihua Hu, Jure Leskovec, and Ste-fanie Jegelka. How powerful are graph neural net-works? In International Conference on Learning
Representations, 2019.
[20] Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: A review of methods and appli-cations. In CoRR, 2018.
