Active Learning on Adversarially Corrupted Graphs

技術的要約：敵対的に改ざんされたグラフにおける能動学習

問題定式化
本論文は、基礎となる構造が敵対者によって改ざんされたグラフにおける**能動学習（active learning）**の問題を扱っている。設定としては、初期の「真の」グラフ $G^* = (V^*, E^*)$ と、一連の改ざんされた（悪意のある）頂点集合 $I$ が存在する。予算 $b$ を持つ敵対者は、以下の3つのステップを通じて最終的なグラフ $G$ を構築する：

1. 新規の頂点集合 $I$（ここで $|I| \le |V^*|$）上の任意の部分グラフを作成する。
2. $V^*$ から $I$ への接続を最大 $b$ 個の頂点に限定して接続する。これが敵対者の権限を定義する：$G$ における $I$ の境界（frontier）のサイズは $b$ によって制限される（すなわち $|\partial_G(I)| \le b$）。
3. $G^*$ 内に任意のエッジを追加する。

アルゴリズムは、結果として得られたグラフ $G$ を受け取り、クエリされた頂点が $I$ に属するかどうかを明らかにするラベル・オラクル $O_{G,I}$ にアクセスできる。目標は、高い確率で、最小限のラベル・クエリ数を用いて、$\hat{I}$ という部分集合（$\hat{I}$ は $I$ を近似するもの）を特定し、対称差 $|\hat{I} \triangle I| \le \gamma |V(G)|$ を達成することである。課題は、$G^*$ と改ざんされた部分グラフ $G[I]$ が任意であり、かつ敵対者が接続数を小さく抑えつつも、グラフ構造を大幅に操作できる点にある。

手法
提案されている解決策は、**頂点拡大率（vertex expansion）**という構造的特性と、再帰的なアルゴリズムの枠組みに基づいている。

1. 構造的洞察: コアとなる直感は、もし改ざんされた頂点集合 $I$ が、グラフ $G^*$ の「良質な」部分よりも著しく小さい頂点拡大率を持つならば、それは分離可能であるということである。具体的には、著者らは $I$ が残りのグラフに対して「拡大率が低い（poorly expanding）」状態であるという条件を定義している。もし $I$ が特定の拡大率のギャップ条件を満たしているならば、小さな境界を持ち、かつ $I$ と同程度のサイズを持つ任意の集合 $S$ は、$I$ と強く相関していなければならない。

2. アルゴリズムの中核 (Sum-of-Squares): このような集合 $S$ を見つけるために、著者らはSum-of-Squares (SoS) アルゴリズムを応用している。具体的には、Feige et al. (2005) によって提案された頂点拡大率のための半正定値計画法（SDP）緩和を修正している。

   • 標準的な頂点拡大アルゴリズムは、返される集合のサイズを保証できなかったり、この特定の敵対的設定に対して近似係数が緩すぎたりすることが多い。
   • 著者らは、次数4のSoS緩和に対する新しい**丸めアルゴリズム（rounding algorithm）**を導入している。この丸めにより、出力される集合 $S$ が（特に $|S| = \Theta(|I|)$ という）容量制約を満たしながら、小さな境界を維持することが保証される。
   • この適応により、アルゴリズムはサイズ制約の下で最小頂点拡大率を近似する集合 $S$ を見つけることが可能となる（これは独立した関心事でもある：定理4）。

3. 再帰的洗練 (Recursive Refinement): アルゴリズムは反復的に動作する：

   • SoSベースの手順を用いて、残りの改ざんされた頂点と高い相関を持つ集合 $S$ を見つける。
   • $S$ およびその補集合の小さなランダムサンプルに対してオラクルにクエリを行い、どちらの集合に改ざんされたノードが多数含まれているかを判定する。
   • 特定された集合をグラフから除去し、残ったグラフに対してプロセスを繰り返す。
   • 著者らは、構造的特性（具体的には残存する真のグラフの頂点拡大率）がこれらの反復を通じて十分に保持され、高割合の改ざんノードが特定されるまでアルゴリズムが継続できることを証明している。

主要な結果
主な貢献は、弱回収（weak recovery）のクエリ複雑性を確立する定理3である。アルゴリズムは、以下の条件下で $(\gamma, \delta, q, b)$-弱回収を達成する：

• クエリ予算 $q$ は $\tilde{O}\left(\frac{1}{\gamma} (\log \frac{1}{\delta} + b\sqrt{\log n})\right)$ とスケールする。
• 敵対者の予算 $b$ は、真のグラフ $G^*$ の頂点拡大率によって制限される：$b \le O\left(\frac{\gamma^6}{\log^3(1/\gamma)\sqrt{\log n}} \cdot \partial_{\eta n}(G^*)\right)$。ここで $\partial_{\eta n}(G^*)$ は、サイズが少なくとも $\eta n$ である部分集合の最小境界である。

本質的に、必要なクエリ数は、敵対者の予算 $b$ に対して線形であり、かつグラフの連結性（頂点拡大率）に対して反比例する。ただし、これは敵対者の予算がグラフの連結性に対して十分に小さい場合に限られる。

さらに、定理4は補助的な結果を提示している。これは、バランスの取れた範囲 $[m, n-m]$ 内のサイズを持ち、かつ小さな頂点拡大率を持つ集合を見つける、ランザム化多項式時間アルゴリズムであり、特定のパラメータに対して $O(\sqrt{\log n})$ の近似係数を達成する。これは、スモールセット拡大問題（small-set expansion problems）に関する既存の境界を改善、あるいは補完するものである。

意義と主張
本論文は、頂点拡大率が、構造的な敵対的攻撃に対して頑健な能動学習アルゴリズムのクエリ複雑性を決定する基本的な尺度であることを示した最初の研究であると主張している。

• 新規性: Sybil攻撃やグラフ・ポイズニングに関する従来の研究は、「良質な」グラフがエキスパンダーであることを前提としたり、追加されたエッジの数を制限したりすることが多かったが、本モデルでは、境界のサイズのみを制限することで、両方の部分グラフ（良質な部分と悪い部分）における任意の内部構造を許容している。
• 理論的根拠: 本研究は、グラフの連結性（頂点拡大率）と、改ざんされたノードを検出することの実現可能性との間の理論的なつながりを提供している。真のグラフがグローバルなエキスパンダーでなくても、十分大きな部分集合の拡大率に対して敵対者の予算が小さい限り、弱回収が可能であることを示している。
• アルゴリズム的貢献: 本論文は、Sum-of-Squaresの手法を活用・適応することで、容量制約の下で小さな頂点拡大率を持つ集合を見つけるアルゴリズム（計算量的に困難であることが知られている問題）を導入している。

著者らは控えめなトーンを維持しており、彼らの結果が特定の拡大率のギャップに依存していること、また、望ましい精度 $\gamma$ が減少するか、あるいは敵対者の予算 $b$ が増加するにつれて、クエリ複雑性が低下することを指摘している。彼らは、あらゆる可能なグラフ構造や任意の敵対者予算に対して問題を解決すると主張しているのではなく、入力グラフの構造的特性と、クエリコストおよび精度の間の正確なトレードオフを確立している。