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.