Графы знаний
GNN на графах знаний
KG embeddings из предыдущего урока обучают векторы независимо для каждой тройки. Но в реальных графах знаний паттерны распределены по структуре: факт 'Пушкин - поэт' становится очевидным, если знать, что он написал поэмы и учился в Лицее. GNN учатся именно на такой структурной информации.
- **Microsoft GraphRAG:** GNN поверх KG для точных ответов на вопросы без hallucination
- **Биомедицина:** предсказание взаимодействий лекарств через R-GCN на графе белков/болезней
- **Рекомендательные системы:** PinSage (Pinterest) - GNN на графе пользователь-пин
R-GCN: отдельные веса для каждого типа отношений
Стандартный GCN (Graph Convolutional Network) агрегирует соседей через одну матрицу весов W. В знаниевом графе рёбра имеют типы: (Пушкин, написал, Онегин), (Пушкин, родился_в, Москва) - это разные отношения. **R-GCN** (Schlichtkrull et al., 2018) вводит отдельную матрицу W_r для каждого типа отношений.
**Проблема параметров:** при 500 типах отношений и d=200 - это 500 × 200 × 200 = 20 миллионов параметров только для одного слоя. R-GCN решает это через **basis decomposition**: W_r = Σ_b a_{rb} · V_b, где V_b - общие базисные матрицы, a_{rb} - скалярные коэффициенты для каждого отношения.
**R-GCN на FB15k-237:** entity classification task MRR 0.248. Преимущество над TransE: R-GCN использует n-hop структуру графа - не просто прямую связь h→t, но и общих соседей, пути через промежуточные сущности.
Зачем R-GCN использует basis decomposition для матриц W_r?
CompGCN: операторы композиции entity+relation
R-GCN агрегирует соседей через W_r, но не изменяет вектор отношения - он не обучается в контексте конкретных сущностей. **CompGCN** (Vashishth et al., 2020) явно включает вектор отношения в message: перед агрегацией entity h_u и relation r_k комбинируются через оператор композиции.
**Зачем три матрицы W_O, W_I, W_S?** Граф знаний направленный: (Пушкин, написал, Онегин) и (Онегин, написан, Пушкин) - разные триплеты. CompGCN обрабатывает incoming и outgoing рёбра с разными весами, и обратные рёбра через специальный вектор r_inv.
Чем CompGCN принципиально отличается от R-GCN в формировании message?
Message Passing Neural Networks: общий фреймворк
R-GCN, CompGCN, GraphSAGE, GAT - все это частные случаи **MPNN (Message Passing Neural Network)** фреймворка (Gilmer et al., 2017). Фреймворк задаёт единую схему: для каждого узла v на каждом слое - вычислить сообщения от соседей, агрегировать, обновить.
Число слоёв L MPNN определяет, информацию из какого радиуса видит каждый узел: после L слоёв узел v агрегирует информацию от всех узлов на расстоянии ≤ L рёбер. Для типичных задач KG completion достаточно 2-3 слоёв.
- **Downstream задачи:** entity classification (класс сущности), link prediction (предсказать r в (h,r,t)), KG completion
- **L=1:** только прямые соседи. L=2:** соседи соседей - типичный для KG
- **Over-smoothing:** при большом L все эмбеддинги сходятся к одному вектору - теряется различимость
После 3 слоёв MPNN узел v агрегирует информацию от узлов на расстоянии:
Стратегии агрегации: mean, sum, attention
AGG-функция - критический выбор: она определяет, как информация от нескольких соседей объединяется в один вектор. Разные стратегии дают разные inductive biases и производительность на разных задачах.
| Агрегация | Формула | Свойство | Лучше для |
|---|---|---|---|
| Mean | Σm_u / |N(v)| | Инвариантна к |N| | Однородные графы |
| Sum | Σm_u | Чувствительна к |N| | Структурные задачи |
| Max | max(m_u) | Ключевой признак | Аномалии, выбросы |
| Attention | Σα_{uv}·m_u | Взвешенные соседи | Гетерогенные KG |
**Теорема Xu et al. (2019):** GNN с sum aggregation так же выразительны, как тест Weisfeiler-Leman (WL) на изоморфизм графов - это теоретический максимум для message-passing GNN. Mean и max aggregation менее выразительны (не различают некоторые структуры).
Узел v имеет 10 соседей с одинаковыми эмбеддингами [1, 0, 0]. Sum aggregation вернёт [10, 0, 0], Mean - [1, 0, 0]. В каком случае Sum предпочтительнее?
GNN для знаниевых графов
- **R-GCN:** отдельная матрица W_r на тип отношений + basis decomposition для экономии параметров
- **CompGCN:** message = φ(entity, relation), оба обновляются; 3 оператора (subtract/multiply/ccorr)
- **MPNN:** единый фреймворк: Message → Aggregate → Update; охват L-hop за L слоёв
- **Aggregation:** sum максимально выразительна по WL-тесту; attention гибка для гетерогенных графов
Связанные темы
GNN на KG соединяет методы эмбеддингов с графовым обучением.
- KG Embeddings: TransE, RotatE, ComplEx — Операторы φ в CompGCN напрямую наследуют scoring functions предыдущего урока
- Graph Neural Networks: базовые концепции — R-GCN и CompGCN - специализация GCN для мультиреляционных графов
Вопросы для размышления
- При каком числе типов отношений basis decomposition в R-GCN перестаёт давать выигрыш в качестве и почему?
- Как проблема over-smoothing в глубоких GNN проявляется специфически для знаниевых графов с миллиардами сущностей?
- Почему attention aggregation полезна для гетерогенных KG, но может давать хуже mean на регулярных однородных графах?