Correlation Clustering

Correlation clustering은 그래프의 정점들을 cluster들로 분할하는데, 각 간선 $e$에는 두 종류의 weight $w_{e}^{+}$와 $w_{e}^{-}$가 있다. 두 endpoint가 같은 cluster에 있으면 $w_{e}^{+}$점, 다른 cluster에 있으면 $w_{e}^{-}$점을 얻는다. 목표는 점수의 합을 최대화하는 clustering을 찾는 것이다. 이 문제는 NP-hard임이 알려져 있고, Max cut처럼 SDP를 이용한 constant factor approximation이 알려져 있다.
이번에도 직관적인 $0.5$-approximation이 있는데, 모든 정점을 한 cluster에 놓거나 / 정점을 다 다른 cluster에 두거나 둘 중 나은 것이 최적해의 절반 이상이 된다. SDP를 이용하여 $0.75$-approximation을 얻을 것이다.

사실 이런 maximization problem이라고 해도 $2$-approximation, $1.33$-approximation 처럼 역수로 쓰는 게 보통인데, 혼란을 방지하기 위해 이번에는 $1$보다 작은 수로 표기한다.

NP-hardness

이거 대충 날먹하려고 했는데 생각보다 어렵다;; 정확히는 unweighted variant의 hardness를 구하는 것이 어렵다.
Multiway-cut problem은 terminal set $s_{1}, \cdots, s_{k}$가 주어졌을 때 각각을 전부 disconnect하는 edge set의 weight를 minimize하는 문제이다. $k=2$일 때 유명한 $(s, t)$ min cut 문제가 되지만, 일반적인 $k$에 대해서는 NP-hard임이 알려져 있다.

Multiway cut problem의 instance가 주어졌을 때, 원래 간선 $e$의 weight가 $w_{e}$였다면 $w_{e}^{+} = 0, w_{e}^{-} = w_{e}$로 assign해주고, 특히 $s_{i}, s_{j}$를 잇는 $w(s_{i}, s_{j})^{+} = -\infty, w(s_{i}, s_{j})^{-} = 0$의 간선을 추가해주고 correlated clustering을 찾으면 그게 곧 multiway cut이 되므로 NP-hardness가 증명된다.

그럼 Multiway cut의 hardness는 어떻게 보이냐? 그건 나중에 다룰 일이 있겠지..

SDP relaxation

지난 번 MAX-CUT 문제에서는 각 정점을 $\mathbf{S}^{n-1}$의 한 축을 기준으로 분할하는 방법을 생각했었다. 이번에도 아이디어는 비슷한데, 우선 원본 문제를 아래와 같이 나타낼 수 있다.
$$\begin{aligned} \mathrm{maximize} & \sum_{(i, j) \in E} w_{ij}^{+} (v_{i} \cdot v_{j}) + w_{ij}^{-} (1 - v_{i} \cdot v_{j}) \\ \mathrm{s.t.} & v_{i} \in \lbrace \mathbf{e} _ {1}, \cdots, \mathbf{e} _ {n} \rbrace \end{aligned}$$

이번에도 똑같이 $v_{i} \cdot v_{i} = 1$로 relax한 뒤 SDP를 풀어주면 될 것 같다. 다만 이번엔 원본인 Integer program의 특성상 모든 성분이 양수면 좋을 것 같은데, 이 제약조건을 어떻게 modeling해줄 수 있을까? 단순히 생각해서, 두 벡터의 각도가 90도 이하여야 하니 $v_{i} \cdot v_{j} \ge 0$을 제약 조건으로 걸어주자. 이래도 여전히 SDP가 된다.

이제 이걸 rounding해줘야 한다. 놀랍게도 축을 두 개 잡아주는 것만으로 꽤 좋은 근사치를 얻을 수 있다.
두 독립인 벡터 $r_{1}, r_{2} \in \mathbf{S}^{n-1}$에 대해 $r_{1} \cdot v_{i}, r_{2} \cdot v_{i}$의 부호에 따라, 총 4개의 cluster를 만들어주자.

MAX CUT에서, 두 벡터 $v_{i}, v_{j}$가 $r_{1}$을 기준으로 같은 쪽에 있을 확률은 $1 - \frac{\cos^{-1}(v_{i} \cdot v_{j})}{\pi}$임을 보였다. 따라서, $v_{i}, v_{j}$가 같은 클러스터에 있을 확률은 $(1 - \frac{\cos^{-1}(v_{i} \cdot v_{j})}{\pi})^{2}$가 된다. 따라서 간선 $(i, j) \in E$에서 얻을 수 있는 점수의 기댓값은
$$w_{ij}^{+}\left(1 - \frac{\cos^{-1}(v_{i} \cdot v_{j})}{\pi}\right)^{2} + w_{ij}^{-}\left(1 - \left(1 - \frac{\cos^{-1}(v_{i} \cdot v_{j})}{\pi}\right)^{2}\right)$$
가 된다. 당연하지만, 이제 이 식을 $C \times \left[ w_{ij}^{+} (v_{i} \cdot v_{j}) + w_{ij}^{-} (1 - v_{i} \cdot v_{j}) \right]$로 lower bound해야 한다.

Lemma. $0 \le x \le 1$에 대해, $(1 - \cos^{-1}(x)/\pi)^{2} \ge 0.75x$.
또한, $(1 - (1 - \cos^{-1}(x) / \pi)^{2}) \ge 0.75(1-x)$.

Proof. $(1 - x/\pi)^{2} - 0.75\cos x$가 $[0, \pi/2]$에서 $[0, 0.25]$에 들어감을 증명하면 된다. 남은 증명은 Wolframalpha가 해준다.

References

• https://www.designofapproxalgs.com/book.pdf