Что такое граф и как его представляют для нейросетей (adjacency matrix, edge list)?

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

Основные способы представления графа:

• Матрица смежности (adjacency matrix): квадратная матрица размера N×N, где N — число вершин. Элемент в позиции (i, j) равен 1 (или весу ребра), если существует ребро из вершины i в вершину j, иначе 0. Удобна для быстрого доступа, но может занимать много памяти при больших разреженных графах.

• Список рёбер (edge list): список пар (i, j), где каждая пара представляет ребро между вершинами i и j. Более компактное представление для разреженных графов.

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

Пример матрицы смежности для графа с 3 вершинами и рёбрами 0→1, 1→2:

adjacency_matrix = [
  [0, 1, 0],
  [0, 0, 1],
  [0, 0, 0]
]

Пример списка рёбер:

edge_list = [(0, 1), (1, 2)]