Перейти к содержанию

Прогресс графовых нейросетей (GNN) 2025

~6 минут чтения

Предварительно: Реализация внимания с нуля | Vision-трансформеры

Главный инсайт 2025 года: трансформер -- это GNN на полносвязном графе, где self-attention = message passing между всеми парами токенов. Трансформеры «победили» не из-за превосходства архитектуры, а из-за hardware lottery -- GPU оптимизированы для dense matrix multiplication, а не для sparse graph operations. Параллельно ADMP-GNN показал, что adaptive depth (разная глубина для разных узлов) устраняет главное ограничение GNN -- over-smoothing, где после 5-6 слоёв все node embeddings сходятся к одному вектору.

Ключевые источники

Transformers = GNN (Инсайт 2025)

  1. Transformers are Graph Neural Networks — Chaitanya K. Joshi, Jun 2025
  2. Инсайт: Transformers = GNN on fully connected graphs
  3. Self-attention = message passing on complete graph
  4. Positional encodings = structure hints
  5. Hardware lottery: Dense matrix ops > sparse message passing

Adaptive Depth

  1. ADMP-GNN: Adaptive Depth Message Passing GNN — Abbahaddou et al., Sep 2025
  2. Проблема: Fixed depth для всех nodes inefficient
  3. Решение: Dynamically adjust message passing depth per node
  4. Results: Performance improvements over baseline GNNs

Ключевые идеи

Transformers are GNNs

Математическая связь:

\[ \text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V \]

В терминах GNN: - \(QK^T\) — edge weights между всеми парами nodes - \(\text{softmax}(\cdot)\) — normalized edge weights - \(V\) — node features

Message Passing view:

\[ h_i^{(l+1)} = \sum_{j \in \mathcal{V}} \alpha_{ij} h_j^{(l)} \]

где \(\alpha_{ij}\) — attention weight между nodes \(i\) и \(j\).

Difference: | Aspect | GNN | Transformer | |--------|-----|-------------| | Graph structure | Sparse (adjacency matrix) | Dense (fully connected) | | Message passing | Neighbors only | All tokens | | Hardware | Sparse ops (slow) | Dense matmul (fast) | | Position | Graph topology | Positional encoding |

Hardware Lottery:

"Transformers are GNNs currently winning the hardware lottery"

Почему: - GPUs оптимизированы для dense matrix multiplication - Sparse operations плохо parallelize - Transformer attention = один big matmul

ADMP-GNN: Adaptive Depth

Insight: Different nodes need different depths

\[ d_i = f(h_i, \text{node characteristics}) \]

где \(d_i\) — depth для node \(i\).

Implementation: 1. Learn depth predictor per node 2. Early stopping для converged nodes 3. More iterations для complex nodes

Benefits: - Reduced computation (некоторым nodes нужно меньше шагов) - Better performance (adaptive vs fixed)

Формулы и математика

Standard GNN Message Passing

\[ h_i^{(l+1)} = \phi\left(h_i^{(l)}, \bigoplus_{j \in \mathcal{N}(i)} \psi(h_i^{(l)}, h_j^{(l)}, e_{ij})\right) \]

где: - \(\mathcal{N}(i)\) — neighbors of node \(i\) - \(\bigoplus\) — aggregation function (sum, mean, max) - \(\phi, \psi\) — learnable functions

Graph Attention Network (GAT)

\[ \alpha_{ij} = \frac{\exp(\text{LeakyReLU}(a^T [Wh_i \| Wh_j]))}{\sum_{k \in \mathcal{N}(i)} \exp(\text{LeakyReLU}(a^T [Wh_i \| Wh_k]))} \]
\[ h_i' = \sigma\left(\sum_{j \in \mathcal{N}(i)} \alpha_{ij} Wh_j\right) \]

Transformer Self-Attention (as GNN)

\[ \text{Attention}(Q, K, V)_i = \sum_j \alpha_{ij} V_j \]

где \(\alpha_{ij} = \text{softmax}(Q_i K_j^T / \sqrt{d_k})\).

Аналогия: - \(\alpha_{ij}\) — edge weights (learned, not fixed) - \(\mathcal{N}(i) = \text{all tokens}\) — fully connected

Связанные работы

Практические применения

Где GNN лучше трансформеров

Задача Почему GNN
Свойства молекул Явная структура связей
Социальные сети Sparse connections
Рекомендации User-item граф
Knowledge graphs Отношения между сущностями

Где трансформеры лучше

Задача Почему трансформер
NLP Последовательная структура слабо выражена
Vision Grid-структура не важна
Код Семантические связи важнее синтаксических

Типичные заблуждения

Заблуждение: GNN устарели -- трансформеры решают все задачи на графах

Трансформеры -- это GNN на полносвязном графе. Для данных с явной sparse-структурой (молекулы, социальные сети, knowledge graphs) GNN эффективнее: вместо O(N^2) attention по всем парам, message passing O(|E|) работает только по рёбрам. На графе с 1M узлов и 10M рёбер GNN обрабатывает 10M пар, трансформер -- 10^12.

Заблуждение: Больше слоёв GNN = лучше результат

Over-smoothing: после 5-6 слоёв message passing все node embeddings сходятся к одному вектору, теряя различимость. ADMP-GNN решает это через adaptive depth -- каждый узел получает столько слоёв, сколько ему нужно. Простые узлы (мало соседей) останавливаются рано, сложные (хабы) получают больше итераций.

Заблуждение: GAT и Transformer attention -- одно и то же

GAT использует однослойный attention с LeakyReLU по соседям (\(\alpha_{ij}\) через \(a^T[Wh_i \| Wh_j]\)), тогда как Transformer -- scaled dot-product attention (\(QK^T/\sqrt{d_k}\)) по ВСЕМ токенам. GAT явно использует топологию графа (adjacency), Transformer -- нет (полносвязный граф + positional encoding).

Вопросы для собеседования

Покажите математически, что Transformer self-attention = message passing на полносвязном графе.

❌ «Оба используют attention, поэтому похожи» -- нет формального доказательства.

✅ Attention: \(h_i^{(l+1)} = \sum_j \alpha_{ij} V_j\) где \(\alpha_{ij} = \text{softmax}(Q_i K_j^T / \sqrt{d_k})\). Это ровно GNN message passing \(h_i^{(l+1)} = \sum_{j \in \mathcal{N}(i)} \alpha_{ij} h_j^{(l)}\) с двумя отличиями: (1) \(\mathcal{N}(i) = \mathcal{V}\) (все узлы -- полносвязный граф), (2) edge weights \(\alpha_{ij}\) вычисляются через QK-проекции вместо topology-aware механизма. Positional encoding компенсирует потерю структурной информации.

Что такое hardware lottery и почему она объясняет доминирование трансформеров?

❌ «Трансформеры просто лучшая архитектура» -- упрощение.

✅ GPU оптимизированы для dense matrix multiplication (GEMM). Transformer attention -- один большой матричный multiply, идеально ложится на GPU. GNN message passing требует sparse operations (gather/scatter по adjacency matrix), которые плохо параллелизуются на текущем hardware. При появлении sparse-efficient accelerators (graph-specific hardware) GNN могут получить «ренессанс».

Как ADMP-GNN решает проблему over-smoothing?

❌ «Просто ограничивает количество слоёв» -- примитивное решение.

✅ ADMP-GNN обучает depth predictor \(d_i = f(h_i, \text{node characteristics})\) для каждого узла. Узлы с low-degree или уже converged embeddings получают early stopping (меньше шагов message passing). Узлы-хабы с complex neighbourhood получают больше итераций. Это adaptive vs fixed depth, аналогично MoE где разные входы получают разное количество compute.

Самопроверка

  1. Формальное доказательство: Запишите формулу self-attention и GNN message passing. Покажите, что при \(\mathcal{N}(i) = \mathcal{V}\) (все узлы) они эквивалентны. Что играет роль adjacency matrix в трансформере?

  2. Вычислительное сравнение: Граф социальной сети: 1M узлов, 10M рёбер. Посчитайте: сколько пар обработает GNN (message passing по рёбрам) vs трансформер (full attention). На сколько порядков разница?

  3. Over-smoothing эксперимент: GNN с 3 слоями даёт 85% accuracy на node classification. С 8 слоями -- 60%. Объясните, почему больше слоёв ухудшает результат. Предложите 3 решения (кроме ADMP-GNN).

Открытые направления

  • Temporal GNN: графы, меняющиеся во времени (финансовые транзакции, эпидемии)
  • Heterogeneous GNN: разные типы узлов и рёбер (knowledge graphs)
  • Graph Transformers: sparse attention patterns, гибриды GNN + Transformer
  • Масштабирование: обучение GNN на графах >1B узлов (neighbor sampling, mini-batch)
  • GNN + MoE: STEM-GNN (2026) -- message passing аналогичен expert routing

See Also

Источники

  1. Chaitanya K. Joshi -- "Transformers are Graph Neural Networks" (arXiv:2506.22084, Jun 2025)
  2. Abbahaddou et al. -- "ADMP-GNN: Adaptive Depth Message Passing GNN" (arXiv:2509.01170, Sep 2025)