f:id:kur0cky:20201023211747j:plain

こんにちは． DSOC 研究開発部の黒木裕鷹です．夏の訪れを感じつつある最近ですが，ランニングをはじめました．形から入ろうと思い，かっちょいいシューズとウェアを揃えたのですが，なんとか1週間は続いており気分が良いです．まだまだ2, 30分走るだけでバテバテになってしまいますが，いずれは健康大魔神になろうと思っています．

さて，この連載では，自分の勉強・復習も兼ねて，ネットワークデータにまつわる（統計）解析を気の向くままに紹介しています．前回の記事では，グラフラプラシアン・グラフフーリエ変換について簡単におさらいしました．あまり理論やモデルの紹介ばかりが続いても面白くないので，今回の記事ではビジネス応用の事例紹介をしたいと思います．

具体的には，Uber における GNN の適用事例を2つほど取り上げることにしました．私たちの生活にもすっかり浸透した Uber や UberEats ですが，その内側にいるデータサイエンティストたちの取り組みを知れば，配達された料理をさらに美味しく感じることができるでしょう．元の記事より分かりやすく紹介するつもりですので，どうぞお付き合いください．

↓元記事↓

Food Discovery with Uber Eats: Using Graph Learning to Power Recommendations (Jain et al., 2019)
Fraud Detection: Using Relational Graph Learning to Detect Collusion (Hu et al, 2021)

Uber AI と対外発信

他の名だたるテックジャイアントと同様，Uber にもデータサイエンスの研究開発組織があり，その名も "Uber AI" というそうです． Uber AI は，機械学習やデータ分析をプロダクトに活かすだけでなく，数多くの研究成果を公開しています．ワーキングペーパーを含む論文はこちらにまとめられているようです．また，よりカジュアルなブログ記事が "Uber Engineering" というオウンドメディアで公開されています． Uber Engineering には，論文として出版されていない事例の紹介も数多く存在し，研究活動の層の厚さが覗えます．

今回する2つの事例も，論文としてはまとめられていないカジュアルなものです．正直，学会発表してしまえば良いのに...と感じずにはいられない内容の濃さでした．この記事を通して興味を持ったら，他の記事も是非読んでみると良いかもしれません（謎の宣伝）．

事例1：GraphSAGE による node embedding を用いたレコメンドエンジンの改善

一つ目は，みんな大好き Uber Eats に関する事例です．特に首都圏に住んでいる人は，いざデリバリーを頼もうと思い立っても，レストランや料理の多さに悩んでしまいますよね．筆者は，自分が何が食べたいのかハッキリしないことすらあります．そんなとき，パーソナライズされた「おすすめリスト」がトップに表示されていれば，気分に合ったものを簡単に探すことができるはずです．

この事例では，ユーザとレストラン・料理をネットワークとして扱い，GNN をレコメンドに活かす試みが紹介されています．より具体的には，ユーザとレストラン・料理を同じ空間でベクトルとして表現し，そのコサイン類似度を後段の ML モデルで特徴量として利用しています．ユーザとレストラン，ユーザと料理間のコサイン類似度をそれぞれ求め，後段の ML モデルの特徴量として使用する試みです．表現ベクトルには，GraphSAGE フィルタ (Hamilton et al., 2018)を使ったネットワークを学習し，その中間層の出力を得ています．（アーキテクチャ全体については記述がありませんでした．）

結果としては，オフラインテスト（学習データ4ヶ月，テストデータ10日間）で Precision@k や NDCG, AUC などが大幅に改善したほか，オンラインでの A/B テストにおいてもエンゲージメントや CTR で圧勝したそうです．また，次図の引用のように，後段モデルでの重要度はグラフ由来の特徴量が1番に来ていたようです．ここから，注文履歴からネットワークを作成し特徴抽出する有用性が覗えます．

ここまでを見ると何も面白くなさそうですが，フードデリバリーというドメインの特性上，いくつか独特な困難さが存在していそうでした．たとえば，次のようなものです．ここからは，これらの課題に対してどのような対策が取られたかを，より詳細と工夫を通して紹介していきます．

「レストラン」か「料理」か，どちらがおすすめされるのが適切かは場合により異なる（多くの場合に比べて店の重要さが大きい）
配達圏内の店舗のみ考慮する必要がある
ユーザやレストラン・料理の数が非常に多い
ユーザやレストラン・料理が頻繁に入れ替わる
ユーザ，レストラン，料理はそれぞれ特徴量の数が異なる
同一ユーザによる同一の注文が複数回に及ぶことがあり，これを考慮したい

GraphSAGE フィルタ

この事例で使用される GraphSAGE フィルタ (Hamilton et al, 2017)は，ランダムに選択された近傍ノードの特徴量を集約し，再帰させるような操作をもちます．集約にはいくつかの種類が提案されていますが，その特徴としては以下のようなものがあります．

サンプリングと集約に付随する係数を学習するため，ノードの出現や消失といった変化に対応できる
ランダムサンプリングによって計算量を抑えることができる

これらの性質は，前節で取り上げた 3, 4 番目の課題に対して有効そうです．実際，DeepWalk (Perozzi et al., 2014) をはじめとする word2vec 系の手法はグラフの変化に対応させるのが非現実的であるように思えます．

GraphSAGE フィルタをはじめとした GNN フィルタについては過去の記事でも扱っているので是非ご覧ください．

取り組み概要と様々な工夫

表現ベクトルの獲得のより詳細なステップを以下に示します．

注文された数をエッジにもつ二部グラフ（ユーザ-レストラン），（ユーザ-料理）をそれぞれ作成する（グラフはそれぞれ都市ごとに，Cypherによるハンドリングで作成する）
GraphSAGE フィルタを持つネットワークで工夫したヒンジロスを最小化．
ノードの種類による次元数を合わせるため，アーキテクチャの一層目は自身への射影&活性化層
中間層で得られる表現ベクトルに基づき，ユーザ-レストラン，ユーザ-料理間のコサイン類似度をそれぞれ得る
コサイン類似度を後段 ML モデルの特徴量として使用する

手順 1 はそのまま課題 1, 2 に対して有効そうですね．また，シンプルではありますが手順 3 が課題 5 の対策になっています．最後に課題 6 の対策についてですが，これが結構面白かったので重点的に紹介します．

同一レストランや料理の注文が複数回にわたること，つまり "リピート" は，ユーザの嗜好を表す強いシグナルになっているでしょう．しかし，通常の GraphSAGE やヒンジロスではこれを考慮することができません．

通常のヒンジロス $L$ は次式で表されます．ここで， $z$ は最終層への入力，ノードのペア $(u, v)$ は注文があった正例，ペア $(u, z)$ はランダムに選ばれた負例であるとします． $\Delta$ はマージンです．

$\displaystyle L = \sum _ {(u, v) \in \mathcal E} \max (0, -z _ u z _ v + z _ u z _ n + \Delta).$

このままでは，たった1度の注文とリピートを区別して考えることができません．そこでこの事例では，次図の引用のようにヒンジロスに少し変更を加えています．

正例ペアと負例ペアのマージンを考える第1項だけでなく，強い正例ペアと弱い正例ペアのマージンを考える第2項が追加されています．この変更により，正例の中でも強いものを学習するようになりそうです．

補足：GraphSAGE の集計やサンプリングでも注文回数を考慮するようにしているようです．

レコメンドにおけるグラフデータの利用

レコメンドシステムは，SNS や EC，音楽・動画のストリーミングなど，多くのオンラインサービスで活用されている技術です．今や私たちのほとんどが，何らかのレコメンドシステムの恩恵を毎日のように受けているはずです．実は，GNN をはじめとするグラフ学習のレコメンドへの適用は，今回の事例に限らずかなり研究されているようです．この事例の最後に，調べた範囲でその流れを紹介しようと思います．

最も有名かつ古くから活用されてきたレコメンドの技術は，おそらく協調フィルタリング (collaborative filtering) でしょう．協調フィルタリングの置いている大きな仮定そして主張は，「過去の行動が類似しているユーザは類似した嗜好をもっているはずだ」ということです．ユーザとアイテムの表現ベクトルを考え，過去の選択履歴を再構築するようにモデリング・最適化します．

ここで，選択履歴のインタラクションは必ずユーザ・アイテム間で行われるため，その履歴を二部グラフとして扱うの自然なことと言えるでしょう．エッジはユーザがアイテムを選択したことを表す重み無しのバイナリでも良いですし，レビューなどの評価値があればその重みでも良いです．

一度選択履歴を二部グラフとして表現してしまえば，グラフ学習の技術を直接適用できることになります． GNN を活用した協調フィルタリングがいくつかあるので，それを紹介しようと思います．

一般的に，協調フィルタリングはエンコーダ・デコーダモデルとみなすことができます．各ユーザ・アイテムをエンコードし，その表現を用いてもとの選択行動をデコード（再構築）します．デコード部分は，二部グラフのエッジが重みなしであれば分類医問題として，重みありであれば回帰問題として解くことができます．では，エンコード部分は GNN を用いてどのように考えることができるでしょうか．まさに今回の UberEats の事例のように，近傍ノードの情報を利用して更新していく畳み込みが一般的であるようです (Berg et al., 2017; Wang et al., 2019)． GNN であればユーザ・アイテムの特徴量をシグナルとして扱えるため，コールドスタート問題に対してもある程度有効そうです．

事例2：R-GCN による不正ユーザ検知の改善

二つ目は，登録するだけで誰でもドライバーになれるライドサービス，Uber での事例です．こちらは2021年5月に公開されたばかりのものであり，もしかしたらこれから学会発表や論文になることがあるかもしれません．

Uber のグラフと聞くと交通ネットワークのイメージが強いかもしれませんが，この事例ではユーザのネットワークを扱っています．ただし，Uber というサービスにおけるユーザは乗る人（ライダー）だけではなく，ドライバーもまたユーザであることに注意が必要です．つまり，グラフのノードにはライダーとドライバーの2種類が存在し，エッジには「乗車」「友達紹介」「情報共有」など様々なものが存在することになります．そのイメージを次図に引用します．

補足：この事例は（まだ？）プロダクションでは利用されていないようです．

課題：Uber の不正利用

Uber が普及し巨大なサービスになるにつれ，犯罪に利用しようという悪質なユーザが目立ってきているようです．たとえば，ドライバーとライダーが結託し，盗難したクレジットカードを使って偽の旅程を組むということです．

ユーザの不正スコアや信用度を推定する機械学習モデルは既に存在するようですが，GNN を用いるモチベーションとしては，「不正を働くようなユーザはクラスター化していることが多い」という知見を積極的に活用したいということです．

R-GCN

冒頭で触れたように，Uber のユーザネットワークは，複数種類のエッジが存在します．「乗車」や「友達紹介」のメカニズムは明らかに異なり，不正検知への利用でも扱いを変えた方が良さそうなことが想定されます．

エッジにいくつかの種類がある場合の GCN フィルタとして代表的なものには， R-GCN フィルタ (Relational-GCN; Schlichtkrull et al., 2018) があり，この事例でも R-GCN フィルタが使用されています．

R-GCN フィルタによる処理を次式に示します．ここで， $h _ i ^ {(l)}$ はノード $i$ に対応する $l$ 層目の出力で， $\sigma$ は活性化関数です．また， $W _ r$ は種類 $r$ のエッジに対応する重み行列であり， $W _ 0$ は自己ループに対応する重み行列です． $\mathcal N _ i ^ r$ は種類 $r$ のエッジでノード $i$ に接続されている近傍ノード集合です．

$\displaystyle h _ i ^ {(l+1)} = \sigma \left( \sum _ {r \in \mathcal R} \sum _ {j \in \mathcal N _ i ^ r} \frac{1}{c _ {i, r}} W _ r ^ {(l)} h _ j ^ {(l)} W _ 0 ^ {(l)} h _ i ^ {(l)} \right).$

少し小難しく見えるかもしれませんが，エッジの種類ごとにフィルタ係数を用意しているだけで，非常にシンプルな構造になっています．元論文 (Schlichtkrull et al., 2018) では，node classification や link prediction タスクに R-GCN を応用するための損失関数が整理されており，参考になると思います．

取り組み概要と結果

それでは，学習の概要と実験結果について紹介します．まずは，モデルの学習についてです．ここでも，アーキテクチャ全体については記述がありませんでした．

正解ラベル：ユーザーの支払いがある時間範囲でチャージバックされたかどうか．
損失関数：logloss
特徴量の次元合わせにはゼロパディングを利用．
得られた予測値は後段の ML モデル（信用スコアの推定）の特徴量として利用

続いて，オフライン実験についてです．こちらのモデルはプロダクトに乗っておらず，オンライン実験は行われていないようでした．

学習データ：4ヶ月間
テストデータ：6週間

結果として，false positive の増加を最小限に抑えつつ，precisionを15%向上させることができたそうです．単体では特徴量があまり得られない不正ユーザに対し，その周辺ユーザの情報が有用だったということでしょうか．また，算出された rider score と driver score の重要度は，後段の ML モデルで利用されている200の特徴のうち4番目と39番目だったそうです．相対的にも予測に寄与していそうなことが分かりますね．

おわりに

今回の記事では，GNN をビジネスの最前線で活用している例として，Uber の事例を2つ紹介しました．取り上げた事例はどちらも（まだ）論文になっているものではありませんが，非常に興味深く参考になる点も多かったです．個人的に Cypher はまだ使ったことがないので興味があります．

最後までご覧いただきありがとうございました．次回以降の内容はまだ未定ですが，なにか読みたいテーマがあればどしどしコメントください！！それでは，ごきげんよう．

参考文献

Berg, R. V. D., Kipf, T. N., & Welling, M. (2017). Graph convolutional matrix completion. arXiv:1706.02263.
Hamilton, W. L., Ying, R., & Leskovec, J. (2017). Inductive representation learning on large graphs. Proceedings of the 31st International Conference on Neural Information Processing Systems, 1025–1035.
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). Deepwalk: Online learning of social representations. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 701-710.
Schlichtkrull, M., Kipf, T. N., Bloem, P., Van Den Berg, R., Titov, I., & Welling, M. (2018). Modeling relational data with graph convolutional networks. European semantic web conference, 593–607.
Wang, X., He, X., Wang, M., Feng, F., & Chua, T. S. (2019, July). Neural graph collaborative filtering. the 42nd international ACM SIGIR conference on Research and development in Information Retrieval, 165–174.
Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., & Leskovec, J. (2018). Graph convolutional neural networks for web-scale recommender systems. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 974–983.
Jain, A., Liu, I., Sarda, A., & Molino, P. (2019). Food Discovery with Uber Eats: Using Graph Learning to Power Recommendations.
Hu, X., Yang, C., Murray, C., Sarda, A., Jain, A. & Molino, P. (2021). Fraud Detection: Using Relational Graph Learning to Detect Collusion.

buildersbox.corp-sansan.com

Sansan Tech Blog

Sansanのものづくりを支えるメンバーの技術やデザイン、プロダクトマネジメントの情報を発信

【ネットワークの統計解析】第8回事例紹介「Uber における GNN の活用」

目次