Active Learning on Adversarially Corrupted Graphs

Technical Summary: Active Learning on Adversarially Corrupted Graphs

Problem Formulation
The paper addresses the problem of active learning on graphs where the underlying structure has been tampered with by an adversary. The setting involves an initial "ground-truth" graph $G^* = (V^*, E^*)$ and a set of corrupted (malicious) vertices $I$. An adversary with a budget $b$ constructs a final graph $G$ through three steps:

1. Creating an arbitrary subgraph on a set of fresh vertices $I$ (where $|I| \le |V^*|$).
2. Connecting at most $b$ vertices from $V^*$ to the set $I$. This defines the adversary's power: the size of the frontier of $I$ in $G$ is bounded by $b$ (i.e., $|\partial_G(I)| \le b$).
3. Arbitrarily adding edges within $G^*$.

The algorithm receives the resulting graph $G$ and has access to a label oracle $O_{G,I}$, which reveals whether a queried vertex belongs to $I$. The goal is to achieve weak recovery: identifying a subset $\hat{I}$ such that the symmetric difference $|\hat{I} \triangle I| \le \gamma |V(G)|$ with high probability, using a minimal number of label queries. The challenge lies in the fact that $G^*$ and the corrupted subgraph $G[I]$ can be arbitrary, and the adversary can manipulate the graph structure significantly, provided the number of connections to the original graph remains small.

Methodology
The proposed solution relies on the structural property of vertex expansion and a recursive algorithmic framework.

1. Structural Insight: The core intuition is that if the set of corrupted vertices $I$ has a significantly smaller vertex expansion than the "good" parts of the graph $G^*$, it can be isolated. Specifically, the authors define a condition where $I$ is "poorly expanding" relative to the rest of the graph. If $I$ satisfies a specific expansion gap condition, any set $S$ with a small boundary and size comparable to $I$ must be heavily correlated with $I$.

2. Algorithmic Core (Sum-of-Squares): To find such a set $S$, the authors adapt Sum-of-Squares (SoS) algorithms, specifically modifying the semidefinite programming (SDP) relaxation for vertex expansion proposed by Feige et al. (2005).

   • Standard vertex expansion algorithms often fail to guarantee the size of the returned set or provide approximation factors that are too loose for this specific adversarial setting.
   • The authors introduce a novel rounding algorithm for the degree-4 SoS relaxation. This rounding ensures the output set $S$ satisfies cardinality constraints (specifically, $|S| = \Theta(|I|)$) while maintaining a small boundary.
   • This adaptation allows the algorithm to find a set $S$ that approximates the minimum vertex expansion subject to size constraints, a result of independent interest (Theorem 4).

3. Recursive Refinement: The algorithm operates iteratively:

   • It uses the SoS-based procedure to find a set $S$ that is highly correlated with the remaining corrupted vertices.
   • It queries the oracle on a small random sample of $S$ and its complement to determine which set contains the majority of corrupted nodes.
   • The identified set is removed from the graph, and the process repeats on the residual graph.
   • The authors prove that the structural properties (specifically the vertex expansion of the remaining ground-truth graph) are preserved sufficiently through these iterations, allowing the algorithm to continue recovering corrupted nodes until a high fraction is identified.

Key Results
The main contribution is Theorem 3, which establishes the query complexity for weak recovery. The algorithm achieves $(\gamma, \delta, q, b)$-weak recovery if:

• The query budget $q$ scales as $\tilde{O}\left(\frac{1}{\gamma} (\log \frac{1}{\delta} + b\sqrt{\log n})\right)$.
• The adversary's budget $b$ is bounded by the vertex expansion of the ground-truth graph $G^*$: $b \le O\left(\frac{\gamma^6}{\log^3(1/\gamma)\sqrt{\log n}} \cdot \partial_{\eta n}(G^*)\right)$, where $\partial_{\eta n}(G^*)$ is the minimum frontier of subsets of size at least $\eta n$.

Essentially, the number of queries required is linear in the adversary's budget $b$ and inversely proportional to the desired accuracy $\gamma$, provided the adversary's budget is small relative to the graph's connectivity (vertex expansion).

Additionally, Theorem 4 presents an auxiliary result: a randomized polynomial-time algorithm that finds a set with small vertex expansion and size within a balanced range $[m, n-m]$, achieving an approximation factor of $O(\sqrt{\log n})$ for certain parameters. This improves upon or complements existing bounds for small-set expansion problems.

Significance and Claims
The paper claims to be the first to demonstrate that vertex expansion is a fundamental measure determining the query complexity of active learning algorithms robust to structural adversarial attacks.

• Novelty: Unlike previous work on Sybil attacks or graph poisoning which often assumes the "good" graph is an expander or bounds the number of added edges, this model allows for arbitrary internal structures in both the good and bad subgraphs, bounding only the boundary size.
• Theoretical Grounding: The work provides a theoretical link between graph connectivity (vertex expansion) and the feasibility of detecting corrupted nodes. It shows that even if the ground-truth graph is not a global expander, weak recovery is possible as long as the adversary's budget is small compared to the expansion of sufficiently large subsets.
• Algorithmic Contribution: The paper introduces a polynomial-time algorithm for finding sets with small vertex expansion under cardinality constraints, a problem known to be computationally hard, by leveraging and adapting Sum-of-Squares techniques.

The authors maintain a modest tone, noting that their results rely on specific expansion gaps and that the query complexity degrades as the desired accuracy $\gamma$ decreases or the adversary's budget increases. They do not claim to solve the problem for all possible graph structures or arbitrary adversary budgets, but rather establish a precise trade-off between query cost, accuracy, and the structural properties of the input graph.