Paper list

• Learning Combinatorial Optimization Algorithms over Graphs ¹
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs²

Learning Combinatorial Optimization Algorithms over Graphs

• 그래프 임베딩과 RL 이용한 문제 해결
• 그래프 임베딩으로 Action 정해줌, MDP 세팅
• Minimum Vertex Cover, Maximum Cut, TSP 문제에 적용함 (일반적인 문제에 적용가능)

Traditional Approaches

• Exact algorithm
  • 열거, branch-and-bound(integer programming formulation) -> 문제가 크면 못 풀 정도로 시간 소요
• Approximation
  • Polynomial-time approximation algorithms -> 이상적이나 Optimality 보장되지 않음, 존재하지 않을 수 있음
• Heuristics
  • 효과적이고 빠르나 이론적인 근거 존재하지 않음, 알고리즘 만들때 많은 trial and error, problem-specific함

그래프 최적화문제 \({G}\)가 주어지고 데이터 분포 \({D}\)를 모를때 heuristics 보다 나은 알고리즘으로 학습할 수 있을까?

이전 페이퍼들과 다른 점

• Algorithm design pattern
  • greedy로 디자인 하였음. Graph constraints 존재
• Algorithm representation
  • 그래프 임베딩으로 structure2vec을 사용
• Algorithm training
  • n-step Q-learning, Fitted Q-iteration 사용 (delayed reward 고려)

weighted graphs \({ G(V,E,w) }\) 로 표현가능

\({V}\) -> Vertex, Node

\({E}\) -> Edge

\({w}\) -> weight

함수 \({w: E\rightarrow\mathbb{R^+}}\)

\(w(u,v)\) , \(\left( u,v \right) \in E\)

Minimum Vertex Cover (MVC)

• 최소한의 노드로 모든 edge 찾는 문제

Maximum Cut (MAXCUT)

• Cut-set의 합이 최대화 되도록 edge의 개수를 찾는 문제

Traveling Salesman Problem (TSP)

• 모든 node를 한번씩만 돌면서 weight를 최소화 하는 문제. 여행경로.

문제들에 대해 알고리즘을 일반적으로 표현 가능

1. A problem instance \({ G }\) ~ \({ D }\)

2. Partial Solution -> ordered list

   \[S=\left( v_{ 1 },\quad { v }_{ 2 },\quad \cdots ,\quad { v }{ \left| S \right| } \right)\]

   \(\overline { S }\) : 추가가능한 노드들, given S

   binary decision variables \({x}\), \({x}_{v}=1\) if \(v\in S\), \(x_v=0\) otherwise

3. A maintenance procedure \(h(S)\) -> maps \({S}\) to constraints

4. quailityt of partial solution S objective function \(C(h(s), G)\)

5. Greedy 알고리즘을 이용해 node \(v\) 선택 -> \(Q(h(S), v) \in \mathbb{R}\)를 최대화 시키는 노드 그리고 선택된 \(V^*\)를 \(S\)에 추가

   \[S:=\left( S, { v }^{ * } \right) ,\quad where\quad { v }^{ * }:=\underset { v\in \bar S }{ argmax }Q\left( h(S), v \right)\]

6. termination criterion \(t\left( h(S) \right)\) 가 만족될때까지 반복

모든 문제가 다른 \(h(S)\), \(c\), \(t\) 들로 표현 가능

MVC

helper function x,

\(t\): 모든 엣지 사용 확인

MAXCUT

helper function divides \(V\) into two sets \(\left( S, \overline { S } \right)\) & maintains a cut-set \(C=\left\{ \left( u,v \right) |\left( u,v \right) \in E,\quad u\in S,\quad v\in \overline { S } \right\}\),

\(c\left( h(S),G \right) =\sum _{ (u,v)\in C }^{ }{ w\left( u,v \right) }\),

termination x

TSP

\(h\) maintains tour (node orders),

terminate when \(S=V\)

Representation: Graph Embedding

structure2vec : 각 노드들은 p-dimension의 feature embedding \(\mu_v\) 갖고있음, \(v\in V\)

\(F\): generic non-linear mapping(NN, kernel function)

\(N(v)\): set of neighbors

-> 이웃 노드들의 feature, weight를 이용해 새로운 \(\mu_v^{t+1}\) 생성

-> 위 연산을 \(T\)번 반복하면 T-hop의 정보를 얻는 것으로 생각할 수 있음 (usually \(T=4\))

뉴럴넷 이용해 다시 적어보면, 위 식은

로 표현할 수 있다.

\(\theta_1\in\mathbb{R}^\rho \quad\), \(\theta_2,\theta_3\in\mathbb{R}^{\rho \times \rho \quad }\), \(\theta_4\in\mathbb{R}^\rho\)

각 파라미터는 위와 같은 차원을 갖고 차근차근(?) 따져보면 \(\mu_v^{t+1}\)는 \(\rho\) 차원을 갖는것을 확인할 수 있다.

위 연산은 각 노드들의 feature를 구하는 과정이고 이 구해진 feature들을 이용해 estimated Q 또한 뉴럴넷 이용해 구한다.

\(\theta_5\in \mathbb{R}^{2\rho} \quad\), \(\theta _{ 6 },\theta _{ 7 }\in { R }^{ \rho \times \rho } \quad\), \([\cdot , \cdot ]: Concatenation\)

-> 해당 노드의 feature + 모든 feature의 합(global feature)를 concatenation 한다.

Training: Q-learning

앞에서 정의했던 \(\hat{Q}\)를 RL의 state-value function으로 간주

\(\hat{Q}\)는 다른 분포, 사이즈를 갖고있는 \({ D },\; D=\left\{ G_i \right\}_{i=1}^m\)에 대해 학습함

RL formulation

• States: \(\sum_{v\in V}{\mu_v}\)

• Transition: deterministic (MDP세팅)

• Actions: a node of G not in S

• Rewards:

-> 새로운 state에서의 cost는 커져야 하고 현재의 state에서의 cost는 작아야 함 -> 현재 cost가 작게 되도록 선택해야 함

• Policy: greedy policy

optimal Q-function은 \(Q^\ast\)로 표기

Learning algorithm

n-step Q-learning, fitted Q-iteration

노드를 다 추가하면 한 에피소드가 끝난것으로 간주,

하나의 노드를 선택하는 것을 1-step 이라고 표현

1-step Q-learning은 매 스텝마다 업데이트 n-step Q-learning은 n 스텝마다 업데이트 (for delayed reward) \(y=\sum_{i=0}^{n-1}{r(s_{t+i}, \, v_{t+i}) + \gamma max_{v^{\prime}} \hat{Q}(h(S_{t+n}), v^{\prime};\theta ) }\)

fitted Q-iteration은 버퍼에 저장했다가 배치로 꺼내서 업데이트 하는것

Algorithm

Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs

• 그래프에서의 Combinatorial Optimization 문제에 대한 완전한 해를 구하는 unsupervised learning framework를 제공한다.
• Erdos의 probabilistic method에서 sets에 대한 확률 분포를 뉴럴넷으로 표현했다.
• maximum clique 문제, constrained min-cut 문제, local graph clustering에 적용했다.
• unsupervised, differentiable, end-to-end로 뉴럴넷을 학습한다.
• loss를 미분 가능하도록 바꾸는 것이 해가 존재하는 것을 보장한다.

The Erdos probabilistic method for deep learning

weighted graph \(G=(V,E,w)\)에서의 조합 문제를 다루고, constrained optimization 문제로 나타낸다.

\(\Omega\)는 문제에 따라 원하는 속성을 가진 노드집합의 집합이다.

The “Erdos Goes Neural” pipeline

non-differentiable한 \(\eqref{eq:2_1}\)을 다루는 대신 GNN을 이용해 해들의 분포를 취급할 수 있도록 한다.

Figure 1에 제안한 방법의 세 과정이 나와있다.

1. GNN \(g_\theta\)를 구성하고 sets에 대한 분포 \(\mathcal{D}=g_\theta(G)\) 분포를 얻는다.
2. 낮은 cost \(f(S^\ast ; G)\)의 유효한 \(S^\ast \; \sim \; \mathcal{D}\)가 존재할 확률의 최적화를 학습한다.
3. conditional expectation 방법으로 Deterministically \(\mathcal{D}\)로부터 \(S^\ast\)를 복구한다.

\(\mathcal{D}\)초기화는 \(v_i \in S\)는 확률 \(p_i\)를 갖는 베르누이 확률변수 \(x_i\)로 초기화한다.