[È˹¤ÖÇÄÜ]CS224W: Machine Learning with Graphs - 03 Node Embeddings

Node Embeddings

1. Graph Represnetation Learning

Graph represnetation learning alleviates the need to do feature engineering every single time (automatically learn the features)
Goal: efficient task-independent feature learning for machine learning with graphs
Why embedding?

• Similarity of embeddings between nodes indicates their similarity in the netwrok
• Encode network information
• Potantially used for many downstream predictions (node classification, link prediction, graph prediction, anomalous node detection, clustering¡­)

2. Node Embeddings: Encoder and Decoder

Goal: encode nodes so that similarity in the embedding space approximates similarity in the graph
a) Encoder ENC maps from nodes to embeddings (a low-dimensional vector)
b) Define a node similarity function (i.e., a measure of similarity in the original network)
c) Decoder DEC maps from embeddings to the similarity score
d) Optimize the parameters of the encoder so that similarity$(u,v)¡Öz_v^T{z}_u$

1). ¡°Shallow¡± Encoding

Simplest encoding approach: encoder is just an embedding-lookup so each node is assigned a unique embedding vector
$$\text{ENV}(v)=z_v=Z?v$$
where $Z$ is matrix and each column is a node embedding and $v$ is an indicator vector with all zeroes excepy a one in column indicating node $v$
Methods: DeepWalk, node2vec

3. Random Walk Approaches for Node Embeddings

• Vector $z_u$ is the embedding of node $u$
• Probability $P(v¨O{z}_u)$ is the (predicted) probability of visiting node $v$ on random walks starting from node $u$
• Random walk: given a graph and a starting point, we select one of its neighbors at random and move to this neighbor; then we select a neighbor of this point at random and move to it, etc. The (random) sequence of points visited this way is a random walk on the graph.

a. Random-walk Embeddings

$z_u^T{z}_v¡Ö\text{probability?that?u?and?v?co-occur?on?a?random?walk?over?the?graph}$

• Estimate probability $P_R(v¨Ou)$ of visiting node $v$ on a random walk starting from node $u$ using the random walk strategy $R$
• Optimize embeddings to encode these random walk statistics

Why random walks?

• Expressivity: flexible stochastic definition of node similarity that incorporates both local and higher-order neighborhood information (If a random walk starting from node $u$ visits $v$ with high probability, $u$ and $v$ are similar)
• Efficiency: do not need to consider all node pairs when training; only need to consider pairs that co-occur on random walks

b. Unsupervised Feature Learning

Intuition: find embedding of nodes in $d$-dimensional space that preserves similarity
Idea: learn node embedding such that nearby nodes are close together in the network
$N_R(u)$: neighborhood of $u$ obtained by the strategy $R$
Goal: learn a mapping $f:u¡ú{\mathbb{R}}_d$: $f(u)=z_u$
Log-likelihood objective:
$$\underset{f}{\max }\underset{u¡ÊV}{¡\AE }logP(N_R(u)¨O{z}_u)$$
Given node $u$, we want to learn feature represnetations that are predictive of the nodes in its random walk neighborhood $N_R(u)$

c. Random-walk Optimization

a) Run short fixed-length random walks starting from each node $u$ in the graph using the random walk strategy $R$
b) For each node $u$, collect $N_R(u)$, the multiset of nodes visited on random walks starting from $u$
c) Optimize embeddings
$$\underset{f}{\max }\underset{u¡ÊV}{¡\AE }\log P(N_R(u)¨O{z}_u)$$
Parameterize $P(v¨O{z}_u)$ using softmax
$$P(v¨O{z}_u)=\frac{\exp (z_u^T{z}_v)}{{¡\AE }_{n¡ÊV}\exp (z_u^T{z}_n)}$$
Let
$$L=\underset{u¡ÊV}{¡\AE }\underset{v¡ÊN_R(u)}{¡\AE }?\log P(v¨O{z}_u)=\underset{u¡ÊV}{¡\AE }\underset{v¡ÊN_R(u)}{¡\AE }?\log (\frac{\exp (z_u^T{z}_v)}{{¡\AE }_{n¡ÊV}\exp (z_u^T{z}_n)})$$
Optimizing random walk embeddings = Finding embeddings $z_u$ that minimizes $L$
Time complexity: $O(¨O{V}^2¨O)$
Solution: Negative sampling
$$\log (\frac{\exp (z_u^T{z}_v)}{{¡\AE }_{n¡ÊV}\exp (z_u^T{z}_n)})¡Ö\log (¦Ò(z_u^T{z}_v))?\underset{i=1}{\overset{k}{¡\AE }}\log (z_u^T{z}_{n_i}),n_i¡«P_V$$
where $¦Ò(?)$ is sigmoid function and $n_i$ follows random distribution over nodes
Instead of normalizing w.r.t. all nodes, just normalize against $k$ random ¡°negative samples¡± $n_i$
Sample $k$ negative nodes each with probability proportional to its degree ($k=5¡«20$ in practice)
To minimize $L$, we can use gradient descent (GD) or stochastic gradient descent (SGD)
How to randomly walk
Simplest idea: just run fixed-length, unbiased random walks starting from each node

d. Overview of Node2vec

• Goal: embed nodes with similar network neighborhoods close in the feature space
• Key observation: flexible notion of network neighborhood $N_R(u)$ of node $u$ leads to rich node embeddings
• Develop biased $2^{nd}$ order random walk $R$ to trade off between local (BFS) and global (DFS) views of the network

Interpolating BFS and DFS
Two parameters:

• Return parameter $p$: return back to the previous node
• In-out parameter $q$ (ratio of BFS vs DFS): moving outwards (DFS) or inwards (BFS)

Biased Random Walks
Idea:remember where the walk came from

• BFS-like walk: low value of $p$
• DFS-like walk: low value of $q$

Node2vec Algorithm
a) compute random walk probabilities
b) simulate $r$ random walks of length $l$ start from each node $u$
c) optimize the node2vec objective using SGD
Time Complexity: linear
Steps are individually parallelizable

e. Other Random Walk Ideas

• Different kinds of biased random walks: based on node attributes/learned weights
• Alternative optimization schemes: directly optimize based on 1-hop and 2-hop random walk probabilities
• Network preprocessing techniques: run random walks on modified versions of the original network

4. Embedding Entire Graphs

To be updated

1). Node-level features: Overview

Goal: characterize the structure and position of a node in the network

• Node degree
• Node centrality
• Clustering coefficient
• Graphlets

2). Node degree

• The degree $k_v$ of node $v$ is the number of edges (neighboring nodes) the node has
• Treats all neighboring nodes equally

3). Node centrality

• Node degree counts the neighboring nodes without capturing their importance.
• Node centrality $c_v$ takes the node importance in a graph into account
• Different ways to model importance: eigenvector centrality, betweenness centrality, closeness centrality and so on.

a. Eigenvector centrality

• A node $v$ is important if surrounded by important neighboring nodes $u¡ÊN(v)$.
• $c_v=\frac{1}{¦Ë}{¡\AE }_{u¡ÊN(v)}{c}_u$, $¦Ë$ is some positive constant.
• $¦Ëc=Ac$, $A$ is the adjacency matrix $A_{uv}=1$ if $u¡ÊN(v)$ and $c$ is centrality vector
• The largest eigenvector ${¦Ë}_{max}$ is always positive and unique
• The leading eigenvector $c_{max}$ is used for centrality

b. Betweenness centrality

• A node is important if it lies on many shortest paths between other nodes
  $$c_v=\underset{sªÁ=vªÁ=t}{¡\AE }\frac{\#(\text{shortest?paths?between?s?and?t?that?contain?v})}{\#(\text{shortest?paths?between?s?and?t})}$$

c. Closeness centrality

• A node is important if it has small shortest path lengths to all other nodes
  $$c_v=\underset{uªÁ=v}{¡\AE }\frac{1}{\#(\text{shortest?paths?length?between?u?and?v})}$$

4). Node Features: Clustering Coefficient

• Measures how connected the neighboring nodes of $v$ are
  $$e_v=\underset{uªÁ=v}{¡\AE }\frac{\#(\text{edges?among?neighboring?nodes})}{{(}_2^{k_v})}¡Ê[0,1]$$
  where ${(}_2^{k_v})$ is the number of node pairs among $k_v$ neighboring nodes

5). Node Features: Graphlets

Observation: clustering coefficient counts the #(triangles) in the ego-network
Idea: we can generalize the above by counting #(pre-specified subgraphs, i.e., graphlets)

• Graphlets: rooted connected non-isomorphic subgraphs.
• Graphlet Degree Vector (GDV): Graphlet-based features for nodes

Compare with node degree and clustering coefficient
Degree counts #(edges) that a node touches
Clustering coefficient counts #(triangles) that a node touches
GDV counts #(graphlets) that a node touches

• Graphlet Degree Vector (GDV): a count vector of graphlets rooted at a given node.
• Considering graphlets on 2 to 5 nodes we get vector of 73 coordinates is a signature of a node that describes the topology of its neighborhood and captures its interconnectivities out to a distance of 4 hops
• GDV provides a more detailed measure of a node¡¯s local network topology than node degrees or clustering coefficient

4. Link-level Tasks

The task is to predict new links based on existing links.
When testing, all node pairs (no existing links) are ranked, and top $K$ node pairs are predicted.
The key is to design features for a pair of nodes
Tow formulations

• Links missing at random: remove a random set of links and then aim to predict them
• Links over time: given $G[t_0,t_0^{{}^{¡ä}}]$, a graph on edges up to time $t_0^{{}^{¡ä}}$, output a ranked list $L$ of links (not in $G[t_0,t_0^{{}^{¡ä}}]$) that are predicted to appear in $G[t_1,t_1^{{}^{¡ä}}]$

Methodology: compute score $c(x,y)$ for each pair of nodes $(x,y)$, sort pairs $(x,y)$ by the decreasing score $c(x,y)$, predict top $n$ pairs as new links, see which of these links actually appear in $G[t_1,t_1^{{}^{¡ä}}]$

1). Link-level Features: Overview

• Distance-based feature
• Local neighborhood overlap
• Global neighborhood overlap

2). Distance-based feature

Shortest-path distance between two nodes. However, this does not capture the degree of neighborhood overlap.

3). Local neighborhood overlap

Captures the number of neighboring nodes shared between two nodes $v_1$ and $v_2$

• Common neighbors: $¨ON(v_1)¡ÉN(v_1)¨O$
• Jaccard¡¯s coefficient: $\frac{¨ON(v_1)¡ÉN(v_1)¨O}{¨ON(v_1)¡ÈN(v_1)¨O}$
• Adamic-Adar index: ${¡\AE }_{u¡ÊN(v_1)¡ÉN(v_1)}\frac{1}{log(k_u)}$
  Limitation: metric is always zero if the two nodes do not have any neighbors in common. However, the two nodes may still potentially be connected in the future.

4). Global neighborhood overlap

• Power of adjacency matrix: let $P_{uv}^{(K)}=$ #(paths of lenght $K$ between $u$ and $v$), then $P^{(K)}=A^K$
• Katz index: count the number of paths of all lengths between a given pair of nodes
  $$S_{uv}=\underset{l=1}{\overset{¡Þ}{¡\AE }}{¦Â}^l{A}_{uv}^l$$
  $$S=\underset{l=1}{\overset{¡Þ}{¡\AE }}{¦Â}^l{A}^l=(I?¦ÂA{)}^{?1}?I$$

4. Graph-level Features

1). Kernel Methods

Idea: design kernels instead of feature vectors

• Kernel $k(G,G^{{}^{¡ä}})¡Ê\mathtt{R}$ measures similarity between data
• Kernel matrix $\mathtt{K}=(k(G,G^{{}^{¡ä}}){)}_{G,G^{{}^{¡ä}}}$ must always be positive semidefinite (i.e., has positive eigenvalues)
• There exists a feature representation $?$ such that $k(G,G^{{}^{¡ä}})=?(G{)}^T?(G^{{}^{¡ä}})$
• Once the kernel is defined, off-the-shelf ML model, such as kernel SVM, can be used to make predictions.

Graph kernels
Goal: design graph feature vector $?(G)$
Key idea: Bag-of-Words (BoW)* for a graph (regard nodes as words)
*: BoW simply uses the word counts as features for documents

• Graphlet kernel
• Weisfeiler-Lehman kernel
• rando-walk kernel, shortest-path graph kernel and many more

2). Graphlet Features

Key idea: count the number of graphlets in a graph
Note: Definition of graphlets here is different from node-level features.

• Nodes in graphlets here do not need to be connected
• The graphlets here are not rooted

Given a graph $G$ and a graphlet list $G_k=(g_1,g_2,...,g_n)$, define the graphlet count vector $f_G$ as
$$(f_G{)}_i=\#(g_i?G)\text{for?i=1,2,...,n}$$
Given two graphs $G$ and $G^{{}^{¡ä}}$, graphlet kernel is
$$k(G,G^{{}^{¡ä}})=h_G^T{h}_G^{{}^{¡ä}}$$
where $h_G=\frac{f_G}{sum(f_G)}$
Limitations: counting graphlets is expensive.

• Counting size-$k$ graphlets for a graph with size $n$ by enumeration takes $n^k$
• This is unavoidable in the worst-case since subgraph isomorphism test is NP-hard
• If a graph¡¯s node degree is bounded by $d$, an $O(n{d}^{k?1})$ algorithm exists to count all the graphlets of size $k$

3). Weisfeiler-Lehman Kernel

Goal: design an efficient graph feature descriptor $?(G)$
Idea: use neighborhood structure to iteratively enrice node vocabulary
Color refinement: given a graph $G$ with a set of nodes $V$, assign an initial color $c^0(v)$ to each ndoe $v$. Then iteratively refine node colors by
c k + 1 ( v ) = HASH ( { c k ( v ) , c k ( u ) u ¡Ê N ( v ) } ) c^{k+1}(v)=\text{HASH}(\{c^k(v), {c^k(u)}_{u\in N(v)}\}) ck+1(v)=HASH({ck(v),ck(u)u¡ÊN(v)?})
where HASH maps different inputs to different colors. After $K$ steps of color refinement, $c^k(v)$ summarizes the structure of $K$-hop neighborhood
WL is computationally efficient
The time complexity for color reinement at each step is linear in #(degs), since it involves aggregating neighboring colors.