Что нового в Graph ML?

Базы данных нейронных графов

Новая веха в управлении графическими данными

Мы представляем концепцию баз данных нейронных графов как следующий шаг в развитии баз данных графов. Разработанный для больших неполных графов и оперативного вывода об отсутствующих ребрах с использованием обучения представлению графа, нейронный анализ поддерживает высокую выразительность и поддерживает сложные логические запросы, аналогичные стандартным языкам запросов графов.

Этот пост был написан совместно с Hongyu Ren, Michael Cochez и Zhaocheng Zhu на основе нашей последней статьи Рассуждения на нейронных графах: ответы на сложные логические запросы и графические базы данных. Вы также можете подписаться на me, Hongyu, Michael и Zhaocheng в Twitter. Посетите наш сайт проекта для получения дополнительных материалов.

Схема:

  1. Базы данных нейронных графов: что и почему?
  2. Схема NGDB
  3. Хранение нейронных графов
  4. Нейронный механизм запросов
  5. Обоснование нейронных графов для механизмов запросов
  6. Открытые вызовы для NGDB
  7. Узнать больше

Базы данных нейронных графов: что и почему?

🍨Ванильные графовые базы данных практически везде благодаря постоянно растущему количеству графов в производстве, гибким графовым моделям данных и выразительным языкам запросов. Классические базы данных символьных графов быстры и круты при одном важном допущении:

Полнота. Механизмы запросов предполагают, что графы в классических БД графов завершены.

В предположении полноты мы можем создавать индексы, хранить графики в различных форматах, оптимизированных для чтения/записи, и ожидать, что БД вернет то, что есть.

Но на практике это предположение не часто выполняется (мы бы сказали, не слишком часто). Если мы посмотрим на некоторые выдающиеся графы знаний (ЗЗ): в Freebase 93,8% людей не имеют места рождения и 78,5% не имеют национальности, около 68% людей не имеют никакой профессии, а в Викиданных, о 50% художников не имеют даты рождения, и только 0,4% известных зданий имеют информацию о высоте. И это для крупнейшего KG, открыто курируемого сотнями энтузиастов. Конечно, 100 миллионов узлов и 1 миллиард операторов — это не самый большой график в отрасли, поэтому вы можете себе представить степень его неполноты.

Ясно, что для объяснения неполноты помимо «что есть?» мы должны также задать вопрос «чего не хватает?» (или "что там может быть?"). Давайте посмотрим на пример:

Здесь, учитывая неполный граф (ребра (Turing Award, win, Bengio) и (Deep Learning, field, LeCun) отсутствуют) и запрос «В каких университетах работают лауреаты премии Тьюринга в области глубокого обучения?» (выраженный в логической форме или в какой-либо язык, например SPARQL), база данных символического графа вернет только один ответ UofT, достижимый путем обхода графа. Мы называем такие ответы простыми ответами или существующими ответами. С учетом отсутствующих ребер мы восстановим еще два ответа UdeM и NYU (жесткие ответы или предполагаемые ответы).

Как вывести недостающие ребра?

  • В классических БД у нас нет большого выбора. Базы данных на основе RDF имеют некоторую формальную семантику и могут поддерживаться огромными онтологиями OWL, но, в зависимости от размера графа и сложности вывода, для завершения вывода в режимах следствия SPARQL может потребоваться бесконечное количество времени. Базы данных графов Labeled Property Graph (LPG) вообще не имеют встроенных средств для вывода отсутствующих ребер.
  • Благодаря достижениям в машинном обучении графов мы часто можем выполнять прогнозирование ссылок в скрытом (вложенном) пространстве за линейное время! Затем мы можем расширить этот механизм для выполнения сложных запросов, подобных базе данных, прямо в пространстве встраивания.

Базы данных Neural Graph сочетают в себе преимущества традиционных баз данных графов с современным машинным обучением графов.

То есть принципы БД, такие как (1) графы как первоклассные граждане, (2) эффективное хранилище и (3) единый интерфейс запросов, теперь поддерживаются методами Graph ML, такими как (1) геометрические представления, (2) устойчивость к шумные входные данные, (3) крупномасштабная предварительная подготовка и точная настройка, чтобы преодолеть разрыв неполноты и обеспечить возможность рассуждений и выводов на нейронных графах.

В целом принципы проектирования NGDB следующие:

  • Предположение о неполноте данных — в базовых данных может отсутствовать информация на уровне узлов, ссылок и графов, которую мы хотели бы вывести и использовать при ответах на запросы;
  • Индуктивность и возможность обновления. Подобно традиционным базам данных, которые допускают обновления и мгновенные запросы, алгоритмы обучения представлению для построения латентных графов должны быть индуктивными и обобщать невидимые данные (новые объекты и отношения во время вывода) в нулевой точке. -шаговый (или малократный) способ предотвращения дорогостоящего переобучения (например, встраивания неглубоких узлов);
  • Выразительность — способность скрытых представлений кодировать логические и семантические отношения в данных, подобных ЛЖ (или его фрагментам), и использовать их при ответах на запросы. На практике набор поддерживаемых логических операторов для нейронных рассуждений должен быть близок или эквивалентен стандартным языкам графовых баз данных, таким как SPARQL или Cypher;
  • Мультимодальность помимо графов знаний – любые графически-структурированные данные, которые могут храниться в виде узла или записи в классических базах данных (состоят, например, из изображений, текстов, молекулярных графов или последовательностей с временными метками) и могут быть наполненный векторным представлением, является действительным источником для хранилища нейронных графов и механизма нейронных запросов.

Ключевые методы реализации принципов NGDB:

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

На самом деле, отвечая на запросы в скрытом пространстве (и не жертвуя производительностью обхода), мы можем вообще отказаться от символических индексов базы данных.

Схема NGDB

Прежде чем погрузиться в NGDB, давайте взглянем на нейронные базы данных в целом — оказывается, они существуют уже некоторое время, и вы могли это заметить. Многие системы машинного обучения уже работают в этой парадигме, когда данные кодируются в параметры модели, а запросы эквивалентны прямому проходу, который может выводить новое представление или прогноз для последующей задачи.

Нейронные базы данных: обзор

Каково текущее состояние нейронных баз данных? Каковы различия между его видами и что особенного в NGDB?

  1. Векторные базы данных относятся к семейству систем, ориентированных на хранение, которые обычно строятся на основе библиотек приблизительных ближайших соседей (ANN), таких как Faiss или ScaNN (или настраиваемые решения), для ответа на запросы на основе расстояния с использованием максимального внутреннего -Поиск продукта (MIPS), L1, L2 или другие расстояния. Будучи независимыми от кодировщика (то есть любой кодировщик, выдающий векторные представления, может быть источником, таким как ResNet или BERT), векторные базы данных работают быстро, но им не хватает возможностей ответа на сложные запросы.
  2. С недавним появлением крупномасштабных предварительно обученных моделей — или базовых моделей — мы стали свидетелями их огромного успеха в задачах обработки естественного языка и компьютерного зрения. Мы утверждаем, что такие базовые модели также являются ярким примером нейронных баз данных. Там модуль хранения может быть представлен непосредственно с параметрами модели или передан внешнему индексу, часто используемому в моделях, дополненных поиском, поскольку закодировать все мировые знания даже в миллиарды параметров модели сложно. Модуль запроса выполняет контекстное обучение либо путем заполнения пробелов в моделях кодировщика (стиль BERT или T5), либо с помощью подсказок в моделях только для декодера (стиль GPT), которые могут охватывать несколько модальностей, например , обучаемые токены для приложений машинного зрения или даже вызов внешних инструментов.
  3. Базы данных естественного языка (NLDB), представленные Торном и др., моделируют атомарные элементы как текстовые факты, закодированные в вектор с помощью предварительно обученной языковой модели (LM). Запросы к NLDB отправляются как высказывания на естественном языке, которые кодируются в векторы, а обработка запросов использует подход retriever-reader.

Базы данных нейронных графов — не новый термин. Многие подходы к машинному обучению графов пытались комбинировать встраивания графов с индексами базы данных, возможно, RDF2Vec и LPG2Vec — одни из наиболее ярких примеров того, как вложения можно встраивать в существующие графические базы данных и запуск поверх символических индексов.

Напротив, мы утверждаем, что NGDB могут работать без символьных индексов прямо в скрытом пространстве. Как мы покажем ниже, существуют алгоритмы машинного обучения, которые могут имитировать точное поведение, подобное обходу ребер, в пространстве встраивания, чтобы получить «что там», а также выполнять нейронные рассуждения, чтобы ответить «чего не хватает». ».

Базы данных нейронных графов: архитектура

На более высоком уровне NGDB содержит два основных компонента: Neural Graph Storage и Neural Query Engine. Конвейер ответа на запрос начинается с запроса, отправленного каким-либо приложением или нижестоящей задачей уже в структурированном формате (полученном, например, с помощью семантического разбора, если исходный запрос на естественном языке, для преобразования его в структурированный формат).

Сначала запрос поступает в Neural Query Engine и, в частности, в модуль Планировщика запросов. Задача планировщика запросов состоит в том, чтобы получить эффективный граф вычислений атомарных операций (проекций и логических операций) с учетом сложности запроса, задач прогнозирования и базового хранилища данных, например возможного разделения графа.

Полученный план затем отправляется Исполнителю запросов, который кодирует запрос в скрытом пространстве, выполняет атомарные операции над базовым графом и его скрытыми представлениями и объединяет результаты атомарных операций в окончательный ответ. набор. Выполнение выполняется через модуль Поиск, который взаимодействует с Хранилищем нейронных графов.

Запоминающий слой состоит из

1️⃣ Graph Store для хранения многореляционной матрицы смежности в экономном пространстве и времени (например, в различных разреженных форматах, таких как COO и CSR);

2️⃣ Хранилище функций для хранения мультимодальных функций на уровне узла и ребра, связанных с базовым графом.

3️⃣ Embedding Store, который использует модуль Encoder для создания графических представлений в скрытом пространстве на основе базовой смежности и связанных функций.

Модуль Retrieval запрашивает закодированные представления графа, чтобы построить распределение потенциальных ответов на атомарные операции.

Хранение нейронных графиков

В традиционных графовых БД дизайн хранилища часто зависит от парадигмы графового моделирования.

Двумя наиболее популярными парадигмами являются графы структуры описания ресурсов (RDF) и графы помеченных свойств (LPG). Однако мы утверждаем, что новая RDF-звезда (и сопровождающая ее SPARQL-звезда) объединит эти две сливающиеся логическую выразительность RDF-графов с атрибутивной природой LPG. Многие существующие KG уже следуют парадигме RDF-star (-подобной), такой как гиперреляционные KG и Модель операторов Викиданных.

Если мы хотим представить парадигму графового моделирования магистральных сетей в ближайшие годы, мы выберем RDF-star.

В хранилище нейронных графов как входной граф, так и его векторные представления являются источниками истины. Для ответа на запросы в скрытом пространстве нам нужно:

  • Кодировщик запросов
  • Графический кодировщик
  • Механизм поиска для сопоставления представления запроса с представлением графа

Процесс кодирования (встраивания) графа можно рассматривать как этап сжатия, но семантическое и структурное сходство сущностей/отношений сохраняется. Расстояние между сущностями/отношениями в пространстве вложений должно положительно коррелировать с семантическим/структурным сходством. Существует множество вариантов архитектуры кодировщика, и мы рекомендуем придерживаться индуктивных вариантов, чтобы придерживаться принципов проектирования NGDB. В нашей недавней работе NeurIPS 2022 мы представили две такие индуктивные модели.

Кодирование запроса обычно совпадает с кодированием графа природы, так что оба они будут в одном и том же пространстве. Когда у нас есть скрытые представления, включается модуль поиска, чтобы извлечь соответствующие ответы.

Процесс поиска можно рассматривать как поиск ближайшего соседа входного вектора в пространстве вложений, и он имеет 3 прямых преимущества:

  1. Оценки достоверности для каждого извлеченного элемента — благодаря предопределенной функции расстояния в пространстве встраивания.
  2. Различные определения скрытого пространства и функции расстояния — для разных графов, например, древовидные графы легче работать в гиперболических пространствах.
  3. Эффективность и масштабируемость — поиск масштабируется до очень больших графов с миллиардами узлов и ребер.

Нейронная система запросов

В традиционных БД типичный механизм запросов выполняет три основные операции. (1) Разбор запроса для проверки правильности синтаксиса (часто дополняется более глубоким семантическим анализом терминов запроса); (2) планирование запроса и оптимизация для получения эффективного плана запроса (обычно это дерево реляционных операторов), который минимизирует вычислительные затраты; (3) Выполнение запроса, которое сканирует хранилище и обрабатывает промежуточные результаты в соответствии с планом запроса.

Довольно просто распространить эти операции на NGDB.

1️⃣ Синтаксический анализ запроса может быть выполнен с помощью семантического анализа в формате структурированного запроса. Мы намеренно оставляем дискуссию о языке запросов для NGDB для будущих работ и бурных публичных дискуссий 😉

2️⃣ Планировщик запросов выводит эффективный план запроса атомарных операций (проекции и логические операторы), максимизируя полноту (должны быть возвращены все ответы по существующим ребрам) и вывод (отсутствующие ребра прогнозируются на лету) с учетом сложности запроса и лежащего в основе графа.

3️⃣ Как только план запроса завершен, исполнитель запросов кодирует запрос (или его части) в скрытое пространство, взаимодействует с хранилищем графов и его модулем извлечения и объединяет промежуточные результаты в окончательный набор ответов. Существует два общих механизма выполнения запросов:

  • Атомарный, напоминающий традиционные БД, когда план запроса выполняется последовательно путем кодирования атомарных шаблонов, извлечения их ответов и выполнения логических операторов в качестве промежуточных шагов;
  • Глобальный, когда весь граф запроса кодируется и выполняется в скрытом пространстве за один шаг.

Основная проблема при выполнении нейронных запросов заключается в сопоставлении выразительности запросов с символическими языками, такими как SPARQL или Cypher — пока нейронные методы могут выполнять запросы, близкие к выразительности логики первого порядка, но мы находимся на полпути к символическим языкам.

Таксономия рассуждений нейронных графов для механизмов запросов

Литература о нейронных методах для ответов на сложные логические запросы (также известная как встраивание запросов) пополняется с 2018 года, а основополагающая работа NeurIPS Гамильтона и др. по встраиванию запросов в графы (ГКО). GQE смог ответить на конъюнктивные запросы с пересечениями и предсказать недостающие ссылки на лету.

GQE можно рассматривать как первый взгляд на механизмы нейронных запросов для NGDB.

GQE запустил целую подобласть машинного обучения графов, за которой последовали некоторые известные примеры, такие как Query2Box (ICLR 2020) и Непрерывная декомпозиция запросов (ICLR 2021). Мы приложили большие усилия, чтобы разделить все эти работы (около 50) по трем основным направлениям:

⚛️ Графики — какова основная структура, на основе которой мы отвечаем на запросы;
🛠️ Моделирование — как мы отвечаем на запросы и какие индуктивные предубеждения используются;
🗣️ Запросы — на что мы отвечаем, какова структура запросов и каковы ожидаемые ответы.

⚛️ Говоря о графиках, мы далее разбиваем их на модальность (классические графы только для троек, гиперреляционные графы, гиперграфы и т. д.), область рассуждения (дискретные объекты или включение непрерывных выходных данных) и Семантика (как нейронные кодировщики фиксируют отношения более высокого порядка, такие как онтологии OWL).

🛠️ В разделе Моделирование мы следуем парадигме кодировщик-процессор-декодер, классифицируя индуктивные смещения существующих моделей, например трансдуктивные или индуктивные кодировщики с нейронными или нейросимволическими процессорами.

🗣️ В разделе Запросы мы стремимся сопоставить набор запросов, на которые можно ответить с помощью нейронных методов, с набором языков запросов с символическими графами. Мы говорим об операторах запросов (выходящих за рамки стандартных И/Или/Не), Шаблонах запросов (от цепочечных запросов до групп DAG и циклических шаблонов) и проецируемых Переменные (ваша любимая реляционная алгебра).

Открытые вызовы для NGDB

Анализируя таксономию, мы обнаруживаем, что на данный момент универсального решения нет, например, большинство процессоров могут работать только в дискретном режиме с древовидными запросами. Но это также означает, что есть много возможностей для будущей работы — возможно, вашего вклада!

Точнее, вот основные задачи NGDB на ближайшие годы.

По ветви График:

  • Модальность: поддержка большего количества модальностей графов: от классических графов, состоящих только из трех элементов, до гиперреляционных графов, гиперграфов и мультимодальных источников, объединяющих графы, тексты, изображения и многое другое.
  • Область рассуждений: поддержка логических рассуждений и ответов нейронных сетей на временные и непрерывные (текстовые и числовые) данные — литералы составляют основную часть графиков, а также релевантные запросы на литералы.
  • Основная семантика: поддержка сложных аксиом и формальной семантики, которые кодируют отношения более высокого порядка между (латентными) классами сущностей и их иерархиями, \например, позволяя нейронным рассуждениям над логикой описания и фрагментами OWL.

В ветке Моделирование:

  • Кодировщик: индуктивные кодировщики, поддерживающие невидимую связь во время вывода — это ключ к (1) обновляемости нейронных баз данных без необходимости переобучения; (2) включение стратегии pretrain-finetune, обобщающей ответы на запросы к пользовательским графикам с пользовательской реляционной схемой.
  • Процессор: сети процессоров Express, способные эффективно и результативно выполнять сложные операторы запросов, аналогичные операторам SPARQL и Cypher. Повышение эффективности выборки нейронных процессоров имеет решающее значение для компромисса время обучения и качество — сокращение времени обучения при сохранении высокого качества прогнозирования.
  • Декодер. Пока что все декодеры, отвечающие на нейронные запросы, работают исключительно с дискретными узлами. Расширение диапазона ответов до непрерывных выходных данных имеет решающее значение для ответов на реальные запросы.
  • Сложность: поскольку основным вычислительным узким местом процессорных сетей является размерность пространства встраивания (для чисто нейронных моделей) и/или количество узлов (для нейросимволических), новые эффективные алгоритмы для нейронных логических операторов а методы извлечения являются ключом к масштабированию NGDB до миллиардов узлов и триллионов ребер.

В разделе Запросы:

  • Операторы: Нейрализация более сложных операторов запросов, соответствующих выразительности декларативных языков запросов графов, например, поддержка Kleene plus и star, путей к свойствам, фильтров.
  • Шаблоны: ответы на более сложные шаблоны, выходящие за рамки древовидных запросов. Сюда входят DAG и циклические графы.
  • Спроецированные переменные: разрешение проецировать больше, чем конечный объект конечного узла, то есть позволяет возвращать промежуточные переменные, отношения и несколько переменных, организованных в кортежи (привязки).
  • Выразительность: ответы на запросы за пределами простых фрагментов EPFO ​​и EFO и стремление к выразительности языков баз данных.

Наконец, в разделах Наборы данных и Оценка:

  • Необходимость в более крупных и разнообразных тестах, охватывающих больше модальностей графиков, более выразительную семантику запросов, больше операторов запросов и шаблонов запросов.
  • Поскольку существующий протокол оценки кажется ограниченным (сосредоточен только на выводе жестких ответов), существует потребность в более принципиальной структуре и показателях оценки, охватывающих различные аспекты ответа на запрос. рабочий процесс.

Что касается хранилища нейронных графов и NGDB в целом, мы выделяем следующие проблемы:

  • Необходимость в масштабируемом механизме поиска для масштабирования нейронных рассуждений до графов с миллиардами узлов. Извлечение тесно связано с обработчиком запросов и его априорными моделями. Существующие библиотеки масштабируемых ИНС могут работать только с базовыми L1, L2 и косинусными расстояниями, которые ограничивают пространство возможных процессоров в механизме нейронных запросов.
  • В настоящее время все наборы данных сложных запросов предоставляют жестко запрограммированный план выполнения запроса, который может быть неоптимальным. Необходим нейронный планировщик запросов, который преобразовывал бы входной запрос в оптимальную последовательность выполнения с учетом задач прогнозирования, сложности запроса, типа нейронного процессора и конфигурации уровня хранилища.

Из-за индуктивности и возможности обновления кодировщика без переобучения необходимо облегчить проблемы постоянного обучения, катастрофического забывания и обобщения размеров при запуске. вывод на гораздо больших графах, чем обучающие.

Узнать больше

NGDB все еще является новой концепцией со многими открытыми проблемами для будущих исследований. Если вы хотите узнать больше о NGDB, не стесняйтесь проверить

  • 📜 наша газета (arxiv),
  • 🌐 наш сайт,
  • 🔧 Репозиторий GitHub с самым актуальным списком соответствующих статей, наборов данных и категоризацией, не стесняйтесь открывать вопросы и PR.

Также мы будем проводить мастер-классы, следите за обновлениями!