データの点と点をつなぐ！？GNNを用いた新たな多次元時系列データ分析手法の提案！

GNN 2021年05月19日

3つの要点
✔️ 多変量時系列データ分析に特化した新たなGNNアーキテクチャを提案
✔️ 従来のGNNに，変数の属性や，複数の時系列データ同士の時間的・空間的依存関係を捉えられる新たなモジュールを追加
✔️ 4種類の評価用データセットで性能評価実験を行ったところ，４種中３種のデータセットでSoTAを達成

Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks
written by Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, Chengqi Zhang
(Submitted on 24 May 2020)
Comments: Accepted by KDD 2020.
Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)

code：

はじめに

時系列データ分析は、現在金融、環境、交通、医療など実社会の多くの分野において注目を集めている研究領域となっています。多くの場合において、得られる時系列データの変数は複数存在し、各変数同士が互いに依存し合いながら変化しています。

企業の株価の変化を考えてみましょう。一例として、自動車メーカーと、自動車の部品メーカーの企業の株価は依存関係にあります。自動車メーカーの業績が好調になるとそれに対応して部品メーカーの業績も好転し、逆に今回のコロナ禍のように自動車メーカーの業績が悪化すると、それに対応して部品メーカーの業績も下がってしまうということはみなさま容易に想像がつくかと思います。今の例にあげられるように、現実世界で得られる時系列データは、ある変数の変化が他の別な変数に影響を与える相互依存関係があります。しかし従来の時系列データ分析手法では、変数同士が潜在的に持っている依存関係を適切に取り出すことが困難です。

既存のオーソドックスな時系列データ分析手法であるベクトル自己回帰モデル(VAR)やガウスプロセスモデル(GP)などの統計的手法は、変数間の線形依存性を前提としています。しかし一般的には変数の数が増えるに従って依存関係が複雑になるので、線形モデルでは依存関係を近似できなくなることが多いです。一方でこのように変数の数が多い場合に依存関係を的確に取り出すことのできる方法は未だ確立されていません。

本研究では、GNNを時系列データ分析に適用することで、変数間の相互依存関係を適切に取り出すことのできる新たなフレームワークを提案することを目標とします。

GNN(Graph Neural Networks) とは？

ここで、本研究の要所技術であるGraph Neural Network(GNN)についての簡潔な説明を行います。

GNNとは、ニューラルネットワークをグラフ構造に適用できるように拡張したアーキテクチャです。

わかりやすいように、畳み込みの場合で、通常のNeural Networkの場合の畳み込みとGraph Neural Networkにおける畳み込みを比較してみます。

近年GNNは、順列不変性、局所結合性、構成性などの特徴を活かして、グラフデータの取り扱いに大きな成功を収めています。GNNの構造を介して情報を伝達することで、グラフ内の各ノードが近隣のノードを認識することができます。この構造により、ノード間の依存関係を取り出すことが可能となります。

多変量時系列に最も適したグラフニューラルネットワークのタイプは、空間-時間グラフニューラルネットワークです。時空間グラフニューラルネットワークは、多変量時系列と外部のグラフ構造を入力とし、多変量時系列の未来の値やラベルを予測することを目的としています。

空間−時間グラフニューラルネットワークアーキテクチャのイメージ図は以下のようになります。

このアーキテクチャを有効に活用することで、従来の方法では抽出することの難しかった、時系列データ間の依存関係を取り出すことが現在期待を集めています。

GNNの問題点

このように、GNNの性質を生かして時系列データの関係性を取り出すことを行う試みは最近行われ始めています。しかし現状のGNNアーキテクチャにはいくつかの点で課題があります。

課題1：既存のGNNネットワークは、時系列データのグラフ構造をあらかじめ定義する必要があります。しかし多くの場合、特に変数の数が多い場合、未知の多次元時系列データは明示的なグラフ構造を持っているわけではありません。しかしこういった場合に変数間の関係をデータより自動的に獲得する方法は未だに確立されていません。
課題2：GNNはグラフ構造に対する学習アーキテクチャですが、現存する多くのGNNアーキテクチャは、GNNの重みに関する学習のみに焦点を当てており、グラフ構造そのものの最適化、つまりグラフ構造自体が学習を通して更新される必要があるという視点が欠けています。従って、時系列データに関するグラフ構造とGNNの重み係数をいかにして同時に学習していくかが重要なポイントになります。

本研究では、上記の二つの問題を解決するための新しいアプローチを提案します。

提案手法

本研究では、多変量時系列データに特化したGNN(MTGNN)を提案します。MTGNNアーキテクチャの全体像は以下の図で表せます。

提案アーキテクチャは、以下のモジュールで構成されています。

Graph Learning Layer
Graph Convolution Module
Temporal Convolution Module

それぞれについて解説を加えていきます。

Graph Learning Layer

時系列データ間の隠れた関係を捉えるために，グラフの隣接行列を動的に学習することを目的としています。

従来のグラフ学習モジュールは、ノード間の距離指標を計算することでノード同士の類似度や関係性を計算していました。しかしこの方法だと、グラフが大きくなるにしたがって計算コストとメモリが指数関数的に増大してしまいます。

この問題を解決するために、本研究では一部のノードのペア関係のみを計算するsampling approachを導入しました。これにより、各ミニバッチにおける計算とメモリのボトルネックが解消されます。この場合に計算するノードのペアは、類似度や関係性を元に動的に変更できるようにします。これにより、時系列データ同士の未知の関係性を取り出せるように工夫されています。

続いての問題として、従来の距離指標は双方向的なものが多く、これにより計算コストが増大するといった問題がありました。しかし多変量時系列データの場合、特定のノードの状態が変化するに応じて、他の隣接するノードの状態が変化するといった性質があります。(例として、気候情報が変化するに応じて、交通量という別な変数が変化するなど)

したがって、学習される変数間の関係は一方向であることが想定されます。本研究では、一方向の関係性を抽出するように特別に設計されたGraph Learning Layerを導入します。

Graph Convolution Module

Graph Convolution Moduleは、ノードの情報と隣接するノードの情報を融合し，グラフの空間依存性を扱うことを目的として導入されています。Graph Convolution Moduleは2つのmix-hop propagation layerで構成され、各ノードを通過した流入情報と流出情報を別々に処理することができます。純流入情報は，2つのミックスホップ伝搬層の出力を加算することで得られます。Graph Convolution Moduleとmix-hop propagation layerのアーキテクチャを以下の図に示します。

Temporal Convolution Module

Temporal Convolution Module は、拡張された標準的な１次元畳み込みフィルタを適用することで、高次元の時間的特徴を抽出することを目標としています。このモジュールは、2種類の拡張されたInception Layerによって構成されています。1つの拡張されたInception Layerには tanh活性化関数が作用されることでフィルタとして機能します。もう1つの層はシグモイド活性化関数が続き、フィルターが次のモジュールに渡すことができる情報量を制御するゲートとして機能します。時間的な畳み込みモジュールと拡張されたInception Layerのアーキテクチャを下図に示します。

時間的畳み込みモジュールとグラフ畳み込みモジュールの連携図を以下に示す。

評価

提案手法の有効性を判定するために、4種類のデータセットに対して、既存手法と提案手法の比較を行いました。評価に用いた4種類のデータセットは以下になります。

Traffic: カリフォルニア州交通局の交通データセット、2015年と2016年にサンフランシスコ・ベイエリアのフリーウェイで862個のセンサーによって計測された道路占有率が含まれています。
Solar-Energy: National Re-newable Energy Laboratoryの太陽エネルギーデータセットには、2007年にアラバマ州の137のPVプラントから収集された太陽光発電量が含まれています。
Electricity：UCI Machine Learning Repositoryの電力データセットには、2012年から2014年までの321人の顧客の電力消費量が含まれています。
Exchange-Rate: 為替レートのデータセットは、オーストラリア、イギリス、カナダ、スイス、中国、日本、ニュージーランド、シンガポールの8カ国の1990年から2016年までの日々の為替レートを収録しています。

これらの4つのデータセットに対する評価は以下のようになります。

上記の表より、Exchange-Rate以外の3つのデータセット全てにおいて、提案手法は最高精度を示していることがわかります。

結論

本論文では、多変量時系列予測のための新しいフレームワークを提案しました。GNNを多変量時系列予測問題に拡張し、複数の時系列間に内在する依存関係を利用する効果的なアーキテクチャを構築することに成功しました。提案アーキテクチャは、様々な多変量時系列予測課題において優れた性能を発揮し、GNNを用いて多様な非構造データを扱うための新しい可能性を見出しています。