Графовое представление данных

Материал из MachineLearning.

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

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

Содержание

1 Формальное определение
2 Основные виды графов
3 Способы хранения графовых данных
4 Представление графа в машинном обучении
5 Числовой пример
6 Основные задачи
7 Применение
8 Утечка данных
- 8.1 Обнаружение утечки
- 8.2 Предотвращение утечки
9 Типичные ошибки оценки
10 Методологический смысл независимой оценки
11 Ограничения и перспективы
12 Примечания
13 Литература

Формальное определение

Граф задаётся парой $G=(V,E)$ , где $V$ — множество вершин, а $E$ — множество рёбер. Вершины соответствуют объектам предметной области. Рёбра фиксируют отношения между ними.^[1]

В неориентированном графе ребро между вершинами $u$ и $v$ записывается как неупорядоченная пара ${u,v}$ . Такая связь симметрична. В ориентированном графе используется упорядоченная пара $(u,v)$ , задающая направление от $u$ к $v$ .

Каждой вершине может соответствовать вектор признаков $x_v\in\mathbb{R}^d$ . Для банковского клиента он может содержать число операций, возраст счёта и среднюю сумму платежа. Признаки ребра $e_{uv}$ описывают само взаимодействие: сумму перевода, время сообщения, расстояние между пунктами или тип химической связи. Иногда вводятся признаки всего графа, например температура молекулярной системы или категория программного проекта.

Степенью вершины называют число инцидентных ей рёбер. Для неориентированного графа она определяется как $\deg(v)=|{u:{u,v}\in E}|$ . В ориентированном графе различаются входящая и исходящая степени. Эти величины отражают локальную структуру, но не показывают положение вершины в сети целиком. Две вершины с одинаковой степенью могут находиться в центре разных сообществ или выполнять принципиально разные функции.

Путь представляет собой последовательность связанных вершин. Длина кратчайшего пути характеризует структурную близость объектов. Компонента связности объединяет вершины, между которыми существует путь. Цикл возникает, когда путь возвращается в исходную вершину. Эти понятия используются при анализе достижимости, сообществ, транспортных маршрутов и распространения информации.^[1]

Основные виды графов

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

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

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

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

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

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

Динамический граф меняется во времени. В нём появляются и исчезают вершины, рёбра и признаки. История может храниться как последовательность снимков $G_1,G_2,\ldots,G_T$ или как набор событий с временными метками. Представление в виде снимков проще, но скрывает точный порядок событий внутри интервала.

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

Способы хранения графовых данных

Матрица смежности графа с $n$ вершинами представляет собой матрицу $A\in\mathbb{R}^{n\times n}$ . В невзвешенном случае $A_{ij}=1$ , если вершины $i$ и $j$ связаны, и $A_{ij}=0$ в противном случае. Для взвешенного графа элемент матрицы хранит вес ребра.

Проверка существования ребра в матрице выполняется за постоянное время. Цена этого свойства — объём памяти $O(n^2)$ . Для графа из миллиона вершин полная матрица содержит $10^{12}$ элементов, хотя реальных связей может быть лишь несколько миллионов.

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

Список смежности сопоставляет каждой вершине перечень её соседей. Его объём равен $O(|V|+|E|)$ . Такой формат удобен для обхода графа, поиска локального окружения и обучения моделей, которые последовательно агрегируют признаки соседних вершин.

Список рёбер хранит записи вида $(u,v)$ или $(u,v,w)$ . Он прост для передачи, сортировки и пакетной обработки. Получение всех соседей конкретной вершины требует индексации или предварительной группировки.

Матрица инцидентности связывает вершины и рёбра. Для графа с $n$ вершинами и $m$ рёбрами она имеет размер $n\times m$ . Такой формат применяется в задачах потоков, оптимизации и анализе гиперграфов, но для обычного поиска соседей используется реже матрицы или списка смежности.

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

Граф знаний обычно хранится как набор троек «субъект — отношение — объект». Запись «Париж — столица — Франция» задаёт ориентированное типизированное ребро. Графы знаний используются для объединения разнородных источников, семантического поиска и восстановления пропущенных отношений.^[1]

Представление графа в машинном обучении

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

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

Методы графовых вложений обучают для каждой вершины вектор фиксированной размерности. Близкие по структуре вершины должны иметь похожие представления. Алгоритм DeepWalk генерирует случайные блуждания по графу и рассматривает их как последовательности объектов.^[1] Метод node2vec управляет направлением блуждания и позволяет смещать обучение либо к локальным сообществам, либо к вершинам с похожими структурными ролями.^[1]

Графовая нейронная сеть вычисляет новое представление вершины через признаки её окружения. Общая схема слоя записывается как $h_v^{(l+1)}=\operatorname{Update}(h_v^{(l)},\operatorname{Aggregate}({h_u^{(l)}:u\in N(v)}))$ , где $N(v)$ — множество соседей вершины $v$ .

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

Для графовой свёрточной сети один слой может быть записан как $H^{(l+1)}=\sigma(\tilde D^{-1/2}\tilde A\tilde D^{-1/2}H^{(l)}W^{(l)})$ , где $\tilde A=A+I$ — матрица смежности с добавленными петлями, $\tilde D$ — матрица степеней, $W^{(l)}$ — обучаемая матрица параметров.^[1]

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

Числовой пример

Пусть граф содержит четыре вершины $V={1,2,3,4}$ и рёбра $E={{1,2},{1,3},{2,3},{3,4}}$ . Вершины 1 и 2 имеют степень 2, вершина 3 — степень 3, вершина 4 — степень 1.

Каждой вершине задан один признак: $x_1=2$ , $x_2=4$ , $x_3=1$ , $x_4=7$ . Новое представление вычисляется как среднее собственного признака и признаков соседей.

Вершина 3 соединена с вершинами 1, 2 и 4. Поэтому $h_3=(1+2+4+7)/4=3{,}5$ . Для вершины 4 единственным соседом является вершина 3, следовательно, $h_4=(7+1)/2=4$ .

До агрегации вершина 3 описывалась числом 1. После агрегации её представление изменилось до 3,5, поскольку в расчёт вошло окружение. В этом состоит принципиальное отличие графовой модели от модели, обрабатывающей каждую строку независимо.

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

Основные задачи

При классификации вершин целевая переменная относится к отдельному объекту. Так определяются категории публикаций в сети цитирования, мошеннические аккаунты или функции белков.

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

При классификации графов один объект наблюдения является целым графом. Молекула представляется вершинами-атомами и рёбрами-химическими связями, а модель прогнозирует токсичность, растворимость или биологическую активность.^[1]

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

Применение

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

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

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

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

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

Утечка данных

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

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

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

Временная утечка возникает при использовании будущих событий. Для прогноза мошенничества в момент $t$ нельзя строить граф по операциям, совершённым после $t$ . Формальное условие для признаков имеет вид $t_{\mathrm{feature}}\leq t_{\mathrm{prediction}}$ .

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

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

Обнаружение утечки

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

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

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

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

Предотвращение утечки

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

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

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

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

Типичные ошибки оценки

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

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

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

Одно разбиение даёт нестабильную оценку. Итог зависит от плотности графа, состава сообществ и доли редких классов. Поэтому используются несколько фиксированных разбиений или стандартные протоколы, явно задающие доступную структуру.^[1]

Методологический смысл независимой оценки

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

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

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

Ограничения и перспективы

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

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

Крупные графы требуют выборки соседей, распределённого хранения и приближённых вычислений. Полный обход окружения для каждой вершины быстро становится невозможным. Индуктивный метод GraphSAGE решает часть этой проблемы за счёт выборки и агрегации ограниченного числа соседей.^[1]

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

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

Примечания

Литература

Bronstein M. M., Bruna J., Cohen T., Veličković P. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. IEEE Signal Processing Magazine. 2021. Vol. 38, No. 6. P. 18–42.
Diestel R. Graph Theory. 5th ed. Cham: Springer, 2017.
Hamilton W. L. Graph Representation Learning. San Rafael: Morgan & Claypool Publishers, 2020.
Newman M. E. J. Networks: An Introduction. Oxford: Oxford University Press, 2010.
Wu Z., Pan S., Chen F., Long G., Zhang C., Yu P. S. A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems. 2021. Vol. 32, No. 1. P. 4–24.
Zhou J., Cui G., Hu S. et al. Graph Neural Networks: A Review of Methods and Applications. AI Open. 2020. Vol. 1. P. 57–81.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%93%D1%80%D0%B0%D1%84%D0%BE%D0%B2%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%B4%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85»