Графовые данные

Коротко

Definition

Графовые данные — это данные, в которых важны не только сами объекты, но и связи между ними: объекты представляются вершинами графа, а отношения между объектами — рёбрами.

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

Примеры графовых данных:

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

Что это за данные

Граф обычно обозначают так:

$$G=(V,E)$$

где:

• $V$ — множество вершин;
• $E$ — множество рёбер;
• $G$ — граф целиком.

У вершин и рёбер могут быть признаки:

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

Граф может быть:

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

Как обычно представлены

Графовые данные можно представить несколькими способами.

Список рёбер

Список рёбер хранит пары связанных вершин:

Откуда	Куда
0	1
1	2
2	3

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

Матрица смежности

Матрица смежности показывает, есть ли связь между вершинами:

$$A_{ij}=\{\begin{array}{ll}1,& \text{если есть ребро между }i\text{ и }j\\ 0,& \text{если ребра нет}\end{array}$$

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

Признаки вершин

Признаки вершин можно хранить в матрице:

$$X\in {\mathbb{R}}^{n\times d}$$

где:

• $n$ — число вершин;
• $d$ — число признаков вершины;
• $X$ — матрица признаков вершин.

Для молекулы строка в $X$ может описывать атом: тип элемента, заряд, гибридизацию и другие признаки.

Признаки рёбер

Если связи имеют свойства, хранят также признаки рёбер.

Например, в молекуле ребро может иметь тип связи:

• одинарная;
• двойная;
• тройная;
• ароматическая.

В кристаллах ребро может описывать соседство атомов и расстояние между ними.

Какие задачи решают

На графовых данных решают разные типы задач.

Предсказание свойства графа

Нужно предсказать одно свойство для всего графа.

Примеры:

• токсичность молекулы;
• энергия образования материала;
• растворимость молекулы;
• класс химического соединения.

Это может быть классификация или регрессия.

Предсказание свойства вершины

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

Примеры:

• классификация пользователя в социальной сети;
• предсказание роли атома в молекуле;
• классификация статьи в citation graph.

Предсказание связи

Нужно предсказать, существует ли связь между двумя вершинами.

Примеры:

• рекомендация друзей;
• предсказание взаимодействия между сущностями;
• восстановление недостающих связей в knowledge graph.

Кластеризация графов или вершин

Можно искать группы похожих вершин или похожих графов. Это связано с кластеризацией.

Какие модели подходят

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

Базовая идея графовых нейросетей: вершина обновляет своё представление, собирая информацию от соседей. Такой процесс часто называют message passing.

Для молекул и кристаллов подробнее см. GNN для молекул и кристаллов.

В задачах материаловедения графовые модели особенно полезны, потому что структура материала естественно задаётся через атомы и связи. Это связано с Геометрическое ML в химии, ML для материалов и проектом Materials ML.

Для простых задач иногда граф сначала превращают в обычные признаки:

• количество вершин;
• количество рёбер;
• степени вершин;
• статистики по соседям;
• агрегированные признаки;
• заранее посчитанные descriptors.

После этого можно применять обычные модели для табличных данных, например Случайный лес или Градиентный бустинг.

Типичная предобработка

Графовые данные требуют своей предобработки.

Типичные шаги:

1. Проверить корректность вершин и рёбер.
2. Удалить дубликаты рёбер, если они не имеют смысла.
3. Добавить или проверить признаки вершин.
4. Добавить или проверить признаки рёбер.
5. Привести графы к единому формату.
6. Решить, нужны ли self-loops.
7. Решить, учитывать ли направление рёбер.
8. Разделить данные на train, validation и test.
9. Проверить, нет ли data leakage через похожие или дублирующиеся графы.
10. Выбрать способ batching для графов разного размера.

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

Частые проблемы

Графы разного размера

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

Например, одна молекула может иметь 10 атомов, другая — 80. Модель должна уметь работать с такими объектами в одном датасете.

Потеря информации при упрощении

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

Например, две молекулы могут иметь одинаковое число атомов и связей, но разную топологию и разные свойства.

Data leakage через похожие объекты

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

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

Неправильное определение рёбер

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

Если правило построения рёбер плохое, модель будет учиться на искажённой структуре.

Слишком слабые признаки вершин

Графовая структура важна, но признаки вершин тоже имеют значение.

Если вершины почти не описаны, модель может не отличать разные типы объектов и давать слабое качество.

Сложность интерпретации

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

Минимальный пример

Рассмотрим простую молекулу как граф.

Вершина	Смысл	Признак
0	атом углерода	C
1	атом кислорода	O
2	атом водорода	H
3	атом водорода	H

Рёбра:

Откуда	Куда	Тип связи
0	1	одинарная
0	2	одинарная
0	3	одинарная

В таком представлении:

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

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

Практические замечания

Хороший стартовый workflow для графовых данных:

1. Понять, что является вершинами.
2. Понять, что является рёбрами.
3. Определить признаки вершин и рёбер.
4. Проверить, что графовое представление соответствует предметной области.
5. Выбрать задачу: классификация, регрессия, кластеризация или link prediction.
6. Сделать корректное разбиение на train, validation и test.
7. Построить простой baseline на агрегированных признаках.
8. Затем сравнить его с графовой моделью.
9. Оценить качество через подходящие метрики.
10. Проанализировать ошибки на разных типах графов.

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

Связанные понятия

Связанные заметки

• Метрики качества классификаторов
• Метрики качества регрессоров
• Метрики качества кластеризации