Machine Learning with Graph (1): Why Graph?

---

Why is processing graphs hard?

• Network is complex (Arbitrary size and complex topological structure; no spatial locality like grids)
• No fixed node ordering or reference point
• Often dynamic and have a multi-modal feature

Feature Engineering such as annotation is not needed; Just learn method of a representation learning

---

Classic Graph ML Tasks

• Node classification: Predict a property of a node(Categorize online users/items)
• Link prediction: Predict whether there are missing links between two nodes(Knowledge graph completion)
• Graph classification: Categorize different graphs(Molecule property prediction)
• Clustering: Detect if nodes form a community(Social circle detection)
• Other tasks: Graph generation(Drug discovery), Graph Evolution(Physical Simulation)

1. Node-Level ML Application

Protein Folding: Computationally predict a protein’s 3D structure based solely on its amino acid sequence (AlphaFold)

AlphaFold
Key Idea: Spatial Graph
Node: Amino acids in a protein sequence
Edge: Proximity between amino acids (residues)
⇒ Final position of the molecules able to be predicted

 

2. Edge-Level ML Application

Recommender Systems(Users interact with items): Nodes as users and items, Edges as user-item interaction ⇒ Recommend items users might like

PinSage (Graph-based Recommender)
$QueryPin(z_{cake1}), Recommend1(z_{cake2}), Recommend1(z_{tee}) \\ \Rightarrow d(z_{cake1}, z_{cake2}) < d(z_{cake1}, z_{tee})$
Drug Side Effects (Biomedical Graph Link Prediction)
Many patient take multiple drugs to treat complex or co-existing diseases ⇒ Given pair of drugs predict adverse side effects

≫ Goal: Can we predict the missing edges?

 

3. Subgraph-Level ML Application

Traffic Prediction: Nodes as road segments, edges as connectivity between road segments

 

4. Graph-Level ML Application

Drug Discovery: Nodes as atoms, and edges as chemical bonds

 

5. Other

Molecule Generation / Optimization (You et al., Graph ConvolutionaI Policy Network for Goal-Directed Molecular Graph Generation, NeuriPS 2018)

---

Organizing lecture from Stanford CS224W: Machine Learning with Graph (Prof. Jure Leskovec, 2021)
Image Reference: https://snap.stanford.edu/class/cs224w-2021/