異常検出のためのいくつかのグラフ分割アルゴリズム

セキュリティ分野では、アカウント取引の異常や異なるイベント間の相関関係など、さまざまなシナリオで「グラフ分析」が広く使用されています。他の機械学習アルゴリズムと比較して、分析方法が人間の思考と一致しており、分析プロセスを直感的に視覚化できるという独自の利点があります。

たとえば、次の図は、Hansi のクライアント企業の 1 つにおける、ログイン、USB ディスクの使用、ウイルス検出、マシンの IP、ユーザーによるマシンの使用など、複数の種類のセキュリティ イベントを組み合わせて相関分析を行っています。

図中の「エッジ」は発生したイベントを表し、ポイントのサイズ（マシン、ユーザー、IP、ウイルス、USB ディスクの 5 つのカテゴリのいずれか）はイベントの数を表します。 1 つのグラフで、最も多く発生したウイルス、同じマシンを使用してルールに違反したユーザー、同じ USB ドライブを使用したマシンをすぐに見つけることができます。

次の図は、Hansi が銀行の顧客のために行ったトランザクションの異常の分析の別の例です。ポイントのサイズは出次数に比例し、色は入次数のサイズに応じて青 ⇒ 白 ⇒ 赤に変化します。金融用語では、過剰な流出は火山と呼ばれ、過剰な流入はブラックホールと呼ばれます。この種の状況は、詐欺やマネーロンダリングに関連していることがよくあります。

ただし、グラフが大きくなると、分析プロセスは遅くなります。分析する必要があるエッジの数は、最悪の場合でも、完全に接続された有向グラフのノード数 N に等しい N*(N-1)/2 に等しくない場合でも、多くの場合、N よりもはるかに大きくなります。さらに、画面サイズと可読性の制限により、何千ものノードと対応するエッジを 1 つのグラフに配置することは適切ではありません。

この場合、分割統治戦略を採用します。実際の経験におけるグラフのコミュニティ特性を使用して、グラフをいくつかの強く接続された領域に分割し、各領域を分析して視覚化します。

優れたグラフ分割アルゴリズムには、実際のアプリケーションで次の 3 つの追加機能が必要です。

1. 高速で、GPU による並列化や高速化が可能です。

2. スモールワールドネットワークの特性（つまり、ノード次数がファットテール方式で分布している）を処理できます。

3. パラメータの影響を受けません。

多くのアルゴリズムは 2 と 3 を満たすことができません。教科書のほとんどのアルゴリズムはグラフを均等に分割し、グラフをいくつのカテゴリに分割する必要があるかがわかっていることを前提としています。

前述のように、HanSi は実際のアプリケーションで「グラフ コンピューティング」を使用して、異常動作検出に関連する問題を顧客が解決できるように支援します。この記事では、広く使用され、効率性が高く、異常検出に適用できる 3 種類のグラフ分割アルゴリズムに焦点を当てます。

スペクトラム部門

スペクトル分割アルゴリズム: グラフ分割を解決するために使用される最も初期のタイプのアルゴリズムであり、そのアイデアはスペクトル グラフ分割理論に由来しています。 行列のスペクトルは、その固有値と固有ベクトルです。 グラフ分割基準の最適解を見つけることは NP 困難な問題です。 良い解決策は、問題の連続緩和形式を考慮し、元の問題をラプラシアン行列のスペクトル分解に変換することです。したがって、このタイプの方法は総称してスペクトル分割と呼ばれます。

各データサンプルをグラフの頂点 V とみなし、頂点間の辺 E にサンプル間の類似度に応じて重み値を割り当てると、類似度に基づく無向重み付きグラフ G=(V,E) が得られます。類似度行列は通常 W または A で表され、親和性行列とも呼ばれ、ガウスカーネルを計算することで得られることが多いです。

類似度行列の各行の要素を足し合わせると、対応する点の次数が得られます。すべての次数の値を対角要素として構成される対角行列は次数行列と呼ばれ、通常は D で表されます。類似度行列 W と次数行列 D を定義すると、次のラプラシアン行列が得られます。

L=D - W

さまざまな基準関数とスペクトル マッピング方法に応じて、スペクトル分割アルゴリズムではさまざまな特定の実装方法が開発されていますが、それらはすべて次の 3 つの主要なステップに要約できます。

与えられたグラフG=(V,E)に対して、グラフのラプラシアン行列Lを計算します。

L行列を固有値分解し、最初のk個の固有値に対応する固有ベクトルを取り、固有ベクトル行列Qを構築します。

K 平均アルゴリズムまたはその他の従来のクラスタリング アルゴリズムを使用して、行列 Q を分割します。各行はサンプル ポイント、つまり元のグラフの頂点が属するカテゴリを表します。

上記の手順は、スペクトル分割のフレームワークにすぎません。具体的な実装では、さまざまな分割基準がありますが、最も一般的なものは、最小カット、比率カット、正規化カットなどです。

スペクトル分割アルゴリズムは、まずラプラシアン行列を導入し、ラプラシアン固有マップを使用して次元を削減します。次に、低次元データはクラスタリングアルゴリズムを使用して分割され、計算量が大幅に削減されます。次の図は、スペクトル分割アルゴリズムによって実現される効果図です。

しかし、スペクトル分割アルゴリズムにもいくつかの欠点があります。

1) 固有ベクトル行列 Q の構築は、間違いなくアルゴリズムの中で最も時間のかかる部分です。高次元の場合、固有ベクトルだけでなく固有値も解くのは非常に困難です。

2) 再帰終了条件を定義するには事前の知識を使用する必要があり、つまり、グラフカテゴリの総数をインテリジェントに識別する機能はありません。

3) 現実世界の複雑なネットワーク グラフには複数のクラスが含まれることが多く、再帰的なバイナリ分割戦略では、取得されたパーティションが最適なパーティションであることを保証できません。

多層分割アルゴリズム

2 番目のタイプのグラフ分割アルゴリズムは、*マルチレベル分割 (1995、Karypis)* と呼ばれます。

高い効率性と高速な計算時間で知られており、スペクトル分割アルゴリズムよりも 10% ～ 50% 高速です。数千万サイズのグラフを数秒で計算できます。その主な実装手順は通常、粗大化フェーズ、初期分割フェーズ、および非粗大化フェーズの 3 つの段階に分かれています。

つまり、下の図に示すように、アルゴリズムは粗化段階で元のグラフを層ごとに圧縮して「小さく」し、頂点数が十分に少ないグラフを取得し、その後、初期分割段階と細分化段階を通じて、頂点数が十分に少ないこのグラフを層ごとに復元して「大きく」し、元のグラフに復元して分割を完了します。

粗大化段階では、主に元のグラフの複雑さを軽減し、グラフの多階層階層を構築します。元のグラフのポイントとエッジを圧縮して結合し、より小さなグラフの階層シーケンスを構築し、最終的に元のグラフを頂点数が十分に少ないグラフに圧縮します。 この圧縮の考え方 (下の図を参照) は、正式にはマッチングとして定義できます。グラフのマッチングとは、2 つのエッジに共通の頂点がないエッジのセットを指します。 グラフのすべてのマッチングの中で、マッチングエッジの数が最も多いマッチングを、グラフの *** マッチングと呼びます。

粗大化段階全体を通じて、元のグラフのすべてのポイントと重みが蓄積され、最終的に最小スケールのグラフに反映されます。 最小スケールのグラフの単純な分割は初期分割段階と呼ばれます。ノード数が少ないため、この段階での操作は非常に高速で、基本的に時間がかかりません。 これは、マルチレイヤーアルゴリズムの核心部分ではありません。そのアルゴリズムは、次の改良段階のアルゴリズムと似ているため、ここでは説明しません。

洗練段階は、グラフの復元と最適化段階とも呼ばれます。この段階では、グラフは粗化レベルに応じて層ごとに元のグラフに復元され、元のグラフの分割が得られるまで、復元プロセス中にいくつかの洗練されたアルゴリズムを使用して層ごとに最適化されます。

これらの一般的な分割アルゴリズムには、スペクトル二分法 (SB)、グラフ成長アルゴリズム (GGP)、貪欲改良法 (GR)、カーニハン・リン改良法 (KLR) などがあります。その中でも、最も有名なのはカーニハン・リン分割アルゴリズムです。

*Kernighan-Lin 分割アルゴリズム* (KL アルゴリズムとも呼ばれる) は、1970 年に Kernighan と Lin によって提案されました。これは、ローカル検索最適化アルゴリズムです。最適化の目的関数は、異なるクラスを接続するエッジの重みの合計を最小化することです。

例えば、下の図に示すように、紫色の点は1つのカテゴリに属し、黒い点は別のカテゴリに属します。KLアルゴリズムは、下の図(a)を下の図(b)に変換する処理です。

紫色のカテゴリーのポイントを黒色のカテゴリーのポイントと交換する方法は、異なるカテゴリーの損失重みの差、つまり、交換前の内部重みと外部重みの差（下の図（a）の数字で示す）から交換後の内部重みと外部重みの値を引いた値を計算することに よって決定されます。この値が正の場合のみスワップが実行され、それ以外の場合はスワップは拒否されます。 値が負になるまで上記の手順を繰り返します。

KL アルゴリズムは理解しやすいですが、得られる解はローカルな *** になることが多いです。次の図は、多層パーティショニング アルゴリズムを使用したグラフ パーティショニングの例です。

多層パーティショニング アルゴリズムの最大の制限は、適切な初期クラスを生成するために事前の知識が必要になることです。

MCLC

***マルコフ クラスター アルゴリズム (2000、Stijn van Dongen) について説明します。これは MCL アルゴリズムとも呼ばれ、高速でスケーラブルな教師なしグラフ クラスタリング アルゴリズムで、グラフ分割にも使用されることがあります。そのアイデアは非常にシンプルで、主にランダム ウォークとマルコフ連鎖に基づいています。 これら2つの概念について簡単に説明しましょう。

ランダム ウォークとは、グラフ内の特定のポイントから「歩き回り」始めると、サブグラフ間を行ったり来たりするのではなく、特定のサブグラフ内を歩き回る可能性が高くなります。ランダム ウォークの計算は、マルコフ連鎖によって行われます。マルコフ連鎖とは、「後遺症がない」という特性を満たすランダムなシーケンスを指します。つまり、将来の状態は現在の状態のみに依存し、過去の状態とは関係がありません。

MCL アルゴリズムの重要なアイデアは、「ランダム ウォーカーが密集したクラスターに到達した後、クラスターから簡単に離れることはありません」です。前者はランダム ウォークのプロセスであり、後者はマルコフ連鎖の「残余効果なし」に基づいています。 MCL アルゴリズムのランダム ウォーク プロセスは、実際には、遷移確率行列を継続的に変更するプロセスであり、拡張とインフレーションの 2 つの操作を繰り返し実行します。

拡張は、前述のマルコフ連鎖の転送行列の極限分布です。このステップでは、遷移確率行列が変化しなくなるまで、その行列をそれ自体で継続的に乗算します。 目標はグラフのさまざまな領域を接続することです。膨張とは、各要素に対してべき乗演算を行い、各列を正規化することです。その目的は、強い隣接要素間の接続を強くし、弱い隣接要素間の接続を弱くすること、つまり、転送行列内の大きな要素の確率を大きくし、小さな要素の確率を小さくすることです。 これら 2 つの操作は、確率転送行列が収束して最終行列が得られるまで繰り返され、最終行列に基づいて結果が得られます。

MCL アルゴリズムは、重み付けされていないグラフと重み付けされたグラフの両方に適用されます。サブグラフの数を事前に設定する必要がないのが、このアルゴリズムの最大の利点です。サブグラフは非均一であり、ロングテールの分散データに適用できます。 次の図は、MCL を使用してグラフを分割した結果です。

ただし、MCL アルゴリズムは、直径の大きいグラフには適用できません。(直径は 2 点間の最大距離を指し、距離は 2 点間のすべてのパスの最小長さです。)