графы на поверхностях и их приложения

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

Звонкин А.К., Ландо С.К.

Графы, нарисованные на двумерных поверхностях, всегда привлекали исследователей своей красотой и разнообразием связанных с ними трудных вопросов. Теория таких графов, долгое время казавшаяся сравнительно изолированной, неожиданно оказалась в самом центре современных исследований. Диапазон этих исследований простирается от теории Галуа до моделей квантовой гравитации. Книга представляет собой доступное введение в указанный круг вопросов. Она включает такие сюжеты, как накрытия римановых поверхностей, действие группы Галуа на вложенных графах (гротендиковская теория «детских рисунков»), метод матричных интегралов, пространства модулей алгебраических кривых, топологические аспекты теории мероморфных функций, а также комбинаторные аспекты инвариантов Васильева.

Использование материалов ЭБ РФФИ

Воспроизведение материалов из ЭБ в любой форме требует письменного разрешения РФФИ. Пользователи вправе в индивидуальном порядке использовать материалы, находящиеся на сайте РФФИ, для некоммерческого использования.

Пользователь обязуется не осуществлять (и не пытаться получить) доступ к каким-либо материалам ЭБ иным способом, кроме как через интерфейс Сайта.

Пользователь обязуется не воспроизводить, не дублировать, не копировать, не продавать, не осуществлять торговые операции и не перепродавать материалы ЭБ для каких-либо целей.

Другие произведения в разделе:

© 1992–2021, Российский фонд фундаментальных исследований

Россия, 119334, Москва, Ленинский проспект, 32а, 20-21 этаж
Телефон для справок: +7 (499) 941-01-15

Источник

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

Physics.Math.Code запись закреплена

Введение в теорию графов [2019] Робин Уилсон

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

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

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

Источник

3D ML. Часть 5: Свертки на графах

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

Наверное вы уже догадались, что речь сегодня пойдет о сверточных операторах на графах.

Серия 3D ML на Хабре:

Репозиторий на GitHub для данной серии заметок.

Заметка от партнера IT-центра МАИ и организатора магистерской программы “VR/AR & AI” — компании PHYGITALISM.

Откуда брать информацию и на чем практиковаться?

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

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

С наиболее общего ракурса, тема сверток на графах хорошо освещена в обзорной статье “Representation Learning on Graphs: Methods and Applications” [1]. Методам машинного обучения на графах посвящены целые университетские спецкурсы, наиболее известным из которых является Stanford CS224W: Machine Learning with Graphs. По мотивам этого курса есть разбор от русскоязычного сообщества исследователей Sberloga, в котором есть записи обсуждения лекций, примеры кода, разбор разных аспектов теории и практики и многое другое. Также стоит отметить вот эту статью с хабра от ODS, в которой упоминается о схожем сообществе для разбора стенфордского курса и заодно изложены несколько основных подходов к получению скрытых представлений графов (т.н. эмбеддинги).

В более сжатом виде есть несколько серий заметок на эту тему на Medium:

Для области 3D ML методы и алгоритмы, основанные на извлечении информации из графовых структур, являются важным подспорьем. Объекты интереса — это зачастую полигональный меш, который сам по себе является пространственным графом (см. например работу [15]), или облако точек, которое также можно мыслить как графовую структуру, если соединять между собою точки в облаке по определенным правилам (см. например работу [14]). Про различные виды сверток на графах, применительно к задачам 3D ML, можно прочитать в нашем обзоре про алгоритмы семантической сегментации облака точек.

С точки зрения инструментов, в основном исследователи в данной области пользуются либо собственноручно написанными библиотеками, либо библиотеками, которые первоначально предназначались для работы с графами в предметной области (например библиотека python rdkit или python NetworkX). На наш взгляд, наиболее удобной библиотекой для построения собственных глубоких архитектур на основе графовых сверток является PyTorch Geometric (на странице с документацией можно найти различные примеры графовых датасетов, методов их обработки и загрузки, и различных сверточных слоев). В репозитории библиотеки TensorFlow Graphics также можно найти пример “Semantic mesh segmentation”, в котором, с помощью встроенных в библиотеку сверточных операторов, конструируют небольшую глубокую архитектуру для решения задачи семантической сегментации меша. Рекомендуем всем начинающим 3D ML исследователям самостоятельно разобрать описанные выше примеры.

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

Граф как неевклидова структура

Рис.1 Пример из статьи [2]: левые изображения демонстрируют, что стандартная свертка (Euclidean CNN) будет по разному обрабатывать данные в зависимости от типа поверхности к которой ее применяют, что, в свою очередь, мотивирует к созданию геометрических сверток (Geometric CNN, правые изображения).

Свертка — замечательный инструмент, позволяющий “аккумулировать” информацию о близлежащих (локальных) частях в данных. В случае с изображениями, мы естественным образом предполагаем, что соседние пиксели скорее всего связаны семантически (являются частью одного объекта). Поскольку одна и та же свертка применяется ко всем пикселям изображения, оператор, основанный на ней, становится независим к размеру изображения и занимает меньше памяти. Исходя из этого соображения, становится несложно понять, почему сверточные сети стали так популярны для обработки изображений.

Более формально, общие свойства евклидовых и неевклидовых данных были описаны в обзорной статье “Geometric deep learning: going beyond Euclidean data” [2] (всем познающим 3D ML, на наш взгляд, обязательно к ознакомлению).

Кратко перечислим свойства евклидовых данных:

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

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

Рис.2 Слева: изображение из датасета MNIST; справа: граф построенный по пикселям данного изображения. (см. работу [3]).

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

Как создать граф на изображении ниже:

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

В качестве примера можно рассмотреть свертку, определяемую матрицей . Пусть в узлах нашей решетки хранятся некоторые числовые значения, например, интенсивность цвета пикселя записанные в матрицу — . Применение свертки обычно выражено в виде скалярного произведения (dot product) матрицы фильтра на матрицу значений в узлах сетки (это может быть подграф всей сети), совпадающую по размерам с фильтром (см. рисунок ниже). Хороший и подробный туториал по применению сверток к изображениям содержится в статье “A guide to convolution arithmetic for deep learning” [4].

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

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

Кстати, рассмотрение изображений как регулярных графовых сетей приводит к интересному результату. Мы можем рассматривать иное разбиение изображения на составные части нежели исходные пиксели, например каким-либо способом объединять группы пикселей в т.н. “суперпиксели” и строить свертки нерегулярной структуры над ними. Про такой подход к обработке изображений можно прочитать в данной заметке.

Рис.3 Пример построение суперпикселей разного разрешения на изображении из работы [5].

Теперь попробуем обобщить свертки на нерегулярные графы. Здесь мы столкнемся со следующей проблемой: граф в общем виде — совокупность двух множеств (вершины — , и связи между этими вершинами — ), а множества — инвариантный к перестановке элементов тип данных. Это значит, что мы можем случайным образом перемешать вершины графа (с учетом соответствующего перемешивания связей) и при этом сам граф останется прежним, но как было отмечено выше — свертка зависит от порядка элементов.

Поскольку не существует какой-то канонической расстановки вершин произвольного графа, требуется определить операцию свертки так, чтобы она не зависела от этой расстановки. Наиболее популярные способы определить свертку на графе — использование операторов на основе усреднения (averaging) [6] или суммирования (summation) [7] по всем соседям рассматриваемой вершины, с последующим умножением на матрицу весов . Таким образом, мы агрегируем всех соседей вместе с самой вершиной и проецируем граф через свертку в пространство другой размерности. Про различные виды агрегирующих операторов на графах можно прочитать в статье [8].

Рассмотрим для лучшего понимания граф состоящий из 5 вершин на изображении ниже (рис.4). Применяя агрегирующий оператор на основе суммирования для вершины получим новое значение признака этой вершины:

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

Рис.4 Пример нерегулярных графов и схематичное изображение соседей рассматриваемых вершин .

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

Конструируем сверточный слой для графов

Сначала вспомним, как конструируется полносвязный слой в классической полносвязной архитектуре (В качестве примера будем держать в голове классификацию рукописных цифр из MNIST). Пусть — вектор значений на -ом слое, — матрица весов -го слоя. Тогда линейный полносвязный линейный слой может быть записан в виде:

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

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

Рис.5 Неориентированный граф из 5 вершин и его матрица смежности (голубой цвет — 0, желтый — 1) для двух вариантов нумерации вершин графа.

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

В данном случае, матрица dist — матрица смежности для полносвязного графа с вершинами, матрица — матрица смежности с учетом пространственной близости (здесь используется эвристическое соображение о том, что близлежащие пиксели должны сильнее коррелировать друг с другом чем те, что лежат на расстоянии). Этот способ определять матрицы смежности для задач, связанных с обработкой изображений, — популярный, но далеко не единственный (см. альтернативы в работах [2, 9]).

Рис.6 Слева-направо: матрица смежности в форме расстояний между пикселями, матрица смежности в форме пространственной близости, подграф полносвязного графа рассматриваемого изображения .

Теперь, на основе матрицы смежности , мы сможем сконструировать т.н. нормированную матрицу смежности . Ее можно сконструировать разными способами, но два наиболее популярных подхода следующие:

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

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

Можно написать достаточно простой код на основе операторов PyTorch, чтобы увидеть разницу в реализации обычного полносвязного слоя и полносвязного слоя с графовой сверткой:

Полный код для данного примера можно найти в оригинальном репозитории здесь. Кстати, если вы попытаетесь сравнить качество обучения на MNIST для обычной и для графовой модели, вы обнаружите, что качество отличается несущественно. Это происходит по той причине, что для данного конкретного датасета, связи между пикселями в рукописных цифрах и так очень сильны, но что более важно, оператор здесь есть не что иное, как Гауссовский фильтр, поэтому такая архитектура графовой сети приводит фактически к тому, что у нас есть обычная сверточная нейронная сеть с фиксированным Гауссовским фильтром. Чтобы сверточная архитектура на регулярных графах работала лучше, можно применить ряд трюков, которые описаны в работах [10, 11, 12].

Рис.7 Гауссовский фильтр, использовавшийся в нейронной сети, описанной выше (слева) и результат его применения к изображению (справа).

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

Рис.8 2D-фильтр нейронной сети, описанной выше, с центром в красной точке. Усреднение (слева, точность 92,24%), обучение на основе координат (посередине, точность 91,05%), обучение на основе координат с некоторыми трюками (справа, точность 92,39%).

Можно заметить, что фильтр, который мы только что обучили (в середине), выглядит странно. Это связано с тем, что задача довольно сложная, поскольку мы оптимизируем две модели одновременно: модель, которая предсказывает разделяющую поверхность для групп пикселей, и модель, предсказывающая класс цифры. Чтобы узнать лучшие фильтры (например, тот, что справа), нам нужно применить некоторые другие приемы, которые можно найти в работе [13].

Выводы

Графовые нейронные сети (GNN) — это очень гибкое и интересное семейство нейронных сетей, которые могут быть применены к действительно сложным данным. Как всегда, такая гибкость должна иметь определенную цену. В случае GNN — это трудность регуляризации модели путем определения таких операторов как свертка. Исследования в этом направлении продвигаются довольно быстро, так что GNN найдут применение во все более широких областях машинного обучения и компьютерного зрения.

Рис.9 Граф работ по конструированию GNN архитектур из туториала Бориса Князева “Anisotropic, Dynamic, Spectral and Multiscale Filters Defined on Graphs”.

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

Тем из вас, кому стало интересно как же расшифровывается формула с обложки, рекомендуем к ознакомлению статью [6].

Для всех кому интересно углубиться в тему сверток на графах, рекомендуем прочитать оставшиеся два туториала в серии заметок Бориса Князева на Medium.

Источник

Визуализация больших графов для самых маленьких

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

Зачем вообще визуализировать графы?

Найти что искать

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

Похвастаться

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

Получить признаки

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

В чём проблема с большими графами?

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

Что об этом пишут разные умные люди?

Есть пара работ, на которые я хотел бы обратить внимание:
[1] Helen Gibson, Joe Faith and Paul Vickers: “A survey of two-dimensional graph layout techniques for information visualisation”
Ребята сначала разбирают какие бывают подходы к отрисовке графов, поясняют принципы работы, а потом пытаются все их испробовать. Есть очень подробная таблица с информацией о разных алгоритмах, в том числе об их алгоритмической сложности.

[2] Oh-Hyun Kwon, Tarik Crnovrsanin and Kwan-Liu Ma “What Would a Graph Look Like in This Layout? A Machine Learning Approach to Large Graph Visualization”

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

Теория

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

Что такое хорошая укладка?

Очень легко сказать, что что-то выглядит хорошо или плохо, но сложно объяснить машине, как такую оценку дать. Чтобы сделать “хорошую” укладку обычно оптимизируют так называемые “эстетические” метрики, которые формулируются более объективно. Вот некоторые из них:

Минимум пересечений рёбер
Всё просто: когда много пересечений, получается “каша”, когда мало, тогда картинка выглядит “чище”

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

Сообщества группируются в кластера
Это вытекает из предыдущего пункта. Если существуют множества узлов, которые сильнее связаны друг с другом, чем со всем остальным графом, они образуют “сообщество” и на картинке должны выглядеть как плотный кластер

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

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

Какие бывают укладки

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

Force-Directed and Energy-Based

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

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

Важные алгоритмы семейства — Force Atlas, Fruchterman-Reingold, Kamada Kawaii и OpenOrd. Последний алгоритм — использует хитрые оптимизации, например обрубает длинные рёбра для ускорения вычислений, и в качестве побочного эффекта получаются более плотные кластера близких вершин.

Dimension Reduction

Граф можно задавать матрицей смежности, то есть квадратной матрицей NxN, где N — число вершин. Это можно интерпретировать как N объектов в пространстве размерности N. Такое представление позволяет использовать универсальные методы снижения размерности, вроде tSNE, UMAP, PCA и так далее. Другой подход основывается на том, чтобы рассчитать теоретические расстояния между вершинами, основываясь на весах рёбер и знании локальной топологии, а затем попытаться сохранить соотношения между этими расстояниями при переходе в пространства меньшей размерности.

Feature-Based Layout

Обычно данные приходят из реального мира, где у нас есть не только информация о смежности вершин. Вершины являются какими-то реальными объектами со своими свойствами. Вспоминая об этом, мы можем использовать свойства вершин для отображения их на плоскости. Для этого можно использовать любые подходы обычно применяемые для табличных данных. Это уже упомянутые выше методы снижения размерности PCA, UMAP, tSNE, Autoencoders. Либо можно рисовать простой scatter plot (диаграмма рассеяния) для пар признаков и рисовать рёбра уже поверх полученного представления. Отдельно можно упомянуть Hive Plot — интересный метод когда значениям признака соответствуют разные оси направленные из центра, на которых располагают вершины, а рёбра рисуют дугами между ними.

Инструменты для визуализации больших графов

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

GraphViz

Транзакции и адреса блокчейна биткоина до 2011-го года

Настроить параметры бывает сложно

Олдскульный CLI инструмент со своим языком описания графов — dot. На самом деле это пакет с разными укладками на любой случай жизни. Для больших графов там есть инструмент sfdp — относится к классу Force Directed укладок. Преимущества и недостатки этого инструмента в запуске из командной строки. Это очень удобно для воспроизводимости и автоматизации, однако без ползунков и отображения промежуточных результатов настройка параметров становится очень болезненным делом. Ставим параметры, запускаем, ждём без прогрессбара, смотрим результат, меняем параметры, перезапускаем. Умеет писать в svg, png и другие картиночные форматы.

Gephi

Рекомендации 173 тысяч фильмов с iMDB

Несколько миллионов вершин — уже слишком тяжёлая задача

Пожалуй, самый мощный инструмент по своей полноте. Это GUI приложение, которое содержит в себе набор основных укладок, а также множество других инструментов для анализа графов. Сообществом для gephi написано много плагинов, например мой любимый Multigravity Force-Atlas 2 или плагин для экспорта укладки в интерактивную веб-страницу. Также оригинальная имплементация OpenOrd содержится именно в Gephi. В Gephi есть инструменты раскраски вершин и рёбер по их свойствам, настройка подписей, размеров и прочих параметров отрисовки. Есть экспорт в основные форматы изображений, включая векторные.

Очень досадный факт в том, что Gephi уже несколько лет заброшен. Два основных разработчика, не обладают ресурсами чтобы передать свои знания, необходимые для дальнейшей разработки кому-то ещё, заявили что уже не могут больше активно поддерживать Gephi. К другим минусам можно отнести некоторую “дубовость” интерфейса, и отсутствие каких-то очевидных фич, но ничего “подобного только лучше” всё равно никто не написал. Из последних новостей, в блоге проекта появилось заявление о том, что мощности современного WebGL уже обгоняют старый Gephi и есть шансы увидеть его возрождение в виде веб-приложения.

igraph

Граф рекомендаций музыки в lastfm. Источник здесь.

Нельзя не отдать дань этому пакету общего назначения для анализа графов. Одна из самых эффектных графовых визуализаций своего времени была сделана одним из авторов igraph. Он разработал для этого свою укладку DrL. Это был граф рекомендаций музыкальных групп из lastfm. Результат выше.

К минусам можно отнести отвратительную документацию. Как минимум к python api. Проще сразу читать исходники.

LargeViz

Несколько десятков миллионов вершин (транзакций и адресов) в одном из крупнейших кластеров блокчейна биткоина

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

Graphistry

Адреса, которые можно взломать за неделю, и их транзакции

Понятный, но очень ограниченный интерфейс, разумные настройки по умолчанию

Единственный в этом списке коммерческий инструмент. Graphistry — это сервис, который принимает ваши данные и выполняет тяжёлые вычисления на своей стороне. Клиент просто смотрит на красивую картинку в браузере. По сути ничем не лучше gephi, кроме разумных параметров по умолчанию и интерактивности. Реализует только одну укладку: что-то похожее на ForceAtlas. Есть ограничение 800 тысяч на максимальное число вершин или рёбер.

Графовые эмбеддинги

Для безумных размеров тоже есть свой подход. Уже начиная с миллиона вершин при отрисовке имеет смысл смотреть только плотность вершин в разных точках пространства, просто потому что ничего другого увидеть не выйдет. Большая часть алгоритмов придуманных специально для отрисовки графов, на десятках миллионов вершин или рёбер будет работать по много часов, если не суток. Из этой ситуации можно выйти решая немного другую задачу. Есть множество методов получения векторных представлений заданной размерности, отражающих свойства вершин графа. После получения таких представлений остаётся только снизить размерность до 2-х, чтобы получить уже картинку.

Node2Vec

Node2Vec + UMAP

Адаптация обычного word2vec для графов. Вместо последовательностей слов берутся последовательности вершин при случайном обходе графа и отправляются в word2vec вместо слов. Метод учитывает только информацию о соседстве вершин. Обычно этого достаточно.

VERSE

VERSE + UMAP

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

Graph Convolutions

Graph Convolutions + Autoencoder

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

Бонус: немного подробнее о графовых свёртках

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

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

Как нам это сделать?

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

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

Мощь табличных фрейморков в анализе графов

Мы пришли к тому, что у нас есть табличка задающая граф и нам надо считать статистики по каким-то величинам. Таблицы и статистики — это всё есть в pandas, поэтому дальше будет пример реализации именно в нём.

Для начала зададим граф:

Это просто цепочка из 101 вершины связанных друг за другом, как на рисунке.

Затем зададим признаки вершин случайным образом:

И сделаем из этого всего датафреймы pandas:

Теперь зададим саму функцию свёртки:

Что тут происходит

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

Для данного графа это будет выглядеть так

Применяем функцию и рисуем результат:

Исходные признаки, затем исходные и результат первой свёртки, затем исходные и результат двух свёрток.

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

Если хочется немного больше математики

Если вы раньше слышали про графовые свёртки, то скорее всего это было в контексте графовых свёрточных сетей (Graph Convolutional Networks — GCN). Кому-то фокусы с табличками, которые здесь описаны, могут показаться «не тру». На самом деле, использованию графовых свёрток без глубокого обучения посвящена одна очень интересная статья: «Simplifying Graph Convolutional Networks». В ней даётся такое определение свёртки где — это матрица признаков, а — нормализованный лапласиан графа, который задаётся вот так: , здесь — это матрица смежности графа суммированная с единичной матрицей, а — матрица в диагонали которой записаны степени вершин графа. И всё это записывается парой строк в python с использоаванием scipy и numpy:

Здесь sparse — это модуль внутри scipy для работы с разреженными матрицами, adj — матрица смежности, а feats и feats_conv — признаки до и после свёртки. Такой подход более строгий, но очень плохо масштабируется. К тому же, если чуть-чуть вдуматься в смысл происходящего, то это эквивалентно разницы между значением признака в вершине и средним по соседям вершины, то есть вполне решается предыдущей схемой с таблицами, если добавить одну операцию.

Источник