Скачать или смотреть Mikhail Shkorin - Computing General Random Walk Graph Kernels [DSML Reading Club #3]

Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs

Текущие методы построения графовых эмбеддингов страдают от отсутствия теоретической обоснованности (GNN) или высокой вычислительной сложности (kernel-подходы)

Статья предлагает простой и масштабируемый алгоритм, который обеспечивает эффективное сравнение графов и их узлов через линейную аппроксимацию random walk kernels

Paper: https://arxiv.org/pdf/2410.10368
Спикер: https://www.dsml.kz/users/Mihey
Хост: https://www.dsml.kz/users/Yela

Таймкоды
[01:35] - Представлено решение: новый метод выборки, снижающий вычислительную сложность ядер случайных блужданий с кубического до линейного времени.

[10:27] - Описание метода "Graph Feature (GF)", который использует "следы" от случайных блуждающих для эффективной оценки сходства графов.

[14:08] - Обсуждение влияния нового метода: более быстрая обработка, повышение точности и возможность анализа графов большего размера.

[15:00] - Упоминание улучшенной классификации графов и узлов как одного из потенциальных применений.

[18:27] - Обозначены такие потенциальные применения, как создание векторных баз данных для графов и интеграция с моделями-трансформерами.