Теория графов для машинного обучения
Узлы, рёбра, матрица смежности, типы графов, признаки графов, представления социальных сетей
«Теория графов для машинного обучения» — бесплатный урок Learn AI with Python на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Learn AI with Python, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Learn AI with Python содержит 4 уроков всего.
Что такое граф
Граф моделирует сущности и отношения между ними. Формально граф — это G = (V, E), где V — множество вершин (узлов), а E — множество рёбер, соединяющих пары узлов. Многие реальные системы по своей природе являются графами.
Узлы и рёбра
Каждый узел представляет сущность (пользователя, атом, веб-страницу). Каждое ребро представляет отношение (дружбу, химическую связь, гиперссылку). Машинное обучение на графах использует эту структуру связей, а не только изолированные примеры.
Матрица смежности
Матрица смежности A кодирует, какие узлы соединены. Для n узлов A имеет размер n на n; A[i][j] = 1, если ребро соединяет узлы i и j, и 0 в противном случае.
import numpy as np
# Triangle: 0-1, 1-2, 0-2
A = np.array([
[0, 1, 1],
[1, 0, 1],
[1, 1, 0],
])Признаки узлов X
Помимо структуры, каждый узел обычно содержит вектор признаков. Объединённые векторы образуют матрицу признаков X формы (num_nodes, num_features). В социальном графе строка может содержать возраст пользователя, количество публикаций и возраст учётной записи.
X = np.array([
[25, 120, 3.0], # node 0
[31, 45, 5.5], # node 1
[22, 300, 1.2], # node 2
])Матрица степеней
Степень узла — это количество его рёбер. Матрица степеней D является диагональной: каждый её диагональный элемент равен степени соответствующего узла. Это строительный блок лапласиана графа.
D = np.diag(A.sum(axis=1))
# Each diagonal entry = number of neighborsЛапласиан графа
Лапласиан графа определяется как L = D - A. Он отражает различия значений между соединёнными узлами и лежит в основе спектральной теории графов и многих формулировок GNN.
L = D - A
print(L)Почему важен лапласиан
Собственные значения и собственные векторы лапласиана раскрывают глобальную структуру: связность, кластеры и гладкость. Графовые свёртки часто выводятся из лапласиана, поэтому понимание L = D - A важно для понимания GNN.
Ориентированные и неориентированные графы
В неориентированном графе ребро не имеет направления (как дружба), поэтому A симметрична. В ориентированном графе рёбра направлены в одну сторону (как подписка или цитирование), поэтому A может быть несимметричной: A[i][j] может отличаться от A[j][i].
# Directed: 0 -> 1 but not 1 -> 0
A_dir = np.array([
[0, 1, 0],
[0, 0, 1],
[0, 0, 0],
])Взвешенные графы
Рёбра могут иметь веса, отражающие силу связи или расстояние. В таком случае элементы матрицы смежности являются вещественными числами, а не только 0 или 1. В дорожной сети весом ребра может быть время в пути, а в графе сходства — косинусное сходство.
Эффективное представление рёбер
Для больших разреженных графов матрица смежности расходует память впустую, поскольку большинство её элементов равны нулю. Вместо этого библиотеки машинного обучения хранят рёбра в виде списка рёбер (формат COO): два массива задают исходный и целевой узел каждого ребра. В PyTorch Geometric это называется edge_index.
# Triangle edges as edge_index [2, num_edges]
edge_index = [
[0, 0, 1], # sources
[1, 2, 2], # targets
]Применения машинного обучения на графах
Графы встречаются повсюду:
- социальные графы: рекомендации друзей, выявление сообществ
- молекулярные графы: предсказание свойств молекул (атомы = узлы, связи = рёбра)
- графы знаний: предсказание связей между сущностями и отношениями
- веб-графы и графы цитирования: ранжирование и классификация
Быстрая проверка
Проверьте свои знания теории графов.
Итоги
Вы изучили основы теории графов для машинного обучения:
- Граф — это
G = (V, E), состоящий из узлов и рёбер - Матрица смежности A кодирует связность, а X содержит признаки узлов
- Лапласиан графа задаётся формулой
L = D - A - Графы могут быть ориентированными или неориентированными, взвешенными или невзвешенными
- Графы применяются в социальных, молекулярных графах и графах знаний
Часто задаваемые вопросы
Урок «Теория графов для машинного обучения» бесплатный?
Да — полный текст урока «Теория графов для машинного обучения» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Learn AI with Python, подпишись на CoddyKit PRO. Курс Learn AI with Python содержит 4 уроков всего.
Чему я научусь в уроке «Теория графов для машинного обучения»?
Узлы, рёбра, матрица смежности, типы графов, признаки графов, представления социальных сетей Ты практикуешь Learn AI with Python с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Learn AI with Python?
Предыдущий опыт не требуется. Learn AI with Python на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Теория графов для машинного обучения»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Learn AI with Python?
Да. Каждый урок Learn AI with Python включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Теория графов для машинного обучения
- Графовые сверточные сети (GCN)
- Классификация узлов с GNN
- Предсказание связей и классификация графов