Signed Network
におけるノードの分散表現の学習
Node Representation Leraning for Signed Networks
在原 大樹
1∗村田 剛志
1Arihara Hiroki
1Murata Tsuyoshi
11
東京工業大学 情報理工学院 情報工学系
1
Department of Computer Science, School of Computing, Tokyo Institute of Technology
Abstract: Network embedding converts each node in a network into a low-dimentional vector which preserves structural information on the network. The target of most work are unsigned networks, which only have positive relationships. However, some real situations are represented as signed networks, which have positive and negative relationships. We propose a new network embedding method for signed networks. Our method learns both structure of a network and relationship of its node pairs. The performance of our method is good for the tasks of relation prediction and link prediction.
1
はじめに
SNS におけるユーザー同士の関係や Web サイトにお けるリンクの関係は,「ノード」とそれらを結ぶ「エッ ジ」からなるネットワークを用いて表現することが出 来る. 近年,SNS 等が広く普及したことにより, 大規模 なネットワークの解析の重要性が高まっている. ネッ トワーク上の各ノードを低次元のベクトルで表現する ネットワークエンベディングが注目を集めている. ネッ トワークエンベディングでは元のネットワークの構造 的な特徴を保存するように各ノードのベクトルを学習 する. 例として,DeepWalk[1] ではネットワーク内で近 いノードは, 対応するベクトルも近くなるように学習す る. ネットワークエンベディングで得られたベクトルを 解析することで, ノードのラベル分類やリンク予測など のタスクを高い精度で行なうことが出来ることが知ら れている [1][3][7]. 既存のネットワークエンベディング の手法の多くはノードやエッジが属性を持たないネッ トワークを対象としている. 人と人との関係では友好と対立, 信頼と不信のよう に, 正と負の関係が存在する場合がある. これらを表現 するために, エッジに正または負の属性を付与したネッ トワークを Signed Network と呼ぶ. Signed Network を解析することにより, ユーザー間の関係性を考慮し た高精度なユーザー推薦や, 将来的なユーザー間の対 立の予測などが可能になると期待されている. Signed Network におけるネットワークエンベディングはネッ トワークの構造と, エッジの属性を保持した各ノードの ∗東京工業大学 情報理工学院 情報工学系 村田研究室 在原大樹 〒 152-8552 東京都目黒区大岡山 2-12-1 W8-59 E-mail: [email protected] 低次元のベクトルを学習することが目的となる. 既存 手法は「ネットワークの構造に基づく学習」[2] を用い たものと「ノード間の関係に基づく学習」[4][6] を用い たものが存在する. 本研究ではこれら 2 つの手法を組み合わせ, ネット ワークの構造とノード間の関係の両方を加味した Signed Network におけるネットワークエンベディングの手法 を提案する. 実験により, 実在の Web サイト内のユー ザーの関係を表したデータセットにおけるノードの関 係予測とリンク予測において, 提案手法は既存手法より 高い精度を示した.2
問題定義
本稿で扱う Signed Network 及び Signed Network に おけるネットワークエンベディングについて述べる.
2.1
Signed Network
Signed Network は友好と敵対, 信頼と不信のような 正と負の関係を表現するために, エッジに正 (positive) または負 (negative) の属性を付与したネットワークで ある. また, 本稿では特にエッジが有向である Signed Network について記述する. これは, 現実のネットワー クは有向なものが多いためである. Signed Network G は G = (V, E) で表す.V はノード の集合であり,E はエッジの集合である. ノード u∈ V からノード v ∈ V への属性 r ∈ {positive, negative} のエッジを (u, v, r) で表す. 人工知能学会研究会資料 SIG-KBS-B902-012.2
Signed Network におけるネットワー
クエンベディング
Signed Network におけるネットワークエンベディン グは Signed Network G, 獲得するベクトルの次元 d≪ |V |, およびモデルのハイパーパラメータを入力とし, 各 ノード u∈ V に対応する d 次元ベクトル −→u を出力と するタスクである. 得られるベクトルは, どのノード間 にエッジが存在するかというネットワークの構造の特 徴と, エッジの属性が正であるか負であるかというノー ド間の関係の特徴を保持している必要がある.3
既存手法
3.1
Skip-gram
Skip-gram[5] は自然言語の領域で単語のベクトル表 現を獲得するために提案されたモデルである. [1] は Skip-gram をネットワークに対して適用し, ノードの ラベル分類などのタスクで高い精度を示した. これ以 降,Skip-gram はネットワークエンべディングでも広く 用いられるようになった. ネットワークエンベディングにおいて,Skip-gram は 以下の損失関数を最小化することで学習を行う. Loss =− 1 |D| ∑ (u,v)∈D log P (v|u) (1) ここで,D はサンプリングされたノード対,P (v|u) はノー ド u のベクトル −→u ∈ Rd, および, 文脈としてのノード のベクトル −→cv ∈ Rdを用いて P (v|u) = exp(− →uT · −→c v) ∑ i∈V exp(−→uT · −→ci) (2) で定義される事後確率である. P (v|u) の分母は計算量 が膨大になるため,Negative Sampling[5] を用いて損失 関数を以下のように近似して学習を行う. Loss =− 1 |D| ∑ (u,v)∈D ψ+u,v+ ∑ i∈Ns(v) ψu,i− (3) ただし,ψ+u,v = log σ(−→u · −→cv), ψu,i− = log σ(−−→u · −→ci)
であり,σ() はシグモイド関数である. また,Ns(v) は Negative Sampling によりサンプリングされたノード の集合である. D のサンプリングの方法により P (v|u) が表す確率は 変わる. 例として,LINE[3] では D はエッジをサンプリ ングすることで集められ,P (v|u) は「あるノード u から エッジが伸びているとき, その先にあるノードが v であ る確率」を表す. DeepWalk[1] や node2vec[7] はランダ ムウォークによってサンプリングすることで,P (v|u) は 「あるランダムウォークで得られるノードの列にノード u が出現するとき, 付近にノード v も出現する確率」を 表す. また, 式 (2) から分かるように,Skip-gram ではノード 対 (u, v) の学習に対して, ネットワーク内の u, v 以外 のノードについても考慮してベクトルの学習を行なう ため,D に含まれないノード対についても学習が行われ る. 例として, ネットワーク内で遠いノード対について は,D に現れないため P (v|u) が小さくなるように学習 が進む.
3.2
Signed Network におけるネットワー
クエンベディング
3.2.1 ネットワークの構造に基づく学習 SIDE[2] は Skip-gram を拡張したモデルを用いて,「あ るノード u と属性 r の関係があるノードが存在するとき, その先のノードが v である」という事後確率 P (v|u, r) を最大化するように学習を行なう. SIDE は Skip-gram を用いることで, ネットワーク全 体の構造を効率よく学習することが出来る. 一方で, 与 えられたノード間の関係については, 表現力が低く学習 の効率が悪いという問題がある. 3.2.2 ノード間の関係に基づく学習 StEM[4] はあるノード対 (u, v) に対してそのノード 間の関係を予測することで学習を行なう手法である. StEM はニューラルネットワークを用いて以下の損失 関数を最小化することでベクトルを学習する. Loss = − 1 |E+| ∑ (u,v,positive)∈E+log P (positive|u, v)
−|E1−| ∑
(u,v,negative)∈E−
log P (negative|u, v) (4) ここで,E+は正の属性を持つエッジの集合,E−は負の 属性を持つエッジの集合である. SiNE[6] はノード x, y, z の 3 つのノードに対して, ノード x, y 間に正の関係があり, ノード x, z 間に負の 関係があるとき,d(−→x , −→y ) < d(−→x , −→z ) となるようにベ クトルの学習を行なう. ここで,d(−→u , −→v ) はノード u の ベクトルとノード v のベクトルの距離であり,SiNE で はニューラルネットワークを用いて表現される. これらの手法はノード間のエッジの属性を表現力の 高いニューラルネットワークで学習することで, ノード 間の関係を効率よく学習することが出来る. 一方で, サ
ンプリングされたノード対について, それらのベクトル についてのみ値の更新を行なうため, ネットワーク全体 に対する学習が進みにくいという問題がある.
4
提案手法
4.1
提案手法概要
Signed Network におけるネットワークエンベディン グでは, どのノード間にエッジが存在するかというネッ トワークの構造の特徴と, エッジの属性が正であるか負 であるかというノード間の関係を保持した各ノードの ベクトルを学習することが必要である. しかし, 既存手 法はどちらか一方のみを重視した学習を行っている. そ こで, 提案手法はネットワークの構造とノード間の関係 の両方を学習することで精度を向上する. また、エッジが有向な Signed Network においては, ノード間の関係が非対称な場合がある. 例として, ノー ド u からノード v に正のエッジが存在し, ノード v から ノード u に負のエッジが存在する場合などがある. こ のような場合には, ノード u に対応するベクトル −→u を 一意に求めることは難しい. そこで提案手法では,1 つ のノード u に対して, エッジの始点としての特徴を学習 したベクトルを −→yu ∈ R d 2, 終点としての特徴を学習し たベクトルを −x→u∈ R d 2 とし, それらを個別に学習する. そして, これらを結合したベクトルをノード u のベクト ル −→u とする.4.2
損失関数
提案手法は, 損失関数にネットワークの構造を学習 する項 Lossstructureと, ノード間の関係を学習する項 Lossrelationを用いることで, ネットワークの構造とノー ド間の関係の両方を加味した各ノードのベクトルを学 習する. 提案手法の損失関数 Loss を以下で定義する.Loss = (1−α)Lossstructure+αLossrelation+λLossreg
(5) ここで,Lossregは正規化項であり,λ は正規化項の重み を表すハイパーパラメータである. また,α は 0≤ α ≤ 1 を満たすハイパーパラメータであり,Lossstructureと Lossrelationの重み付けを行うハイパーパラメータであ る. α が 1 に近いときネットワークの構造を重視した 学習を行い,α が 0 に近いときノード間の関係を重視し た学習を行う.
4.3
ネットワークの構造の学習
エッジが属性を持たないネットワークに対するネット ワークエンべディングの研究により, Skip-gram はネッ トワークの構造を精度よく学習することが出来ること が示されている. しかし, 通常の Skip-gram ではエッ ジの属性を考慮していないことから,Skip-gram を拡張 したモデルを提案する. 提案手法におけるネットワークの構造の学習は, 以下 の損失関数 Lossstructureを最小化することで行う. Lossstructure=− 1 |E| ∑ (u,v,r)∈E log P (v|u, r) (6) ここで,P (v|u, r) はノード u を始点とした属性 r のエッ ジが存在するとき, その終点がノード v である確率で あり,P (v|u, r) = exp{f(u, r)
T · −→x v} ∑ i∈V exp{f(u, r)T · −→xi} (7) で定める. ただし,f (u, r) はノード u と属性 r が与えら れたとき, 対応する d 次元のベクトルを返す関数であ り, 以下のように定める. f (u, r) = −→yuTWr+ b (8) ここで,Wr ∈ R d 2×d2 および,b∈ Rd2 は学習されるパラ メータである。このままでは式 (7) の分母の計算に全 てのノードについての計算が必要となり, 計算量が莫大 になる. そこで,Negative Sampling を用いて以下のよ うに近似する. Lossstructure=− 1 |E| ∑ (u,v,r)∈E ψ+u,v,r+ ∑ i∈Ns(u) ψu,i,r− (9) ここで,ψ+
u,v,r= log σ(f (u, r)T·−x→v), ψ−u,i,r= log σ(−f(u, r) T· − →xi) である.
4.4
ノード間の関係の学習
現実の Signed Network は多くのノードが複雑に影 響しあっており, これらを学習するために表現力の高 いモデルが必要である. SiNE や StEM は, 表現力の高 いニューラルネットワークを用いて学習を行なうこと で, 高い精度を示している. 本研究でもこれらに習い, ニューラルネットワークを用いる. 提案手法は以下の様に構成される 2 層のニューラル ネットワークを用いてノード間の関係の学習を行なう. h0 = [−→yu, −x→v] h1 = σ(W1hT0 + b1) g(u, v) = σ(W2hT1 + b2) (10)ここで,[ ] は結合を表し,W1 ∈ Rd×d, W2 ∈ Rd, b1 ∈ R1×d, b 2∈ R は学習されるパラメータである. σ() はシ グモイド関数である. 提案手法では, ニューラルネットワークの出力 g(u, v) で以下のように P (r|u, v) を定める.
P (positive|u, v) = g(u, v) (11)
P (negative|u, v) = 1 − g(u, v) (12) これを用いて, 以下の損失関数を最小化することによっ て学習を行う. Lossrelation = − 1 |E+| ∑ (u,v,positive)∈E+
log P (positive|u, v)
−|E1−| ∑
(u,v,negative)∈E−
log P (negative|u, v) (13) ここで,E+は正の属性を持つエッジの集合,E−は負の 属性を持つエッジの集合である.
5
実験
5.1
実験概要
既存手法との精度の比較と, 提案手法の α による精 度の影響について実験を行なう. 既存手法との精度比 較では, 関係予測とリンク予測のタスクについて提案手 法と既存手法の精度を比較することによって提案手法 の有効性を確認する. α による精度の影響では, 提案手 法について, ハイパーパラメータ α の値によってどの ように精度が変化するかを確認する.5.2
データセット
データセットは SNAP1で公開されている Slashdot および Epinons を用いる. どちらも実在の Web サイト から抽出されたデータセットである. Slashdot は科学技術に関する情報交換サイト Slash-dot のユーザー間の関係を抽出したデータセットであ る. Slashdot では他のユーザーを“friend”および“foe” として登録することが出来る. 本実験では“ friend ”を 正のエッジ,“ foe ”を負のエッジとした Signed Network で実験を行なう. Epinions は消費者レビューサイト Epinions のユー ザー間の関係を抽出したデータセットである. Epinions では他のユーザーを“ trust ”および“ distrust ”として 1https://snap.stanford.edu/ 登録することが出来る. 本実験では“ trust ”を正のエッ ジ,“ distrust ”を負のエッジとした Signed Network で 実験を行なう. 表 1 に各データセットのノード数|V |, エッジ数 |E|, および, 正のエッジの割合を示す. 表 1: データセット |V | |E| 正のエッジ (%) Slashdot 82140 549202 76.1 Epinions 131828 841371 85.35.3
既存手法との精度比較
5.3.1 比較手法 提案手法と比較を行なう手法は Signed Network にお けるネットワークエンべディングの手法である SiNE[6], StEM[4], SIDE[2] を用いる. SiNE および StEM はノー ド間の関係に基づいて学習を行なう手法であり, ニュー ラルネットワークを用いて各ノードのベクトルの学習 を行なう. SIDE はネットワークの構造に基づいて学習 を行なう手法であり,Skip-gram を拡張したモデルを用 いて各ノードのベクトルの学習を行なう. StEM およ び SIDE は元論文の著者による実装を用い, 提案手法と SiNE については本実験のために本稿の著者が実装した ものを用いる. 5.3.2 パラメータチューニング 全手法に共通して, 学習するベクトルの次元 d は d = 60 とする. 提案手法および SIDE では有向グラフに対 してエッジの始点側と終点側について異なるベクトル を学習するため, それぞれ 30 次元としそれらを結合し たものをノードのベクトルとして扱う. 提案手法は α = 0.5 とし, その他のパラメータについ ては, 学習データ内でグリッドサーチを行い決定した. 既存手法は論文中で値が明言されているパラメータに ついてはその値を用い, その他のパラメータについて は, 学習データ内でグリッドサーチを行い決定した. 5.3.3 関係予測 関係予測はあるノード間にエッジが存在することはわ かっているとき, そのエッジの属性が正であるか負であ るかを予測するタスクである. 本実験では, データセッ ト中の 80%のエッジを学習データとしてエンベディン グを行なう. その後, 得られた各ノードのエンベディン グを用いて, ロジスティック回帰の学習を行なう. 最後表 2: 提案手法と既存手法の関係予測の精度
データセット 指標 SiNE StEM SIDE 提案手法
AUC 0.863 0.893 0.853 0.904 Slashdot F1 0.879 0.890 0.861 0.881 Macro-F1 0.755 0.769 0.731 0.784 AUC 0.833 0.939 0.923 0.943 Epinions F1 0.851 0.936 0.916 0.948 Macro-F1 0.791 0.840 0.811 0.841 表 3: 提案手法と既存手法のリンク予測の精度
データセット 指標 SiNE StEM SIDE 提案手法
Slashdot Micro-F1 0.633 0.622 0.660 0.672 Macro-F1 0.572 0.510 0.613 0.638 Epinions Micro-F1 0.763 0.710 0.784 0.787 Macro-F1 0.681 0.597 0.686 0.701 に残りの 20%のエッジを用いて関係予測を行う. 評価 指標として AUC,F1,Macro-F1 の 3 つを用いた. すべ て 0 から 1 までの値をとり,1 に近いほど精度が高い. 結果を表 2 に示す. 太字は各指標において最も良い 数値を, 下線は 2 番目に良い数値を表す. 実験の結果か ら以下のことがわかる. • Slashdot の F1 を以外の項目について, 提案手法 が最も高い精度を示した. このことから, 提案手 法は元の Signed Network の特徴を効率よく学習 できていると考えられる. • 提案手法と StEM が高い数値を示した. このと ことから, 関係予測においてはノード間の関係を 用いた学習が効果的であると考えられる. 一方 で,SIDE の精度は提案手法や StEM と比較して 低い。これは, 関係予測においてはエッジの存在 は確定しているため, ネットワークの構造に基づ く学習の効果が小さいためであると考えられる. 5.3.4 リンク予測 リンク予測はどのノード間にエッジが存在するかを 予測するタスクである. エッジに属性を持たないネット ワークに対しては, エッジが存在するか存在しないかと いう 2 値分類を行なうが, 本実験では Signed Network に対するリンク予測であるため, 属性を考慮するのが妥 当である. したがって, 本実験ではあるノード間に正の エッジが存在する, 負のエッジが存在する, あるいはエッ ジが存在しないという 3 値分類を行いその精度を確認 する. まずデータセット中の 80%のエッジを学習デー タとしてエンベディングを行なう. その後, 学習データ 中の負のエッジと同じ数の正のエッジとエッジが存在 しないノード対をサンプリングし, ロジスティック回帰 の学習を行なう. 最後に, 残りの 20%のエッジに, 負の エッジと同じ数のエッジが存在しないノード対を加え たものをテストデータとしリンク予測を行なう. 評価 指標として他クラス分類の精度指標である Micro-F1 お よび Macro-F1 を用いている. どちらも 0 から 1 まで の値をとり,1 に近いほど精度が高い指標である. 結果を表 3 に示す. 太字は各指標において最も良い 数値を, 下線は 2 番目に良い数値を表す. 実験の結果か ら以下のことがわかる. • 提案手法が最も高い結果を示した. そのことから, 提案手法は精度よく元のネットワークの特徴を学 習できていると考えられる. • 提案手法と SIDE が高い精度を示したが, リンク 予測において高精度であった StEM の精度は低 い. このことから, リンク予測の場合にはネット ワークの構造に基づく学習が効果が高いと考えら れる. これは, リンク予測の場合にはエッジの属 性に加えて, エッジの有無を学習することが必要 であり,Skip-gram を用いてエッジが存在しない ノード間の学習を行うことが有効なためであると 考えられる.
5.4
α による影響
本節ではパラメータ α により提案手法の精度がどの ように変化するかを確認する. 関係予測とリンク予測 について α を 0,0.2,0.4,0.6,0.8,1.0 と変化させた場合に どのように精度が変化するかを調べる. Slashdot と Epinions でほぼ同様の結果を示したた め,Slashdot の結果について述べる. α と関係予測の精 度との関係を図 1 に, リンク予測の精度との関係を図 2 に示す. 横軸が α の値を, 縦軸が各指標の数値を表す.図 1: α と関係予測の精度との関係 図 2: α とリンク予測の精度との関係 関係予測においては α = 1.0 で最も高い結果となっ ている. このことから, 関係予測の場合には α を大き くし, ノード間の関係に基づく学習を重視することで精 度が高くなると考えられる. 一方, リンク予測において は,α が 0 と 1 の間で精度が向上することがわかる. こ のことから, リンク予測においてはノード間の関係に基 づく学習とネットワークの構造に基づく学習の両方が 重要であると考えられる.
6
おわりに
Signed Network におけるネットワークエンべディン グの手法を提案した. 提案手法はネットワークの構造 に基づく学習と, ノード間の関係に基づく学習の両方を 用いることで, 精度を向上する. 実験によって, 提案手 法は既存手法と比較して高い精度でネットワークの特 徴を学習することが出来ると確かめられた. 特に, タス クがリンク予測である場合には, ノード間の関係の学習 とネットワークの構造に関する学習の両方を組み合わ せることが有効であると考えられる.参考文献
[1] Perozzi, Bryan., Al-Rfou, Rami., Skiena, Steven.: Deepwalk: Online learning of social representa-tions, Proceedings of the 20th ACM SIGKDD
in-ternational conference on Knowledge discovery and data mining, pp. 701-710 (2014)
[2] Kim, Junghwan., Park, Haekyu., Lee, Ji-Eun., Kang, U.: Side: representation learning in signed directed networks, Proceedings of the 2018 World
Wide Web Conference, pp. 509-518 (2018)
[3] Tang, Jian., Qu, Meng., Wang, Mingzhe., Zhang, Ming., Yan, Jun., Mei, Qiaozhu.: Line: Large-scale information network embedding,
Proceed-ings of the 24th international conference on world wide web, pp. 1067-1077 (2015)
[4] Inzamam Rahaman., Patrick Hosein.: A Method for Learning Representations of Signed Net-works, Proceedings of the 14th International
Workshop on Mining and Learning with Graphs (MLG), (2018)
[5] Mikolov, Tomas., Sutskever, Ilya., Chen, Kai., Corrado, Greg S., Dean, Jeff.: Distributed repre-sentations of words and phrases and their compo-sitionality, Advances in neural information
pro-cessing systems, pp. 3111-3119 (2013)
[6] Wang, Suhang., Tang, Jiliang., Aggarwal, Charu., Chang, Yi., Liu, Huan.: Signed net-work embedding in social media, Proceedings of
the 2017 SIAM international conference on data mining, pp. 327-335 (2017)
[7] Grover, Aditya., Leskovec, Jure.: node2vec: Scalable feature learning for networks,
Proceed-ings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864 (2016)
