Revealing graph bandits for maximizing local influence
Abstractの概要
本論文は、グラフ構造に関する事前知識がない状況で、グラフ内で最も影響力のあるノードを特定することを目的としたグラフバンディット問題を研究している。各ラウンドにおいて、学習者はノードを選択し、そのノードが現在影響を与えている確率的なノード集合を観測する。影響は直接の隣接ノードに限定されるローカル影響モデルが採用されている。著者らはBARE（Bandit Revelator）という二段階戦略を提案しており、まず一様ランダム探索により有望なノードを特定し、次に縮小された候補集合に対してバンディットアルゴリズム（GraphMOSS）を実行する。分析では、検出可能次元（detectable dimension）という問題依存の量を導入しており、これはノードの総数よりも大幅に小さくなり得る量であり、有利なグラフ構造においてリグレットを支配する。
新規性
本研究の独自の貢献は、グラフが最初は未知であり、学習者の行動を通じて徐々に明らかになるグラフバンディットの定式化にある。これは、部分的または完全なグラフ知識（例えば少なくとも2次近傍情報）を仮定する先行研究とは異なる。論文は検出可能次元を導入し、それを用いてBAREのリグレット保証を導出し、グラフ全体を事前にスキャンすることなく構造情報を活用できることを示している。
成果
主要な理論的結果として、BAREの期待リグレットがC·min(r⋆n, D⋆r⋆ + √(r⋆nD⋆) + nε⋆)で上界されることが示されており、D⋆は検出可能次元、ε⋆は影響力ギャップである。無向グラフ（ε⋆=0）の場合、これはD⋆がdを置き換えたミニマックス最適レートと一致する。定数倍を除いたマッチする下界も提供されている。Barabási-Albert（d=1000）、Facebook（d=4039）、Enron（d=36692）、Gnutella（d=10879）グラフでの実験では、BAREがGraphMOSSよりも早く有望なノードを特定し、中心性の高いネットワークや影響確率が高い場合により大きな優位性を示すことが確認された。
論文の注目点
- 本設定ではグラフに関する事前知識を仮定しない：ノードを選択した後、学習者はそのノードが現在影響を与えている確率的なノード集合（明らかになった隣接ノード）のみを観測し、ネットワーク構造全体は観測できない。
- BAREは一様ランダム探索フェーズと縮小された候補集合に対するバンディットフェーズを組み合わせており、そのリグレットはノードの総数dに直接依存するのではなく、検出可能次元D⋆（dよりも大幅に小さくなり得る）に依存する。
- 実験結果は、グラフ非依存のGraphMOSSベースラインに対するBAREの優位性が中心性の高いネットワーク（Facebook、Enron）で顕著であり、より分散的なGnutellaネットワークでは小さく、影響を受けた隣接ノードが明らかになる確率が高いほど優位性が増大することを示している。