Обработка графов
Рассмотрим основные задачи, которые решаются для данных, представимых в виде графа, с помощью нейронных сетей.
Понятие графа и его основные виды
Граф [1] в математике представляет собой коллекцию вершин (verteх) или узлов (node), соединённых друг с другом рёбрами (edge). Граф может быть направленным (directed graph) и ненаправленным (undirected graph) в зависимости от того, отношение связности действует в одну сторону или всегда в обе. Также граф может быть взвешенным (weighted graph), когда каждому ребру ставится в соответствие сила связи. Также ребрам можно ставить в соответствие и дискретные категории (тип связи) и вещественные признаки. Пример графа (источник):
Примеры данных, представляемых в виде графа
Графы часто возникают на практике. Ниже приведены примеры данных, которые можно представить в виде графа:
-
социальная сеть, где узлами выступают люди, а связи - добавил ли человек другого человека в друзья или писал ли ему сообщения;
-
интернет, где узлами выступают веб-страницы, а связи отражают ссылки одних веб-страниц на другие;
-
научные публикации, где узлами выступают статьи, а рёбра проводятся, если одна статья ссылается на другую;
-
компьютерная сеть, где узлами выступают компьютеры и сетевые устройства, а ребра проводятся, если устройства соединены и посылают друг другу данные;
-
знания, где узлами выступают сущности, а ребра отражают связи между этими сущностями, как показано ниже (источник):
-
вещества, где узлами выступают молекулы, а связями - их химические соединения (источник):
Задачи на графах, решаемый нейросетями
Опишем основные задачи, которые можно решать на графах с помощью нейросетей.
Классификация графа (graph classification [2]) - отнесение графа к одному из дискретных классов. Например, по химическому соединению лекарства предсказать, будет ли оно обладать лечебным эффектом. Также можно решать и задачу регрессии (graph regression [3]), например, по виду химического соединения определить его температуру плавления.
Классификация узлов графа (node classification [4]). Например, для графа социальной сети определять, является ли аккаунт ботом или реальным человеком.
Восстановление ребер на графе (link prediction [5]). Например, в графе научных работ предсказывать недостающие ссылки на связанные научные исследования.
Можно решать задачу классификации и регрессии на ребрах графа (edge classification / edge regression). Например, в графе социальной сети предсказывать, как часто друзья будут обмениваться сообщениями и будут ли посылать друг другу изображения, приглашать в группы и т.д.
Генерация графа, обладающего требуемыми свойствами (graph generation [6]). Например, нас может интересовать список химических соединений, обладающих как высокой прочностью, так и низкой плотностью для авиапромышленности. Либо в медицине интересны лекарственные вещества, обладающие максимальным лечебным действием при минимуме побочных эффектов.
Прогнозирование изменений во времени (dynamic / temporal graph prediction [7]). Например, предсказание, как будет эволюционировать социальная сеть, какие связи появятся или исчезнут в будущем, или как изменится структура молекулы при воздействии внешней среды.
Кластеризация графа (graph clustering [8]). Например, выделение сообществ пользователей в социальной сети, выявление функциональных групп атомов в молекуле или модулей в биологических сетях.
Сопоставление графов (graph matching / graph similarity [9]). Например, определение степени схожести двух химических соединений или поиск похожих подструктур в базе графов научных публикаций.
Обработке графов нейросетевыми методами посвящён отдельный раздел учебника.
Литература
- Wikipedia: Граф (математика).
- paperswithcode.com: Graph Classification.
- paperswithcode.com: Graph Regression.
- paperswithcode.com: Node Classification.
- paperswithcode.com: Link Prediction.
- paperswithcode.com: Graph Generation.
- Doujiang Zheng: Dynamic Temporal Graph Learning Reading List.
- paperswithcode.com: Graph Clustering.
- Wikipedia: Graph matching.