Knowledge Graphs на собеседовании

Senior-инженер пришёл на финал собеседования в LinkedIn. Вопрос: «Спроектируй Knowledge Graph для миллиарда профилей и сотен миллиардов связей between them». Слабый кандидат начнёт с того, что Knowledge Graph - это (subject, predicate, object). Сильный сразу спросит: каков RPS на чтение? Сколько hops запрашивает типовой query? Что критичнее - freshness или consistency? Эти уточняющие вопросы и есть демонстрация инженерного мышления - то самое, ради чего FAANG нанимает principal engineers за полмиллиона долларов в год.

• **Facebook TAO** - распределённая graph DB обслуживает 1 миллиард активных пользователей, 200 миллиардов рёбер; именно эта архитектура - объект изучения на System Design собеседованиях
• **Google Knowledge Graph** - 500+ миллиардов фактов о людях, местах и объектах; питает rich answers в поиске
• **Microsoft Satori** - граф для Bing и Office 365; пример production применения semantic web технологий

Моделирование онтологии

Классический вопрос с собеседования в Amazon: «Спроектируй граф знаний для product catalog с миллиардом товаров». Слабый ответ - сразу нарисовать (Product)-[hasCategory]->(Category) и закончить. Сильный кандидат сначала уточняет: какие сущности кроме товаров (бренды, продавцы, отзывы, варианты)? Какие отношения нужны для поисковых сценариев? Как обрабатываются полиморфные сущности (например, «iPhone 15» - это и Product, и Model, и Brand)? Только потом - схема, и она получается на двух уровнях: онтология (Product, Category, Brand) и instances (конкретные товары).

Ключевые решения моделирования: RDF (triples с глобальными URIs) или property graph (узлы и рёбра со свойствами)? RDF лучше для semantic web с шарингом данных между организациями, property graph - для production-систем с интенсивными query workloads. Большинство FAANG-внедрений (Microsoft Satori, LinkedIn Knowledge Graph) используют property graph, потому что Cypher/Gremlin синтаксически удобнее SPARQL для типовых запросов.

Query patterns: Cypher, SPARQL, Gremlin

Следующий вопрос: «Как найти все товары, купленные пользователями, которые также купили текущий товар?» - классический collaborative filtering через граф. Слабый ответ - SQL-подобный JOIN из четырёх таблиц. Сильный - короткий Cypher: `MATCH (p:Product {id: $pid})<-[:BOUGHT]-(u:User)-[:BOUGHT]->(rec:Product) RETURN rec, count(u) AS strength ORDER BY strength DESC LIMIT 10`. Это - читаемо, оптимизатор использует индексы по типам рёбер, и масштабируется лучше JOIN при глубине 3+.

Что важно знать: переменная глубина пути - `MATCH (a)-[:KNOWS*1..3]->(b)` ищет в радиусе 1-3 хопов. Это - убийца производительности на dense узлах (пользователь с тысячами связей). Решение - ограничение через WHERE и эвристики, например брать только top-K самых сильных рёбер. Pattern matching в графах - NP-hard в общем случае; на собеседовании важно показать понимание сложности.

Embeddings и graph ML вопросы

Вопрос: «Как использовать knowledge graph для рекомендаций холодному пользователю?». Слабый ответ - просто запросом по графу. Сильный - комбинация: graph embeddings (TransE, ComplEx, RotatE) кодируют структуру графа в плотные векторы, потом задача рекомендации сводится к поиску ближайших соседей в embedding-пространстве. Для нового пользователя без истории строится embedding на основе известных атрибутов (страна, демография) и графовых соседей этих атрибутов.

Главные семейства методов: TransE моделирует тройку (head, relation, tail) как h + r ~ t в евклидовом пространстве - простой и быстрый, но не работает на симметричных отношениях. ComplEx использует комплексные числа и эффективно ловит асимметрию. GNN-подходы (R-GCN, GraphSAGE) учитывают локальное соседство при построении эмбеддинга. На собеседовании важно показать понимание trade-offs: TransE масштабируется на миллиарды triples, GNN - на сотни миллионов из-за стоимости message passing.

System Design: KG на масштабе

Финальный вопрос: «Спроектируй knowledge graph для социальной сети с миллиардом узлов и сотнями миллиардов рёбер». Хороший ответ строится так: (1) выбор хранилища - Neo4j Enterprise или собственное на RocksDB/HBase; (2) sharding - по vertex-cut (hash узла) или edge-cut (граф разрезается так, чтобы минимизировать межшардовые рёбра); (3) репликация и failover; (4) query routing - где живёт планировщик запросов и как он избегает cross-shard JOIN; (5) caching горячих узлов на edge.

Production-решения: Facebook TAO - собственная распределённая графовая БД с миллиардами узлов, оптимизирована под чтение (10000:1 read/write ratio). LinkedIn Knowledge Graph - построен на гибриде RocksDB + Espresso. Microsoft Satori - кастомное хранилище под триплетную модель с шардингом по subject. Все они вынуждены жертвовать ACID-гарантиями ради масштаба: eventual consistency с конфликтным разрешением через CRDT или vector clocks.

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

• **Моделирование** - это не «нарисовать узлы и рёбра», а решить sparse/dense, versioning, polymorphism, inferred edges; стандарт FAANG-уровня
• **Query languages** - Cypher для production property graphs, SPARQL для semantic web, Gremlin для императивных API; выбор зависит от workload
• **Embeddings (TransE, ComplEx, RotatE, GNN)** - закрывают пробелы query languages: cold-start, similarity search, approximate reasoning
• **Sharding и масштабирование** - vertex-cut для простоты, replication горячих узлов, async для celebrity-write проблемы; компромиссы вместо идеального решения

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

Возврат к мотивации: вопросы FAANG по knowledge graphs синтезируют весь курс. Связь с предыдущими уроками:

• Graph Neural Networks — GNN-подходы (R-GCN, GraphSAGE) - основа современных embedding-методов, обсуждаемых на собеседовании
• Knowledge Graph Embeddings — TransE, ComplEx и RotatE - классические модели для query expansion и рекомендаций
• Query Languages — Cypher, SPARQL, Gremlin - инструменты, которые требуют выбирать осознанно под конкретный workload

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

• Когда стоит использовать knowledge graph вместо обычной реляционной БД, и какие сигналы указывают на необходимость такого перехода?
• Если interviewer сказал «у нас стандартный triple store, но queries медленные», какие гипотезы о причинах стоит проверить в первую очередь?
• Возврат к мотивации: на 45-минутном интервью невозможно спроектировать реальный production-граф. Что именно тогда оценивает интервьюер, и как кандидат может это продемонстрировать?

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

• kg-13 — Scale KG - база для system design вопросов
• kg-07 — KG Embeddings - обязательная тема interview
• kg-09 — SPARQL/Cypher - практические вопросы запросов
• kg-10 — QA over KG - ключевая задача на собеседованиях
• ir-14 — IR и KG interview имеют общий system design формат
• aie-63-graphrag — GraphRAG - пересечение KG и LLM, топ вопрос 2025
• ml-01-intro