Traditional Graph Machine Learning
AI60007
Model of Traditional Graph ML
Graph or Node Level Feature Extraction
Machine Learning Algorithm
Prediction
Features in Traditional Graph ML
Traditional Graph ML Features
Node Level Features
Link Level Features
Graph Level Features
Node Level Prediction
Link Level Prediction
Graph Level Prediction
Node Level Features
Degree Centrality:
Eigenvector Centrality:
A node is important if it is linked to by other important nodes
Node Level Features
Eigenvector Centrality:
Matrix form:
Desired: centrality values to be positive
Choose eigenvector with all positive elements
Perron-Frobeneus Theorem: A real squared matrix with positive elements has a unique
largest eigenvalue and its corresponding eigenvector has all positive elements
Node Level Features
Eigenvector Centrality: How likely that a node is visited on a random walk of infinite length on the graph?
Node Level Features
1
2
3
4
5
Iteration 1
Node Level Features
1
2
3
4
5
Iteration 2
Iteration 3
Node Level Features
1
2
3
4
5
Iteration 4
Convergence!!!
Node Level Features
Katz Centrality:
Centrality of the neighbors and a small constant for the
central node
Matrix form:
Node Level Features
Katz Centrality:
Matrix form:
Node Level Features
Betweenness Centrality:
If there are many paths passing through a node, it is at an
important position of the graph
Node Level Features
Peruzzi and Guadagni
🡺 degree (3 v.s. 4)
🡺 eigenvector centralities (0.28 vs. 0.29)
Peruzzi family is in the
midst of a relatively tight-knit cluster of families, the Guadagni family occurs in a more star-like role
Clustering Coefficient
Node Level Features
Clustering Coefficient
Proportion of closed triangles in a node’s local
neighborhood
Node Level Features
Can we generalize it to any pattern other than triangle? Graphlets
Node Level Features
Motifs and Graphlets
Node Level Features
Graphlet Degree Vector (GDV): Count vector of graphlets rooted at a given node
Edge Level Features
Quantifies the extent to which a pair of nodes are related
Neighborhood Overlap
Edge Level Features
Sorensen Index:
Salton Index:
Jaccard Index:
Resource Allocation:
Resource Allocation:
Local Neighborhood Overlap
Edge Level Features
Global Neighborhood Overlap
Two nodes having no local neighborhood overlap may be members of the same community in the graph
Katz Index: Counts the no of paths of all lengths between a pair of nodes
Graph Level Features
Bag of Nodes
- Aggregate node level statistics
- Histogram of node degrees, centralities, clustering coeffs, etc.
- Aggregated statistics as representation of a graph
- Entirely based on local node information and ignores global info.
Graph Level Features
subgraph structures (graphlets)
difficult problem
Graphlet Kernel Statistics
Graph Level Features
Path-based Kernel