<jupyter_start><jupyter_text>The Role of Recurrent Transitions in RGNNs for Graph Classification Social networks represent a rich source of graph data, and due to the popularity of social networking applications, accurate user and community classifications have become exceedingly important for the purpose of analysis, marketing, and influencing. In this example, we look at how the recurrent application of a transition function aids in making predictions on the graph domain, namely, in graph classification.  SetupHere we load required libraries, define paths to data, and define some helper functions. **Feel free to skip this section.**<jupyter_code>import numpy as np
import math
import json
import networkx as nx
import itertools

from IPython.display import HTML
import matplotlib
import matplotlib.animation as animation
import matplotlib.pyplot as plt

import dgl
from dgl.nn.pytorch import GraphConv

import torch
import torch.nn as nn
import torch.nn.functional as F

from sklearn import metrics
from sklearn import manifold
fp_data = "./datasets/"
fp_data_stargazer = f"{fp_data}github_stargazers/"
fp_data_webmluser = f"{fp_data}git_web_ml/"
# Helper function to visualize stargazer dataset graphs
def plot_stargazer_graph(G, label=None, print_info=False, labels=True):
    # Print info with graph if we want
    if print_info:  
        print(f"{G.number_of_nodes()} vertices")
        print(f"{G.number_of_edges()} edges")
        
    # Grey if no label, pink if 0, green if 1
    col = [[0.7, 0.7, 0.7]]
    if label is not None:
        if label == 0:
            col = [[0.6, 0, 0.6]]
        elif label == 1:
            col = [[0, 0.5, 0]]
    
    # Visualise as undirected
    nx_G = G.to_networkx().to_undirected()
    
    # Use the reconmmended Kamada-Kawaii layout for arbitrary graphs
    pos = nx.kamada_kawai_layout(nx_G)
    nx.draw(nx_G, pos, with_labels=labels, node_color=col)
# Helper function to visualize the webmluser graph
def plot_webmluser_graph(G):    
    # Visualise as undirected
    nx_G = G.to_networkx().to_undirected()
    
    # Use the reconmmended Kamada-Kawaii layout for arbitrary graphs
    pos = nx.kamada_kawai_layout(nx_G)
    nx.draw(nx_G, pos, node_color=[[0.7, 0.7, 0.7]])
# Helper for getting batches from a dataset
def get_batches(xs, ys, batch_size=16):
    # How many batches is there of given size for this dataset
    num = len(xs)
    num_batches = math.ceil(num / batch_size)
    
    # Go through and get all batches
    batches_x = []
    batches_y = []
    
    # Get all batches in memory
    for i in range(num_batches - 1):
        sidx = batch_size * i
        fidx = batch_size * (i + 1)
        fidx = min(fidx, num)
        batches_x.append(xs[sidx:fidx])
        batches_y.append(ys[sidx:fidx])
        
    return batches_x, batches_y<jupyter_output><empty_output><jupyter_text>DatasetsWe'll introduce two distinct kinds of graph datasets through the following examples.  GitHub Stargazers Dataset12,725 graphs of undirected developer social networks. Again, vertices are users who starred popular machine learning and web development repositories (with at least 10 stars), and edges are mutual follower relationships. The task is to classify each graph as a machine learning, or web development social network.**In this dataset, each training sample is a distinct graph.**<jupyter_code># Load the ground truth labels. Every element here here is a 
# [graph index, label] pair
stargazer_labels = np.loadtxt(f"{fp_data_stargazer}git_target.csv", \
                                  delimiter=",", skiprows=1)
    
# Adopting the accepted ML notation of input data (x) and labels (y)
stargazer_y = stargazer_labels[:,1].astype(int)
# Then we'll load the edges (defined against vertex ids) - note that there
# are no node or edge features, so predictions are made purely based on 
# undirected graph properties
with open(f"{fp_data_stargazer}git_edges.json") as f:
    stargazer_edges = json.load(f)
# Every item in this dictionary are the edges for a single graph, where each 
# edge is defined as a [vertex index, vertex index] pair. Here we show the 
# first 10 edges from graph 19
stargazer_edges['19'][:10]
# This function takes the data loaded in the stargazer dataset form and turns 
# it into a DGL graph
def make_stargazer_graph(index):
    # Define every edge by its source and destination vertex ids
    edges = np.array(stargazer_edges[f"{index}"])
    src = edges[:,0]
    dst = edges[:,1]
    
    # Edges are directional in DGL; Make them undirectional by making them 
    # go both ways
    u = np.concatenate([src, dst])
    v = np.concatenate([dst, src])
    
    # Construct a DGLGraph
    return dgl.DGLGraph((u, v))
# We can use this data to build each of the 12725 graphs as a single DGL
# graph object, thus forming our graph dataset
stargazer_x = []
for i in range(12725):
    G = make_stargazer_graph(i)
    stargazer_x.append(G)
# Lets look at one of our graphs (pink for class 0, green for class 1)
plot_stargazer_graph(stargazer_x[19], label=stargazer_y[24], print_info=True, labels=False)
# Lets look at another - noting that the structure alone will be the inputs 
# to the GNN (no vertex or edge features), and that this will be sufficient
# to determine if the social network group is a ML developer group or 
# a Web developer group
plot_stargazer_graph(stargazer_x[24], label=stargazer_y[2], print_info=True, labels=False)<jupyter_output>30 vertices
66 edges<jupyter_text>GitHub Web or Machine Learning DatasetOne single graph representing the GitHub social network: vertices are users (who have starred at least 10 repositories) and edges represent if they mutually follow eachother. Each node has input features derived from profile data (location, repositories starred, employer and e-mail address), and belongs to one of two classes (derived from the user's job title): a web developer or machine learning developer. **Note that using a single graph represents a departure from traditional supervised machine learning, where we typically use hundreds or thousands of training instances**. In this application, it is perhaps easier to consider the **vertices** of the graph as training instances. Indeed, we would reserve some vertices for training and some for testing.<jupyter_code># Lets start by loading the vertices with their ground truth labels 
# and names attached. Every element is a [vertex index, name, label] triplet
webmluser_labels = np.loadtxt(f"{fp_data_webmluser}musae_git_target.csv", \
                                  delimiter=",", skiprows=1, usecols=[0,2])
webmluser_y = webmluser_labels[:,1].astype(int)
# Now load the associated vertex features
with open(f"{fp_data_webmluser}musae_git_features.json") as f:
    webmluser_features = json.load(f)
# There are 37700 vertices here, with each index keying into the features
# dictionary we just loaded. Here is an example of one vertex's features
print(webmluser_features['9001'])
# Then we'll load the edges (defined against vertex id pairs)
webmluser_edges = np.loadtxt(f"{fp_data_webmluser}musae_git_edges.csv", \
                                  delimiter=",", skiprows=1)
# We only need to make on graph here, and that is our 'dataset'
def make_webmluser_graph():
    # Define every edge by its source and destination vertex ids
    src = webmluser_edges[:,0]
    dst = webmluser_edges[:,1]
    
    # Edges are directional in DGL; Make them undirectional by making them 
    # go both ways
    u = np.concatenate([src, dst])
    v = np.concatenate([dst, src])
    
    # Construct a DGLGraph
    G = dgl.DGLGraph((u, v))
    
    return G
# Build the graph from the data - note that this is a big graph
webmluser_x = make_webmluser_graph()
print(f"{webmluser_x.number_of_nodes()} nodes")
print(f"{webmluser_x.number_of_edges()} edges")
# For the purpose of this example, we will consider only the
# Stargazer's Dataset, but its good to be aware of different kinds of 
# datasets<jupyter_output><empty_output><jupyter_text>ArchitecturesTrue RGNNs are seldom used in contemporary GNN work. RGNNs require a transition function to be repeatedly applied until convergence of the hidden states - an expensive computation. Instead of use true RGNNs here, we'll use GCNs with varying numbers of layers, thus mimicking the repeated application of a transition function.<jupyter_code># We want to experiment with the amount of computation required in the 
# forward pass, so we'll build various GNNs here, each with different 
# numbers of transition function layers
class StargazerGNN(nn.Module):
    def __init__(self, num_hidden_features):
        super().__init__()
        
        # We'll apply some number of spatial convolutions / message passing 
        # RGNNs
        self.convs = nn.ModuleList()
        for i in range(len(num_hidden_features) - 1):
            self.convs.append(GraphConv(num_hidden_features[i], 
                                        num_hidden_features[i+1]))
            
        # Classify out to one of two classes
        self.classify = nn.Linear(num_hidden_features[-1], 2)

    def forward(self, g):
        # Start with just the degree as a feature
        h = g.in_degrees().view(-1, 1).float()
        for i in range(len(self.convs)):
            h = self.convs[i](g, h)
            h = torch.relu(h)
            
        # Calculate graph representation by averaging all the node 
        # representations, thus making a graph representation
        g.ndata['h'] = h
        hg = dgl.mean_nodes(g, 'h')
        output = self.classify(hg)
        return output

    def hidden(self, g):
        # Start with just the degree as a feature
        h = g.in_degrees().view(-1, 1).float()
        for i in range(len(self.convs)):
            h = self.convs[i](g, h)
            h = torch.relu(h)
        
        return h<jupyter_output><empty_output><jupyter_text>ExperimentsNow we'll perform our experiments, we want to create GNNs which use learned transition functions of increasing complexity. We'll start by defining a training and testing procedure, and then we'll produce and discuss some results.  Training and TestingWe'll use a learning rate of 0.001, MSE Loss in our loss function, and a batch size of 64.<jupyter_code># The following operations will train the GNN
def train_stargazer_gnn(gnn, num_epochs):
    loss_func = nn.MSELoss()
    opt = torch.optim.Adam(itertools.chain(gnn.parameters()), 
                           lr=0.001)

    # Get the batches to work with
    num_train = 8096
    batches_x, batches_y = get_batches(stargazer_x[:num_train], \
                                       stargazer_y[:num_train], \
                                       batch_size=64)

    # Run every batch in every epoch
    epoch_losses = []
    for epoch_index in range(num_epochs):
        epoch_loss = 0
        for batch_index in range(len(batches_x)):
            # Get the batch of interest
            batch_x = batches_x[batch_index]
            batch_y = batches_y[batch_index]

            # Calculate an output for each graph
            x = dgl.batch(batch_x)
            y_hat = gnn(x)

            # And compare to the true value
            y = F.one_hot(torch.tensor(batch_y), num_classes=2).float()

            #print(y_hat)
            #print(y)

            # Calculate loss 
            loss = loss_func(y_hat, y)

            # Calculate loss and perform gradient descent step accordingly
            opt.zero_grad()
            loss.backward()
            opt.step()

            epoch_loss += loss.item()
        epoch_loss /= len(batches_x)
        print(f"Epoch {epoch_index}: loss {epoch_loss}")
        epoch_losses.append(epoch_loss)
        
    # Return the trained architecture and loss
    return epoch_losses
    
# The following operation will test the GNN, returning hidden representations and 
# predictions
def test_stargazer_gnn(gnn):
    num_train = 8096
    num_test = 2048

    batches_x, batches_y = get_batches(stargazer_x[num_train:num_train+num_test],\
                                       stargazer_y[num_train:num_train+num_test],\
                                       batch_size=1)

    num_correct = 0
    y_true = []
    y_pred = []
    hidden = []
    for batch_index in range(len(batches_x)):
        # Get the batch of interest
        batch_x = batches_x[batch_index]
        batch_y = batches_y[batch_index]

        # Calculate an output for each graph
        x = dgl.batch(batch_x)
        y_hat = gnn(x)
        y_hat = torch.argmax(y_hat, dim=1).detach().numpy()

        # Also get some hidden representations for plotting
        h = torch.mean(gnn.hidden(x), dim=0).detach().numpy()
        hidden.append(h)

        # Take note of everything
        y_pred.extend(y_hat)
        y_true.extend(batch_y)
    hidden = np.array(hidden)
    
    return hidden, y_true, y_pred<jupyter_output><empty_output><jupyter_text>As en example, lets now use these functions to train and test a Stargazer GNN.<jupyter_code>stargazer_gnn_example = StargazerGNN([1, 16, 16, 16, 16, 16, 16, 16])
epoch_losses = train_stargazer_gnn(stargazer_gnn_example, 8)
hidden, y_true, y_pred = test_stargazer_gnn(stargazer_gnn_example)
print(metrics.classification_report(y_true, y_pred, \
                                    target_names=['web', 'ml']))
fpr, tpr, thresholds = metrics.roc_curve(y_true, y_pred)
print(f"AUC\t{metrics.auc(fpr, tpr)}")
# Plot a TSNE fit on the features
tsne = manifold.TSNE(n_components=2)
tsne_embedded = tsne.fit_transform(hidden)
tsne_embedded.shape
plt.scatter(tsne_embedded[:,0], tsne_embedded[:,1], \
            marker='.', c=y_true, 
            cmap=matplotlib.colors.ListedColormap(['purple', 'green']))<jupyter_output><empty_output><jupyter_text>As expected, the loss decreases (with ultimately diminishing returns) over the 8 epochs. Ultimately the features become more separable, as shown by the TSNE plot.  Results and Discussion Now lets wrap all this up into one function so we can test multiple architectures.<jupyter_code>def train_test_architecture(num_hidden_features, num_epochs, plot_loss=False):
    # Make architecture and train
    gnn_run = StargazerGNN(num_hidden_features)
    epoch_losses = train_stargazer_gnn(gnn_run, num_epochs)
    
    if num_epochs > 0 and plot_loss:
        plt.plot(range(num_epochs), epoch_losses)
        plt.ylim((0, 1.0))
        plt.title("Loss during training")
        plt.show()
    
    # Test and return hidden representations plus predictions
    hidden, y_true, y_pred = test_stargazer_gnn(gnn_run)
    
    # Print performance metrics
    print(metrics.classification_report(y_true, y_pred, \
                                        target_names=['web', 'ml']))
    fpr, tpr, thresholds = metrics.roc_curve(y_true, y_pred)
    print(f"AUC\t{metrics.auc(fpr, tpr)}")
    
    # Plot TSNE visualization
    tsne = manifold.TSNE(n_components=2)
    tsne_embedded = tsne.fit_transform(hidden)
    tsne_embedded.shape
    plt.scatter(tsne_embedded[:,0], tsne_embedded[:,1], \
                marker='.', c=y_true, 
                cmap=matplotlib.colors.ListedColormap(['purple', 'green']))<jupyter_output><empty_output><jupyter_text>Now lets conduct some experiments - we keep the number of epochs consistent and vary the number of layers in the transition function. This is similar to the examples ran in section B.1 in the paper.<jupyter_code>train_test_architecture([1, 16], 6)
train_test_architecture([1, 16, 16], 6)
train_test_architecture([1, 16, 16, 16, 16], 6)
train_test_architecture([1, 16, 16, 16, 16, 16, 16, 16], 6)<jupyter_output>Epoch 0: loss 0.3079410365649632
Epoch 1: loss 0.2533067696624332
Epoch 2: loss 0.24540737011129893
Epoch 3: loss 0.23956490674662212
Epoch 4: loss 0.23251398144260285
Epoch 5: loss 0.22694622133932416
              precision    recall  f1-score   support

         web       0.71      0.40      0.51       991
          ml       0.60      0.85      0.70      1056

    accuracy                           0.63      2047
   macro avg       0.66      0.62      0.61      2047
weighted avg       0.66      0.63      0.61      2047

AUC	0.6244830367244596
{'fraction_non_alphanumeric': 0.08240534521158129, 'fraction_numerical': 0.023447166542934918, 'mean_word_length': 3.123724489795918, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '537004', 'license': 'CC0-1.0', 'n_tokens_mistral': 5269, 'n_tokens_neox': 4884, 'n_words': 1644, 'path': 'notebooks/b1-transition.ipynb', 'repo_name': 'isolabs/gnn-tutorial', 'size': '16164'}