Active Learning on Adversarially Corrupted Graphs

기술 요약: 적대적으로 오염된 그래프에서의 능동 학습 (Active Learning on Adversarially Corrupted Graphs)

문제 정의
본 논문은 기저 구조가 적대적 요소에 의해 조작된 그래프에서의 능동 학습(active learning) 문제를 다룹니다. 설정에는 초기 "지상 진실(ground-truth)" 그래프 $G^* = (V^*, E^*)$와 일련의 오염된(악의적인) 정점 집합 $I$가 포함됩니다. 예산 $b$를 가진 적대자는 다음 세 단계를 통해 최종 그래프 $G$를 구성합니다:

1. 새로운 정점 집합 $I$($|I| \le |V^*|$) 위에 임의의 부분 그래프를 생성합니다.
2. $V^*$의 정점 중 최대 $b$개를 집합 $I$에 연결합니다. 이는 적대자의 권한을 정의하며, $G$ 내에서 $I$의 경계(frontier) 크기는 $b$로 제한됩니다 (즉, $|\partial_G(I)| \le b$).
3. $G^*$ 내부에 임의로 에지를 추가합니다.

알고리즘은 결과 그래프 $G$를 전달받으며, 쿼리된 정점이 $I$에 속하는지 여부를 밝혀주는 레이블 오라클(label oracle) $O_{G,I}$에 접근할 수 있습니다. 목표는 높은 확률로 최소한의 레이블 쿼리를 사용하여, $\hat{I}$라는 부분 집합을 찾아내어 $|\hat{I} \triangle I| \le \gamma |V(G)|$를 만족하는 **약한 복구(weak recovery)**를 달하는 것입니다. 과제는 $G^*$와 오염된 부분 그래프 $G[I]$가 임의적일 수 있으며, 적대자가 그래프 구조를 크게 조작할 수 있다는 점입니다 (단, $G^*$와의 연결 수는 작게 유지됨).

방법론
제안된 솔루션은 **정점 확장성(vertex expansion)**의 구조적 특성과 재귀적 알고리즘 프레임워크에 의존합니다.

1. 구조적 통찰: 핵심 직관은 만약 오염된 정점 집합 $I$가 그래프의 "좋은" 부분들에 비해 현저히 작은 정점 확장성을 가진다면, 이를 격리할 수 있다는 것입니다. 구체적으로, 저자들은 $I$가 나머지 그래프에 비해 "확장성이 낮은(poorly expanding)" 상태인 조건을 정의합니다. 만약 $I$가 특정 확장 간극(expansion gap) 조건을 만족한다면, 작은 경계를 가지며 $I$와 크기가 유사한 임의의 집합 $S$는 $I$와 밀접하게 상관되어 있어야 합니다.

2. 알고리즘 핵심 (Sum-of-Squares): 이 문제를 해결하기 위해 저자들은 Sum-of-Squares (SoS) 알고리즘을 활용하며, 특히 Feige 등(2005)이 제안한 정점 확장에 관한 반정부호 계획법(semidefinite programming, SDP) 완화 기법을 수정하여 적용합니다.

   • 표준 정점 확장 알고리즘은 종종 반환된 집합의 크기를 보장하지 못하거나, 이 특정한 적대적 설정에 대해 너무 느슨한 근사 계수를 제공하는 경우가 많습니다.
   • 저자들은 차수-4(degree-4) SoS 완화에 대한 새로운 **라운딩 알고리즘(rounding algorithm)**을 도입합니다. 이 라운딩은 출력 집합 $S$가 크기 제약 조건(구체적으로 $|S| = \Theta(|I|)$)을 만족하면서도 작은 경계를 유지하도록 보장합니다.
   • 이러한 적응을 통해 알고리즘은 크기 제약 조건 하에서 최소 정점 확장에 근사하는 집합 $S$를 찾을 수 있으며, 이는 독립적인 관심사로서의 결과입니다 (정리 4).

3. 재귀적 정제 (Recursive Refinement): 알고리즘은 반복적으로 작동합니다:

   • SoS 기반 절차를 사용하여 남은 오염된 정점들과 높은 상관관계를 갖는 집합 $S$를 찾습니다.
   • $S$와 그 여집합의 작은 무작위 샘플에 대해 오라클을 쿼리하여, 어느 집합에 더 많은 오염된 노드가 포함되어 있는지 결정합니다.
   • 식별된 집합을 그래프에서 제거하고, 잔여 그래프(residual graph)에 대해 과정을 반복합니다.
   • 저자들은 이러한 반복 과정 중에도 구조적 특성(특히 남은 지상 진실 그래프의 정점 확장성)이 충분히 보존되어, 높은 비율의 정점이 식별될 때까지 알고리즘이 계속해서 오염된 노드를 복구할 수 있음을 증명합니다.

주요 결과
주요 기여는 약한 복구를 위한 쿼리 복잡도를 확립하는 정리 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$에 선형적이며, 그래프의 연결성(정점 확장성)에 비해 적대자의 예산이 작다는 전제하에 원하는 정확도 $\gamma$에 반비례합니다.

또한, 정리 4는 보조적인 결과를 제시합니다: 균형 잡힌 범위 $[m, n-m]$ 내의 크기를 가지면서 작은 정점 확장을 갖는 집합을 찾는 무작위 다항 시간 알고리즘을 제시하며, 특정 파라미터에 대해 $O(\sqrt{\log n})$의 근사 계수를 달성합니다. 이는 소 집합 확장(small-set expansion) 문제에 대한 기존 경계들을 개선하거나 보완합니다.

의의 및 주장
본 논문은 정점 확장성이 구조적 적대 공격에 강건한 능동 학습 알고리즘의 쿼리 복잡도를 결정하는 근본적인 척량임을 최초로 입증했다고 주장합니다.

• 신규성: Sybil 공격이나 그래프 포이즈닝(graph poisoning)에 관한 기존 연구들이 흔-그래프(good graph)가 확장자(expander)라고 가정하거나 추가된 에지의 수를 제한하는 것과 달리, 본 모델은 두 부분 그래프 모두의 내부 구조는 임의적이지만 오직 *경계(boundary)*의 크기만을 제한합니다.
• 이론적 토대: 이 연구는 그래프 연결성(정점 확장성)과 오염된 노드 탐지의 가능성 사이의 이론적 연결 고리를 제공합니다. 지상 진실 그래프가 전역적 확장자가 아니더라도, 적대자의 예산이 충분히 큰 부분 집합의 확장성에 비해 작다면 약한 복구가 가능하다는 것을 보여줍니다.
• 알고리즘적 기여: 본 논문은 Sum-of-Squares 기법을 활용하고 적응시킴으로써, 계산적으로 어려운 문제로 알려진 크기 제약 하의 작은 정점 확장을 갖는 집합을 찾는 다항 시간 알고리즘을 소개합니다.

저자들은 자신의 결과가 특정 확장 간극에 의존하며, 원하는 정확도 $\gamma$가 감소하거나 적대자의 예산 $b$가 증가함에 따라 쿼리 복잡도가 저하된다는 점을 언급하며 신중한 태도를 유지합니다. 이들은 모든 가능한 그래프 구조나 임의의 적대자 예산에 대한 문제를 해결한다고 주장하는 것이 아니라, 입력 그래프의 구조적 특성, 쿼리 비용, 그리고 정확도 사이의 정밀한 트레이드오프(trade-off)를 확립하는 데 목적을 두고 있습니다.