DSML Reading Club #3: efficient random-walk graph kernels

This week, Mikhail Shkorin will present graph embeddings through the paper “Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs”.

Current graph-embedding methods either lack theoretical grounding, as with GNNs, or have high computational complexity, as with kernel approaches.

The paper proposes a simple and scalable algorithm that compares graphs and their nodes efficiently through a linear approximation of random-walk kernels.

At the meeting, we will discuss:

• Why graph embeddings are needed
• How to create node embeddings in linear time
• How to move from node embeddings to graph embeddings on the fly without computing a huge adjacency matrix
• Graph transformers on point clouds in robotics
• Add to calendar: calendar.app.google/wci6yDfF8M68tHCv7
• Thursday, May 15, 11:00 Kazakhstan time
• Google Meet
• Host: Yelaman Abdullin