Representation Learning on Graphs

Oct 21^st, 2021

BMI 826-23 Computational Network Biology�Fall 2021

Anthony Gitter

https://compnetbiocourse.discovery.wisc.edu

Original slides created by Prof. Sushmita Roy

Topics in this section

• Representation learning on graphs
• Graph neural networks
• Generative graph models

Goals for today

• Overview of representation learning for graphs
• Introduce frameworks for learning node embeddings
• Discuss multi-tissue application

Representation learning of graphs

• How can we effectively represent graphs, subgraphs, nodes to machine learning algorithms?
• Important for many network analysis tasks
• Visualization, function prediction, link prediction, community detection
• Goal is to find a mapping that embeds nodes as points in a low-dimensional vector space R^d
• Today’s focus
• Unsupervised: graph structure, node features only
• Shallow: not using multi-layer neural networks

Hamilton, Ying, Leskovec, 2018

From graphs to embeddings

DeepWalk embedding of Zachary Karate Club social network

Representation learning of graphs

• Earlier work represented graphs with hand-engineered statistics to extract structural information
• Node degree
• Node attributes
• Path distance between nodes
• Shared neighbors between nodes
• Inflexible, non-adaptive features
• Representation learning treats this problem as machine learning task itself, a data-driven approach to learn embeddings that encode graph structure

Hamilton, Ying, Leskovec, 2018

Notation

Encoder-decoder framework of representation learning

Hamilton, Ying, Leskovec, 2018

Encoder-decoder framework

• A pairwise similarity function

​

• An encoder, ENC that generates node embeddings

​

• A decoder, DEC, which reconstructs pairwise node similarities

​

• A loss function L, which determines how the quality of the pairwise reconstructions is evaluated in order to learn the ENC function

​

​

​

Classes of node embeddings

• Shallow encoding

​

• v_i is one hot indicator indicating which column corresponds to node v_i
• Matrix factorization-based methods
• Random walk-based methods
• Autoencoder-based methods

​

• Deep encoding (next week)
• Multi-layer “deep” neural networks
• Graph neural networks

Matrix factorization-based representation

• Laplacian eigen maps

​

​

​

​

Matrix factorization-based representation

Random-walk based representation

• More recent methods are based on random walk statistics
• These measures are more flexible than matrix factorization
• DeepWalk
• node2vec

DeepWalk

Perozzi et al. 2014

node2vec

Grover et al. 2016

node2vec

Objective function

“Neighborhood” of u from sampler S

Conditional independence assumption

node2vec

Likelihood of source-neighborhood node pair

node2vec

Neighborhood autoencoder

• Encode the vector of similarities to all other nodes
• No longer learn independent embedding for each node
• Parameter sharing
• Autoencoder structure is fixed
• Cannot generalize to new nodes or across graphs (transductive)

A few applications

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

​

• Mashup (extra slides at end)
• Cho, H., Berger, B. & Peng, J. Compact Integration of Multi-Network Topology for Functional Analysis of Genes. Cell Systems 3, 540–548.e5 (2016).

​

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

• Motivation: How can we predict the function of a protein in a tissue-specific manner?
• 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

​

OhmNet representation of multi-layered networks

Tissue

Feature encoding in OhmNet

Encoding each network

Incorporating the hierarchy

OhmNet objective

• This has two parts

Per network objective

Hierarchical part

OhmNet Algorithm

Create the similarity function

OhmNet Algorithm

Learn the encodings

Dataset description

• 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 i 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

​

• Transfer learning

​

• Data visualization

Predicting cellular function

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

• 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 matrix factorization, random walk, or autoencoder-based
• Deep embeddings have the potential to address limitations of shallow embeddings
• Incorporate graph structure
• 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).

​

​

Mashup

• A computational approach to integrate data across multiple networks to address multiple tasks

​

​

​

Mashup

• How can we systematically integrate diverse types of networks (e.g. protein-protein, gene expression, genetic) to predict gene function?
• Existing approaches have tried to create a single network from all these diverse sources: might suffer loss in information
• Mashup: learn network specific “compact” feature representations

Mashup key steps

• Run a localized network diffusion process (e.g. random walk with restarts)
• Approximate each node’s diffusion distribution by a low-dimensional vector
• Use the learned features for different downstream tasks

Mashup overview

Mashup tasks

• Gene function prediction

​

• Ontology reconstruction

​

• Genetic interaction prediction

Mashup: function prediction

Mashup: genetic interaction prediction