Недавно я наткнулся на встраивание графиков, таких как DeepWalk и LINE. Тем не менее, я до сих пор не имею четкого представления о том, что подразумевается под вложением графов и когда его использовать (приложения)? Любые предложения приветствуются!
13
Ответы:
Внедрение графа изучает отображение из сети в векторное пространство, сохраняя при этом соответствующие свойства сети.
Векторные пространства более поддаются науке о данных, чем графы. Графики содержат ребра и узлы, эти сетевые отношения могут использовать только определенное подмножество математики, статистики и машинного обучения. Векторные пространства имеют более богатый набор инструментов из этих доменов. Кроме того, векторные операции часто проще и быстрее, чем эквивалентные графовые операции.
Одним из примеров является поиск ближайших соседей. Вы можете выполнить «прыжки» от узла к другому узлу на графике. На многих реальных графиках после пары прыжков содержится мало значимой информации (например, рекомендации друзей друзей друзей). Однако в векторных пространствах вы можете использовать метрики расстояния для получения количественных результатов (например, евклидово расстояние или косинусное сходство). Если у вас есть количественные метрики расстояния в значимом векторном пространстве, найти ближайших соседей просто.
« Методы встраивания графиков, приложения и производительность: обзор » - это обзорная статья, которая углубляется в детали.
источник
Что такое графические вложения? «Graph Embeddeds» сегодня является горячей областью в машинном обучении. Это в основном означает поиск «скрытого векторного представления» графов, которое отражает топологию (в самом базовом смысле) графа. Мы можем сделать это «векторное представление» богатым, также учитывая отношения вершина-вершина, информацию о ребрах и т. Д. В графе есть примерно два уровня вложений (конечно, мы можем в любое время определить больше уровней, логически разделив весь граф на подграфы разных размеров):
Приложения - если присмотреться, вложения являются «скрытыми» представлениями, что означает, что граф имеет | V | * | V | матрица смежности где | V | = 1M, трудно использовать или обрабатывать числа 1M * 1M в алгоритме. Таким образом, скрытое вложение размерности 'd', где d << | V |, сделало бы матрицу смежности | V | * г и относительно проще в использовании. Другое приложение может быть - Рассмотрим простой сценарий, в котором мы хотим рекомендовать продукты людям, которые имеют схожие интересы в социальной сети. Получая вложения вершин (здесь это означает векторное представление каждого человека), мы можем найти похожие путем построения этих векторов, и это облегчает рекомендации. Это одни приложения, а есть и другие. Вы можете обратиться к хорошей обзорной статье - Методы вложения графиков, Опрос .
Откуда все это пришло? В этой области было проделано много работ, и почти все они были получены из новаторских исследований в области обработки естественного языка - "Word2Vec" Миколова. Если вы хотите начать исследования встраивания графов, я бы рекомендовал сначала понять, как работает Word2Vec. Вы можете найти хорошие объяснения - объяснение изучения параметров Word2Vec и лекция Стэнфорда . Затем вы можете перейти к документам, которые вы перечислили. Эти работы могут быть классифицированы как:
Работает на основе "Вершинных вложений ": - DeepWalk , Node2Vec , LINE .
Работы, основанные на «Графических вложениях»: - Ядра Deep Graph , Subgraph2Vec .
источник
В статье Центральная предельная теорема для вложения в омнибус случайных графов точечных произведений Левина и др. В частности, конкретный тип вложения графа (вложение Омнибуса) определяет вложение графа как методологию, «в которой вершины графа отображаются на векторы в евклидовом пространстве с низкой размерностью». Проверьте ссылку для получения дополнительной информации.
источник