Machine Learning on graphs

  • Machine learning model

  • Generally, is a vector
  • Most of machine learning methods are defined for vectors

How to connect graphs to machine learning models ?
What can we do with graphs ?

Machine Learning Tasks on graphs

  • Node-level
  • Graph-level
  • Edge-level
  • Graph Generation

Graph Level

center

Node Level

center

Inductive vs Transductive

  • Inductive Tasks : Predict the label of a node given the graph
  • Transductive Tasks : Predict the label of a node given the graph and the labels of the other nodes

center

Link Prediction

center

Community Detection

center

Graph Generation

center

Why learning on graphs is difficult ?

Problems with ML on Graphs

Graph space is not an Euclidean space

Variable number of nodes

  • No fixed/limit number of nodes
  • How to deal with a variable number of nodes/neighbours ?

Permutation (equi/in)variance

  • No predefined order of nodes
  • No order on neighbours ( images)

Permutation Invariance

center fit

Permutation Equivariance

center fit

Graphs versus Images

Images

  • Constant number of neighbours
  • Fixed position of neighbours
  • We want shift invariance

Graphs

  • Variable number of neighbours
  • No predefined ordering of neighbours
  • Permutation (equi/in)variance

How to connect graphs with Machine Learning ?

Classic Methods

center

Representation Learning on Graphs

center

Classic embedding (node2vec, old methods, kernels (wl + treelet(slides asi 5)) ) node and graph embedding. Calcul de descripteurs noeuds et graphes Cours 2 et 3 de Leskovec Cours 2 : feature engineering, node centrality, graphlets, graph kernel, Cours 3 : node embedding, random walk -> deepwalk, node2vec. Graph embedding. path kernel WL-kernel, treelet kernel