NPO — Combinatorial problem
There have been works on solving combinatorial problems with Graph Neural Networks. In this post, I will go through 3 important papers on this matter.
Table of Contents1. Overview
>>> What is a combinatorial problem?
>>> Why Graph Neural Network?2. Outline of papers
>>> Approximation Ratios of Graph Neural Networks for Combinatorial Problems, Sato et al., NIPS 2019.
>>> Exact Combinatorial Optimization with Graph Convolutional Neural Networks, Gasse et al., NIPS 2019.
>>> Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP, Prates et al., AAAI 2019.
{What is the problem and Why; How to solve the problem; Results}3. Conclusions
>>> Why Graph Neural Network, after review
>>> Future works, unexplored problem space
1. Overview
What is a combinatorial problem?
Combinatorial problems involve finding a grouping, ordering, or assignment of a discrete, finite set of objects that satisfies given conditions. [1] Typically, combinatorial problems can be solved by formatting candidate solutions, which are combinations of solution components that may be encountered during a solution attempt but do not satisfy all given conditions. Then, find the true solutions by searching within the candidate solutions an instance that satisfy all given conditions.
For example: for traveling salesman problems, candidate solutions are any round trip that visits all destinations (a sequence of destinations) while the solution is the one arrangement that has the shortest path.
Combinatorial Problem Examples:
- Traveling Salesman Problem — arrange the list of destinations to achieve the least traveling distance.
- Set cover —Given a set, how to cover (with specified subset rules) with the least number of subsets.
e.g. for a graph, cover all vertices with min number of edge, with the selection of each edge covers the connected 2 vertices. - Knapsack problem —Given a set of items each with weight and value, find the highest value that can be carried by a knapsack with a fixed load.
Combinatorial Problems in the 3 papers:
- Traveling Salesman Decision Problem — Given a distance quota, determine if a travel agenda with a total distance less than the quota is possible.
- Mixed Integer Linear Programs —with N variables some integer some unrestricted, optimize under linear constraints for a linear objective.
- Minimum vertex cover problem (on a graph)— the least amount of vertices in a graph such that the union of all vertices and adjacent vertices is the total vertices.
- Maximum matching problem (on a graph)—the largest amount of edges without common vertices.
Why Graph Neural Network?
(initial thoughts before reading paper)
- Graphs are discrete and naturally connected to combinatorial problems
- Neural Networks generally better than traditional algorithms in the following manner:
1) NN: no need for expertise, just collect datasets and train; Traditional algorithm: difficult mathematics involved in algorithm design
2) NN can generalize to i.i.d. examples. (Is i.i.d. good enough for combinatorial problems? How much difference is still workable?)
3) Run time/test time can potentially be faster. Generally speaking, NN trades test time with training time. On the other hand, traditional algorithms can only be improved by redesigning the whole algorithm.
2. Outline of papers
What is the problem and why?
To investigate whether GNN can solve NP-Complete problems. Deep learning for the symbolic domains (e.g. graph can encode the relationships/distances between TSP points) is still incipient. Thus, they investigate the TSP decision problem. TSP decision problem instances are generated by sampling 20~40 random points in a 1 diameter square.
How is the problem solved?
[dataset]
For each TSP decision problem instance (Graph G), the Concorde TSP solver is utilized to find the optimal route and the minimum cost C*.
Then, a pair training sample of (G, 1.02C*) → Yes and (G, 0.98C*) → No, can be created for each instance G.
[model]
Initial edge embedding E = E_init (w, C), then the vertex embedding V and edge embedding E is updated back and forth with hidden vector
Results.
Exact Combinatorial Optimization with Graph Convolutional Neural Networks, Gasse et al., NIPS 2019.
What is the problem and why?
MILP: Linear program for linear objective with a mix of integer and floating-point variables. In the default branch and bound approach, branch on a selected floating-point variable and split by floor, ceiling of current value. Then bound by selecting one of the branches. This forms an episodic decision process. Prior work uses hardcoded heuristics to decide which variable to branch on. However, in the setting of day-to-day production planning, there is repetition in problem size and statistical learning is possible.
This work: reduce manual feature engineering by GCN, reduce the difficulty by imitation on expert rules.
How is the problem solved?
[dataset]
On different MILP subproblems, collect training samples by running expert branching decision on each decision to collect {state, action} pairs.
Encode the state as bipartite graphs of constraints and variables.
[model]
A graph neural network, following the bipartite graph nature, utilizing only 2 passes: one from variable → constraint, then, from constraint → variable. Select by final pass 2 layer MLP + softmax.
Results.
Accuracy is best (compare with other ML)
Overall, runtime has advantage (win = fastest run time on particular instance) compared to ML + human-designed sota (RPB)
ablation: mean + prenorm < sum (no prenorm) < sum + prenorm (GCNN). Substantiates the hypothesis that averaging by node degree will lose the node degree information. (think: “how many variables a constraint affects”, or “how many constraints a variable is included” are important knowledge)
Approximation Ratios of Graph Neural Networks for Combinatorial Problems, Sato et al., NIPS 2019.
What is the problem and why?
- This work connects GNN to the distributed local algorithm, then utilizes proven theory to categorize and propose even more complex GNN, which can also be backed by corresponding theories.
- Since it is backed by theory, approximation ratios for GNN trained for solving combinatorial problems. (spoilers: it is the same as the ratios of distributed local algorithms)
- Such a study provides an understanding of the limits of GNN.
- (From the 2-coloring trick utilized in the distributed local algorithm), this work reveals the effectiveness of node features, which (2-coloring) is solely from the graph structure.
Some taste of the theoretical tone involved.
- A graph problem is a function of Graph G → solution S. A solution S is a function of any vertex in G → item in a finite set.
- GNN solves graph problem if there exist parameter θ, with which GNN(θ) maps any (or to a satisfactory percentage of) graph (under some node degree limit) to the correct solution.
How is the problem solved?
- The concept of Vector-Vector consistent (VVc, proposed), Multiset-broadcasting (MB), and Set-broadcasting (SB) are depicted. MB-GNN and SB-GNN are shown in the following algorithms. Note that MB ≥ SB is proved in the GIN is most powerful paper. Whereas by connecting GNN to local discrete algorithms, this work proves VVc ≥ MB, SB.
- Vector-Vector consistent can be demonstrated by port numbering, which is basically an iterative numbering for all edges connecting to each vertex of a graph.
Two functions to find the corresponding node and port index are written on the other side of a certain node + port index is written:
With this, layer update algorithm for Consistent Port Numbering Graph Neural Networks (CPNGNN), an instance belonging to the VVc-GNN category can be written as:
Results.
for Minimum domain set problem, Minimum vertex cover problem, and maximum matching problem:
1) using the node degree as node feature: CPNGNN can only solve the above problems to an unsatisfactory degree (baseline) or cannot solve them at all.
2) with (weak) 2-coloring, there are much better results.
Such “theorems” are proved by connection to proofs for local distributed algorithms in prior works.
3. Conclusions
Why Graph Neural Network, after review
- Graphs are discrete and naturally connected to combinatorial problems. check.
- Neural Networks generally better than traditional algorithms in the following manner:
1) NN: no need for expertise, just collect datasets and train; Traditional algorithm: difficult mathematics involved in algorithm design. generalizability does not seem strong, the repeated settings in the second paper make more sense than the first paper.
2) NN can generalize to i.i.d. examples. (Is i.i.d. good enough for combinatorial problems? How much difference is still workable?)
I consider this demonstrated in the first paper.
3) Run time/test time can potentially be faster. Generally speaking, NN trades test time with training time. On the other hand, traditional algorithms can only be improved by redesigning the whole algorithm.
I consider this demonstrated in the second paper.
Future works, unexplored problem space
The practicality of GNN methods
>>> “#1 Learn to solve”: only compared to simple baseline.
1) different, skewed distribution (possible after normalizing large-scale realistic geolocations) not presented, generalizability unknown.
2) comparison against the expert (esp. computing time) not shown
>>> “#3 Approximate ratios”: did not explain and compare best theoretical guarantee to traditional algorithm ratios.
Unexplored problem space, questions.
>>> “#1 Learn to solve”:
1) what could be the meaning of the exact function of the Multi-Layer Perceptron trained for (C, w) → R^D embedding? Can it be explained?
2) The final result seems smooth, why?
>>> “#2 Exact Combinatorial”
1) Theoretical meaning from the resulting GNN, is it explainable? (by considering variables and constraints, do so and so decision).
>>> “#3 Approximate ratios”
1) Apparently, GNN designs did not extract the most information out the structure of a graph. still more to be considered.
2) Is local distributed a strong assumption? (GNN and CNN connect locally; DNN, transformer connects everything; could there be something in between?)