Redes neuronales gráficas Parte 3: Cómo los grafsage manejan la estructura de gráficos cambiando

Partes de esta serie, analizamos las redes convolucionales Graph (GCN) y las redes de atención de gráficos (GATS). Ambas arquitecturas funcionan bien, ¡pero también tienen algunas limitaciones! Una gran es que para gráficos grandes, calcular las representaciones de nodo con GCN y GATS se volverá muy lento. Otra limitación es que si la estructura del gráfico cambia, GCNS y GATS no podrán generalizar. Entonces, si se agregan nodos al gráfico, un GCN o GAT no puede hacer predicciones para él. ¡Afortunadamente, estos problemas se pueden resolver!

En esta publicación, explicaré Gráfico y cómo resuelve problemas comunes de GCN y GATS. Entrenaremos Graphsage y lo usaremos para predicciones de gráficos para comparar el rendimiento con GCN y GATS.

¿Nuevo en GNNS? Puedes comenzar con Publicar 1 sobre GCNS (que también contiene la configuración inicial para ejecutar las muestras de código), y Publicar 2 sobre GATS.

Dos problemas clave con GCNS y GATS

Brevemente lo toqué en la introducción, pero vamos a sumergirnos un poco más. ¿Cuáles son los problemas con los modelos GNN anteriores?

Problema 1. No generalizan

Los GCN y los GAT luchan por generalizar a gráficos invisibles. La estructura del gráfico debe ser la misma que los datos de entrenamiento. Esto se conoce como aprendizaje transductivodonde el modelo entrena y hace predicciones en el mismo gráfico fijo. En realidad, es excesivo a topologías gráficas específicas. En realidad, los gráficos cambiarán: los nodos y los bordes se pueden agregar o eliminar, y esto sucede a menudo en escenarios del mundo real. Queremos que nuestros GNN sean capaces de aprender patrones que se generalizan a nodos invisibles, o a gráficos completamente nuevos (esto se llama inductivo aprendiendo).

Problema 2. Tienen problemas de escalabilidad

Entrenar GCN y GATS en gráficos a gran escala es computacionalmente costoso. Los GCN requieren una agregación vecina repetida, que crece exponencialmente con el tamaño de la gráfica, mientras que los GAT implican mecanismos de atención (múltiples) que escalan mal con los nodos crecientes.
En los sistemas de recomendaciones de gran producción que tienen grandes gráficos con millones de usuarios y productos, los GCN y los GAT no son prácticos y lentos.

Echemos un vistazo a Graphsage para solucionar estos problemas.

Graphsage (muestra y agregado)

Gráfico Hace que el entrenamiento sea mucho más rápido y escalable. Hace esto por Muestreo solo un subconjunto de vecinos. Para gráficos súper grandes, es computacionalmente imposible procesar a todos los vecinos de un nodo (excepto si tiene tiempo ilimitado, que no todos no …), como con los GCN tradicionales. Otro paso importante de Graphsage es Combinando las características de los vecinos muestreados con una función de agregación.
Caminaremos por todos los pasos de Graphsage a continuación.

1. Vecinos de muestreo

Con datos tabulares, el muestreo es fácil. Es algo que haces en todos los proyectos de aprendizaje automático común al crear conjuntos de trenes, pruebas y validación. Con gráficos, no puede seleccionar nodos aleatorios. Esto puede dar lugar a gráficos desconectados, nodos sin vecinos, etc.:

Que tu poder hacer gráficos es seleccionar un subconjunto de vecinos de tamaño fijo aleatorio. Por ejemplo, en una red social, puede probar 3 amigos para cada usuario (en lugar de todos los amigos):

2. Información agregada

Después de la selección del vecino de la parte anterior, Graphsage combina sus características en una sola representación. Hay múltiples formas de hacer esto (múltiples funciones de agregación). Los tipos más comunes y los explicados en el papel son agregación media, LSTMy agrupación.

Con la agregación media, el promedio se calcula en todas las características de los vecinos muestreados (muy simples y a menudo efectivos). En una fórmula:

La agregación LSTM usa un LSTM (tipo de red neuronal) para procesar las características de los vecinos secuencialmente. Puede capturar relaciones más complejas, y es más poderosa que la agregación media.

El tercer tipo, la agregación del grupo, aplica una función no lineal para extraer características clave (piense en polvocanado en una red neuronal, donde también toma el valor máximo de algunos valores).

3. Actualizar la representación del nodo

Después de muestreo y agregación, el nodo Combina sus características anteriores con las características de vecino agregado. Los nodos aprenderán de sus vecinos pero también mantendrán su propia identidad, tal como vimos antes con GCNS y GATS. La información puede fluir a través del gráfico de manera efectiva.

Esta es la fórmula para este paso:

La agregación del paso 2 se realiza sobre todos los vecinos, y luego la representación de características del nodo se concatena. Este vector se multiplica por la matriz de peso y pasa a través de la no linealidad (por ejemplo, Relu). Como paso final, se puede aplicar la normalización.

4. Repita para múltiples capas

Los primeros tres pasos se pueden repetir varias veces, cuando esto sucede, la información puede fluir de vecinos distantes. En la imagen a continuación, vea un nodo con tres vecinos seleccionados en la primera capa (vecinos directos) y dos vecinos seleccionados en la segunda capa (vecinos de vecinos).

Para resumir, las fuerzas clave de Graphsage son su escalabilidad (el muestreo lo hace eficiente para gráficos masivos); flexibilidad, puede usarla para Aprendizaje inductivo (funciona bien cuando se usa para predecir en nodos y gráficos invisibles); La agregación ayuda con la generalización porque suaviza características ruidosas; y las múltiples capas permiten que el modelo aprenda de nodos lejanos.

¡Fresco! Y lo mejor, GraphSage se implementa en Pygpor lo que podemos usarlo fácilmente en Pytorch.

Predecir con Graphsage

En las publicaciones anteriores, implementamos un MLP, GCN y GAT en el Cora DataSet (CC BY-SA). Para refrescar un poco su mente, Cora es un conjunto de datos con publicaciones científicas en las que debe predecir el tema de cada artículo, con siete clases en total. Este conjunto de datos es relativamente pequeño, por lo que podría no ser el mejor conjunto para probar GraphSage. Haremos esto de todos modos, solo para poder comparar. Veamos qué tan bien funciona Graphsage.

Partes interesantes del código que me gusta resaltar relacionados con Graphsage:

• El NeighborLoader que realiza la selección de los vecinos para cada capa:

from torch_geometric.loader import NeighborLoader

# 10 neighbors sampled in the first layer, 10 in the second layer
num_neighbors = [10, 10]

# sample data from the train set
train_loader = NeighborLoader(
    data,
    num_neighbors=num_neighbors,
    batch_size=batch_size,
    input_nodes=data.train_mask,
)

• El tipo de agregación se implementa en el SAGEConv capa. El valor predeterminado es meanpuedes cambiar esto a max o lstm:

from torch_geometric.nn import SAGEConv

SAGEConv(in_c, out_c, aggr='mean')

• Otra diferencia importante es que Graphsage está entrenado en mini lotes, y GCN y GAT en el conjunto de datos completo. Esto toca la esencia de Graphsage, debido a que el muestreo vecino de Graphsage hace posible entrenar en mini lotes, ya no necesitamos el gráfico completo. Los GCN y los GAT necesitan el gráfico completo para la propagación de características correctas y el cálculo de los puntajes de atención, por eso entrenamos GCN y GATS en el gráfico completo.
• El resto del código es similar al antes, excepto que tenemos una clase donde todos los modelos diferentes están instanciados en función de model_type (GCN, GAT o SAGE). Esto hace que sea fácil comparar o hacer pequeños cambios.

Este es el script completo, entrenamos 100 épocas y repetimos el experimento 10 veces para calcular la precisión promedio y la desviación estándar para cada modelo:

import torch
import torch.nn.functional as F
from torch_geometric.nn import SAGEConv, GCNConv, GATConv
from torch_geometric.datasets import Planetoid
from torch_geometric.loader import NeighborLoader

# dataset_name can be 'Cora', 'CiteSeer', 'PubMed'
dataset_name = 'Cora'
hidden_dim = 64
num_layers = 2
num_neighbors = [10, 10]
batch_size = 128
num_epochs = 100
model_types = ['GCN', 'GAT', 'SAGE']

dataset = Planetoid(root='data', name=dataset_name)
data = dataset[0]
device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
data = data.to(device)

class GNN(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, num_layers, model_type='SAGE', gat_heads=8):
        super().__init__()
        self.convs = torch.nn.ModuleList()
        self.model_type = model_type
        self.gat_heads = gat_heads

        def get_conv(in_c, out_c, is_final=False):
            if model_type == 'GCN':
                return GCNConv(in_c, out_c)
            elif model_type == 'GAT':
                heads = 1 if is_final else gat_heads
                concat = False if is_final else True
                return GATConv(in_c, out_c, heads=heads, concat=concat)
            else:
                return SAGEConv(in_c, out_c, aggr='mean')

        if model_type == 'GAT':
            self.convs.append(get_conv(in_channels, hidden_channels))
            in_dim = hidden_channels * gat_heads
            for _ in range(num_layers - 2):
                self.convs.append(get_conv(in_dim, hidden_channels))
                in_dim = hidden_channels * gat_heads
            self.convs.append(get_conv(in_dim, out_channels, is_final=True))
        else:
            self.convs.append(get_conv(in_channels, hidden_channels))
            for _ in range(num_layers - 2):
                self.convs.append(get_conv(hidden_channels, hidden_channels))
            self.convs.append(get_conv(hidden_channels, out_channels))

    def forward(self, x, edge_index):
        for conv in self.convs[:-1]:
            x = F.relu(conv(x, edge_index))
        x = self.convs[-1](x, edge_index)
        return x

@torch.no_grad()
def test(model):
    model.eval()
    out = model(data.x, data.edge_index)
    pred = out.argmax(dim=1)
    accs = []
    for mask in [data.train_mask, data.val_mask, data.test_mask]:
        accs.append(int((pred[mask] == data.y[mask]).sum()) / int(mask.sum()))
    return accs

results = {}

for model_type in model_types:
    print(f'Training {model_type}')
    results[model_type] = []

    for i in range(10):
        model = GNN(dataset.num_features, hidden_dim, dataset.num_classes, num_layers, model_type, gat_heads=8).to(device)
        optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

        if model_type == 'SAGE':
            train_loader = NeighborLoader(
                data,
                num_neighbors=num_neighbors,
                batch_size=batch_size,
                input_nodes=data.train_mask,
            )

            def train():
                model.train()
                total_loss = 0
                for batch in train_loader:
                    batch = batch.to(device)
                    optimizer.zero_grad()
                    out = model(batch.x, batch.edge_index)
                    loss = F.cross_entropy(out, batch.y[:out.size(0)])
                    loss.backward()
                    optimizer.step()
                    total_loss += loss.item()
                return total_loss / len(train_loader)

        else:
            def train():
                model.train()
                optimizer.zero_grad()
                out = model(data.x, data.edge_index)
                loss = F.cross_entropy(out[data.train_mask], data.y[data.train_mask])
                loss.backward()
                optimizer.step()
                return loss.item()

        best_val_acc = 0
        best_test_acc = 0
        for epoch in range(1, num_epochs + 1):
            loss = train()
            train_acc, val_acc, test_acc = test(model)
            if val_acc > best_val_acc:
                best_val_acc = val_acc
                best_test_acc = test_acc
            if epoch % 10 == 0:
                print(f'Epoch {epoch:02d} | Loss: {loss:.4f} | Train: {train_acc:.4f} | Val: {val_acc:.4f} | Test: {test_acc:.4f}')

        results[model_type].append([best_val_acc, best_test_acc])

for model_name, model_results in results.items():
    model_results = torch.tensor(model_results)
    print(f'{model_name} Val Accuracy: {model_results[:, 0].mean():.3f} ± {model_results[:, 0].std():.3f}')
    print(f'{model_name} Test Accuracy: {model_results[:, 1].mean():.3f} ± {model_results[:, 1].std():.3f}')

Y aquí están los resultados:

GCN Val Accuracy: 0.791 ± 0.007
GCN Test Accuracy: 0.806 ± 0.006
GAT Val Accuracy: 0.790 ± 0.007
GAT Test Accuracy: 0.800 ± 0.004
SAGE Val Accuracy: 0.899 ± 0.005
SAGE Test Accuracy: 0.907 ± 0.004

¡Impresionante mejora! ¡Incluso en este pequeño conjunto de datos, Graphsage supera a GAT y GCN fácilmente! Repetí esta prueba para conjuntos de datos de CitaSeer y PubMed, y siempre Graphsage salió mejor.

Lo que me gusta señalar aquí es que GCN sigue siendo muy útil, es una de las líneas de base más efectivas (si la estructura del gráfico lo permite). Además, no hice mucha afinación de hiperparameter, pero solo fui con algunos valores estándar (como 8 cabezas para la atención GAT Multi-Head). En gráficos más grandes, más complejos y ruidosos, las ventajas de Graphsage se vuelven más claras que en este ejemplo. No hicimos ninguna prueba de rendimiento, porque para estos gráficos pequeños Graphsage no es más rápido que GCN.

Conclusión

Graphsage nos trae mejoras y beneficios muy agradables en comparación con GATS y GCNS. El aprendizaje inductivo es posible, Graphsage puede manejar las estructuras gráficas cambiantes bastante bien. Y no lo probamos en esta publicación, pero el muestreo de vecinos hace posible crear representaciones de características para gráficos más grandes con buen rendimiento.

Relacionado

Optimización de conexiones: optimización matemática dentro de los gráficos

Redes neuronales gráficas Parte 1. Redes convolucionales gráficas explicadas

Redes neuronales gráficas Parte 2. Redes de atención de gráficos vs. GCNS