Network Embeddings

Subheading

Moscow, 2023 video

---

Graphs representation

In many fields the data have a graph structure - social: friendship graph in social networks, graph of scientific citations - man-made: internet, web, road networks, air communication networks - In biology: protein interactions, complex molecules.

Machine learning tasks on graphs and their applications

• supervised, semi-supervised
  • node classification
    • Is the account a bot
    • Predicting user age, gender, profession in a social network
    • Predicting the function of a new protein based on its interaction with others
    • article topic prediction on the basis of citations
  • link prediction
    • content recommendation in an online platform
    • forecasting drug side effects
  • community detection
    • searching for users with similar interests
    • Revealing functional groups of proteins

Objective: extract features from the graph in a form suitable for machine learning algorithms

---

Approaches to learning graph representations

Task: find a representation of graph vertices as vectors of (low-dimensional) space that preserve useful information. Normally, vectors are close in space if the vertices are close in the graph

graph embedding ~ representation learning

Approaches: 1. Based on matrix decompositions; 2. Based on random walks; 3. Graph neural networks.

---

1. Matrix Decomposition

Node representation as a dimensionality reduction problem with information preservation.

General idea: represent the graph as a matrix and decompose it.

SVD example

Notation: \(G(V,E)\) - graph with vertices \(V\) and edges \(E\) \(W\) - adjacency matrix with weights \(D\) - diagonal degree matrix \(L = D - W\) - Laplacian of the graph \(Y_i\) is the vector representation of a vertex \(i\) of dimension \(d \ll |V|\) \(I\) is a unary matrix \(\phi(Y)\) - loss function

1) Locally Linear Embedding (2000)

\(Y_i \approx \sum\limits_j{W_{ij}Yj}\) \(\phi(Y) = \sum\limits_i{||Y_i - \sum{W{ij}Yj}||^2}\) is reduced to finding the largest eigenvectors of the sparse matrix \((I-W)^T(I-W)\)

2) Laplacian Eigenmaps (NIPS, 2002)

Idea: vertex representation is close if the vertices are connected \(\phi(Y) = \frac{1}{2}\sum\limits_{i,j}{||Y_i - Yj||_2^2W_{ij}} = Tr(Y^TLY)\) \(Y^TDY = I\) is reduced to finding the smallest eigenvectors of the normalized Laplassian

\(L_{norm} = D^{-1/2}LD^{-1/2}\)

3) Cauchy Graph Embeddings (ICML 2011)

Другая метрика близости \(distance = \frac{|Y_i - Y_j|^2}{|Y_i - Y_j|^2+\gamma^2}\) \(\phi(Y) = \frac{1}{2}\sum\limits_{i,j}\frac{W_{i,j}}{|Y_i-Y_j|^2+\gamma^2}\)

The main problem is maintaining only 1st order proximity

Definitions: First-order proximity between vertices \(i\) and \(j\) = edge weight \(W_{ij}\) Let \(s_i=[s_{i1},s_{i2},s_{iN}]\) be the \(k\)-order closeness. Then the \((k+1)\)order closeness between vertices \(i\) and \(j\) = the similarity measure of vectors \(s_i\) and \(s_j\).

4) GraRep (CIKM, 2015)

Normalized transition matrix \(X^k_{i,j}=log\frac{A^k_i,j}{\sum\limits_iA^k_{i,j}}-\log\beta\) \(\phi(Y)=||X^k-Y_s^kY_t^{kT}||^2_F\) The representations for all k are concatenated. The disadvantage is the complexity of the algorithm \(O(|V|^3)\).

5) HOPE, AROPE

Take S proximity matrix instead of adjacency matrix (Katz Index, Rooted Page Rank, Common Neighbors, Adamic-Adar score)

\(\phi(Y)=||S-Y_sY_t^T||^2_F\) , сложность алгоритма \(O(|E|d^2)\)

Основные недостатки алгоритмов матричного разложения: сохранение близости только 1-го порядка и/или большая сложность алгоритма

• HOPE paper
  • authors’ code (MATLAB)
  • [add python code]

- AROPE paper - authors’ code (MATLAB + Python)

---

Word2vec

word2vec learns vector representations of words, useful in application tasks. Vectors show interesting semantic properties. For example: - king: male = queen: female ⇒ - king - man + woman = queen

word2vec explanation word2vec seminar

---

2. Random walks

Key Idea: Nodes in random walks \(\approx\) words in sentences -> use word2vec.

1) Deepwalk (KDD, 2014)

• Parameters

  • In practical tasks \(w = 10\), \(\gamma=80\), \(t=80\)
  • newer change \(w\)
  • If you lower \(w\), increase \(\gamma\), \(t\)

• DeepWalk paper

  • authors’ code (Python)
  • C++ code

2) LINE

Key Idea: - don't generate random walks - LINE paper - authors’ code (C++)

3) Node2vec

Low q - explore intra-cluster information High q - explore inter-cluster information

• node2vec paper
  • authors’ code (Python)
  • C++ code

VERSE

Random walks define a hidden similarity distribution

• VERSE paper
  • authors’ code (C++)

Useful Links

• Survey on graph embeddings and their applications to machine learning problems on graphs peerj

• RandNE paper

  • authors’ code (Python)

• FastRP paper

  • authors’ code (Python)

• NodeSketch paper

  • authors’ code