Introduction

We have various ml talks in graphs, where the goal is to classify nodes or doing a link prediction and etc like shown below

Node Classification

Link Prediction

And machine learning life cycle includes lots of steps, where we do feature engineering on raw data, to get structured data suited for the ml task at hand, and using the structured data we use some learning algorithm to build our final model. Feature engineering used to be core challenge until neural networks in case of image recognition, nlp and other ML tasks. Now we just let the neural network figure out embeddings of our original data instead of engineering them by hand. We want that also to happen when it comes to ml tasks in Graphs.

Our goal is to do feature learning on nodes/graphs efficiently independent of what the downstream task, may it be node classification, clustering, link prediction etc. We want an effective and efficient representation of nodes in an embedding space $f:u\to {\Re }^d$, that captures all the network structure in its neighbourhood.

We want to map each node in a network into a low-dimensional space, who distribution represents the nodes in the network. And similarity of embeddings between nodes indicates their network similarity. And encode network information and generate a node representation.

From adjacency matrix of size $n\times n$ to a low d-dimensional latent space where $d<<n$. So that we can use these embeddings for downstream ML tasks.

Below is an example embedding of Zachary karate club network nodes into a two dimensional space, keeping the clustered nodes in the network close in the 2-d space.

Finding embeddings for graphs is harders as they have complex topological structure, no spatial locality like in grids like images, nor like sequences like in nlp. There is no reference point in case of graphs. The same graph of size n can be represented $n!$ different adjacency matrices that are isomorphic. They often have dynamic and have multimodal features.

Embedding Nodes

Assume a Graph $G$ with vertex set $V$ and adjacency matrix $A$, for now a non weighted edge matrix. For now let's try to just use network structure, with no node features or any other extra information.

Our goal is to encode nodes in way the similarity in the embedding space approximates(e.g cosine similarity or dot product) similarity in the original network. $similarity(u,v)\approx z_v^T{z}_u$

We need to define the $similarity$ function in the network space, define the encoder function $ENC$ a mapping function from nodes to embeddings. And finally optimize the parameters of the encoder so that $similarity(u,v)\approx z_v^T{z}_u$

Encoder function maps node to low dimensional embedding space. $ENC(v)=z_v$

Shallow Encoding.

Simplest encoder is just an embedding lookup. $ENC(v)=ZV$ where $Z\in {\Re }^{d\times |\mathcal{V}|}$, a matrix, with each column is a node embedding, that we have to learn and $V\in {\mathcal{I}}^{|v|}$, an indicator vector, with all zeros except a one in column indicating a node $v$

Each node is assigned to a unique embedding vector. We have many methods to figure out this embedding lookup, like DeepWalk, node2vec, TransE.

Node similarity

Our another challenge is how to define node similarity, should two nodes be similar if they are connected, or share neighbours, or have similar structural roles and how do we automatically infer these properties of nodes.

Random Walk Embeddings

The following section is based on the following two papers DeepWalk Perozzi et al. 2014, node2vec Grover et al 2016

Given a graph and a starting node, we select a neighbor of it at random, and move to this neighbor; then we select a neighbor of this node at random and move to it and continue the process. The random sequence of nodes selected this way is a random walk on the graph.

And now we can define the similarity of two nodes as, the probability that $u$ and $v$ co-occuring on a random walk over the network. The more probable the similar they are.

Estimate probability of visiting node $v$ on a random walk starting from node $u$ using some random walk strategy $R$ and optimize embeddings to encode these random walk statistics. Similarity function encodes random walk similarity. $z_u^T{z}_v\approx P_R(v|u)$

We use random walks for their expressivity and efficiency. Its easy to express them as they have a flexible stochastic definition of node similarity that incorporates both local and high-order neighbourhood information and its easy to parametrize both locality and high-orderness of a random walk. Its efficient because we do not have to consider all nodes pairs when training, only need to consider pairs that co-occur on random walks.

Unsupervised Feature Learning

Learn node embeddings of nodes to d-dimensions that preserve similarity. We define similarity of of nodes using node neighbourhood of node u $N_R(u)$ using a random walk strategy $R$

Given a graph $G=(V,E)$ we need a mapping $z:u\to {\Re }^d$. Using the log-likelihood objective $\underset{z}{\max }\sum _{u\in V}\log P(N_R(u)|z_u)$, where $N_R(u)$ is neighbourhood of node $u$ by strategy $R$.

Given a node $u$, we want to learn feature representations that are predictive of the nodes in its neighbourhood $N_R(u)$ using the log-likelihood objective above.

Random walk optimization

We will run short fixed-length random walks starting from each node on graph using some strategy $R$. For each node $u$ collect $N_R(u)$, the multiset of nodes visited on random walks starting from $u$, its a multiset because the same node can be visited multiple times on random walks of a single node. And optimize embeddings according to the objective function$\underset{z}{\max }\sum _{u\in V}\log P(N_R(u)|z_u)$. We want to maximize the conditional probability given embedding vector $z_u$ is going to be close to the node neighbourhood of $u$.

We end up with the following loss function. Optimize embeddings to maximize likelihood of random walk co-occurences.

$\mathcal{L}=\sum _{u\in V}\sum _{v\in N_R(u)}-\log (P(v|z_u))$

And parameterize $P(v|z_u)$ using softmax. We want node $v$ to be most similar to node $u$ out of all nodes n, and using this intuition ${\sum }_i\exp (x_i)\approx {\max }_i\exp (x_i)$ we get

$P(v|z_u)=\frac{exp(z_u^T{z}_v)}{{\sum }_{n\in V}exp(z_u^T{z}_n)}$

Replacing $P(v|z_u)$ with its parameterized version we get

$\mathcal{L}=\sum _{u\in V}\sum _{v\in N_R(u)}-\log \left(\frac{exp(z_u^T{z}_v)}{{\sum }_{n\in V}exp(z_u^T{z}_n)}\right)$

The loss function $\mathcal{L}$ is predicted probability of $u$ and $v$ co occurring on a random walk, for all $v$ seen on a random walk starting from $u$ and for all $u$ in our network. Optimizing random walk embeddings is the same as finding embeddings $z_u$ that minimize $\mathcal{L}$

But doing this naively is of $O(|V{|}^2)$ complexity because of the normalization term in the softmax. So we use negative sampling to approximate the softmax term like below

$log\left(\frac{exp(z_v^T{z}_u)}{{\sum }_{n\in V}exp(z_u^T{z}_n)}\right)\approx log(\sigma (z_u^T{z}_v))-\sum _{i=1}^{k}log(\sigma (z_u^T{z}_{n_i})),n_i\sim P_V$

The sigmoid function makes each term a probability and instead of normalizing w.r.t all nodes, just normalize against $k$ random "negative samples" $n_i$ which is a random distribution over all the nodes. Even though this is a different objective function, negative sampling is a form of Noise Contrastive Estimation(NCE) which approximately maximizes the log probability of softmax. New formulation corresponds to using a logistic regression sigmoid function to distinguish the target node $v$ from nodes $n_i$ sampled from background distribution $P_v$. I also didn't really understand the intuition behind this but you can find the original negative sampling paper here https://arxiv.org/pdf/1402.3722.pdf

We sample $k$ negative nodes proportional to the degree. Higher $k$ gives more robust estimates, and higher $k$ correspond to higher bias on negative events. In practice $k=5to20$

So far given a random walk strategy we described how to optimize embeddings. The simplest random walk is to just run fixed-length, unbiased random walks starting from each node described in the DeepWalk paper but such notion of similarity is too constrained. We need a more general approach for this.

node2vec: Biased Walks

We needed a flexible notion of network neighbourhood $N_R(U)$ of node $u$ that will eventually lead to rich node embeddings. The random walk strategy of just running fixed-length walks is too constrained. We want to develop a $2^{nd}$ order random walk strategy $R$ to generate network neighbourhood $N_R(u)$ of node $u$.

We want a flexible, biased random walk strategy that can trade off between local and global views of the network. Local microscopic view by doing a BFS and global macroscopic view by doing a DFS. We need a way of interpolating both BFS and DFS. We do this by having two parameters $p$ and $q$. Return parameter $p$ to return back to the previous node in the walk, and In-out parameter $q$ to decide if we should do BFS or DFS at a given node. Moving outwards is DFS and inwards BFS. Intuitively, $q$ is the ratio of BFS vs. DFS.

Biased $2^{nd}$-order random walks explore the network neighbourhoods. In each walk, we have to remember where that walk came from, in case we need to step back. In the image below, if a random walk traversed the edge $(s_1,w)$ and is now at $w$. Now we have 4 options to go from node $w$, go back to $s_1$, go to $s_2$ which is BFS option wrt $s_1$, or go to $s_3$ or $s_4$ that are DFS options wrt $s_1$. If $p$ is the return parameter, and q walk-away parameter. We make the next move according to the unnormalized probabilities in this image. $p$ and $q$ are model transition probabilities and are our model hyperparameters.

So following this strategy we compute random walk probabilities, simulate $r$ random walks of length $l$ starting from each node $u$, optimize the node2vec objective using stochastic gradient descent.

We can use these embeddings to do clustering/community detection, node classification or link prediction.

Clustering and node classification are straightforward, just do a k-means on the embeddings or classify on the embed space vectors.

When it comes to link-prediction. Predict edge $(i,j)$ based on $f(z_i,z_j)$, where we can concatenate, avg, product, or take a difference between the embeddings;

• Concatenation: $f(z_i,z_j)=g([z_i,z_j])$
• Hadamard: $f(z_i,z_j)=g(z_i\ast z_j)$ per coordinate product
• Sum/avg: $f(z_i,z_j)=g(z_i+z_j)$
• Distance: $f(z_i,z_j)=g(||z_i-z_j|{|}_2)$

There are other notions of similarity, Adjacency-based, multi-hop similarity definitions, or random walk approaches. No one method is best in every scenario. We must choose task specific similarity approach. node2vec performs better on node classification while multi-hop methods performs better on link prediction. (Goyal and Ferrara, 2017 Survey)

TransE, Translating embeddings for Multi-relational data.

TransE is an application of Embeddings to the Knowledge Graph. A knowledgraph is composed of facts/statements about interrelated entities. Nodes are entities and edges are relationships between the entities. The relationships can be of many types. These knowledge graphs are huge, with limited information about how entities are related to each other, which might limit us in doing downstream tasks related to knowledge graphs. So predicting the edges/relationships between entities is an important problem. We want a link prediction model that learns from local and global connectivity patterns in the knowledge graph, taking into account entities and relationships of different types at the same time. Relation predictions are performed by using the learned patterns to generalize observed relationships between an entity of interest and all the other entities.

In TransE, relationships between entities are represented as triplets $(h,l,t)$, head entity $h$, relation $l$ and tail entity $t$. Entities are first embedded in an entity space ${\Re }^k$ like previous methods. And relations are represented as translations, if for a $(h,l,t)$ there exists a relationship between $h$ and $t$, we consider $h+l\approx t$ else $h+l\ne t$.

Entities and relations are initialized uniformly and normalized. Triplet negative sampling with links that does not appear in KG and using comparative loss, which favours lower distance values for valid triplets, high distance values for corrupted ones.

$\mathcal{L}=\sum _{((h,l,t),(h^{\prime },l,t^{\prime }))\in T_{batch}}\Delta [\gamma +d(h+l,t)-d(h^{\prime }+l,t^{\prime })]$

In the above equation $(h,l,t)$ is a positive sample and $(h^{\prime },l,t^{\prime })$ a corrupted one.

Embedding Entire Graphs

We want to be able to embed entire graphs into the latent space, for tasks like graph classification or graph anomaly detection. Like identifying a toxic vs non-toxic molecules and etc.

A simple way of doing it is just sum all the node embeddings of a graph to get graph embedding. From Duvenaud et al., 2016 where they used graph embeddings to classify molecules.

$z_G=\sum _{v\in G}{z}_v$

Or we can introduce a virtual node to represent the graph or a subgraph and run a standard node embedding technique. And then use the embedding of that node in place of a graph or a subgraph. Proposed by Li et al., 2016 as a general technique for subgraph embedding.

Anonymous Walk Embeddings

Another approach is by using [Anonymous Walk Embeddings (https://arxiv.org/pdf/1805.11921.pdf). Essentially we do random walks in the graph and anonymize the nodes visited. States in anonymous walk correspond to the index of the first time we visited the node in a random walk. Consider the following 3 walks in a graph with nodes $A,B,C,D,E,F,\cdots$

• Random Walk 1: $[A\to B\to C\to B\to C]$
• Random Walk 2: $[C\to D\to B\to D\to B]$
• Random Walk 3: $[A\to B\to A\to B\to D]$

After anonymising the nodes, the first two random walks are essentially the same. Because the first three nodes in both walks are different and the 4th node in both the walks is the same as the 2nd node and 5th node is the same as the 3rd node. We store both random walk 1 and random walk 2 as $1\to 2\to 3\to 2\to 3]$ And the anonymised walk of random walk 3 is $[1\to 2\to 1\to 2\to 3]$.

Essentially using anonymous random walks we are capturing where are the random walks getting stuck in during a random walk or how often it's visiting the same node. The idea is that through anonymised random walks we are capturing the graph behaviour rather than node behaviour.

Number of anonymous walks grow exponentially wrt to the length of the walks. There are 5 anonymous walks of length 3 but more than 4 Million of length 12

Enumerate all possible anonymous walks $a_i$ of $l$ steps and record their counts. Represent the graph as a probability distribution over these walks. $Z_G[i]$ is the probability of anonymous walk $a_i$ in G.

Complete counting of all anonymous walks in a large graph maybe infeasible. So we do sampling to approximate the true distribution. Generate independently a set of $m$ random walks and calculate its corresponding empirical distribution of anonymous walks.

The number of random walks $m$ needed for the distribution to have error of more than $ϵ$ with probability less than $\delta$ is $m=[\frac{2}{{ϵ}^2}(\log (2^{\eta }-2)-\log (\delta ))]$ where $\eta$ is the total number of anonymous walks of length $l$. For example we need to generate $m=122500$ random walks of length $l=7$, as there are $\eta =877$ total anonymous walks of length 7. with $ϵ=0.1$ and $\delta =0.01$

We need to learn embedding $z_i$ of every anonymous walk $a_i$, The embedding of a graph $G$ is then sum/avg/concatenation of walk embeddings $z_i$

$w_t^u$ is the t-th random walk starting at node $u$. Embed walks such that next walk can be predicted. Set $z_i$ such that we maximize $P(w_t^u|w_{t-\Delta }^u,\cdots ,w_{t-1}^u)=f(z)$

Run $T$ different random walks from $u$ each of length $l$, $N_R(u)=[w_1^u,\cdots ,w_T^u]$, And $a_i$ be its anonymous version of walk $w_i$. We learn to predict walks that co-occur in $\Delta$ sized window. Estimate embedding $z_i$ of anonymous walk $a_i$ of $w_i$ using

$\max \frac{1}{T}\sum _{t=\Delta }^T\log P(w_t|w_{t-\Delta },\cdots ,w_{t-1})$

And the parameterized version of the log probability in the above equation is

$P(w_t|w_{t-\Delta ,\cdots ,w_{t-1}})=\frac{exp(y(w_t))}{{\sum }_i^{\eta }\exp (y(w_i))}$

$y(w_t)=b+U.\left(\frac{1}{\Delta }\sum _{i=1}^{\Delta }{z}_i\right)$ where $b\in \Re ,U\in {\Re }^d$

In summary, we represent graphs via the distribution over all the anonymous walks, sample the walks to approximate the distribution, and embed the anonymous walks.

Chapters

1. Introduction, Structure of Graphs
2. Properties of Networks and Random Graph Models
3. Motifs and Structural Roles in Networks
4. Community Structure in Networks
5. Spectral Clustering
6. Message Passing and Node Classification
7. Graph Representation Learning
8. Graph Neural Networks
9. Graph Neural Networks - Pytorch Geometric
10. Deep Generative Models for Graphs
11. Link Analysis: PageRank
12. Network Effects and Cascading Behaviour
13. Probabilistic Contagion and Models of Influence
14. Influence Maximization in Networks
15. Outbreak Detection in Networks
16. Network Evolution
17. Reasoning over Knowledge Graphs
18. Limitations of Graph Neural Networks
19. Applications of Graph Neural Networks