Теория графов для машинного обучения

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

Тип: Реализация Язык: Python Предварительные требования: Фаза 1, уроки 01–03 (линейная алгебра, матрицы) Время: ~90 минут

Цели обучения

• Создать класс графа с представлениями в виде матрицы/списка смежности и реализовать обходы BFS и DFS.
• Вычислять лапласиан графа и использовать его собственные значения для обнаружения связных компонент и кластеризации узлов.
• Реализовать один раунд передачи сообщений в стиле GNN как умножение на нормализованную матрицу смежности.
• Применять спектральную кластеризацию для разбиения графа с помощью вектора Фидлера.

Проблема

Социальные сети, молекулы, базы знаний, сети цитирования, дорожные карты — всё это графы. Традиционное ML рассматривает данные как плоские таблицы: каждая строка независима, а каждый признак занимает столбец. Но когда важна структура связей, таблицы не справляются.

Рассмотрим социальную сеть. Вы хотите предсказать, какой продукт купит пользователь. Его история покупок важна, но история покупок его друзей важнее. Сигнал несут связи.

Или рассмотрим молекулу. Вы хотите предсказать, свяжется ли она с белком. Атомы важны, но по-настоящему важно то, как они соединены друг с другом. Структура и есть данные.

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

Вам нужны четыре вещи:

1. Способ представлять графы матрицами (чтобы их можно было перемножать).
2. Алгоритмы обхода для исследования структуры графа.
3. Лапласиан — важнейшая матрица в спектральной теории графов.
4. Передача сообщений — операция, которая обеспечивает работу GNN.

Концепция

Графы: узлы и рёбра

Граф G = (V, E) состоит из вершин (узлов) V и рёбер E. Каждое ребро соединяет два узла.

Ориентированные и неориентированные графы. В неориентированном графе ребро (u, v) означает, что u соединён с v И v соединён с u. В ориентированном графе (диграфе) ребро (u, v) означает, что u указывает на v, но не обязательно наоборот.

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

Тип графа	Пример
Неориентированный, невзвешенный	Сеть дружеских связей Facebook
Ориентированный, невзвешенный	Сеть подписок Twitter
Неориентированный, взвешенный	Дорожная карта (расстояния)
Ориентированный, взвешенный	Ссылки веб-страниц (оценки PageRank)

Матрица смежности

Матрица смежности A — основное представление. Для графа с n узлами:

A[i][j] = 1    if there is an edge from node i to node j
A[i][j] = 0    otherwise

Для неориентированных графов A симметрична: A[i][j] = A[j][i]. Для взвешенных графов A[i][j] = weight of edge (i, j).

Пример — треугольник:

Nodes: 0, 1, 2
Edges: (0,1), (1,2), (0,2)

A = [[0, 1, 1],
     [1, 0, 1],
     [1, 1, 0]]

Матрица смежности — вход для каждой GNN. Матричные операции над A соответствуют операциям над графом.

Степень

Степень узла — это число рёбер, присоединённых к нему. Для ориентированных графов есть входящая степень (рёбра, входящие в узел) и исходящая степень (рёбра, исходящие из него).

Матрица степеней D диагональна:

D[i][i] = degree of node i
D[i][j] = 0    for i != j

Для примера с треугольником: D = diag(2, 2, 2), потому что каждый узел соединён с двумя другими.

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

BFS и DFS

Это два фундаментальных алгоритма обхода графов. Нужны оба.

Поиск в ширину (Breadth-First Search, BFS): сначала исследует всех соседей, затем соседей соседей. Использует очередь (FIFO).

BFS from node 0:
  Visit 0
  Queue: [1, 2]        (neighbors of 0)
  Visit 1
  Queue: [2, 3]        (add neighbors of 1)
  Visit 2
  Queue: [3]           (neighbors of 2 already visited)
  Visit 3
  Queue: []            (done)

BFS находит кратчайшие пути в невзвешенных графах. Расстояние от старта до любого узла равно уровню BFS, на котором этот узел впервые обнаружен. Поэтому BFS применяют для расстояний в числе переходов (hop-count) в социальных сетях.

Поиск в глубину (Depth-First Search, DFS): идёт как можно глубже, прежде чем вернуться назад. Использует стек (LIFO) или рекурсию.

DFS from node 0:
  Visit 0
  Stack: [1, 2]        (neighbors of 0)
  Visit 2               (pop from stack)
  Stack: [1, 3]         (add neighbors of 2)
  Visit 3               (pop from stack)
  Stack: [1]
  Visit 1               (pop from stack)
  Stack: []             (done)

DFS полезен для:

• Поиска связных компонент (запускайте DFS из непосещённых узлов).
• Обнаружения циклов (обратные рёбра в дереве DFS).
• Топологической сортировки (обратный порядок завершения DFS).

Алгоритм	Структура данных	Находит	Сценарий использования
BFS	Очередь	Кратчайшие пути	Расстояние в социальной сети, обход графа знаний
DFS	Стек	Компоненты, циклы	Связность, топологическая сортировка

Лапласиан графа

L = D - A. Это важнейшая матрица в спектральной теории графов.

Для треугольника:

D = [[2, 0, 0],    A = [[0, 1, 1],    L = [[2, -1, -1],
     [0, 2, 0],         [1, 0, 1],         [-1, 2, -1],
     [0, 0, 2]]         [1, 1, 0]]         [-1, -1,  2]]

Лапласиан обладает замечательными свойствами:

1. L положительно полуопределена. Все собственные значения >= 0.

2. Число нулевых собственных значений равно числу связных компонент. У связного графа ровно одно нулевое собственное значение. У графа с 3 несвязанными компонентами их три.

3. Наименьшее ненулевое собственное значение (значение Фидлера) измеряет связность. Большое значение Фидлера означает, что граф хорошо связан. Малое означает, что в графе есть слабое место — узкое горлышко.

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

Спектральные свойства

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

Спектральная кластеризация работает так:

1. Вычислите лапласиан L.
2. Найдите k наименьших собственных векторов L (пропустите первый, который для связных графов состоит из единиц).
3. Используйте эти собственные векторы как новые координаты для каждого узла.
4. Запустите k-means на этих координатах.

Почему это работает? Собственные векторы L кодируют наиболее «гладкие» функции на графе. У хорошо соединённых узлов получаются близкие значения собственных векторов. У узлов, разделённых узким горлышком, значения различаются. Собственные векторы естественным образом разделяют кластеры.

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

Передача сообщений

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

h_v^(k+1) = UPDATE(h_v^(k), AGGREGATE({h_u^(k) : u in neighbors(v)}))

В простейшей форме AGGREGATE = mean, а UPDATE = линейное преобразование + функция активации:

h_v^(k+1) = sigma(W * mean({h_u^(k) : u in neighbors(v)}))

Это замаскированное матричное умножение. Если H — матрица всех признаков узлов, а A — матрица смежности:

H^(k+1) = sigma(A_norm * H^(k) * W)

где A_norm — нормализованная матрица смежности (сумма каждой строки равна 1).

Один раунд передачи сообщений позволяет каждому узлу «увидеть» непосредственных соседей. Два раунда позволяют увидеть соседей соседей. K раундов дают каждому узлу информацию из K-hop окрестности.

Понятия и применения в ML

Понятие	Применение в ML
Матрица смежности	Входное представление GNN
Лапласиан графа	Спектральная кластеризация, обнаружение сообществ
BFS/DFS	Обход графов знаний, поиск пути
Распределение степеней	Важность узлов, инженерия признаков
Передача сообщений	Слои GNN (GCN, GAT, GraphSAGE)
Собственные значения L	Обнаружение сообществ, разбиение графа
Спектральная кластеризация	Неконтролируемая группировка узлов
PageRank	Важность узлов, веб-поиск

graph-degree-distribution

Реализуйте

Шаг 1: класс Graph с нуля

class Graph:
    def __init__(self, n_nodes, directed=False):
        self.n = n_nodes
        self.directed = directed
        self.adj = {i: {} for i in range(n_nodes)}

    def add_edge(self, u, v, weight=1.0):
        self.adj[u][v] = weight
        if not self.directed:
            self.adj[v][u] = weight

    def neighbors(self, node):
        return list(self.adj[node].keys())

    def degree(self, node):
        return len(self.adj[node])

    def adjacency_matrix(self):
        import numpy as np
        A = np.zeros((self.n, self.n))
        for u in range(self.n):
            for v, w in self.adj[u].items():
                A[u][v] = w
        return A

    def degree_matrix(self):
        import numpy as np
        D = np.zeros((self.n, self.n))
        for i in range(self.n):
            D[i][i] = self.degree(i)
        return D

    def laplacian(self):
        return self.degree_matrix() - self.adjacency_matrix()

Список смежности (self.adj) эффективно хранит соседей. При преобразовании в матрицу смежности используется numpy, потому что он необходим для всех спектральных операций.

Шаг 2: BFS и DFS

from collections import deque

def bfs(graph, start):
    visited = set()
    order = []
    distances = {}
    queue = deque([(start, 0)])
    visited.add(start)
    while queue:
        node, dist = queue.popleft()
        order.append(node)
        distances[node] = dist
        for neighbor in graph.neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return order, distances


def dfs(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph.neighbors(node)):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

BFS использует deque (двустороннюю очередь) для popleft со сложностью O(1). DFS использует список как стек. Оба посещают каждый узел ровно один раз — время O(V + E).

Шаг 3: связные компоненты и собственные значения лапласиана

def connected_components(graph):
    visited = set()
    components = []
    for node in range(graph.n):
        if node not in visited:
            order, _ = bfs(graph, node)
            visited.update(order)
            components.append(order)
    return components


def laplacian_eigenvalues(graph):
    import numpy as np
    L = graph.laplacian()
    eigenvalues = np.linalg.eigvalsh(L)
    return eigenvalues

eigvalsh предназначена для симметричных матриц — лапласиан всегда симметричен для неориентированных графов. Функция возвращает собственные значения в порядке возрастания. Посчитайте нули, чтобы найти количество связных компонент.

Шаг 4: спектральная кластеризация

def spectral_clustering(graph, k=2):
    import numpy as np
    L = graph.laplacian()
    eigenvalues, eigenvectors = np.linalg.eigh(L)
    features = eigenvectors[:, 1:k+1]

    labels = np.zeros(graph.n, dtype=int)
    for i in range(graph.n):
        if features[i, 0] >= 0:
            labels[i] = 0
        else:
            labels[i] = 1
    return labels

При k=2 знак вектора Фидлера разбивает граф на два кластера. При k>2 следует запустить k-means на первых k собственных векторах (исключая тривиальный вектор из единиц).

Шаг 5: передача сообщений

def message_passing(graph, features, weight_matrix):
    import numpy as np
    A = graph.adjacency_matrix()
    row_sums = A.sum(axis=1, keepdims=True)
    row_sums[row_sums == 0] = 1
    A_norm = A / row_sums
    aggregated = A_norm @ features
    output = aggregated @ weight_matrix
    return output

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

Используйте

С networkx и numpy те же операции выполняются одной строкой:

import networkx as nx
import numpy as np

G = nx.karate_club_graph()

A = nx.adjacency_matrix(G).toarray()
L = nx.laplacian_matrix(G).toarray()

eigenvalues = np.linalg.eigvalsh(L.astype(float))
print(f"Smallest eigenvalues: {eigenvalues[:5]}")
print(f"Connected components: {nx.number_connected_components(G)}")

communities = nx.community.greedy_modularity_communities(G)
print(f"Communities found: {len(communities)}")

pr = nx.pagerank(G)
top_nodes = sorted(pr.items(), key=lambda x: x[1], reverse=True)[:5]
print(f"Top 5 PageRank nodes: {top_nodes}")

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

Спектральный анализ в numpy

import numpy as np

A = np.array([
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0]
])

D = np.diag(A.sum(axis=1))
L = D - A

eigenvalues, eigenvectors = np.linalg.eigh(L)
print(f"Eigenvalues: {np.round(eigenvalues, 4)}")
print(f"Fiedler value: {eigenvalues[1]:.4f}")
print(f"Fiedler vector: {np.round(eigenvectors[:, 1], 4)}")

fiedler = eigenvectors[:, 1]
group_a = np.where(fiedler >= 0)[0]
group_b = np.where(fiedler < 0)[0]
print(f"Cluster A: {group_a}")
print(f"Cluster B: {group_b}")

Вектор Фидлера выполняет основную работу. Положительные элементы относятся к одному кластеру, отрицательные — к другому. Не нужна итеративная оптимизация — достаточно одного разложения на собственные значения и векторы.

Доведите до результата

Этот урок создаёт:

• outputs/skill-graph-analysis.md — справочник навыка анализа данных с графовой структурой.

Связи

Понятие	Где встречается
Матрица смежности	Вход GCN, GAT, GraphSAGE
Лапласиан	Спектральная кластеризация, фильтры ChebNet
BFS	Обход графа знаний, запросы кратчайшего пути
Передача сообщений	Каждый слой GNN, нейронная передача сообщений
Спектральный зазор	Связность графа, время смешивания случайных блужданий
Распределение степеней	Сети со степенным законом, инженерия признаков узлов
Связные компоненты	Предобработка, работа с несвязными графами
PageRank	Ранжирование важности узлов, инициализация attention

GNN заслуживают отдельного упоминания. Операция графовой свёртки в GCN (Kipf & Welling, 2017) использует матрицу смежности с добавленными self-loops, A_hat = A + I:

H^(l+1) = sigma(D_hat^(-1/2) * A_hat * D_hat^(-1/2) * H^(l) * W^(l))

где A_hat = A + I (смежность плюс self-loops), а D_hat — матрица степеней A_hat. Self-loops гарантируют, что при агрегации каждый узел включает собственные признаки. Это в точности передача сообщений с симметричной нормализацией. D_hat^(-1/2) * A_hat * D_hat^(-1/2) — нормализованная матрица смежности. Лапласиан появляется потому, что эта нормализация связана с L_sym = I - D^(-1/2) * A * D^(-1/2). Понимать лапласиан — значит понимать, почему работают GCN.

Упражнения

1. Реализуйте PageRank с нуля. Начните с равномерных оценок. На каждом шаге: score(v) = (1-d)/n + d * sum(score(u)/out_degree(u)) для всех u, указывающих на v. Используйте d=0.85. Выполняйте до сходимости (изменение < 1e-6). Проверьте на небольшом веб-графе.

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

3. Реализуйте алгоритм Дейкстры для кратчайших путей во взвешенных графах. Сравните результаты с BFS на том же графе с равномерными весами.

4. Постройте двухслойную сеть передачи сообщений. Дважды примените передачу сообщений с разными матрицами весов. Покажите, что после 2 раундов каждый узел имеет информацию из своей 2-hop окрестности.

5. Проанализируйте граф реального мира. Используйте граф Karate Club (34 узла, 78 рёбер). Вычислите распределение степеней, собственные значения лапласиана и спектральную кластеризацию. Сравните результат спектральной кластеризации с известным истинным разбиением.

Ключевые термины

Термин	Как обычно говорят	Что это на самом деле означает
Граф	«Узлы и рёбра»	Математическая структура G=(V,E), кодирующая попарные отношения
Матрица смежности	«Таблица связей»	Матрица n x n, где A[i][j] = 1, если узлы i и j соединены
Степень	«Насколько связан узел»	Число рёбер, касающихся узла
Лапласиан	«D минус A»	L = D - A, матрица, чьи собственные значения раскрывают структуру графа
Значение Фидлера	«Алгебраическая связность»	Наименьшее ненулевое собственное значение L, измеряющее, насколько хорошо связан граф
BFS	«Поиск по уровням»	Обход, который посещает всех соседей до углубления; находит кратчайшие пути
DFS	«Сначала вглубь»	Обход, который идёт по одному пути до конца перед возвратом
Передача сообщений	«Узлы разговаривают с соседями»	Каждый узел агрегирует информацию от соседей; ядро GNN
Спектральная кластеризация	«Кластеризация по собственным векторам»	Разбиение графа с использованием собственных векторов его лапласиана
Связная компонента	«Отдельная часть»	Максимальный подграф, в котором каждый узел может достичь каждого другого

Дополнительное чтение

• Kipf & Welling (2017) — «Semi-Supervised Classification with Graph Convolutional Networks». Статья, запустившая современные GNN. Показывает, что спектральные графовые свёртки упрощаются до передачи сообщений.
• Spielman (2012) — «Spectral Graph Theory», конспекты лекций. Каноническое введение в лапласианы, спектральные зазоры и разбиение графов.
• Hamilton (2020) — «Graph Representation Learning». Книга, охватывающая GNN от основ до приложений.
• Bronstein et al. (2021) — «Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges». Статья о единой концептуальной рамке.
• Veličković et al. (2018) — «Graph Attention Networks». Расширяет передачу сообщений механизмами attention.

---

Источник: Graph Theory for Machine Learning Навигация: ← 01.20 — Преобразование Фурье · ↑ Фаза 1 — Математические основы · Полный каталог · → 01.22 — Стохастические процессы