ML with Graphs

1.1 Why Graphs?

• Graphs are a general language for describing and analyzing entities with relations/interactions

• Main Question: How do we take advantage of relational structure for better prediction?

  • Comeplex domains have a rich relational structure, which can be represented as a relational graph
  • By explicitly modeling relationships we achieve better performance

• Modern deep learning toolbox is designed for simple sequences(text) & grids(image)

  • How can we develop neural networks that are much more broadly applicable?
    → Graphs are the new frontier of deep learning
    

1.2 Applications of GraphML

PapersWithCode - Graphs

• In many Graph Machine Learning, we can formulate different types of tasks:

  • At the level of individual nodes
    • The Protein Folding problem: Computationally predict a protein's 3D structure based solely on its amino acid sequence
    • DeepMind's AlphaFold
  • At the level of edges which is pairs of nodes
    • RecSys - Graph Neural Networks in Recommender System: A survey (2022)
  • At the level of sub-graphs of nodes
    • Traffic Prediction - Graph Neural Network for Traffic Forecasting: A Survey (2022)
  • At the level of entire graphs
    • Drug Discovery - A Deep Learning Approach to Antibiotic Discovery (2020)

• Classic GraphML Tasks

  • Node classification - Predict a property of a node
  • Link Prediction - Predict whether there are missing links b/t two nodes
  • Graph classification - Categorize different graphs
  • Graph Clustering - Detect if nodes form a community
  • Graph generation

1.3 Choice of Graph Representation

• How do you define a graph? (= How to build a graph?)

  • What are nodes?
  • What are edges?
  • Choice of the proper network representation of a given domain/problem determines our ability to use networks successfully

• Directed Graphs Vs. Un-directed Graphs

  • 

• Node degrees

  • 

• Bi-partite graph

  • 

• Representing graphs: Adjacency matrix

  • 
  • 
  • 
  • 

• Representing graphs: Edge list

  • 
  • This is a representation that is quite popular in deep learning frameworks because we can simply represent it as a two-dimensional matrix
  • The problem of this representation is that it is very hard to do any kind of graph manipulation or any kind of analysis of the graph because even computing a degree of a given node is non-trivial in this case

• Representing graphs: Adjacency list

  • 

• Node and Edge Attributes (Possible options)

  • 

• More Types of Graphs: Weighted Graphs Vs. Un-Weighted Graphs

  • 

• More Types of Graphs: Self-edges (self-loops) / Multi Graph

  • 

• Connectivity of Un-directed graphs

  • 
  • 

• Connectivity of Directed graphs

  • 
  •