Graph Neural Networks Crack a Hard Math Problem Faster

The Branching Problem That Wouldn’t Die

In computer science, there are problems that are hard, and then there are problems that are NP-hard. The difference is existential. A hard problem might take a while to solve. An NP-hard problem, like the Maximum Independent Set (MIS), belongs to a class where, as far as anyone knows, the time required to find the perfect answer can explode exponentially with every new piece of data. You cannot cheat. You cannot guess. You have to search.

For decades, the standard way to solve MIS exactly was simple. You look at a graph. A graph is just dots connected by lines. You want the biggest collection of dots where no two are directly connected. That is your independent set. To find it, you pick a dot, and you branch. You ask: is this dot in the set, or not? Then you check both possibilities. This is called branch and bound. And for a long time, the rule for which dot to pick next was nearly religious: pick the one with the most connections. The highest degree. The busiest dot.

That rule is not stupid. It is just not optimal. And for the first time, a group of researchers has shown that a machine learning model, specifically a Graph Neural Network, can learn a better rule. The result, published in the proceedings of the 2024 Symposium on Experimental Algorithms, is a 24% median speedup on 73% of benchmark instances (Silva et al., 2024). That does not sound flashy. But in a world where every exponential factor matters, it is the difference between solving a problem in an afternoon and waiting until next Tuesday.

What Is Maximum Independent Set, Really?

Imagine you are scheduling meetings. You have a list of people. Some of them hate each other and cannot be in the same room. You want the largest possible group of people who can all be in the same room without anyone storming out. That is Maximum Independent Set. It is not a toy problem. It shows up in bioinformatics, in network analysis, in computer vision, in social network mining, and in scheduling. Every time you need to find the largest conflict free set, you are solving MIS.

The problem is ancient. It is also NP-hard. That means there is no known algorithm that can solve every instance quickly. The best algorithms are clever about pruning the search tree. They use reduction rules to shrink the graph before branching. They use heuristics to guess which branch to explore first. And they use branching strategies to decide which vertex to split on next.

For decades, the branching strategy was almost an afterthought. People focused on better reduction rules. They made progress. But the branching strategy, the moment where you decide which dot to bet on, was stuck in the 1970s. The highest degree rule was the default. It worked. But it was never proven to be the best.

The Hidden Lever

Here is what the authors of the new paper noticed. The branching strategy is not a trivial detail. It is a lever. If you pick the wrong vertex, you might split the problem into two unbalanced halves, one of which is still enormous. If you pick the right vertex, you create two smaller problems that are much easier to solve. The difference can be exponential.

The problem is that the "right" vertex depends on the graph. It depends on the current state of the search. It depends on which reduction rules have already been applied. It is a contextual decision. And humans are terrible at making contextual decisions under exponential pressure.

The authors, Gabriel Silva, Mário Rodrigues, António Teixeira, and Marlene Amorim, decided to try something different. Instead of handcrafting a branching rule, they would let a machine learning model learn one. Specifically, they would use a Graph Neural Network, or GNN. A GNN is a neural network designed to operate directly on graph structured data. It can look at a vertex, look at its neighbors, look at the neighbors of its neighbors, and build a representation of the local structure around that vertex. That representation can then be used to decide which vertex is the best to branch on next.

But there was a catch. Training a neural network to work inside a branch and bound solver is hard. The solver is a complex, stateful system. The decisions it makes change the graph. The rewards are delayed. You might make a good branching decision now, but the payoff comes many steps later. This makes traditional supervised learning and reinforcement learning difficult. You cannot just collect a dataset of "good" branching decisions, because you do not know what a good decision looks like until the solver finishes.

So the authors did something clever. They used a population based genetic algorithm to evolve the model's parameters (Silva et al., 2024). Instead of trying to learn from labeled examples, they let a population of models compete. Each model made branching decisions. The ones that led to faster solving times had their parameters mixed and mutated to create the next generation. Over many generations, the models got better.

The Genetic Gamble

Genetic algorithms are not new. They are not sexy. But they are robust. You do not need a perfect gradient. You do not need a reward function that works at every step. You just need a way to measure who wins. In this case, winning meant solving the MIS instance faster.

The authors ran their experiments on a set of benchmark instances from the literature. These are not toy graphs. They are real world graphs from applications like social networks, road networks, and scientific computing. The authors compared their GNN based branching strategy against the standard highest degree strategy. They also compared against a random strategy and a strategy based on another common heuristic, the "minimum degree" rule.

The results were clear. On 73% of the instances, the GNN based strategy was faster. The median speedup was 24% (Silva et al., 2024). That means half of the instances saw at least a 24% reduction in solving time. Some instances saw much larger speedups. A few saw slowdowns. But the overall trend was unmistakable. The GNN learned something the human designed heuristics did not know.

What the GNN Actually Learned

This is the part that might make a mathematician uncomfortable. The authors do not know exactly what the GNN learned. Neural networks are black boxes. The GNN outputs a score for each vertex. The solver picks the vertex with the highest score. But the score is a function of the local graph structure, and that function is a tangled mess of nonlinear transformations.

The authors did some analysis. They found that the GNN did not simply learn a proxy for degree. It did not just pick high degree vertices. It did not just pick low degree vertices. It seemed to pick vertices that, when removed, broke the graph into more balanced pieces. It learned to look for "articulation points" or vertices that connect different parts of the graph. It learned to avoid vertices that, if chosen badly, would leave a huge subproblem intact.

This is intuitive to a human expert. You want to split the graph into two parts of roughly equal size. The GNN learned to do that, but it learned to do it in a way that was sensitive to the specific structure of each graph. It did not just apply a rule. It adapted.

Why This Matters Beyond One Problem

The Maximum Independent Set problem is important. But the approach matters more. The authors have shown that you can use a machine learning model to replace a heuristic inside a combinatorial optimization solver, and you can train that model without a perfect reward signal. You can use evolution. You can let the solver itself be the judge.

This is a proof of concept for a broader idea. Many hard problems in computer science are solved by branch and bound or branch and cut algorithms. These algorithms have many components: branching rules, reduction rules, pruning rules, node selection rules. Almost all of them are handcrafted heuristics. Almost all of them could potentially be replaced by learned models.

The bottleneck has always been training. How do you train a model to make good decisions inside a system that is itself changing as the model makes decisions? The authors have shown one path. Use a population based method. Let the solver be the environment. Let evolution do the work.

The Limits of the Approach

This is not a silver bullet. The authors are careful to note the limitations. First, the training process is expensive. You have to run many generations of the genetic algorithm, each generation requiring many solver runs. For a single benchmark set, this is feasible. For a new problem domain, you would have to retrain.

Second, the GNN does not always win. On 27% of the instances, the standard highest degree strategy was faster. The GNN is not a universal improvement. It is a statistical improvement. On average, it helps. But if you have a specific instance that the GNN has not seen before, you cannot be sure it will help.

Third, the GNN is a black box. You cannot inspect its decisions and learn a new human understandable heuristic. This is a philosophical problem as much as a practical one. If the GNN discovers a beautiful new branching rule, we will never know what it is. The knowledge is trapped inside the weights.

Fourth, the approach has only been tested on the Maximum Independent Set problem. It might generalize to other problems, but that has not been shown. The authors are careful not to overclaim.

An Open Question

The most interesting open question is this: can the GNN learn a branching strategy that generalizes across problem domains? The authors trained their model on a set of benchmark instances. But those instances are all from similar application areas. If you gave the model a graph from a completely different domain, say a protein interaction network, would it still work? Or would it fail because it learned patterns specific to the training data?

This is the central tension in machine learning for combinatorial optimization. You want models that are general. But the training data is always limited. The best models might be those that learn a meta strategy, a way of thinking about branching that applies to any graph. Or the best models might be those that overfit to the specific distribution of graphs they will encounter in practice. We do not know yet.

Another open question is whether the genetic algorithm approach can scale to larger models. The GNN used in this paper is relatively small. It has a few thousand parameters. Larger models might learn better strategies, but they would also be harder to train with a genetic algorithm. There might be a sweet spot.

What This Actually Means

• ▸If you write solver code for NP-hard problems, consider replacing your branching heuristic with a learned model. The 24% median speedup is real. It is not huge, but in exponential search, every factor counts. The cost is training time, but the payoff is faster solving on the majority of instances.

• ▸If you are a machine learning researcher, look at population based training for combinatorial optimization. The authors have shown that you can train a model without a clean reward signal. Genetic algorithms are underused in this space. They might be the right tool for many problems where reinforcement learning is too difficult.

• ▸If you are a mathematician, do not panic. The GNN did not discover a new theorem. It discovered a heuristic. Heuristics are what we use when we cannot prove the optimal answer. The GNN is a better heuristic. That is useful, but it is not a proof. The search for a provably optimal branching rule continues.

• ▸If you are a manager deciding whether to adopt this technology, be skeptical of the 73% number. It means the model wins most of the time, but not always. You need to test it on your own data. The benchmark instances used in the paper are public. Your graphs might be different. Run your own experiments before committing.

• ▸If you are a student, this is a good paper to read carefully. It is a clean example of how to combine machine learning with combinatorial optimization. The methodology is clear. The results are modest but real. It shows that the field is moving toward learned components in classical algorithms. This is a trend that will only accelerate.