Graph convolutional neural networks: extensions and limitations

Oct 3^rd, 2024

BMI/CS 775 Computational Network Biology�Fall 2024

Anthony Gitter

https://compnetbiocourse.discovery.wisc.edu

Topics in this section

• Graph neural networks
• Graph neural network extensions and limitations
• Graph transformers
• Generative graph models

​

Goals for today

• Graph neural network extensions
• Edge features
• Alternative ways to handle variable node degree
• Graph attention
• Pooling
• Limitations of graph neural networks
• More biological applications
• Protein function prediction
• Epigenomics
• Drug side effects
• Drug discovery

​

Basic graph convolutional neural network

• Assumptions made in graph convolution layer
• No edge features
• All neighbors should be treated in the same way (shared weight matrix)
• All neighbors are equally important
• Do not need to aggregate information until the end

Edge features in graph convolutions

• Recall protein graph had edge features
• Minor modification makes it easy to update in first graph convolution layer
• Unlike node features, harder to update in later layers

Image from Fout et al. NIPS 2017

Unique neighbor weights in graph convolutions

• Have been using the same weight vector for all neighbors
• Can generalize if we can sort neighbors
• In protein interface prediction, can sort by residue-residue distance

Protein interface prediction results

• More complex network architectures did not have a big impact

GraphSAGE: alternative approach for graphs with variable degree

GraphSAGE: alternative approach for graphs with variable degree

Image from Hamilton et al. NIPS 2017

Sampling naturally handles variable degree

Defined multiple aggregation strategies in addition to mean

Which neighbors are important

• Graph convolutional neural networks give each neighbor the same influence
• What if some neighbors are more important?
• How do we know which neighbors are important in advance?

​

• Attention is a deep learning approach to address this
• Originally developed for sequence models
• Key idea: learn which neighbors are important

Graph Attention Networks

5

1

3

2

4

All edges have equal importance

Calculating attention in graphs

Image from Veličković et al. ICLR 2018

Use a simple neural network to calculate attention

Calculating attention in graphs

Image from Veličković et al. ICLR 2018

Can have parallel kinds of attention (multiple heads): blue, green, purple

Concatenate or aggregate them

Calculating attention in graphs

Need to normalize attention over neighbors

Use softmax function

Before normalization

After normalization

Graph Attention Networks: putting it all together

Simplified notation from Zhang et al. in DGL docs

Transform current representation

Calculate edge attention as function of node representations

Normalize edge attentions

Use edge attentions in node updates

Concatenation

Top Hat question

Partial graph attention example

1

2

3

4

5

6

7

8

9

10

Examine partial graph attention calculations for nodes 1 and 10

Nodes 2 and 7 have same initial features

Partial graph attention example

1

2

3

4

5

6

7

8

9

10

Only showing some of the calculations

Partial graph attention example

1

2

3

4

5

6

7

8

9

10

Partial graph attention example

1

2

3

4

5

6

7

8

9

10

https://paperswithcode.com/method/leaky-relu

Partial graph attention example

1

2

3

4

5

6

7

8

9

10

Pooling

• In 1D or 2D convolutional neural networks, pooling is common
• Search for patterns in small regions, then aggregate, repeat

Image source

Initially recognize holes in the ball

Then recognize configurations of holes

…

…

…

…

…

Pooling

• Pooling is important in graphs as well but challenging
• No pre-defined grid structure
• Can make computation more efficient
• Could help generalize across graphs

​

• Consider how to learn the pooling
• Self-attention graph pooling
• Lee et al. 2019 arXiv:1904.08082

Self-attention graph pooling

Image from Lee et al. 2019 arXiv:1904.08082

Compute attention with graph convolution

Select top k fraction of the nodes to keep

Use attention mask to shrink the graph

Limitations of graph neural networks

• Empirical and theoretical studies of classic graph neural networks revealed limitations:
• Under-reach
• Over-smoothing
• Over-squashing
• Expressiveness

​

Limitations of graph neural networks: under-reach

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

Require k graph layers to share information k edges away

Cannot learn long distance relationships

i

Layer 1

Layer 2

Limitations of graph neural networks: over-smoothing

1

3

2

4

Input graph

1

2

3

4

Limitations of graph neural networks: over-squashing

Also known as bottlenecks

Image from Alon and Yahav ICLR 2021

Label green node from {A, B, C} based on number of neighbors

General graph

Limitations of graph neural networks: over-squashing

Images from Alon and Yahav ICLR 2021

Information from all leaves must be aggregated in top node’s representation

Test case: binary tree with depth r, predict label of root

Limitations of graph neural networks: expressiveness

Image from PubChem

Image from GraphGPS blog post

Decalin molecule

Molecular graph

Standard graph neural network representation

Ideal representation

Biological applications

• Initially popular in chemistry / biochemistry
• Gained traction in many other areas
• Biological network analysis with deep learning

​

• Key considerations:
• Unsupervised / supervised
• Node / edge / graph predictions
• What varies? Node features, graph structure, etc.

Predicting quantitative protein function

• Input: Wild type protein structure, amino acid sequence
• Output: Functional activity score
• Gelman et al. 2021 doi:10.1073/pnas.2104878118

​

Predicting quantitative protein function

• Importance of control experiments
• Does graph neural network performance change with alternative graphs?

​

​

​

​

​

​

• For these datasets, can often still get good performance with the control graphs
• Requires fully connected layer after the graph layers

​

Gelman et al. 2021 doi:10.1073/pnas.2104878118

Predicting protein function

• Input: Protein structure, residue (node) features
• Output: Gene Ontology labels
• Gligorijevic et al. 2021 Nature Communications

​

Predicting epigenetic state

• Input: DNA sequence, Hi-C contact maps
• Output: TF binding, histone modifications, accessibility
• Lanchantin and Qi 2020 Bioinformatics

​

Predicting polypharmacy side effects

• Input: 3 types of protein and drug interactions, node features
• Output: Types of side effects for drug-drug pair
• Zitnik et al. 2018 Bioinformatics

​

Predicting drug properties

• Input: Chemical structure
• Output: Chemical’s ability to inhibit a drug target
• Chen et al. 2018 Drug Discovery Today

​

Does this chemical bind an important protein domain and affect bioactivity?

Predicting drug properties

• IDG-DREAM Drug-Kinase Binding Prediction Challenge
• Predict binding affinity between 25-70 compounds and ~200 kinases
• One top performer used graph convolutional neural networks
• Park et al. 2019 DMIS_DK Submission
• Tested multiple graph architectures in ensemble
• Graph Attention Networks most important in ensemble but random forest also competitive
• 78 node features from RDKit: atom type, degree, bound Hs, valence, aromatic

Conclusions

• Graph convolutional networks can be applied to many of the other biological tasks in this course
• Can be advantages to coupling node representation with final prediction
• Very flexible formulation, can tweak almost anything
• Many hyperparameters, non-trivial to train
• Limitations in how information is shared across graph
• Critical to benchmark against simpler models

Recent GNN extensions

• Wang and Cho 2024 Non-convolutional Graph Neural Networks
• New approach to overcome some limitations of GNNs we won’t have time to discuss
• Finkelshtein 2024 Cooperative Graph Neural Networks
• GNN extension where nodes play a game and select among different actions during message passing

​