Главная » Хабрахабр » Где и как врубиться в эмбеддинги графов

Где и как врубиться в эмбеддинги графов

Привет, Хабр!

Cразу же после разминки с открытым курсом машинного обучения, который начнётся через несколько дней. Три года назад на сайте Леонида Жукова я ткнул ссылку на курс Юре Лесковека cs224w Analysis of Networks и теперь мы будем его проходить вместе со всеми желающими в нашем уютном чате в канале #class_cs224w.

image

Покажем на примере улучшения процесса IT-рекрутинга. Вопрос: Что там начитывают?
Ответ: Современную математику.

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

План у нас такой:

  1) Что такое cs224w
  2) Шашечки или ехать
  3) Как я до всего этого докатился
  4) Зачем почитывать журнал Биоинформатика
  5) Что такое графовые эмбеддинги и откуда взялись
  6) Случайный бродяга в форме матрицы
  7) Возвращение случайного бродяги и сила связей
  8) Путь случайного бродяги и вершина в векторе
  9) Наши дни — случайный бродяга для всех и каждого
10) Как и где такие данные хранить и откуда брать
11) Чего опасаться
12) Памятка воспроизводителю

Отличие от прочих в том, что программа охватывает очень широкий спектр вопросов. Курс Юре Лесковека Analysis of Networks выделяется в плеяде образовательных продуктов факультета вычислительных наук университета Стенфорда. Призом же становится универсальный язык описания сложных систем — теория графов, разобраться с которой предлагается за десять недель. Именно междисциплинарный характер делает приключение вызовом.

image

Курс не стоит себе так, а открывает программу Mining Massive Data Sets Graduate Certificate, в которой ещё много вкусного.

Вторым в приключении идёт CS229 Machine Learning Эндрю Ына, который рекламировать излишне.

Далее следует CS246 Mining Massive Data Sets Юре Лесковека, в котором желающим предлагается упороться MapReduce и Spark-ом.

Завершает банкет CS276 Information Retrieval and Web Search Криса Маннинга.

Опять в гостях у Юре. В качестве бонуса предлагается CS246H Mining Massive Data Sets: Hadoop Labs специально для тех, кому было мало.

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

Когда-то давно мой руководитель и ментор, на тот момент — СТО в украинском Nestlé, втолковывал мне, молодому и амбициозному, порывавшемуся получить МВА чтобы стать ещё звездатее, истину о том, что на рынке труда покупают и продают опыт и знания, а не дипломы и результаты тестов.

Описанную выше специализацию можно пройти онлайн за символические $18,900.

Для получения сертификата требуется пройти все курсы с оценкой не ниже В (3. В среднем, приключение занимает 1-2 года, но не более 3. 0).

Есть и другой путь.

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

В этот сезон, после окончания Открытого Курса Машинного Обучения на Хабре, который полезно пройти в качестве разминки, мы устроим забег в выделенном канале #class_cs224w чата ods.ai.

Рекомендуется обладать следующим набором навыков:

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

Руководил проектами внедрения SAP. Жил себе, не тужил. Можно сказать, почти никого не трогал. Временами — выступал в роли играющего тренера по своей основной специализации — и гайки CRM крутил. В какой-то момент решил специализироваться в области трансформации бизнеса (или проведении организационных изменений). Самообразованием занимался. Знание откуда и куда меняться — здорово помогает. Задача анализа организаций до и после перемен — важная часть этой работы. Несколько лет уделил изучению "мягких" методологий исследования организаций, да всё никак удовлетвориться не мог — вопросом: "А кто кого заборет: главнокоммивояжер главносчетовода, или же завскладом всех сильнее?" задаюсь уж несколько лет кряду. Понимание связей между людьми — весомый фактор успеха. Всё ищу способ наверняка измерить.

Переломным стал 2014 год, когда я отказался от грёз о МВА и в качестве второго высшего выбрал (тут звучит барабанная дробь) снова статистику и управление информацией в новом лиссабонском университете (первое — и ныне здравствующая кафедра телекоммуникаций уже несуществующего факультета авиационных и космических систем киевского политеха + кафедра связи на военке).

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

Поначалу хватало классики.

Чтобы разобраться с эмбеддингами (и перепилить под свои задачи работы Маринки Житник), пришлось вникать в глубокое обучение, в чём здорово помог курс о Deep Learning на пальцах. Захотелось большего. Учитывая то, с какой скоростью группа Лесковека создаёт новое знание, для того, чтобы решать управленческие задачи автоматически, достаточно просто следить за их работой.

Кого с кем в одну лодку садить не стоит — один из насущных вопросов. Командообразование — задача непростая. И местность незнакомая. Особенно, когда лица новые. И в пути обязательно тесное взаимодействие как в лодках, так и между ними. А вести к далёким берегам нужно не одну лодку, но целую флотилию. За всю свою рабочую деятельность, ни разу никого не нанимал — всегда выдавали команду. Обычные будни внедрения SAP, когда Заказчику нужно поставить сконфигурированную под его специфику систему из кучи модулей, и план проекта состоит из тысячи строк. Как-то так. Ты — руководитель проектов, на тебе полномочия, и крутись. Выкручивался.

Пример из жизни:

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

Нашёл.  
Природная лень требовала — найди способ автоматизации. Делюсь.

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

С идеями Ицхака Адизеса я знаком уже лет десять и во многом согласен.

Известны примеры того, как успешные руководители, перейдя из одной отрасли, проваливались в другой. Личности сотрудников — как витамины — влияют на успех в определенных условиях. Например, Марисса Майер, поднявшая поиск Google, уронила Yahoo. Бывает и хуже. Среда и способы взаимодействия в ней — важный фактор. Уоррен Баффет говорит, что навряд-ли добился бы успеха, родившись в Бангладеш.

Хорошо бы предсказывать осложнения до экспериментов на живом, верно?

Задача предсказания побочных эффектов при совместном применении препаратов математически близка к управленческой. В эту канву ложится очередное исследование Маринки Житник, опубликованное в журнале Биоинформатика. Рассмотрим её детальнее. Всё благодаря универсальности языка графов.

image

Графовая свёрточная сеть Decagon — инструмент предсказания связей в мультимодальных сетях.

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

Всего — 964 различных вида побочных эффектов (обозначенных рёбрами типа ri, i = 1, ..., 964). На рисунке приведен пример графа побочных эффектов, полученных из данных генома и популяции. Дополнительная информация в модели представлена в виде векторов свойств протеинов и препаратов.

image

Мы видим, что Ciprofloxacin (узел C), принятый одновременно с Doxycycline (узел D) или Simvastatin (узел S), повышают риск побочного эффекта, выражающегося в замедлении сердечного ритма (побочный эффект типа r2), а комбинация с Mupirocin (M) — повышает риск кровотечений желудочно-кишечного тракта (побочный эффект типа r1). Для препарата Ciprofloxacin (узел C) подсвеченные соседи по графу отражают воздействия на четыре белка и три других препарата.

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

Архитектура графовой свёрточной нейронной сети Decagon:

image

Модель состоит из двух частей:

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

Подробнее можно узнать на сайте проекта или ниже по тексту.

Здорово, а как это к командообразованию прикрутить?

image

Как-то так.

Правда, копать доведётся интенсивно — теория графов активно развивается. Вот для того, чтобы чувствовать себя комфортно в области исследований, подобных описанному, и стоит копнуть гранит науки. На то оно и остриё прогресса — там мало кому комфортно бывает.

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

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

Сформулируем задачу предсказания связей:

Рассмотрим ненаправленный граф $inline$\beginG(V,E)\end{align*}$inline$, где
$inline$\begin{align*}V\end{align*}$inline$ — множество вершин $inline$\begin{align*}v\end{align*}$inline$,
$inline$\begin{align*}E\end{align*}$inline$ — множество рёбер $inline$\begin{align*}e(u, v)\end{align*}$inline$, соединяющих вершины $inline$\begin{align*}u\end{align*}$inline$ и $inline$\begin{align*}v\end{align*}$inline$.

Определим множество всех возможных рёбер $inline$E^{\diamond}$inline$, его мощность
$inline$\begin{align*} |E^{\diamond}| &= \frac{|V|*(|V| - 1)}{2}\\ \end{align*}$inline$, где
$inline$\begin{align*}|V| = n\end{align*}$inline$, — количество вершин.

Очевидно, что множество несуществующих рёбер можно выразить как $inline$\begin{align*}\overline{E} = E^{\diamond} - E\end{align*}$inline$.

Мы предполагаем, что в множестве $inline$\begin{align*}\overline{E}\end{align*}$inline$ есть пропущенные связи, либо связи, которые появятся в будущем, и хотим их найти.

Решение сводится к определению функции $inline$\begin{align*}D(u, v)\end{align*}$inline$ дистанции между вершинами графа, позволяющей по структуре графа $inline$\begin{align*}G(t_0, t_0^\star)\end{align*}$inline$, заданной на промежутке времени $inline$\begin{align*}(t_0, t_0^\star)\end{align*}$inline$, предсказать появление рёбер $inline$\begin{align*}G(t_1, t_1^\star)\end{align*}$inline$ в интервале $inline$\begin{align*}(t_1, t_1^\star)\end{align*}$inline$.

Уже в 2003 вышла статья Джона Клейнберга с обзором актуальных методов решения задачи прогнозирования связей в социальной сети.  
Одна из первых публикаций, которая предлагает перейти от кластеризации к задаче предсказания связей в контексте изучения совместной экспрессии генов, появилась в журнале (как нетрудно догадаться) Биоинформатика в 2000 году. Его книга "Networks, Crowds, and Markets: Reasoning About a Highly Connected World" — учебник, который рекомендуется читать во время прохождения курса cs224w, большинство глав — указаны в разделе обязательной к прочтению литературы.

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

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

Дадим определение:

Вершина $inline$u$inline$ является соседом по графу для вершины $inline$v$inline$, если ребро $inline$e(u, v) \in E$inline$.

Обозначим $inline$\Gamma(u)$inline$ множество соседей вершины $inline$u$inline$,

тогда дистанция между вершинами $inline$u$inline$ и $inline$v$inline$ может быть записана как

$inline$D_{CN}(u, v) =\Gamma(u) \cap \Gamma(v)$inline$.

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

Более продвинутые эвристики — коэффициент Жаккара $inline$D_J(u, v) =\frac{\Gamma(u) \cap \Gamma(v)}{\Gamma(u) \cup \Gamma(v)}$inline$ (которому уже тогда было сто лет) и недавно (на то время) предложенная дистанция Адамик/Адар $inline$D_{AA}(u, v) =\sum_{x \in \Gamma(u) \cap \Gamma(v)}\frac{1}{\log|\Gamma(x)|}$inline$ развивают идею путем нехитрых преобразований.

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

Оценим качество прогноза:
 

  • Для каждой пары вершин $inline$(u, v)$inline$ каждого несуществующего ребра $inline$e(u, v)\in\overline{E}$inline$ вычислим дистанцию $inline$D(u, v)$inline$ на графе $inline$G(t_0, t_0^\star)$inline$.
  • Отсортируем пары $inline$(u, v)$inline$ по убыванию дистанции $inline$D(u, v)$inline$.
  • Отберём $inline$m$inline$ пар с наибольшими значениями — это наш прогноз.
  • Посмотрим, сколько из предсказанных рёбер появились в $inline$G(t_1, t_1^\star)$inline$.

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

Обобщённо, графовые эмбеддинги — это способ представления графов компактно для задач машинного обучения с помощью функции преобразования $inline$\begin{align*}\phi:G(V,E)\longmapsto\mathbb{R}^d\end{align*}$inline$.

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

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

Дадим определение:

Матрица смежности графа $inline$G$inline$ с конечным числом вершин $inline$n$inline$ (пронумерованных числами от 1 до $inline$n$inline$) — это квадратная матрица $inline$A$inline$ размера $inline$n \times n$inline$, в которой значение элемента $inline$a_{ij}$inline$ равно весу $inline$w_{ij}$inline$ ребра $inline$e(i,j)$inline$.

Примечание: здесь мы намеренно отойдём от использовавшихся ранее индикаторов вершин $inline$u,v$inline$ и будем использовать привычные для линейной алгебры и вообще в работе с матрицами обозначения $inline$i,j$inline$.

Проиллюстрируем рассмотренные концепции:

Пусть $inline$G$inline$ — граф из четырёх вершин $inline$\{A,B,C,D\}$inline$, соединенных рёбрами.

$inline$\forall e(i,j) \in E, \exists e(j,i) \in E \land w_{ij} = w_{ji}$inline$. С целью упрощения построений, примем допущение, что рёбра нашего графа — двунаправленные, т.е.

$inline$ $inline$e(A,B), w_{AB} = 1;\\ e(B,C), w_{BC} = 2;\\ e(A,C), w_{AC} = 3;\\ e(B,C), w_{BC} = 1.

Изобразим множества рёбер: $inline$E$inline$ — синим, а $inline$\overline{E}$inline$ — зелёным цветом.

image

$inline$\begin{align*}A = \left[ \begin{matrix} 0 & 1 & 3 & 0\\ 1 &0 & 2 & 1\\ 3 & 2 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} \right]\end{align*}$inline$

Чтобы их продемонстрировать, заглянем в работу Сергея Брина и Ларри Пейджа, и разберёмся с тем, как работает PageRank — алгоритм ранжирования вершин графа, до сих пор являющийся важной частью поиска Google.  
Запись графа в матричной форме открывает интересные возможности.

Страница считается хорошей, если её ценят (ссылаются на неё) другие хорошие страницы. PageRank — придуман, чтобы искать самые лучшие страницы в интернете. Чем больше страниц содержат ссылки на неё, и чем выше их рейтинг, тем выше PageRank для данной страницы.

Рассмотрим интерпретацию работы метода с помощью цепей Маркова.

Дадим определение:

Степень вершины (degree) — мощность множества соседей:
$inline$d_i = |\Gamma(i)|$inline$,

Для нашего примера они эквивалентны. Различают in-degree и out-degree.

\end{matrix} \right.\end{align*}$inline$ Построим взвешенную матрицу смежности, руководствуясь правилом:
$inline$\begin{align*}M_{ij} = \left\{ \begin{matrix} \frac{1}{d_j} & \forall i,j \iff i \in \Gamma(j), \\ 0 & \forall i,j \iff i \notin \Gamma(j).

$inline$\begin{align*}M = \left[ \begin{matrix} 0 & \frac{1}{3} & \frac{1}{2} & 0 \\ \frac{1}{2} &0 & \frac{1}{2} & 1 \\ \frac{1}{2} & \frac{1}{3} & 0 & 0\\ 0 & \frac{1}{3} & 0& 0 \end{matrix} \right]\end{align*}$inline$

$inline$M$inline$ — "столбцовая стохастическая матрица"). Обратите внимание, что столбцы $inline$M$inline$ должны в сумме давать 1 (т.е. Элементы каждого столбца задают вероятность перехода из вершины $inline$j$inline$ в одну из соседних вершин по графу $inline$i \in \Gamma(j)$inline$ .

Тогда мы можем выразить PageRank для её соседа $inline$j$inline$ как  
Пусть $inline$r_i$inline$ будет значением PageRank для вершины $inline$i$inline$, у которой $inline$d_i$inline$ исходящих рёбер.

$$display$$r_j = \sum_{i \to j}\frac{r_i}{d_i}$$display$$

его PageRank), и обратно пропорционален размеру окружения соседа. Таким образом, каждый из соседей $inline$i$inline$ вершины $inline$j$inline$ вносит вклад в её PageRank, и его размер прямо пропорционален авторитету соседа (т.е.

Мы можем и будем хранить значения PageRank для всех вершин в векторе $inline$\begin{align*}r = [r_1, r_2, ..., r_n]^T \end{align*}$inline$ — это позволит записать уравнение компактно в виде скалярного произведения:

$$display$$r = Mr$$display$$

В любой момент времени $inline$t$inline$ он находится на странице $inline$i$inline$ и в момент $inline$t+1$inline$ переходит по одной из ссылок на одну из соседних страниц $inline$j \in \Gamma(i)$inline$, выбирая её случайным образом, причём все переходы — равновероятны. Представьте веб-сёрфера, который проводит бесконечное количество времени в интернете (что недалеко от реальности).

$inline$p(t)$inline$ — распределение вероятностей между страницами, поэтому сумма элементов равна 1. Обозначим $inline$p(t)$inline$ вектор с вероятностями того, что сёрфер находится на странице $inline$i$inline$ в момент времени $inline$t$inline$.

Поэтому, для каждой вершины $inline$i$inline$ Вспомним, что $inline$M_{ij}$inline$ — это вероятность перехода от вершины $inline$j$inline$ к вершине $inline$i$inline$ с учётом того, что сёрфер находится на вершине $inline$j$inline$ и $inline$p_j(t)$inline$ — вероятность того, что он находится на странице $inline$j$inline$ в момент $inline$t$inline$.

. $$display$$p_i(t+1) = M_{i1}p_1(t) + M_{i2}p_2 + . + M_{in}p_n(t)$$display$$ .

и это значит, что

$$display$$p(t + 1) = Mp(t)$$display$$

Вспомним, что уравнение для PageRank в векторной форме $inline$r = Mr$inline$. Если случайные блуждания когда-либо достигнут состояния, в котором $inline$p(t + 1) = p(t)$inline$, тогда $inline$p(t)$inline$ — стационарное распределение. Вывод — вектор $inline$r$inline$ значений PageRank — это стационарное распределение случайного бродяги!

Идея в том, что мы инициализируем вектор $inline$r^{(t0)} = [1/n, 1/n, ..., 1/n]^T $inline$ одинаковыми значениями и последовательно вычисляем $inline$r^{(t+1)} = Mr^{(t)}$inline$ для каждого $inline$t$inline$ до тех пор, пока значения не сойдутся, т.е. На практике для $inline$r$inline$ уравнение PageRank зачастую решается степенным методом. (Обратите внимание, что $inline$||x||_1 = \sum_{k} |x_k|$inline$ — это $inline$L_1$inline$ норма, или дистанция Минковского). $inline$||r^{(t+1)} - r^{(t)}||_1 < \epsilon$inline$, где $inline$\epsilon$inline$ — допустимая погрешность. Как правило, хватает 20-30 итераций. Тогда значения вектора $inline$r^{(t+1)}$inline$ и будут оценкой Page Rank для вершин.

Здесь мемасик про решение задач случайным перебором приобретает новые оттенки.

image

В описанном "ванильном" виде метод чувствителен к двум проблемам:

  • Т.н. "паучьи гнёзда" — вершины, ссылающиеся на себя — приводит к тому, что PageRank в них втекает. Весь. И никому больше не достаётся.
  • Тупики — вершины с одними только входящими рёбрами — через них PageRank утекает из системы. И заканчивается в какой-то момент. Вектор $inline$r$inline$ заполняется нулями.

Брин с Пейджем решили проблему 20 лет назад, выдав бродяге дробовик телепорт!

Обыкновенно значение $inline$1 - \beta \approx 0. Пусть наш веб-сёрфер с вероятностью $inline$\beta $inline$ выбирает исходящую ссылку, а с вероятностью $inline$1 - \beta $inline$ — телепортируется на случайно выбранную страницу. наш веб-сёрфер делает 5-7 шагов между телепортациями. 15 $inline$, т.е. Уравнение для PageRank принимает вид: Из тупика — всегда телепортируется.

$$display$$r_j = \sum_{i \to j}\beta\frac{r_i}{d_i} + (1-\beta)\frac{1}{n}$$display$$

(данная формулировка предполагает, что в графе нет тупиков)

Подобно нашей предыдущей матрице $inline$M $inline$, мы можем определить новую матрицу

$$display$$ M^{\star} = \beta M + (1-\beta) [1/n]_{n×n} $$display$$

Остаётся решить уравнение $inline$ r = M^{\star}r $inline$ аналогичным способом. вероятности переходов. Ради сохранения интриги, просто скажу, что обобщённый алгоритм описан на слайдах 37-38 в 14-й лекции курса cs224w 2017 года, в которой Юре прекрасно раскрывает все детали и показывает, как метод используется у них в Pinterest (он там главный по науке).

Какой практический толк от всех этих матричных операций? Вернёмся к делам менеджерским.

Обозначим несколько задач руководителя проекта:
 

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

Так, например, мы выловили г-на Барака Обаму из переписки, которой любезно поделилась г-жа Хиллари Клинтон в то время как прочие методы не уделили ему должного внимания.  
Первая задача решается построением графа связей и применением классического PageRank.

Оставшиеся две — потребуют модификации алгоритма.

В реальном мире это заняло восемь лет.

А что если мы ограничим множество возможных перемещений неслучайной выборкой по какому-нибудь критерию? Напомним, что ранее наш бродяга с телепортом перемещался в случайно выбранную вершину. Так и сделали в 2006 году коллеги Юре по аспирантуре.

Усовершенствуем наш пример:

Допустим, мы что-то знаем о вершинах рассматриваемого графа $inline$G $inline$, какие-то признаки.

Для каждой вершины $inline$i $inline$ зададим вектор из $inline$k $inline$ свойств $inline$f^{(i)} = [f_1, f_2, ..., f_k]^T $inline$.

image

Пусть первое из них, $inline$f_1 $inline$ будет, скажем, любимый цвет глаз.

В какой-то момент возникает потребность добавить ещё одного игрока.  
Предположим, что читатель дослужился до высоких рангов и у него уже есть команда, которая трудится над созданием нового революционного продукта. Для того, чтобы облегчить жизнь нашему IT-рекрутеру в формировании списка тех, кого мы пригласим собеседоваться с ключевыми участниками команды (их время тоже дорого стоит) — будем решать её алгоритмически. Допустим, что пул кандидатов — достаточно обширный (например, у нас дядя работает на фабрике датасаентистов).

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

Мы знаем, что предыдущее успешное сотрудничество — залог успеха сотрудничества будущего.

Поэтому построим граф связей датасаентистов из истории командных выступлений в соревнованиях на какой-нибудь площадке, вроде Kaggle или Hackerrank, которая позволяет участникам не только мериться математикой, но и общаться на форумах, ставить лайки кернелам и всё такое (предположим, что читатель уже сделал это).

Дадим определение:

Персонализированной выборкой $inline$S_k(x) $inline$ по значению $inline$x $inline$ критерия $inline$ k $inline$, назовём подмножество вершин графа $inline$G$inline$:

$inline$\forall i \in V, i \in S_k(x) \iff f^{(i)}_{k} = x$inline$

 
Остаётся построить персонализированную матрицу вероятности переходов:

\end{matrix} \right.\end{align*}$inline$ $inline$\begin{align*}M^{p}_{ij} = \left\{ \begin{matrix} \beta M_{ij} + \frac{1-\beta}{|S_k(x)|} & \forall i,j \iff i \in S_k(x), \\ \beta M_{ij} & \forall i,j \iff i \notin S_k(x).

В векторе $inline$\begin{align*} r \end{align*}$inline$ содержатся значения персонализированного PageRank по отношению к нашей выборке — наиболее относящиеся к ней вершины. И решить уравнение $inline$\begin{align*} r = M^{p} r \end{align*}$inline$ относительно $inline$\begin{align*} r \end{align*}$inline$, как мы это уже не раз делали. Для решения вопроса с поиском потенциальных кандидатов, отсортируем содержимое $inline$\begin{align*} r \end{align*}$inline$ по убыванию значений — нас интересует вершина списка.

Именно этот метод отвечает за подготовку 80% рекомендаций в Pinterest.

В результате мы получаем меру близости для каждой вершины графа по отношению к той единственной. Частный случай, когда $inline$\begin{align*}|S_k(x)| = 1\end{align*}$inline$, называется Random Walks with Restarts — бродяги возвращаются и возвращаются в одну интересующую нас вершину. И это решает задачу предсказания связей лучше, чем позволяет дистанция Адамик/Адар.

Добавим ещё улучшений:

Вспомним, что рёбра $inline$\begin{align*} e(i,j) \in E \in G \end{align*}$inline$ нашего графа имеют веса $inline$\begin{align*}w_{ji}\end{align*}$inline$.

Это позволит задать взвешенную матрицу $inline$\begin{align*}M^w\end{align*}$inline$ вероятности переходов:

\end{matrix} \right.\end{align*}$inline$ $inline$\begin{align*}M^{w}_{ij} = \left\{ \begin{matrix} \frac{w_{ij}}{\sum_{j}w_{ij}} & \forall i,j \iff e(i,j) \in E, \\ 0 & \forall i,j \iff e(i,j) \notin E.

Бродяга будет совершать переходы по-прежнему случайно, но уже не равновероятно!

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

Нужно было построить систему рекомендации друзей из друзей друзей, да так, чтобы максимизировать создание новых связей. Этим же озадачились в Facebook в 2011. Как-то силу дружбы в интернете померять. И первым шагом было создание взвешенного графа связей между пользователями из информации в их профилях и истории взаимодействия (лайки, сообщения, совместные фото и прочее).

$$display$$ w_{ij} = f^w(i,j) = e^{- \sum_{z}{\xi_z x_{ij}[z]}} ,$$display$$

$inline$\begin{align*}x_{ij} = f^{(i)} \cup f^{(j)} \cup f^{e(ij)} \end{align*}$inline$, а $inline$\begin{align*}\xi \end{align*}$inline$ — вектор весов, которые предстоит выучить из данных. где $inline$\begin{align*}x_{ij} \end{align*}$inline$ — вектор свойств вершин и соединяющего их ребра, т.е.

Здесь подготовленный читатель узнает линейную модель, а неподготовленный — задумается о том, что стоит пройти открытый курс машинного обучения, чтобы разобраться с градиентным спуском, с помощью которого мы и выучим значения весов в векторе $inline$x_{ij} $inline$ — они покажут, как влияют лайки и сообщения на дружбу в интернете.

Зачем нам это всё надо?

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

Мы наблюдаем за развитием сотрудничества (совместное участие в соревнованиях) в группе условных датасаентистов на интервале $inline$\begin{align*}(t_0, t_0^\star)\end{align*}$inline$ (например, один календарный месяц) и хотим предсказать командообразование в интервале $inline$\begin{align*}(t_1, t_1^\star)\end{align*}$inline$ (другой месяц). Напомним условия нашего упражнения. Всю собранную информацию храним в матрице $inline$X^{\star} \in \mathbb{R}^{(2k+l)\times|E|} $inline$ (её колонки — вектора $inline$x_{ij} $inline$, $inline$k, l$inline$ — размерности векторов свойств вершин и рёбер $inline$f^{(i)}, f^{e(ij)}$inline$, соответственно) и графе $inline$\begin{align*}G \end{align*}$inline$ для двух интервалов времени. Кроме участия в соревнованиях, мы отслеживаем общение на форумах, лайки кернелов, и ещё чего заблагорассудится.

Подготовим данные для машинного обучения.

Для каждой вершины $inline$\begin{align*} i\end{align*}$inline$:

1) определим множество друзей друзей:

$$display$$\Gamma^{fof}(i) = \bigcup_{j \in \Gamma(i)} \Gamma(j) - \Gamma(i)$$display$$

2) и построим суб-графы $inline$\begin{align*} G^{fof}(i)\end{align*}$inline$ связей с друзьями и друзьями друзей, $inline$\begin{align*} \forall e(x,y) \in E, e(x, y) \in G^{fof}(i) \iff x, y \in \Gamma^{fof}(i) \cup \Gamma(i) \end{align*}$inline$

3) выделим множество вершин, $inline$\begin{align*} D_i: \{d_1, ..., d_k \}\end{align*}$inline$, с которыми образовались связи — это наши позитивные примеры для обучения,

4) все неслучившиеся связи из множества $inline$\begin{align*} \overline{D_i} = \Gamma^{fof}(i) - D_i\end{align*}$inline$ — это наши негативные примеры для обучения.

image align=center

Наша задача — подобрать такой вектор весов $inline$\begin{align*} \xi \end{align*}$inline$, при котором позитивные примеры из множества $inline$\begin{align*} D_i\end{align*}$inline$ получат более высокое значение Personalized PageRank относительно $inline$\begin{align*} i\end{align*}$inline$, чем негативные примеры.

Для этого зададим функцию потерь, которую будем минимизировать:

$$display$$ L = \sum_{i} \sum_{d \in D_i, \overline{d} \in \overline{D_i} } h(r_{\overline{d}} - r_{d}) + \lambda||\xi||^2,$$display$$

где $inline$h(x) = 0\iff x <0; h(x) = x^2 \iff x\geqslant 0;$inline$ — штраф за нарушение условия, $inline$\lambda$inline$ — сила $inline$L_2$inline$ регуляризации весов $inline$\xi$inline$, $inline$r$inline$ — вектор с решениями уравнения $inline$r = M^wr$inline$ относительно $inline$r$inline$ для суб-графа друзей друзей отдельно взятой вершины $inline$i$inline$.

Подробности — в 17-й лекции редакции 2014 года, слайды 9-27. Забавная деталь — градиент этой функции вычисляется так же, как и PageRank, степенным методом.

Вот так выглядело острие прогресса в момент моего первого знакомства с курсом cs224w.

А потом наступило торжество лени!

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

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

image

 
Здесь мы знакомимся с графовыми эмбеддингами в современном понимании этого термина.

Формально, мы хотим:

1) Определить энкодер (функцию соответствия ENC, которая задаёт преобразование узла $inline$u$inline$ в вектор $inline$z_u$inline$);
2) Определить функцию подобия узлов (меру близости в графе, который мы будем подавать на вход энкодера);
3) Оптимизировать параметры энкодера таким образом, что:

$$display$$similarity(u,v) \approx z_{v}^{T} z_v$$display$$

image

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

Здорово, а как её определить, эту близость в графе?

Функция потерь для такого случая примет вид: Например, будем считать, что вес ребра — хорошая мера близости и её можно приближенно считать равной скалярному произведению для эмбеддингов двух узлов.

$$display$$L = \sum_{(u,v) \in V \times V} || z_{u}^{T}z_v - A_{u,v}||^2,$$display$$

остаётся найти (например, градиентным спуском) матрицу $inline$Z \in \mathbb{R}^{d \times|V|}$inline$, которая минимизирует $inline$L$inline$.

Альтернативный подход — определить окружение $inline$N(v)$inline$ для вершины шире, чем множество соседей.

image

Первый проект, использовавший этот подход — DeepWalk. В этом нам помогут блуждания по графу. Суть метода заключается в том, что мы будем запускать бродягу гулять по графу случайным образом из каждой вершины $inline$v$inline$, и скармливать короткие последовательности фиксированной длины посещённых за время его прогулки вершин в word2vec.

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

То, откуда мы пришли в вершину — никак не влияет на выбор следующего шага. В DeepWalk бродяга реализует марковский процесс первого порядка — из каждой вершины мы переходим в соседние, согласно вероятностям из взвешенной матрицы смежности $inline$M$inline$ (либо её производных, вроде $inline$M^w$inline$).

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

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

— Джон фон Нейман

 
Здесь остаётся посоветовать стремящимся к праведной жизни найти в продаже альбом «Black and White Noise» — в 1995 Джордж Марсаглия записал на компакт-диск массив байтов, полученных оцифровкой шума с усилителя во время проигрывания рэпчика и назвал его соответственно.

Рассмотрим, как это работает. Развитием метода является node2vec, в котором реализован марковский процесс второго порядка — мы смотрим, откуда пришли, и это влияет на вероятности выбора направления следующего шага.

После каждого шага, мы можем выполнить одно из трёх возможных действий: 1) вернуться ближе к $inline$u$inline$; 2) исследовать вершины на той же дистанции от $inline$u$inline$, что и та, в которой сейчас находимся; 3) удалиться от $inline$u$inline$. Допустим, мы запускаем бродягу гулять по графу из вершины $inline$u$inline$, ей смежна вершина $inline$s_1$inline$, вершины $inline$s_2$inline$ и $inline$w$inline$ — в двух шагах, а $inline$s_3$inline$ — в трёх.

image

Реализуется эта стратегия с помощью двух параметров:
$inline$p$inline$ — задаёт вероятность вернуться в предыдущую вершину;
$inline$q$inline$ — задаёт баланс между поиском вширь и поиском вглубь.

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

Для ребра $inline$e(w,s_1)$inline$ мы назначим вес (ненормированную вероятность) $inline$1/p$inline$. Допустим, мы находимся в вершине $inline$w$inline$ и пришли в неё из вершины $inline$s_1$inline$. Для уводящего вдаль от $inline$u$inline$ ребра $inline$e(w,s_3)$inline$ — $inline$1/q$inline$. Для ребра $inline$e(w,s_2)$inline$ — $inline$1$inline$ (как и для всех прочих рёбер, ведущих в вершины, равноудалённые от $inline$u$inline$).

Затем — нормируем вероятности (чтобы сумма была равна 1), и совершим следующий шаг.

Подбор стратегий для бродяги, оптимальных для решения конкретных задач — область активного исследования. Нас интересует последовательность посещённых вершин — её мы и будем отправлять в word2vec (разобраться с ним поможет вот эта статья, либо лекция 8 из курс о Deep Learning на пальцах). Например, node2vec, с которым мы ознакомились, — чемпион в классификации вершин (например — определении токсичности препаратов, или пола/возраста/расы участника социальной сети).

Оптимизировать будем вероятность появления вершин на пути бродяги, функция потерь:

$$display$$L = \sum_{u \in V} \sum_{v \in N_{R}(u)} -log(P(v|z_u))$$display$$

в её явной форме — достаточно дорогое по вычислительной нагрузке удовольствие

$$display$$L = \sum_{u \in V} \sum_{v \in N_{R}(u)} -log(\frac{e^{z_{u}^{T}z_v}}{\sum_{n \in V} e^{z_{u}^{T}z_n}}),$$display$$

которое по счастливой случайности решается негативным семплингом, т.к.

$$display$$ log(\frac{e^{z_{u}^{T}z_v}}{\sum_{n \in V} e^{z_{u}^{T}z_n}}) \approx log(\sigma (z_{u}^{T}z_v)) - \sum_{i=1}^{k} log(\sigma (z_{u}^{T}z_{n_i})) ,\\где\,\,\, n_i \sim P_V, \sigma(x) = \frac{1}{1 + e^{-x}}.$$display$$

Дело в шляпе! Итак, мы разобрались с тем, как получить векторное представление вершин.

image

Как готовить эмбеддинги для рёбер:

Таким оператором может выступать: Нам нужно определить оператор, позволяющий для любой пары вершин $inline$u$inline$ и $inline$v$inline$ построить векторное представление $inline$z_{(u,v)} = g(z_u, z_v)$inline$, независимо от того, связаны ли они на графе.

a) среднее арифметическое: $inline$[z_u \oplus z_v]_i = \frac{z_u(i) + z_v(i)}{2}$inline$;
b) произведение Адамара: $inline$[z_u \odot z_v]_i =z_u(i) * z_v(i)$inline$;
c) взвешенная L1 норма: $inline$||z_u - z_v||_{\overline{1}i} =|z_u(i) - z_v(i)|$inline$;
d) взвешенная L2 норма: $inline$||z_u - z_v||_{\overline{2}i} =|z_u(i) - z_v(i)|^2$inline$.

В экспериментах наиболее устойчиво себя ведёт произведение Адамара.

На всякий случай, вспомним Free Lunch Theorem:

Ни один алгоритм не является универсальным — стоит проверить несколько методов.

Изначально был разработан для моделирования связей между белками в разных органах (а они ведут себя по-разному в зависимости от местоположения).  
Развитием node2vec является проект OhmNet, который позволяет объединить несколько графов в иерархию и построить эмбеддинги вершин для разных уровней иерархии.

image

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

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

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

На выходе мы получаем таблицу соответствия вершина-вектор. Теперь — о недостатках методов, построенных на неглубоких энкодерах — внутри word2vec всего один скрытый слой, веса которого и кодируют эмбеддинги. Всем подобным подходам свойственны следующие ограничения:

  • Каждая вершина кодируется уникальным вектором и модель не предполагает совместного использования параметров;
  • Мы можем кодировать только те вершины, которые модель видела во время обучения — для новых вершин ничего сделать не сможем (кроме как переобучить энкодер заново);
  • Никак не учитываются вектора свойств вершин.

Мы подобрались к Decagon! От обозначенных недостатков свободны графовые свёрточные сети.

А там забавно. Про бродяг мне ещё повезло написать первый магистерский диплом и защитить его в далёком 2003, а вот с глубоким обучением пришлось пройти классическим путём, чтобы разобраться с тем, что там под капотом.

Для начала посмотрим, почему стандартные методы глубокого обучения — не подходят графам.

Графы — это вам не котики!

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

Нетрудно видеть, что мы можем пронумеровать вершины иначе, например $inline$\{1,3,2,4\}$inline$, или $inline$\{4,1,3,2\}$inline$ — всякий раз получая новую матрицу смежности одного и того же графа. В нашем игрушечном графе $inline$G$inline$, состоящем из вершин $inline$\{A,B,C, D\}$inline$, для построения матрицы смежности $inline$A$inline$, мы предположили сквозную нумерацию $inline$\{1,2,3,4\}$inline$.

\end{align*}$inline$ $inline$\begin{align*}A = \left[ \begin{matrix} 0 & 1 & 3 & 0\\ 1 &0 & 2 & 1\\ 3 & 2 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} \right],\, A^{\{1,3,2,4\}} = \left[ \begin{matrix} 0 & 3 & 1 & 0\\ 3 & 0 & 2 & 0\\ 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix} \right],\, A^{\{4,1,3,2\}} = \left[ \begin{matrix} 0 & 1 & 2 & 1\\ 1 & 0 & 0 & 0\\ 2 & 0 & 0 & 3 \\ 1 & 0 & 3 & 0 \end{matrix} \right].

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

image

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

Решение — будем строить новые архитектуры, вдохновляясь структурой графов.

image

Для этого воспользуемся простой двухшаговой стратегией:

  1. Для каждой вершины построим вычислительный граф с помощью бродяги;
  2. Соберём и трансформируем информацию о соседях.

Вычислительный граф может быть произвольной глубины. Напомним, что свойства вершин мы храним в векторах $inline$f^{(u)}$inline$ — столбцах матрицы $inline$X \in \mathbb{R}^{k \times |V|} $inline$ и наша задача — для каждой вершины $inline$u$inline$ собрать свойства соседних вершин $inline$f^{(v\in N(u))}$inline$, чтобы получить вектора эмбеддингов $inline$z_{u}$inline$. Рассмотрим вариант с двумя слоями.

image

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

А что там в коробках?

В простом случае — слой нейронов и нелинейность:

$$display$$ h^0_v = x_v (=f^{(v)}); \\ h^k_v = \sigma (W_k \sum_{u \in N(v)} \frac{h^{k-1}_v}{|N(v)|} + B_k h^{k-1}_v), \forall k \in \{1, ..., K\} ;\\ z_v = h^K_v, $$display$$

где $inline$W_k $inline$ и $inline$B_k $inline$ — веса модели, которые мы выучим градиентным спуском, применяя одну из рассмотренных функций потерь, а $inline$\sigma $inline$ — нелинейность, например RELU: $inline$\sigma(x) = max(0,x) $inline$.

И здесь мы оказываемся на перепутье — в зависимости от стоящей задачи, можем:

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

Для задачи бинарной классификации функция потерь примет вид:

$$display$$L = \sum_{v \in V} y_v log(\sigma(z_v^T\theta)) + (1-y_v)log(1-\sigma(z_v^T\theta)),$$display$$

где $inline$y_v $inline$ — класс вершины $inline$v $inline$, $inline$\theta $inline$ — вектор весов, а $inline$\sigma $inline$ — нелинейность, например сигмоида: $inline$\sigma(x) = \frac{1}{1 + e^{-x}} $inline$.

Подготовленный читатель здесь узнает кросс-энтропию и логистическую регрессию, а неподготовленный — задумается о том, что стоит пройти открытый курс машинного обучения, чтобы чувствовать себя комфортно с задачей классификации, простыми, и более продвинутыми алгоритмами для её решения (включая градиентный бустинг).

А мы двинемся дальше и рассмотрим принцип работы GraphSAGE — предвестника Decagon.

image

Для каждой вершины $inline$v $inline$ мы будем аггрегировать информацию от соседей $inline$u \in N(v) $inline$, и её самой.

$$display$$h^k_v = \sigma([W_k \cdot AGG(\{ h^{k-1}_u, \forall u \in N(v) \} ), B_k h^{k-1}_v]),$$display$$

где $inline$AGG $inline$ — обобщённое обозначение функции аггрегации — главное — дифферинцируемой.

Усреднение: возьмём взвешенное среднее от соседей

$$display$$AGG = \sum_{u \in N(v)} \frac{h^{k-1}_u}{|N(v)|}.$$display$$

Пулинг: поэлементное среднее/максимальное значение

$$display$$AGG = \gamma (\{ Qh^{k-1}_u, \forall u \in N(v) \}).$$display$$

LSTM: взболтать окружение (не смешивать!) и запустить в LSTM

$$display$$AGG = LSTM([ h^{k-1}_u, \forall u \in \pi ( N(v)) ]).$$display$$

В Pinterest, например, напихали туда многослойных перцептронов и выкатили в прод PinSAGE.

Рассмотрим её детальнее и приведём аналогии с процессами командообразования и IT-рекрутинга. В решении задачи предсказания функций белков в органах особо отличились аггрегаторы пулинг и LSTM (которые навсегда).

Проведём очевидные параллели:
 

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

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

В похожих органах белки выполняют биологически близкие функции.

Решение — используем графы взаимодействий между белками в разных органах. Задача — определить вероятность выполнения одной из множества функций (multi-label node
classification task) — один белок может выполнять несколько ролей в разных органах. Тренируем графовую свёрточную сеть GraphSAGE, и выучиваем веса, общие для всех вершин — теперь мы знаем обобщённые правила аггрегации информации о соседях. Свойствами вершин (белков) будут их генетические структуры и иммунологические сигнатуры (эти данные — достаточно фрагментарные — недоступны для 42% белков).

Полученные веса позволяют генерировать эмбеддинги для ранее не встречавшихся графов!

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

Напомним, метод состоит в построении мультимодального графа взаимодействий белок-белок, препарат-белок, и побочных эффектов от комбинации препаратов, которые представляются связями препарат-препарат, где каждый из побочных эффектов — ребро определённого типа ri. Вот теперь-то мы разобрались с деталями, необходимыми для понимания функционирования Decagon. Для каждой вершины-препарата мы строим 964 (по количеству побочных эффектов) вычислительных графа. Каждый из побочных эффектов моделируется изолированно.

image

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

image

Формально, для каждого слоя мы вычисляем

$$display$$h^k_v = \sigma(\sum_rW^{k-1}_r(\sum_{u \in N_r(v)} \frac{h^{k-1}_u}{\sqrt{|N_r(v)||N_r(u)|}}+\frac{h^{k-1}_v}{|N_r(v)|})),$$display$$

Как видим, в Decagon использован простейший вариант графовой свёрточной сети — взвешенная сумма. где $inline$\sigma $inline$ — нелинейность, например RELU. Полученные на финальном слое эмбеддинги вершин подаём на вход декодера, который возвращает вероятности возникновения каждого из побочных эффектов при совместном приёме препаратов. Очевидно, что ничто не мешает усложнить модель, аналогично GraphSAGE.

image

Разберёмся с тем, как этот декодер функционирует.

Каждый тип ребра обрабатывается по-своему. Его задача — реконструировать маркированные рёбра в графе, полагаясь на выученные эмбеддинги. Для каждой тройки параметров $inline$(u,r,v) $inline$, декодер вычисляет функцию:

\end{matrix} \right.\end{align*}$inline$ $inline$\begin{align*}g(u,r,v) = \left\{ \begin{matrix} z^T_uD_{r_i}RD_{r_i}z_j & u,v - препараты; \\ z^T_uM_rz_v & u,v - препарат\, и\, белок, \,или\, оба\, белки.

и подаёт результат в сигмоиду, чтобы определить вероятность появления ребра заданного типа:

$$display$$p^{uv}_{r} = p((u,r,v) \in E) = \sigma (g(u, r, v)), \sigma(x) = \frac{1}{1 + e^{-x}}.$$display$$

Итого, у нас есть сквозная (end-to-end) модель энкодер-декодер, в которой четыре типа параметров: (i) $inline$W_r $inline$ — веса нейронных сетей для аггрегации каждого типа отношений в графе, (ii) $inline$M_r $inline$ — матрицы параметров отношений препарат-белок и белок-белок, (iii) $inline$R $inline$ — общая матрица параметров побочных эффектов, и (iv) $inline$D_{r_i}$inline$ — матрицы параметров каждого побочного эффекта.

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

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

Здорово, что для того, чтобы обуздать всё это буйство связей теперь уже не нужно жечь нервные клетки, а можно просто взять и посчитать. Подытоживая всё сказанное выше — в сложных системах с кучей взаимосвязей, которые мы моделируем с помощью графов, отчётливо проявляются характерные черты: 1) гомофилия — подобное — притягивается; и 2) старое правило "Скажи мне, кто твой друг, и я скажу тебе, кто ты" — по-прежнему актуально.

Кратко — в ОЗУ — так быстрее.

Например, все исследования генома, проведённые человечеством из базы GenBank уместятся в 1 Тб, и машина с таким объемом памяти сейчас стоит примерно столько же, сколько автомобиль гольф-класса — рабочий инструмент торгового представителя, ездящего по аптекам. Моя личная позиция по поводу обработки графов в оперативной памяти на одной машине связана с тем, что размер структурированных данных (а именно из них мы и строим графы) растёт медленнее, чем объемы доступной за вменяемые деньги ОЗУ. Кластерные вычисления — это здорово, но распределённый подсчёт триад для большого графа из-за необходимости координировать и собирать результаты вычислений занимает в разы (если не на порядок) больше времени, чем та же операция в SNAP при соразмерных вычислительных мощностях.

Рассмотрим несколько доступных на сегодняшний день инструментов и способов работы.

Достаточно подробное описание возможных конструкций из точек и линий в одноимённой работе дают причастные к созданию первой графовой базы данных Neo4j, в которой реализована модель графа со свойствами (property graph).

image

Рабочая задача, с которой сразу обратился к преподавателю, — связать вместе (i) бизнес-процессы, (ii) отношения между сотрудниками, и (iii) план проекта, в котором куски работы — отдельные задачи — так или иначе влияют на первые два. Такой подход позволяет построить мультимодальный граф, в котором много разных сущностей можно связать различными типами связей. Ответ довелось искать самостоятельно.

Альтернативный пример таких данных — сама статья и все к ней причастные:

image

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

MATCH (nicole:Actor {name: 'Nicole Kidman'})-[:ACTED_IN]->(movie:Movie)
WHERE movie.year < $yearParameter
RETURN movie

Neo4j с помощью костылей можно заставить работать в памяти.

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

Сейчас большую часть исследований провожу аналитически, картинки рисую на финише.

Три года назад нашёл решение для работы с мультимодальными графами. Мой поиск инструментов и способов обработки данных в сложно связанных системах продолжается. Использую Snap.py — версию для Python (прокси к функциям SNAP, реализованным на C++) и набора из около трёх сотен доступных операций мне хватает в большинстве случаев. Библиотека SNAP Юре Лесковека — инструмент, который он разработал для себя и померял им уже много чего.

Недавно Маринка Житник выпустила MAMBO — набор инструментов (внутри — SNAP) для работы с мультимодальными сетями и туториал в виде серии блокнотов Jupyter с образцово-показательным анализом генетических мутаций.

Наконец, есть SAP HANA Graph — там внутри ML, SQL, OpenCypher — всё, чего душе угодно.

Ещё один плюс — мощные инструменты поиска суб-графов по заданным шаблонам — полезная и непростая задача, реализации которой в других пакетах не встречал и использовал специализированные программы. В пользу SAP HANA тот факт, что копать скорее всего доведётся хорошо структурированные данные транзакций из ERP, а чистые данные — многого стоят. Забавный вызов — набор аналитических алгоритмов из коробки — мал, PageRank нужно будет реализовать самостоятельно. Бесплатная лицензия для разработчика предоставляет базу размером 1 Гб — как раз хватит, чтобы поиграться с достаточно большими сетями. Как говорил мой тренер по гребному слалому, для мастера — это пыль! Для этого потребуется освоить GraphScript — новый язык программирования, но это уже мелочи.

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

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

image

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

  1. Даннинга-Крюгера, модифицированный, без эйфории новичка и плато совершенства. Лесковека попробуй догони.
  2. Скука в провинции у моря. Из 400 человек на курсе, которым дали матаппарат, заставили написать проект, и сдать экзамен в первую же сессию во время моей второй магистратуры, графы зашли полутора. Преподаватели в их исследовательской деятельности — так и остались на уровне модулярности и мер центральности. На митапах про питон и данные тоже грустно. В общем, если не умеете развлечь себя самостоятельно — я предупреждал.
  3. Гордость за славянский акцент в английской речи.

Привет, воспроизводитель!

Курс состоит из 20 лекций, четырёх домашек, на каждую из которых рекомендуется выделить около 20 часов, рекомендованной литературы, а также — обширного списка дополнительных материалов, которые позволят составить первое впечатление о состоянии дел на острие прогресса в любой из рассмотренных тем. В приключении, которое нам подарил Юре Лесковек, тебе потребуется свободное время.

Для выполнения заданий настоятельно рекомендуется использовать библиотеку SNAP (в каком-то смысле, весь курс можно рассматривать как обзор её возможностей).

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

Краткое содержание лекций 2017 года:

Вступление и структура графов
Анализ сетей — это универсальный язык описания сложных систем и сейчас — самое время с ним разобраться. 1. Начнём со способов представления объектов: узлы, рёбра, и способы их организации. Курс акцентируется на трёх направлениях: свойства сетей, модели, и алгоритмы.

Всемирная паутина и модель случайного графа
Мы узнаем, почему интернет похож на бабочку, и познакомимся с понятием сильно связанных компонентов. 2. И познакомимся с моделью случайного графа Эрдоша-Рейни. Как измерять сети — основные свойства: распределение степеней узлов, длина пути, и коэффициент кластеризации.

Феномен малого мира
Замеряем основные свойства случайного графа. 3. Поговорим о числе Эрдоша и том, как тесен мир. Сравним его с реальными сетями. Наконец, опишем всё происходящее математически (модель Ваттса-Строгатца). Вспомним Стенли Милграма и про шесть рукопожатий.

Децентрализованный поиск в малом мире и пирнинговые сети
Как ориентироваться в распределённой сети. 4. Собираем всё в кучу — свойства, модели, и алгоритмы. И как работают торренты.

Приложения анализа социальных сетей
Меры центральности. 5. Эффект подобия. Люди в интернете — как кто кого оценивает. Теория структурного баланса. Статус.

Сети с разнозначными рёбрами
Баланс в сетях. 6. Как кормить троллей. Взаимные лайки и статус.

Каскады: модели, основанные на решениях
Распространение в сетях: диффузия инноваций, сетевые эффекты, эпидемии. 7. Решения и теория игр в сетях. Модель коллективного действия.

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

Максимизация влияния
Как создавать большие каскады. 9. Итоги экспериментов. А вообще, насколько задача сложна?

Выявление заражения
Что общего у заразы и новостей. 10. И где размещать сенсоры в водопроводе. Как быть в курсе самого интересного.

Степенной закон и предпочтительное присоединение
Процесс роста сети. 11. Математика степенной функции распределения. Масштабно-инвариантные сети. Модель предпочтительного присоединения — богатые богатеют. Следствия: устойчивость сети.

Модели растущих сетей
Меряем хвосты: экспотенциальный против степенного. 12. Вид на всё это с высоты птичьего полёта. Эволюция социальных сетей.

Графы Кронекера
Продолжаем полёт. 13. Рекурсивная генерация графов. Модель лесного пожара. Эксперименты с реальными сетями. Стохастические графы Кронекера.

Анализ связей: HITS и PageRank
Как упорядочить интернет? 14. Находка Сергея Брина и Ларри Пейджа. Хабы и Авторитеты. Как делать рекомендации — опыт Pinterest. Пьяный бродяга с телепортом.

Сила слабых связей и структура сообществ в сетях
Триады и потоки информации. 15. Метод Гирвана-Ньюмана. Как выделить сообщества? Модулярность.

Обнаружение сообществ: спектральная кластеризация
Добро пожаловать, матрицы! 16. Мотифы (графлеты). Поиск оптимального сечения. Экспрессия генов. Пищевые цепочки.

Биологические сети
Взаимодействия белков. 17. Определение молекулярных аттрибутов, например функций белков в клетках. Выявление цепочек болезненных реакций. Навешиваем ярлыки. Что делают гены?

Пересекающиеся сообщества в сетях
Различные социальные круги. 18. От кластеров к пересекающимся сообществам.

Изучение представлений на графах
Автоматическое формирование фичей — просто праздник для ленивых. 19. Node2vec. Графовые эмбеддинги. От отдельных графов — к сложным иерархическим структурам — OhmNet.

Сети: пара забавностей
Жизненный цикл участника абстрактного сообщества. 20. И как управлять поведением сообществ с помощью бейджей.

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Как распознавание лиц помогает находить тестовые телефоны

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

Security Week 39: на смерть Google+

На прошлой неделе Google объявил (новость) о закрытии социальной сети Google+, но сделано это было достаточно необычно. Компания Google вообще не стесняется закрывать проекты, которые по разным причинам не взлетели. Многие до сих пор не могут простить компании отказа от ...