Learning Combinatorial Optimization Algorithms over Graphs 논문 리뷰 및 설명

Learning Combinatorial Optimization Algorithms over Graphs

Abstract

• graphical np-hard combinatorial problem에 초점을 맞추어 RL로 해결하는 논문입니다. 해결 범위는 structure가 고정된 채, 안의 data만 바뀌는 상황을 가정합니다. graph를 embedding하여(Structure2Vec) fitted q-learning를 통해 학습합니다.

Introduction

• Np-hard graph optimization problem을 해결하기 위한 접근법은 세 가지로 분류될 수있습니다.
  • 첫 째로, 전역해를 구하는 것입니다. 이는 scale이 커지면 연산량 때문에 사용이 불가능할 수 있습니다.
  • 둘 째로, 다항시간으로 근사한 해를 구하는 것입니다. 이는 optimality를 보증하기 어려울 수 있을 뿐더러 성능적 문제나 근사가 불가능할 수도 있습니다.
  • 셋 째로, 휴리스틱한 알고리즘을 사용하는 것입니다. 이는 이론적인 배경이 부족하지만 빠르고 강력할 수 있습니다. 다만 이를 만들기 위해선 또 연구자의 큰 노력이 필요합니다.
• 기존에 Combinatorial problem을 해결하기 위한 연구들이 많이 존재하나, graph structure를 잘 반영하지 못했습니다. 또한, generalization을 위해 다양한 학습 set이 필요하고, on-policy로 인한 sample inefficiency를 겪습니다. pointer network를 통해 graph의 다양한 크기를 처리할 수 있는 것은 좋았으나, 이를 위한 추가적인 작업이 필요합니다.
• 본문에서는 RL과 graph embedding을 통해 이를 해결합니다.

1. Algorithm design pattern
   • agent는 greedy action을 취합니다.
2. Algorithm representation
   • representation을 배우기 위해 graph embedding network를 사용합니다. 이는 graph의 nodes와 정보에 대해 featurize합니다.(주변의 인접한 노드의 context를 반영해 특성을 얻어냅니다.) 이 또한 기존의 sequence-to-sequence방식과는 대비되지만 이 방식 또한 다양한 크기의 graph를 처리 가능합니다.
3. Algorithm training
   • fitted Q-learning을 통해 greedy policy를 학습합니다. 5.2에서 자세히 설명하겠습니다.

Common Formulation for Greedy Algorithms on Graphs

• 본문에서는 Mimum Vertex Cover(MVC)와 Maximum Cut(MAXCUT), Traveling Salesman Problem(TSP)에 적용함을 보입니다. 이 때 graph \(G\)에 대해 \(G(V,E,w)\)로 표현합니다. 이는 vertices와 edges, weights를 나타내며 graph는 undirected합니다.
  • Minimum Vertex Cover(MVC)
    • 그래프 G에 대해, 모든 edges를 포함하는 최소한의 nodes를 찾는 문제입니다.
  • Maximum Cut(MAXCUT)
    • 그래프 G에 대해, nodes를 두 set으로 나눌 때, 최대로 edge의 weights를 자르는 문제입니다.
  • Traveling Salesman Problem(TSP)
    • 평면의 그래프 G에 대해, 한 노드를 기점으로 모든 노드를 돌아 원점까지 돌아오는 최단거리를 구하는 문제입니다.
• 먼저 문제를 해결하는 방식은 evaluation function \(Q\)가 graph nodes를 greedy하게 하나씩 선택해 완성되지 않은 partial solution list \(S\)에 추가시키는 방식으로 학습됩니다. 이 문제들을 표현하기 위한 공통적인 formulation을 정의합니다.
  1. distribution \(\mathbb{D}\)로 부터 sampling된 하나의 graph problem \(G\)는 Vertices와 edges, weights로 이루어져있습니다.
  2. partial solution은 ordered list \(S= (v_1,v_2,...,v_{\vert S \vert})\)로 나타낼 수 있습니다. \(\bar{S}=V \backslash S\)는 \(S\)에 포함될 수 있는 candidates를 의미합니다. 이 때, \(S\)에 포함됐는지에 대한 여부 binary를 이용하는 vector \(x_v\)를 정의하는데 각 노드가 \(S\)에 포함되었을 때 1, 아닐 때 0으로 총 node와 같은 dimension을 가집니다.
  3. \(h(S)\)는 ordered list \(S\)를 다시 문제에 조건에 맞게 graph에 mapping하는 함수입니다.
  4. objective function \(c\)는 주어진 partial solution \(S\)의 graph에 대해 문제 \(G\)에서의 quality를 측정합니다. 이는 다음과 같이 나타냅니다. \(c(h(S),G)\)
  5. evaluation function \(Q\)를 maximize하는 \(v\)에 대해 partial solution \(S\)는 다음과 같이 확장됩니다. \(S := (S,v^*),\ \ \mathrm{where} \ v^* := \mathrm{argmax}_{v \in \bar{S}} Q(h(s),v)\) 이는 특정 termination criterion \(t(h(s))\)가 만족될 때까지 반복됩니다. 이를 이용해 MVC, MAXCUT, TSP를 어떻게 정의하는지 보입니다.
  • MVC
    • objective function은 \(c(h(s),G) = -\vert S \vert\)이고 \(t\)는 모든 edge가 포함되었는지 확인합니다.
  • MAXCUT

    • 위에서 표현한대로, 자른 edge들의 set cut-set은 edge의 한쪽은 \(S\)에, 다른한쪽은 \(\bar{S}\)에 존재하는데 이를 표현하면 다음과 같습니다.

      \[C = \{(u,v) \vert (u,v) \in E, u \in S, v \in \bar S \}\]

      그리고 이를 objective function으로 표현하면 다음과 같습니다.

      \[c(h(s),G) = \sum_{(u,v) \in C}w(u,v)\]
  • TSP

    • objective function은 다음과 같고 \(S=V\)일 때 종료됩니다.

      \[c(h(S),G) = -\sum^{\vert S \vert - 1}_{i=1}w(S(i),S(i+1)) - w(S(\vert S \vert),S(1))\]

Representation: Graph Embedding

• graph \(G\)를 optimizing하기 위해서 evaluation function \(\hat{Q}\)는 현재까지의 partial solution \(S\)에 대한 정보 \(x_v\)를 받아야하고, 이런 graph \(G\)에 대한 정보를 요약해 다음 node를 내놓아야합니다. 이 때 graph 상태와 node \(v\)에 대한 context를 같이 embedding하는 것은 굉장히 복잡한 일인데, 이를 해결하기 위해 graph를 사용한 structure structure2vec를 정의합니다.

1. Structure2Vec
   • 이 graph embedding network는 각 노드에 대한 p-dimensional feature embedding \(\mu_v\)를 생성합니다. 이는 아래와 같이 node가 neighbors와 recursive하게 연산하여 그래프의 특징과 long-range interaction을 표현하게 됩니다. 첫 \(\mu^{(0)}_v\)는 0으로 embedding 되지만, 다음과 같이 iterative하게 반복됩니다.
   \[\mu^{(t+1)}_v ←F(x_v, \{\mu^{(t)}_u\}_{u \in \mathcal{N}}, \{w(v,u)\}_{u \in \mathcal{N}(v)};\Theta)\]

   \(\mathcal{N}(v)\)는 graph \(G\)에서 노드 \(v\)에 인접한 노드 neighbors만을 이용하는 것에 유의하면 됩니다. \(F\)는 아래에서 자세히 정의하겠습니다.

2. Parameterizing \(\hat{Q}(h(S),v;\Theta)\)
   • \(F\)를 자세히 나타내면 다음과 같습니다.
   \[\mu^{(t+1)}_v ← \mathrm{ReLU}(\theta_1 x_v + \theta_2 \sum_{u \in \mathcal{N}(v)}\mu^{(t)}_u + \theta_3 \sum_{u \in \mathcal{N}(v)}\mathrm{ReLU}(\theta_4w(v,u)))\]

   이 연산을 통해 \(x_v\)는 처음엔 binary vector지만 recursive하게 연산되면서 다양한 정보가 통합되어 좀더 많은 의미를 가진 vector가 됩니다. (이전의 \(\mu_u\)에 대해 더많은 nonlinear layer를 거쳐도 된다고 합니다.) 이 연산을 \(T\)번 진행하여 얻은 각 node에 대한 embedding \(\mu^{(T)}_v\)를 가지고 마지막으로 다음과 같은 연산을 통해 \(\hat{Q}(h(s),v; \Theta)\)를 정의합니다.

   \[\hat{Q}(h(S),v ;\Theta) = \theta^T_5 \mathrm{ReLU}([\theta_6\sum_{u \in V}\mu^{(T)}_u,\theta_7 \mu^{(T)}_v])\]

   trainable parameter \(\Theta\)는 \(\Theta = \{ \theta_i\}^7_{i=1}\)이고, \(T\)는 4번 정도로 사용을 했습니다. 마지막으로 이를 학습시킨 learning method를 보겠습니다.

Training : Q-learning

• Q-learning을 통해 학습하는데, nodes의 개수가 몇개든, max를 뽑는 연산을 하기 때문에 size가 dynamic함에 영향을 받지 않습니다.
  1. Reinforment learning formulation
  • States
    • state \(S\)는 graph \(G\)에서의 nodes입니다. 이전에 설명한 연산을 통해 p-dimensional space를 가지고 있습니다.
  • Transition
    • environment가 deterministic한 특성을 가지고 있습니다.
  • Actions
    • action \(v\)는 \(S\)에 있지않는 \(G\)의 node중 하나입니다.
  • Rewards

    • reward function \(r(S,v)\)는 다음과 같이 계산할 수 있습니다.

      \[r(s,v) = c(h(S'),G) - c(h(S),G) ,\ \ c(h(\emptyset),G)=0\]

      이 때 \(R(\hat{S}) = \sum^{\vert \hat{S} \vert}_{i=1} r(S_i,v_i)\)는 \(c(h(\hat{S}),G)\)와 같습니다.

  • Policy
    • \(\hat{Q}\)에 의해 determinstic greedy policy \(\pi(v \vert S) := \mathrm{argmax}_{v' \in \bar{S}}\hat{Q}(h(S),v')\)를 가집니다.

1. Learning algorithm
   • n-step Q-learning과 fitted Q-iteration을 통해 학습됩니다. 이는 다음의 algorithm 1과 같습니다.

   

   Q-learning에서 Q의 update는 target y와의 L2 loss를 minimize하여 update합니다.

   \[(y - \hat{Q}(h(s_t),v_t; \Theta))^2\]

   이 때, trajectory가 길고 어려우므로 이를 보정하기 위해 n-step learning을 진행합니다.

   \[y= \sum^{n-1}_{i=0}r(S_{t+i},v_{t+i}) + \gamma \max_{v'} \hat{Q}(h(S_{t+n}),v';\Theta)\]

   fitted Q-learning은 기존 Q-learning에서 online sample-by-sample으로 학습하는 것을 replaybuffer를 만들어 개선하였습니다.(이에 Neural Fitted Q learning이 존재하는데, 이는 environment를 표현할 충분한 data를 가진상태를 가정하고 replaybuffer에서 data만 뽑아학습하는 Q-learning과 같습니다.) 이때 Q를 표현하기 위해 neural network를 사용합니다. 당연한 얘기지만 이후의 논문에서도 S2V-DQN을 baseline으로 쓰므로 DQN처럼 구현해도 괜찮을 것 같습니다.

References

• Learning Combinatorial Optimization Algorithms over Graphs