Недавно я закончил Стэнфордский курс CS224W Machine Learning with Graphs. Это вторая часть серии постов в блоге, где я делюсь своими заметками после просмотра лекций. Остальные вы можете найти здесь: 1, 3, 4.

Классификация узлов означает:данная сеть с метками на некоторых узлах назначает метки всем остальным узлам в сети. Основная идея этой лекции — рассмотреть коллективную классификацию, использующую существующие корреляции в сетях.

Индивидуальное поведение коррелируется в сетевой среде. Например, сеть, в которой узлы — это люди, ребра — это дружба, а цвет узлов — это раса: люди разделены по расе из-за гомофилии (склонности людей объединяться и связываться с похожими другими).

Принцип «вины по ассоциации»: похожие узлы обычно расположены близко друг к другу или связаны напрямую; если я подключен к узлу с меткой X, то, скорее всего, у меня также будет метка X.

Коллективная классификация

Интуиция, стоящая за этим методом: одновременно классифицируйте взаимосвязанные узлы, используя корреляции.

Применение метода можно найти в:

  • классификация документов,
  • тегирование речи,
  • предсказание ссылок,
  • оптическое распознавание символов,
  • сегментация изображений/3D-данных,
  • разрешение объектов в сенсорных сетях,
  • обнаружение спама и мошенничества.

*некоторые списки/абзацы/формулы/изображения могут быть отключены, проверьте исходную публикацию на https://elizavetalebedeva.com/ml-with-graphs-notes-part-2/

Коллективная классификация основана на предположении Маркова — метка одного узла i зависит от меток его соседей:

Этапы алгоритмов коллективной классификации:

  1. Локальный классификатор: используется для первоначального присвоения ярлыка.
  • Предсказать метку на основе атрибутов/функций узла.
  • Стандартная классификационная задача.
  • Не используйте сетевую информацию.

2. Реляционный классификатор: фиксирует корреляции между узлами на основе сети.

  • Изучите классификатор для маркировки одного узла на основе меток и/или атрибутов его соседей.
  • Используется сетевая информация.

3. Коллективный вывод: распространение корреляции по сети.

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

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

Методы приближенного вывода (все это итерационные алгоритмы):

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

Вероятностный реляционный классификатор

Идея состоит в том, что вероятность класса Y является средневзвешенным значением вероятностей классов его соседей.

  • Для помеченных узлов инициализируйте их метками Y.
  • Для непомеченных узлов инициализируйте Y единообразно.
  • Обновляйте все узлы в случайном порядке до сходимости или до тех пор, пока не будет достигнуто максимальное количество итераций.

Повторите для каждого узла i и меткиc:

Пример 1-й итерации для одного узла:

Проблемы:

  • Сходимость не гарантируется.
  • Модель не может использовать информацию об узлах.

Итеративная классификация

Основная идея итеративной классификации состоит в том, чтобы классифицировать узел i на основе его атрибутов, а также меток набора соседей:

Архитектура итеративного классификатора:

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

Примечание. Сходимость не гарантируется (необходимо выполнить максимальное количество итераций).

Применение итеративной классификации:

Зацикленное распространение убеждений

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

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

Передача сообщений:

  • Задача: подсчитать количество узлов в графе.
  • Условие: каждый узел может взаимодействовать (передавать сообщения) только со своими соседями.
  • Решение: Каждый узел прослушивает сообщение от своего соседа, обновляет его и передает дальше.

Циклический алгоритм распространения убеждений:

Инициализируйте все сообщения значением 1. Затем повторите для каждого узла:

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

Применение распространения убеждений:

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

  • Он дает распределенные представления для узлов;
  • Сходство вложений между узлами указывает на их сетевое сходство;
  • Сетевая информация кодируется в сгенерированное представление узла.

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

Внедрение узлов

Настройка: граф G с набором вершин V, матрица смежности A (пока никакие особенности узла или дополнительная информация не используются).

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

Встраивания Learning Node:

  1. Определите кодировщик (т. е. сопоставление узлов с вложениями).
  2. Определите функцию сходства узла (т. е. меру сходства в исходной сети).

Два компонента:

  • Кодировщик: сопоставляет каждый узел маломерному вектору.Enc(v) =где v — узел входного графа и d-мерное вложение.
  • Функция подобия: указывает, как отношения в векторном пространстве сопоставляются с отношениями в исходной сети — zTz — скалярное произведение между вложениями узлов.

Поверхностное кодирование

Самый простой подход к кодированию - это когда кодировщик - это просто поиск встраивания.

Enc(v) = Zv, где Z – матрица, в которой каждый столбец представляет собой вложение узлов (что мы изучаем), а v – индикаторный вектор. со всеми нулями, кроме единицы, в столбце, указывающем узел v.

Множество методов кодирования: DeepWalk, node2vec, TransE. Методы различаются тем, как они определяют сходство узлов (должны ли два узла иметь одинаковые вложения, если они соединены, имеют общих соседей или имеют схожие «структурные роли»?).

Подходы Random Walk к внедрению узлов

Учитывая граф и начальную точку, мы случайным образом выбираем его соседа и движемся к этому соседу; затем случайным образом выбираем соседа этой точки и движемся к нему и т. д. (Случайная) последовательность выбранных таким образом точек представляет собой случайное блуждание по графу.

Свойства случайных блужданий:

  • Выразительность: гибкое стохастическое определение сходства узлов, которое включает как локальную информацию, так и информацию о соседстве более высокого порядка.
  • Эффективность: не нужно учитывать все пары узлов при обучении; нужно рассматривать только пары, которые встречаются при случайных блужданиях.
  1. Запустите короткие случайные блуждания фиксированной длины, начиная с каждого узла на графе, используя некоторую стратегию R.
  2. Для каждого узла u соберите N(u), мультимножество (узлы могут повторяться) узлов, посещенных при случайном блуждании, начиная с u.

Оптимизация вложений: заданный узел u предсказывает его соседей

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

Затем параметризуйте его с помощью softmax:

где первая сумма представляет собой сумму по всем узлам u, вторая сумма представляет собой сумму по узлам v, наблюдаемым при случайном блуждании, начиная с u, и дробью (под журналом ) — прогнозируемая вероятность совпадения u и v при случайном блуждании.

Оптимизация вложений случайных блужданий = Поиск вложений z u, которые минимизируют Λ. Наивная оптимизация слишком дорога, используйте отрицательную выборку для аппроксимации.

Стратегии для самого случайного блуждания:

  • Простейшая идея: просто запускать беспристрастные случайные блуждания фиксированной длины, начиная с каждого узла (например, DeepWalk из Perozzi et al., 2013). Но такое понятие сходства слишком условно.
  • В более общем виде: node2vec.

Node2vec: необъективные прогулки

Идея: использовать гибкие, предвзятые случайные блуждания, которые могут выбирать между локальным и глобальным представлениями сети (Гровер и Лесковец, 2016).

Два параметра:

  1. Возвращаемый параметр p: возврат к предыдущему узлу.
  2. Параметр входа-выхода q: движение наружу (DFS) и внутрь (BFS). Интуитивно q — это «отношение» BFS к DFS.

Алгоритм Node2vec:

  1. Вычислить вероятности случайного блуждания.
  2. Моделирование r случайных блужданий длиной l, начиная с каждого узла u.
  3. Оптимизируйте цель node2vec с помощью стохастического градиентного спуска.

Методы случайного блуждания, как правило, более эффективны.

Перевод вложений для моделирования многореляционных данных

Граф знаний состоит из фактов/утверждений о взаимосвязанных объектах. Узлы называются сущностями, ребра — отношениями. В графах знаний (KG) ребра могут быть разных типов!

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

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

В методе Translating Embeddings ( TransE) отношения между объектами представлены в виде триплетов h (головной объект), l (отношение), t (хвостовая сущность) =› (ℎ, l, t).

Сущности сначала встраиваются в пространство сущностей R, а отношения представляются как переводы ℎ + l ≈ t, если данный факт верен, иначе ℎ + l ≠ t.

Встраивание целых графиков

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

Подход 1:

Запустите стандартный метод встраивания графа в (под)граф G. Затем просто просуммируйте (или усредните) вложения узлов в (под)граф G. (Duvenaud et al., 2016 — классификация молекул на основе их структуры графа).

Подход 2:

Идея: ввести «виртуальный узел» для представления (под)графа и запустить стандартную технику встраивания графа (предложенную Li et al., 2016 в качестве общей техники встраивания подграфа).

Подход 3 — встраивание анонимных обходов:

Состояния в анонимном блуждании соответствуют индексу первого посещения узла в случайном блуждании.

Встраивание Anonymous Walk имеет 3 метода:

  1. Представьте граф через распределение по всем анонимным блужданиям (перечислите все возможные анонимные блуждания ai из l шагов, запишите их количество и переведите его в распределение вероятностей.
  2. Создайте суперузел, который охватывает (под)граф, а затем вставьте этот узел (поскольку полный подсчет всех анонимных обходов в большом графе может быть невозможен, образец для аппроксимации истинного распределения: сгенерируйте независимо набор m случайные блуждания и вычислить соответствующее эмпирическое распределение анонимных блужданий).
  3. Встроить анонимные блуждания (изучить вложение zi каждого анонимного блуждания ai. Вложение графа G тогда представляет собой сумму/среднее/объединение вложений блужданий zi).

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

Enc(v) =несколько слоев нелинейных преобразований структуры графа.

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

Наивный подход применения CNN к сетям:

  • Соедините матрицу смежности и функции.
  • Подайте их в глубокую нейронную сеть.

Проблемы с этой идеей: O(N) параметров; не применимо к графикам разного размера; не инвариантно к порядку узлов.

Основы глубокого обучения для графов

Настройка: граф G с набором вершин V, матрица смежности A (предположим, бинарная), матрица признаков узла X(например, профиль пользователя и изображения для социальных сетей, профили экспрессии генов и функциональная информация генов для биологических сетей; для случая без признаков это могут быть индикаторные векторы (горячее кодирование узла) или вектор константа 1 [1, 1, …, 1]).

Идея: соседство узла определяет граф вычислений — › генерировать вложения узлов на основе соседства локальной сети. За идеей стоит интуиция: узлы собирают информацию от своих соседей с помощью нейронных сетей.

Модель может быть произвольной глубины:

  • Узлы имеют вложения на каждом уровне.
  • Вложение уровня 0 узла x является его входной функцией, .
  • Встраивание Layer-K получает информацию от узлов, которые находятся на расстоянии K переходов.

Различные модели различаются тем, как они агрегируют информацию по слоям (как выполняется агрегация соседей).

Основной подход заключается в усреднении информации от соседей и применении нейронной сети.

Вложения начального 0-го слоя равны характеристикам узла: . Следующие:

где σ — нелинейность (например, ReLU), — вложение предыдущего слоя v, сумма (после W k) — среднее вложение предыдущего слоя v-го соседа.

Встраивание после K слоев агрегации окрестностей: .

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

  1. Неконтролируемый способ: используйте только структуру графа.
  • «Похожие» узлы имеют похожие вложения.
  • Неконтролируемая функция потерь может быть чем угодно: от случайных блужданий (node2vec, DeepWalk, struc2vec), факторизации графа, близости узлов в графе.

2. Контролируемый способ: непосредственное обучение модели контролируемой задаче (например, классификация узлов):

где — вывод кодировщика (встраивание узла), — метка класса узла, θ — веса классификации.

Этапы обучения под наблюдением:

  1. Определение функции агрегации окрестности
  2. Определите функцию потерь для вложений
  3. Тренируйтесь на наборе узлов, т. е. на пакете вычислительных графов.
  4. Создание вложений для узлов по мере необходимости

Одни и те же параметры агрегации являются общими для всех узлов:

Подход имеет индуктивный потенциал (создание вложений для невидимых узлов или графов).

Граф сверточных сетей и GraphSAGE

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

Варианты

Граф сверточных сетей усредняет информацию о соседстве и складывает нейронные сети. Оператор свертки графа объединяет сообщения по окрестностям, N(v).

a = 1/|N(v)| — весовой коэффициент (важность) сообщения узла u узлу v. Таким образом, a определяется явным образом на основе структурных свойств графа. Все соседи u ∈ N(v) одинаково важны для узла v.

GraphSAGE использует обобщенную агрегацию соседей:

Графические сети внимания

Идея: вычислить встраивание каждого узла в граф, следуя стратегии внимания:

  • Узлы посещают сообщения своих соседей.
  • Неявное указание разных весов для разных узлов в окрестности.

Пусть вычисляется как побочный продукт механизма внимания a. Пусть a вычисляет коэффициенты внимания для пар узлов u, v на основе их сообщений: указывает важность сообщения узла u узлу v , Затем нормализуйте коэффициенты с помощью функции softmax, чтобы их можно было сравнивать в разных районах:

Форма механизма внимания a:

  • Подход не зависит от выбора a
  • Например, используйте простую однослойную нейронную сеть.
  • a может иметь параметры, которые должны быть оценочными.
  • Параметры a обучаются совместно:

Документ Величковича и др. введено многоголовое внимание для стабилизации процесса обучения механизма внимания:

  • Операции внимания на данном уровне независимо реплицируются R раз (каждая реплика с разными параметрами). Выходы агрегируются (путем объединения или добавления).
  • Ключевое преимущество: позволяет (неявно) указывать разные значения важности () для разных соседей.
  • Вычислительная эффективность: вычисление коэффициентов внимания может быть распараллелено по всем ребрам графа, агрегирование может быть распараллелено по всем узлам.
  • Эффективное хранение: для операций с разреженными матрицами требуется хранить не более O(V+E) записей; фиксированное количество параметров, независимо от размера графика.
  • Тривиально локализовано: посещает только районы локальной сети.
  • Индуктивная способность: общий пограничный механизм, не зависящий от глобальной структуры графа.

Пример приложения: PinSage

Граф Pinterest имеет 2 миллиарда выводов, 1 миллиард досок, 20 миллиардов ребер и является динамическим. PinSage граф сверточной сети:

  • Цель: создать встраивания для узлов (например, пинов/изображений) в веб-графе Pinterest, содержащем миллиарды объектов.
  • Ключевая идея: Заимствовать информацию у ближайших узлов. Например, ограждение кровати Pin может выглядеть как садовая ограда, но ворота и кровати редко соседствуют на графике.
  • Встраивание пинов необходимо для различных задач, таких как рекомендации пинов, классификация, кластеризация, ранжирование.
  • Проблемы: большая сеть и богатые возможности изображения/текста. Как масштабировать обучение, а также вывод встраивания узлов в графы с миллиардами узлов и десятками миллиардов ребер?

Ключевые новшества:

  1. Свертки графа на лету:
  • Выберите окрестности вокруг узла и динамически постройте граф вычислений.
  • Выполните свертку локализованного графа вокруг определенного узла.
  • Не нужен весь график во время обучения.

2. Построение сверток методом случайных блужданий:

  • Выполнение сверток над полными окрестностями невозможно.
  • Пул важности для выбора набора соседей узла для свертки: определите окрестности на основе важности, имитируя случайные блуждания и выбирая соседей с наибольшим количеством посещений.

3. Эффективный вывод MapReduce:

Общие советы по работе с GNN

  • Предварительная обработка данных важна:
  • Используйте приемы перенормировки.
  • Инициализация в масштабе дисперсии.
  • Отбеливание сетевых данных.
  • Оптимизатор ADAM: естественно заботится о снижении скорости обучения.
  • Функция активации ReLU часто работает очень хорошо.
  • Нет функции активации на вашем выходном слое: простая ошибка, если вы создаете слои с общей функцией.
  • Включите термин смещения в каждый слой.
  • Слоя GCN размером 64 или 128 уже достаточно.

В Colab Notebook есть все, что нужно для работы с PyTorch Geometric. Проверьте это!

В бесценных лекциях мы рассмотрели кодировщики графов, где выходные данные представляют собой встраивания графов. Эта лекция посвящена противоположному аспекту — декодерам графов, где выходными данными являются структуры графов.

Проблема построения графика

Почему важно генерировать реалистичные графики (или синтетические графики на основе большого реального графика)?

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

Задачи построения графа:

  1. Создание реалистичных графиков: создавайте графики, похожие на заданный набор графиков [Фокус этой лекции].
  2. Генерация целевых графиков: создание графиков, которые оптимизируют заданные цели/ограничения (генерация/оптимизация молекулы лекарства). Примеры: обнаружение молекул, очень похожих на лекарства, завершение существующей молекулы для оптимизации желаемого свойства.

Почему задачи Graph Generation сложны:

  • Большое и переменное выходное пространство (для узлов n нам нужно сгенерировать n*n значений; размер графа (узлы, ребра) варьируется).
  • Неуникальные представления (n-узловой граф может быть представлен n! способами; трудно вычислить/оптимизировать целевые функции (например, восстановление ошибки)).
  • Сложные зависимости: формирование ребра имеет дальнодействующие зависимости (наличие ребра может зависеть от всего графа).

Генерационные модели графов

Настройка: мы хотим изучить генеративную модель из набора точек данных (т. е. графиков) {}; ) — это распределение данных, которое нам никогда не известно, но мы взяли выборку ). — это модель, параметризованная параметром θ, которую мы используем для аппроксимации ).

Цель:

Для проектирования f(⋅)используйте Deep Neural Networks и обучите его, используя имеющиеся у нас данные.

Эта лекция посвящена авторегрессионным моделям (предсказание будущего поведения на основе прошлого поведения). Резюме авторегрессионных моделей: используется как для оценки плотности, так и для выборки (из плотности вероятности). Затем примените цепное правило: совместное распределение является продуктом условных распределений:

В нашем случае: x будет t-м действием (добавить узел, добавить ребро).

[ Ю и др., ICML 2018]

Идея: создание графов путем последовательного добавления узлов и ребер. Граф G с порядком узлов π может быть однозначно отображен в последовательность добавлений узлов и ребер S π.

Последовательность S π имеет два уровня:

  • Уровень узла: на каждом шаге добавляйте новый узел.
  • Уровень ребра: на каждом шаге добавляйте новое ребро/ребра между существующими узлами. Например, шаг 4 для рисунка выше Sπ4 = (Sπ4,1, Sπ4,2, Sπ431: 0,1,1) означает соединение 4&2, 4&3, но не 4&1).

Таким образом, S представляет собой последовательность последовательностей: граф + порядок узлов. Порядок узлов выбирается случайным образом.

Мы преобразовали задачу генерации графа в задачу генерации последовательности. Теперь нам нужно смоделировать два процесса: сгенерировать состояние для нового узла (последовательность на уровне узла) и сгенерировать ребра для нового узла на основе его состояния (последовательность на уровне ребра). Мы используем RNN для моделирования этих процессов.

GraphRNN имеет RNN на уровне узла и RNN на уровне края. Связь между двумя RNN:

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

Для инициализации используйте токен начала/конца последовательности (SOS, EOS) — например, нулевой вектор. Мы могли бы позволить генерировать последовательности, но эта модель детерминирована. Вот почему мы используем образец Thenis. Другими словами, каждый шаг RNN выводит вектор вероятности; затем мы делаем выборку из вектора и передаем выборку на следующий шаг.

В процессе обучения мы используем принцип «Teacher Forcing», изображенный ниже: заменяем ввод и вывод реальной последовательностью.

  1. Предположим, что узел 1 находится на графике. Затем добавьте узел 2.
  2. Edge RNN предсказывает, как узел 2 соединяется с узлом 1.
  3. Edge RNN получает наблюдение от наземной истины.
  4. Новые ребра используются для обновления Node RNN.
  5. Edge RNN предсказывает, как узел 3 соединяется с узлом 2.
  6. Edge RNN получает наблюдение от наземной истины.
  7. Новые ребра используются для обновления Node RNN.
  8. Узел 4 не подключается ни к каким узлам, остановите генерацию.
  9. Обратное распространение во времени: все градиенты накапливаются по временным шагам.
  10. Замените наземную правду собственными предсказаниями GraphRNN.

У GraphRNN есть проблема — удобочитаемость:

  • Любой узел может соединиться с любым предыдущим узлом.
  • Слишком много шагов для создания края:
  • Необходимо создать полную матрицу смежности.
  • Сложные зависимости длинных ребер.

Шаги для создания графика ниже: Добавить узел 1 — Добавить узел 2 — Добавить узел 3 — Соединить 3 с 1 и 2 — Добавить узел 4. Но тогда узел 5 может соединиться с любым/всеми предыдущими узлами.

Чтобы ограничить эту сложность, примените порядок узлов поиска в ширину (BFS). Шаги с BFS: Добавить узел 1 — Добавить узел 2 — Соединить 2 с 1 — Добавить узел 3 — Соединить 3 с 1 — Добавить узел 4 — Соединить 4 с 2 и 3. Поскольку узел 4 не соединяется с узлом 1, мы знаем все соседи узла 1 уже пройдены. Следовательно, узел 5 и последующие узлы никогда не будут подключаться к узлу 1. Нам нужна память только на 2 «шага», а не на n — 1 шаг.

Преимущества:

  • Сократите возможные порядки узлов: с O(n!) до количества различных порядков BFS.
  • Сократите количество шагов для создания ребер (количество предыдущих узлов для просмотра).

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

Применение: открытие лекарств[You et al., NeurIPS 2018]

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

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

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

Открытые проблемы в построении графиков

  • Создание графиков в других областях:
  • Масштабирование до больших графиков:
  • Другие приложения: Обнаружение аномалий.

Лекция посвящена анализу сети как графа. Веб-страницы рассматриваются как узлы, гиперссылки — как ребра. В первые дни веб-ссылки были навигационными. Сегодня многие ссылки являются транзакционными (используются для перехода не со страницы на страницу, а для публикации, комментирования, лайков, покупки и т. д.).

Интернет является ориентированным графом, поскольку ссылки ведут от исходной страницы к целевой. Для всех узлов мы можем определить IN-множество (какие другие узлы могут достигать v?) и OUT-множество (данный узел v, какие узлы могут v достичь?).

Как правило, существует два типа ориентированных графов:

  1. Сильная связь: любой узел может достичь любого узла по направленному пути.
  2. Направленный ациклический граф (DAG) не имеет циклов: если u может достичь v, то v не может достичь u.

Любой ориентированный граф (Сеть) может быть выражен в терминах этих двух типов.

Сильно связанный компонент (SCC) — это набор узлов S, так что каждая пара узлов в S может связаться друг с другом, и не существует большего набора, содержащего S. с этим свойством.

Каждый ориентированный граф является DAG на своих SCC:

  • SCC разделяет узлы G (то есть каждый узел находится ровно в одном SCC).
  • Если мы построим граф G', узлы которого являются SCC, и с ребром между узлами G', если есть ребро между соответствующими SCC в G, то G' — это DAG.

Бродер и др.: веб-сканирование Altavista (октябрь 1999 г.): сделал большой снимок Интернета (203 миллиона URL-адресов и 1,5 миллиарда ссылок), чтобы понять, как его SCC «сочетаются» в качестве DAG.

Авторы вычислили IN(v) и OUT(v), начиная со случайных узлов. BFS либо посещает много узлов, либо очень мало, как показано на графике ниже:

На основе IN и OUT случайного узла v они обнаружили Out(v) ≈ 100 миллионов (50% узлов), In(v) ≈ 100 миллионов (50% узлов), наибольший SCC: 56 миллионов (28% узлов). Это показывает, что сеть имеет так называемую структуру «галстук-бабочка»:

Существует большое разнообразие подключений узлов веб-графа — › все веб-страницы не одинаково «важны».

Основная идея: страница тем важнее, чем больше на нее ссылок. Они считают внутренние ссылки голосами. «Голосование» (ссылка) с важной страницы стоит больше:

  • Голос каждой ссылки пропорционален важности ее исходной страницы.
  • Если на странице i с важностью ri есть исходящие ссылки di, каждая ссылка получает ri / di голосов.
  • Собственная значимость страницы j rj – это сумма голосов, проголосовавших за ее входящие ссылки.

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

Интерпретация случайного блуждания

Представьте себе случайного веб-серфера. В любой момент времени t пользователь находится на некоторой странице i. В момент времениt + 1 пользователь переходит по исходящей ссылке из i равномерно на случайный. Заканчивается на какой-то странице j, связанной с i. Процесс повторяется бесконечно. Тогда p(t) — это распределение вероятностей по страницам, это вектор, чья координата i — это вероятность того, что пользователь находится на странице i в время t.

Чтобы определить, где находится пользователь в момент времени t+1, равномерно и случайным образом перейдите по ссылке p(t+1) = M ⋅ p(t). Предположим, что случайное блуждание достигает состояния p(t+1) = M ⋅ p(t) = p(t). Тогда p(t) является стационарным распределением случайная прогулка. Наш исходный вектор рангов r удовлетворяет условию r = M ⋅ r. Итак, r — стационарное распределение случайного блуждания.

Поскольку уравнение потока r = M ⋅ r, r является собственным вектором стохастической веб-матрицы M. Но Начиная с любого вектора u, предел M(M(…(M(Mu))) представляет собой долгосрочное распределение пользователей. С помощью математики мы получаем, что предельное распределение является главным собственным вектором M — PageRank. Примечание. Если r является пределом M(M(…(M(Mu)), то r удовлетворяет уравнению r = M ⋅ r, поэтому r является собственным вектором M с собственным значением 1. Зная это, теперь мы можем эффективно найти r с помощью метода итерации Power.

Мощная итерация представляет собой простую итеративную схему:

Как решить PageRank

Дан веб-граф с n узлами, где узлы — это страницы, а ребра — гиперссылки:

Вычислите рейтинг страницы каждого узла ( …. исходящая степень узла i):

Решение PageRank ставит 3 вопроса: Сходится ли это? Сходится ли оно с тем, что мы хотим? Являются ли результаты разумными?

PageRank имеет некоторые проблемы:

  1. Некоторые страницы являются тупиковыми (нет исходящих ссылок, правая часть веб-«бабочки»): такие страницы вызывают «утечку» важности.
  2. Ловушки для пауков (все исходящие ссылки внутри группы, левая часть паутины «бабочка»): в конечном итоге ловушки для пауков поглощают всю важность.

Решение для ловушек для пауков: на каждом временном шаге у случайного пользователя есть два варианта:

  • С вероятностью β перейти по ссылке наугад.
  • С вероятностью 1-β перейти на случайную страницу.

Общие значения β находятся в диапазоне от 0,8 до 0,9. Серфер телепортируется из ловушки для пауков в течение нескольких временных шагов.

Решение для тупиков: телепорты — следуйте случайным ссылкам телепорта с общей вероятностью 1,0 из тупиков (и соответствующим образом настройте матрицу)

Почему тупики и ловушки для пауков являются проблемой и почему телепорты решают эту проблему?

  • Паучьи ловушки не проблема, но с ловушками оценки PageRank не то, что нам нужно.
  • Тупики — это проблема: матрица не является стохастической по столбцу, поэтому наши первоначальные предположения не выполняются.

Это приводит к уравнению PageRank [Brin-Page, 98]:

Эта формулировка предполагает, что M не имеет тупиков. Мы можем либо предварительно обработать матрицу M, чтобы удалить все тупики, либо явно следовать случайным ссылкам телепорта с вероятностью 1,0 из тупиков. ( d … исходящая степень узла i).

Матрица Google становится такой:

У нас есть рекурсивная проблема: r = A ⋅ r и метод Power все еще работает.

Расчет рейтинга страниц

Ключевым шагом является умножение матрицы на вектор: r = A · r. Легко, если у нас достаточно оперативной памяти для хранения каждого из них. При 1 миллиарде страниц матрица A будет иметь N 2 записей, а 10 18 — это большое число.

Но мы можем изменить уравнение PageRank

M — разреженная матрица (без тупиков): 10 ссылок на узел, приблизительно 10N записей. Итак, на каждой итерации нам нужно: вычислить r = β M · r и добавить постоянное значение (1-β)/N к каждой записи в r new. Обратите внимание, что если M содержит тупики, то ∑ r ‹ 1, и мы также должны перенормировать r, чтобы суммирует 1.

Случайный обход с перезапусками

Идея: каждый узел имеет определенное значение; важность равномерно распределяется между всеми ребрами и передается соседям. Учитывая набор QUERY_NODES, мы имитируем случайное блуждание:

  • Подойдите к случайному соседу и зафиксируйте посещение (количество посещений).
  • С вероятностью АЛЬФА перезапустить обход на одном из QUERY_NODES.
  • Узлы с наибольшим количеством посещений имеют наибольшую близость к QUERY_NODES.

Преимущества этого подхода в том, что он учитывает: множественные соединения, множественные пути, прямые и непрямые соединения, степень узла.

Первоначально опубликовано на https://elizavetalebedeva.com 31 января 2021 г.