日本データベース学会和文論文誌
一般論文

Vol. 21-J, Article No. 3, 2023年 3月

量子モデルを利用した推薦システム

良い推薦システムが提供可能であることが示されている．

の提案

さ れ て い る． [5]で は， 嗜 好 行 列 が 低 ラ ン ク 近 似 可 能 と い う

最近では量子アルゴリズムを利用した推薦システムが提案
前 提 条 件 の 元， あ る ユ ー ザ ー𝑖 に 対 す る 価 値 が 高 い ア イ テ ム

和山弘1を𝑂 (poly(𝑘) polylog(𝑚𝑛)) の計算量で嗜好行列の特異ベクトル

杉山一成2をサンプリングを行う手法が提案されている． 𝑚 がユーザー数，𝑛がアイテム数， 𝑘 が𝑚 × 𝑛の嗜好行列のランクである．従来のコクリックなどユーザからの暗黙的なフィードバックを用いた推ンピュータを利用した場合，特異値分解は𝑂 (poly(𝑚𝑛)) の速度が薦システムにおいては，ユーザーとアイテムの間にインタラクシ

必要なため，指数関数的な高速化を実現している．一方，低ラン

ョンがあれば1を，なければ0を付け，隣接行列に基づいてモデ

ク近似を仮定すれば，従来のコンピュータを利用しても同程度のルが作成されることが多い．ここで，隣接行列とは，ユーザーと計算速度で特異ベクトルがサンプリング可能であることが示さアイテムを無向2部グラフとする対称行列である．しかしながら，れた [11]．さらに，Baiら [1]は，量子空間グラフ畳み込みニュー

隣接行列はすべて1か0かの二値で表現され，グラフの結びつきのラルネットワークというグラフ構造を持つ量子アルゴリズムを強さを表現することが出来ないという問題がある．その一方で，提案した．この研究では，これまで提案された畳み込み層のグラ

連続時間の量子ウォークの概念を用いると，グラフ上の情報の伝フ表現と，量子空間グラフ畳み込み層を統合してグラフを分類す

播をシュレディンガー方程式に従う形で表現することが可能である深層学習のアーキテクチャを提案している．その中で，量子版る．このようなモデルでは，古典的な隣接行列を用いた情報の伝

ランダムウォークである量子ウォークが提案されている [2]．ま播とは振る舞いが大きく異なることが予想される．そこで本研究

た，グラフ分類タスクを量子回路を用いて実行する研究も行わ

では，平均混合行列で量子ウォークを表現し，隣接行列に量子モ

れ，Zhangら [15]は，量子グラフ畳み込みニューラルネットワー

デルの考えを応用することにより精度の高い推薦システムを提案

クを提案している．
このように，近年グラフ構造や量子アルゴリズムなどを利用しする．

た推薦システムが提案され，活発に研究されている．

1 はじめに2 関連研究推薦システムで利用される手法の一つに協調フィルタリン

2.1 グラフ畳み込みネットワーク

グ [10]， [9]がある．協調フィルタリングはユーザーの購入やク

本節では，グラフ畳み込みネットワークを利用した最先端のモリックなどの暗黙的なフィードバックを元に生成されるユーザー

デルであるLightGCN [3]を中心に説明を行う．

とアイテムの嗜好行列を元に推薦を行う手法である．協調フィル

2.1.1 嗜好行列と隣接行列

タリングは，さらに(1)モデルベースの方法と(2)メモリベースの

協調フィルタリングではユーザーがアイテムに対してクリッ方法に分けられる． (1)モデルベースの方法は，行列分解 [7]など

クや購入などの暗黙的なフィードバックを受けた場合は1，そのにより，高次元のデータを低次元のデータとして表現し，特定の他は0とする嗜好行列(user-item interaction matrix)が利用される．

ユーザーと親和性の高いアイテムを抽出する方法である．ユーザ

嗜好行列は以下のように定義される．

ーとアイテムを学習可能なベクトルとして表現し，ユーザーとアイテムのインタラクションを二つのベクトルの内積で表現する．

Ru,i =(2)メモリベースの方法は，同じような行動履歴を持つユーザー

1,0,

if (𝑢, 𝑖) interaction is observed
otherwiseは同じような嗜好を持つという仮定の元に，コサイン類似度など

2.1.2 隣接行列を利用しユーザーの近傍探索を行い，似たようなユーザーを抽出

隣接行列は嗜好行列を用いて以下のように定義される．

する手法である．
ユーザーやアイテムの隣接情報を利用する手法として， GCNA=[6]， NGCF [13]， LightGCN [3]などのグラフ畳み込みネットワ

0
R𝑇

R
0



ーク（GCN）が提案され，協調フィルタリングを利用した最先端の手法として盛んに研究されている．ユーザーとアイテムの隣

行列の大きさはユーザー数を𝑚 ，アイテム数を𝑛とすると，(𝑚+接行列を利用して，ユーザー，アイテムそれぞれの初期ベクトル𝑛) × (𝑚 + 𝑛) である．グラフ畳み込みネットワークではこの形のを隣接行列に従い伝播させるとことでそれぞれのベクトルを改善

隣接行列では計算が収束しないことが知られており，正規化が行する手法である． LightGCN [3]では，従来のグラフ畳み込みネ

われる．各ユーザーのinteraction数の合計を対角成分に持つ正方ットワークを大幅に簡素化し，計算量を大幅に削減しても精度の行列DU = Diag(R · 1) と，各アイテムのinteraction数の合計を対角成分に持つ正方行列 DI = Diag 1𝑇 · R を利用して，正規化嗜

1 学生会員好行列は以下のように定義される．

京都大学大学院情報学研究科

wayama.hiroshi.84h@st.kyoto-u.ac.jp
2 正会員

京都大学大学院情報学研究科

1

1

R̂ = DU − 2 RDI − 2

kaz.sugiyama@i.kyoto-u.ac.jp

1

日本データベース学会和文論文誌
一般論文

Vol. 21-J, Article No. 3, 2023年 3月

この正規化嗜好行列を利用して正規化隣接行列が定義される．


Â =

0
R̂T

R̂
0


(1)

図1に，ユーザーとアイテムの2 部グラフから，正規化隣接行列を作成する図を示す．

2.1.3

LightGCN

LightGCN [3]では，グラフのノードが持つ情報を正規化嗜好
行列に従って伝播させる．最初にユーザーとアイテムをベクトルで表現し，それに対して隣接行列を作用させることで情報の伝播
図1を実現している．ユーザー 𝑘 の潜在ベクトルをeuk ，アイテム 𝑗 の2部グラフと正規化嗜好行列と隣接行列の例．ユーザーがアイテムに対してクリックや購入などのフィードバックを行う

潜在ベクトルをeij とすると，E (0) を以下のように定義できる．

とグラフ上で頂点同士が辺で結ばれる． R̂とÂは正規化された嗜好行列と隣接行列である．

eu© .1 ª
­ . ®
­ . ®
­
®
­ e ®
(0)
E = ­ um ®
­ ei1 ®
­ . ®
­ . ®
­ . ®
« ein ¬

2.3.1 スペクトル分解

M̂(𝑡) を具体的に計算するためにÂのスペクトル分解を利用す
る． Âはエルミート行列であり，スペクトル分解が可能である．
すなわち，以下のように書くことができる．

この初期状態E (0) は，正規化隣接行列に従って，グラフ上で隣Â =接する頂点に伝播される．

∑︁

𝜆𝑟 |𝑟⟩⟨𝑟 |(4)𝑟|𝑟⟩ はÂの固有ベクトルあり， 𝜆𝑟 は |𝑟⟩ に対する固有値である．

E (𝑛+1) = ÂE (𝑛)Âはエルミート行列なので，各固有ベクトルは直交し， ⟨𝑖| 𝑗⟩ =2.2 量子ウォーク

𝛿𝑖 𝑗 が成立する．
式(4)を式(2)に代入して計算を進めると， T̂(𝑡) を簡単に表現す

本節では，量子ウォークの簡単な説明を行う．量子ウォークはることができる．ここで， ⟨𝑖| 𝑗⟩ = 𝛿𝑖 𝑗 を利用した．

ランダムウォークの量子版として研究されている．量子ウォーク
は物理学で微視的な粒子の状態を記述するシュレディンガー方程𝑑|𝜓⟩ = 𝐻|𝜓⟩ に従い時間発展する．ハミルトニアン𝐻 が時
𝑑𝑡
𝐻間に依存しない場合， |𝜓(𝑡)⟩ = 𝑒 𝑖ℏ 𝑡 |𝜓(0)⟩ と表現することができT̂(𝑡) =式 𝑖ℏ∑︁

exp (𝑖𝜆𝑟 𝑡) |𝑟⟩⟨𝑟 |

(5)

𝑟

2.3.2

る． |𝜓(0)⟩ は系の初期状態である．一般に，ハミルトニアン𝐻 は

量子ウォークによる隣接行列式(5)を式(3)に代入すると，遷移行列M̂を具体的に計算するこ𝐻

エルミート行列でありユニタリ行列ではないが，𝑈 = 𝑒 𝑖ℏ 𝑡 はユニとができる．本研究では， M̂の𝑡 = 1の行列を量子ウォークによタリ行列となり，この行列に従って系は時間発展する．

る隣接行列と考え，ÂQ と表現する．

[2]では，平均混合行列を用いて連続時間量子ウォークを表し，グラフ上の各頂点における時間平均的な量子状態の変化を論じてÂQ =いる．ここでは， [2]に従い，量子ウォークの定式化を行う．

∑︁|𝑟⟩⟨𝑟 | ◦2 + 2

𝑟

2.3 連続時間量子ウォーク∑︁cos (𝜆𝑟 − 𝜆 𝑠 ) |𝑟⟩⟨𝑠| ◦ |𝑟⟩⟨𝑠|

(6)

𝑟 <𝑠

ここで， |𝑟⟩⟨𝑟 | ◦2 は |𝑟⟩⟨𝑟 | ◦ |𝑟⟩⟨𝑟 | である．

正規化隣接行列Âをハミルトニアン𝐻 として考え，以下の行列

2.4 量子ウォークの利点を定義する．

古典的なランダムウォークはグラフ上の隣接する頂点をマルコフ過程に沿って時間発展するモデルである．量子ウォークはグラT̂(𝑡) := exp(𝑖𝑡 Â)(2)T̂(𝑡) とT̂(𝑡) の随伴行列 T̂† (𝑡) = T̂(−𝑡) の要素積を計算した行

フ上の頂点を遷移することは同じだが，ユニタリ行列に沿って時間発展する．また，式(1)を利用したグラフ上の畳み込みは高周波列をM̂(𝑡) と定義する．

M̂(𝑡) := T̂(𝑡) ◦ T̂(−𝑡)成分をカットするローパスフィルタの性質を持つ [14]．式(6)の第一項の最大固有値は1であり，式(1)と比較して効率的に高周波(3)成分をカットすることが可能である．グラフ上の高周波成分は，◦は要素毎の積（アダマール積）を表す． T̂(𝑡) がユニタリ行列

隣接するノード間の値の差が大きいということを意味し，推薦シなので，M̂(𝑡) の各行，各列における和は常に１になる．よって，

ステムにおいては悪い影響があると考えられる．このように，量M̂(𝑡) は確率行列として捉えることも可能である．そのように考子ウォークによる隣接行列(式(6))は従来の隣接行列(式(1))とは異えると， M̂(1) は，量子状態 |𝜓(𝑡)⟩ から |𝜓(𝑡 + 1)⟩ へと遷移させるなる性質を持ち，推薦システム全体に対しても良い影響を与える

遷移行列として定義することができる．

ことが期待される．

2

日本データベース学会和文論文誌
一般論文

Vol. 21-J, Article No. 3, 2023年 3月

(1)
e𝑐,𝑢
(1)
e𝑐,𝑖

!

(1)
e𝑞,𝑢
(1)
e𝑞,𝑖

!

!

= Â

(0)
e𝑐,𝑢
(0)
e𝑐,𝑖

!

= ÂQ

(0)
e𝑞,𝑢
(𝑢)
e𝑞,𝑖

最終的なユーザーとアイテムの潜在ベクトルは，それぞれの潜在ベクトルの和の平均として計算する．

図2 レイヤー数を1にしたモデル2のアーキテクチャ．

e𝑢 =3 提案手法
古典的な正規化隣接行列(式(1))と，量子ウォークに基づく量子𝐿
1 ∑︁  (𝑘 )(𝑘 )e𝑐,𝑢 + e𝑞,𝑢;𝐿 + 1 𝑘=0

e𝑖 =

𝐿

1 ∑︁  (𝑘 )(𝑘 )e𝑐,𝑖 + e𝑞,𝑖𝐿 + 1 𝑘=0

推薦スコアは，モデル1と同様に，式(7)を用いて計算する．

化隣接行列(式(6))の二つの隣接行列を利用した二つのモデルを提3.3 最適化

案する．

提案するモデルの最適化パラメータは初期潜在ベクトルだけで

3.1 モデル1

ある．損失関数として，グラフ畳み込みネットワークでよく利用

モデル1は単純に隣接行列として，式(6)を利用するモデルであされるBPR Loss (Bayesian Personalized Ranking loss) [8]を利用

る．初期化されたユーザーとアイテムの潜在ベクトルをE (𝑛+1) =する．ユーザー数を𝑚 ，N𝑢 をユーザー𝑢 とインタラクションがあÂQ E (𝑛) という漸化式にしがたって情報を伝播させる．

るアイテムの集合とすると，以下のように定義される．

(0)

例えば，ユーザーの初期潜在ベクトルをe𝑢 と，アイテムの初(0)期潜在ベクトルをe𝑖 とすると，次のレイヤー1におけるベクト

𝐿=−

(1)
(1)
ルe𝑢 とe𝑖 は，𝑚 ∑︁ ∑︁∑︁2
ln 𝜎 𝑟ˆ𝑢𝑖 − 𝑟ˆ𝑢 𝑗 + 𝜆 E (0)𝑢=1 𝑖 ∈ N𝑢 𝑗∉N𝑢

!

e𝑢(1)
e𝑖(1)

= ÂQ

(0)

e𝑢(0)
e𝑖(𝑢)

𝜆は過学習を防ぐための 𝐿 2 正則化係数である．

!

4 実験
4.1 データセット(0)と表現できる．ここで， e𝑢 とe𝑖 はすべてのユーザーとすべて

今 回 提 案 し た モ デ ル を 比 較 す る た め に， [13]や [3]で ものアイテムのベクトルを並べた行列を表す．

利 用 さ れ て い る， MovieLens 1M， Gowalla， Yelp， Amazon(0)© e𝑢1 ª­®
(0)e𝑢 = ­ ... ® ;­®
(0)« e𝑢 𝑚 ¬(0)

Booksの4つのデータセットを利用した． いずれのデータセッ© e𝑖1 ª®
­(0)e𝑖 = ­ ... ®
®
­(0)« e𝑖𝑛 ¬

トも一般的に公開されており，誰でも利用することが可能である． MovieLensは，ユーザーの映画のレビュー結果をまとめたデータセットである． Gowallaは，ユーザーがチェックインするこ

このようにして次々と伝播される情報を最後に平均して，最終とで場所を共有することができるソーシャルネットワークサービ

的なユーザーベクトルe𝑢 ，アイテムベクトルe𝑖 とする．

スから作成されたデータセットである． Yelpは，バーやレストラ
ンなどの飲食店を中心としたお店の評価がまとめられたデータセe𝑢 =𝐿
1 ∑︁ (𝑘 )e ;𝐿 + 1 𝑘=0 𝑢e𝑖 =𝐿
1 ∑︁ (𝑘 )e
𝐿 + 1 𝑘=0 𝑖

ットである． Amazon-Booksは，その名の通りアマゾンの本を対象としたデータセットである．
いずれの4つのデータセットも，推薦システムを評価する際に推薦に必要なスコアはユーザーとアイテムの二つのベクトルのよく利用される．これらのデータセットのユーザー数やアイテム

内積によって計算する．

数，インタラクション数，スパース性などは様々である．本実験𝑟ˆ𝑢𝑖 = e𝑇𝑢 e𝑖

では計算時間を有限に抑えるためにも，各ユーザー，アイテムの(7)

インタラクション数に対して下限と上限を設けてフィルタリング

3.2 モデル2を行った．

モデル2では従来の隣接行列(式(1))と量子化隣接行列(式(6))のまた，今回提案するモデルの考察を深めるために，MovieLens-

両方を利用したハイブリッド形式のモデルである．

1Mを除く三つのデータセットについて，interactionの少ない疎なユーザー，アイテムの初期潜在ベクトルとして，従来の隣接行

データセットも作成した．すなわち，今回利用するデータセット(0)(0)
列に作用させる潜在ベクトルe𝑐,𝑢 ， e𝑐,𝑖 ，量子化隣接行列に作用(0)(0)
される潜在ベクトルe𝑞,𝑢 ，e𝑞,𝑖 をそれぞれ用意する．モデル1と同はMovieLens-1Mについてはinteractionの多いユーザーとアイテ
ムを抽出した密なデータセット，他の三つのデータセットについ様に，これらの潜在ベクトルに対して，従来の隣接行列と量子化ては，密なデータセットに加え，interactionの少ないユーザーと隣接行列をそれぞれ作用させる．

アイテムを抽出した疎なデータセットも利用する．

3

日本データベース学会和文論文誌
一般論文

Vol. 21-J, Article No. 3, 2023年 3月

図3 レイヤー数を2にしたモデル2のアーキテクチャ．

表1

表2

Filtering conditions for dense dataset.

Filtering conditions for sparse dataset.

Dataset

Lower

Upper

Dataset

Lower

Upper

MovieLens-1M

10∞

Gowalla3

25

Gowalla

20

∞

Yelp

3

25

Yelp

35

∞

Amazon-Books

3

20

Amazon-Books

32

∞
表3

表1と表2に，密なデータセットのフィルタリングの条件と，疎なデータセットのフィルタリングの条件を，それぞれ示す．

Statistis of the dense datasets.

Dataset#Users#Items#Interactions

Density

MovieLens-1M

6,041

3,261

998,5390.005069

フィルタリングを行った後の統計情報は表3と表4の通りであGowalla

5,993

5,640

281,4120.008326

る．密なデータセットと疎なデータセットでは，interactionにお

Yelp

9,024

7,789

657,692

0.009357

Amazon-Books

8,465

9,107

608,034

0.007887

およそ一桁程度の差がある．

4.2 評価指標
評価指標には推薦システムの評価でしばしば利用され

表4

るRecall(再現率)，normalized discounted cumulative gain (nDCG)

Statistis of the sparse datasets.

[4]を利用する． Recallは正解データの中でどれだけの割合を推

Dataset#Users#Items#Interactions

Density

薦できたかを表す指標で，上位10件のアイテムを対象とする．

Gowalla

3,518

3,412

13.4830.00112nDCGは， DCG (Discounted Cumulative Gain)を正規化すること

Yelp

5,482

5,202

11,6650.00041で得られる指標であり，ランキング上位のアイテムを正解できAmazon-Books

5,574

5,587

21,8850.00070

ると高い評価を得ることができるという性質を持つ． nDCGも上位10件のアイテムを対象とする．

4.3 計算量
式(6)の計算量について議論する． 表現を簡素化するために，
式(6)を以下のように分解する．

4

日本データベース学会和文論文誌
一般論文

Vol. 21-J, Article No. 3, 2023年 3月

表5 実験結果．上の表が密なデータセット1，下の表が疎なデータセット2に関する結果である． Ours-Model1はモデル1， OursModel2はモデル2を示す． (†) はスコアの最大値である．

DatasetMovieLens-1m

GowallaYelp

MethodRecall@10

nDCG@10

Recall@10

nDCG@10

Recall@10

Amazon-Books

nDCG@10

Recall@10

nDCG@10BPR

0.16710.25890.16840.14250.08080.081

0.08720.0828NGCF

0.16700.25580.15750.13630.07860.07740.08370.0788LightGCN

0.17440.2688(†)

0.17110.1494(†)

0.0913(†)

0.0914(†)

0.09580.0927Ours-Model1

0.16920.26190.16410.14240.08530.08470.09070.0860Ours-Model2

0.1746(†)

0.2688(†)

0.1713(†)

0.14770.08690.08650.0984(†)

0.0943(†)

DatasetGowallaYelp

Amazon-Books

MethodRecall@10

nDCG@10

Recall@10

nDCG@10

Recall@10

nDCG@10BPR

0.09940.06690.43700.43130.34700.2709NGCF

0.12010.07110.4473(†)

0.43930.38240.2831

LightGCN

0.12570.0782(†)

0.44330.4397(†)

0.38450.2927Ours-Model1

0.068

0.04250.28060.20470.39030.2995(†)

Ours-Model2

0.1290(†)

0.07780.44440.43870.3914(†)

0.2989モデル2の一部のデータセットにおいて，最良のベースラインÂQ = Q0 + Q1

(8)であるLightGCNを上回る結果も得ることができた．従来の隣接行列に加え，量子的な隣接行列の効果により，隠れたグラフ間の

Q0 =

∑︁

|𝑟⟩⟨𝑟 |

◦2

隣接関係を表現することできたことが原因だと考えられる．た(9)だ，上回った量も高々5%程度であり，統計的にLightGCNよりも𝑟

Q1 = 2∑︁cos (𝜆𝑟 − 𝜆 𝑠 ) |𝑟⟩⟨𝑠| ◦ |𝑟⟩⟨𝑠|

優れたモデルとは言いがたい．

(10)

4.4.1

𝑟 <𝑠

4.3.1

Q0 の計算量られた．原因としては，モデル1では従来の隣接行列を全く考慮

Q0 を正確に計算するには， |𝑟⟩⟨𝑟 | の計算に𝑂 (𝑁 2 ) で，さらにそしていないため，グラフ間の情報の伝達が十分ではなかったことの和を計算する必要があるので，𝑂 (𝑁 3 ) の計算量が必要になる．

4.3.2

モデル１とモデル２の比較

モデル1とモデル2を比較すると，モデル2の方が良い結果が得が考えられる．

Q1 の計算量

4.5 考察∑︁Q1 を 正 確 に 計 算 す る に は， |𝑟⟩⟨𝑠| の 計 算 に 加 え て，の𝑂 (𝑁 2 ) の計算量が必要なため，合計で𝑂 (𝑁 4 ) の計算量が必

今回提案した我々のモデルについて，以下の３つの観点か
ら(Research Questions, RQs)考察を行う．

𝑟 <𝑠

4.5.1 [RQ1] Q0 とQ1要になる．

式(8)において，第一項であるQ0 と第二項であるQ1 が結果に以上の議論により， Q0 + Q1 を正確に計算するには𝑂 (𝑁 3 ) +𝑂 (𝑁 4 ) ∼ 𝑂 (𝑁 4 ) という膨大な計算量が必要になる．今回，我々どのような影響を与えるか確認する．評価指標はRecall@10で，が用意したデータセットでは現実的な時間で計算が終わらないこ

GowallaとAmazon-Booksの密なデータセットを利用する．表6にとが分かった．

結果を示す．

4.3.3

GowallaとAmazon-Booksに お い て ど ち ら もQ1 が な い 方 が 良

Q1 サンプリング

Q1 を 正 確 に 計 算 す る こ と が 不 可 能 な の で， 式(10)の 係
数cos (𝜆𝑟 − 𝜆 𝑠 ) に着目し，この大きさに応じて確率的にサンプ

いRecallを得ることができた． Q1 はあくまでも100,000個をサリングする．今回の実験ではサンプリング数は100,000とした．

4.5.2 [RQ2] 対角成分の影響

Q1 ∼ 𝑝(𝑟, 𝑠) = cos2 (𝜆𝑟 − 𝜆 𝑠 )ンプリングしていることも原因と考えられる．
式(6)を計算すると，対角成分が非常に大きな値を持つことが(11)分かった．対角成分が大きいと，グラフ上の情報の伝播において

表5に，実験結果を示す．我々が提案する手法とこれまで提案

フの多様な成分を伝播させるという目的に沿わないことが予想さ

自分自身の要素が最大になることを意味し，接続されているグラ

4.4 実験結果されてきたBPR [8]，NGCF [13]，LightGCN [3]の手法で得られれる．よって，RQ2では対角成分を0にして，その後正規化処理た結果を比較する．モデル1とモデル2にはハイパーパラメータがをした行列を作成し，結果がどのように変化するか調べた．

あるが，最も結果が良いパラメータセットの結果を示している．

5

日本データベース学会和文論文誌
一般論文

Vol. 21-J, Article No. 3, 2023年 3月

表6

Q0

4.6.1

RQ1の結果Q1

GowallaAmazon-Books

Ours-Model1

TRUE

TRUE

0.14910.0885Ours-Model1

TRUE

FALSE

0.16410.0892Ours-Model2

TRUE

TRUE

0.1697

0.0943Ours-Model2

TRUE

FALSE

表7

0.1705

定義

ユーザー𝑢 にとって，式 (7) が𝑠番目に高いアイテムのベクトルをe𝑖,𝑢(𝑠) と表記する．また， 𝑠番目から𝑡 番目までのアイテムのベ
クトルの平均を以下のように表記する．

e𝑖,𝑢(𝑠,𝑡 ) =0.0955𝑡∑︁
1e𝑖,𝑢(𝑟 )𝑡 − 𝑠 + 1 𝑟=𝑠(12)

本研究では，多様性を定量的に考察するために，あらかじめ各

RQ2の結果ユーザーのアイテムの順位の範囲を定め，その順位の範囲にある

Diag set to 0

GowallaAmazon-Books

アイテムのベクトルの平均を計算し，各ベクトルとその平均のベ

Ours-Model1

FALSE

0.14060.0776

クトルのユークリッド距離の平均を求め，さらにその平均を全ユ

Ours-Model1

TRUE

0.14930.0845ーザに対して計算し平均をとった𝑑𝑖 を以下のように定義する．

Ours-Model2

FALSE

0.1697

0.0942Ours-Model2

TRUE

0.1713

0.0961

表8

Ours-Model1

𝑑𝑖 (𝑠, 𝑡) =RQ3の結果𝑚 ∑︁𝑡∑︁
1e𝑖,𝑢(𝑠) − e𝑖,𝑢(𝑠,𝑡 )𝑚(𝑡 − 𝑠 + 1) 𝑢=1 𝑟=𝑠(13)

例えば， 𝑑𝑖 (25, 29) は，あるユーザーに対するアイテムのランキング順位が25位から29位のアイテムのベクトルと，その5つのÂQ Filter

GowallaAmazon-Books

TRUE

0.14060.0776ベクトルの平均のユークリッド距離の平均を求め，さらに，すべてのユーザーに対して同様の計算を行い，平均をとることを意味

Ours-Model1

FALSE

0.14910.0885Ours-Model2

TRUE

0.1697

0.0942Ours-Model2

FALSE

0.1697

0.0943する．

𝑑𝑖 (𝑠, 𝑡) が大きければ，ランキング順位が𝑠から𝑡 までのアイテムの集合がベクトル空間上で広い範囲に存在することを示し，多様性のある推薦システムを構築できたことを意味する．
以下においては，主に本研究にて提案するOur-Model1とOur-

こ ち ら も 評 価 指 標 はRecall@10で， デ ー タ セ ッ ト は，Model2について考察を行い，LightGCN [3]を比較対象とする．

GowallaとAmazon-Booksの密なデータセットを利用する．
対角成分を0にしてその分他の成分を強くしたことで，グラフ

4.6.2

図4は，ランダムに選んだある一人のユーザーに対して，1 ≤ 𝑠 ≤ったと考えることができる．

4.5.3

定性的考察

最初に，広いランキング範囲を対象にした結果を図4に示す．

上で接続されている他の頂点から情報が伝播され良い結果に繋が50， 1001 ≤ 𝑠 ≤ 1050， 2001 ≤ 𝑠 ≤ 2050， 3001 ≤ 𝑠 ≤ 3050に[RQ3] ÂQ のフィルタリング

式(6)におけるQ0 とQ1 は従来の隣接行列と比較して0の成分がおけるe𝑖,𝑢(𝑠) をそれぞれその距離関係を可能な限り保存した状態

圧倒的に少ない．これは量子化隣接行列の特徴であり，従来の隣で2次元にプロットした図である．それぞれのベクトルは64次元接行列にはないグラフ間の情報伝播を可能にするものである．しであるが，それをt-SNE [12]を利用して， 2次元に圧縮した．利かしながら，ÂQ が密になりすぎると，他の重要な成分の接続の用したデータセットはYelpである．
横 軸 に は， 比 較 対 象 と し て 選 択 し たLightGCN [3]とOur-

強度が弱まる可能性が考えられる．
い，0の成分の割合を従来の隣接行列と同等になるように行いそModel1， Our-Model2の各モデルが並び，縦軸には，サンプルの順位𝑠 （1 ≤ 𝑠 ≤ 50， 1001 ≤ 𝑠 ≤ 1050， 2001 ≤ 𝑠 ≤ 2050，の影響を調べた．

3001 ≤ 𝑠 ≤ 3050）を取り，順位に対するユークリッド距離

よって， RQ3として， ÂQ の大きい方からフィルタリングを行

結果はフィルタリングしない方が高いRecallが得られた．本来の依存性をプロットした． Our-Molde1では， LightGCNやOur-

値がある成分を0にフィルタリングすることで，量子化隣接行列

Model2と比較して，順位が下がるにつれてベクトル間の距離が特有の成分が無効化され，結果が悪くなると考えられる．

広がっていることがわかる．

4.6 多様性，意外性の考察

4.6.3

定量的考察

推薦システムでは，上記で議論したRecallやPrecisionなどの評

次に粒度を細かくし，推薦システムにおいて，多様性を必要と価指標の他に，多様性や意外性（セレンディピティ）も求められする比較的低いランキング順位におけるアイテムについて定量的る．推薦システムがユーザーが欲しい情報をタイミング良くユーな考察を行う．

ザーに提供できたとしても，同じようなアイテムを推薦し続ける

具 体 的 に は， 順 位𝑠が26 ≤ 𝑠 ≤ 30， 51 ≤ 𝑠 ≤ 55，とユーザーに飽きが生じる．最新の推薦システムでは，式 (7) で76 ≤ 𝑠 ≤ 80， 101 ≤ 𝑠 ≤ 105， 151 ≤ 𝑠 ≤ 155， 251 ≤定義されるスコアが上位のアイテムは高いRecallやPrecisionを持𝑠 ≤ 255 の ア イ テ ム を 対 象 と す る． こ れ ら の 順 位 に つ い て，

つ一方で，スコアが下位のアイテムでは高いセレンディピティを定義である式(13)に基づき𝑑𝑖 (26, 30) ， 𝑑𝑖 (76, 80) ， 𝑑𝑖 (101, 105) ，持つアイテムをユーザーに推薦することが求められている．

𝑑𝑖 (151, 155) ， 𝑑𝑖 (251, 255) を計算する．
6

日本データベース学会和文論文誌
一般論文

Vol. 21-J, Article No. 3, 2023年 3月

量子化隣接行列(式(6))は，従来利用されてきた正規化隣接行
列(式(1))と比較して， 2部グラフ上で直接接続されていないア
イテム-ユーザーの成分を持つ．この成分がLightGCN [3]と比較して多様性や意外性などを持つことが期待される．今回のOur-

Model1では，最適化されたアイテムはベクトル空間上で広い範囲に分布し，その予想を定量的に裏付ける結果となった．

5 結論
5.1 本研究のまとめ
本研究の結論は以下の通りである．

1. 推薦システムに量子ウォークに基づく量子化隣接行列を利用するモデルを二つ提案した．

2. ランキング順位が上位のアイテムについては， LightGCN[3]と同等のRecallやPrecisionなどの評価指標を得た．
3. ランキング順位が下位のアイテムについては，比較対象であるLightGCN [3]と比較して，多様性のある推薦システムを
構築した．
図4

t-SNE [12]を利用して、 e𝑖,𝑢(𝑠) を2次元にプロットした散5.2 本研究の課題

布図．データセットはYelpであり，ある一人のユーザーをラン

5.2.1 Our-Model1とOur-Model2の差異

ダムにサンプリングした．

本研究の課題の一つに， Our-Model1とOur-Model2の差異の考 察 が 不 十 分 と い う 点 が あ げ ら れ る． 例 え ば， 図5で， Our-

Model1では，ランキング順位が下がるに応じて，ユークリッ
ド距離も広がっているが， Our-Model2ではそのような傾向は見

図5はLightGCN [3]と比較して，ランキング順位が下位のアイ
テムについて𝑑𝑖 (𝑠, 𝑡) の値をプロットした図である．左軸は，Our-

られなかった．この差異については，さらに考察を深める必要がModel1とOur-Model2に対して，隣接行列がÂQ = Q0 +Q1 とÂQ =ある．

Q0 の𝑑𝑖 (𝑠, 𝑡) をLightGCN [3]の𝑑𝑖 (𝑠, 𝑡) で規格化した値を示す．右5.2.2 計算量

軸は，比較対象であるLightGCN [3]の変化をプロットするため

Q1 を求める際，式(11)に従ってサンプリングを行うが，あくに， LightGCN [3]の𝑑𝑖 (1, 5) で各𝑑𝑖 (𝑠, 𝑡) を規格化した値である．

までもサンプリングを行っているため，量子化隣接行列を正右軸であるLightGCN [3]の𝑑𝑖 (𝑠, 𝑡) は，データセットがGowallaの確に計算できていないという課題がある．また，量子化隣接行

場合，ランキングの順位が下がるにつれて，大きくなってい列(式(6))は，正規化隣接行列(式(1))と比較して密な行列になってることがわかる． また，他のデータセットについては，ほぼいるため， Our-Model1やOur-Model2において，ニューラルネッ

一 定 の 値 と な っ て い る． ま た， そ の𝑑𝑖 (𝑠, 𝑡) で 規 格 化 し たOur-

トワークの計算を行う際，疎行列として定義することができず，

Model1の𝑑𝑖 (𝑠, 𝑡) についても，ランキング順位が下がる毎に大計算時に余計なメモリや計算量が必要という課題もある．

きくなっていることがわかる．ただし，Our-Model2については，

5.2.3 連続時間量子ウォーク
本研究では連続時間量子ウォークの概念を取り入れた際，遷移ほぼ一定の値をとり， 𝑑𝑖 (𝑠, 𝑡) に変化がないことがわかる．
図6は， Our-Model1の 隣 接 行 列 がÂQ

= Q0 + Q1 の 場 合

行列M̂において， 𝑡 = 1を仮定し隣接行列を計算した．この仮定の𝑑𝑖 (𝑠, 𝑡) のアイテムのベクトルの次元数に対する依存性を示

が妥当なものなのか，もしくは，Q1 の時間平均が0であることにすグラフである．本研究で基本となる次元数は64であるが，そ着目し，式(6)の第一項であるQ0 のみを考慮すれば十分なのか考の倍である128，さらにその倍である256について実験を行った．

察を深める必要がある．

データセットがYelpの次元サイズが256のデータを除き，すべて

5.3 今後の展望
今後は量子ウォークに関するモデルの理解を深め，モデル改善の次元数についてランキング数順位が下がるにつれて上昇することが確認できる．

4.6.4に取り組み，精度がより高く，かつ多様性や意外性のある量子モ多様性に関する結果

デルを利用した推薦システムの研究を進める予定である．

図5と 図6の 結 果 か ら， Our-Model1に お い て は， LightGCN[3]と比較して，ランキング順位が下がるにつれて，ベクトル空間上での距離が広くなり，多様性がある推薦システムを構築することができた． Our-Model2については，ランキング順位が下がるにつれて，距離は広くなるが，LightGCN [3]と比較するとほぼ同程度であり，優位性があるとは認められなかった．

7

日本データベース学会和文論文誌
一般論文

Vol. 21-J, Article No. 3, 2023年 3月

ラ ン キ ン グ 順 位 が 下 位 の ア イ テ ム に つ い て𝑑𝑖 (𝑠, 𝑡) の 値 を プ ロ ッ ト し た 図． 左 軸 がOur-Model1とOurModel2の𝑑𝑖 (𝑠, 𝑡) をLightGCN [3]の𝑑𝑖 (𝑠, 𝑡) を基準に計算した値，右軸がLightGCN [3]の𝑑𝑖 (1, 5) の値を基準に計算した値． OurModel1では，LightGCN [3]と比較してもアイテムのベクトル空間上で広い範囲に存在していることがわかる．

図5

図6

Our-Model1の隣接行列がÂQ = Q0 + Q1 の場合の𝑑𝑖 (𝑠, 𝑡) のアイテムのベクトルの次元数依存性．各プロットはベクトルの次元数が64, 128, 256の場合を示す． Yelpのベクトルの次元数が256のデータを除き，すべてランキング順位が下がるにつれて増加す
る．

[10] J. Ben Schafer, Dan Frankowski, Jon Herlocker, and Shilad Sen. Collaborative Filtering Recommender Systems, page 291–324. SpringerVerlag, Berlin, Heidelberg, 2007.
[11] Ewin Tang. A Quantum-Inspired Classical Algorithm for Recommendation Systems. In Proceedings of the 51st Annual ACM SIGACT
Symposium on Theory of Computing (STOC 2019), page 217–228.
[12] Laurens van der Maaten and Geoffrey Hinton. Visualizing Data using
t-SNE. Journal of Machine Learning Research (JMLR), 9(86):2579–
2605, 2008.
[13] Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng
Chua. Neural Graph Collaborative Filtering. In Proceedings of the
42nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2019), page 165–174.
[14] Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao
Yu, and Kilian Q. Weinberger. Simplifying Graph Convolutional Networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors,
Proceedings of the 36th International Conference on Machine Learning (ICML 2019), pages 6861–6871.
[15] Jin Zheng, Qing Gao, and Yanxuan Lv. Quantum Graph Convolutional Neural Networks. In Proceedings of the 40th Chinese Control
Conference (CCC ’21), pages 6335–6340, 2021.

参考文献[1] Lu Bai, Yuhang Jiao, Luca Rossi, Lixin Cui, Jian Cheng, and Edwin R.
Hancock. Graph Convolutional Neural Networks based on Quantum
Vertex Saliency. arXiv preprint arXiv:1809.01090, 2019.
[2] Chris Godsil. Average mixing of continuous quantum walks. Journalof Combinatorial Theory, Series A, 120(7):1649–1662, 2013.
[3] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, YongDong Zhang,and Meng Wang. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. In Proceedings of the 43rd
International ACM SIGIR Conference on Research and Development
in Information Retrieval (SIGIR 2020), page 639–648.
[4] Kalervo Järvelin and Jaana Kekäläinen. Cumulated Gain-Based Evaluation of IR Techniques. ACM Trans. Inf. Syst., 20(4):422–446, oct
2002.
[5] Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation
Systems. In Christos H. Papadimitriou, editor, 8th Innovations in
Theoretical Computer Science Conference, ITCS 2017, January 9-11,
2017, Berkeley, CA, USA, volume 67, pages 49:1–49:21.
[6] Thomas N. Kipf and Max Welling. Semi-Supervised Classification
with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations (ICLR 2017).
[7] Yehuda Koren. Factorization Meets the Neighborhood: A Multifaceted Collaborative Filtering Model. In Proceedings of the 14th
ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining (KDD 2008), page 426–434, New York, NY, USA.
[8] Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars
Schmidt-Thieme. BPR: Bayesian Personalized Ranking from Implicit
Feedback. In Proceedings of the 25th Conference on Uncertainty in
Artificial Intelligence (UAI 2009), page 452–461.
[9] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl.
Item-Based Collaborative Filtering Recommendation Algorithms. In
Proceedings of the 10th International Conference on World Wide Web(WWW 2001), page 285–295.

8