Решение задач на графах

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

Построение эмбеддингов вершин

Начальные эмбеддинги

Эмбеддинг вершины графа (node embedding) - это вектор вещественных чисел, характеризующий признаки вершин:

$$v_i \to \mathbf{h}^0_i \in \mathbb{R}^{D}, \quad i=1,2,...N$$

Этим вектором данных могут выступать начальные характеристики вершины. Например, если рассматривается граф социальной сети, в которой вершинами выступают пользователи, то $\mathbf{h}_i^0$ может описывать пол, возраст и интересы, указанные в анкете. Если информации об узлах не предоставлено, можно задать её самостоятельно, передавая:

• one-hot закодированный номер вершины (для небольших графов);

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

Контекстное уточнение эмбеддингов

Используя геометрию графа, можно уточнять эмбеддинги вершин, учитывая контекстную информацию о соседних вершинах для каждого узла графа (neighborhood aggregation), аналогично тому, как уточнялись эмбеддинги слов в архитектуре трансформера по контексту соседних слов. Для этого применяется итеративный алгоритм свёрточных графовых сетей (graph convolutional networks), описанный в следующей главе.

На выходе алгоритма мы получаем эмбеддинги каждой вершины $\{\mathbf{h}_i^1\}_i$ с учётом контекста её соседей 1-го порядка (соединённых ребром напрямую), эмбеддинги $\{\mathbf{h}_i^2\}_i$ с учётом контекста соседей 2-го порядка (соседей от соседей) и т.д. После $K$ итераций алгоритма получаем окончательные контекстные эмбеддинги $\{\mathbf{h}_i\}_i$ (graph-based contextual embeddings), которые совместно будут храниться в матрице $H=[\mathbf{h}_1,...\mathbf{h}_N]\in\mathbb{R}^{D\times N}$.

Задачи на графе целиком

Рассмотрим задачи, в которых известно некоторое свойство для графов $G_1,...G_M$ и требуется предсказывать свойство для нового графа $G=(V,E,X)$, содержащего $N$ вершин. Поскольку обучающие и тестовые данные разделены, то это классическая задача обучения с учителем (supervised learning) или индуктивного обучения (inductive learning).

Корректно специфицированная модель должна быть инвариантной к перенумерации вершин (invariance to permutation), то есть результат не должен зависеть от того, как именно мы пронумеруем вершины графа. Формально это записывается как

$$\hat{y}(H)\equiv \hat{y}(H\cdot P)$$

для любой матрицы перестановки вершин $P$.

Регрессия

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

$$\hat{y}(G) = w_0+\mathbf{w}^T \cdot H \cdot \mathbf{i}/N,$$

где

• $\mathbf{i}=[1,1,...1]^T\in\mathbb{R}^{D}$ - вектор из единиц;

• $w_0\in\mathbb{R}, \mathbf{w}\in\mathbb{R}^{D}$ - настраиваемые параметры.

Домножение на вектор из единиц и деление на число узлов $N$ означает усреднение эмбеддингов всех вершин.

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

Бинарная классификация

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

$$\hat{y}(G) = \sigma(w_0+\mathbf{w}^T \cdot H \cdot \mathbf{i}/N),$$

где $\sigma(u)=1/(1+e^{-u})$ - сигмоидная функция активации (сигмоида).

Поскольку сигмоида принимает значения в интервале $(0,1)$, то выход интерпретируется как вероятность положительного класса (вероятность токсичности вещества).

Многоклассовая классификация

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

$$\left(\begin{array}{c} p(y=1|G)\\ p(y=2|G)\\ \cdots\\ p(y=C|G) \end{array}\right)=\text{SoftMax}\left(\mathbf{w}_{0}+W\cdot H\cdot\mathbf{i}/N\right),$$

где настраиваемые параметры - это:

• $\mathbf{w}_{0}\in \mathbb{R}^C$ - вектор смещений;

• $W\in\mathbb{R}^{C\times D}$ - матрица весов.

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

Альтернатива усреднению эмбеддингов

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

• Суммирование эмбеддингов. В этом случае количество узлов графа будет влиять на результат, увеличивая разброс значений суммы.

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

:::

Задача

Докажите, что модели в каждом случае обладают инвариантностью к перенумерации вершин. Для этого воспользуйтесь свойством $P\cdot \mathbf{i}=\mathbf{i} \; \forall P$ (которое тоже докажите).

Обработка отдельных вершин графа

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

Поскольку вершины, для которых нужно что-то предсказать, известны заранее, то это задача частичного обучения (semi-supervised learning).

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

Регрессия

Рассмотрим задачу регрессии на каждой вершине графа. Например, для графа социальной сети нужно предсказать ожидаемое время, которое каждый пользователь проведёт в сети. Для вершины $v_i$ с контекстным эмбеддингом $\mathbf{h}_i$ она решается по формуле:

$$\widehat{y}(\mathbf{h}_{i})=w_{0}+\mathbf{w}^{T}\mathbf{h}_{i}$$

Для всех узлов прогноз строится как

$$\widehat{y}(H)=w_{0}+\mathbf{w}^{T}H$$

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

Бинарная классификация

Рассмотрим задачу бинарной классификации каждой вершины графа. Например, на графе социальной сети для каждой вершины (пользователя) нужно предсказать, является ли аккаунт ботом или реальным человеком. Для вершины $v_i$ с контекстным эмбеддингом $\mathbf{h}_i$ она решается по формуле:

$$p(\hat{y}=1|\mathbf{h}_{i}) = \sigma(w_{0}+\mathbf{w}^{T}\mathbf{h}_{i})$$

Для всех узлов прогноз строится, применяя сигмоиду поэлементно:

$$\mathbf{p}(\hat{\mathbf{y}}=1|H) = \sigma(w_{0}+\mathbf{w}^{T}H)$$

Многоклассовая классификация

Рассмотрим задачу бинарной классификации каждой вершины графа на $C$ классов. Например, для графа социальной сети нужно предсказать, является ли человек безработным, работающим по найму, самозанятым или предпринимателем. Для этого вычисляется $C$ рейтингов каждого класса, которые преобразуются в набор вероятностей классов через SoftMax-преобразование:

$$\left(\begin{array}{c} p(y=1|\mathbf{h}_{i})\\ p(y=2|\mathbf{h}_{i})\\ \cdots\\ p(y=C|\mathbf{h}_{i}) \end{array}\right)=\text{SoftMax}\left(\mathbf{w}_{0}+W\cdot\mathbf{h}_{i}\right),$$

где настраиваемые параметры - это:

• $\mathbf{w}_{0}\in \mathbb{R}^C$ - вектор смещений;

• $W\in\mathbb{R}^{C\times D}$ - матрица весов.

Сразу для всех вершин вероятности считаются как

$$\hat{P}(H)=\text{SoftMax}\left(\mathbf{w}_{0}+W\cdot H\right),$$

где SoftMax применяется независимо к каждому столбцу.

Задача

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

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

Восстановление рёбер графа

Рассмотрим один граф, часть рёбер которого известна, и надо восстановить недостающие рёбра графа (edge reconstruction, graph completion). Например, в графе цитирования дополнить научную статью недостающими ссылками на похожие исследования. Для этого можно посчитать вероятность связи между каждой парой узлов $v_i$ и $v_j$ по формуле

$$p((v_i,v_j) \text{ - связаны}\,|\,\mathbf{h}_i,\mathbf{h}_j) = \sigma(\mathbf{h}_i^T\mathbf{h}_j),$$

где $\sigma(\cdot)$ - сигмоидная функция. По смыслу скалярное произведение вычисляет сочетаемость характеристик вершин друг с другом по схожести их признаков, а соединяются вершины, обладающие схожими характеристиками. После расчёта вероятности связи для каждой пары вершин можно провести рёбра там, где эта вероятность больше некоторого порога $t$:

$$p((v_i,v_j) \text{ - связаны}\,|\,\mathbf{h}_i,\mathbf{h}_j)>t \;\Longrightarrow\; \text{соединить } v_i,v_j.$$

Гиперпараметр $t$ управляет противоречием между точностью и полнотой (precision and recall) восстановления связей и подбирается по валидационной выборке (качеству восстановления вершин на подмножестве рёбер, на котором все связи известны, но часть была предварительно затёрта).

Если эмбеддинги $\{\mathbf{h}_i\}_i$ настраиваются для решения других задач, то можно усложнить расчёт вероятности связи, введя дополнительную параметризацию:

$$p((v_i,v_j) \text{ - связаны}\,|\,\mathbf{h}_i,\mathbf{h}_j) = \sigma(w_0+\mathbf{h}_i^T W \mathbf{h}_j),$$

где новые параметры - это

• $w_0\in\mathbb{R}$ - смещение,

• $W\in\mathbb{R}^{D\times D}$ - симметричная матрица весов, т.е. $W=W^T$.

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

В качестве обобщения приведённых подходов можно применять многослойный персептрон к поэлементному произведению эмбеддингов $\mathbf{h}_i\odot\mathbf{h}_j$ либо к их конкатенации.

Симметричность для ненаправленного графа

Для ненаправленного графа должно выполняться свойство:

$$p((v_i,v_j) \text{ - связаны}\,|\,\mathbf{h}_i,\mathbf{h}_j)=p((v_j,v_i) \text{ - связаны}\,|\,\mathbf{h}_j,\mathbf{h}_i)$$

Для многослойного персептрона от конкатенации эмбеддингов оно в общем случае выполняться не будет:

$$f(\mathbf{h}_i,\mathbf{h}_j) \ne f(\mathbf{h}_j,\mathbf{h}_i),$$

поэтому в этом случае вероятность связи лучше предсказывать по формуле:

$$p((v_i,v_j) \text{ - связаны}\,|\,\mathbf{h}_i,\mathbf{h}_j)= f(\mathbf{h}_i,\mathbf{h}_j) + f(\mathbf{h}_j,\mathbf{h}_i)$$

Регрессия и классификация рёбер

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

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

---

В следующей главе будет описан алгоритм, уточняющий эмбеддинги вершин графа, по их соседям на графе (neighborhood aggregation).