"Начиная"

Вложения узлов

Введение

Это обзор вложения узлов от Christos Ziakas, Jan Rüttinger и Till Richter. Он проводился в Лаборатории машинного обучения группы аналитики данных и машинного обучения ТУМ. Благодарим Александра Щура за руководство нашим проектом и Проф. Доктор Гюннеманн за возможность проводить исследования в своей группе.

Код этого проекта можно найти на GitHub.

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

Почему графики?

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

Приложения

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

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

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

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

Мотивация

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

Техники встраивания

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

Бернулли (4 модели)

Для моделей Бернулли оценка подобия истинного графа дается в форме матрицы смежности. Таким образом, запись равна 1, если два узла соединены, и 0 в противном случае. Декодер дает оценку подобия во вложенном пространстве, которое может быть сигмоидальным, экспоненциальным, гауссовым или основанным на расстоянии встраивании. Таким образом, мы моделируем потери, чтобы сгенерировать смежность с учетом встроенной матрицы.

Где ядро ​​может быть либо

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

KL Дивергенция (3 модели)

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

СВД (7 моделей)

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

Эксперимент

Всего сравнивается 14 методов встраивания с использованием 3 оценочных задач на 4 популярных наборах данных для графиков.

Результаты

Для результатов, в частности, сравнение одной и той же меры сходства, например Интересна матрица смежности при различных техниках встраивания.

При прогнозировании ссылок:

По той же мере сходства модели на основе KL превосходят модели на основе SVD для стохастических матриц.

По классификации узлов:

Для классификации узлов все модели показывают одинаковую производительность.

О кластеризации узлов:

Модели на основе KL работают лучше, чем модели на основе Бернулли и SVD. В частности, SVD проигрывает в этом сравнении из-за слишком большого количества шума, включенного в более высокие размеры. В результатах SVD это дополнительно анализируется.

По СВД:

С увеличением числа встраиваемых измерений производительность моделей SVD для кластеризации узлов снижается.

О Бернулли:

Модели на основе z_i - z_j работают лучше, чем модели на основе ZZ ^ T. Причиной тому может быть необходимость регуляризации, возникающая при умножении. Для сравнения не использовалась регуляризация.

По времени схождения:

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

Вывод

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