How can Machine Learning be used to find attributes/characteristics of graphs?

Question

I am aware ML is not necessary for many graph classification problems (as the graph theorists have many clever solutions), but I'm specifically interested in ML approaches to these types of questions. I imagine if you had enough training examples (1000s?) you could use a supervised approach for classification type of questions. I also assume an adjacency matrix would be a good data representation to use for ML approaches to undirected graph classification. Example problems are shown below.

1.) Given an undirected graph represented by an adjacency matrix, broadly speaking, how (if possible) could machine learning be used to find if said graph has a hamiltonian path?

2.) Given an undirected graph represented by an adjacency matrix, how can ML be used to determine if the graph is a tree?

Answer 1

ML is not likely to be a good approach for these kinds of problems. It will probably perform far worse than a hand-designed algorithm. Current ML is not magic; it is just a form of pattern-matching.

Answer 2

This depends heavily on the attribute you have in mind: I see no point in using ML for tree recognition for instance since we already have very practical exact algorithms for this. But sure, if you wanted to, nothing is stopping you from taking a bunch of graphs, representing them in some way and labeling them ("is a tree", "is not a tree") and training a classifier. Probably not very useful though.

With that being said, NP-hard problems could be more interesting but even then there are different approaches in the literature.

You can roughly say that there are at least three types of approaches:

• (i) using ML for choosing a heuristic that will perform well for a given instance,
• (ii) using ML for somehow finding the answer directly; and
• (iii) using ML for helping the human design heuristics.

For (i), a good keyword to search for is "algorithm portfolio". The distinction between say (ii) and (iii) is not that clear or easy to make. For (iii), you could have a look at [1]. For (ii), I can mention at least the works [2] and [3] for TSP and maximum clique, respectively. These areas develop at an enormous speed, so you will find plenty of follow-up work to this already recent work.

---

[1] Khalil, Elias, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. "Learning combinatorial optimization algorithms over graphs." In Advances in Neural Information Processing Systems, pp. 6348-6358. 2017.

[2] Prates, Marcelo, Pedro HC Avelar, Henrique Lemos, Luis C. Lamb, and Moshe Y. Vardi. "Learning to solve NP-complete problems: A graph neural network for decision TSP." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 4731-4738. 2019.

[3] Lauri, Juho, and Sourav Dutta. "Fine-Grained Search Space Classification for Hard Enumeration Variants of Subset Problems." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 2314-2321. 2019.