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

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

Основные архитектуры и подходы для link prediction:

• Методы на основе признаков (Feature-based): используют характеристики узлов и их соседей, например, общих соседей, коэффициенты Джаккара.

• Графовые нейронные сети (Graph Neural Networks, GNN): обучают представления узлов с учетом их окружения. Популярные архитектуры:

  • Graph Convolutional Networks (GCN)
  • Graph Attention Networks (GAT)
  • GraphSAGE

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

• Модели на основе вероятностных графов: используют вероятностные модели для оценки связей.

Пример с GNN для link prediction: сначала обучают GNN для получения эмбеддингов узлов, затем вычисляют вероятность ребра между двумя узлами через функцию сходства (например, dot product) и применяют сигмоиду для получения вероятности.