Stanford CS224W: Machine Learning with Graphs | 2021 | Lecture 12.3 - Finding Frequent Subgraphs

For more information about Stanford’s Artificial Intelligence professional and graduate programs, visit: stanford.io/3Ex4Igv
Jure Leskovec
Computer Science, PhD
In this lecture, we discuss the techniques to mine frequent subgraphs. We will first give you an idea on the computational difficulty of the subgraph mining problems, as well as the standard problem setup for such problems. Then, we introduce SPMiner, a neural model to identify frequent motifs. The algorithm of SPMiner consists of the step of randomly selecting starting nodes, and growing the set to larger subgraphs. You'll see how SPMiner heuristically picks nodes in subsequent iterations, and the inspiring experimental results from it.
To follow along with the course schedule and syllabus, visit:
web.stanford.edu/class/cs224w/
#machinelearning #machinelearningcourse

[@maksimkazanskii4550]

May be I missed smth but it's not completely clear how to find k-frequent subgraphs with greeady approach. It is pretty trivial technique how to find one, but in order to find k we need smth more extravagant than a greedy approach. For example to create subtrees from the (max_depth-1) subgraph. But I am not sure it will be efficient.