LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation
This addresses the problem of scaling combinatorial optimization for applications like vertex cover and max-cut, though it is an incremental improvement by combining existing techniques.
The paper tackles the scalability issue of combinatorial optimization heuristics on large graphs by proposing LeNSE, a reinforcement learning method that identifies small subgraphs for efficient near-optimal solutions, achieving comparable results to full-graph heuristics with up to 10 million edges at a fraction of the run time.
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.