Using deep-learning on graph data for binary classification
Feeding arbitrary graphs as inputs to any current general purpose ML algorithm, unless your problem and graphs are very specific (e.g., all graphs on a handful of nodes, or the size of your training set is of the same scale as the number of possible graphs of that size, or there is some very simple dependency - e.g. output is determined by the presence of some particular edge, etc) seems a rather pointless approach. 

You can encode all NP-complete problems or e.g. the halting problem by a graph or a directed graph and few other inputs, and a 0/1 label. 

One of very few successful ML algorithms that applied neural networks for a combinatorial problem was AlphaGo/AlphaZero, but it relied heavily on some specific properties of the game, the possibility to generate infinite amount of training data via self-play and enormous resources.

What you did so far (trying to construct features based on your graphs and your particular problem) makes much more sense in practice, I would explore this path further. There is also some recent literature that tries to assign graph nodes vectors of numbers, or "node embeddings", but this might work better for a specific type of graphs (sparse networks, where some additional data is available per node).