Роб Харрис, Карл Шан в рамках курсового проекта Stanford CS224W
Введение
В 2018 году Кумар и др. др. опубликовал исследовательскую работу на The Web Conference, WWW 2018 под названием Взаимодействие сообщества и конфликты в сети.
В статье исследователи исследуют посты сабреддитов, которые содержат перекрестные ссылки на другие сообщества сабреддитов. Некоторые из этих сообщений вызывают «мобилизацию» пользователей в связанном сабреддите, что приводит к конфликтам и преследованиям. Другими словами, атака между онлайн-сообществами.
По мере того, как все больше политического дискурса перемещается в онлайн-пространства, такие как Reddit, становится все более важным способствовать здоровому и гражданскому обсуждению сложных идей. Таким образом, мы строим Kumar et. al. по созданию гетерогенной модели классификации на основе GNN, которая предсказывает, какие перекрестные ссылки из одного сообщества в другое могут привести к атаке, даже без точного текста сообщения.
Код этой статьи можно найти здесь. Наборы данных ниже.
Используемые наборы данных:
Социальная сеть: сеть гиперссылок Reddit
Этот набор данных был создан Kumar et. др. и содержит сообщения на Reddit с 1 января 2014 г. по 1 апреля 2017 г., которые ссылаются из одного сабреддита в другой.
Он имеет в общей сложности ~ 56 000 узлов (субреддиты) и ~ 860 000 ребер (сообщения с перекрестными ссылками). Каждое сообщение сопоставляется с отметкой времени, функциями частоты слов TF-IDF и флагом, указывающим, имеет ли текст положительное или отрицательное настроение. Всего в каждом посте 86 функций.
Внедрения пользователей Reddit и Subreddit
Этот набор данных также был создан Kumar et. др. Он содержит обученные встраивания (длиной 300) пользователей и сабреддитов, обученные для максимального сходства между пользователями и сабреддитами, в которых они публикуют сообщения. Полученные вложения охватывают аспекты контента и интересы как пользователей, так и сабреддитов.
Аналогично вложения, обученные для рекомендательных систем (совместная фильтрация), вложения сообщества и пользователей были контрастно обучены с использованием алгоритма оптимизации отрицательной выборки со следующей функцией потерь:
Где:
- эпсилон – это набор ребер в двудольном мультиграфе (сообщения от пользователей в сообществах).
- Pₙ — равномерное распределение по всем сообществам (используется для создания отрицательных выборок).
- K — количество использованных отрицательных образцов (Кумар и др. выбрали 5).
Предыдущее исследование
Кумар и др. др. протестировали три различных подхода к классификации постов с перекрестными ссылками:
- Базовый уровень: классификатор случайного леса, который использует только функции прямой публикации (функции частоты слов TF-IDF + тональность).
- Socially-Primed LSTM: рекуррентная модель, которая сначала обрабатывает вложения пользователя/сообщества, а затем слова самой публикации.
- Случайный лес + LSTM: базовая модель случайного леса с функциями, расширенными за счет включения вложений пользователя/сообщества и среднего скрытого состояния социально-примированного LSTM.
Наша работа описывает этот сценарий как проблему классификации ссылок, и мы стремимся заменить предыдущую LSTM сверточной сетью графов. Вместо обработки каждого слова поста наш метод будет использовать только функции частотности слов и встраивания пользователей/субреддитов. Существующие вложения собирают статистику совпадений между сообществами. Мы ожидаем, что свертки графа могут использовать шаблон предыдущего взаимодействия между сабреддитами, чтобы лучше предсказывать поведение мобилизации.
Формулировка графика
Исходная задача: классификация бинарных ссылок.
Требуемая задача:классификация двоичных узлов.
Наша цель — предсказать, относится ли данная ссылка (кросс-пост) между узлами (субреддитами) к одному из двух классов: (1) атака или (2) не атака. Если мы сможем найти способ конвертировать кросс-посты из ссылок в сами узлы, мы сможем свести задачу классификации ссылок к гораздо более распространенной задаче классификации узлов. Это также обеспечивает простой способ использования пост-специфических функций, поскольку многие распространенные слои GNN обновляют только функции узлов и игнорируют любые граничные функции.
Подход 1: сопряженный граф
Сопряженный граф (или линейный график) преобразует каждое ребро в узел, а каждый узел — в несколько ребер. Если G — исходный граф, а L(G) — сопряженный граф, то каждое ребро в G преобразуется в узел в L(G). Затем для каждых двух ребер в G, имеющих общий узел, мы создаем ребро между соответствующими узлами в L(G).
Поскольку наш исходный граф представляет сабреддиты в виде узлов, а перекрестные посты — в виде ребер, сопряженный граф содержит узел для каждого поста и ребра между постами, которые имеют общий сабреддит. Мы могли бы дополнительно различать эти ребра в зависимости от того, как связаны связанные посты, создавая отдельные типы ребер для случаев, когда посты имеют общий исходный субреддит, когда они совместно используют целевой субреддит и когда цель одного является источником другого. Это позволило бы передаче сообщений в нашей GNN обрабатывать эти разные «типы» почтовых соединений по-разному.
К сожалению, ключевым ограничением сопряженного графа является то, что количество созданных ребер масштабируется как O(d2), где d — максимальная степень исходного графа. Когда в исходном графе есть узлы с большим количеством ребер, тогда сопряженный граф должен соединять каждое ребро в этом узле с каждым другим ребром в этом узле. Это именно то, что происходит в нашем наборе данных, особенно для популярных субреддитов, таких как r/politics, которые являются источником и целью для многих кросс-постов. Когда каждый кросс-пост преобразуется в узел, каждый кросс-пост в/из r/politics нуждается в ребрах, соединяющихся с каждым другим кросс-постом в/из r/politics.
Исходный граф имеет ~56 тыс. узлов и ~280 тыс. ребер. Сопряженный граф имеет около 280 тыс. узлов (по 1 на каждое ребро) и около 300 млн ребер, требующих более 7 ГБ для хранения на диске. Поскольку было бы невозможно выполнить наш анализ на этом графе, мы решили использовать альтернативную форму сопряженного графа.
Подход 2: публикации как дополнительный тип узла
Чтобы представить кросс-посты как узлы без резкого увеличения количества ребер, мы просто поддерживаем два типа узлов: сабреддиты и кросс-посты. Учитывая исходный граф, мы просто создаем новый узел «post» в центре каждого ребра, разделяя ребро на два ребра.
Этот новый граф имеет два типа узлов (subreddit, post) и два неориентированных типа ребер:
- (post, source, subreddit): подключение кросс-поста к его исходному субреддиту.
- (post, target, subreddit): подключение кросс-поста к его целевому субреддиту.
Этот новый граф имеет только в два раза больше ребер, чем исходный, поскольку связи между сообщениями опосредуются через узлы сабреддита. Код ниже (и в нашем Colab) показывает, как мы создаем этот Heterogeneous graph:
data = HeteroData() # Community nodes only include subreddit embeddings as features data["community"].x = torch.from_numpy(subreddit_embeds).float() # Order corresponds to subreddit_ids # Post nodes include word frequency features, user embeddings, and sentiment data["post"].x = torch.from_numpy(np.concatenate([ post_features, user_embeds[post_info["user_index"]], post_info["sentiment"].values.reshape(-1, 1) ], axis=1)).float() # Undirected edges between source community and post data["community", "source", "post"].edge_index = torch.from_numpy(np.vstack([ post_info["source_index"], post_info.index ])) data["post", "source", "community"].edge_index = torch.from_numpy(np.vstack([ post_info.index, post_info["source_index"] ])) # Undirected edges between post and target community data["community", "target", "post"].edge_index = torch.from_numpy(np.vstack([ post_info["target_index"], post_info.index ])) data["post", "target", "community"].edge_index = torch.from_numpy(np.vstack([ post_info.index, post_info["target_index"] ]))
Создание графического семплера
Чтобы тренироваться на нашем графе, нам нужно иметь возможность сэмплировать мини-пакеты помеченных кросс-постовых узлов, а также ограниченное соседство узлов вокруг них. Для этого мы используем NeighborSampler от pytorch-geometric, настроенный на выборку до 10 соседей каждого узла мини-пакета, повторяя это для каждого слоя GNN в нашей модели (чтобы гарантировать, что мы покрываем все восприимчивое поле нашей модели).
Создание нашей гетерогенной модели GNN
Макет ключевой архитектуры состоял из трех этапов:
- Слои GNN: [GNN conv → BatchNorm → Leaky ReLU] (мы использовали 2 слоя)
- Слои постобработки MLP: [слой Multi-Layer Perceptron → BatchNorm → Leaky ReLU] (мы использовали 0 слоев)
- Голова классификации: [Линейный слой с 1 выходом → Сигмоид]
Использованная нами свертка GNN была сверткой GATConv графа внимания, которая использует механизм внимания для взвешивания сообщений, поступающих от разных соседних узлов. Как видно ниже (и в нашем Colab), мы создаем этот классификатор как обычную однородную сеть, затем применяем преобразование to_hetero pytorch-geometric, чтобы преобразовать его в модуль свертки гетерогенного графа. Это преобразование создает несколько версий классификатора, каждая из которых обрабатывает сообщения для определенного типа ребер, и обрабатывает агрегирование сообщений от разных типов ребер для обновления функций узла.
''' Architecture Layout: [GNN conv --> batchnorm --> lrelu] * gnn_layer_count --> [mlp layer --> batchnorm --> lrelu] * mlp_layer_count --> mlp layer --> sigmoid ''' class GATClassifier(nn.Module): def __init__(self, gnn_layer_count: int, mlp_layer_count: int, hidden_size: int): super().__init__() self.gnn_layer_count = gnn_layer_count self.mlp_layer_count = mlp_layer_count self.hidden_size = hidden_size # GNN layers (GATConv + Linear) self.gnn_convs = nn.ModuleList( [gnn.GATConv((-1, -1), hidden_size, add_self_loops=False)] + [gnn.GATConv(hidden_size, hidden_size, add_self_loops=False) for _ in range(gnn_layer_count - 1)] ) self.gnn_linears = nn.ModuleList( [gnn.Linear(-1, hidden_size)] + [gnn.Linear(hidden_size, hidden_size) for _ in range(gnn_layer_count - 1)] ) # Batchnorm after each GNN layer self.gnn_batchnorms = nn.ModuleList( [nn.BatchNorm1d(hidden_size, eps=1) for _ in range(gnn_layer_count)] ) # Activation after each GNN layer self.gnn_activations = nn.ModuleList( [nn.LeakyReLU() for _ in range(gnn_layer_count)] ) # Post-processing mlp layers if mlp_layer_count > 0: self.mlp_layers = nn.ModuleList( [gnn.Linear(hidden_size, hidden_size) for _ in range(mlp_layer_count)] ) # Batchnorm after each mlp layer self.mlp_batchnorms = nn.ModuleList( [nn.BatchNorm1d(hidden_size, eps=1) for _ in range(mlp_layer_count)] ) # Activation after each mlp layer self.mlp_activations = nn.ModuleList( [nn.LeakyReLU() for _ in range(gnn_layer_count)] ) # Final classification head self.classification_head = gnn.Linear(hidden_size, 1) self.logit_transform = nn.Sigmoid() def forward(self, x, edge_index): for i in range(self.gnn_layer_count): x = self.gnn_convs[i](x, edge_index) + self.gnn_linears[i](x) x = self.gnn_batchnorms[i](x) x = self.gnn_activations[i](x) if self.mlp_layer_count > 0: for i in range(self.mlp_layer_count): x = self.mlp_layers[i](x) x = self.mlp_batchnorms[i](x) x = self.mlp_activations[i](x) x = self.classification_head(x) x = self.logit_transform(x) return x GNN_LAYER_COUNT = 2 MLP_LAYER_COUNT = 0 HIDDEN_SIZE = 256 LR = 1e-3 LOSS_FUNCTION = nn.BCELoss() model = GATClassifier(GNN_LAYER_COUNT, MLP_LAYER_COUNT, HIDDEN_SIZE) model = gnn.to_hetero(model, data.metadata(), aggr="mean") model.to("cuda") optimizer = torch.optim.Adam(model.parameters(), lr=LR)
Полученные результаты
После обучения нашей модели GNN для 30 эпох и выбора прогона с наилучшей проверкой ROC-AUC мы достигаем тестовой оценки ROC-AUC 0,771.
Это превосходит все три метода, использованные Kumar et. др.:
- Базовый случайный лес: AUC = 0,67
- Социально ориентированный LSTM: AUC = 0,72
- Случайный лес + LSTM: AUC = 0,76
- Классификатор GNN (наш): AUC = 0,771
Заключение
В заключение, этот проект демонстрирует, что сетевые паттерны взаимодействия субреддитов кодируют важную информацию о мобилизационном поведении, и даже наивная модель GNN может превзойти модель LSTM, которая использует точную расшифровку сообщений. Это указывает на то, что использование структуры социального графа является мощным инструментом для прогнозирования атак между онлайн-сообществами и поддержания здоровья нашего онлайн-дискурса.