График:
Графики, такие как социальные сети, сети элементов-пользователей, естественным образом встречаются в различных реальных приложениях. Просто используя узлы, ребра и их свойства, мы можем найти взаимосвязь между многими вещами: баскетболистами и командами, фильмами и издателями, стартапами и фондами. Поэтому в последние годы анализ графов привлекает все большее внимание из-за повсеместного распространения сетей в реальном мире. Например, на веб-сайте электронной коммерции мы можем наблюдать за сетью клиент-продукт, чтобы найти сходство клиентов, сходство товаров и сходство клиентов с разными продуктами. Задачи графического анализа можно в общих чертах разделить на следующие три категории:
(1) классификация узлов.
(2) предсказание ссылки.
(3) кластеризация.
Классификация узлов заключается в классификации меток узлов на основе других помеченных узлов и структуры сети. В целом существует две категории подходов: методы, которые используют случайные обходы для распространения меток, и методы, которые извлекают функции из узлов и применяют к ним классификаторы.
Прогнозирование ссылок - это задача прогнозирования недостающих ссылок или ссылок, которые могут появиться в будущем. Например, в сети «пользователь-элемент» прогнозирование ссылки предназначено для прогнозирования того, щелкнет ли клиент или купит элемент в будущем. Подходы к прогнозированию ссылок включают методы, основанные на сходстве, модели максимального правдоподобия и вероятностные модели.
Проблема кластеризации связана с поиском похожих объектов в сети и их объединением. Методы кластеризации включают модели и методы на основе атрибутов, которые напрямую максимизируют межкластерные расстояния.
Традиционно мы просто используем исходную матрицу смежности графа для построения моделей для решения задач на основе графов. Однако это определенно проблема, если у нас есть миллиарды узлов и ребер. В последнее время, вдохновленные word2vec Google, методы, основанные на представлении сетей в векторном пространстве с сохранением их свойств, стали широко популярными. Вложения вводятся в модель как функции, а параметры изучаются на основе данных обучения.
Встраивание графиков:
Встраивание сопоставляет каждый узел с вектором признаков низкой размерности и пытается сохранить силу соединения между вершинами. Вот три основных типа методов встраивания графов:
(1) На основе факторизации.
(2) На основе случайного блуждания.
(3) На основе глубокого обучения.
Методы на основе факторизации, которые непосредственно вдохновлены классическими методами уменьшения размерности, представляют связи между узлами в форме матрицы и факторизуют эту матрицу для получения вложений. Эти методы включают в себя локально линейное вложение (LLE), лапласовские собственные карты (LE), вложение графа Коши (CGE), вложение с сохранением структуры (SPE), факторизацию графов (GF). GraRep и НАДЕЖДА.
В подходе, основанном на случайном блуждании, вложение графа генерируется путем построения матрицы на основе узлов и ребер данного графа.
Методы, основанные на глубоком обучении (мой любимый), были разработаны с недавним успехом в нейронных сетях. В отличие от методов факторизации, которые вычисляют вложения с использованием линейных функций на графике, методы глубокого обучения позволяют нам вычислять нелинейные функции на графиках, что может привести к повышению производительности. Однако методы, основанные на глубоком обучении, могут быть сложнее установить выше, чем методы факторизации или встраивания графов случайных блужданий. Некоторые примеры методов встраивания графов с глубоким обучением включают использование автокодировщика для создания низкоразмерного представления данных (SDNE), использование сверточных сетей графов (GCN), использование глубоких нейронных сетей для генерации представлений графов (DNGR) и использование сверточный сетевой кодировщик графов и решатель внутреннего продукта для оценки производительности автокодировщиков вариационных графов (VGAE).
Полезные ссылки для изучения моделей встраивания графов:
