デバイスグラフ分析：セッションをまたいで点と点をつなぐ
グラフデータベースがデバイス間の隠れたつながりをどのように明らかにし、大規模な複数アカウント検知と不正リングの特定を可能にするのか。
一人の不正者が数十のアカウントを操作している場合、個々のアカウントは単独で見ると正規に見えます。それぞれが固有のメールアドレス、もっともらしいIPアドレス、現実的な閲覧パターンを持っています。従来のルールベースの検知は各アカウントを独立して調べるため、不審な点は何も見つかりません。アカウント間のつながり、つまり共有されたデバイス、重なり合うセッション、共通のネットワークフィンガープリントは、アカウントを一つずつ処理するシステムには見えないのです。
なぜグラフなのか
デバイスグラフ分析はモデルそのものを変えます。アカウントを独立して評価する代わりに、ノードがデバイス、アカウント、IPアドレス、セッションであり、エッジが観測されたつながり、たとえば「このデバイスはこのアカウントの作成に使われた」「このIPはこのデバイスとともに観測された」「これら2つのアカウントはセッションクッキーを共有した」を表すグラフを構築します。グラフは、フラットなテーブルでは示せない構造を明らかにします。
5台のデバイスと3つのIPアドレスにまたがって50のアカウントを使う不正リングは、グラフ上で特徴的なクラスターを形成します。クラスター密度、すなわち小さなノード群の内部にある多数のつながりは、強力なシグナルです。正規のユーザーが見知らぬ他人とデバイスを共有することはめったになく、そのアカウント・デバイス間のつながりは密なクラスターではなく、疎で木構造をなします。
グラフデータベースのアーキテクチャ
私たちは4種類のノードを持つプロパティグラフモデルを使用しています。Device（訪問者IDで識別）、Account（お客様のユーザーID）、Network（IPアドレス+ASN）、Session（個々の識別イベント）です。エッジはメタデータ、すなわちタイムスタンプ、信頼度スコア、イベント種別を保持します。
グラフは、2ホップの走査に最適化された専用の隣接インデックスに保存されます。新しい識別イベントが到着すると、そのイベントをSessionノードとして挿入し、DeviceノードおよびNetworkノードに接続し、リンクされたAccountが他のデバイスとのつながりを持つかどうかを確認します。この挿入とクエリの操作は、最大1,000万ノードのグラフに対して5ms未満で完了します。
実は最初はNeo4jを試しました。10万ノードでの開発環境では申し分なく動作しました。ところが本番データ、すなわち5億ノードを読み込むと、2msで済んでいたCypherクエリが800msかかるようになりました。Davidは1週間かけて代替案をベンチマークしてから、私たちはシャーディングしたRocksDBを裏側に持つ独自の隣接インデックスを構築しました。地味なオーダーメイドの解決策が、エレガントな既製の解決策を上回ることもあるのです。
クラスタリングアルゴリズム
私たちはデバイスグラフに2つのクラスタリングアルゴリズムを適用しています。
連結成分
最もシンプルなアプローチは、あるデバイスから到達可能なすべてのノードを見つけることです。Device AがAccount 1とAccount 2に接続され、Device BもAccount 2に接続されている場合、Device AとBは同じ連結成分に属します。これにより、何らかの推移的なデバイス接続を共有するすべてのアカウントを特定できます。
連結成分は計算が高速ですが、正規の共有デバイス（家庭用コンピューター、図書館の端末）が無関係なアカウント間の橋渡しをすると、非常に大きなクラスターを生み出すことがあります。私たちはこれをエッジの重み付けで対処しています。既知の共有環境を経由するつながりには、より低い重みが与えられます。
コミュニティ検出
より繊細な分析のために、重み付きグラフに対してLouvainのコミュニティ検出を実行します。このアルゴリズムは、コミュニティ内のつながりが密で、コミュニティ間のつながりが疎になるように、グラフをコミュニティに分割します。不正リングは、共有インフラを通じてより広いグラフに接続されている場合でも、密なコミュニティを形成します。
LouvainアルゴリズムはO(n log n)の時間で実行されるため、数百万ノードのグラフに対して実用的です。私たちはこれを増分的に実行しています。新しいエッジが追加されると、パーティション全体を再計算するのではなく、コミュニティの割り当てを局所的に更新します。
実例パターン：不正リングの検知
あるゲームプラットフォームが、組織的な不正リングを検知するために私たちのデバイスグラフAPIを統合しました。最初の1週間で、グラフは8台のデバイスと4つのIPアドレスを通じてつながる127個のアカウントのクラスターを明らかにしました。これらのアカウントは3か月間にわたって作成され、それぞれ固有のメールアドレスと現実的なプロフィールを持っていました。ルールベースの検知は、そのうち1つも検知していませんでした。
グラフ構造こそが決め手でした。8台のデバイスを共有する127個のアカウントは、1台あたり平均15.8アカウントを生み出します。このプラットフォームでの正規ユーザーは1台あたり平均1.2アカウントです。クラスター密度は基準値の47倍で、まぎれもない不正のシグナルでした。
スケールでのパフォーマンス
私たちの本番デバイスグラフは23億ノードと81億エッジを扱います。挿入レイテンシはp99で2.4msです。2ホップの走査（長さ2の任意の経路を通じてデバイスに接続されたすべてのアカウントを見つける）はp99で4.1msで完了します。コミュニティ検出の更新は、毎秒50,000個の新しいエッジを処理します。
グラフはデバイスIDのハッシュによって12ノードにシャーディングされ、各シャードは約1億9,000万ノードを保持します。レプリケーション係数3が可用性を保証します。私たちはディザスタリカバリのために1時間ごとにグラフのスナップショットを取得し、増分更新に対する整合性チェックとして、コミュニティ検出の完全な再計算を毎日実行しています。
統合
デバイスグラフは2つのインターフェースを通じてアクセスできます。個別のルックアップ用のリアルタイムクエリAPI（このデバイスは他のアカウントと接続されているか？）と、分析用のバッチエクスポートAPI（N個を超えるアカウントを持つすべてのクラスターを教えてほしい）です。リアルタイムAPIはインラインの不正判断向けに設計されており、アカウント作成時にクエリを実行してそのデバイスが他のアカウントを見たことがあるかを確認します。バッチAPIは、お客様のデータチームの調査ワークフローに供給されます。