Graph convolutional neural networks

Oct 6^th, 2022

BMI/CS 775 Computational Network Biology�Fall 2022

Anthony Gitter

https://compnetbiocourse.discovery.wisc.edu

Topics in this section

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

Goals for today

• Neural network definitions and appeal
• Fully connected neural networks
• Convolutional neural networks
• Graph convolutional neural networks
• Problem settings with graph convolutional neural networks
• Node or edge classification
• Graph classification
• Node, edge, or graph embedding
• Biological applications
• Protein-protein interaction interface prediction
• Essential gene prediction

Power of deep learning on graphs

• AlphaFold: a solution to a 50-year-old grand challenge in biology

​

• “A folded protein can be thought of as a “spatial graph”, where residues are the nodes and edges connect the residues in close proximity… AlphaFold, used at CASP14, we created an attention-based neural network system, trained end-to-end, that attempts to interpret the structure of this graph, while reasoning over the implicit graph that it’s building.”

Supervised graph prediction task

• Given:
• Graph structure G_i = (V_i , E_i )
• Optional features on the nodes V_i
• Optional features on the edges E_i
• Do:
• Predict a label y_i for the graph
• Can be discrete (classification) or continuous (regression)

​

• Goal:
• Use the node relationships to influence the predictions
• Avoid deciding how to represent a graph structure or graph-graph similarity in advance

​

One advantage of neural networks

• Many supervised learning problems require non-linear decision boundaries
• Example of explicit feature engineering

​

​

​

​

​

​

One advantage of neural networks

• Many supervised learning problems require non-linear decision boundaries
• Example of explicit feature engineering

​

​

​

​

​

​

• Neural networks can approximate these (and other) functions
• Do not specify kernels or feature transformations in advance
• Learn encoding from training data

How do neural networks learn feature transformations?

• Combine many simple non-linear transformations

Neuron

Actual neural network

How a perceptron works

Fire if weighted sum > 1

Weighted sum = 1*-1 + 0*-2 + 1*3 + 1*2 = 4

1

(fire)

Inputs

Weights

Learning perceptron weights (parameters)

?

w_y

We need to choose weights w_x and w_y

Inputs

Weighted sum = ?

Learning perceptron weights

?

3

Inputs

Weighted sum = ?

Random guess: w_x= -1 and w_y= 3

Learning perceptron weights

?

3

Inputs

Weighted sum = ?

Random guess: w_x= -1 and w_y= 3

Training data

Learning perceptron weights

?

3

Inputs

Random guess: w_x= -1 and w_y= 3

Training data

Weighted sum = 1*-1 + 1*3 = 2 (True)

Learning perceptron weights

?

1

Inputs

Training data

Weighted sum = ?

Update our guess: w_x= -1 and w_y= 1

Learning perceptron weights

?

1

Inputs

Training data

Update our guess: w_x= -1 and w_y= 1

Weighted sum = 1*-1 + 1*1 = 0 (False)

Learning perceptron weights

?

1

Inputs

Training data

Weighted sum = ?

Does it work for another example?

Learning perceptron weights

?

1

Inputs

Training data

Weighted sum = 9*-1 + 4*1 = -5 (False)

Does it work for another example?

Perceptron observations

• Random guessing is fine for initialization
• Need a way to formally update weights to fit training data
• Use gradient of objective function
• Not yet a non-linear classifier
• Add activation functions
• Combine many different perceptrons

Activation functions

• What makes the neuron “fire”?
• Step function

​

​

​

• Sigmoid function

​

​

​

• Rectified linear unit (ReLU)

Images from Wikipedia: Activation function

From perceptrons to fully connected neural networks

• Simple linear decision boundary
• Linear decision boundary fails for XOR
• XOR with one hidden layer
• Complex, non-linear patterns

​

• Try varying weights, hidden units, and layers
• What patterns can you learn with 0 hidden layers?
• 1 hidden layer?
• More?

From perceptrons to fully connected neural networks

• If we stack perceptrons, we get a fully connected neural network
• Has to learn weights independently for each input feature (e.g. node)
• Not using edges of input graph

Input graph

Hidden layers

(perceptrons)

Prediction

Some datasets have special structure

• 1D sequences

​

​

​

​

• 2D images

A 1 0 0 0 1 0 0 0 0 0

C 0 0 0 1 0 0 0 0 1 0

G 0 1 1 0 0 1 0 1 0 1

T 0 0 0 0 0 0 1 0 0 0

A G G C A G T G C G

AG pattern repeats

GC pattern repeats

Bowling ball pattern in different locations (image 1, 2, 3)

One hot encoding of DNA sequence

Some datasets have special structure

• 1D sequences

​

​

​

​

​

​

​

• Convolutional neural networks
• Share parameters instead of trying to recognize patterns independently in each position

A 1 0 0 0 1 0 0 0 0 0

C 0 0 0 1 0 0 0 0 1 0

G 0 1 1 0 0 1 0 1 0 1

T 0 0 0 0 0 0 1 0 0 0

A G G C A G T G C G

AG pattern repeats

GC pattern repeats

w w

w w

w w

w w

8 independent parameters

Adapting convolutions for graphs

Image from Wu et al. 2019 A Comprehensive Survey on Graph Neural Networks

2D images

Look for common patterns

in local regions

Graphs

Look for common patterns

node neighborhoods

Challenge for convolutions on graphs

2D images

Fixed number of pixels

Graphs

Graph size varies

Node degree varies

One solution is to share parameters for each neighbor

Graph convolution definitions

Basic graph convolutional neural network

Graph convolution example

Graph convolution example

Graph convolution example

Elementwise average

Graph convolution example

Graph convolution example

Apply ReLU

Interactive examples in Distill GNN articles by Sanchez-Lengeling et al. and Daigavane et al.

Multiple graph convolutional layers

Image from Gligorijevic et al. 2019 bioRxiv 786236

Stack K graph convolutional layers

What type of prediction to make?

Aggregation or readout layer

Can follow by multilayer perceptron (fully connected)

Image from Wu et al. 2019 A Comprehensive Survey on Graph Neural Networks

Top Hat question

Example of biological graph convolutional neural networks

• Many network algorithms require accurate protein-protein interaction networks
• Experimental networks are incomplete, many approaches to predict interactions

​

• Related problem is predicting which parts of interacting proteins directly interface
• Can frame protein-protein interface prediction as edge prediction
• Represent each protein as a graph
• Predict class label for a pair of residues

Protein Interface Prediction using Graph Convolutional Networks

Red: ligand

Blue: receptor

Yellow: interface

Image from Fout et al. NIPS 2017

Predict this: interacting residues

Protein Interface Prediction using Graph Convolutional Networks

Pair representations of residue x from graph 1 and residue y from graph 2

Image from Fout et al. NIPS 2017

Representing proteins as a graph

• For each residue, search within fixed radius in 3D space
• Or take k nearest residues
• Define contact map (adjacency matrix)

Image from Gligorijevic et al. 2019 bioRxiv 786236, reviewed by Fasoulis et al. 2021

Featurizing protein graphs

Image from Fout et al. NIPS 2017

Evaluating protein interface prediction

• Benchmark with Docking Benchmark Dataset
• Consider multiple graph neural networks
• Best model with no graph convolution: 0.812 AUC
• Best model with graph convolutions: 0.891 AUC
• 3 graph convolution layers better than 4

​

Predicting gene essentiality

• Yeast has approximately 6,000 genes
• Roughly 20% are essential, or required for growth
• Deletion strain is inviable

​

Gene 1

Gene 2

Predicting gene essentiality

• Relationship between yeast gene essentiality and centrality in protein interaction network

​

Image from Jeong et al. 2001 Nature

Red: lethal

Orange: slow-growth

Green: non-lethal

Yellow: unknown

Predicting gene essentiality

• Can we predict yeast gene essentiality?
• Node classification problem
• Graph structure: protein-protein interactions
• Node features: gene expression data, other phenotypes, etc.

​

• EPGAT: Gene Essentiality Prediction With Graph Attention Networks (Schapke et al. 2021)

​

Conclusions

• Graph convolutions generalize 1D sequence and 2D image convolutions
• Take advantage of parameter sharing and invariances
• Basic operation: get neighbors’ features, multiply by weight vector(s) to transform, aggregate, non-linear activation
• One framework adapts to multiple problem settings
• Unsupervised or supervised
• Node, edge, or graph tasks
• Unlike graph kernels customize (learn parameters) from training data

Resources

• 2021 lecture slides on extensions to graph neural networks
• Wu et al. 2019 A Comprehensive Survey on Graph Neural Networks
• Excellent slides by Jack Lanchantin
• PyTorch Geometric implementations of dozens of graph neural networks
• Stanford Network Analysis Project with tutorials, implementations, biological datasets
• DeepChem with biochemistry datasets and graph neural network implementations
• Deep Graph Library
• CS 540 Fall 2020 slides on neural networks
• Distill GNN articles by Sanchez-Lengeling et al. and Daigavane et al.
• Review Biological network analysis with deep learning

Kernels for graph classification

• A kernel k is a function that maps pairs of objects to a real-valued space
• It enables one to define very general similarity functions between pairs of objects
• Let denote a set of objects of a particular type
• Such as an entire graph!
• A kernel k is defined as

​

Slide from Prof. Sushmita Roy

Kernels for graph classification

• Given a kernel function k we can solve the graph classification task
• Many type of graph kernels
• Shortest path-based
• Random walk-based
• Graph featurization-based
• Kriege et al. 2019 A Survey on Graph Kernels
• Support vector machine and other approaches directly applicable after defining kernel
• Possible limitation: decide type of kernel in advance

​