Понимание встраивания графов

В последние годы встраивание графов становится все более важным в стратегии корпоративного графа знаний или Enterprise Knowledge Graph (EKG). Вложения графов скоро станут де-факто способом быстрого поиска похожих элементов в больших графах с миллиардами вершин. Расчеты результатов запроса пользователей в реальном времени имеют решающее значение для многих областей (например рекомендаций), необходимо научиться создавать когорты.

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

Прогулка Маугли

Метафора объяснения строится на сюжете повести Редьярда Киплинга «Книга джунглей». Главный герой, мальчик Маугли, живет в деревне, окруженной прочной оградой. У Маугли есть домашний кот с оранжевым мехом и полосками. Однажды Маугли идет по тропинке сразу за деревенской оградой встречает большого тигра. Что делать Маугли?

Должен ли он продолжать путь или быстро бежать обратно в деревню? У Маугли не так много времени, чтобы принять это решение. Всего пара секунд. Мозг Маугли обнаруживает угрозы в режиме реального времени, и его жизнь зависит от быстрого решения.

Если мозг Маугли думает, что животное похоже на его домашнюю кошку, он пойдет по тропинке. Но если он понял, что это тигр и это представляет угрозу, он быстро убежит обратно в безопасное место в деревне.

Как эволюционировал мозг Маугли, чтобы выполнять эту оценку угроз в реальном времени? Образ тигра поступает через глаза Маугли и передается в зрительную кору его мозга. Оттуда извлекаются ключевые особенности изображения. Сигналы этих признаков посылаются в области классификации объектов его мозга. Маугли нужно сравнить это изображение с любым другим изображением, которое он когда-либо видел, а затем сопоставить его со знакомыми понятиями. Его мозг вычисляет сходство в реальном времени.

Как только мозг Маугли сопоставит изображение с концепцией тигра, а концепция тигра, в свою очередь, будет связана с эмоцией «опасности» в центре страха миндалевидного тела мозга, то Маугли развернется и побежит обратно в деревню. Эта быстрая реакция может даже не пройти логическую обработку в неокортексе Маугли, потому что для обдумывания этого требуется дополнительное время, и люди с такими генами уже удалены из генофонда. Мы создали структуры данных в нашем мозгу, которые способствуют нашему выживанию, анализируя миллионы входных данных с сетчатки наших глаз с точностью до 1/10 секунды.

Сжатие данных экономит ресурсы и ускоряет ответ

Хорошо, как это связано с встраиванием графов? Это небольшие структуры данных, которые помогают функциям ранжирования сходства в реальном времени в нашем корпоративном графе знаний. Они работают так же, как части классификации в мозгу Маугли. Вложения поглощают большой объем информации о каждом элементе нашего EKG, возможно, из миллионов элементов данных. Встраивания сжимают его в компактные структуры данных, которые легко сравнивать в режиме реального времени с использованием недорогого оборудования для параллельных вычислений, такого как FPGA. Они позволяют выполнять расчеты сходства в реальном времени, которые можно использовать для классификации элементов на вашем графе и предоставления рекомендаций пользователям в реальном времени, экономя большие ресурсы на расчетах.

Допустим, пользователь заходит на ваш интернет-магазин в поисках подарка на рождение сына. Должны ли мы порекомендовать симпатичную плюшевую игрушку тигра или популярный новый пистолет? Можем ли мы порекомендовать нужный элемент за 1/10 секунды? В ближайшем будущем способность компании быстро реагировать на потребности клиентов и давать рекомендации относительно дальнейших действий будет иметь решающее значение для выживания любой организации. EKG могут экономично хранить десятки тысяч элементов данных об истории клиентов. Вложения помогают нам анализировать эти данные в автономном режиме и использовать их в сжатом виде во встраивании в режиме реального времени.

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

Что такое встраивание графов?

Прежде чем объяснить способ хранения данных и вычисления вложения, опишем структуру встраивания и характеристики того, что делает вложения полезными для аналитики в реальном времени.

Встраивание графов — это структуры данных, используемые для быстрого сравнения похожих структур данных. Слишком большие графы требуют больше оперативной памяти и больше времени для вычисления сравнения. Но в этой истории меньше значит лучше.
Вложения графа сжимают многие сложные функции и структуры данных вокруг вершины нашего графа, включая все атрибуты вершины и атрибуты ребер и вершин вокруг основной вершины. Данные вокруг вершины называются «контекстным окном», которое мы обсудим позже.

Вложения графов рассчитываются с использованием алгоритмов машинного обучения

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

Процесс создания нового вектора встраивания называется «кодированием» или «кодированием вершины». Процесс регенерации вершины из вложения называется «декодированием» или генерацией вершины. Процесс измерения того, насколько хорошо работает вложение, и поиска похожих элементов называется «функцией потерь».

Не может быть «семантики» или значения, связанного с каждым числом во вложении. Вложения можно рассматривать как низкоразмерное представление элемента в векторном пространстве. Элементы, которые находятся рядом друг с другом в этом пространстве встраивания, считаются похожими друг на друга в реальном мире. Встраивания ориентированы на производительность, а не на смысл.

Вложения идеально подходят для «нечетких» задач соответствия

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

Вложения графов работают с другими алгоритмами графов

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

Близость в пространстве для встраивания

Что означает сходство двух понятий? Начнем с метафоры географической карты.

Учитывая две точки на карте, мы можем рассчитать расстояние между этими двумя точками, используя формулу расстояния. Входные данные — это просто координаты двух точек, выраженные в виде чисел, таких как их долгота и широта. Задача также может быть обобщена на три измерения для двух точек в пространстве. Но в версии для трехмерного пространства вычисление расстояния добавляет дополнительный термин для высоты или оси Z.

Вычисления расстояний во встраивании работают аналогичным образом. Суть в том, что вместо двух или трех измерений у нас может быть 200 или 300 измерений. Единственная разница заключается в добавлении одного члена расстояния для каждого нового измерения.

Аналогии встраивания слов

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

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

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

Обратите внимание, что если у нас есть новое слово, которое мы никогда раньше не видели, этот подход не сработает.

Английский язык насчитывает около 40 000 слов, используемых в обычной речи. Мы могли бы поместить каждое из этих слов в граф знаний и создать попарную связь между каждым словом и каждым другим словом. Вес на ссылке будет расстоянием. Однако это было бы неэффективно, поскольку с помощью встраивания мы могли бы быстро пересчитать ребро и вес.

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

Как хранятся встраивания графов?

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

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

Размер вложений

Вложения графов обычно содержат от 100 до 300 числовых значений. Отдельные значения обычно представляют собой 32-битные десятичные числа, но бывают ситуации, когда вы можете использовать меньшие или большие типы данных. Чем меньше точность и длина вектора, тем быстрее вы сможете сравнить этот элемент с аналогичными элементами.

Для большинства сравнений не требуется более 300 чисел во встраивании. Если алгоритмы машинного обучения сильны, мы можем сжать многие аспекты нашей вершины в эти значения.

Нет семантики с каждым значением

Числа могут не представлять того, что мы можем напрямую связать с одним атрибутом или формой графа. У нас может быть функция под названием «возраст клиента», но встраивание не обязательно будет иметь одно число для функции возраста. Возраст может быть объединен с одним или несколькими числами.

Любая вершина может иметь вложение

Вложения могут быть связаны со многими вещами на вашем EKG. Любой важный элемент, такой как клиент, продукт, магазин, поставщик, грузоотправитель, веб-сеанс или жалоба, может иметь свой собственный вектор внедрения.

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

Существуют также проекты, в которых создаются вложения для ребер и путей, но они не так распространены, как встраивания вершин.

Расчет контекстного окна встраивания

Область вокруг вершины, используемая для кодирования встраивания, называется контекстным окном. К сожалению, простого алгоритма определения окна контекста не существует. Некоторые вложения могут учитывать только покупки клиентов за последний год для расчета встраивания. Другие алгоритмы могут учитывать покупки и поиски за всю жизнь, которые произошли с тех пор, как клиент впервые посетил веб-сайт. Понимание влияния времени на вложение, называемое темпоральным анализом, может потребовать дополнительных правил и настройки. Очевидно, что покупатель, купивший детские подгузники на вашем веб-сайте 20 лет назад, может сильно отличаться от покупателя, который только начал покупать их в прошлом месяце.

Встраивания и разработка функций с ручным кодированием

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

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

Компромиссы создания вложений

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

Гомогенные и гетерогенные графики

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

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

Социальные сети, где каждая вершина — это человек, а единственный тип ссылки — «подписчики» или «друг» — еще один тип однородного графа. Вложения слов, где каждое слово или фраза имеют вложение, являются еще одним примером однородного графа.

К сожалению, графы знаний обычно имеют много разных типов вершин и много типов ребер. Они известны как многодольные графы. И именно они усложняют процесс вычисления вложений. Граф клиентов может иметь такие типы, как «Клиент», «Продукт», «Покупка», «Посещение Интернета», «Поиск в Интернете», «Обзор продукта», «Возврат продукта», «Жалоба на продукт», «Ответ на рекламу», «Использование купона», «Ответ на опрос» и т. д. Создание вложений из сложных наборов данных может занять некоторое время, чтобы настроить алгоритмы машинного обучения.

Как рассчитываются внедрения Enterprise Knowledge Graph (EKG)

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

В Google Scholar есть около 1400 статей, в которых упоминается тема «встраивания графов знаний». В целом они делятся на две категории.

1. Граф сверточных нейронных сетей (GCN)
2. Случайные прогулки

Граф сверточных нейронных сетей (GCN)

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

Алгоритмы случайного блуждания

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

Заключение

Автор надеется, что истории и метафоры в этой статье дали вам более интуитивное представление о том, что такое встраивание графов и как они используются для ускорения аналитики в реальном времени. Хотя вас может обескуражить тот факт, что не существует окончательной библиотеки функций для вычисления вложений на всех платформах, возможно очень скоро они появятся, т.к. сейчас это активная область исследований. Так же, как AlexNet открыла новые возможности в классификации изображений, а BERT установила новый стандарт для NLP, в течение следующих нескольких лет встраивание графов займет центральное место в области инновационной аналитики. Встраивания явно являются горячей темой в глубоком обучении.

Автор Дэн МакКрири, инженер по графам знаний

Адаптация и курирование: Онтограф