Skip-graph

[alanyuchenhou]

paper

Skip-graph: Learning graph embeddings with an encoder-decoder model

problem: labeled graph embedding

• given: an undirected graph where each node has a label
• task: embed this graph into a vector

solution: skip graph

0. sample random walks from the graph
1. divide each walk into 3 sections: section 0, section 1, section 2 to produce the following data set:

walk	section 0	section 1	section 2
HOCOHCOHCOHC	HOCO	HCOH	COHC
HCOHHOCOCOHC	HCOH	HOCO	COHC
...	...	...	...

0. train skip graph model (a rebranding of skip-thought model)
   • architecture: RNN (sequential input, sequential output), encoder(embedding layer) -> 2 decoders
   • input: section 1
   • output: (section 0, section 2)
1. collect all walk embeddings from the embedding layer weights
2. aggregate (average, max) all walk embeddings into a graph embedding

evaluation: graph classification

• given a set of graphs where each graph has a label
• task: use skip-graph model to embed each graph and use another model to learn to predict the graph label from a graph embedding

datasets

4 chemical compound datasets (each graph is a compound; each label is the compound anti-cancer propoerty, sampled equal amount of positive and negative examples):

• NCI81
• NCI83
• NCI123
• HIV

code: skip thoughts

https://github.com/ryankiros/skip-thoughts

[alanyuchenhou]

This approach takes advantage of the characteristic of a specific type of graphs which have very limited types of nodes. For example, chemical compounds are graphs composed of very limited types of atoms. This characteristic makes graph embedding much easier because it allows nodes to be treated as enumerables, much simpler than unique node vectors in high dimensional space.

If I'm to work on graph embedding I should revisit this interesting approach.