構造化データに基づく異常検出の再考: 本当に必要なのはどのようなグラフ ニューラル ネットワークでしょうか?

論文アドレス: https://arxiv.org/abs/2205.15508

コードアドレス: https://github.com/squareRoot3/Rethinking-Anomaly-Detection

構造化グラフデータの異常検出: 背景と課題

異常検出は、データマイニングにおける古典的なタスクの 1 つです。異常なデータを分析することで、企業やユーザーはその背後にある形成メカニズムを理解し、適切な決定を下して損失を回避することができます。インターネットの発展に伴い、構造化データの異常検出、すなわちグラフ異常検出がますます注目されるようになりました。

グラフ異常検出は、具体的には、グラフ上で他の大多数のオブジェクトとは異なる分布パターンを持つ少数のオブジェクト (ノード、エッジ、サブグラフなど) を見つけることとして定義できます。この論文では、グラフ上の異常なノードを検出するタスクに焦点を当てています。従来の異常検出方法と比較して、グラフ異常検出では、さまざまなエンティティ間の相関情報を活用して、ネットワーク セキュリティ、詐欺検出、ウォーター アーミー検出、財務リスク管理、障害監視などの実用的なシナリオにより適したサービスを提供できます。

以下の図は、従来の異常検出とグラフ指向の異常検出タスクの違いを直感的に比較したものです。

図 1: 従来の異常検出タスクとグラフ指向の異常検出タスクの比較。

近年、グラフニューラルネットワークは構造化データを分析および処理するための強力なツールとなっています。グラフ ニューラル ネットワークは、ノード機能と隣接情報を含む埋め込み表現を学習し、分類、再構築、回帰などの下流タスクをより適切に完了します。

しかし、一般的なグラフニューラルネットワーク（グラフ畳み込みネットワークなど）は主に正常データ用に設計されており、異常検出タスクでは「過剰平滑化」問題が発生しやすく、つまり、異常ノードと正常ノードの表現を区別することが難しく、異常検出の精度に影響を与えます。例えば、金融詐欺検出の実際の応用では、通常、異常アカウントは、違法な取引を行う前に、複数の正常なアカウントで正常な取引を行い、自分自身を偽装して自身の疑わしさを軽減します。この種の「関係性詐欺」は、グラフ異常検出の難易度をさらに高めます。

上記の困難を解決するために、研究者らは、（1）注意メカニズムを使用して複数のビューから近傍情報を集約する、（2）再サンプリング法を使用して異なるカテゴリの近傍情報を集約する、（3）グラフニューラルネットワークのトレーニングを支援するための追加の損失関数を設計する、などを含む異常検出タスク専用のグラフニューラルネットワークモデルを提案した。これらの方法は主に、異常に対処するために空間領域の観点からグラフニューラルネットワークを設計しますが、スペクトル領域の観点からこの問題を考慮した人はいません。

異なるスペクトル フィルターを選択すると、グラフ ニューラル ネットワークの表現力に影響し、パフォーマンスに違いが生じることが判明しました。

異なるアプローチ: スペクトルの観点からのグラフ異常検出

既存の研究のギャップを埋めるために、この論文では、グラフ ニューラル ネットワークにおける異常検出用のスペクトル フィルターをどのようにカスタマイズするかという質問に答えることを目的としています。

この論文では、グラフ上の異常データをスペクトル領域の観点から初めて分析し、異常データによってスペクトル エネルギーが「右シフト」する、つまり低周波数に集中するエネルギーが少なくなり、高周波数に集中するエネルギーが増えることを観察しています。

この右シフト現象を視覚化するために、研究者らはまず500個のノードを持つバラバシ・アルバートグラフ（BAグラフ）をランダムに生成し、グラフ上の正常ノードと異常ノードの属性が2つの異なるガウス分布に従い、異常ノードの分散が大きいと仮定しました。

図の上部は、BA 図上のさまざまな程度の異常を含むデータの分布を示しており、下部は対応するスペクトル エネルギー分布を示しています。このうち、棒グラフは対応するスペクトル間隔のエネルギー割合を表し、折れ線グラフはゼロからその点までの周波数領域エネルギーの累積割合を表します。

図 2: スペクトルエネルギーの「右シフト」現象の視覚化。

上図からわかるように、異常データの割合が 0% の場合、エネルギーのほとんどは低周波部分 (λ<0.5) に集中しています。異常ノードの分散 σ または正常ノードに対する比率 α が増加すると、データの異常度が徐々に増加し、スペクトルの低周波部分のエネルギーが徐々に減少し、高周波部分がそれに応じて増加します。この論文では、ガウス分布の仮定に基づいて、データ異常の増加とスペクトルエネルギーの「右シフト」の間に単調な関係があることを理論的に厳密に証明しています。

実際のシナリオでは、異常なデータは通常、より複雑な分布に従います。研究者らは、4つの大規模グラフ異常検出データセットにおいて、「右シフト」現象の存在も確認した。 Amazon の異常ユーザー検出データセットを例にとると、データ内のいくつかの異常ノードを削除すると、スペクトル内の低周波エネルギーが大幅に増加し、高周波エネルギーはそれに応じて減少します。同じ数のランダムノードが削除された場合、スペクトルのエネルギー分布はほとんど変化しません。これにより、異常なデータがスペクトル エネルギーの「右シフト」の鍵であることがさらに証明されます。

図3: 異なるノードの削除がAmazonの異常ユーザー検出データセットのスペクトルエネルギー分布に与える影響: オリジナル、ドロップランダム、ドロップ異常

グラフ異常検出のための新しいツール: ベータウェーブレットグラフニューラルネットワーク

前のセクションの分析では、グラフの異常を検出するときに「右シフト」効果に注意する必要があることが示されています。たとえば、上記の Amazon データセットでは、固有値 λ = 1 付近のスペクトル情報は異常データと高い相関関係にあります。異常な情報をより適切に捕捉するために、グラフ ニューラル ネットワークは、λ = 1 に近い信号のみを保持し、残りをフィルタリングするバンドパス フィルターの特性を備えている必要があります。

残念ながら、既存のグラフニューラルネットワークのほとんどはローパスフィルタまたは適応フィルタであり、バンドパス特性を保証することはできません。適応フィルタはあらゆる関数に適合する能力を備えていますが、異常検出ではローパス フィルタに退化する可能性もあります。これは、データセット全体において、異常データに対応する高周波情報の割合が小さい一方で、スペクトルエネルギーの大部分が依然として低周波に集中しているためです。

異常なデータによって引き起こされる「右シフト」をより適切に処理するために、研究者はグラフ異常検出の新しい方法であるベータウェーブレットグラフニューラルネットワーク (BWGNN)を提案しました。彼らはハモンドのグラフウェーブレット理論を活用して、グラフニューラルネットワークのスペクトルフィルターとしてベータ関数に基づく新しいウェーブレットカーネルを設計しました。

一般的に使用される熱カーネル関数と比較すると、ウェーブレット カーネルとしてのベータ関数は、バンドパス フィルターの要件を満たすだけでなく、周波数領域の局所性と空間領域の局所性も優れています。下の図は、サーマル カーネル ウェーブレットとベータ カーネル ウェーブレットの違いを比較したものです。

図 4: スペクトル領域 (左) と空間領域 (右) における熱カーネル ウェーブレットとベータ カーネル ウェーブレットの比較。ベータ関数の方がバンドパス特性とローカル特性が優れています。

この論文では、4 つの大規模グラフ異常検出データセットで BWGNN のパフォーマンスを検証します。このうち、Yelp データセットはレビュー Web サイト上の異常なコメントの検出を目的としており、Amazon データセットは電子商取引プラットフォーム上の異常なユーザーの検出を目的としており、T-Finance データセットはトランザクション ネットワーク上の異常なユーザーの検出を目的としており、T-Social データセットはソーシャル ネットワーク上の異常なユーザーの検出を目的としており、最大 500 万のノードと 7,000 万のエッジが含まれています。

下の表からわかるように、従来の分類モデル、一般的なグラフ ニューラル ネットワーク、特殊なグラフ異常検出モデルと比較すると、BWGNN は 40% のトレーニング データと 1% のトレーニング データ (半教師あり) の両方のシナリオで優れた結果を達成しています。実行効率の点では、BWGNN はほとんどの一般的なグラフ ニューラル ネットワークと同程度の時間がかかり、他のグラフ異常検出モデルよりも効率的です。

要約する

この論文では、研究者らは、グラフ上に異常なノードが出現するとスペクトルエネルギーが「右にシフト」することを発見し、構造化データの異常検出に新たな視点をもたらしました。この発見に基づいて、本論文ではグラフ異常検出のための新しいツールであるベータ ウェーブレット グラフ ニューラル ネットワーク (BWGNN) を提案します。特別に設計されたバンドパス フィルターを使用して、「右シフト」によって生成される高周波の異常情報をキャプチャし、複数のデータ セットで最適な結果を実現します。

実際の実装では、グラフ異常検出は通常複雑なシステムエンジニアリングですが、適切なグラフニューラルネットワークを選択することがシステムパフォーマンスに影響を与える重要な要素となります。研究者らが提案した BWGNN は、設計が簡潔で、複雑さが少なく、置き換えが容易なため、グラフ ニューラル ネットワークの新たな選択肢となります。