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

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

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

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

Эмбеддинг вершины графа (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}$.

Все контекстные эмбеддинги будут храниться в матрице $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$.

Поскольку каждая симметричная матрица представима в виде разложения Холецкого

$$W=L\cdot L^T, \text{ $L$ - нижнетреугольная матрица,}$$

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

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

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

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

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

---

В следующей главе вы узнаете алгоритм, уточняющий эмбеддинги вершин графа, используя информацию о его геометрии, т.е. о том, как вершины связаны друг с другом на графе (neighborhood aggregation, graph-based contextual embeddings).