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

GNN — это обучаемые модели, которые сами учат, как агрегировать информацию из соседей и как использовать признаки узлов/ребер для решения задачи. Классические алгоритмы на графах обычно имеют фиксированное правило распространения информации и решают более узкие задачи. Отличие в том, что GNN оптимизируются под конкретный датасет и целевую метрику, а PageRank или label propagation — это заранее заданные процедуры.

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

GNN (Graph Neural Networks) — это семейство нейросетевых моделей для графов, где представление вершины строится через обмен сообщениями с соседями и последующее обучение параметров на данных. В отличие от классических алгоритмов, GNN обычно используют признаки узлов, ребер и иногда глобальный контекст, а также могут обучаться для классификации, регрессии, ранжирования и предсказания связей.

Классические алгоритмы на графах, такие как PageRank и label propagation, работают по фиксированной математической схеме:

PageRank оценивает “важность” узла через структуру ссылок;
label propagation распространяет метки по соседям до стабилизации или по заданному числу итераций.

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

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

Например, в задаче предсказания мошенничества в платежной сети:

PageRank может выделить узлы с высокой связностью или влиянием;
label propagation может распространить известные метки “fraud / non-fraud” на соседей;
GNN может использовать признаки транзакций, типы связей, время и топологию графа, чтобы обучиться находить сложные паттерны мошенничества.

# Упрощенная схема: GNN учится предсказывать метку узла по его соседям и признакам
# x — признаки узлов, edge_index — список ребер, y — истинные метки

import torch
import torch.nn as nn
import torch.nn.functional as F

class SimpleGNN(nn.Module):
    def __init__(self, in_dim, hidden_dim, out_dim):
        super().__init__()
        self.lin1 = nn.Linear(in_dim, hidden_dim)
        self.lin2 = nn.Linear(hidden_dim, out_dim)

    def aggregate(self, x, edge_index):
        # Простейшая агрегация: среднее по соседям
        row, col = edge_index
        agg = torch.zeros_like(x)
        agg.index_add_(0, row, x[col])
        deg = torch.bincount(row, minlength=x.size(0)).clamp(min=1).unsqueeze(1)
        return agg / deg

    def forward(self, x, edge_index):
        h = self.aggregate(x, edge_index)
        h = F.relu(self.lin1(h))
        h = self.aggregate(h, edge_index)
        return self.lin2(h)

# На практике такие модели обучаются end-to-end по loss функции

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

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

Код не требуется для классических алгоритмов, но логика их работы такая:

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

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

GNN — обучаемые модели, классические алгоритмы — фиксированные процедуры.
GNN используют признаки и оптимизируются под конкретную задачу, а PageRank/label propagation решают узкие структурные задачи.
GNN могут учитывать сложные зависимости и разные типы данных, если это заложено в архитектуре и обучении.
Классические алгоритмы обычно проще, интерпретируемее и дешевле вычислительно.
GNN могут переобучаться и страдать от over-smoothing/over-squashing на больших глубинах.
PageRank и label propagation полезны как базовые методы, эвристики или компоненты более сложных систем, но они не заменяют обучаемую модель там, где нужен task-specific inference.

Чем GNN отличаются от классических алгоритмов на графах (PageRank, label propagation)?