Графические методы глубокого обучения на больших графах

Иногда мы сталкиваемся с большими графиками, которые вынуждают нас выходить за пределы доступной памяти нашего графического процессора или процессора. В этих случаях мы можем использовать методы выборки графов. PyTorch Geometric - это библиотека для глубокого обучения графов, которая позволяет нам легко реализовать многие архитектуры графических нейронных сетей. Библиотека содержит множество стандартных наборов данных для глубокого обучения графов, таких как Cora, Citeseer и Pubmed. Но в последнее время в открытых наборах данных с графическим интерфейсом появилась тенденция к использованию крупномасштабных сетей, таких как Open Graph Benchmark (OGB) [3]. В OGB различные наборы данных варьируются от маленьких сетей, таких как ogbn-arxiv (169 343 узла), до больших наборов данных, таких как ogbn-paper100M (111 059 956 узлов). Возможно, ogbn-arxiv может уместиться в памяти, если вы просто выполняете классификацию узлов с небольшим GCN или что-то в этом роде, но попробуйте что-нибудь помимо этого или используйте средний или большой набор данных в OGB, и вам, возможно, придется прибегнуть к выборке графа.

Есть разные способы пробовать большой график, и я попытаюсь охватить два из них.

  1. NeighborSampler

2. GraphSAINTSampler

Класс NeighborSampler взят из статьи GraphSAGE, Обучение индуктивному представлению на больших графах [2] . Если вы раньше не использовали SAGEConv, вы можете думать об этом как об обучении функции, которая выводит вложения узлов на основе их соседства, а не непосредственно в изучении всех вложений узлов. Это делает его особенно полезным для индуктивных задач, поскольку вы можете передавать узлы GNN, которых он никогда раньше не видел.

Я набросал абстрактный вид трехслойного NeighborSampler GNN с равными размерами ниже, где каждый слой разбит на образец окрестности двудольного графа.

Я пытаюсь нарисовать исходные узлы синим цветом, а целевые узлы - красным. Как видите, целевые узлы также имеют петли, поэтому они представлены слева и справа от двудольного графа. Вот как выглядит код:

train_loader = NeighborSampler(data.edge_index, node_idx=train_idx, 
                               sizes=[15, 10, 5], batch_size=1024, 
                               shuffle=True, num_workers=12)

sizes указывает количество соседей для выборки для каждого исходного узла. Представьте, что мы начинаем с набора узлов, для которых мы хотим вычислить вложения (это последние красные узлы в слое 3 изображения выше). Затем мы вычисляем все образцы, как указано в гиперпараметрах, и в конечном итоге они возвращаются нам - в обратном порядке. Это означает, что по мере прохождения всех слоев мы в конце получаем только те вложения узлов, которые нам интересны.

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

Из Пример GraphSAGE в PyTorch Geometric в наборе данных ogbn-products мы видим, что train_loader состоит из batch_size, n_id иadjs.

for batch_size, n_id, adjs in train_loader:
    ...
    out = model(x[n_id], adjs)
    ...

n_id - это все идентификаторы каждого узла, используемого в процедуре выборки, включая выбранных соседей и исходных узлов. Передав нашу модель x[n_id], мы изолируем векторы признаков узлов только тех узлов, которые используются в вычислениях этого пакета. Есть 3 adj inadjs, которые состоят из edge_index, e_id и size. Итак, на прямом проходе модели SAGE в PyTorch Geometric у нас есть:

def forward(self, x, adjs): 
    for i, (edge_index, _, size) in enumerate(adjs): 
        x_target = x[:size[1]] 
        x = self.convs[i]((x, x_target), edge_index)            
        if i != self.num_layers - 1:                
            x = F.relu(x) 
            x = F.dropout(x, p=0.5, training=self.training) 
    return x.log_softmax(dim=-1)

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

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

GraphSAINTSampler позволяет работать с фактическими подграфами исходного набора обучающих данных и повторно записывает идентификаторы узлов с 0 на n, где n - это число. узлов в подграфе.

У родительского класса GraphSAINTSampler есть три дочерних класса: GraphSAINTNodeSampler, GraphSAINTEdgeSampler и GraphSAINTRandomWalkSampler. Каждый из этих классов использует свои соответствующие схемы выборки для вычисления важности узлов, что переводится в распределение вероятностей для выборки [5]. Этот начальный семплер похож на этап предварительной обработки, который оценивает вероятность узла v в V и ребра e в E отбираются. Эта вероятность используется позже как коэффициент нормализации на подграфе [4].

Вот пример GraphSAINTRandomWalkSampler в примере graph_saint в PyTorch Geometric.

loader = GraphSAINTRandomWalkSampler(data, batch_size=6000, 
                                     walk_length=2, num_steps=5, 
                                     sample_coverage=100, 
                                     save_dir=dataset.processed_dir, 
                                     num_workers=4)

Имейте в виду, что загрузчик может не загружать весь набор данных в зависимости от того, как вы устанавливаете гиперпараметры. batch_size гиперпараметр - это количество проходов для выборки на партию. Например, с набором данных Citeseer и batch_size = 1, walk_length = 1 и num_steps = 1 мы получаем 1 образец данных с 2 узлами. С batch_size = 10 мы получаем 1 образец данных с 20 узлами. С batch_size = 100 мы получаем около 200 узлов, которые могут меняться на каждой итерации, например, 189, 191 и т. Д. Гиперпараметр num_steps - это количество итераций за эпоху. Итак, если мы увеличим num_steps до 2, количество узлов вырастет примерно до 380 с batch_size = 100 и walk_length = 1. Гиперпараметр walk_length относится к длине каждого случайного обхода для сэмплера, и результаты количества возвращенных узлов будут широко варьироваться в зависимости от ассортативности вашей сети. Фактически это компилирует реализацию C ++ (и впоследствии реализацию cuda) случайного блуждания на разреженном тензорном представлении из torch_sparse библиотеки PyTorch Geometric. См. Учебник по PyTorch по расширению TorchScript с помощью пользовательских операторов C ++ для получения дополнительной информации.

Одним из наиболее важных аспектов статьи GraphSAINT является вычисление статистики нормализации для уменьшения систематической ошибки в каждой выборке подграфа. GraphSAINTSampler вычисляет эту статистику, которая частично контролируется гиперпараметром sample_coverage. Итоговая статистика возвращается в виде атрибута edge_norm объекта data. Мы можем изменить атрибут edge_weight перед прямым проходом нашей нейронной сети графа с атрибутом edge_norm.

edge_weight = data.edge_norm * data.edge_weight            
out = model(data.x, data.edge_index, edge_weight)

[1] М. Фей. PyTorch Geometric. Библиотека Graph Deep Learning.

[2] У. Гамильтон и др., Индуктивное обучение представлению на больших графах (2017).

[3] W. Hu et al. Open Graph Benchmark (2020).

[4] Х. Цзэн и др., GraphSAINT: Индуктивный метод обучения на основе выборки графов (2020)

[5] М. Бронштейн. Простые нейронные сети с масштабируемым графом (2020).