Deep Graph Representation Learning and Optimization for Influence Maximization(ICML 2023)

Author

Chen Lingらのチーム

Link

icml.cc

メモ書き

  • 影響力最大化(Influence Maximization)について
  • 影響力最大化とは、以下を満たす \tilde{\mathbf{x}} \subseteq Vを探すこと。
\tilde{\mathbf{x}} = \rm{argmin}_{|\mathbf{x}| \leq k} M \left( \mathbf{x}, G; \theta \right)

ここで、 Mは影響拡散モデルであり、 \mathbf{x}を感染させた時にどれぐらいその感染が広がるかを示す。要するに、 k個以下のノードを感染させて感染を広げる時、感染したノード数を最大にする初期ノード集合tex: \tilde{\mathbf{x}} \subseteq Vはどれか？という問題。

  • 従来手法は大きく分けて二つ。非学習ベース(生成モデル系?)と学習ベース。

  • 非学習ベースは明示的に影響拡散モデル Mを定めている。現実世界ではそう単純なモデルで拡散過程が表現できるとは限らない。

  • 学習ベースは与えられたデータから Mを推定する。が、いろいろ制約や限界があるらしい、というよりは結局ヒューリスティックな解法に頼らざるを得ないようだ。

  • 提案手法は、学習フェーズと推論フェーズの二つのフェーズに分けられる。

  • 学習フェーズでは、tex: p(\mathbf{x})を直接学習することは困難なので、代わりに潜在変数 zを用いて p(\mathbf{x}|z)を用いることを提案している。この時、以下のようなオートエンコーダ( \mathbf{x}から zへエンコード、そしてまた \mathbf{x}へデコード)の最適化問題を解いて zを学習する:

\rm{max}_{\phi, \psi} = \mathbb{E} \left[ p_{\phi}(z | \mathbf{x}) p_{\psi}(\mathbf{x} | z) \right ]
  • さらに、影響拡散モデル Mの学習も行う。提案手法では、以下のようにモデルを二つの関数に分解している:
M = g_{r} \circ g_{u} \left( \mathbf{x}, G; \theta \right)

二つの関数[tex: g{r}, g{u}]はそれぞれaggregationとnormalizationを担当しており、出力 yは最終的な情報の拡散を表現する、らしい。

  • 推論フェーズでは、「連続性」と「完全性」という二つの仮定を置いてから潜在変数 zを用いた推論を行う。

  • 連続性…潜在空間上で近い2点は離散空間上でも性質が近い

  • 完全性…潜在空間上でサンプリングされた点はデコードされた時に「意味がある」内容を含む(?)

結局、推論の場を離散空間 \mathbf{x}から連続空間 zに移しただけである。

  • 残念ながらこの手法ではまだまだオーバーヘッドが大きかったらしく、本研究ではさらに「知識蒸留」(Knowledge Distillation)を導入している

  • 知識蒸留とは、スケールの大きなモデル(教師モデル)の持つ情報を比較的小さなモデル(生徒モデル)に伝達する技術のこと。要するに入出力をできるだけ変えないままスケールの小さなモデルに置き換えること

  • これにより、1) \mathbf{x}のエンコード 2)潜在変数 zを拡散モデル内部でaggregate 3)normalizeの3ステップで行なっていた計算を、生徒モデル M_{s}(z; \lambda)により軽量化できる(グラフ情報とかを破棄することで軽量化している)

  • 実験の結果、汎化性能に問題のあるOIMや、スケーラビリティに問題のあるIMINFECTORなどを抑えて優れた成績を発揮した。

感想

  • テーマとしては面白いが、ユースケースが不明だった。マーケティングにおいて影響力のあるノードに広告を打つなどの例が挙げられていたが、そういった人たちは概して案件で宣伝しているし、そもそもグラフ構造と全てのノードの情報が閲覧できる権限を持ちつつ限られたノードにしか広告を掲載できないという状況とは一体…
  • 申し訳ないが個人的には知識蒸留の方が興味が向いた。よりシンプルなモデルで再学習を行うことで、計算量を改善できるのは単純だが面白い。
  • 推論フェーズの「意味のある」内容では何をもって意味としているのだろうか？

LazyGNN: Large-Scale Graph Neural Networks via Lazy Propagation(ICML 2023)

Author

Rui Xueらのチーム

Link

icml.cc

メモ書き

  • 長距離関係(離れた位置にあるノード同士の関係性のこと?)を捉えることによって性能向上が見られる
  • 従来の手法では、GNNを深層化することによってこれに対処しようとしたが、グラフが大きくなるにつれて計算量が爆発してしまう問題(neighborhood explosion problem)があった
  • これに対する対策はまだまだ制約のあるものが多かった(メモリコスト、性能、サーバ同士の通信確保などなど)
  • 本研究ではそもそも深層化をやめ、浅いGNNのまま長距離依存性を捉えることを目的とする(LazyGNN)
  • 従来のモデルのk番目のiterationにおける初期化/更新式:
\begin{align} \mathbf{X}_{\rm{in}}^{k} &= f\left( \mathbf{X}_{\rm{fea}}, \Theta^{k} \right) \\ \mathbf{X}_{0}^{k} &= \mathbf{X}_{\rm{in}}^{k} \\ \mathbf{X}_{l+1}^{k} &= (1 - \alpha) \tilde{\mathbf{A}}\mathbf{X}_{l}^{k-1} + \alpha \mathbf{X}_{\rm{in}}^{k} \\ \end{align}

に対する検証で、隠れ特徴量 \mathbf{X}_{l}^{k}がすぐに収束しiterationによってほぼ変化していないことがわかった

  • なので、LazyGNNでは真ん中の初期化式を以下のように変更する:
\mathbf{X}_{0}^{k} = (1 - \alpha) \tilde{\mathbf{A}}\mathbf{X}_{L}^{k} + \alpha \mathbf{X}_{\rm{in}}^{k}

  • これにより、前のiterationにおける情報をある程度保持しながら勾配計算を行うことができ、長距離依存性を捉えることができるらしい。

  • backward計算においては、各層の特徴量を保存する必要がなく(従来法ではある)、結果メモリコストの改善につながっている

  • さらにミニバッチ学習(ターゲットノードを中心としたサブグラフによるサンプリング)を導入することによって計算/メモリコストを改善することができる

  • 実験により、LazyGNNは期待通りコストを削減しつつ、他のモデルと比較しても遜色ない予測性能を実現　またミニバッチ学習は予測性能に大きく影響しないことがわかった。

感想

  • 提案手法における初期化の式から長距離依存性を捉えることが本当にできているのか自明ではないなと感じた。第 L層における特徴量には遠距離にいるノードの情報が含まれている、ということだろうか

Alternately Optimized Graph Neural Networks(ICML 2023)

Author

Haoyu Hanらのグループ

Link

icml.cc

メモ書き

  • GNNモデルは以下の二つのアルゴリズムからなる
  • 特徴変換…入力特徴を低次元空間に写像するもの。学習可能なパラメタを持つ

  • 特徴伝搬…グラフ構造を利用して情報を伝搬するもの。the message passing scheme を利用するのが多いらしい。

  • 後者はback-propagationを用いるため計算コストが大きい、なんとかしたい

  • 多くの既存研究では学習において二段階の最適化問題を解いている

\begin{align} \rm{min}_{\Theta, \Phi} &{||f_{\Theta}(\mathbf{F}_{L}) - \mathbf{Y}_{L}||}_{F}^{2}, \nonumber \\ \rm{s.t.} \quad \mathbf{F} = \rm{argmin} &{|| g_{\Phi}(\mathbf{X}) - \mathbf{F}||}_{F}^{2} + \lambda \rm{tr} (\mathbf{F}^{\rm{T}}\mathbf{L}\mathbf{F}) \end{align}
  • 本研究では誤差関数を一つに統一し、最適化すべきパラメタ \Thetaと \mathbf{F}のそれぞれについてiterativeに最適化することを提案(ALT-OPT):
\begin{align} \mathcal{L} = \lambda_{1} {||\rm{MLP}(\mathbf{X};\Theta) - \mathbf{F}||}_{F}^{2} + \rm{tr} (\mathbf{F}^{\rm{T}}\tilde{\mathbf{L}}\mathbf{F}) + \lambda_{2}{||\mathbf{F}_{L} - \mathbf{Y}_{L}||}_{F}^{2} \end{align}

  • 左辺第一項はノード特徴 \mathbf{X}をノード表現(潜在変数) \mathbf{F}に写像すること、第二項は \mathbf{F}に拘束条件を課すこと、第三項は \mathbf{F}_{L}と \mathbf{Y}_{L}との間に関係性を持たせること(ふんわりした説明だな！)を目的としている　なおMLPはおそらく多層パーセプトロンのこと。

  • まず \mathbf{F}について最適化(特徴伝搬に相当?)、その後 \Thetaについて最適化(情報変換に相当?)、これを繰り返す。

  • 前者の最適化は依然としてback-propagationを利用するためコストが大きいが、後者の最適化が頑張るためそこまで回数こなさなくても良いらしく、結果として計算コスト改善につながるらしい。

  • 提案誤差関数第二項の \tilde{\mathbf{L}}は正則化グラフラプラシアンだが、これはローパスフィルタとして機能しており、homophily graphなら有用だがheterophilyでは高周波信号が破棄されるため性能が悪くなる恐れがある

  • これに対する対策として、ALT-OPT-Hを提案:

\begin{align} \mathcal{L} = \lambda_{1} {||\rm{MLP}(\mathbf{X};\Theta) - \mathbf{F}||}_{F}^{2} + \rm{tr} (\mathbf{F}^{\rm{T}}{\tilde{\mathbf{L}}}^{2}\mathbf{F}) + \lambda_{2}{||\mathbf{F}_{L} - \mathbf{Y}_{L}||}_{F}^{2} \end{align}

  • 第二項をいじることで高周波成分も通すようになるらしい。最適化手法は前のものと同じ。

  • 結果、計算効率、メモリ効率ともに良いことが理論的に示され、また実験によりラベリング率が低いノード分類問題において有効な性能を示すことが検証された。

感想

  • 最適化問題における誤差関数を一つに統一したのは面白いが、ハイパーパラメタが増えるという欠点がある。うまい設定ならともかく、まずい設定の場合ではどうなのかを知りたい。

  • どこの研究もGraph Transformerに対抗して計算量の削減を頑張っているんだな、と思った。

参考文献

Leveraging Label Non-Uniformity for Node Classification in Graph Neural Networks(ICML 2023)

Author

Feng Jiらのチーム

Link

icml.cc

メモ書き

  • Node分類において、一様分布とのWasserstein距離を用いたnon-uniformityを導入(この概念自体は前の研究で提言されていた -> [2304.03507] Distributional Signals for Node Classification in Graph Neural Networks )

  • 実験の結果、non-uniformityは(同じラベルに分類される?)ノード集合の境界部分からの距離の指標として用いることができる(non-uniformityが高いと境界部分から遠い)

  • ノード集合の中心部分にある(とされる)ノードは予測の信憑性が高いと言える(周りが同じクラスに分類されるのだから、これも同じクラスだろう、ということ)　逆に境界部分にあるノードは信憑性が低い(違うクラスに分類されるノードが近くにあるので)

  • 以上より、non-uniformityは予測に対する信頼度を測る指標として有効である

  • これらの考察から、2つのアルゴリズムを考えた

  • (半教師あり?)学習によってモデルを学習、予測結果に対してnon-uniformityによって信憑性を評価、評価が高いものを教師データとして信頼して学習データを更新、モデルを再学習

  • 予測結果に対してnon-uniformityを評価、評価が低いものを境界部分と断定、境界部分で構成されるサブグラフを連結性を保持しながらエッジを間引く、間引いた結果を元のグラフに反映させて再学習

  • 一つ目のアルゴリズムは質の良い学習データによる予測性能の向上、二つ目のアルゴリズムは質の悪い(敵対的な)エッジの削除による予測性能の向上が見込める　組み合わせ可能

感想

  • エッジ削減に対する前の研究とは異なるアプローチ。

usapyoi.hatenablog.com

前の研究を見た身としては、エッジの削減方法がランダム抽出で良いのかという疑念が残る。

  • 理論を追えていないので位相幾何学について勉強したいと思った。

  • non-uniformityの概念的な解釈ができていない。周りのノードと分類クラスが同じ→一様性がある→non-uniformityが低い、ではないのか。前の研究を読みたい。

RGE: A Repulsive Graph Rectification for Node Classification via Influence(ICML 2023)

Author

Jaeyun Songらのグループ

Link

icml.cc

メモ書き

  • ノード分類問題:
\begin{align} \theta^{*} &=\rm{argmin} \mathcal{L}_{Tr} (G, theta) \nonumber \\ &= \rm{argmin} \Sigma_{v \in V_{tr}} \mathcal{l}(\hat{y}, y) / N_{Tr} \end{align}

の予測性能を低下させる(と、検証データから推測できる)エッジ(opponent edge)をうまく削除する方法

  • Exhaustive edge Group Elimination(EGE)では、悪影響のあるエッジを順に並べて、上位のものから順番に削除していたが、うまく性能が向上していなかった

  • 本研究ではその理由を、それぞれのエッジの影響度と、複数のエッジによる影響度(group influence)の間には単純な加法がなり立たないからであり、かつその「成り立たなさ」は対象のエッジの位置に依存すると説明している

  • その上で、位置的に近いエッジを削除しすぎないように工夫した削除方法(RGE)を提案

  • EGEを踏襲し影響度によってランク付けするが、エッジの削除によって影響がある(予測値が変化する)ノードを考慮し、直近に削除対象として選んだエッジと影響範囲が被らないエッジを次の削除対象として選定　負の影響力を持つエッジがなくなるまで再学習、再選定する

  • 上記の選択ルールで選択できるものが無くなった時(かつ誤差がまだ大きい時?)は従来手法通り近いエッジを削除することを許容する

  • 実験の結果、SGC Squirrelのようなgroup influenceの推定誤差が大きいものを除き多くの場合で性能が改善された

感想

  • 最初のiterationで削除したノード集合と次のiterationで削除したノード集合との間に「group influence」は存在しないのだろうか？少なくとも論文中では言及がなかったが、opponent edgeを削除するのではなく、重みを減衰させるようにすれば(そしてopponentでなければenhanceする)、最初のiterationでopponent判定されても後々敗者復活してくる可能性が残せるのではないかと思った

JSAI2023 4日目感想 : 時系列予測における人工データを用いたデータ拡張

背景

時系列データ予測において訓練データの足りなさが問題で、データを水増しするか転移学習するかしないと予測精度が上がらない。

関連研究

自動生成した人工的な時系列データ(人工データ)を用いてモデルを事前に学習しておく転移学習を行った研究がある(すげー)。しかし、タスクは時系列分類であり、予測ではない。

時系列予測手法ではNeural Laplaceが提案されている。これは元々の時系列データを関数で表現したものをラプラス変換して得られる像関数をモデル化するらしい(すげー)。

提案手法

元データに人工データを追加したものを訓練データとし、さっきのNeural Laplaceを用いて学習させる。なお、この時の目的関数を、先行研究での予測系列のみを対象とした誤差から、入力系列も含めた誤差に変更する。

結果

予備実験として、さっき再定義した目的関数でもちゃんと学習できるか確かめた。また、メインの実験として予測性能を確かめたところ、人工データ+元データによって予測性能が向上することがわかった。また、元データの数を半分に減らしても問題なかった。

感想

人工データは元データと全く関係のないデータなのに予測性能が上がるのはすごいと思った。ラプラス空間上で人工データと元データとの親和性が高かったのか、人工データによってモデルの正規化が行われたのかはわからないが、人工データの有用性が確かめられましたね、といった感じ。

JSAI2023 4日目感想 : 抽象的な商品画像を学習したCVAEに基づく商品画像生成モデルの提案

背景

ECサイト上で顧客は各商品に付与された商品情報、特に視覚情報である画像に注目して判断する。なので、顧客のニーズをとらえた商品画像があれば売り上げが上がる。

関連研究

顧客は何らかのキーワードを属性として指定して検索し、得られた商品一覧の商品情報を読んで購入するが、顧客が指定した属性と、本当に顧客が望んでいる属性が一致しているとは限らない。従来手法ではこの潜在的なニーズを判断しきれなかった。抽象的な属性(例えば「かわいい」や「上品」など)の場合顧客の潜在的なニーズとの乖離を引き起こしにくい。よって、商品の抽象的な属性が商品画像に与える影響のモデル化ができれば、主観によって判断される具体的な属性に依存せずに商品画像を捉えられるので、顧客の潜在的ニーズに合致した商品画像の生成が可能になる。

提案手法

Latent Dirichlet Allocation(LDA)によって商品説明文から抽象的な属性を抽出、その後Conditional Variational Autoencoder(CVAE)を、抽象的な特徴を入力、元商品の画像を出力とした学習を行う。学習後は、任意の抽象的な属性に対して画像を生成する。

結果

LDAによって抽象的な情報を抽出することができた。CVAEにおいて元画像の再構成もうまくできており、学習もうまくいっている。しかし、特定の商品についての抽象的属性に、任意の属性を追加して画像を生成した場合について、あんまり元々の画像と変わらなかった。

感想

抽出された属性に対して、CVAEの中で重要な属性とそうでない属性があって、属性を追加しても生成される画像に影響されないのかなと思った。できるだけ各属性の重要度が均等になるように目的関数を調整するとかできないのでしょうか。L2正則化を強くすればなんとかなるかな…