[ICML 2022] 3편: Neural Combinatorial Optimization studies

ICML 2022(International Conference on Machine Learning 2022)는 올해로 39회째를 맞은 대규모 국제 학회입니다. 논문 채택률 20%, 임팩트 팩터 6.99로 매년 약 7만 명 이상이 참가하며 AI 분야에서 가장 영향력 있는 인공지능 학회 중 하나로 손꼽히고 있습니다. LG AI연구원은 지난 7월 17일부터 23일까지 미국 메릴랜드 볼티모어와 온라인에서 하이브리드로 개최되었던 'ICML 2022'에 참관했습니다. LG AI연구원의 세 연구원이 학회에서 공유되었던 내용 중 유의미한 논문을 골라 소개합니다. - 1편: Long-Tail Distribution Learning – Applied AI Research Lab 윤수희 님 - 2편: Self-supervised learning – Applied AI Research Lab 정혜민 님 - 3편: Neural Combinatorial Optimization studies – Applied AI Research Lab 정한슬 님

Introduction

생활 속에서 접하는 다양한 문제들은 조합 최적화(Combinatorial Optimization, CO) 문제에 해당합니다. 조합 최적화는 실행 가능한 해(Feasible Solution)의 집합이 이산적(Discrete)으로 정의되거나 이산적인 집합으로 환원될 수 있는 수학적 최적화 분야를 의미합니다. 대표적으로 물건을 여러 장소에 배달해야 할 때 어떤 순서로 방문하는 것이 효율적일 지 결정하는 외판원 문제(Traveling Salesman Problem, TSP)가 있습니다.

최적화 이론은 오랫동안 연구되어 효과적으로 해를 찾는 수학적 기법이 많이 제시되었지만, 조합 최적화의 많은 문제들은 다항(polynomial) 시간 내에 해를 보장할 수 없는 NP-hard에 해당합니다. 이러한 조합 최적화 문제들을 효과적으로 풀기 위해서 최근 딥러닝을 활용한 Neural Combinatorial Optimization (NCO) 분야가 활발히 연구되고 있습니다. 이번 ICML 2022에서 발표된 연구 두 편을 통해 최근 NCO 연구동향을 설명해드리겠습니다.

1. LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation^[1]

문제는 다양한 방법으로 표현될 수 있지만, 최근 NCO 연구에서는 graph 형태가 많이 활용되고 있습니다. 대표적으로 다뤄지는 TSP, Capacitated Vehicle Routing Problem (CVRP)에서는 100개 이하의 노드를 갖는 그래프에서 실험하는 것이 일반적이고^[2,3,4], 선택된 점들을 적은 비용으로 연결하는 경로를 찾는 문제인 슈타이너 트리 문제(Steiner Tree Problem, STP)도 grid graph에서 30X30 크기의 데이터를 만들어 실험하는 것을 확인할 수 있습니다^[5].

이와 달리 현실 세계에서는 큰 사이즈의 데이터를 다뤄야 하는 상황이 많습니다. Figure 1은 광섬유 통신망 설계에 이용된 실제 샘플들을 모은 Vienna^[6] 데이터 세트로, 100,000개 이상의 노드를 갖는 그래프로 구성된 STP용 공개 데이터 세트입니다. 이처럼 다양한 분야에 활용할 수 있도록 NCO의 scalability를 개선하는 연구의 필요성이 대두되었습니다.

Figure 1. Vienna 데이터 세트 샘플

LeNSE는 큰 사이즈의 graph에서 효율적으로 조합 최적화 문제를 풀기 위한 방법론을 제시한 논문입니다. 조합 최적화 문제들은 각각의 문제마다 형태나 제약 조건 등이 상이합니다. 휴리스틱(Heuristic) 알고리즘은 특정 문제에 적합하도록 고안되어 해당 문제에서는 좋은 성능을 보여주지만 다른 문제에 적용하기는 어렵다는 한계가 있습니다. 저자들은 다양한 조합 최적화 문제에 적용할 수 있도록 연구 목표를 설정했는데, solver는 각각의 문제에 최적화된 휴리스틱 알고리즘을 그대로 이용하되, solver가 빠른 속도로 결과를 낼 수 있는 효율적인 subgraph를 찾자는 목표를 설정하였습니다. 전체 graph보다 크기가 작은 subgraph를 대상으로 하면 휴리스틱의 탐색 공간이 줄어드는 효과를 얻을 수 있고, 이러한 subgraph 중에서도 전체 graph 대비 성능 하락이 적은 subgraph를 찾는 방법론을 학습하면 효율적으로 scalability issue를 해결할 수 있다는 아이디어입니다.

LeNSE는 크게 두 부분으로 나눌 수 있습니다. 첫 번째는 optimal solution를 포함하는 likelihood를 나타내도록 subgraph의 representation을 학습하는 부분이고, 두 번째는 예측한 likelihood를 기반으로 더 좋은 subgraph를 찾을 수 있도록 subgraph를 수정해나가는 부분입니다.

Learning a discriminative subgraph representation

저자들은 일정 개수의 노드로 solution이 정의되는 budget-constrained 조합 최적화 문제들을 대상으로 연구했습니다. 따라서 주어진 문제 graph에 대한 optimal solution을 구하면 subgraph가 주어진다고 할 때, optimal solution에 속하는 노드 중에서 subgraph에 포함되는 노드가 얼마인지 계산할 수 있습니다. 논문에서는 optimal solution을 포함할 likelihood를 간접적으로 이용할 수 있는 subgraph classification 문제를 정의하였습니다. 다수의 subgraph가 주어졌을 때 각각의 likelihood를 기반으로 ranking을 매길 수 있고, ranking 순서대로 K개의 그룹을 나누어 class를 정의하였습니다. 이때 모델은 GraphSAGE^[7]와 k-pooling layer^[8]를 이용하여 encoder를 구성하였습니다. Encoder의 학습을 위해, InfoNCE loss^[9]를 이용하였는데, 이는 아래와 같이 정의됩니다.

${\chi }_{+}$와 ${\chi }_{-}$는 각각 positive, negative샘플을 의미하고 $\tau$는 positive와 negative를 얼마나 discriminative하게 볼지 조절하는 hyperparameter입니다. infoNCE loss는 contrastive predictive coding (CPC) 기반의 함수로, 다른 클래스를 앵커로 두고 같은 클래스에 속하는 샘플의 embedding을 유사하게 만드는 역할을 합니다. $\chi$를 기준으로 positive는 같은 클래스, negative는 다른 클래스에 속하는 subgraph를 의미하며 이 loss를 통해서 negative 샘플 대비 $\chi$와 ${\chi }_{+}$의 mutual information을 최대화할 수 있도록 합니다.

Subgraph navigation

LeNSE의 궁극적인 목표는 전체 graph를 대체할 수 있는 효율적인 subgraph를 찾는 것입니다. 임의로 initialize된 subgraph를 더 나은 subgraph로 변경하기 위해서 저자들은 Reinforcement Learning (RL)을 활용하였습니다. Optimal solution을 많이 포함하는 subgraph를 찾을 수 있도록 매 step마다 subgraph를 변형시키는 순차적 의사 결정 문제로 정의하였고 이때의 action은 subgraph의 modification operation입니다.

Figure 2. Modification operation

Modification operation은 다양한 방법으로 지정될 수 있으나, 저자가 제안한 방법은 subgraph의 노드 수는 고정시킨 채 노드를 하나씩 변경하는 방식입니다. Subgraph에 포함되는 노드와 그 neighborhood 중에서 subgraph에 포함되지 않는 노드를 하나의 쌍으로 묶어 action space를 구성합니다. Figure 2에서 표현되는 파란색 노드들이 현재 subgraph를 구성하는 노드들을 의미하고, 구불거리는 선으로 묶은 노드들이 파란색 노드와 쌍이 될 수 있는 노드들을 표현한 것입니다. 초록색 노드들은 action 쌍을 구성하기 위해 선택된 노드를 나타냅니다. 이 그림에서는 action space가 $\mathcal{A}=\left\{\left(\nu ,{\nu }_1\right),\left(\upsilon ,{\upsilon }_2\right)\right\}$로 정의됩니다. $\left(\nu ,{\nu }_1\right)$이 선택되었다면, $\nu$ 대신 ${\nu }_1$로 node를 교체하여 다음 step의 subgraph를 재구성합니다.

이렇게 변경시킨 subgraph가 optimal solution을 많이 포함할 수 있도록, reward는 class 1에 속하는 subgraph embedding들의 centroid와 거리를 최소화하도록 지정되었습니다. 이는 즉 likelihood가 높은 subgraph와 유사한 embedding을 갖는 subgraph로 action을 취하는 것을 의미하고, 결과적으로 optimal solution을 많이 포함한 subgraph로 변형시키는 policy를 학습할 수 있도록 합니다.

$g^{*}$는 centroid, $s_{t+1}$는 $t+1$ step의 subgraph embedding을 나타내며 $\beta$는 reward의 크기를 조절하는 hyperparameter입니다. 학습을 위해서 기본적으로는 q-learning을 활용하되, 학습 시 주어지는 optimal solution 정보를 prior로 활용하여 epsilon greedy를 변형한 guided q-learning을 이용하였습니다.

Experiments

Figure 3. Time step에 따른 subgraph trajectory

 

Figure 4. Time step에 따른 centroid와의 거리 변화

Figure 3은 모델이 잘 학습되었는지 정성적으로 확인하기 위해 time step에 따라 embedding space상에서 subgraph의 위치가 어떻게 변화하는지 그 trajectory를 시각화한 그림입니다. 시작 시점이 원형으로 표시되어 있고 보라색 실선은 변화 과정을 나타내며 마지막 지점은 사각형으로 표현되어 있습니다. 시작 값은 랜덤하게 초기화된 subgraph여서 class와 멀리 떨어져 있으나, 점차 class 1에 속하는 subgraph embedding cluster에 가까워지는 것을 확인할 수 있습니다. Figure 4는 centroid와의 distance를 나타낸 그림에서도 time step이 진행됨에 따라 평균과 분산 모두 점차 줄어드는 것을 보여주어 LeNSE 방법론이 목적에 맞게 잘 학습되었다는 것을 확인할 수 있습니다.

 

Table 1. 실험 성능비교 표

Table 1은 다른 방법론들과 정량적으로 성능을 비교한 표입니다. GCOMB-P^[10]는 SOTA 모델이고, GNN-R, GNN-T는 노드 classification 문제로 보고 각각 ranking 순서대로 특정 개수 노드를 선택하는 방법과, threshold 이상의 확률을 갖는 모든 노드들을 선택하는 방법을 이용하여 함께 비교하였습니다. Ratio는 전체 graph에서 heuristic solver의 결과를 모델이 찾아낸 subgraph의 결과 값으로 나눈 비율을 의미하여 값이 클수록 optimal에 가깝다는 사실을 나타냅니다.

LeNSE는 여러 세팅에서 모두 압도적이진 않으나 다른 방법론들과 비교했을 때 커다란 편차 없이 좋은 성능을 내는 것을 볼 수 있습니다. 이 결과는 subgraph의 크기와 함께 비교하면 더욱 극대화되는데, 선택된 subgraph의 노드와 엣지 비율을 나타내는 ${{\rm P}}_v$, ${{\rm P}}_E$를 볼 때, 선택되는 노드 개수를 고정한 GNN-R를 제외한 나머지 baseline들은 BMC, IM에서 아주 큰 값을 나타냅니다. 이는 거의 전체 graph와 유사한 크기이기 때문에 문제의 사이즈가 커질수록 효율이 떨어진다는 것을 의미합니다. 이와 비교해서 LeNSE는 여러 세팅에서 꾸준히 원 사이즈보다 작은 subgraph를 구성하며 그 성능도 강건한 것을 확인할 수 있습니다. GNN-R도 대체적으로 좋은 성능을 나타내는데 graph 사이즈가 큰 YouTube, Skitter 데이터 세트에서 Ratio 성능이 떨어지는 것을 확인할 수 있습니다. 이와 비교하여 LeNSE는 큰 사이즈의 문제에 대해서도 성능 하락 없이 효과적으로 효율적인 subgraph를 구성할 수 있다는 것을 확인할 수 있습니다.

한 가지 흥미로운 부분은 MVC 문제에 대해서 Wiki 데이터 세트의 Ratio 값이 1보다 큰 것을 확인할 수 있습니다. 이는 전체 문제를 봤을 때보다 subgraph를 입력했을 때 heuristic solver의 결과가 더 좋았다는 것을 의미합니다. Heuristic 알고리즘을 이용했기 때문에 solution이 optimal이 아닐 수 있어 발생한 결과이지만 subgraph만 보는 것이 전체 graph보다 결과의 quality 측면에서도 개선된다는 점은 흥미로운 결과입니다.

2. Augment with Care: Contrastive Learning for Combinatorial Problems^[11]

두 번째로 소개드릴 논문에서는 boolean satisfiability problem (SAT)를 위한 방법론을 제안했습니다. SAT도 조합 최적화에 해당하며 여러 변수로 이루어진 논리식에 대해서 각 변수에 true나 false 값을 입력해서 논리식의 결과를 true로 만들 수 있는지(=sat)를 판단하는 문제입니다. Figure 5는 논리식 $\varphi =\left(xv{ㄱ}^{y}v{ㄱ}^z\right)\wedge \left({ㄱ}^{x}v y v z\right)$ 을 bipartite graph로 나타낸 그림입니다. ∧로 연결된 두 절 (clause)를 각각 $C_1$,$C_2$로 표현하고 각각의 변수와의 관계를 나타낼 수 있습니다.

Figure 5. Bipartite graph로 표현한 SAT

SAT의 결과를 효과적으로 예측하기 위해서 저자들은 data augmentation 기법에 주목하였습니다. 다른 도메인에서 사용되는 augmentation 기법을 적용하였을 때 SAT 문제에서는 label이 보존되지 않는다는 문제점이 있었습니다. 예를 들어, Figure 6은 vision에서 흔히 사용되는 augmentation 기법을 적용한 고양이 사진입니다 앞서 제시한 기법들은 원본 이미지를 변형하여 한정적인 학습 데이터의 분포를 보다 풍성하게 만들 수 있으나, 일반적으로 고양이 이미지를 강아지로 만드는 등의 label의 변형은 나타나지 않습니다.

Figure 6. 이미지에서 사용되는 대표적인 augmentation 기법

Label-preserving augmentation (LPA)

그러나 graph 데이터에 사용되는 node dropping과 같은 기법은 SAT의 label을 바꿀 수 있다는 문제점이 있습니다. 저자들은 이러한 점을 개선하기 위해 SAT 도메인 지식을 활용해 문제의 Label을 변형하지 않는 여섯 가지 augmentation 기법을 제안하였습니다. 여섯 가지 중 하나인 Unit Propagation (UP)을 예시로 설명하겠습니다. 하나의 변수 $l$로만 구성된 절이 있다면 그 변수를 포함하는 모든 절을 제거하고 그 변수의 부정형 ${ㄱ}^l$을 제거해도 동일한 label을 갖게 됩니다. (Figure 7의 ${\hat{\varphi }}_1$이 UP이 적용된 샘플입니다.) 각 augmentation 기법은 원문에 좀 더 자세히 설명되어 있습니다. Figure 7에 나타난 것처럼, 하나의 논리식으로 구성된 입력 $\varphi$는 augmentation을 적용하여 서로 다른 샘플 ${\hat{\varphi }}_1$,${\hat{\varphi }}_2$를 생성합니다. Mini-batch 내 $N$개의 샘플에 대해서 각각 augmentation을 통해 총 2$N$개의 샘플을 생성할 수 있고, 각각을 bipartite graph로 변환해 encoder를 통과시켜 embedding을 뽑습니다. Encoder는 SAT의 SOTA인 NeuroSAT^[12]로 구성됩니다.

Figure 7. 전체 모델의 구조

생성된 데이터의 representation을 label 없이 효과적으로 학습하기 위해서 simCLR^[13] contrastive loss를 이용하였으며, 그 수식은 아래와 같습니다.

$sim\left(m_i,m_j\right)=m_i^T{m}_j/\parallel m_i\parallel \parallel m_j\parallel$ 은 두 embedding의 similarity를 측정하며 $m_i$,$m_j$는 서로 같은 샘플에서 생성된 두 샘플의 embedding을 의미하고 τ는 temperature parameter입니다. 이 때 같은 샘플에서 augmentation된 샘플은 positive, 그 외의 $2\left(\mathrm{N}-1\right)$개의 샘플은 negative로 구분하여 positive샘플끼리 embedding의 유사도를 높이도록 encoder를 학습하는 효과를 줄 수 있습니다.

Experiments

Figure 8. 성능 비교 히트맵

Figure 8은 저자들이 제안한 LPA 방식과 일반적인 graph augmentation 기법, 즉 label agnostic augmentation (LAA)를 비교하기 위해서 각 축에 해당하는 기법 두 개씩을 적용한 후 그 정확도를 히트맵으로 시각화했습니다. 각 행렬에서 대각 성분은 한 종류, 대각이 아닌 경우는 두 종류의 augmentation 기법을 이용했을 때의 정확도를 의미하고, 행에 명시된 기법이 먼저 적용된 기법입니다. SR, PR 데이터는 10개의 변수로 이루어져 있고, DP, PS는 20개의 변수로 이루어져 좀 더 긴 논리식으로 구성돼 있습니다.

전반적으로 여러 데이터, 여러 조합에서 LAA 대비 LPA의 성능이 더 높은 것을 확인할 수 있습니다. 최고 성능을 확인해 보면 SR, PR, DP, PS 데이터 순서대로, LPA는 95.1, 93.3, 86.0, 96.9인데 반해 LAA는 54.4, 59.1, 70.0, 65.5입니다. 이를 통해 LPA를 이용하여 학습했을 때가 좀 더 나은 representation을 배운다는 것을 알 수 있습니다. 또한 대각 성분과 아닌 경우를 비교해봤을 때, 두 종류의 augmentation을 이용했을 때가 하나의 augmentation을 적용했을 때 대비 성능이 더 개선되는 것을 확인할 수 있습니다. 그러나 보통의 augmentation과 유사하게 데이터 세트에 따라서 성능 차가 크고, augmentation 조합의 종류나 심지어는 그 순서에 따라서도 성능이 크게 변한다는 점은 한계점으로 보여집니다.

Conclusion

지금까지 ICML 2022에 NCO를 주제로 한 두 편의 논문을 소개했습니다. 첫 번째 논문은 subgraph navigation 문제로 관점을 바꿔서 조합 최적화의 특성을 최대한 배제했고, 두 번째 논문은 SAT의 특성을 반영한 augmentation 기법을 제안하여 도메인 지식을 활용하였다는 점에서 앞선 논문과 반대 전략을 취하고 있습니다. 하지만 전혀 다른 조합 최적화 문제를 대상으로 하면서도 두 논문 모두 contrastive loss를 활용하여 좋은 representation을 얻는 방식으로 성능을 개선하였다는 점은 NCO에서도 representation learning이 효과적이라는 점을 보여줍니다. 이전에는 조합 최적화에 ML을 적용해 보는 것에 초점이 맞춰져 있었다면, 최근 연구들은 조합 최적화의 특징을 고려하여 좋은 representation으로 성능 개선을 위해 노력했다는 점에서 NCO 분야가 발전했음을 보여줍니다. 앞으로 아직 다뤄지지 않은 조합 최적화 문제들에 대한 활발한 연구 및 관심과 그 결과물들이 다양한 산업군에 적용되기를 기대해봅니다.