Роб Харрис, Карл Шан в рамках курсового проекта 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).

Предыдущее исследование

Кумар и др. др. протестировали три различных подхода к классификации постов с перекрестными ссылками:

  1. Базовый уровень: классификатор случайного леса, который использует только функции прямой публикации (функции частоты слов TF-IDF + тональность).
  2. Socially-Primed LSTM: рекуррентная модель, которая сначала обрабатывает вложения пользователя/сообщества, а затем слова самой публикации.
  3. Случайный лес + 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) и два неориентированных типа ребер:

  1. (post, source, subreddit): подключение кросс-поста к его исходному субреддиту.
  2. (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

Макет ключевой архитектуры состоял из трех этапов:

  1. Слои GNN: [GNN conv → BatchNorm → Leaky ReLU] (мы использовали 2 слоя)
  2. Слои постобработки MLP: [слой Multi-Layer Perceptron → BatchNorm → Leaky ReLU] (мы использовали 0 слоев)
  3. Голова классификации: [Линейный слой с 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. др.:

  1. Базовый случайный лес: AUC = 0,67
  2. Социально ориентированный LSTM: AUC = 0,72
  3. Случайный лес + LSTM: AUC = 0,76
  4. Классификатор GNN (наш): AUC = 0,771

Заключение

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