Перейти к основному содержимому

Обработка графов

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

Понятие графа и его основные виды

Граф [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]). Например, определение степени схожести двух химических соединений или поиск похожих подструктур в базе графов научных публикаций.

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

Литература

  1. Wikipedia: Граф (математика).
  2. paperswithcode.com: Graph Classification.
  3. paperswithcode.com: Graph Regression.
  4. paperswithcode.com: Node Classification.
  5. paperswithcode.com: Link Prediction.
  6. paperswithcode.com: Graph Generation.
  7. Doujiang Zheng: Dynamic Temporal Graph Learning Reading List.
  8. paperswithcode.com: Graph Clustering.
  9. Wikipedia: Graph matching.