> For the complete documentation index, see [llms.txt](https://lichangbin.gitbook.io/paper_notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lichangbin.gitbook.io/paper_notes/sep/learning-combinatorial-optimization-algorithms-over-graphs.md).

# Learning combinatorial optimization algorithms over graphs

## Motivation

The current methods for combinatorial optimization problem cannot learn from experience. 

Can we learn from experience?

Given a graph optimization problem $$G$$ and a distribution $$D$$ of problem instances, can we learn a better greedy heuristics that generalize to unseen instances from $$D$$ ?

## Three common greedy algorithms on Graphs

Given weighted graph: $$G(V,E,w)$$ , $$w$$ : edge weight function, $$w(u,v)$$ is the weight of edge $$(u,v)\in E$$ 

#### Minimum Vertex Cover (MVC):

Given a graph $$G$$, find a subset of nodes $$S\subseteq V$$, s.t. every edge is covered.

*  $$(u,v)\in E \Leftrightarrow u\in S \text{ or } v\in S$$ 
* $$|S|$$ is minimized

#### Maximum Cut (MAXCUT):

Given a graph $$G$$, find a subset of nodes $$S\subseteq V$$, s.t. the weight of cut-set $$\sum\_{(u,v)\in C}w(u,v)$$ is maximized.

cut-set: $$C$$, the set of edges with one end in $$S$$ and the other end in $$V \backslash S$$ 

#### Traveling Salesman Problem (TSP)

## Overview

![](/files/-MIHc96gY424YRCOHyOQ)

basic idea

1. original graph with initial state
2. input the graph to an embedding model (*structure2vec*) for T steps
3. each node has a corresponding score based on *structure2vec*
4. pick up the node with the highest score  (after one iteration)
5. go back to step 2 and repeat until termination

## Relation to Q-learning (taking MVC for example)

![RL vs MVC](/files/-MIHfVbq7HzZH5-pxEmh)

|                                                                             | Reinforcement Learning                                                                                          | MVC (Minimum Vertex Cover)                        |
| --------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------- | ------------------------------------------------- |
| Reward $$R(t)$$                                                             | score we earned at current step                                                                                 | $$r^t=-1$$                                        |
| State $$S$$                                                                 | current screen                                                                                                  | current selected nodes                            |
| Action $$i$$                                                                | move your board left/right                                                                                      | select a node                                     |
| <p>Action value function</p><p> <span class="math">\hat{Q}(S,i)</span> </p> | predicted future total rewards                                                                                  | structure2vec embedding                           |
| Policy $$\pi(s)$$                                                           | <p>How to choose the action </p><p><span class="math">i^\* = \operatorname{argmax}\_i(\hat{Q}(S,i))</span> </p> | $$v^\* = \operatorname{argmax}\_v(\hat{Q}(S,v))$$ |

### How to represent the node embedding:

![](/files/-MIHgZn21d97xxI5BZsU)

###

### How to measure the Q-value for each node:

![](/files/-MIHi2UMVffaK7M_hONl)

## Reference

* <https://arxiv.org/abs/1704.01665>
* <https://github.com/Hanjun-Dai/graph_comb_opt>
*