# How to use Scikit-Learn Label Propagation on graph structured data?

As part of my research, I am interested in performing label propagation on a graph. I am especially interested in those two methods:

I saw that scikit-learn offer a model to do that. However, this model is supposed to be applied on vector structured data (i.e. data points).

The model builds an affinity matrix from the data points using a kernel, and then run the algorithm on the constructed matrix. I would like to be able to directly input the adjacency matrix of my graph in place of the similarity matrix.

Any idea on how to achieve that? Or do you know any Python library that will allow to run label propagation directly on graph structured data for the two aforementioned methods?

• Have you checked the Scikit-learn source code to see what it does after calculating the affinity matrix? Maybe could "copy" the code after that part to apply it directly to your adjacency matrix. Feb 12, 2019 at 19:02
• Thanks for your comment! So, actually, this is what I am currently doing, but some parts of the code I need to modify to suit my needs are somewhat cryptic. I am afraid rewriting those parts will lead to errors. I was hoping there existed a more straightforward method. Feb 12, 2019 at 19:47
• The source code at github.com/scikit-learn/scikit-learn/blob/7389dba/sklearn/… - says that implementations should override _build_graph method. So natually you should try creating a derived class which accepts precomputed matrix. Feb 14, 2019 at 11:58

Answering my own question here, as I hope it will be useful to some readers.

Scikit-learn is primarily designed to deal with vector structured data. Hence, if you want to perform label propagation/label spreading on graph-structured data, you're probably better off reimplementing the method yourself rather than using Scikit interface.

Here is an implementation of Label Propagation and Label Spreading in PyTorch.

The two methods overall follow the same algorithmic steps, with variations on how the adjacency matrix is normalized and how the labels are propagated at each step. Let's, therefore, create a base class for our two models.

from abc import abstractmethod
import torch

class BaseLabelPropagation:
"""Base class for label propagation models.

Parameters
----------
"""
self.one_hot_labels = None
self.n_classes = None
self.predictions = None

@staticmethod
@abstractmethod
raise NotImplementedError("_normalize must be implemented")

@abstractmethod
def _propagate(self):
raise NotImplementedError("_propagate must be implemented")

def _one_hot_encode(self, labels):
# Get the number of classes
classes = torch.unique(labels)
classes = classes[classes != -1]
self.n_classes = classes.size(0)

# One-hot encode labeled data instances and zero rows corresponding to unlabeled instances
labels = labels.clone()  # defensive copying
self.one_hot_labels = torch.zeros((self.n_nodes, self.n_classes), dtype=torch.float)
self.one_hot_labels = self.one_hot_labels.scatter(1, labels.unsqueeze(1), 1)

def fit(self, labels, max_iter, tol):
"""Fits a semi-supervised learning label propagation model.

labels: torch.LongTensor
Tensor of size n_nodes indicating the class number of each node.
Unlabeled nodes are denoted with -1.
max_iter: int
Maximum number of iterations allowed.
tol: float
Convergence tolerance: threshold to consider the system at steady state.
"""
self._one_hot_encode(labels)

self.predictions = self.one_hot_labels.clone()
prev_predictions = torch.zeros((self.n_nodes, self.n_classes), dtype=torch.float)

for i in range(max_iter):
# Stop iterations if the system is considered at a steady state
variation = torch.abs(self.predictions - prev_predictions).sum().item()

if variation < tol:
print(f"The method stopped after {i} iterations, variation={variation:.4f}.")
break

prev_predictions = self.predictions
self._propagate()

def predict(self):
return self.predictions

def predict_classes(self):
return self.predictions.max(dim=1).indices


The model takes as input the adjacency matrix of the graph as well as the labels of the nodes. The labels are in the form of a vector of an integer indicating the class number of each node with a -1 at the position of unlabeled nodes.

Label Propagation algorithm is presented below.

$$\begin{array}{l}{ \mathbf{W} \text {: adjacency matrix of the graph} \\ \text { Compute the diagonal degree matrix } \mathbf{D} \text { by } \mathbf{D}_{i i} \leftarrow \sum_{j} W_{i j}} \\ {\text { Initialize } \hat{Y}^{(0)} \leftarrow\left(y_{1}, \ldots, y_{l}, 0,0, \ldots, 0\right)} \\ {\text { Iterate }} \\ {\text { 1. } \hat{Y}^{(t+1)} \leftarrow \mathbf{D}^{-1} \mathbf{W} \hat{Y}^{(t)}} \\ {\text { 2. } \hat{Y}_{l}^{(t+1)} \leftarrow Y_{l}} \\ {\text { until convergence to } \hat{Y}^{(\infty)}} \\ {\text { Label point } x_{i} \text { by the sign of } \hat{y}_{i}^{(\infty)}}\end{array}$$

We get the following implementation.

class LabelPropagation(BaseLabelPropagation):

@staticmethod
"""Computes D^-1 * W"""
degs[degs == 0] = 1  # avoid division by 0 error

def _propagate(self):

# Put back already known labels

def fit(self, labels, max_iter=1000, tol=1e-3):
super().fit(labels, max_iter, tol)


$$\begin{array}{l}{ \mathbf{W} \text {: adjacency matrix of the graph} \\ \text { Compute the diagonal degree matrix } \mathbf{D} \text { by } \mathbf{D}_{i i} \leftarrow \sum_{j} W_{i j}} \\ {\text { Compute the normalized graph Laplacian } \\ \mathcal{L} \leftarrow \mathbf{D}^{-1 / 2} \mathbf{W} \mathbf{D}^{-1 / 2}} \\ {\text { Initialize } \hat{Y}^{(0)} \leftarrow\left(y_{1}, \ldots, y_{l}, 0,0, \ldots, 0\right)} \\ {\text { Choose a parameter } \alpha \in[0,1)} \\ {\text { Iterate } \hat{Y}(t+1) \leftarrow \alpha \mathcal{L} \hat{Y}^{(t)}+(1-\alpha) \hat{Y}^{(0)} \text { until convergence to } \hat{Y}^{(\infty)}} \\ {\text { Label point } x_{i} \text { by the sign of } \hat{y}_{i}^{(\infty)}} \end{array}$$

The implementation is, therefore, the following.

class LabelSpreading(BaseLabelPropagation):
self.alpha = None

@staticmethod
"""Computes D^-1/2 * W * D^-1/2"""
norm = torch.pow(degs, -0.5)
norm[torch.isinf(norm)] = 1
return adj_matrix * norm[:, None] * norm[None, :]

def _propagate(self):
self.predictions = (
+ (1 - self.alpha) * self.one_hot_labels
)

def fit(self, labels, max_iter=1000, tol=1e-3, alpha=0.5):
"""
Parameters
----------
alpha: float
Clamping factor.
"""
self.alpha = alpha
super().fit(labels, max_iter, tol)


Let's now test our propagation models on synthetic data. To do so, we choose to use a caveman graph.

import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

# Create caveman graph
n_cliques = 4
size_cliques = 10
caveman_graph = nx.connected_caveman_graph(n_cliques, size_cliques)

# Create labels
labels = np.full(n_cliques * size_cliques, -1.)

# Only one node per clique is labeled. Each clique belongs to a different class.
labels[0] = 0
labels[size_cliques] = 1
labels[size_cliques * 2] = 2
labels[size_cliques * 3] = 3

# Create input tensors
labels_t = torch.LongTensor(labels)

# Learn with Label Propagation
label_propagation.fit(labels_t)
label_propagation_output_labels = label_propagation.predict_classes()

# Plot graphs
color_map = {-1: "orange", 0: "blue", 1: "green", 2: "red", 3: "cyan"}
input_labels_colors = [color_map[l] for l in labels]
lprop_labels_colors = [color_map[l] for l in label_propagation_output_labels.numpy()]

plt.figure(figsize=(14, 6))
ax1 = plt.subplot(1, 4, 1)
ax2 = plt.subplot(1, 4, 2)
ax3 = plt.subplot(1, 4, 3)

ax1.title.set_text("Raw data (4 classes)")
ax2.title.set_text("Label Propagation")

pos = nx.spring_layout(caveman_graph)
nx.draw(caveman_graph, ax=ax1, pos=pos, node_color=input_labels_colors, node_size=50)
nx.draw(caveman_graph, ax=ax2, pos=pos, node_color=lprop_labels_colors, node_size=50)

# Legend
ax4 = plt.subplot(1, 4, 4)
ax4.axis("off")
legend_colors = ["orange", "blue", "green", "red", "cyan"]
legend_labels = ["unlabeled", "class 0", "class 1", "class 2", "class 3"]
dummy_legend = [ax4.plot([], [], ls='-', c=c)[0] for c in legend_colors]
plt.legend(dummy_legend, legend_labels)

plt.show()


The implemented models work correctly and allow to detect the communities in the graph.

Note: The propagation methods presented are meant to be used on undirected graphs.

The code is available as an interactive Jupyter notebook here.