In [ ]:

import marimo as mo

import marimo as mo

Graph Convolutional Networks¶

August 4 2026 Training Workshop: Introduction to Deep Graph Learning Ingo Scholtes, CAIDAS, Julius-Maximilians-Universität Würzburg (JMU), Germany

Building on the Neural Message Passing layer implemented in the previous notebook, we now implement a full-fledged graph convolutional neural network and apply it to synthetic and empirical example networks.

In [ ]:

import numpy as np
import pandas as pd
import seaborn as sns
import torch
import torch_geometric
from matplotlib import pyplot as plt
from sklearn.datasets import make_circles
from sklearn.decomposition import TruncatedSVD

import pathpyG as pp

plt.style.use('default')
sns.set_style("whitegrid")

device = 'cuda' if torch.cuda.is_available() else 'cpu'
print('Running on', device)

import numpy as np import pandas as pd import seaborn as sns import torch import torch_geometric from matplotlib import pyplot as plt from sklearn.datasets import make_circles from sklearn.decomposition import TruncatedSVD import pathpyG as pp plt.style.use('default') sns.set_style("whitegrid") device = 'cuda' if torch.cuda.is_available() else 'cpu' print('Running on', device)

Running on cpu

We use a simple example for a network with two strong communities from the lecture, which define our ground truth (binary) node classes. In fact, these two node classes can be easily predicted based on the topology of the graph alone, i.e. here we do not need any node features.

In [ ]:

n = 50
random_1 = pp.algorithms.generative_models.watts_strogatz(n=n, s=4, p=0.01, mapping=pp.IndexMap([str(x) for x in range(n)]), undirected=True)
random_1.data.y = torch.tensor([0] * n)
random_2 = pp.algorithms.generative_models.watts_strogatz(n=n, s=4, p=0.01, mapping=pp.IndexMap([str(x + 1 * n) for x in range(n)]), undirected=True)
random_2.data.y = torch.tensor([1] * n)
colors = {}
for _v in random_1.nodes:
    colors[_v] = 'orange'
for _v in random_2.nodes:
    colors[_v] = 'blue'
network = random_1 + random_2
network = network.to_undirected()
network.data.y = torch.cat([random_1.data.y, random_2.data.y])
src_indices = torch.where(network.data.y < 1)[0]
tgt_indices = torch.where(network.data.y >= 1)[0]
num_edges_to_update = 2
# to_undirected() only preserves edge_index/x/edge_attr, so we have to restore the node labels
edge_indices_to_update = np.random.choice(network.data.edge_index.shape[1], num_edges_to_update, replace=False)
for edge_index in edge_indices_to_update:
# randomly update src and tgt in network.edge_index so that link source in random_1 to target in random_2 and vice-versa
    src, tgt = network.data.edge_index[:, edge_index]
    if src in src_indices and tgt in src_indices:
        new_tgt = np.random.choice(tgt_indices.cpu().numpy())
        network.data.edge_index[1, edge_index] = new_tgt
    elif src in tgt_indices and tgt in tgt_indices:
        new_src = np.random.choice(src_indices.cpu().numpy())
        network.data.edge_index[0, edge_index] = new_src
pp.plot(network, edge_color='gray', node_color=colors);

n = 50 random_1 = pp.algorithms.generative_models.watts_strogatz(n=n, s=4, p=0.01, mapping=pp.IndexMap([str(x) for x in range(n)]), undirected=True) random_1.data.y = torch.tensor([0] * n) random_2 = pp.algorithms.generative_models.watts_strogatz(n=n, s=4, p=0.01, mapping=pp.IndexMap([str(x + 1 * n) for x in range(n)]), undirected=True) random_2.data.y = torch.tensor([1] * n) colors = {} for _v in random_1.nodes: colors[_v] = 'orange' for _v in random_2.nodes: colors[_v] = 'blue' network = random_1 + random_2 network = network.to_undirected() network.data.y = torch.cat([random_1.data.y, random_2.data.y]) src_indices = torch.where(network.data.y < 1)[0] tgt_indices = torch.where(network.data.y >= 1)[0] num_edges_to_update = 2 # to_undirected() only preserves edge_index/x/edge_attr, so we have to restore the node labels edge_indices_to_update = np.random.choice(network.data.edge_index.shape[1], num_edges_to_update, replace=False) for edge_index in edge_indices_to_update: # randomly update src and tgt in network.edge_index so that link source in random_1 to target in random_2 and vice-versa src, tgt = network.data.edge_index[:, edge_index] if src in src_indices and tgt in src_indices: new_tgt = np.random.choice(tgt_indices.cpu().numpy()) network.data.edge_index[1, edge_index] = new_tgt elif src in tgt_indices and tgt in tgt_indices: new_src = np.random.choice(src_indices.cpu().numpy()) network.data.edge_index[0, edge_index] = new_src pp.plot(network, edge_color='gray', node_color=colors);

We also add a one-hot encoding of the nodes as additional feature:

In [ ]:

network.data.x = torch.eye(network.n, dtype=torch.float32)
network.data.y.unsqueeze_(-1)

network.data.x = torch.eye(network.n, dtype=torch.float32) network.data.y.unsqueeze_(-1)

tensor([[0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1]])

We now implement the graph convolutional network (GCN). We first reuse the implementation of the neural message passing layer from the previous notebook:

In [ ]:

class GraphConvolution(torch_geometric.nn.MessagePassing):
    """A graph convolution layer following (Kipf, Welling 2017)."""
    # Arguments passed to `propagate()`. pyG usually infers them from the source code of the class,
    # which is not possible for classes defined in marimo notebooks
    propagate_type = {'x': torch.Tensor, 'norm': torch.Tensor}

    def __init__(self, in_ch, out_ch):
        """Initialize the layer parameters."""
        super().__init__(aggr='add')

        # this linear function is used to transform node features 
        # into messages that are then "sent" to neighbors
        self.linear = torch.nn.Linear(in_ch, out_ch)
    
    def forward(self, x, edge_index):
        """Perform a graph convolution.

        This function uses the edges captured in edge_index, performs
        the graph convolution function according to (Kipf, Welling 2017)
        and propagates the transformed features along the edges of the graph.
        """
        # by adding self-loops, we ensure that aggregated messages from neighbors 
        # are combined with information from the node itself
        # this corresponds to matrix $\tilde{A}$ in (Kipf, Welling 2017)
        edge_index, _ = torch_geometric.utils.add_self_loops(edge_index, num_nodes=x.size(0))

        # we linearly transform the features of *all* nodes stored in x
        x = self.linear(x)

        # extract source and target nodes of all edges
        source, target = edge_index
    
        # compute the (in-)degrees $d_i$ of source nodes
        deg = torch_geometric.utils.degree(target, x.size(0), dtype=x.dtype)
        deg_inv_sqrt = deg.pow(-0.5)
        deg_inv_sqrt[deg_inv_sqrt == float('inf')] = 0

        # with this, the normalization to be applied in the propagation step can be expressed as
        # this corresponds to D^{-0.5} A * D^{-0.5} in (Kipf, Welling 2017)
        norm = deg_inv_sqrt[source] * deg_inv_sqrt[target]
    
        # the propagate function propagates messages along the edges of the graph
        # this function internally calls the functions: message(), aggregate() and update()
        # the normalization is applied in the message() function
        return self.propagate(edge_index, x=x, norm=norm)

    def message(self, x_j, norm):
        """Construct the message that is sent along each edge."""
        # x_j is a so-called **lifted** tensor which contains the source node features of each edge, 
        # i.e. it has a shape (m, out_ch) where m is the number of edges

        # a call to view(-1, 1) returns a reshaped tensor, where the second dimension 
        # is one and the first dimension is inferred automatically
        return norm.view(-1,1) * x_j

class GraphConvolution(torch_geometric.nn.MessagePassing): """A graph convolution layer following (Kipf, Welling 2017).""" # Arguments passed to `propagate()`. pyG usually infers them from the source code of the class, # which is not possible for classes defined in marimo notebooks propagate_type = {'x': torch.Tensor, 'norm': torch.Tensor} def __init__(self, in_ch, out_ch): """Initialize the layer parameters.""" super().__init__(aggr='add') # this linear function is used to transform node features # into messages that are then "sent" to neighbors self.linear = torch.nn.Linear(in_ch, out_ch) def forward(self, x, edge_index): """Perform a graph convolution. This function uses the edges captured in edge_index, performs the graph convolution function according to (Kipf, Welling 2017) and propagates the transformed features along the edges of the graph. """ # by adding self-loops, we ensure that aggregated messages from neighbors # are combined with information from the node itself # this corresponds to matrix $\tilde{A}$ in (Kipf, Welling 2017) edge_index, _ = torch_geometric.utils.add_self_loops(edge_index, num_nodes=x.size(0)) # we linearly transform the features of *all* nodes stored in x x = self.linear(x) # extract source and target nodes of all edges source, target = edge_index # compute the (in-)degrees $d_i$ of source nodes deg = torch_geometric.utils.degree(target, x.size(0), dtype=x.dtype) deg_inv_sqrt = deg.pow(-0.5) deg_inv_sqrt[deg_inv_sqrt == float('inf')] = 0 # with this, the normalization to be applied in the propagation step can be expressed as # this corresponds to D^{-0.5} A * D^{-0.5} in (Kipf, Welling 2017) norm = deg_inv_sqrt[source] * deg_inv_sqrt[target] # the propagate function propagates messages along the edges of the graph # this function internally calls the functions: message(), aggregate() and update() # the normalization is applied in the message() function return self.propagate(edge_index, x=x, norm=norm) def message(self, x_j, norm): """Construct the message that is sent along each edge.""" # x_j is a so-called **lifted** tensor which contains the source node features of each edge, # i.e. it has a shape (m, out_ch) where m is the number of edges # a call to view(-1, 1) returns a reshaped tensor, where the second dimension # is one and the first dimension is inferred automatically return norm.view(-1,1) * x_j

As explained before, this class implements the convolution layer based on a single round of message passing. The parameter in_ch must correspond to the dimensionality of the node feature vector. By changing the parameter out_ch we can use a linear transformation that maps node features to a higher-dimensional vector, which - analogy to the neural graph embeddings introduced in Lecture 10 - we can view as hidden layer that contains a latent representation of nodes.

We eventually map those latent node representations to the output classes for all nodes. We apply a non-linear transformation to node features and add a second graph convolutional layer, i.e. we run a second round of message passing, where the messages now contain latent representations of nodes that will be used for the classification. The second convolutional layer generates the output for our binary classification problem, i.e. the probability of class 1.

In [ ]:

class GCN(torch.nn.Module):
    """A two-layer graph convolutional network."""

    def __init__(self, data: torch_geometric.data.Data, out_ch, hidden_dim=16):
        """Initialize the model parameters."""
        super().__init__()

        # first convolution layer 
        self.input_to_hidden = GraphConvolution(data.num_node_features, hidden_dim)

        # second convolution layer
        self.hidden_to_output =  GraphConvolution(hidden_dim, out_ch)
    
    def forward(self, x, edge_index):
        """Compute class probabilities for all nodes."""
        # first graph convolution -> map nodes to representations in hidden_dim dimensions
        x = self.input_to_hidden(x, edge_index)

        # non-linear activation function
        x = torch.sigmoid(x)

        # second graph convolution -> maps node representations to output classes
        x = self.hidden_to_output(x, edge_index)

        # output class probabilities
        return torch.sigmoid(x)

class GCN(torch.nn.Module): """A two-layer graph convolutional network.""" def __init__(self, data: torch_geometric.data.Data, out_ch, hidden_dim=16): """Initialize the model parameters.""" super().__init__() # first convolution layer self.input_to_hidden = GraphConvolution(data.num_node_features, hidden_dim) # second convolution layer self.hidden_to_output = GraphConvolution(hidden_dim, out_ch) def forward(self, x, edge_index): """Compute class probabilities for all nodes.""" # first graph convolution -> map nodes to representations in hidden_dim dimensions x = self.input_to_hidden(x, edge_index) # non-linear activation function x = torch.sigmoid(x) # second graph convolution -> maps node representations to output classes x = self.hidden_to_output(x, edge_index) # output class probabilities return torch.sigmoid(x)

We are now ready to apply our model to our example. We use a hidden layer to learn a latent node representations in a 16-dimensional space. Due to the use of the one-hot-encoding as node features, each node has 100 features:

In [ ]:

model = GCN(network.data, out_ch=1, hidden_dim=16)

model = GCN(network.data, out_ch=1, hidden_dim=16)

Let's inspect the parameters of our Graph Convolutional Network with 16 hidden dimensions and two graph convolution layers, where the first layer maps the features of the 100 nodes to 16 hidden dimensions and the second layer maps the 16 hidden dimensions to one output per node, that is interpreted as a class probability.

In the first graph convolution layer, a linear transformation is applied in the message passing and we map the 100-dimensional node features of nodes to 16 dimensions in the first hidden layer. In other words, each node feature is passed through the same linear layer with 100 inputs and 16 outputs. This translates to a $16 \times 100$ weight matrix with additional 16 bias terms.

In [ ]:

_params = [x for x in model.input_to_hidden.parameters()]
print(_params[0].shape)
print(_params[1].shape)

_params = [x for x in model.input_to_hidden.parameters()] print(_params[0].shape) print(_params[1].shape)

torch.Size([16, 100])
torch.Size([16])

In the second layer, we apply a linear layer that maps the 16 hidden dimensions for each node to a single output dimension, that we will interpret as probability of the positive class in our binary classification task. We thus have 16 weight parameters and one additional bias parameter.

In [ ]:

_params = [x for x in model.hidden_to_output.parameters()]
print(_params[0].shape)
print(_params[1].shape)

_params = [x for x in model.hidden_to_output.parameters()] print(_params[0].shape) print(_params[1].shape)

torch.Size([1, 16])
torch.Size([1])

For a network with 100 nodes, we thus have 100 * 16 + 16 + 16 + 1 = 1633 learanble parameters. Without training those parameters, we get similar probabilities

In [ ]:

model.forward(network.data.x, network.data.edge_index)

model.forward(network.data.x, network.data.edge_index)

tensor([[0.3874],
        [0.3874],
        [0.3888],
        [0.3887],
        [0.3887],
        [0.3878],
        [0.3877],
        [0.3883],
        [0.3882],
        [0.3944],
        [0.3882],
        [0.3825],
        [0.3935],
        [0.3882],
        [0.3882],
        [0.3890],
        [0.3890],
        [0.3884],
        [0.3886],
        [0.3888],
        [0.3888],
        [0.3888],
        [0.3888],
        [0.3874],
        [0.3889],
        [0.3889],
        [0.3890],
        [0.3890],
        [0.3889],
        [0.3889],
        [0.3888],
        [0.3889],
        [0.3889],
        [0.3890],
        [0.3943],
        [0.3890],
        [0.3890],
        [0.3890],
        [0.3890],
        [0.3890],
        [0.3890],
        [0.3890],
        [0.3889],
        [0.3895],
        [0.3881],
        [0.3875],
        [0.3890],
        [0.3888],
        [0.3888],
        [0.3887],
        [0.3886],
        [0.3886],
        [0.3886],
        [0.3886],
        [0.3886],
        [0.3887],
        [0.3876],
        [0.3888],
        [0.3889],
        [0.3889],
        [0.3895],
        [0.3895],
        [0.3894],
        [0.3895],
        [0.3836],
        [0.3893],
        [0.3898],
        [0.3883],
        [0.3897],
        [0.3897],
        [0.3892],
        [0.3833],
        [0.3894],
        [0.3894],
        [0.3895],
        [0.3902],
        [0.3886],
        [0.3888],
        [0.3883],
        [0.3889],
        [0.3950],
        [0.3889],
        [0.3889],
        [0.3889],
        [0.3889],
        [0.3896],
        [0.3895],
        [0.3900],
        [0.3900],
        [0.3889],
        [0.3900],
        [0.3900],
        [0.3834],
        [0.3900],
        [0.3900],
        [0.3900],
        [0.3899],
        [0.3893],
        [0.3892],
        [0.3891]], grad_fn=<SigmoidBackward0>)

We use torch_geometric to generate a training-test split. The RandomNodeSplit function creates a training and test mask, that is used by the functions below:

In [ ]:

_transform = torch_geometric.transforms.RandomNodeSplit(split='train_rest', num_val=0.3, num_test=0)
data = _transform(network.data)
print(data)

_transform = torch_geometric.transforms.RandomNodeSplit(split='train_rest', num_val=0.3, num_test=0) data = _transform(network.data) print(data)

Data(edge_index=[2, 800], num_nodes=100, y=[100, 1], x=[100, 100], train_mask=[100], val_mask=[100], test_mask=[100])

In [ ]:

out = model.forward(data.x, data.edge_index)
print(out[80])
print(data.y[80])

torch.nn.functional.binary_cross_entropy(out[1], data.y.float()[1])

out = model.forward(data.x, data.edge_index) print(out[80]) print(data.y[80]) torch.nn.functional.binary_cross_entropy(out[1], data.y.float()[1])

tensor([0.3950], grad_fn=<SelectBackward0>)
tensor([1])

tensor(0.4901, grad_fn=<BinaryCrossEntropyBackward0>)

The following function trains the network and plots the evolution of the training loss. Since we have a binary classification task, we use binary cross entropy as a loss function.

In [ ]:

model_1 = GCN(data, out_ch=1, hidden_dim=4)
epochs = 100
_lrn_rate = 0.1
optimizer = torch.optim.SGD(model_1.parameters(), lr=_lrn_rate)

model_1 = GCN(data, out_ch=1, hidden_dim=4) epochs = 100 _lrn_rate = 0.1 optimizer = torch.optim.SGD(model_1.parameters(), lr=_lrn_rate)

In [ ]:

_indices = np.arange(100)
_losses = []
model_1.train()
for _epoch in range(epochs):
    _error = 0
    np.random.shuffle(_indices)
    for _i in _indices:
        if data.train_mask[_i]:
            optimizer.zero_grad()
            _output = model_1(data.x, data.edge_index)
            _loss = torch.nn.functional.binary_cross_entropy(_output[_i], data.y.float()[_i])
            _loss.backward()
            optimizer.step()
            _error = _error + _loss.detach().numpy()
    _losses.append(_error)
plt.plot(range(epochs), _losses)

_indices = np.arange(100) _losses = [] model_1.train() for _epoch in range(epochs): _error = 0 np.random.shuffle(_indices) for _i in _indices: if data.train_mask[_i]: optimizer.zero_grad() _output = model_1(data.x, data.edge_index) _loss = torch.nn.functional.binary_cross_entropy(_output[_i], data.y.float()[_i]) _loss.backward() optimizer.step() _error = _error + _loss.detach().numpy() _losses.append(_error) plt.plot(range(epochs), _losses)

In [ ]:

model_1.forward(data.x, data.edge_index)

model_1.forward(data.x, data.edge_index)

tensor([[0.0859],
        [0.1164],
        [0.4987],
        [0.4477],
        [0.3895],
        [0.3264],
        [0.2678],
        [0.2146],
        [0.1795],
        [0.1714],
        [0.1379],
        [0.1037],
        [0.2019],
        [0.1210],
        [0.1139],
        [0.1078],
        [0.1010],
        [0.0961],
        [0.0883],
        [0.0808],
        [0.0738],
        [0.0676],
        [0.0619],
        [0.2234],
        [0.0576],
        [0.0544],
        [0.0522],
        [0.0506],
        [0.0495],
        [0.0490],
        [0.0485],
        [0.0482],
        [0.0481],
        [0.0478],
        [0.3293],
        [0.0471],
        [0.0460],
        [0.0448],
        [0.0438],
        [0.0431],
        [0.0431],
        [0.0440],
        [0.0468],
        [0.0513],
        [0.0654],
        [0.3834],
        [0.7402],
        [0.7005],
        [0.6912],
        [0.7145],
        [0.7640],
        [0.8227],
        [0.8778],
        [0.9208],
        [0.9497],
        [0.9674],
        [0.4612],
        [0.9778],
        [0.9837],
        [0.9869],
        [0.9885],
        [0.9894],
        [0.9898],
        [0.9897],
        [0.9914],
        [0.9891],
        [0.9879],
        [0.5077],
        [0.9873],
        [0.9867],
        [0.9862],
        [0.9781],
        [0.9847],
        [0.9834],
        [0.9820],
        [0.9821],
        [0.9797],
        [0.9778],
        [0.5354],
        [0.9760],
        [0.9672],
        [0.9735],
        [0.9735],
        [0.9744],
        [0.9761],
        [0.9782],
        [0.9803],
        [0.9810],
        [0.9827],
        [0.5276],
        [0.9836],
        [0.9833],
        [0.9732],
        [0.9775],
        [0.9699],
        [0.9564],
        [0.9341],
        [0.9050],
        [0.8568],
        [0.7976]], grad_fn=<SigmoidBackward0>)

In [ ]:

_output = model_1.forward(data.x, data.edge_index)
_prediction = _output.round().long()
colors_1 = {}
for _v in network.nodes:
    _index = network.mapping.to_idx(_v)
    if data.val_mask[_index]:
        if _prediction[_index] == 0:
            colors_1[_v] = 'blue'
        else:
            colors_1[_v] = 'orange'
    else:
        colors_1[_v] = 'gray'
pp.plot(network, edge_color='gray', node_color=colors_1);

_output = model_1.forward(data.x, data.edge_index) _prediction = _output.round().long() colors_1 = {} for _v in network.nodes: _index = network.mapping.to_idx(_v) if data.val_mask[_index]: if _prediction[_index] == 0: colors_1[_v] = 'blue' else: colors_1[_v] = 'orange' else: colors_1[_v] = 'gray' pp.plot(network, edge_color='gray', node_color=colors_1);

Do We Really Need a One-Hot Encoding?¶

As discussed above, using a one-hot encoding as node features effectively gives every node its own free, independently learnable embedding vector already in the first layer of the GCN, before any message passing even takes place. This raises a legitimate concern: does our classifier actually learn something about the topology of the network, or could it simply be memorizing individual node identities via this per-node lookup, which would not generalize to any node outside of the training graph?

To test this, we repeat the exact same classification experiment, but replace the 100-dimensional one-hot encoding with a much lower-dimensional random feature vector for every node. Since a low-dimensional random vector does not act as a unique identifier for a node (many nodes may even have very similar values), the GCN can no longer rely on a per-node lookup and has to exploit the actual graph topology (via message passing) to succeed.

In [ ]:

from sklearn.metrics import balanced_accuracy_score
results = {}
for feature_dim in [1, 2, 4, 8, network.n]:
    torch.manual_seed(0)
    if feature_dim == network.n:
        network.data.x = torch.eye(network.n, dtype=torch.float32)
        label = f'one-hot ({network.n}-dim)'
    else:
        network.data.x = torch.rand(network.n, feature_dim)
        label = f'{feature_dim}-dim random'
    _transform = torch_geometric.transforms.RandomNodeSplit(split='train_rest', num_val=0.3, num_test=0)
    data_1 = _transform(network.data)
    model_2 = GCN(data_1, out_ch=1, hidden_dim=4)
    optimizer_1 = torch.optim.SGD(model_2.parameters(), lr=0.1)
    _indices = np.arange(network.n)
    model_2.train()
    for _epoch in range(100):
        np.random.shuffle(_indices)
        for _i in _indices:
            if data_1.train_mask[_i]:
                optimizer_1.zero_grad()
                _output = model_2(data_1.x, data_1.edge_index)
                _loss = torch.nn.functional.binary_cross_entropy(_output[_i], data_1.y.float()[_i])
                _loss.backward()
                optimizer_1.step()
    _output = model_2.forward(data_1.x, data_1.edge_index)
    _prediction = _output.round().long()
    val_acc = balanced_accuracy_score(data_1.y[data_1.val_mask].cpu().numpy(), _prediction[data_1.val_mask].cpu().numpy())
    results[label] = val_acc
    print(f'{label:>20}: validation balanced accuracy = {val_acc:.3f}')

from sklearn.metrics import balanced_accuracy_score results = {} for feature_dim in [1, 2, 4, 8, network.n]: torch.manual_seed(0) if feature_dim == network.n: network.data.x = torch.eye(network.n, dtype=torch.float32) label = f'one-hot ({network.n}-dim)' else: network.data.x = torch.rand(network.n, feature_dim) label = f'{feature_dim}-dim random' _transform = torch_geometric.transforms.RandomNodeSplit(split='train_rest', num_val=0.3, num_test=0) data_1 = _transform(network.data) model_2 = GCN(data_1, out_ch=1, hidden_dim=4) optimizer_1 = torch.optim.SGD(model_2.parameters(), lr=0.1) _indices = np.arange(network.n) model_2.train() for _epoch in range(100): np.random.shuffle(_indices) for _i in _indices: if data_1.train_mask[_i]: optimizer_1.zero_grad() _output = model_2(data_1.x, data_1.edge_index) _loss = torch.nn.functional.binary_cross_entropy(_output[_i], data_1.y.float()[_i]) _loss.backward() optimizer_1.step() _output = model_2.forward(data_1.x, data_1.edge_index) _prediction = _output.round().long() val_acc = balanced_accuracy_score(data_1.y[data_1.val_mask].cpu().numpy(), _prediction[data_1.val_mask].cpu().numpy()) results[label] = val_acc print(f'{label:>20}: validation balanced accuracy = {val_acc:.3f}')

        1-dim random: validation balanced accuracy = 0.805
        2-dim random: validation balanced accuracy = 0.593
        4-dim random: validation balanced accuracy = 0.839
        8-dim random: validation balanced accuracy = 0.962
   one-hot (100-dim): validation balanced accuracy = 0.950

The exact numbers vary a bit between runs (this is a small, 100-node graph trained with plain SGD for a fixed, fairly small number of epochs, so individual results are noisy), but the overall pattern is clear: already with a handful of random input dimensions, dramatically fewer than the 100 dimensions required for a one-hot encoding, the GCN reaches an accuracy that is close to (and sometimes on par with) the one-hot baseline. A single random dimension is occasionally enough to beat chance level, but is not reliable; by around 8 random dimensions, performance consistently approaches the one-hot result.

This confirms that the classification signal is coming from the topology of the graph, propagated through message passing, and not from memorized per-node identities: a low-dimensional random vector cannot possibly serve as a unique lookup key for all 100 nodes, so the only way for the model to succeed is by aggregating and comparing feature information along the edges of the graph. A one-hot encoding is a convenient choice exactly because it requires no real attribute data and trivially provides every node with a distinct input, but as discussed above this comes at the cost of not scaling to large graphs and not generalizing to nodes outside of the training graph. Low-dimensional random features avoid both of these problems, though in practice we of course prefer real, informative node attributes whenever they are available, as we will see in the next notebook.

Viusalizing feature maps¶

We can visualize the latent representations generated by the first hidden layer of our model.

In [ ]:

embedding = model_2.input_to_hidden.forward(data_1.x, data_1.edge_index)
print(embedding)

embedding = model_2.input_to_hidden.forward(data_1.x, data_1.edge_index) print(embedding)

tensor([[-0.2943, -0.4716,  0.8659, -0.4757],
        [-0.2845, -0.4209,  0.7766, -0.4783],
        [-0.1201, -0.1197,  0.1797, -0.4697],
        [-0.1635, -0.1939,  0.3085, -0.4641],
        [-0.2269, -0.2786,  0.4763, -0.4519],
        [-0.2926, -0.3802,  0.6718, -0.4585],
        [-0.3339, -0.4605,  0.8228, -0.4481],
        [-0.3853, -0.5319,  0.9253, -0.4486],
        [-0.4077, -0.5548,  0.9918, -0.4324],
        [-0.3984, -0.5670,  1.0104, -0.4217],
        [-0.4107, -0.5976,  1.0824, -0.4518],
        [-0.4350, -0.6474,  1.1748, -0.4746],
        [-0.2361, -0.3057,  0.5592, -0.4335],
        [-0.4161, -0.6104,  1.0928, -0.4608],
        [-0.4000, -0.6138,  1.0673, -0.4721],
        [-0.3815, -0.5826,  1.0205, -0.4650],
        [-0.3748, -0.5835,  1.0063, -0.4615],
        [-0.3642, -0.5807,  1.0095, -0.4579],
        [-0.3663, -0.5864,  1.0345, -0.4732],
        [-0.3719, -0.5850,  1.0416, -0.4682],
        [-0.3929, -0.5989,  1.0526, -0.4544],
        [-0.3936, -0.6008,  1.0654, -0.4604],
        [-0.3982, -0.6077,  1.0910, -0.4587],
        [-0.2170, -0.2704,  0.4988, -0.4631],
        [-0.4082, -0.6119,  1.1043, -0.4642],
        [-0.4189, -0.6333,  1.1202, -0.4693],
        [-0.4350, -0.6335,  1.1273, -0.4750],
        [-0.4455, -0.6390,  1.1290, -0.4829],
        [-0.4465, -0.6454,  1.1267, -0.4715],
        [-0.4599, -0.6460,  1.1404, -0.4672],
        [-0.4406, -0.6287,  1.1238, -0.4801],
        [-0.4322, -0.6364,  1.1100, -0.4742],
        [-0.4225, -0.6128,  1.0930, -0.4705],
        [-0.4100, -0.6043,  1.0792, -0.4716],
        [-0.1524, -0.1516,  0.2858, -0.4371],
        [-0.3941, -0.5892,  1.0549, -0.4625],
        [-0.3679, -0.5677,  1.0391, -0.4777],
        [-0.3474, -0.5513,  1.0225, -0.4815],
        [-0.3401, -0.5475,  1.0192, -0.4969],
        [-0.3221, -0.5518,  1.0152, -0.5089],
        [-0.3337, -0.5631,  1.0373, -0.4941],
        [-0.3398, -0.5575,  1.0318, -0.4818],
        [-0.3277, -0.5590,  1.0133, -0.4775],
        [-0.3380, -0.5628,  1.0140, -0.4716],
        [-0.3035, -0.5060,  0.9141, -0.4817],
        [-0.1199, -0.1119,  0.2037, -0.4824],
        [-0.1012, -0.0864,  0.0919, -0.5147],
        [-0.1173, -0.1041,  0.1140, -0.5039],
        [-0.1131, -0.0987,  0.0954, -0.4896],
        [-0.0979, -0.0468,  0.0365, -0.4747],
        [-0.0436,  0.0125, -0.0676, -0.4825],
        [ 0.0345,  0.1244, -0.2617, -0.5047],
        [ 0.1142,  0.2347, -0.4940, -0.5062],
        [ 0.1903,  0.3852, -0.7287, -0.5112],
        [ 0.2713,  0.5046, -0.9426, -0.5269],
        [ 0.3330,  0.5914, -1.0989, -0.5246],
        [-0.0912, -0.0542,  0.1206, -0.4912],
        [ 0.3838,  0.6590, -1.2163, -0.5480],
        [ 0.4202,  0.7104, -1.3128, -0.5603],
        [ 0.4319,  0.7378, -1.3702, -0.5702],
        [ 0.4251,  0.7620, -1.3869, -0.5815],
        [ 0.4128,  0.7650, -1.3685, -0.5699],
        [ 0.3932,  0.7515, -1.3183, -0.5631],
        [ 0.3886,  0.7214, -1.2857, -0.5739],
        [ 0.3717,  0.7294, -1.3006, -0.5953],
        [ 0.3532,  0.6959, -1.2074, -0.5704],
        [ 0.3512,  0.6757, -1.1717, -0.5505],
        [-0.0905, -0.0405,  0.0822, -0.4920],
        [ 0.3431,  0.6552, -1.1403, -0.5345],
        [ 0.3587,  0.6321, -1.1305, -0.5299],
        [ 0.3667,  0.6186, -1.1322, -0.5251],
        [ 0.2984,  0.5257, -0.9947, -0.5379],
        [ 0.3599,  0.5938, -1.1530, -0.5407],
        [ 0.3529,  0.5981, -1.1315, -0.5425],
        [ 0.3715,  0.5873, -1.1171, -0.5401],
        [ 0.3675,  0.5990, -1.1172, -0.5426],
        [ 0.3542,  0.5927, -1.0931, -0.5495],
        [ 0.3540,  0.5865, -1.0986, -0.5657],
        [-0.0838, -0.0457,  0.0819, -0.4825],
        [ 0.3512,  0.5869, -1.0858, -0.5811],
        [ 0.3416,  0.5648, -0.9985, -0.5498],
        [ 0.3673,  0.6038, -1.0652, -0.5793],
        [ 0.3665,  0.6266, -1.0560, -0.5601],
        [ 0.3674,  0.6167, -1.0670, -0.5440],
        [ 0.3578,  0.6237, -1.0730, -0.5316],
        [ 0.3773,  0.6259, -1.0874, -0.5375],
        [ 0.3915,  0.6293, -1.1145, -0.5325],
        [ 0.4029,  0.6429, -1.1189, -0.5226],
        [ 0.3894,  0.6590, -1.1372, -0.5080],
        [-0.1025, -0.0773,  0.1023, -0.4744],
        [ 0.3838,  0.6451, -1.1456, -0.5211],
        [ 0.3571,  0.6191, -1.1206, -0.5095],
        [ 0.2899,  0.4997, -0.9460, -0.5462],
        [ 0.2905,  0.5297, -0.9751, -0.5314],
        [ 0.2601,  0.4595, -0.8817, -0.5410],
        [ 0.2002,  0.3888, -0.7618, -0.5244],
        [ 0.1216,  0.2811, -0.5719, -0.5081],
        [ 0.0552,  0.1785, -0.3767, -0.5122],
        [-0.0060,  0.0549, -0.1693, -0.5095],
        [-0.0691, -0.0366, -0.0082, -0.4972]], grad_fn=<ScatterAddBackward0>)

In [ ]:

_svd = TruncatedSVD()
_low_dim = _svd.fit_transform(embedding.detach().numpy())
colors_2 = {}
for _v in network.nodes:
    _index = network.mapping.to_idx(_v)
    if data_1.val_mask[_index]:
        colors_2[_index] = 'grey'
    elif data_1.y[_index] == 0:
        colors_2[_index] = 'blue'
    else:
        colors_2[_index] = 'orange'
plt.scatter(_low_dim[:, 0], _low_dim[:, 1], c=colors_2.values())

_svd = TruncatedSVD() _low_dim = _svd.fit_transform(embedding.detach().numpy()) colors_2 = {} for _v in network.nodes: _index = network.mapping.to_idx(_v) if data_1.val_mask[_index]: colors_2[_index] = 'grey' elif data_1.y[_index] == 0: colors_2[_index] = 'blue' else: colors_2[_index] = 'orange' plt.scatter(_low_dim[:, 0], _low_dim[:, 1], c=colors_2.values())

Application to network with non-linear pattern in latent space¶

We can now use this model to classify nodes in a synthetic example network generated based on a non-linear pattern in a two-dimensional latent space. We reuse the example from Laplacian Eigenmaps and Logistic Regression, i.e. we generate a network based on the circles data set in sklearn.

In [ ]:

x, c = make_circles(n_samples=200, noise=0.05, factor=0.5)
data_2 = pd.DataFrame({'x0': x[:, 0], 'x1': x[:, 1], 'y_class': c})
sns.scatterplot(x='x0', y='x1', data=data_2, hue='y_class')
plt.xlabel('$X_0$', fontsize=16)
plt.ylabel('$X_1$', fontsize=16)

x, c = make_circles(n_samples=200, noise=0.05, factor=0.5) data_2 = pd.DataFrame({'x0': x[:, 0], 'x1': x[:, 1], 'y_class': c}) sns.scatterplot(x='x0', y='x1', data=data_2, hue='y_class') plt.xlabel('$X_0$', fontsize=16) plt.ylabel('$X_1$', fontsize=16)

In [ ]:

def euclidean_dist(x, y):
    """Return the Euclidean distance between two points."""
    return np.linalg.norm(x-y)

def soft_rule(dist, **kwargs):
    """Randomly decide whether to connect two nodes at the given distance."""
    p = kwargs['beta'] * np.exp(-dist/kwargs['alpha'])
    if np.random.random() <= p:
        return True
    else:
        return False

def euclidean_dist(x, y): """Return the Euclidean distance between two points.""" return np.linalg.norm(x-y) def soft_rule(dist, **kwargs): """Randomly decide whether to connect two nodes at the given distance.""" p = kwargs['beta'] * np.exp(-dist/kwargs['alpha']) if np.random.random() <= p: return True else: return False

In [ ]:

nodes = []
pos = {}
g = {}
cluster = []
for _i, row in data_2.iterrows():
    nodes.append(str(_i))
    pos[str(_i)] = np.array([row['x0'], row['x1']])
    g[str(_i)] = c[_i]
    cluster.append(torch.tensor([c[_i]]))
edges = []
for _v in nodes:
    for w in nodes:
        if soft_rule(euclidean_dist(pos[_v], pos[w]), alpha=0.05, beta=50) and _v != w:
            edges.append((_v, w))
net = pp.Graph.from_edge_list(edges).to_undirected()
net.data.y = torch.tensor(cluster).unsqueeze_(-1)
net.data.x = torch.eye(net.n, dtype=torch.float32)
print(net.data)

nodes = [] pos = {} g = {} cluster = [] for _i, row in data_2.iterrows(): nodes.append(str(_i)) pos[str(_i)] = np.array([row['x0'], row['x1']]) g[str(_i)] = c[_i] cluster.append(torch.tensor([c[_i]])) edges = [] for _v in nodes: for w in nodes: if soft_rule(euclidean_dist(pos[_v], pos[w]), alpha=0.05, beta=50) and _v != w: edges.append((_v, w)) net = pp.Graph.from_edge_list(edges).to_undirected() net.data.y = torch.tensor(cluster).unsqueeze_(-1) net.data.x = torch.eye(net.n, dtype=torch.float32) print(net.data)

Data(edge_index=[2, 2348], num_nodes=200, y=[200, 1], x=[200, 200])

In [ ]:

colors_3 = {}
colors_3[0] = 'CornflowerBlue'
colors_3[1] = 'orange'
for _v in nodes:
    colors_3[_v] = colors_3[g[_v]]
pp.plot(net, edge_color='grey', node_color=colors_3);

colors_3 = {} colors_3[0] = 'CornflowerBlue' colors_3[1] = 'orange' for _v in nodes: colors_3[_v] = colors_3[g[_v]] pp.plot(net, edge_color='grey', node_color=colors_3);

In [ ]:

_transform = torch_geometric.transforms.RandomNodeSplit(split='train_rest', num_val=0.3, num_test=0)
data_3 = _transform(net.data)

_transform = torch_geometric.transforms.RandomNodeSplit(split='train_rest', num_val=0.3, num_test=0) data_3 = _transform(net.data)

In [ ]:

model_3 = GCN(net.data, out_ch=1, hidden_dim=4)
epochs_1 = 100
_lrn_rate = 0.1
optimizer_2 = torch.optim.SGD(model_3.parameters(), lr=_lrn_rate)

model_3 = GCN(net.data, out_ch=1, hidden_dim=4) epochs_1 = 100 _lrn_rate = 0.1 optimizer_2 = torch.optim.SGD(model_3.parameters(), lr=_lrn_rate)

In [ ]:

_indices = np.arange(net.n)
_losses = []
model_3.train()
for _epoch in range(epochs_1):
    _error = 0
    np.random.shuffle(_indices)
    for _i in _indices:
        if data_3.train_mask[_i]:
            optimizer_2.zero_grad()
            _output = model_3(net.data.x, net.data.edge_index)
            _loss = torch.nn.functional.binary_cross_entropy(_output[_i], data_3.y.float()[_i])
            _loss.backward()
            optimizer_2.step()
            _error = _error + _loss.detach().numpy()
    _losses.append(_error)
plt.plot(range(epochs_1), _losses)

_indices = np.arange(net.n) _losses = [] model_3.train() for _epoch in range(epochs_1): _error = 0 np.random.shuffle(_indices) for _i in _indices: if data_3.train_mask[_i]: optimizer_2.zero_grad() _output = model_3(net.data.x, net.data.edge_index) _loss = torch.nn.functional.binary_cross_entropy(_output[_i], data_3.y.float()[_i]) _loss.backward() optimizer_2.step() _error = _error + _loss.detach().numpy() _losses.append(_error) plt.plot(range(epochs_1), _losses)

In [ ]:

_output = model_3.forward(net.data.x, net.data.edge_index)
_prediction = _output.round().long()
_node_cols = {}
for _v in net.nodes:
    _index = net.mapping.to_idx(_v)
    if data_3.val_mask[_index]:
        _node_cols[_v] = colors_3[_prediction[_index].item()]
    else:
        _node_cols[_v] = 'gray'
pp.plot(net, edge_color='gray', node_color=_node_cols);

_output = model_3.forward(net.data.x, net.data.edge_index) _prediction = _output.round().long() _node_cols = {} for _v in net.nodes: _index = net.mapping.to_idx(_v) if data_3.val_mask[_index]: _node_cols[_v] = colors_3[_prediction[_index].item()] else: _node_cols[_v] = 'gray' pp.plot(net, edge_color='gray', node_color=_node_cols);

In [ ]:

embedding_1 = model_3.input_to_hidden.forward(data_3.x, data_3.edge_index)
_svd = TruncatedSVD()
_low_dim = _svd.fit_transform(embedding_1.detach().numpy())
color_points = {}
for _v in net.nodes:
    _index = net.mapping.to_idx(_v)
    if data_3.val_mask[_index]:
        color_points[_index] = 'grey'
    else:
        color_points[_index] = colors_3[net.data.y[_index].item()]
plt.scatter(_low_dim[:, 0], _low_dim[:, 1], c=color_points.values())

embedding_1 = model_3.input_to_hidden.forward(data_3.x, data_3.edge_index) _svd = TruncatedSVD() _low_dim = _svd.fit_transform(embedding_1.detach().numpy()) color_points = {} for _v in net.nodes: _index = net.mapping.to_idx(_v) if data_3.val_mask[_index]: color_points[_index] = 'grey' else: color_points[_index] = colors_3[net.data.y[_index].item()] plt.scatter(_low_dim[:, 0], _low_dim[:, 1], c=color_points.values())

Application to empirical network¶

In [ ]:

karate = pp.io.read_netzschleuder_graph(name='karate', network='78')
karate.data.y = torch.tensor(karate.data.node_groups-1, dtype=torch.float)
karate.data.y.unsqueeze_(-1)
karate.data.x = torch.eye(karate.n, dtype=torch.float32)
print(karate)
pp.plot(karate, edge_color='gray',  node_color=[karate["node_groups", v].item() for v in karate.nodes]);

karate = pp.io.read_netzschleuder_graph(name='karate', network='78') karate.data.y = torch.tensor(karate.data.node_groups-1, dtype=torch.float) karate.data.y.unsqueeze_(-1) karate.data.x = torch.eye(karate.n, dtype=torch.float32) print(karate) pp.plot(karate, edge_color='gray', node_color=[karate["node_groups", v].item() for v in karate.nodes]);

/tmp/marimo_39408/__marimo__cell_fwwy_.py:2: UserWarning: To copy construct from a tensor, it is recommended to use sourceTensor.detach().clone() or sourceTensor.detach().clone().requires_grad_(True), rather than torch.tensor(sourceTensor).
  karate.data.y = torch.tensor(karate.data.node_groups-1, dtype=torch.float)

Undirected graph with 34 nodes and 78 edges
{   'Edge Attributes': {},
    'Graph Attributes': {   'analyses_average_degree': "<class 'float'>",
                            'analyses_degree_assortativity': "<class 'float'>",
                            'analyses_degree_std_dev': "<class 'float'>",
                            'analyses_diameter': "<class 'int'>",
                            'analyses_edge_properties': "<class 'list'>",
                            'analyses_edge_reciprocity': "<class 'float'>",
                            'analyses_global_clustering': "<class 'float'>",
                            'analyses_hashimoto_radius': "<class 'float'>",
                            'analyses_is_bipartite': "<class 'bool'>",
                            'analyses_is_directed': "<class 'bool'>",
                            'analyses_knn_proj_1': "<class 'float'>",
                            'analyses_knn_proj_2': "<class 'float'>",
                            'analyses_largest_component_fraction': "<class 'float'>",
                            'analyses_mixing_time': "<class 'float'>",
                            'analyses_num_edges': "<class 'int'>",
                            'analyses_num_vertices': "<class 'int'>",
                            'analyses_transition_gap': "<class 'float'>",
                            'analyses_vertex_properties': "<class 'list'>",
                            'num_nodes': "<class 'int'>"},
    'Node Attributes': {   'node__pos': "<class 'numpy.ndarray'>",
                           'node_groups': "<class 'torch.Tensor'> -> torch.Size([34])",
                           'node_name': "<class 'torch.Tensor'> -> torch.Size([34])"}}

In [ ]:

_transform = torch_geometric.transforms.RandomNodeSplit(split='train_rest', num_val=0.3, num_test=0)
data_4 = _transform(karate.data)

_transform = torch_geometric.transforms.RandomNodeSplit(split='train_rest', num_val=0.3, num_test=0) data_4 = _transform(karate.data)

In [ ]:

model_4 = GCN(data_4, out_ch=1, hidden_dim=4)
epochs_2 = 200
_lrn_rate = 0.1
optimizer_3 = torch.optim.SGD(model_4.parameters(), lr=_lrn_rate)

model_4 = GCN(data_4, out_ch=1, hidden_dim=4) epochs_2 = 200 _lrn_rate = 0.1 optimizer_3 = torch.optim.SGD(model_4.parameters(), lr=_lrn_rate)

In [ ]:

_indices = np.arange(karate.n)
_losses = []
model_4.train()
for _epoch in range(epochs_2):
    _error = 0
    np.random.shuffle(_indices)
    for _i in _indices:
        if data_4.train_mask[_i]:
            optimizer_3.zero_grad()
            _output = model_4(data_4.x, data_4.edge_index)
            _loss = torch.nn.functional.binary_cross_entropy(_output[_i], data_4.y[_i])
            _loss.backward()
            optimizer_3.step()
            _error = _error + _loss.detach().numpy()
    _losses.append(_error)
plt.plot(range(epochs_2), _losses)

_indices = np.arange(karate.n) _losses = [] model_4.train() for _epoch in range(epochs_2): _error = 0 np.random.shuffle(_indices) for _i in _indices: if data_4.train_mask[_i]: optimizer_3.zero_grad() _output = model_4(data_4.x, data_4.edge_index) _loss = torch.nn.functional.binary_cross_entropy(_output[_i], data_4.y[_i]) _loss.backward() optimizer_3.step() _error = _error + _loss.detach().numpy() _losses.append(_error) plt.plot(range(epochs_2), _losses)

In [ ]:

_output = model_4.forward(data_4.x, data_4.edge_index)
_prediction = _output.round().long()
_node_cols = {}
for _v in karate.nodes:
    _index = karate.mapping.to_idx(_v)
    if data_4.val_mask[_index]:
        if _prediction[_index] == 0:
            _node_cols[_v] = 'CornflowerBlue'
        else:
            _node_cols[_v] = 'orange'
    else:
        _node_cols[_v] = 'gray'
pp.plot(karate, edge_color='gray', node_color=_node_cols);

_output = model_4.forward(data_4.x, data_4.edge_index) _prediction = _output.round().long() _node_cols = {} for _v in karate.nodes: _index = karate.mapping.to_idx(_v) if data_4.val_mask[_index]: if _prediction[_index] == 0: _node_cols[_v] = 'CornflowerBlue' else: _node_cols[_v] = 'orange' else: _node_cols[_v] = 'gray' pp.plot(karate, edge_color='gray', node_color=_node_cols);

In [ ]:

embedding_2 = model_4.input_to_hidden.forward(data_4.x, data_4.edge_index)
_low_dim = TruncatedSVD().fit_transform(embedding_2.detach().numpy())
colors_4 = {}
for _v in karate.nodes:
    _index = karate.mapping.to_idx(_v)
    if data_4.y[_index].item() == 0:
        colors_4[_index] = 'CornflowerBlue'
    else:
        colors_4[_index] = 'orange'
plt.scatter(_low_dim[:, 0], _low_dim[:, 1], c=colors_4.values())

embedding_2 = model_4.input_to_hidden.forward(data_4.x, data_4.edge_index) _low_dim = TruncatedSVD().fit_transform(embedding_2.detach().numpy()) colors_4 = {} for _v in karate.nodes: _index = karate.mapping.to_idx(_v) if data_4.y[_index].item() == 0: colors_4[_index] = 'CornflowerBlue' else: colors_4[_index] = 'orange' plt.scatter(_low_dim[:, 0], _low_dim[:, 1], c=colors_4.values())