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

Задачи на графах

Типы задач на графах​

Существует три типа самых популярных задач на графах, решаемых нейросетями:

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

  2. Дан один большой граф, для части рёбер которого известно некоторое свойство. Необходимо восстановить это свойство для других рёбер.

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

  3. Дан один большой граф, лишь часть рёбер которого известны. Необходимо восстановить недостающие рёбра.

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

Стоит отметить, что существуют и другие задачи на графах, которые мы не будем рассматривать:

  • Обнаружение сообществ в графе (community detection), то есть подмножества узлов такие, что каждый из них связан с каждым. Например, сообществом могут выступать люди одного плотно общающегося коллектива (друзья, одноклассники, коллеги по работе). Данная задача решается вычислительными методами без использования нейросетей.

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

Примеры прикладных задач​

Социальная сеть​

Социальную сеть (social network) можно рассматривать как граф, в котором узлами являются люди, а связи устанавливаются, если они

  • добавили друг друга в друзья,

  • подписаны друг на друга,

  • писали друг другу сообщения.

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

Задачи, которые можно решать:

  • предсказание свойства узла:

    • определение тем, которые человеку могут быть интересны;

    • оценка возраста (если не указан), материального статуса;

    • предсказание поведения (вероятность клика или покупки);

    • обнаружение аномалий (соответствующих тому, что аккаунт является ботом или мошенником)

  • восстановление рёбер:

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

Граф цитирований​

Граф цитирований (citation graph) описывает научные работы, выступающие узлами этого графа. Узел соединяется с другим узлом, если научная работа ссылается на другую. Поскольку цитирование - несимметричная операция, то это всегда будет направленный граф.

Задачи, которые можно решать:

  • предсказание свойств узла:

    • оценка тематики и научной ценности работы по её содержанию и ссылкам на неё из других работ;

  • восстановление рёбер:

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

Интернет​

Интернет можно описать графом (network graph), в котором узлами являются веб-страницы, а ребро проводится, если одна веб-страница содержит гиперссылку на другую. Как и в случае графа цитирований, это будет направленный граф.

Задачи, которые можно решать:

  • предсказание свойства узла:
    • оценка тематики веб-страницы;
    • оценка важности веб-страницы для оценки её позиции в поисковой выдаче;
  • восстановление рёбер:
    • определение веб-страниц схожей тематики, даже если они не ссылаются друг на друга.

Химические соединения​

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

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

  • является ли вещество проводником или диэлектриком, какова его температура плавления и кипения, теплоёмкость и другие свойства;

  • растворимость вещества в воде, способность вещества вступать в химические реакции.

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

  • лечебный эффект, способность связываться с определёнными патогенами в организме;

  • токсичность для человека и возможные побочные эффекты;

  • скорость распространения вещества в организме и выведения из него;

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

Более сложные задачи​

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

Компьютерная сеть​

Интернет или внутреннюю сеть (intranet) можно описать в виде графа, где узлами выступают сетевые устройства, а рёбра проводятся, если между устройствами устанавливаются сетевые соединения.

Тогда можно решать следующие задачи:

  • оценка пропускной способности определённых участков сети,

  • оптимизация маршрутов передачи данных,

  • обнаружение аномалий (взломов, атак, вредоносного ПО).

Городское планирование и транспорт​

Пассажиропоток можно описать в виде графа (transportation network), в котором узлами будут остановки, перекрёстки, станции, а рёбрами - маршруты между ними. Тогда можно решать задачи:

  • оптимизация транспортных потоков,

  • прогнозирования пробок,

  • планирования городских систем (размещение станций, прокладка маршрутов).

Рынки и логистика​

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

  • оценивать кредитоспособность агента,

  • управлять запасами на складе,

  • прогнозировать логистические задержки поставок,

  • оптимизировать цепочки поставок.

Граф знаний​

По размеченным текстам (например, из википедии) можно построить граф знаний (knowledge graph), где узлами выступают персоны, компании и события, а рёбрами - характер их взаимодействия.

Ниже рассмотрен пример такого графа для музеев и картин [1]:

Примерами задач на подобном графе могут выступать:

  • поиск опосредованных связей между персонами или событиями;

  • оценка важности того или иного события в контексте поискового запроса;

  • группировка людей, сообществ, событий по темам;

  • суммаризация набора разрозненных фактов в целостные события.

Используя инструменты автоматического анализа, граф знаний можно составлять и из неструктурированного текста, а также из изображений, как показано ниже [2]:

Программный код​

Можно представить программный код в виде графа (control flow graph, call graph), в котором узлами будут функции, между которыми проводится ребро, если одна функция вызывает внутри себя другую. Либо узлами могут выступать переменные, а рёбрами - участие одних переменных в формировании других переменных (вычислительный граф). Над подобными графами можно решать следующие задачи:

  • определение избыточного кода, выявление участков, выполняющих одинаковые действия;

  • обнаружение ошибок и уязвимостей;

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

  • генерация кода, дополняющего уже имеющийся;

  • семантический поиск по коду - обнаружение всех участков кода, выполняющих определённый характер действий;

  • анализ полноты покрытия кода тестами, автоматическое создание проверочных тестов.

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

Литература​

  1. https://www.wikidata.org/wiki/User:Fuzheado/queries
  2. Shin D., Kim I. Deep image understanding using multilayered contexts //Mathematical Problems in Engineering. – 2018. – Т. 2018. – №. 1. – С. 5847460.