【書き起こし】グラフ理論と不正対策　つながりをデータから解き明かしたい – hmj 【Merpay Tech Fest 2022】

Merpay Tech Fest 2022 は、事業との関わりから技術への興味を深め、プロダクトやサービスを支えるエンジニアリングを知ることができるお祭りで、2022年8月23日（火）からの3日間、開催しました。セッションでは、事業を支える組織・技術・課題などへの試行錯誤やアプローチを紹介していきました。

この記事は、「グラフ理論と不正対策 つながりをデータから解き明かしたい」の書き起こしです。

それでは「グラフ理論と不正対策　つながりをデータから解き明かしたい」というテーマでお話しします。それでは、よろしくお願いします。

自己紹介

IDは、@hmjです。2018年より株式会社メルペイにて、機械学習を中心とした与信モデルの設計開発に携わり、2019年10月からは不正検知領域の機械学習モデルやシステム開発を行っています。辛いラーメンや脂っこいラーメンが好きです。よろしくお願いします。

はじめに、グラフ理論について簡単にお話しします。その後は、グラフ理論を活用している不正対策の事例をいくつか紹介します。最後に、Future Workについてお話しします。

グラフ理論

最初にグラフ理論についてお話しします。グラフ理論の「グラフ」は、折れ線グラフや円グラフではなく、数学の一つの分野である「グラフ理論」のグラフを指しています。

グラフ理論の起源は、1935年頃に数学者のオイラーが「ケーニヒスベルクの橋の問題」を解いたこととして知られています。興味のある方は、「ケーニヒスベルク　オイラー」で検索してみてください。

図にあるように、丸い円とそれらを結ぶ線で抽象化されたものをグラフといいます。丸い円はノードといい、節点や頂点ともいわれています。矢印はリンクで、孤や辺とも言われています。分野によって呼び方はさまざまですが、今回はノードとリンクという言葉を使用します。

丸と線だけで書ける、かつ資料に抽象化された理論ですので、現実世界にどう応用するかは分析者や活用する人のアイディア次第ですし、腕の見せどころだと思います。

「メルカリ」のユニークなデータ

次に、メルカリ・メルペイで、どのようなデータがあって、グラフ理論として活用できるかというお話をします。

メルカリ・メルペイには多種多様なデータがあります。たとえば、メルカリ内の取引に着目すると、ノードをメルカリのお客さまのアカウント（以下、アカウント）、リンクを出品者の方から購入者の方への矢印とすると、グラフとして見ることができます。

この他にも、お店でメルペイを使うシーンもグラフとして見ることができ、一つのノードをアカウントのノード、もう一つのノードを加盟店さまのノードとして決済関係を矢印で結ぶと、またグラフとして見ることができます。

これはあくまで2つの例なのですが、他にもいくつかデータがあり、このようなノードと矢印の関係にしてグラフとして考え、応用することを考えています。

グラフ理論を活用している不正対策の事例紹介

次に、グラフ理論を活用した不正対策の事例を紹介します。今回はクレジットカードの不正利用にフォーカスし、2つの事例をピックアップしました。

1つは多種多様で、多くのノードが作るグラフを解析することで見える特定のパターンの紹介。もう1つは、アカウント同士をグラフ理論を構築して類似度を計算した事例を紹介します。

それでは、1つずつ具体的に見ていきます。

はじめに、特定の位置での出現度合いという例で紹介します。

長らく機械学習チームの方で、グラフを使った分析をしていました。取引でグラフを作ると非常に巨大なグラフになるのですが、その一部分の特定の形状や大きさ、形を細かく分析していくと、特定のパターンで特定の種類、たとえば不正クレジットカードの出現が高くなることが、分析を通して見えてきました。

さらに、形状ごとに不正の発生しやすい場所があるのではないかともわかってきました。図の一番左に Suspiciousという怪しいアカウントが配置されていて、購入者から出品者への矢印でグラフを表現しています。1、2、3、4の表記は、0のノードからどのくらい離れているかという距離を表現しています。たとえばこの図ですと、ノード3とノード0の間にはリンクが1、2、3とあるので、距離は3となります。

取引をリンクにしてグラフ分析をすることで、たとえば怪しいSuspiciousなアカウントに出品したのがノード1ですので、ノード1は怪しいアカウントかもしれないと直感的に言えそうです。

他のノード2, ノード3, ノード4でどういった関係性があるのかをみたときに、距離が1以外のノードでも特定の形状だと、たとえば距離2のときはこういう形状のときに出現しやすい距離3のときはこういった形状のときに出現しやすい、そういったパターンがいくつか見えてきました。

このように、メルカリ・メルペイで行われている取引のグラフからパターンを発見すれば、不正クレジットカードの検出ができるのではないかと考えました。

ただ、この発見は効果があったように思うのですが、取引のみのグラフですとカード関係全体を覆うほどの量にはなっていません。それが、チームの大きな課題になっていました。そこで取引だけではなく、属性情報に着目してグラフを作れないかと考えました。

アカウント同士の類似度合い

続いて、アカウント同士の類似度についてグラフを活用した例です。

これは、取引をリンクに使えない場合にどうするかを考えた図です。アカウントが持っている属性情報を青いノード、それ以外の人のマークがついたものをアカウントのノードとしています。

アカウント同士に類似度があるほど、アカウント間の青いノードが増えていきます。

2つの図がありますが、これは3つの属性情報を2つのアカウントが共有している状態で、属性情報にもよりますが「もしかしたら2つのアカウントは非常に類似度が高いのではないか」と言えそうです。

アカウント同士につながりがあるといっても、図のように01と02で2つの状態に分けられます。図01は右側に緑色のアカウント、左側に黒いSuspiciousなノードがあり、Suspiciousなノードと緑のノードは属性情報を3つ共有しているので、何か怪しいのではないかと言えそうです。

それに対して図02は同じく3つの属性情報共有していますが、2つともSuspiciousなノードではないので、単純に属性情報が似ているだけとしか言えません。常にSuspiciousと関係性があるグラフなのかそうでないのか、2つの状態に分けることができます。

カード不正の場合も図01のような状態を見つけることができれば、不正検知として応用できます。

カード不正にフォーカスすると、図01・02は別々な状態であるとも言えます。でも実はそれだけでなく、時間が経つにつれてそれぞれの状態が変わっていくとも見ることができます。その例を、次に解説します。

時間発展をするグラフ

それが、時間発展するグラフです。この例は、連続的に流れる時刻のグラフを5つのスナップショットで分けたものです。

一番左の時刻1から見ていきたいと思います。時刻1はアカウントがひとつ作られていて、そのアカウントが3つの属性を持っている状態を表しています。

次に時刻2を見ると、先ほど作られたアカウントに対して、もうひとつアカウントが作られている状態を表しています。2つ目のアカウントは、先ほど作られたアカウントに対して2つの属性情報を共有していることがわかります。

実は時刻2はもう一つの情報を持っていて、小さく下の方にピンク色で書いてある通りカード決済を右下のアカウントがこの時刻にしていることも表現しています。カード決済については、のちほど伏線が回収されます。

次の時刻3では左下にアカウントが作られて、同じく2つの属性情報が共有されており、計3つのアカウントが作られたことを表現しています。

一番情報量が多いのは、時刻4です。時刻がしばらくたった想定なのですが、時刻2でのカード決済が、実は不正利用だったことが情報として届いたことを表現しています。通常、カード決済から不正利用が判明するまでにはとてもタイムラグがあるので、それを表しています。

時刻3までは、ひとつ前の時刻2の状態、つまり誰もがSuspiciousではなく単純に属性情報だけを共有している状態を表現していました。しかし、時刻4では3つのノードのうち、1つが黒いSuspiciousなノードに変わっています。図ではSuspicious なノードをFraudと記載しています。ですので、時刻02の状態、属性情報を共有している中で、誰か1人が既にFraudだとわかったことを表現しています。

先ほどお伝えしたように、時刻1・2は別々に存在しているわけではなく、時刻が進む中で変わっていく状態を表しています。

時刻4のスナップショットを見ると、右のノードがFraudだとわかったので、それに合った属性情報を多く共有している左の2つのアカウントを、「もしかしたらSuspiciousなのではないか」と言えるかもしれません。

時刻4をもって不正アカウントが判明したという事実を活用すると、Fraudとわかっているアカウントと新しく入ってきたアカウントの類似度が高く、属性情報を多く共有している場合は、その時点で怪しいと判定できると考えています。それを表現しているのが、時刻5です。右側に新しいノードが生成され、その属性情報をFraudとわかっている黒いノードと共有しているので、新しいアカウントはその時点でSuspiciousだと考えられます。

もちろんこれは属性情報の内容やつながり方を正確に細かくケース分解しないとわからないのですが、今は抽象的には、何か属性情報は共有しているので怪しいんじゃないかと言えます。

このように、取引の関係性を使った特定の位置での発生度合いを見ることや、属性情報を使って既にSuspiciousとわかっているアカウントとどのくらいの類似があるかを見ることを、グラフ理論の事例として紹介しました。

リアルタイム不正検知システムとの連携

ここまでは、抽象的な理論寄りの話でした。類似性を活かしてSuspiciousなアカウントを見つけてデータ分析をしているというお話をしましたが、ただ分析するだけでは不正の対策になりません。

実際にはMLチームで安定したSuspiciousなアカウントの判定の結果をリアルタイムで検証しているマイクロサービスに連携し、不正を検知しています。Suspiciousと判定したものをデータとして別のチームに連携し、決済のタイミングや事後のモニタリングで活用するシステムアーキテクチャです。

参考資料
ゼロからメルペイのリアルタイム不正検知システムを作る話：https://engineering.mercari.com/blog/entry/20220419-14cfb92734/

Future Work

最後に Future Work として、これから取り組みたいテーマについてお話しします。

つながりを見いだせないと施策のカバレッジも増えません。グラフのように関係・対策でいうと、取引で属性情報を使ってもつながりがないと何も見えないことは、グラフを使っている範囲では見えません。

そこでどうしたらそのつながりを発見できるか、予測結果をどのように活用・解釈するかを考えています。これらに関する取り組みについて紹介します。

1つ目に、リンク予測（Link Prediction）というタスクがあります。

既にあるつながりから、まだノード同士のつながりがわからない状態で、その2つのノード間にリンクがあるかを予測するタスクです。

左側の図に、左と上に緑色のノードが2つあります。これらは具体的なつながりはありませんが、持っている属性情報などいろいろな情報を使うと、これらにはどのくらいリンクがあるのかを予測するようなタスクとして応用できればと考えています。

これを実現できると、既にSuspiciousな情報はいくつかたまっているので、それらのノードに対してつながりが予測できると、新しくできたアカウントもSuspiciousだと言えます。

実現するために大量のグラフのデータを解析したいので、グラフデータベースの活用も同時に検討しています。機械学習的なタスクになるので、一つ前にFeature Storeに関するセッションがありましたが、オンラインのStoreを構築中で、それも活用してFeature StoreにFraudにききそうなメールモデルを扱う特徴量をストックして、それらを活用する先としてLink Predictionを考えています。

引用：https://feast.dev/

二つ目は不正対策に限った話ではないのですが、 Link PredictionやML・機械学習を使ったモデルがいくつかあります。

従来の機械学習はブラックボックスになっているため予測結果が説明しにくかったのですが、なぜその予測値になったのかをなるべく説明しやすくしたいと考えています。

自分たちの機械学習モデルに対する理解を深め、分析者や機械学習エンジニアが自分たちの業務の改善のためにも、きちんと予測結果を解釈できるところも重視したいです。よって、昨今話題になっている機械学習のモデルの解釈性についても、手厚く取り組んでいきたいと思います。

今回はグラフ理論と不正対策についてお話ししました。ご清聴いただき、ありがとうございました。

引用：https://github.com/slundberg/shap