Graph Basics

Вершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.

Ключевые тезисы

Плотный граф удобно хранить матрицей, разреженный — списком смежности; выбор влияет на всё остальное.
Обходы в ширину и глубину дают компоненты связности, расстояния и циклы.
Двудольные графы описывают взаимодействия «пользователь — товар» и лежат в основе рекомендаций.

Подробный разбор

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Способы хранения графа

Выбор структуры определяет, какие операции будут быстрыми.

Структура	Память	Быстро	Медленно
Матрица смежности	$O (n^{2})$	проверка ребра	обход соседей разреженного графа
Список смежности	$O (n + m)$	обход соседей	проверка конкретного ребра
Список рёбер	$O (m)$	потоковая обработка	любые локальные запросы
CSR	$O (n + m)$	векторизованные операции	изменение структуры

На практике

Реальные графы почти всегда разрежены: у миллиона вершин обычно десятки миллионов рёбер, а не $1 0^{12}$ . Поэтому матрицу смежности материализуют редко.

Графовые признаки для табличных моделей

Самый быстрый способ получить пользу от графа.

Степень вершины, число треугольников, коэффициент кластеризации.
Размер компоненты связности и расстояние до известных «плохих» вершин.
PageRank и персонализированный PageRank относительно множества меток.
Агрегаты по соседям: средний возраст аккаунта соседей, доля заблокированных.

На практике

Эти признаки считаются один раз и подаются в бустинг. На практике такой подход часто обыгрывает графовую нейросеть — при несопоставимо меньшей сложности.

Связанные темы

Машинное обучение на графах

Ключевые тезисы

Подробный разбор

Способы хранения графа

Графовые признаки для табличных моделей

Связанные темы

Centrality85%

PageRank85%

Community Detection85%

Graph Embeddings85%

Graph Neural Networks85%

Message Passing85%

Link Prediction85%

Knowledge Graphs85%

Network Motifs85%

Clustering85%

Eigenvector85%