Link Prediction — Предсказание связей

Задача «появится ли ребро между вершинами»: рекомендации друзей и товаров, достройка графов знаний.

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

Простые эвристики (общие соседи, Adamic-Adar) — сильный бейзлайн.
Отрицательные примеры нужно сэмплировать осознанно: случайные пары слишком просты.
Валидация только по времени: обучаемся на прошлом состоянии графа, проверяемся на новых рёбрах.

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

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

Эвристики как бейзлайн

Три формулы, которые трудно обыграть.

Common Neighbors = ∣ N (u) \cap N (v) ∣, Adamic-Adar = w \in N (u) \cap N (v) \sum \frac{1}{lo g ∣ N ( w ) ∣}

Обозначения

$w$ веса модели — то, что подбирается при обучении
$n$ число объектов в выборке
$\sum$ суммирование по всем перечисленным элементам
$lo g$ логарифм: превращает произведения в суммы и сжимает масштаб

Adamic-Adar понижает вес общих соседей-хабов: знакомство через популярный аккаунт значит меньше, чем через редкого общего знакомого. На многих задачах эта формула уступает GNN лишь на несколько процентов.

Корректная валидация

Где здесь легко получить утечку.

Разбиение только по времени: обучаемся на графе до момента T, предсказываем рёбра после.
Рёбра из валидации нужно удалить из графа при обучении — иначе модель видит ответ.
Отрицательные примеры должны быть правдоподобными: случайная пара из миллиона вершин — слишком лёгкий негатив.
Метрики: AUC вводит в заблуждение при огромном числе несуществующих рёбер, смотрите Hits@k и MRR.

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

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

Graph Basics85%

Основы графов · Графы и сети

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

Centrality85%

Центральности · Графы и сети

Меры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.

PageRank85%

PageRank · Графы и сети

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

Community Detection85%

Поиск сообществ · Графы и сети

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

Graph Embeddings85%

Графовые эмбеддинги · Графы и сети

Векторные представления вершин, в которых близость отражает связанность в графе.

Graph Neural Networks85%

Графовые нейросети · Графы и сети

Нейросети, работающие прямо на структуре графа: представление вершины обновляется по представлениям соседей.

Message Passing85%

Передача сообщений · Графы и сети

Единая схема, к которой сводятся почти все архитектуры GNN: собрать сообщения от соседей, агрегировать, обновить состояние.

Knowledge Graphs85%

Графы знаний · Графы и сети

Факты в виде троек «субъект — предикат — объект». Структурированная память, которую всё чаще подключают к языковым моделям.

Network Motifs85%

Мотивы и триады · Графы и сети

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

Clustering85%

Кластеризация · Обучение без учителя

Разбиение объектов на группы похожих без заранее известных меток.

Eigenvector85%

Собственный вектор · Математический справочник

Направление, сохраняющееся при линейном преобразовании с точностью до масштаба.