Representation Learning for Unsupervised Learning on Graphs

Oct 24^th, 2024

BMI/CS 775 Computational Network Biology�Fall 2024

Sushmita Roy

https://compnetbiocourse.discovery.wisc.edu

Some slides adapted from Prof. Anthony Gitter

Plan for this section

• Topological properties of networks (Oct 17^th, )

​

• Graph clustering and motifs (Oct 22^nd)

​

• Representation learning on graphs (Oct 24^th, Oct 29^th)

​

• Graph alignment and applications (Nov 7^th, Nov 9^th)

Goals for today

• The case for learning representations in unsupervised problems for graphs

​

• Shallow, graph structure-based representations

​

• OhmNet: Application of node2vec for multi-tissue networks

Representation learning of graphs

Hamilton, Ying, Leskovec, 2018

Learning representations for unsupervised problems on graphs

• What do we mean by unsupervised learning on graphs?
• No labels/output variables
• Why learn representations for such problems?
• Problem of interest is unsupervised in nature, e.g. community detection
• Pre-training to learn task agnostic representations and finetune later
• Could improve performance even in supervised tasks
• How?
• Some form of “self-supervised” or “unsupervised” learning
• Think of encoder-decoder framework
• We will largely focus on node representations

​

From graphs to embeddings

DeepWalk embedding of Zachary Karate Club social network

Hamilton, Ying, Leskovec, 2018

Overview of algorithms we will see

• Shallow, structure only
• Matrix factorization
• Random walk based methods: Node2vec, DeepWalk
• Deep, structure and node features
• Graph AutoEncoder and Graph Variational AutoEncoder

​

Goals for today

• The case for learning representations in unsupervised problems for graphs

​

• Shallow, graph structure-based representations

​

• Application of node2vec for multi-tissue networks

Notation

Unsupervised representation learning on graphs

Encoder-decoder framework of representation learning

Hamilton, Ying, Leskovec, 2018

Encoder-decoder framework

A set of training node pairs

Classes of node embedding methods

• Shallow embedding
• Matrix factorization-based methods
• Laplacian eigen maps
• Graph Factorization
• GraRep
• HOPE
• Random walk-based methods
• DeepWalk
• Node2vec
• Deep embedding
• Graph autoencoders
• Deep Graph Infomax

​

Laplacian eigenmaps

• Encoder:

​

• Decoder:

​

​

• Loss function

​

​

Coming from the original graph

Graph factorization, GraRep, HOPE

Random-walk based methods

• More recent methods are based on random walk statistics
• Key idea: nodes that co-occur in the same short random walks should have similar embeddings
• Encoders are similar to matrix factorization methods
• These measures are more flexible than matrix factorization
• DeepWalk
• Node2vec

Hamilton, Ying, Leskovec, 2018; See also node2vec+ better handles edges weights. Liu et al. bioRxiv 2022 https://doi.org/10.1101/2022.08.14.503926

Random walk based methods

• Random walk: Instead of deterministically traversing a graph, we can probabilistically transition from a vertex to its neighbor

DeepWalk

• In DeepWalk, the decoding function is defined as:

​

​

​

​

​

​

​

• Unbiased random walks
• Naively optimizing with this normalization term is expensive: DeepWalk uses node grouping and hierarchical softmax to reduce the number of nodes in the normalization term.

​

​

​

​

​

​

Perozzi et al. 2014

Motivation for node2vec

• Node embedding can consider community structure or structure similarity
• DFS: Community structure
• BFS: Structure similarity
• Since real graphs have a combination of community abd structure similarity, we want to combine BFS or DFS style walk

​

Grover et al. 2016

Node2vec key steps

• Generate node neighborhoods

​

• Optimize an objective function that maximizes the probability of the neighborhoods

Node2vec: generating neighborhood

d_tx: Shortest path distance from t to x

distances wrt t

Node2vec: Objective function

Maximize the likelihood of neighborhoods

“Neighborhood” of u from sampling strategy S

Conditional independence assumption over individual source-neighbor pairs

Node2vec: Objective function

Likelihood of source-neighbor node pair

Node2vec: effect of p and q

Grover et al. 2016

p = 1

q = 0.5

p = 1

q = 2

Les Misérables character co-appearance network:77 nodes, 237 edges

Colors: clusters on learned embeddings

Experiments: Node classification

• Consider standard supervised learning task of node classification
• Compare to Spectral clustering, DeepWalk, LINE
• Use a one vs rest Logistic Regression classifier

Experiments: Link prediction

• Consider standard supervised learning task of link prediction
• Compare to Spectral clustering, DeepWalk, LINE
• Evaluate with AUC

Goals for today

• The case for learning representations in unsupervised problems for graphs

​

• Shallow, graph structure-based representations

​

• OhmNet: Application of node2vec for multi-tissue networks

OhmNet: Predicting multicellular function through�multi-layer tissue networks

• Motivation:
• How to predict the function of a protein in a tissue-specific manner?
• Can we use the embeddings for different tasks?
• Requires explicit modeling of tissues
• Extract rich feature representations of proteins in each tissue-specific network
• Use these rich feature representations to predict tissue-specific function of proteins

​

​

Zitnik, M. & Leskovec, J. Predicting multicellular function through multi-layer tissue networks. Bioinformatics 33, i190–i198 (2017).

​

OhmNet representation of multi-layered networks

Tissue

Feature encoding in OhmNet

OhmNet overview

• OhmNet framework has two parts

​

• Single network objective: embeddings of nodes with similar neighborhoods should be similar

​

• Hierarchical dependency: nodes in nearby layers in the hierarchy have similar embeddings

​

Encoding each network

Incorporating the hierarchy

OhmNet objective

• This has two parts

Per network objective

Hierarchical part

OhmNet Algorithm

Sample neighborhoods

Go over all leaf nodes in the tissue tree

OhmNet Algorithm

Learn the encodings

OhmNet evaluation dataset

• 107 tissues with tissue-specific networks from Greene 2015
• Unweighted PPI has 21,557 nodes and 342,353 interactions
• Tissue-specific
• An edge exists in tissue t if either both partners are co-expressed
• OR one partner is expressed in the tissue and the other partner is ubiquitous
• Gene function
• 584 tissue-specific cellular functions covering 48 tissues
• All functions for a tissue were assigned to the leaf corresponding to the tissue

OhmNet prediction tasks

• Predict tissue-specific function
• Multi-node classification

​

• Transfer learning
• Transfer information from one or more layers to a target layer in tissue hierarchy

​

• Data visualization

Predicting cellular function

Transfer learning task

• For each target tissue t, train a classifier using all tissue network embeddings other than t

​

​

• Predict class using trained classifier for t
• no training

Predicting function in a transfer learning manner

Degradation in performance is expected, but only graceful degradation

Visualizing tissue-specific networks

OhmNet was used only on the brainstem and brain networks and project the nodes in a 2D space

OhmNet key points

• Task independent approach to embed nodes of multiple related networks
• Can accurately predict function in the same or transfer learning mode
• Can be used to visualize hierarchically related networks

Conclusions

• Representation learning on networks finds data-driven encodings that can be input into standard ML methods
• (Shallow) node embeddings can be based on matrix factorization and random walks
• Deep embeddings have the potential to address limitations of shallow embeddings
• Better use of node attributes
• Fewer parameters
• Generalize to new nodes and graphs (inductive)
• OhmNet: node2vec encoding that also uses relationship across samples

References

• Zitnik, M. & Leskovec, J. Predicting multicellular function through multi-layer tissue networks. Bioinformatics 33, i190–i198 (2017).
• Hamilton, W. L., Ying, R. & Leskovec, J. Representation Learning on Graphs: Methods and Applications. arXiv:1709.05584 [cs] (2018).
• Nelson, W. et al. To Embed or Not: Network Embedding as a Paradigm in Computational Biology. Front Genet 10, 381 (2019).
• Grover, A. & Leskovec, J. node2vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2016).
• Check https://www.youtube.com/watch?v=3XTuhchTWd8&t=227s

​

​

​