cs224w | Lecture 2. Traditional Methods for ML on Graphs

Graph-Level Features

Kernel Methods

• Graph Kernels: Measure similarity between graphs
• Goal: Design graph feature vector $\phi (G)$
• Key Idea: Bag of Words

Graphlet Kernels

• Key Idea: Count the number of different graphlets in a graph
• Don't have to be connected
• Don't have to be rooted
• Given two graphs, G and G', graphlet kernel is computed as
  $K(G,G')=\mathit {\bold{f}}_{G}^{T} \mathit{\bold{f}}_{G'}$

• Limitations: Counting graphlets is expensive!

Weisfeiler-Lehman Kernel

• Color Refinement: iterate color aggregation and obtain color count vectors
• Closely related to Graph Neural Networks
• Counting colors takes linear-time w.r.t. #(nodes)