LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation
Combinatorial Optimisation problems arise in several application domains and
are often formulated in terms of graphs. Many of these problems are NP-hard,
but exact solutions are not always needed. Several heuristics have been
developed to provide near-optimal solutions; however, they do not typically
scale well with the size of the graph. We propose a low-complexity approach for
identifying a (possibly much smaller) subgraph of the original graph where the
heuristics can be run in reasonable time and with a high likelihood of finding
a global near-optimal solution. The core component of our approach is LeNSE, a
reinforcement learning algorithm that learns how to navigate the space of
possible subgraphs using an Euclidean subgraph embedding as its map. To solve
CO problems, LeNSE is provided with a discriminative embedding trained using
any existing heuristics using only on a small portion of the original graph.
When tested on three problems (vertex cover, max-cut and influence
maximisation) using real graphs with up to $10$ million edges, LeNSE identifies
small subgraphs yielding solutions comparable to those found by running the
heuristics on the entire graph, but at a fraction of the total run time.