はじめに
- 出典: AAAI 2023
Enhanced Multi-Relationships Integration Graph Convolutional Network for Inferring Substitutable and Complementary Items という、AAAIに提出された論文を紹介します。
この論文は中国のMeituan Maicaiと呼ばれるオンラインスーパーマーケットの研究者が取り組んだ、商品推薦の論文です。
論文を選んだ動機
E-Commerceサイトの推薦では、ユーザーが見ている商品の代替商品だけでなく、一緒に買われる補完商品の推定も重要な分野です。ここで言う代替商品や補完商品とは、以下の通りです。
- 代替商品: ユーザーがほしい商品と交換・比較可能な商品であり、どちらか一方が購入される商品。例えば、ある食パンを探しているユーザーに対して、別ブランドの食パンが代替商品に該当します。
- 補完商品: ユーザーがほしい商品と一緒に買われる商品。例えば、ある食パンに対して一緒に食べる牛乳やジャムなどが該当します。
より具体的な例は以下に挙げています。
補完商品を推定する際は補完関係にある商品だけでなく、代替関係にある商品も活用することでより性能が向上することが考えられます。例えば、パンAとパンB が代替関係にあり、パンAとミルクAが補完関係にある場合は、パンBとミルクAも補完関係にあるだろうと推定できます（推移律）。このように、補完関係を推定するときに代替関係を活用することで性能が向上できそうです。
本論文ではこのアイデアに則り、代替関係と補完関係を同時に推定しつつ、それぞれの異なる関係の情報を活用する手法を提案しており、興味深かったため読みました。
どんなもの?
- 以下のようにユーザーが食パン(=query item)を見ているとき、その代替商品として別の味の食パンを推薦し、更にミルクなどの補完商品も同時に推定する問題設定を考えた論文。
- 本研究では、代替と補完それぞれの関係の相互作用をモデル化し、2段階の異種情報を統合するモジュールを提案。
- 従来の先行研究では、query itemに対する代替・補完それぞれで関係の強さ(=度合い)を考慮していなかったが、本研究では関係の強さも考慮したtriplet lossを導入。
- オフライン・オンラインともに提案手法の実験を行い、先行研究よりも性能が優れていることを把握した。
先行研究と比べてどこがすごい?
先行研究
代替・補完関係を推定するときに、異種情報(代替関係であれば補完関係)を使用する先行研究として以下が挙げられる。
-
DecGCN
- 本研究と同様に、代替・補完それぞれのグラフから相互情報を活用する手法。ある商品の埋め込みベクトルを作成するときに、代替関係の近傍と補完関係の近傍それぞれの情報をco-attention 機構を用いて統合する。
- DecGCN は商品が代替・補完それぞれの関係をともに持つ場合に有効であり、どちらか一方の関係しか持たないときは性能が限定的であることがわかっている。現実問題では、どちらか一方の関係しか持たないことはよくある。
異種情報を活用するかは関係なく、商品間の関係予測の先行研究は様々ある。しかし、ほとんどが関係予測を 0 or 1 の分類タスクとして定義していた。そのため、商品間の関係の強さは無視していた。例えば、パンとミルクの補完関係はランチョンミートよりも関係が強く、実際に購入ユーザー数は10.5倍も異なっていた。(パン, ミルク) と (パン, ランチョンミート) を同一の補完関係と扱ってしまうのは問題である。理想的には、補完関係の強さは (パン, ミルク) > (パン, ランチョンミート) のように、関係の強度に応じた関係予測をしたい。
先行研究よりも優れている点
本論文の手法は上記先行研究と比べて、以下の点が優れている。
- 商品が代替・補完どちらか一方の関係しか持たないときでも、上手く相互情報を活用できる。
- 0/1の関係予測ではなく、関係の強度まで考慮することができる。
技術や手法のキモはどこ?
提案手法 EMRIGCN は以下3つの部分で構成されている。
- BaseModel: PinSageを用いた代替関係と補完関係それぞれ独立したGNN
- Multi-Relationships Integration: 代替商品と補完商品それぞれの埋め込みベクトルを交差させる機構。Multi-Relationships Integrationは更に以下2つで構成されている
- Feature Integration: 代替と補完それぞれで共通の商品を初期ベクトルへマッピングする機構
- Structure Integration: 代替と補完それぞれで得たGNNの中間表現を交差させ、同種edgeの近傍と異種edgeの近傍からの情報を集約する機構
- Relationship Enhance: 関係強度を考慮したロスを導入することで、positiveの商品間の位置関係と関係強度とを一貫させることができる
提案手法の概要図は以下の通りである。補完グラフと代替グラフそれぞれのPinSageは(b)の上段の黄と下段の青に相当する。そして、初期ベクトルを作成している $f_f$ が Feature Integration, それぞれのPinSageのConv結果を統合するのが $f_s$ となっている。
BaseModel
提案手法ではベースに代替・補完それぞれで独立したGNNが存在する。GNNにはPinSageが採用されている。PinSageは近傍をサンプリングするGNNであり、近傍爆発によるメモリ枯渇や計算時間の削減を行う。以下では補完のベクトルを求めるPinSageの流れを示すが、代替についても同様である。
まず、商品の特徴量(titleやcategoryなど)をmultilayer-perceptron $f^c$ で変換する。
その後、サンプリングされた近傍 $\mathcal{N}_i^c$ から情報を集約する畳み込み層を適用する。ある層 $l$ における畳み込みは以下の通り。
agg関数はmax poolingかaverage poolingを示す。$\sigma$ はReLUなどの活性化関数を示し、$:$ はconcatenateを意味する。この畳み込み操作を繰り返し、最終的な埋込 $z_i^c$ を得る。
PinSageではmax-marginロスを採用しており、以下の通り。ここで、$s$ は与えられた2つの埋込ベクトルのscoreを表し、コサイン類似度や内積を意味する。このロスの意味としては、positive商品(node: $i$の近傍 = $z^c_{pos}$) は、negative商品 (近傍以外 = $z^c_{neg}$) よりもマージン $\Delta$ 以上大きいscoreを取るように埋め込みベクトルを作れということである。
Multi-Relationships Integration
BaseModelだけでは代替/補完で異種の情報を組み込むことができない。そこで、Multi-Relationships Integrationで異種情報を組み込む。Multi-Relationships Integrationは、入力特徴量段階で異種情報を入れるFeature Integration $f_f$ と、中間の畳み込み層で異種の構造情報を組み込むStructure Integration $f_s$ の2種類がある。
Feature Integration
入力特徴量では、商品をさまざまな観点から表現した特徴量が必要なため、代替/補完それぞれで別々の埋め込み表現を使うのではなく、1つの共有された変換器を作成する。具体的には後述するIntegration Function $f_f$ を使って入力特徴量を補完 $h_i^{c:0}$ と $h_i^{s:0}$ に変換する。ここで変換器自体は代替と補完で同一だが、得られる特徴量は異なる点に注意。
Structure Integration
中間層などのより高次な段階では、補完/代替それぞれで異種の構造情報を取り入れるようにする。具体的には、以下のように近傍の情報を同一種のみではなく、異種の近傍情報も活用する。以下では、あるnode $i$ の補完と代替の近傍情報を集約した埋め込みベクトル $h_i^{c:l}, h_i^{s:l}$ は、式(6)のようにnode $i$ の同種の近傍と異種の近傍それぞれを集約してconcatしたベクトル $\hat{h}_i^{l}$ を用いて表現される。この近傍集約ベクトルを $f_s$ という変換器にいれ、最終的な集約ベクトルを獲得する。 $f_s$ は後述の通り。
代替と補完でベクトル空間の意味合いが異なるので、何も考えずに同一に扱うのは違和感がありますが、なぜかこれで上手くいっています。
最終的に得た近傍集約ベクトル $\hat{h}_i^{c:l}, \hat{h}_i^{s:l}$ は、それぞれ独立したPinSageの式(3) に入力され、node $i$ のベクトル $h_i^{c:l-1}$ を計算する。
Integration Function
Feature Integration, Structure Integrationそれぞれで使用した変換器 $f_f, f_s$ は自動的に補完/代替それぞれで必要な表現を学習してほしい。そこで、MMOEという先行研究に基づいて、補完/代替で共通の複数のexpert networkと、個別でgating関数 $g_c, g_s$ を用いたネットワークを使用する。
具体的には、Feature Integraion $f_f$ については、補完/代替で共通の $n_f$ 個のexpert と呼ばれるMLP $f_{f}$ と、補完/代替それぞれ別々のgating関数 $g_{f}^c, g^s_{f}$ を用いて以下のように表現される。ここで、$f_{f:j}$ はj番目のexpertを $g_{f:j}^{c}, g_{f:j}^{s}$ はそれぞれ補完・代替の j 番目のexpertの重要度を決めるgating scalar値である。
まず、expertで様々な観点の特徴量を抽出する。その後、補完・代替それぞれで各expertの重要度をgating関数で計算し、その重要度に応じた線形結合で表現する。gating関数は、入力特徴量を$n_f$次元ベクトルに線形変換し、softmaxをかけたベクトルを作成する。そして各要素がexptertの重要度に対応している。
Attention機構を模倣した機構だと考えるとわかりやすいです
Structure Integration $f_s$ は上と同様。
Integration Functionは、異種のknowledgeを上手く変換することでモデルの性能を改善する。
やりたいことはなんとなく分かるのですが、あまり背景のモチベーションがなく、とりあえず交差させてみたら性能が上がったと感じています、、、
Relationship Enhance
多くの手法は関連があるなしの0/1の予測だが、関連している場合でもその関連強度が存在する。またその関連強度をモデル化することで後続のタスクの性能を改善することができる。
関連強度をモデル化するため、式4の通常のmax-marginロスに加えて、以下の補助ロスを導入する。以下は、ppositive商品の埋め込みベクトルについて、その関連強度に応じた位置関係になるようにするロスである。具体的には、あるpositve商品ペア pos1 $v_{pos_1}$とpos2 $v_{pos_2}$が与えられたときに、pos1とpos2の関連強度scoreが $r^c(v_i, v_{pos_1}) < r^c(v_i, v_{pos_2})$ である場合、つまりpos2のほうがpos2よりも商品 $i$ との関連が強い場合は pos2のscoreがpos1よりも $\Delta'$ 大きいように設定する。ここで、$\Delta'$ は関連強度の差に応じたマージンである。下記は補完に対する補助ロスだが、同様に代替関係に対する補助ロスも計算する
論文では、関連強度を測る基準 $r^c$ は共起確率としていました。また関連強度差に応じたマージンを決める $\gamma$ はハイパーパラメータです。このハイパーパラメータの調整は職人芸になりそうです。
代替・補完それぞれのPinSageは上記の補助ロスと式(4)のposとnegのmax-marginロスを線形結合した、以下のロスを最小化する。以下は補完のロスだが、代替も同様に計算する。
$$
\mathcal{L}\left(z_i^c\right)=(1-\alpha) \mathcal{L}_{\text {main }}\left(z_i^c\right)+\alpha \mathcal{L}^{\prime}\left(z_i^c\right)
$$
最終的には、補完と代替のロスを組み合わせた以下のロスを計算し、代替・補完それぞれのPinSageを同時に学習する。
$$
\mathcal{L}=\frac{1}{|\mathcal{V}|} \sum_{i=1}^{|\mathcal{V}|}\left(\mathcal{L}\left(z_i^c\right)+\mathcal{L}\left(z_i^s\right)\right)
$$
どうやって有効だと検証した?
以下2つの方法でモデルの有効性を検証した。
- Offline Experiment
- 以下2つのデータセットにおいて先行研究との性能を比較し、提案手法 EMRIGCN が最も性能が良いことを把握した。
- Amazon datasets
- 本論文の著者が所属している会社が運営しているMeituan Maicaiという中国のオンラインスーパーマーケットサイトで収集したログをもとに作成したデータセット
- また、Cold-Start問題に着目した実験とAblation Studyを実施した。
- 以下2つのデータセットにおいて先行研究との性能を比較し、提案手法 EMRIGCN が最も性能が良いことを把握した。
- Online Experiment
- 実際にMeituan Maicaiに提案手法をだし、ABテストで性能を検証し、売上・利益ともに有意に改善したことを確認
Offline Experiment
データセット
データセットは以下2つ
- Amazon datasets
- 使用したのは、Beauty, Electronics, Cellphones と Clothing カテゴリのデータセット
- “also-viewed” と “also-bought” というラベルがついた関係をそれぞれ代替・補完関係とみなしてグラフを作成
- 85%のedgeをランダムにサンプリングし、それらを学習データ、残り15%をテストデータとした
- 本論文の著者が所属している会社が運営しているMeituan Maicaiという中国のオンラインスーパーマーケットサイトで収集したログをもとに作成したデータセット
- 6ヶ月のサイトのログを学習データ、その後1ヶ月のログをテストデータとする
- 検索結果に一緒に出てきた商品ペアを代替関係、一緒に購入された商品ペアを補完関係とする
上記データセットの統計値は以下の通り
商品数であるTotal itemはかなり少なく、最も多くても10万程度です。通常のECサイトを考えると商品数が数十から数百万のオーダーで他の先行研究と比較しても少ないです。
比較手法
比較先行手法は以下の4つです。
- LVA
- Linked Variational AutoEncoders for Inferring Substitutable and Supplementary Items WSDM2019
- コンテンツ情報をもとにVariational AutoEncoderで商品間の関係のための商品表現を学習する手法
- PinSage
- Graph Convolutional Neural Networks for Web-Scale Recommender Systems KDD 2018
- 広く使われるspatial GNNであり、重要な近傍をサンプリングすることで計算量を削減しつつ性能を維持できる手法。今回の実験では、代替と補完それぞれ別のPinSageを学習させた
- R-GCN
- Modeling Relational Data with Graph Convolutional Networks 2017
- 補完・代替で単位の共通の埋め込みベクトルを持つGNN手法
- DecGCN
- Decoupled Graph Convolution Network for Inferring Substitutable and Complementary Items CIKM2020
- 提案手法と同じく代替・補完の異種の情報を活用したGNN手法。中間層で異種の中間表現を活用するときにAttention機構を導入し、最終的な埋込ベクトルを作成するときも代替と補完それぞれの最終出力のを混ぜ合わせる Knowledge transfer機構を持つ。
先行研究を各機能ごとの有り無し表にすると以下の通りになる。
| 手法名 | テキストなどの数値情報以外の使用 | グラフ構造の使用 | 代替・補完の両方の情報を活用 | 代替と補完で別々の埋め込みベクトルを持つ |
|---|---|---|---|---|
| LVA | ✅ | ❌ | ❌ | ❌ |
| PinSage | ✅ | ✅ | ❌ | ❌ |
| R-GCN | ✅ | ✅ | ✅ | ❌ |
| DecGCN | ✅ | ✅ | ✅ | ✅ |
| EMRIGCN | ✅ | ✅ | ✅ | ✅ |
実装詳細
- GCN系のモデルはすべて2層であり、各層で10個の近傍サンプリングをおこなった
- 提案手法のハイパーパラメータは以下の通り
- 出力層の次元数は $d = 64$
- pos, negaのマージンは $\Delta=1$
- positiveラベルの関係強度差に対するscale値は $\gamma = 0.02$
- pos, negaのロスと関係強度のロスの線形結合の重みは $\alpha = 0.2$
提案手法との性能差
各データセットにおける提案手法と先行研究の性能差は以下の通り。
- 全体的に提案手法EMRIGCNが最も性能が良い
- 代替関係と補完関係の異種情報を組み込むモデル R-GCN/EMRIGCNの性能がPinSageよりも良いことが多い。よって、単一の情報よりも異種情報を活用することは価値があると分かった。ただし、異種情報を組み込むDecGCNの性能は低い。これは後述の通りエッジが片方しかない状態では性能が悪くなることが主な要因
- R-GCNは、ElectronicsとCellphoneの性能が悪いが、これは補完と代替それぞれの近傍数が不均衡なことが原因。実際Electronicsにおいて補完と代替それぞれの近傍数は31と12であった。R-GCNは各商品について単一の共通ベクトルで補完と代替の関係を表すが、近傍数が不均衡の場合は性能が悪くなる。
- LVAのようにグラフ構造情報を活用せずテキスト情報だけの場合は、one-hop先の関係しか学習しないため、十分な性能がでない
Cold-Startに関する実験
提案手法のロバストネスを検証するため、cold-start商品に関する性能を確認した。cold-start商品は、補完もしくは代替のエッジが4つよりすくない商品を指す。それらの商品に対してのテストデータの性能結果は以下の通り。
提案手法 EMRIGCNは他の手法と比べて有意に改善している。DecGCNはnodeが補完と代替どちらのエッジも持っている場合に上手く機能するが、どちらか一方しかない場合は異種情報を組み込むattention機構やknowledge transfer機構が上手く動作しない。具体的には、代替補完どちらかが欠けることがatttentionやknowledge transferでノイズとなってしまう。逆に各商品のエッジの数が増えると性能が向上する。この実験結果から提案手法は性能もよく、ロバストであることが分かった。
DecGCNが代替補完どちらかが欠けるとnoiseが入り性能が悪化するとありますが、なぜnoiseが入るのかはよく分かっていません。DecGCNの論文を読みましたが、こちらの手法とほぼ同じ構成でした。さらに、異種情報を組み込むモジュールはDecGCNのほうがより丁寧にモデリングされている印象でした。
Ablation Study
提案手法の3つのコンポーネント, feature integration module, structure integration module, relationship enhance module それぞれがどの程度性能に寄与しているかを調査するためのAblation Studyを実施した。具体的には以下の3つのモデルを提案手法とPinSageそれぞれと比較した。
- EMRIGCN-FI: 提案手法EMRIGCNからfeature integration moduleを除いたもの
- EMRIGCN-SI: 提案手法からstructure integration moduleを除いたもの
- EMRIGCN-RE: 提案手法からRelationship Enhance module (関係強度を考慮したロス)を除いたもの
結果は以下の通り。 - 全コンポーネントをもつEMRIGCNが最も性能が良いため、全コンポーネントで意味があり、異種との相互作用をモデルに組み込むことおは有益と結論づけられる。
- コンポーネントの中で最も寄与しているのはFeature Integration。Feature Integrationは入力特徴量を作成するモジュールのため、モデルの全般に影響する。よって、Feature Integrationが最も寄与しているのだろうと考えた。
- 今までは関係のありなしの1/0のラベルだったが、それとは別に関係の強度（共起確率）をラベルにしたndcgを見たところ、EMRIGCNはEMRIGCN-REよりも性能が高かった。そのため、Relationship Enhance moduleを入れて関係強度を考慮することで、関係強度の順序に相関があるようにscore付けできている
Online A/B Test
オンラインでの効果を測るため、EMRIGCNを様々な下流の推薦タスクに使用し、実際のオンラインスーパーマーケット Meituan Maicai のサイトに推薦データを表示した。具体的には以下の2つのタスクで評価をおこなった
- Retrieval Stage: EMRIGCNで作成した各商品の補完と代替のベクトルをANNにインデックスしたシステムをdeploy。ユーザーの行動履歴に基づきANNから推薦候補商品を取得。取得した候補商品を他のソースから取得した候補商品とマージし、Ranking Stageでリランキングする
- Ranking Stage: ユーザーの直近の行動に応じて候補商品をリランキングする部分。Meituan Maicai ではDIN と呼ばれるモデルを使用してリランキングしている。このモデルに入力する商品ベクトルとして、EMRIGCNで作成した代替と補完の埋め込みベクトルを使用した。
論文では明示的に書いていませんが、以下の通りだと思います
- Retrieval Stage（リランキングするRanking StageはAとBで同一）
- A: EMRIGCNで作成した候補商品以外を候補商品に用いる
- B: EMRIGCNで作成した候補商品も候補商品に加える
- Ranking Stage （候補商品はAとBで同一）
- A: DINへ入力するベクトルは、学習時に構築したItem-to-Vecを使用。Item-to-Vecは学習時はランダムに初期化したパラメータだったもの
- B: DINへ入力するベクトルはEMRIGCNで作成した代替と補完の埋め込みベクトル
実験結果は以下の通り。VBRはVisit Buy Rateといわゆる購買CVRであり、RPMはRevenue Per Thousand Impressionsであり、売上を表している。それぞれの%はAに対するBのリフトである。これらのリフトはすべて統計的に有意であり、提案手法EMRIGCN はビジネス売上の成長に大きく貢献したとみなせる。
議論はある?
- 補完関係を推定するときに代替関係を用いるのは確かに筋が良さそう。しかし、モデリング方法はかなりシンプル。式6で集約ベクトルを作成するときに、代替と補完それぞれをconcatしているが、代替と補完で別のベクトル空間にあるものを混ぜこんで良いのかが疑問。
- 関係強度を考慮したロスはそこまで難しくないため簡単に試せそうだが、関係強度の定義は職人芸になりそう。
- また、DecGCNがなぜこんなにも性能が悪いのかも納得できていない。DecGCNの論文でもAmazonデータセットで実験しており、そちらではここまで性能が悪い報告はなかった。本論文で説明があった、代替補完どちらかが欠けるとnoiseが入り性能が悪化するという点も納得できていない。
次読むべき論文は?
-
BLADE: Biased neighborhood sampling based graph neural network for directed graphs - Amazon Science
- asymmetricをロスに組み込むことで性能が改善したという手法
- 上記論文を紹介したAmazonのテックブログ: Biased graph sampling for better related-product recommendation - Amazon Science
- おそらく以下の論文をブラッシュアップしたものがBLADE。論文名は異なるが、著者が同じで公開日が早い。しかし、以下の論文のほうが補完商品推薦に専念していそう
まとめ
- EMRIGCNと呼ばれる代替・補完それぞれに対応できる商品推薦の論文を紹介しました。
- EMRIGCNでは、代替/補完それぞれの関係を異種の関係情報を活用することで性能を上げることができました。この手法では以下3つのモジュールから構成されています。
- BaseModel: PinSageを用いた代替関係と補完関係それぞれ独立したGNN
- Multi-Relationships Integration: 代替商品と補完商品それぞれの埋め込みベクトルを交差させる機構。Multi-Relationships Integrationは更に以下2つで構成されている
- Feature Integration: 代替と補完それぞれで共通の商品を初期ベクトルへマッピングする機構
- Structure Integration: 代替と補完それぞれで得たGNNの中間表現を交差させ、同種edgeの近傍と異種edgeの近傍からの情報を集約する機構
- Relationship Enhance: 関係強度を考慮したロスを導入することで、positiveの商品間の位置関係と関係強度とを一貫させることができる
- 本論文ではオフライン実験だけでなく、A/Bテストなど様々な観点からEMRIGCNを評価しており、どの観点からでもEMRIGCNが既存手法よりも優れていることが分かりました。