https://arxiv.org/pdf/1704.01665.pdf

요약

  • Graph 데이터를 사용하는 조합최적화 문제는 비슷한 문제 형태를 갖지만 문제가 조금만 달라져도 다른 알고리즘을 적용해야 했습니다.
  • 본 논문에서는 Graph 데이터를 사용하는 조합최적화 문제의 구조를 일반화하여 다양한 문제 세팅에서 알고리즘의 큰 조정 없이 적용할 수 있는 S2V-DQN 알고리즘을 제안했습니다.

배경지식

  • 조합최적화 (Combinatorial Optimization)
  • Maximum vertex cover, Maximum cut, TSP
  • 강화학습 (Reinforcement Learning)

배경

[조합 최적화 문제](https://dice.tistory.com/41)는 이산적인 탐색 공간에서의 최적의 해를 찾는 문제입니다. 조합최적화는 np-hard 문제로 해결하는데 오래 걸린다는 특징이 있습니다. 조합최적화를 해결하는 방법은 Exact algorithm, Approximation, Heuristic 방법 등이 있습니다. 이러한 방법들은 각각 성능과 수행시간을 trade-off하여 결과를 출력합니다.

하지만 Learning Combinatorial Optimization Algorithms over Graphs 논문에서는 기존의 알고리즘들이 문제가 조금이라도 변형되면 다시 알고리즘을 수행해야 하는 일반화 관점에서의 문제점을 제기합니다. 이 논문은 이를 input data가 graph 구조인 것을 활용하여 일반화 성능을 높인 알고리즘을 제안합니다. 즉, 같은 유형의 문제에 대해서는 빠르게 결과를 출력하게 됩니다.

Learning Combinatorial Optimization Algorithms over Graphs 논문에서는 아래와 같은 세가지 조합최적화 문제에 대해서 알고리즘을 적용하여 성능을 평가했습니다.

  • Minimum Vertex Cover (MVC): 모든 edge를 커버하는 가장 작은 vertex set을 찾는 문제 입니다. 최소한의 카메라로 모든 공간을 확인하는 방법등을 찾는데 활용할 수 있습니다.

Minimum vertex cover (WIKI)

  • Maximum Cut (MAXCUT): Graph를 두 subgraph S와 V \ S로 나눌 때, 각 subgraph 사이의 edge weight의 합이 최대가 되도록하는 문제입니다. Clustering에 활용됩니다.

Maximum Cut

  • Travelling Salesman Problem (TSP): 각 vertex를 한번씩 순회할 때 사용한 edge weight의 합이 최소가 되도록 하는 문제입니다. 물류 최적화 등의 문제에 활용됩니다.

알고리즘

본 논문에서는 문제를 greedy meta-algorithm 방식으로 해결합니다.
meta-algorithm은 문제와 상관없이 알고리즘을 적용할 수 있기 때문에 붙여진 것 같습니다.
Greedy는 강화학습 단에서 Agent가 Action을 선택할 때 현재 state에서 최적의 결과를 선택하기 때문에 붙여졌다고 생각됩니다.

이를 적용한 전반적인 프레임워크는 다음과 같습니다.

S2V-DQN 알고리즘 흐름도

1) Graph Embedding: 지금까지 배치된 node 들의 정보와 현재 배치할 node 정보를 Embedding
2) Action Selection: Embedding 값을 사용하여 가장 좋은 reward를 줄 것으로 예상되는 들의 선택

위 두 과정을 반복하면서 최종 결과물을 출력하고 이를 사용해 학습을 하게 됩니다.
논문에서는 1) Graph Embedding을 하기 위해서 Strcture2Vec을 사용하고, 2) Action Selection 및 훈련을 하기 위해 Fitted Q-learning을 사용합니다.

Structure2Vec (S2V)

지금까지 배치된 node 들의 정보와 현재 node 정보를 embedding 하기 위해서 본 논문에서는 structure2vec(S2V) 모델을 사용하여 각 node 정보를 embedding하고 이를 사용해 지금까지 배치된 node들 즉, subgraph의 embedding값을 계산합니다..

먼저, S2V모델은 Node v에 대한 embedding $\mu_v$를 아래의 식과 같이 recursive하게 업데이트 합니다.
$$\mu_v^{(t+1)}\leftarrow F(x_v,{\mu_{u}^{(t)}}_{u\in N(v)}, {w(v, u)}_{u\in N(v)};\theta )$$

  • $x_v$: Node v의 feature vector
  • $F$: Nonlinear mapping (e.g. neural network, kernel function)
  • $N(v)$: Node v의 neighbors

Embedding $\mu_v$는 업데이트 할 때마다 주변 vertex의 embedding, feature, edge 정보를 통합합니다. 즉, n번 업데이트 하면 n-hop neighbors의 정보를 embedding하게 됩니다.

본 논문에서는 Nonlinear mapping F를 다음과 같이 정의합니다.
$$F(x_v,{\mu_{u}^{(t)}}_{u\in N(v)}, {w(v, u)}_{u\in N(v)};\theta) = \text{ReLU}(\theta_1 x_v + \theta_2 \sum_{u\in N(v)}\mu_t^{(t)} + \theta_3 \sum_{n \in N(v)} \text{ReLU}(\theta_4 w(v,u)))$$

이후 위의 node embedding 값을 사용해 subgraph의 embedding $Q(h(S),v;\theta)$는 다음과 같이 계산합니다.
$$Q(h(S),v;\theta) = \theta_5 \text{ReLU}(\text{CONCAT}[\theta_6 \sum_{u \in V}\mu_u, \theta_7\mu_v])$$

  • $S$: Subset of nodes $V$
  • $\sum_{u \in V}\mu_u$ : 전체 graph 정보 embedding
  • $\mu_v$ : 현재 배치할 node

(개인적으로는 $\sum_{u \in V}\mu_u \rightarrow $\sum_{u \in S}\mu_u$$ 오른쪽 항과 같이 변경되어야 할 것 같은데 확인해봐야할 것 같습니다.)

Fitted Q-learning

강화학습의 요소는 state, action, reward로 정의할 수 있습니다.

  • State: 선택된 node 집합 (혹은 선택된 node 집합의 embedding)
  • Action: 선택되지 않은 node 중 하나를 선택
  • Reward: Node를 선택했을 때 얻게 되는 Objective의 기대값

State는 위에서 얻은 Embedding을 사용합니다. 이후 매 step마다 각 state마다 최대한의 기대값을 갖는 action을 선택하면서 문제를 풀고, 학습하게 됩니다. 이때 사용하는 학습 알고리즘은 Neural fitted q-learning(NFQ) 입니다. NFQ는 빠른 수렴을 위해 기존 q-learning에 다른 exploration 없이 experience replay에서 random sampling한 episode로 업데이트 하는 방식입니다.
자세한 설명은 블로그와 아래 수도코드를 참조해주세요.

Fitted Q-learning의 수도코드

실험 결과

논문에서는 S2V-DQN과 이전 블로그에 포스팅한 pointer network (PN-AC)를 비교했습니다. PN-AC를 사용할 때는 더 좋은 성능을 보여준 active search가 아닌 greedy search를 사용한 버전과 비교했습니다. 그외에도 각 문제에 적용되는 여러가지 heuristic, approximation 알고리즘들과 같이 비교했습니다. 이때 각 알고리즘의 성능은 optimal 값 대비 알고리즘 결과값 비율로 측정합니다. 이 때 Optimal solution은 각 문제를 해결하는 툴을 1시간 동안 구동시킨 결과 입니다.

실험 데이터는 MVC, MAXCUT, TSP를 잘 모델링하는 모델을 사용하여 직접 생성하였습니다.

결론

Approximation ratio on 1000 test graphs

1000개의 test data에 대해서 실험 결과시 S2V-DQN은 MVC, MAXCUT, TSP 모두에서 잘 동작했습니다. MVC와 MAXCUT은 모두 기존 알고리즘 대비 좋은 성능을 보였고, TSP에서는 PN-AC가 좋은 성능을 보였지만 S2V-DQN도 그에 못지 않은 성능을 보여주었습니다.

S2V-DQN의 일반화 성능

또한 50-100개의 노드에 대해서 훈련시키고 더 많은 노드 데이터에 대해 적용했을 때에도 좋은 성능을 보여주었습니다. 1000개의 노드에 대해서도 좋은 성능을 보여주었다는 것은 매우 신기한 결과 였습니다.

 

저는 논문을 읽으면서 다음 사항들이 아쉬웠습니다.

  • PN-AC는 가장 좋은 성능을 내는 active search를 사용하지 않음
  • Optimal solution은 1시간만 수행 후 결과를 측정함. 이 값이 optimal solution이 아닐수도 있는데 어떻게 1시간이라는 기준이 생겼는지 궁금함
  • 논문에서는 NFQ를 사용했다하지만 제안한 알고리즘 이름이 S2V-DQN인 이유를 모르겠음

또한 Future work로 다음 작업들이 있지 않을까 생각되었습니다.

  • Graph Embedding을 S2V가 아닌 GNN을 사용
  • Objective function을 제대로 설정하기 위해서는 여전히 domain knowledge 가 필요한데 이 부분도 일반화
  • Action 개수가 많아질수록 DQN을 사용하기 어려우므로 Policy Gradient 계열의 RL 알고리즘을 적용

Reference

저작자표시 (새창열림)

티스토리툴바