Что хотят услышать интервьюеры:

Link prediction — это задача предсказания вероятности появления ребра между двумя вершинами графа. Обычно важно показать, что это не только классификация пары узлов, но и работа с их структурным окружением и эмбеддингами. Хороший ответ должен упомянуть базовые подходы, графовые нейросети и способы scoring для пары узлов.

Определение:

Link prediction — это задача из графового ML, где по уже известной структуре графа нужно оценить, будет ли связь между двумя вершинами, либо насколько она вероятна.
Такая задача используется, когда граф неполный, а связи можно восстановить или предсказать по топологии, атрибутам узлов и их окружению. На практике это часто формулируют как бинарную классификацию пары узлов или ранжирование кандидатов по вероятности ребра.

Пример использования:

Например, в социальной сети нужно предсказать, кто с кем может стать другом в будущем.

# Упрощённая схема link prediction
# 1. Получаем эмбеддинги узлов из GNN
# 2. Для пары узлов считаем score
# 3. Превращаем score в вероятность связи

import torch
import torch.nn as nn

class LinkPredictor(nn.Module):
    def __init__(self, in_dim):
        super().__init__()
        self.scorer = nn.Sequential(
            nn.Linear(in_dim * 2, 64),
            nn.ReLU(),
            nn.Linear(64, 1)
        )

    def forward(self, z_u, z_v):
        pair = torch.cat([z_u, z_v], dim=-1)
        score = self.scorer(pair)
        return torch.sigmoid(score)

# z_u и z_v — эмбеддинги двух узлов после GNN

Здесь GNN сначала строит представления узлов, а затем отдельная голова оценивает, насколько вероятна связь между ними.

Пояснение кода:

z_u и z_v — это эмбеддинги двух вершин, полученные из графовой модели или другого энкодера.
torch.cat([z_u, z_v], dim=-1) объединяет признаки пары в один вектор.
self.scorer — простая MLP, которая учится выдавать score для пары узлов.
torch.sigmoid(score) переводит score в вероятность от 0 до 1.
На практике вместо простого concat могут использовать dot product, cosine similarity, bilinear-слой или более сложный decoder.

Архитектурно link prediction обычно строится как encoder + decoder:

encoder извлекает эмбеддинги узлов;
decoder считает вероятность ребра для пары эмбеддингов.

Часто используют такие архитектуры:

Методы на эмбеддингах без GNN: node2vec, DeepWalk, matrix factorization.
GNN + MLP decoder: GCN, GraphSAGE, GAT, GIN как энкодер.
Bilinear / dot-product decoder: простые и быстрые декодеры.
Siamese / pairwise architectures: две башни для узлов с последующим сравнением.
Вариационные графовые автоэнкодеры: например, VGAE для восстановления ребер.
Heterogeneous / relational GNN: R-GCN, HAN и другие, если граф разнородный.

Ключевые моменты:

Link prediction предсказывает наличие или вероятность ребра между двумя узлами.
Базовая схема почти всегда: encoder для узлов + decoder для пары.
Для декодера часто используют dot product, bilinear scoring или MLP.
GNN-архитектуры применимы, потому что они учитывают локальную структуру графа и соседей.
Важный практический момент — отрицательные примеры: нужно сэмплировать пары без ребра.
Метрики зависят от постановки: часто используют ROC-AUC, AP, Hits@K, MRR.

Что такое link prediction и какие архитектуры используют?