グラフの含む情報をフルに活用した生成・対照自己教師あり学習異状検知

Time-series 2021年10月08日

3つの要点
✔️ グラフ構造が含む情報をフルに生かす異状検知モデルが現れました
✔️ GNNエンコーダ／デコーダをベースに生成モデル、対照学習を組み込んでいます
✔️ 2つのモデルから得られた異状スコアを組み合わせて、最終的な異状スコアを得ます

Generative and Contrastive Self-Supervised Learning for Graph Anomaly Detection
written by Yu Zheng, Ming Jin, Yixin Liu, Lianhua Chi, Khoa T. Phan, Yi-Ping Phoebe Chen
(Submitted on 23 Aug 2021)
Comments: Published on arxiv.
Subjects: Machine Learning (cs.LG)

code：

本記事で使用している画像は論文中のもの、紹介スライドのもの、またはそれを参考に作成したものを使用しております。

はじめに

最近、グラフまたはネットワークの形式で表される、複雑で相互依存し、接続されたデータを継続的に生成するドメインの増加が目にされます。典型的な例としては、ソーシャルネットワーク、生物学的ネットワーク、交通ネットワーク、金融取引ネットワークなどがあります。これらのグラフ構造化データからのデータマイニングと分析は、特にグラフの大部分のパターンとは大幅に異なるパターン（ノード、エッジ、サブグラフなど）を特定することを目的とする、グラフ異常検出のタスクで大きな注目を集めています。たとえば、金融取引ネットワークでは、2つのアカウント間の異常なエッジ（不正な取引）を特定することが非常に重要です[1]。ソーシャルネットワークでは、異常なノード（ソーシャルボット）がソーシャルネットワーク上で噂を広める可能性があるため、それらを検出することも重要です[2]。ただし、多くのグラフには複雑なリンケージ（構造）情報とノード属性情報が含まれているため、グラフの異常を検出することは困難な作業です。その結果、構造空間、属性空間、および両方の組み合わせに異常が隠される可能性があります。さらに、多くの場合、異状の正解は不明であるため、多くの教師あり分類アプローチは適用できません。これらの2つの課題は、純粋に教師なし学習の方法で、異状検出のための浅い方法から深い表現方法に至るまで、効率的な異状検出への取り組みの増加を促しています。

浅い方法は、主としてグラフに対しての異常量の計量の定義に集中し、これらの計量値に基づく異状捕捉手法を開発しています。

深層学習ベースの手法については、異状検知では、正解データがなく、純粋に教師なし学習環境では、オートエンコーダがよく使用されます。コンテキストと構造を潜在埋め込みにエンコードし、復元誤差により異状スコアを計算します。

しかし、既存のグラフ・オートエンコーダベースの手法では、異状検知には重要であるのにもかかわらず、コンテキスト情報をフルに活用することはできていません。

そこで、この論文では、Fig.1に示す自己教師あり学習手法を提案します。ターゲットノード周辺のサブグラフを対象にして、GNNで潜在表現にエンコードした後、生成モデル、対照モデルを生成し、2つを組み合わせて、最終的な異状スコアを作成します。

先行技術

異状検知

伝統的統計手法、深層学習、半教師あり異状検知などいずれもユークリッド空間でのターゲットデータをとりあつかうものですが、最近ユークリッド空間外のグラフ構造データからの異状検知が注目を浴びてきています。グラフの異状検知では、どのように異常を測定するかが重要です。AMENでは、正常性を定義し測値としました。行列回帰アプローチを適用し、残差が大きい場合に異状とするRaderアプローチ、Anomalousアプローチがあります。グラフでは深層アプローチが適用されています。これらは、グラフのオートエンコーダを潜在空間でのノードの埋め込みに適用し、グラフ情報を復元します。CoLAという自己教師あり学習では、ネットワークデータからの局所情報をインスタンスのペアサンプリングにより探求し、ノード表現の学習に対照学習を用います。異状スコアは対照ペアでに予測スコアで計算されます。CoLAは、自己教師あり学習を対照的に異常パターンを把握するだけに用います。

自己教師あり学習

自己教師あり学習は、コンピュータビジョン、自然言語処理で大きく成功していますが、グラフ領域にも拡張されてきました。DGI(Deep Graph Infomax)は、埋め込み形式のグラフデータを教師なしで学習する最初の対照学習アルゴリズムです。MVGRLは１次隣接と２つのビューでのグラフ拡散からグラフでの対照学習を行います。CG³では、グラフ構造とノード間の限定的につけられたラベル情報ベースの対照学習を利用します。MERITは、異なるビューやネットワークをまたいだノード埋め込みの一致を最大化することにより教師信号を高めます。JOAOは自己学習モデルでグラフ拡張を自動的に学習します。

しかし、これらのすべてのアルゴリズムは、ノードの表現をするだけのアルゴリズムで、異状検知は行いません。

グラフ表現学習

グラフ表現学習の目標は、各ノードやグラフ全体の表現を学習し、下流のグラフ分析タスクを容易にすることです。GCN(Graph Convolutional Networks)はスペクトルドメインでメッセージを伝え、ノード分類で成果を上げています。GAT(Graph Attention network)では、メッセージ伝達過程での隣接の重みを自動的に学習します。GraphSageアルゴリズムは、スケーラビリティを改善し、SIGNは異なるサイズでグラフ畳み込みを行い、グラフサンプリング依存を軽減します。ARGA(Adversarial Regularised Graph Autoencoder)はグラフ学習の頑強性を改善するために、潜在空間での埋め込みを規制する敵対学習を用います。GSNN(Graph Stochastic Neural Network)では、関数ファミリーを同時に学習することにより分類関数の不確実性をモデリングしようとしています。GILはユークリッドと双曲線幾何学の強みを用います。

しかし、既存のGNNアプローチは大部分汎用のグラフ表現学習に焦点を当て、異状検知については探索中です(論文著者)。

手法

SL-GADはFig. 2のように３つの部分、グラフビューサンプリング、敵対対照自己教師あり学習、グラフ異状スコアリングからなります。

まず、インプットグラフからターゲットノードを選び、そのノードのコンテキスト情報を利用します。具体的には、異なる拡張を使って２つの関連したグラフビューを生成します。その後、リッチモードとサブグラフレベルの情報を全活用し、２つの自己教師ありオブジェクト、すなわち生成的属性復元とマルチビュー対照学習を生成します。前者はGAE(Graph Auto-encoder)のアイデアに触発され、選ばれたターゲットノードが異常の場合、もともとの特徴量ベクトルと復元ベクトル間の回帰損失の属性がミスマッチします。後者は、ターゲットノードと周囲のコンテキストを埋め込みと構造空間で直接比較する対照オブジェクティブです。総合して、グラフの異状検知に密接に関連した２つの自己教師ありオブジェクティブを最適化するモデルです。推論時には、２つのスコアリング関数が上の２つのオブジェクティブを基に具体的に設計されます。

異状検知のためのグラフビュー確立

先行研究を見ると、分別器ペアの設計がグラフエンコーダが豊かな構造、属性情報を引き出すキーであることがわかります。大まかに、生成的と対照的の２つのカテゴリーに分けられ、前者は主として属性と構造補助特性予測、後者は異なるスケール（例えばノードとグラフ）での分別を行えます。

ここでは、ターゲットノードとその周辺コンテキストの接続を確立するために、異なるスケール／空間から２つの自己教師あり学習対象(objectives)を提案します。まず、ノードレベルの分別を実施します。これはターゲットノードの特徴量ベクトルをGAEで復元、属性空間で正解と比較します。次に、豊富な構造情報を注入するために、ターゲットノードと局所サブグラフ間の埋め込み、構造空間での混合レベル対照を構成します。複数のビューをサンプリングすることで、対照モジュールで分別中に多様なセミグローバル情報を探索します。

Fig.2の左ブロックでは、入力グラフからターゲットノードをサンプリングします。続いて、その周辺の2つの異なるビューを異なるグラフ拡張をするようにサンプリングします。3つ以上に増やすと返って特性を劣化させるようです。

生成対象には、分別ペアはオリジナルと復元ターゲットノードです。対照対象は、ターゲットノードと２つの分別器ペアからなるサンプリングした２つのグラフビューです。

・ターゲットノードサンプリング

グラフ中のノードレベルの異状検知を主にフォーカスするため、まずターゲットのノードをサンプリングします。

・グラフビューサンプリング

グラフに対してデータ拡張としてRWR(Random Walk with Restart)を適用、ターゲットノードを中心とするグラフビューから固定サイズKでサンプリングします。

・グラフビュー匿名化

サンプリングされたグラフビューは匿名化します。つまり、特徴量はゼロにします。これにより、ターゲットノードの生の属性情報は特徴量の復元やグラフビューの埋め込みの計算に使われません。情報リークを防ぎ、異状検知はコンテキスト情報のみに依ります。

属性復元による生成学習

深層自己エンコーダが異状検知に適していますが、グラフに対しては、ノードの属性情報しか復元しないので、次のようなGNNベースのエンコーダ／デコーダを用います。

・GNNベースエンコーダ

エンコーダは、埋め込み行列、ノード特徴量行列、近接行列を用いて次のように表されます。詳細は、論文を確認してください。

・GNNベースデコーダ

同様にデコーダは次のように表されます。Ｗ_decは学習パラメータ行列です。

・生成グラフ異状検知

Fig.2の中央ブロックのように、近接情報を集めて、２つのグラフビューのオリジナルと復元特徴量の差(MSE)を最小化するように次の損失関数で最適化します。

マルチビュー対照学習

Fig.2の中央ブロックに図示されているように、対照モジュールは３つの部分から構成されます。

・GNNベースエンコーダ

ターゲットノードと２つの関連グラフビューをインプットとして、特徴量ベクトル／行列を求めます。グラフエンコーダは生成モデルのものと同じです。しかし、特徴量ベクトルの変換は次式になります。

・リードアウトモジュール

隠れ層h_tを周辺のサブグラフと対照させるため、リードアウトモジュールは2つのセミ-グローバル表現を生成します。(Fig.2中央部分)この論文では簡単のため平均プーリングを使用しています。

・対照モジュール

次のように、h, gの正、負のペアPを生成します。

ペアの2つの要素を対照するため、シグモイド関数を使ったバイリニア変換による分別器を設計し、次のように対照分別スコアを得ます。

・マルチビュー対照グラフ異状検知

グラフの異常点では、周囲のコンテキストと、属性、トポロジカル特性が異なるはずです。言い換えると(12)が(13)より顕著に大きくなるはずです。このことから、Jensen-Shannonダイバージェンスによるマルチビュー対照オブジェクティブを形成します。これは、ターゲットノードと周辺のコンテキストが一致すると最大化します。

２つのサブグラフについて足し合わせて次式を得ます。

グラフ異状スコアリング

生成モデルでは、ターゲットノードの属性復元は局所コンテキスト情報のみに基づき、スコア関数はL２ノルム距離を用いて次のようになります。

対照モデルでは、ターゲットノードと周辺のノードの分別を行います。このことからスコア関数は次のようになります。

上記2つの異状スコア関数を組み合わせて次式の最終グラフ異状スコア関数を得ます。α、βは調整可能なバランシングファクターです。

モデル最適化とアルゴリズム

モデル最適化に用いる損失関数は、(7)と(15)を組み合わせて次式になります。

実験

実験データセットとしては、次の実世界のデータを使用しています。上２つ(BlogCatalog, Flickr)はソーシャルネットワークのデータです。ノードはユーザを、エッジは2つのユーザの間の関係を示します。残りは引用についてのデータ(ACM, Cora, CiteSeer, Pubmed)です。ノードは出版された論文、エッジは2つの論文の引用関係を示します。

ベースラインには、AMEN, Radar, ANOMALOUS, DOMINANT, DGI, CoLAを使用しています。評価指標は、ROC-AUCです。サブグラフのサイズkは４です。その他のパラメータは論文を参照してください。

結果はTable 3, Fig.3です。見た通り、SL-GADは狙い通り過去SOTAに対してとびぬけた性能を示しています。深層モデルを使わず表現力の劣る上の3つはもちろん、他の深層モデルよりも優れた性能を示しているのは、2つの学習（生成モデル、対照モデル）を組み合わせた効果が表れているとみられます。

また、引用データは押しなべて性能がよく、これはSNSデータがより高い次元で構成されていることと関係しているとみられます。今回はサブグラフのサイズを固定していますが、より高次のグラフの効率の良いビューサンプリングは将来の課題です。