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

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

Например, Cohen et al. проиллюстрируйте в разделе «Вычисление классической центральности близости в масштабе», что вычисление центральности близости в сети из 24 миллионов узлов занимает поразительные 44 222 часа, или около 5 лет (с учетом стандартных вычислительных ресурсов) .

Действительно, центральность промежуточности при применении алгоритма Брандеса имеет временную сложность O (| V || E |), и, следовательно, для больших сетей потребуется постоянно увеличивающееся время выполнения при вычислении этой метрики центральности. С другой стороны, мера центральности степени имеет временную сложность O (| V |) и, следовательно, вычисляется за довольно короткое время выполнения.

План и основные выводы

Схема проекта, который мы сделали с Марком Нидхэмом, выглядит следующим образом: мы предполагаем, что в Neo4j существует определенный граф, на котором аналитик графов хочет вычислить меру гармонической центральности. После того, как мы получили график для изучения из Neo4j, используя драйвер Python, мы загружаем его в нейронную сеть графа (GNN). Эта модель, в свою очередь, генерирует предсказанные значения гармонической центральности, которые затем возвращаются в граф в Neo4j как свойства узла.

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

Мера Harmonic Centrality
Мы выбрали Harmonic Centrality, меру геометрического типа, по той основной причине, что она была описана Boldi и Vigna в их статье Axioms for Centrality . Это единственная метрика центральности, которая удовлетворяет всем аксиомам, разработанным для ранжирования этих метрик. Другими словами; это золотой стандарт показателей центральности, и, конечно же, он является частью библиотеки Neo4j's Graph Data Science.

Напомним, что гармоническая центральность - это мера центральности, основанная на «расстоянии», и усовершенствование меры центральности по близости. Последний оценивает центральность узла на основе среднего расстояния, которое он имеет до всех других узлов в сети. В результате высокая центральность близости означает, что этот конкретный узел может в среднем достигать других узлов за меньшее количество шагов. Основная проблема этого подхода заключается в том, что недостижимые узлы имеют бесконечное расстояние. Чтобы решить эту проблему, Маркиори и Латора предложили в «Гармония в маленьком мире» заменить среднее расстояние «гармоническим средним» всех расстояний. Формально гармоническая центральность узла x определяется как:

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

Реальная сеть
Чтобы проиллюстрировать нашу работу, мы получили график из Стэнфордской платформы анализа сети (SNAP) Стэнфордского университета. В частности, для этой первой версии проекта мы использовали только один набор: soc-Slashdot0811 ('SDot'): ориентированный граф из социальной сети с подписью Slashdot Zoo от 6 ноября 2008 г., состоящий из 77 360 узлов, 905 468 ребер со средней степенью 4,13 и средним коэффициентом кластеризации 0,055.

Графическая нейронная сеть

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

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

Подходом, которым мы будем следовать в этом проекте, будет метод Structure2vec, разработанный Dai et al. в «Дискриминационные внедрения моделей скрытых переменных для структурированных данных». В методе Structure2Vec каждый узел кодируется с учетом двух основных входных данных:

i) любую информацию о конкретных узлах
ii) встраивание всех его соседей.

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

Мы следуем подходу, используемому Mendonca et al. в Приближении показателей централизации сети с использованием встраивания узлов и машинного обучения, где авторы опубликовали свой код TensorFlow по адресу https://github.com/MatheusMRFM/NCA-GE

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

Опять же, у нас есть три скрытых слоя (полностью связанных), которые создают весовые матрицы, где каждый слой использует функцию активации Rectified Linear Unit (Relu).

Обучение модели

Наконец, для обучения модели мы сгенерировали набор данных синтетического графа, применив модель Барабаши-Альберта, где мы сгенерировали 900 обучающих и 100 тестовых графов, где параметры для генерации графиков были сгенерированы случайным образом. Границы количества узлов были установлены в диапазоне от 1000 до 100. Границы ребер, которые должны быть присоединены от нового узла к существующим узлам, были установлены в диапазоне от 3 до 10. В среднем каждый граф состоял из 558 узлов. со средней степенью 13 и средним коэффициентом кластеризации 0,08. Наконец, ранжируются и нормализуются показатели центральности как входных, так и выходных данных. После обучения модели мы протестировали ее в реальной сети Sdot и достигли коэффициента Кендалла Тау около 95%.

Рабочий процесс

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

Шаг 1: загрузите набор данных Sdot в Neo4j
Поскольку набор Sdot не загружен в Neo4j предварительно, и чтобы получить полное представление о В рабочем процессе мы сначала загружаем график в Neo4j, применяя следующий код Cypher.

Шаг 2. Получите график из Neo4j и загрузите его в модель GNN
Второй шаг, с которого начинается настоящая работа, - это загрузка графика в Graph Neural. Сеть от Neo4j. Для этого мы используем драйвер Python Neo4j, чтобы получить график из Neo4j и вернуть его в формате .csv, готовом к обработке.

Шаг 3. Запустите модель нейронной сети Graph и получите прогнозируемые значения
Теперь, когда у нас есть график Sdot в виде файла CSV, мы можем запустить Graph Neural Сетевая модель на нашем локальном компьютере, которая вычисляет приблизительные значения гармонической центральности.

Шаг 4. Установите прогнозируемую меру гармонической центральности как свойство узла графа в Neo4j
После вычисления приблизительных мер гармонической центральности мы снова используем драйвер Python Neo4j. чтобы вернуть полученные значения в Neo4j и присоединить их как свойство Node к графику Sdot, как показано в приведенном ниже коде:

Запрос Neo4j

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

и действительно - мы находим то, что ищем:

Заключение

Как указано во введении, используя драйверы Python Neo4j и развернув графическую нейронную сеть, мы нашли эффективный способ аппроксимации меры центральности менее чем за 10 секунд, тогда как точный алгоритм может легко занять несколько часов. По нашим оценкам, весь рабочий процесс может быть рассчитан менее чем за минуту при достижении высокой точности аппроксимации.

В моем следующем посте мы сравним оценки гармонической центральности, вычисленные нейронной сетью Graph, с оценками, вычисленными алгоритмом в библиотеке Graph Data Science Library.