Innovation and Practice of Dynamic Network Representation Learning in the Field of Recommendation

はじめに

現在、node2vec、GCN、GraphSAGE、GAT などの Graph Embedding 手法の多くは静的グラフモデルを対象としており、グラフが変化しないことを前提としている。しかし現実には、関係グラフは時間とともに変化することが多い。たとえば、ユーザーの興味は、ある期間を経てワンピースからハイヒールへと徐々に移り変わる。関係グラフにおいて、前期はユーザーの近傍が主にワンピースであるのに対し、後期はハイヒールが近傍の中心となる。静的グラフのモデリング手法に従うと、ワンピースとハイヒールが同じグラフ上に存在することになる。関係エッジに時間情報を追加することは可能だが、それはウォークや集約を制御する重みとして機能するだけで、ユーザーの興味の変遷を時系列として明確にモデル化することはできない。

動的ネットワーク表現学習は動的グラフ埋め込みとも呼ばれ、現在のネットワークの構造情報だけでなく、ネットワークの時間的な変化も学習できる。Graph Embedding の有望な研究方向の一つとして注目されている。近年、DynamicTriad や DySAT などの動的ネットワーク表現学習に関連するアルゴリズムが数多く提案されている。ただし、現状では主に動的等質グラフを対象としている。DySAT と HAN のアルゴリズムに触発され、動的異種ネットワークにおける階層型アテンション機構に基づく動的グラフ表現アルゴリズム（DyHAN）を提案した。オフライン評価において、既存の手法を上回る性能を示している。

ビジネスへの実装においては、開発難易度とオンラインでの露出を考慮し、従来の GraphSAGE ベースの i2i に動的モデルを導入することで時系列情報をよりよく学習し、ビジネスで一定の成果を達成した。

イノベーションの探求

イノベーションの面では、ユーザーと商品の動的異種グラフに対して、階層型アテンション機構に基づく動的グラフ表現学習アルゴリズム（DyHAN、Dynamic Heterogeneous Graph Embedding using Hierarchical Attention の略）を提案した。

グラフの構築

ここでは主に自社データセットの構築情報について説明する。他のデータセットも同様である。ユーザーの行動履歴ログを使用してグラフを構築する。

ノードタイプ：ユーザーと商品の 2 種類。

エッジタイプ：クリック、問い合わせ（AB）、注文など。

タイムスライシング：1 日ごとのユーザー行動を 1 つのタイムスライスとする。10 日間のタイムスライスを学習に使用し、11 日目のタイムスライスを評価に使用する。

ノード情報：ノード ID（実験を容易にするためノード ID 特徴量を直接使用している。グラフに他の特徴量がある場合は追加可能）。

これにより構築されるグラフは、11 個のタイムスライス、2 種類のノードタイプ、3 種類のエッジタイプを持つ異種動的グラフである。あるタイムスライスにおいて、クリックタイプのエッジのみを参照すると、そのタイムスライスにおけるクリックタイプの部分グラフが得られる。

モデル

DyHAN のモデル構造は図 1 に示す通り、主に 3 層のアテンション機構から成る。ここでの 3 層の融合は、ノードレベル、エッジレベル、時系列レベルでの集約である。DyHAN ではすべての層にアテンション機構を使用しているが、実際にはこれら 3 つのモジュールは他の集約方法に置き換えることも可能だ。たとえば、ノードレベルの集約には GraphSAGE の平均法、平均プーリング、最大プーリングを使用でき、時系列レベルの集約には LSTM や GRU などの RNN ベースの手法を使用できる。

ノードレベルの集約は、各タイムスライス内の各エッジタイプの部分グラフにおいて、各ノードに自身と近傍ノードの情報を融合させる埋め込みを生成する。こうして融合されたベクトルは、そのエッジタイプにおけるノードのセマンティック情報を表現できる。Query はノード自身、Key は近傍ノード（自身を含む）である。

エッジレベルの集約は、各タイムスライスにおけるノードの各エッジタイプベクトルを集約するために使用される。特定のエッジタイプベクトルがそのノードに大きく寄与する場合がある。たとえば、注文のエッジタイプベクトルは取引された商品に対して大きな貢献をする。

時系列レベルの集約は、主に各タイムスライス上のノードベクトルを集約する。ここでは標準的なスケーリングドット積アテンションを使用する。M はマスク行列であり、ノードベクトルが過去のノードベクトルのみを参照できるようにする役割を持つ。

表現力を高めるため、各層の集約にマルチヘッド機構を使用できる。

損失関数には交差エントロピーを選択する。正例と負例は最後のタイムスライスでのみ選択する。

実験

レコメンデーションにおける定量的リコールは、2 つのノード間の類似度を計算して、ユーザーが潜在的に興味を持つ商品を予測する。ビジネスへの適合度を高めるため、エッジ予測を実験タスクとして選択した。ベースラインとして、DeepWalk、metapath2vec、GraphSAGE、GAT といった静的グラフの代表的アルゴリズム、および DynamicTriad、DySAT などの動的グラフアルゴリズムを選択した。2 つの公開データセットと自社データセットで実験を実施した。以下に実験結果を示す。

実践的な取り組み

ICBU 推薦エンジンの現行メカニズムではユーザーベクトル化の露出割合が低いため、動的グラフ表現のオンライン実装においては、まず i2i で試みることを優先した。すなわち、GraphSAGE i2i を基盤として、直接動的モデルを導入するアプローチである。

グラフの構築

各タイムスライスのグラフ構築は、従来の GraphSAGE i2i のパターンに従う。実装上の制約により、最後のタイムスライスのノードベクトルのみが転送される。したがって、商品のカバレッジを低下させないよう、各タイムスライスを 90 日間に設定し、タイムスライス間に適切なオーバーラップを設けている。

モデル

このモデルは、前述の DyHAN の簡略版となる。2 層構造で、第 1 層は GraphSAGE の集約機構により各タイムスライスのノードベクトルを計算し、第 2 層は前述のスケーリングドット積アテンションを使用した時系列レベルの集約を行う。最後のトレーニングは教師なし学習である。教師なし学習サンプルの選択を最適化し、損失関数としてトリプレットロスを使用している。

オフライン評価とオンライン効果

オフライン評価：セッション内の最初のアイテムをランダムにトリガーとして選択し、同じセッション内でクリックされた異なるアイテムのカバレッジ率を計算する。1 万サンプルを抽出した結果、i2i のカバレッジ増加率は 4.2%、dynamic_i2i のカバレッジ増加率は 10.9% であった。

オンライン効果：詳細ページのクロスストアレコメンデーションの導入時、L-AB コンバージョン率が 3.54% 上昇し、L-O コンバージョン率が 14.23% 上昇した。詳細ページ全体の変換では、D-AB コンバージョン率が 0.85% 上昇し、D-O コンバージョン率が 2.57% 上昇した。

まとめ

動的グラフ特性の研究において、異種動的グラフモデリング向けの DyHAN 手法を考案し、Alibaba International Station（ICBU）のレコメンデーション分野に動的グラフ特徴モデルを導入して、ビジネスで一定の成果を達成した。同時に、タイムスライスベースの動的グラフ表現は計算コストが比較的高いという課題も見つかった。各タイムスライスで静的グラフ表現モデルを実行する必要があるため、計算コストの削減が今後の研究方向の一つとなる。また、時間次元で時系列情報をよりよく統合する方法も、今後の研究方向である。