Notes on graph embeddings, major references are:

- Hamilton et al. 2018. Representation Learning on Networks WWW 2018 Tutorial
- Primož Godec. 2018. Graph Embeddings — The Summary

## What is Graph Embeddings?

- Graph embeddings are the transformation of property graphs to a vector or a set of vectors.
- Similar to word embeddings, which are vector representation of words.
- Two major types of graph embeddings:
- Vertex Embeddings - Each vertex has its own vector representation. Two vertices with similar properties (e.g. similar neighbours, similar connection types, etc.) should have vectors close to each other.
- Graph Embeddings - Represent the whole graph as a single vector

## Applications

There are many different machine learning tasks that are related to graphs and networks:

**node classification**: predict the class of a node**link prediction**: predict whether two nodes are connected**community detection**: detect densely linked clusters of nodes**network similarity**: determine how similar two (sub)networks are

## Challenges

- Make sure that the embeddings describe well the properties of the graphs
- The speed of creating or learning the embeddings should not increase drastically with the size of the graph
- How to determine the number of dimensions of the embedding

## Node Embeddings

- Learn a representation of the nodes in the embedding space (where the number of dimensions is smaller than the number of nodes)
- The goal is to embed nodes such that similarity in the embedding space approximates similarity of the nodes in the network
- Steps to learn node embeddings
- Define an encoder (i.e. a mapping from nodes to vectors)
- Define a node similarity function (i.e. a measure of node similarity in the original network)
- Optimize the parameters such that $z_u^{\top}z_v$ approximates $similarity(u, v)$

### Different Approaches to Similarity

#### Adjacency-based Similarity

- References:
- Similarity function is just the edge weight between two nodes $u$ and $v$ in the original network
- We want to minimize the following loss function: $\mathcal{L} = \sum_{(u,v)\in V \times V}||z_u^{\top}z_v - A_{u,v}||^2$, where $A_{u,v}$ is the corresponding cell in the adjacency matrix
- Limitations:
- $O(|V|^2)$ runtime (it must consider all node pairs)
- It only considers direct and location connections

#### Multi-hop Similarity

#### Random Walk Approaches

### Methods

#### DeepWalk

- DeepWalk: Online Learning of Social Representations
- Implementation: https://github.com/phanein/deepwalk
- DeepWalk uses local information obtained from truncated random walks tolearnlatent representations by treating walks as the equivalent of sentences.
- Steps:
- Sampling with random walks: about 32 to 64 random walks from each node will be performed
- Training skip-gram model: accept a vector representing one random walk of a node, predict the neighbour nodes (e.g. 20)
- Computing the embedding of each node

#### node2vec

- node2vec: Scalable Feature Learning for Networks
- A generalization of DeepWalk
- Parameters
**$p$ (return parameter)**: controls how likely the random walk would go back to the previous node**$q$ (in-out parameter)**: controls how likely the random walk will visit new (undiscovered) nodes in the graph

- Random walks become 2nd order Markov chains
- Increase efficient sampling rate by reusing samples, for example:
- Let $k$ be the number of steps we need to sample
- We can perform a random walk of length $l > k$, such that we can generate samples for $l - k$ nodes at once
- e.g. a random walk ${u, s1, s2, s3, s4, s5}$ results in $N(u) = {s1, s2, s3}$, $N(s1) = {s2, s3, s4}$, $N(s2) = {s3, s4, s5}$.

- DeepWalk can be considered as a special case of node2vec with $p = q = 1$

#### Structural Deep Network Embedding (SDNE)

- Structural Deep Network Embedding
- Implementation: https://github.com/suanrong/SDNE
- Does not perform random walks
- Designed to preserve the first and second order proximity:
**First order proximity**: local pairwise similarity between nodes linked by an edge, characterise local network sturcture (e.g. if a paper cites another paper, they address similar topics)**Second order proximity**: indicate the similarity of the nodes’ neighbourhood structures; if two nodes share many neighbours, they tend to be similar to each other

- SDNE is semi-supervised:
- The unsupervised component: to learn a representation to reconstruct the second order proximity of nodes
- The supervised component: to learn a representation that preserves the first order proximity of nodes

## Graph Embeddings

### Graph2vec

- graph2vec: Learning Distributed Representations of Graphs
- Implementation: https://github.com/benedekrozemberczki/graph2vec

## Collective Classification

According to Sen et al., Give a network and an object $o$ in the network, three types of correlations can be utilized to determine the label of $o$:

- Correlations between the label of $o$ and the attributes of $o$
- Correlations between the label of $o$ and the attributes of the objects in the neighbourhood of $o$
- Correlations between the label of $o$ and the unobserved labels of the objects in the neighbourhood of $o$

Collective classification refers to the combined classification of a set of interlinked objects using all three types of information described above.

Applications: classification of webpages

- Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, Tina Eliassi-Rad. Collective Classification in Network Data.

## References

### Research Papers

- William L. Hamilton, Rex Ying, Jure Leskovec. 2017. Representation Learning on Graphs: Methods and Applications. IEEE Data Engineering Bulletin, September 2017.
- Amr Ahmed et al. 2013. Distributed Large-scale Natural Graph Factorization. WWW 2013.
- Bryan Perozzi, Rami Al-Rfou, Steven Skiena. DeepWalk: Online Learning of Social Representations
- Aditya Grover, Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. KDD 2016.
- Daixin Wang, Peng Cui, Wenwu Zhu. 2016. Structural Deep Network Embedding. KDD 2016.
- Annamalai Narayanan et al. 2017. graph2vec: Learning Distributed Representations of Graphs. MLGWorkshop 2017.

### Blogs and Articles

- Alessandro Epasto and Bryan Perozzi. 2019. Innovations in Graph Representation Learning
- Primož Godec. 2018. Graph Embeddings — The Summary

### Tutorials

- Hamilton et al. 2018. Representation Learning on Networks WWW 2018 Tutorial.