3
$\begingroup$

The data:

I have certain data that I decided to represent it as a graph (I thought it would suit).
So I have the weighted graph data that includes a numeric attribute for each node. (networkx graphs).
Each graph represents a session.
Each session label is either good (1) or bad (0).

The mission:

I need to predict given an unlabeled graph, whether it's good (1) or bad (0).

What did I do so far:

I've made the ML method that calculates features (using networkx excellent algorithms) over those graphs. For example I took the networkx algorithms for calculating betweenesss, degree_centrality, closeness_centrality, etc

I've received better results than the currently available results (which didn't use a graph for representing the data): F1-Score ~ 65%, ROC_AUC ~ 90%.

My intuition:

Maybe I shouldn't randomly choose networkx function. What if I could do something smarter using deep-learning. The model should understand how bad graph looks like, a good graph looks like, and make the classification

Problems:

I'm not sure if my intuition is correct. Maybe feeding the graph as is wouldn't be enough in order for the model to learn. I feel that I need advice regarding this approach, and especially previous similar works if they exist.

Relevant previous work

http://openaccess.thecvf.com/content_cvpr_2017/papers/Monti_Geometric_Deep_Learning_CVPR_2017_paper.pdf
http://proceedings.mlr.press/v48/niepert16.pdf
https://arxiv.org/pdf/1803.03324.pdf
https://arxiv.org/pdf/1709.05584.pdf

Questions:

  1. Is anyone familiar code implementations of those previous work / other previous works?
  2. Is someone familiar for methods that do it with a weighted graph that includes node attributes?
  3. Do you agree/disagree with my intuition?
  4. Do you suggest alternate ways with handling this problem? (DL or not DL)

Thank you :)

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.