Deep Representation Learning for Unsupervised Learning on Graphs

Nov 2^nd, 2023

BMI/CS 775 Computational Network Biology�Fall 2023

Sushmita Roy

https://compnetbiocourse.discovery.wisc.edu

Goals for today

• Motivation for deep representation learning
• Deep graph representation learning
• Autoencoder
• Graph AutoEncoder and Graph Variational AutoEncoder

​

​

Overview of algorithms for unsupervised representation learning

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

​

Limitations of shallow methods

• Unable to use node features/attributes (easily)

​

• Are inherently transductive
• All nodes must be seen during the training phase/embedding phase
• Therefore, cannot be used in an inductive setting
• No general function that could make a prediction on a new test node

​

Unsupervised representation learning on graphs

task: what we want to reconstruct back

Embedding graphs with node attributes

Learn embedding

x₁

x₄

x₃

x₂

x₇

x₅

x₆

Goals for today

• Motivation for deep representation learning
• Deep graph representation learning
• Autoencoder
• Graph AutoEncoder and Graph Variational AutoEncoder

​

​

Autoencoder

• A dimensionality reduction framework which can be used for various downstream tasks e.g. visualization, clustering, denoising etc.
• Comprises of an
• “encoder” that takes the input and projects it into a (typically) low dimensional space
• “decoder” that takes the low dimensional projection and puts into the original high dimensional space

​

Autoencoder

From Antonio Longa’s tutorial: https://github.com/AntonioLonga/PytorchGeometricTutorial/tree/main

Autoencoder

From Antonio Longa’s tutorial: https://github.com/AntonioLonga/PytorchGeometricTutorial/tree/main

Autoencoder

encoder

decoder

Input

Output

Adapted from Ava Amini slides; see https://www.youtube.com/watch?v=3G5hWM6jqPk

• To train an autoencoder we need to minimize a reconstruction loss.
• Mean squared error is commonly used as the loss function

Autoencoder vs Variational Autoencoder

https://towardsdatascience.com/tutorial-on-variational-graph-auto-encoders-da9333281129

Variational Autoencoder

Adapted from Ava Amini slides; see https://www.youtube.com/watch?v=3G5hWM6jqPk

encoder

decoder

Goals for today

• Motivation for deep representation learning
• Deep graph representation learning
• Autoencoder
• Graph AutoEncoder and Graph Variational AutoEncoder

​

​

Notation

Graph AutoEncoder (GAE)

encoder

decoder

logistic, sigmoid

Encoder:

Decoder:

A: Adjacency matrix

X: nXF features

Variational Graph Autoencoder (VGAE)

encoder

decoder

Encoder for the VGAE

a two layer GCN

Decoder for the VGAE

Evaluation of GAE and VGAE

• Experiments done for link prediction for several datasets
• Models trained on incomplete data where some edges were hidden/removed
• Assessed via AUC, and Average Precision (AP)

​

Evaluation of GAE and VGAE

SC: Spectral clustering

DW: DeepWalk

GAE*, VGAE*: Variants with no features

VGAE’s embedding can reveal clustering structure

Latent space of unsupervised VGAE model trained on Cora citation network dataset. Grey lines denote citation links. Colors denote document class (not provided during training).

​

Overview of GNN methods for clustering

Su, X. et al. A Comprehensive Survey on Community Detection with Deep Learning. IEEE Trans. Neural Netw. Learning Syst. 1–21 (2022) doi:10.1109/TNNLS.2021.3137396.

Overview of deep methods for graph clustering

• Methods can be grouped into two broad categories
• First generation of methods
• Use graph structure only and do node embedding
• DNR, DGNR, GraphEncoder
• Second generation of methods
• Use graph structure and node attributes and do node embedding
• Independent of cluster information: MGAE, SDGN
• Incorporate cluster structure: Senet, SGCN

​

The general idea of methods for graphs with node attributes

3

4

5

6

7

1

2

Learn embedding

x₁

x₄

x₃

x₂

x₇

x₅

x₆

kmeans clustering

node attributes

Note 1: Most methods aim to do this in an unsupervised manner because we assume we don’t have labels.

Note 2: The node embedding could be further influenced by the “clustering” structure

Does deep node embedding help for biological network module detection?

Song Z, Baur B and Roy S. Benchmarking graph representation learning algorithms for detecting modules in molecular networks [version 1; peer review: 1 approved, 1 approved with reservations]. F1000Research 2023, 12:941 (https://doi.org/10.12688/f1000research.134526.1)

References

• Graph autoencoders from https://github.com/AntonioLonga/PytorchGeometricTutorial/tree/main
• Variational autoencoders and graph variational autoencoders https://towardsdatascience.com/tutorial-on-variational-graph-auto-encoders-da9333281129

​

​