Knowledge Graph Completion

Freebase - крупнейший граф знаний в истории до Google - закрылся в 2016 году имея 3 миллиарда фактов. И 95% возможных рёбер были пустыми. Не потому что факты неизвестны. Потому что люди физически не успевают вносить. KGC - это попытка научить граф достраивать себя самостоятельно.

• **Wikidata Link Suggestion** (2023): BERT-модель предсказывает пропущенные property-value пары для статей, снижая нагрузку на 11K редакторов
• **Google Product KG**: CompGCN-подобные методы связывают товары с категориями и атрибутами, которые поставщики не указали явно
• **OpenBioLink**: RotatE на биомедицинском KG предсказывает drug-target interactions - потенциальные мишени для лекарств без клинических испытаний
• **Microsoft Academic Graph**: автоматическое выявление связей автор-институция через rule mining - без перебора 250 млн публикаций вручную

Задача предсказания связей

Wikidata в 2023 году - 11 тысяч активных редакторов, 1.8 миллиарда утверждений. И при этом 85% потенциальных связей между сущностями отсутствуют. Freebase перед закрытием в 2016 году содержал 3 миллиарда фактов - и 95% возможных рёбер оставались пустыми. Не потому что никто не знал ответа. Просто никто не успел внести.

Это не проблема сбора данных. Это математическая реальность: граф знаний с N сущностями и R типами отношений потенциально имеет $N^2 \times R$ рёбер. Для Wikidata это ~100 триллионов пар. Рука человека не дотянется.

**Knowledge Graph Completion (KGC)** - автоматическое предсказание отсутствующих рёбер на основе существующей структуры графа. Формально: дан граф $\mathcal{G} = (\mathcal{E}, \mathcal{R}, \mathcal{T})$ из троек $(h, r, t)$ - нужно ответить, существует ли тройка $(h, r, ?)$ или $(?, r, t)$ и что стоит на месте `?`.

Google Knowledge Graph использует KGC для заполнения карточек в поиске: если граф знает что Илон Маск - CEO Tesla, а Tesla - компания в Остине - KGC может вывести что Маск связан с Остином. Microsoft Academic Graph применял это для автодополнения связей автор-институция. Amazon Product Graph предсказывает "также подходит к" между товарами.

Подходы делятся на три класса. **Трансляционные модели** (TransE, RotatE) - геометрия в пространстве эмбеддингов. **Rule mining** (AMIE) - автоматическое извлечение логических правил. **GNN-методы** (CompGCN, KGCN) - нейросети на структуре графа. Каждый класс находит разные паттерны.

Ключевая метрика - **Mean Reciprocal Rank (MRR)**: для каждого запроса модель ранжирует всех кандидатов, берётся обратный ранг правильного ответа, усредняется по всем запросам. MRR = 1 означает что правильный ответ всегда первый. Ещё используют **Hits@K** - доля случаев где правильный ответ попал в топ-K. На датасете FB15k-237 лучшие модели достигают MRR 0.35-0.48 и Hits@10 около 0.53-0.63.

TransE и RotatE: геометрия отношений

2013 год. Bordes et al. в NIPS публикуют TransE - модель с идеей обезоруживающей простотой. Если тройка $(h, r, t)$ истинна, то в пространстве эмбеддингов должно выполняться приближённое равенство: $\mathbf{h} + \mathbf{r} \approx \mathbf{t}$. Отношение - это вектор трансляции.

Та же идея, что word2vec для слов: "king - man + woman = queen" - только теперь для сущностей. "Einstein + bornIn = Ulm" в пространстве эмбеддингов должно давать вектор близкий к вектору Ульма. Модель обучается контрастивно: истинные тройки должны иметь высокий score, случайные - низкий.

TransE элегантен, но имеет фундаментальный изъян: отношение - это вектор трансляции, одинаковый для всех пар. Это работает для 1-to-1 отношений. Но "bornIn" - 1-to-many: у тысяч людей место рождения Москва. TransE пытается вытолкнуть все их эмбеддинги в одну точку. Москва = Пушкин = Толстой в пространстве? Нет.

RotatE (Sun et al., 2019) решает это элегантнее. Вместо трансляции в вещественном пространстве - **вращение в комплексном**. Отношение - это вращение $e^{i\theta_r}$ на каждой координате:

Операция Адамара $\circ$ (поэлементное умножение в $\mathbb{C}^d$) кодирует симметрию, антисимметрию и инверсию. "Spouse" - симметричное отношение: вращение на $\pi$ дважды = тождественное. "parentOf" - антисимметричное: вращение на угол без обратного. KGBERT (2022) достигает MRR 0.479 на FB15k-237 - против 0.279 у TransE.

**Паттерны отношений и их кодирование:** - **Симметрия** (A married_to B => B married_to A): RotatE кодирует как вращение на $\pi$ - **Антисимметрия** (A parentOf B => B NOT parentOf A): вращение без обратного - **Инверсия** (A bornIn City => City birthplaceOf A): $\theta_{r_1} = -\theta_{r_2}$ - **Композиция** (A parentOf B, B parentOf C => A grandparentOf C): сложение углов TransE не может кодировать симметрию (h + r = t и t + r = h означало бы r = 0). RotatE кодирует все четыре паттерна.

В продакшне embedding-подходы используются в Wikidata Query Service (link suggestion tool), в системах рекомендации знаний в Alexa и в Google's KELM (Knowledge-Enhanced Language Model). Размерность эмбеддингов обычно 200-1000; датасеты - FB15k-237 (14,541 сущностей, 237 отношений) и WN18RR (40,943 сущности, 11 отношений).

AMIE и GNN: правила и нейросети на графе

Embedding-модели предсказывают связи, но не объясняют почему. Выдала TransE что между X и Y есть отношение R - и что? Нельзя проверить. Нельзя доверять в медицине или праве. AMIE (Association Rule Mining under Incomplete Evidence) решает это иначе: ищет логические правила прямо в структуре графа.

Идея: если в графе часто встречается паттерн $\text{livesIn}(X, Y) \land \text{capitalOf}(Y, Z) \Rightarrow \text{nationality}(X, Z)$, то это правило. AMIE считает **поддержку** (сколько раз голова правила истинна) и **confidence** (доля случаев, когда условие истинно и вывод тоже).

AMIE - интерпретируемый подход. Каждое предсказание сопровождается правилом-объяснением. Ограничение: правила линейны (цепи троек), не улавливают сложные структурные паттерны. И работают только если паттерн уже встречался в графе.

CompGCN (Vashishth et al., 2020) объединяет лучшее из двух миров. Это Graph Neural Network, где агрегация сообщений учитывает типы отношений. Каждая сущность обновляет своё представление через соседей - с учётом того, через какое ребро они подключены.

Здесь $\phi$ - операция объединения эмбеддинга соседа с эмбеддингом ребра (сложение, умножение или конкатенация). $W_\lambda$ - матрица, разная для прямых, обратных и self-loop рёбер. Посчитав L слоёв такой агрегации, сущность видит свой L-hop контекст.

CompGCN на FB15k-237 достигает MRR 0.355 - выше чем TransE (0.279) и сопоставимо с RotatE (0.338), но при этом GNN ещё можно дообучать при добавлении новых узлов. Embedding-модели статичны: новая сущность требует переобучения. GNN - нет, достаточно нескольких шагов агрегации.

**Сравнение подходов KGC:** | Подход | MRR (FB15k-237) | Интерпретируемость | Инкрементальность | |---|---|---|---| | TransE | 0.279 | нет | нет | | RotatE | 0.338 | нет | нет | | AMIE (rules) | ~0.20 | да | частично | | CompGCN | 0.355 | нет | да | | KGBERT | 0.479 | частично | да | KGBERT - это fine-tuned BERT на текстовых описаниях сущностей и отношений. Самые высокие MRR - у моделей, сочетающих структурные эмбеддинги с языковым контекстом.

В реальных системах подходы комбинируются. Wikidata Mismatch Finder использует правила (AMIE-стиль) для выявления противоречий. Google's Product Knowledge Graph применяет GNN для связей товар-категория. OpenBioLink (медицинский KG) использует RotatE - потому что биологические отношения часто симметричны и имеют чёткую семантику.

Связанные темы

KGC стоит на пересечении теории графов, embedding-моделей и символического AI.

• Graph Neural Networks — CompGCN - GNN-подход к KGC с агрегацией по типам рёбер
• GraphRAG — Link prediction обогащает контекст в RAG-системах на графах
• Knowledge Graphs в AI Engineering — Практическое применение KGC в продуктовых системах
• Word Embeddings — TransE применяет ту же идею трансляции что word2vec

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

• **KGC-проблема**: крупнейшие графы знаний заполнены на 5-15% - KGC предсказывает пропущенные рёбра автоматически
• **TransE**: $\mathbf{h} + \mathbf{r} \approx \mathbf{t}$ - отношение как трансляция; элегантно, но ломается на симметричных и 1-to-many отношениях
• **RotatE**: отношение как вращение в $\mathbb{C}^d$; кодирует симметрию, антисимметрию, инверсию и композицию - MRR 0.338 vs 0.279 у TransE
• **AMIE**: rule mining с confidence и support - даёт интерпретируемые правила вроде livesIn + capitalOf => nationality
• **CompGCN**: GNN с типизированной агрегацией - инкрементален при добавлении новых сущностей, embedding-модели нет

Вопросы для размышления

• TransE ломается на симметричных отношениях, RotatE решает это вращением. Какие ещё паттерны отношений могут ломать геометрические подходы?
• AMIE даёт интерпретируемые правила, GNN - нет. В каких областях (медицина, право, финансы) это критично и почему?
• Если добавить в граф 10 миллионов новых сущностей без рёбер - что предскажут embedding-модели и что GNN-подходы?

Связанные уроки

• aie-41-knowledge-graphs — KG completion - ядро продуктовых KG-систем в AI Engineering
• aie-63-graphrag — GraphRAG использует link prediction для обогащения контекста
• ml-35-word-embeddings — TransE - это word2vec для рёбер графа: та же идея трансляции в пространстве эмбеддингов
• ml-31-transformers — CompGCN и GNN-методы используют те же механизмы агрегации что трансформеры - но на графах
• ds-16-graphs-intro — Базовое понимание графов необходимо для работы с KG embeddings
• ml-01