2
$\begingroup$

Sorry if this is a newbee question, I'm not an expert in data science, so this is the problem:

We have a directed and weighted graph, which higher or lower weight values does not imply the importance of the edge (so preferably the embedding algorithm shouldn't consider higher weights as more important), they are just used to imply the timing of the events which connect the nodes, so the higher weighted edges are events that have happened after the lower ones.

There can be multiple edges between nodes, and I want to do a binary classification using deep learning, meaning that my model gets a embedded graph vector as input and decides if its malicious(1) or not(0).

So what is the best state of the art graph embedding algorithm for this task that can capture as much information as possible from the graph? i read some graph embedding papers but couldn't find any good comparison of them since there are so many new ones.

IMPORTANT NOTE: One problem i have seen with some of the graph embedding algorithms, is that they try to have a small vector dimension, since i guess they are used in fields which there are a LOT of nodes so they need to do this, but in this task its not really important, the nodes are the functions in the program, and they very rarely go above 2000 functions, so even if the algorithm creates a 20k dimensions its no problem, I'm saying this because some of the algorithms that I'm reading will produce a vector that even has lower dimensions compared to number of the nodes in the graph! and that causes loss of information in my opinion. so to sum up, the performance and large vector size is not a problem in my task. so preferably the algorithm should gather as much information as possible from the graph.

Improve this question
$\endgroup$
6
  • $\begingroup$ Related (maybe duplicate?): datascience.stackexchange.com/questions/24081/… $\endgroup$
    – Itamar Mushkin
    Mar 24, 2020 at 8:17
  • $\begingroup$ @ItamarMushkin thanks but I'm not looking for their definitions, I know the basic and have read some of graph embedding algorithms mentioned, but all of them will produce a not very large vector which causes loss of information, was wondering if there is any algorithm that gathers as much as information as possible at the penalty of performance and large vector size, i guess since this might not be ideal for many tasks, such algorithm might not be used in many papers so its hard to find. $\endgroup$
    – OneAndOnly
    Mar 24, 2020 at 8:23
  • $\begingroup$ I thought you can define the embedding dimension... $\endgroup$
    – Itamar Mushkin
    Mar 24, 2020 at 8:32
  • $\begingroup$ @ItamarMushkin that was based on a paper i was reading, so is this false? : "Graph embeddings map the given graph G to a d-dimensional feature space Φ(υ) where the dimension of the embedding is significantly smaller than the number of nodes." paper : Deep learning for effective Android malware detection using API call graph embeddings $\endgroup$
    – OneAndOnly
    Mar 24, 2020 at 9:47
  • $\begingroup$ Well, word2vec takes the dimension as an input (I checked again on wikipedia, just to be sure), so I'm guessing that Node2Vec does so too... $\endgroup$
    – Itamar Mushkin
    Mar 24, 2020 at 11:17

1 Answer 1

Reset to default
0
$\begingroup$

I'm no expert myself, but recently (i.e. this is true to 2019), I've heard (at a meetup from an expert) that Node2Vec is the SOTA.

Here's a link to a post on Medium explaining it - basically, Node2Vec generates random walks on the graph (with hyper-parameters relating to walk length, etc), and embeds nodes in walks the same way that Word2Vec embeds words in a sentence.

Note that since random walks are generated on the graph, intuitively you don't have to use edge weights, and can use multiple edges.

P.S. There's an older (2014) algorithm for this, called "DeepWalk", which I don't know much about but is supposed to be similar, simpler, and not as performative. I'm just adding this in case you want to search the term.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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