Это вторая часть про графы: мы будем смотреть на граф как на пространство сигналов, изучать его спектр и динамику, а затем строить меры сходства и векторные представления для практических задач.

С помощью этих методов вы сможете:

• Анализировать глобальную структуру сетей — выявлять сообщества, оценивать связность и находить узкие места.
• Моделировать динамические процессы — понимать, как распространяется информация (или влияние) в социальных сетях, интернете или биологических системах.
• Представлять графы для ML — превращать сложные графовые структуры в векторы (эмбеддинги), понятные для классических алгоритмов, или сравнивать графы напрямую с помощью ядер.
• Понимать основу современных GNN — увидеть, как спектральный анализ и графовые фильтры лежат в основе графовых нейронных сетей.

Мы специально вынесли эту главу в конец, поскольку для комфортного чтения вам потребуются знания из глав по математическому анализу, линейной алгебре и теории вероятностей.

Эта глава состоит из двух параграфов:

• В первом поговорим о спектральных методах и диффузии на графах. Мы введём понятия графового лапласиана и его спектра, разберёмся, как его собственные значения и векторы описывают структуру графа. Изучим графовое Фурье-преобразование, диффузионные процессы (включая PageRank) и графовые фильтры — основу GCN.
• Второй будет посвящён ядрам и эмбеддингам графов. Мы рассмотрим методы сравнения графов (ядра) и способы их векторного представления (эмбеддинги, Node2Vec и Graph2Vec). Затем покажем, как эти представления используются для кластеризации, извлечения признаков для табличных моделей и быстрого поиска похожих объектов.

В итоге вы получите рабочий инструментарий: от анализа структуры графа и моделирования процессов до построения векторных представлений, кластеризации и быстрого поиска похожих объектов.

Давайте приступим!