Машинное обучение на графах, часть 1

Машинное обучение на графах, часть 1

Сбор базовой статистики

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

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

Предварительные мероприятия

Я предполагаю знакомство с основными концепциями графов. Я буду рассматривать неориентированные графы без петель (узлы, соединенные между собой ребром), но это только для простоты представления. Граф обозначается G = (V, E), где V - это набор узлов или вершин, а E - это набор ребер. . Количество узлов обозначается n = | V | и количество ребер на m = | E |.

Какую статистику на графике искать?

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

• Распределение степеней. Степенное распределение двух реальных сетей показано на рисунке 1. Первый график получен из электронной переписки в учреждении ЕС, а второй график - это граф соавторства из базы данных DBLP. Мы заметили, что наиболее распространенная степень узла в графе электронной почты - 1, что означает, что большинство людей общаются только с одним человеком. В графе соавторства у большинства авторов есть два-три соавтора.

• Плотность графика. Количество определяется как

Объяснение простое: максимально возможное количество ребер равно n * (n-1) / 2, поскольку каждый узел может быть связан ровно с n-1 другими узлами, а ребра неориентированы. Он измеряет, насколько близок граф к полносвязному графу или клике. Большинство реальных сетей очень разрежены, поэтому этот показатель в большинстве случаев не очень информативен.

• Подключенные компоненты. Мы говорим, что узел u достижим из узла v, если существует путь, последовательность ребер, между u и v. В связном компоненте каждый узел доступен из любого другого узла в компоненте. Количество и соответствующий размер связанных компонентов могут предоставить информацию о графе. Однако в большинстве случаев нас интересуют связные графы, состоящие из одной компоненты связности.
• Диаметр графика. Кратчайший путь между двумя узлами u и v - это минимальное количество ребер, которые необходимо пройти, чтобы достичь v после запуска в u. Диаметр графа - это максимальная длина кратчайшего пути между любыми двумя узлами графа. Если граф имеет более одной компоненты связности, то его диаметр бесконечен. В таком случае нас интересует диаметр каждого связного компонента. Диаметр графа можно использовать, чтобы различать разные типы сетей. Например, сети метро, ​​вероятно, будут иметь больший диаметр, чем небольшие социальные сети.
• Количество треугольников и коэффициент транзитивности. В теории графов есть фундаментальное понятие графы Эрдеша – Реньи. Это теоретическая модель, в которой ребра между узлами генерируются случайным образом, каждое с фиксированной вероятностью p, независимо от других ребер. Реальные графы сильно отличаются от графов Эрдеша – Реньи, поскольку рёбра не создаются случайным образом независимо друг от друга. В частности, для большинства реальных графиков часто считается, что друзья моих друзей также являются моими друзьями. Это побудило исследователей рассматривать треугольники как фундаментальную единицу в аналитике графов [1]. На высоком уровне количество треугольников показывает, насколько наш график отличается от случайного.

Коэффициент транзитивности графа определяется как

В приведенном выше числителе указано количество треугольников, умноженное на 3, а знаменатель обозначает количество 2-путей в графе, которые можно вычислить как:

На графике на рисунке 2 есть два треугольника, а именно (u, v, w) и (u, v, z). 2-пути - это последовательности из 3 узлов, соединенных ребром, например z-u-w. Обратите внимание, что каждая пара соседей данного узла приводит к 2-пути, отсюда приведенная выше формула для общего количества 2-путей. Мы умножаем количество треугольников на 3, потому что мы считаем каждый из трех его 2-путей. Таким образом, коэффициент транзитивности - это значение от 0 (отсутствие треугольников) до 1 (полносвязные графики).

На рисунке 2 количество 2-трактов равно 8, поэтому коэффициент транзитивности равен 0,75.

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

• Локальное количество треугольников и коэффициент кластеризации. Определен коэффициент локальной кластеризации узла u.

то есть количество треугольников, в которых вершиной u является узел, деленное на количество 2-путей с центром в u.

Затем это обобщается на глобальный коэффициент кластеризации

На рисунке 2 узел u имеет коэффициент локальной кластеризации 2/3, а коэффициент глобальной кластеризации графа равен (2/3 + 2/3 + 1 + 1) / 4 = 0,833.

Наконец, мы хотели бы отметить, что в литературе коэффициент транзитивности иногда называют коэффициентом кластеризации, а глобальный коэффициент кластеризации, как определено выше, называется средним коэффициентом кластеризации. Путаница в обозначениях проистекает из того факта, что Уоттс и Строгац ошибочно заявили в своей основополагающей статье [1], что коэффициент транзитивности и коэффициент кластеризации идентичны.

Как посчитать количество треугольников?

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

import networkx as nx
import numpy as np
G = nx.Graph()
for u, v in <list of edges or edge generator>:
      G.add_edge(u, v)

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

След определяется как сумма диагональных элементов матрицы. Каждая диагональная запись в A³ измеряет количество путей длиной ровно 3 от соответствующего узла до самого себя. Рассмотрим треугольник между тремя узлами (u, v, w). Есть 6 перестановок этих трех узлов, поэтому нам нужно разделить трассу на 6. В Python код выглядит как

def count_triangles(G):
   A = nx.to_scipy_sparse_matrix(G)
   A2 = A.dot(A)
   A3 = A2.dot(A)
   return A3.diagonal().sum()/6

Обратите внимание, что выше используется умножение разреженных матриц. Однако не гарантируется, что третья степень матрицы смежности будет разреженной, особенно для графов небольшого диаметра, и вычисления могут стать узким местом. В таком случае я рекомендую использовать алгоритм Дулиона [2]. Doulion работает, выбирая ребра из исходного графа. Каждое ребро сохраняется с вероятностью p. Таким образом, треугольник выживает в разреженном графе с вероятностью p³. Мы оцениваем количество треугольников в исходном графе, умножая количество треугольников в разреженном графе на 1 / p³.

def sparsify_graph(G, p):
    G_sparse = nx.Graph()
    for u,v in G.edges():
        if np.random.random() <= p:
            G_sparse.add_edge(u,v)
    return G_sparse

Провожу эксперимент с графом, полученным из сети DBLP. Граф состоит из 317 080 узлов и чуть более 1 миллиона ребер. Путем выборки рёбер с вероятностью 10% я получил следующее время работы для алгоритма точного подсчета и для Doulion. И достигнутое приближение количества треугольников отличное.

Elapsed time exact:   13.21 secs
Elapsed time Doulion: 1.19 secs
Approximation exact/estimated: 1.030

Еще немного расширенной статистики.

Вкратце отметим, что есть и более продвинутая статистика графов.

• Центральность посредничества. Эта мера фиксирует влияние узлов на графике. Для каждого узла u мы подсчитываем, сколько кратчайших путей между парами узлов проходит через u. Узлы с высокой промежуточностью считаются более важными в сети. Распределение оценок центральности промежуточности позволяет нам лучше понять структуру графа. Однако вычислительная сложность для вычисления центральности для всех узлов составляет O (m * n).
• Плотно связанные подграфы. Важной темой исследования является обнаружение плотносвязных подграфов [3]. Это подграфы в исходном графе, где почти все пары узлов соединены ребром. Это основа алгоритмов обнаружения сообществ. Но количество и плотность этих плотных компонентов также являются важной статистикой.
• Мотивы графов майнинга. Выявление частых графических паттернов - активная область исследований [4]. Он обобщает алгоритмы подсчета треугольников на поиск и подсчет более сложных подграфов или мотивов . Эти подсчеты можно использовать в задачах классификации графов. На рисунке 3 я показываю три разных мотива на 4 узлах. Однако подсчет мотивов может быть дорогостоящим в вычислительном отношении и ограничен небольшими подграфами. Можно утверждать, что успех нейронных сетей с графами основан на их способности изучать сложные мотивы, относящиеся к рассматриваемой проблеме.

Код

Код для приведенных выше примеров можно найти по адресу: https://github.com/konstantinkutzkov/ML_on_graphs/

[1] Дункан Дж. Уоттс, Стивен Х. Строгац. Коллективная динамика сетей« маленького мира ». Nature 393, 1998.

[2] Харалампос Э. Цуракакис, У Канг, Гэри Л. Миллер и Христос Фалаутсос. ДОУЛЬ: Счет треугольников в массивных графах с монетой. КДД 2009.

[3] Харалампос Э. Цуракакис, Франческо Бонки, Аристидес Гионис,
Франческо Гулло и Мария А. Циарли. Плотнее, чем самый плотный подграф:
Извлечение оптимальных квазиклик с гарантиями качества. КДД 2013.

[4] Гую Хан и Хариш Сетху. Болтливое блуждание: быстрый и точный анализ статистики мотивов в больших графах. ICDM 2016.