Como usar a Propagação de etiquetas Scikit-Learn em dados estruturados em gráficos?

11

Como parte da minha pesquisa, estou interessado em realizar a propagação de rótulos em um gráfico. Estou especialmente interessado nesses dois métodos:

Vi que o scikit-learn oferece um modelo para fazer isso. No entanto, esse modelo deve ser aplicado em dados estruturados vetoriais ( isto é, pontos de dados).

O modelo constrói uma matriz de afinidade a partir dos pontos de dados usando um kernel e, em seguida, executa o algoritmo na matriz construída. Gostaria de poder inserir diretamente a matriz de adjacência do meu gráfico no lugar da matriz de similaridade.

Alguma idéia de como conseguir isso? Ou você conhece alguma biblioteca Python que permitirá executar a propagação de rótulos diretamente nos dados estruturados em gráficos para os dois métodos mencionados acima?

Agradeço antecipadamente por sua ajuda!

Thibaud Martinez
fonte
Você verificou o código-fonte do Scikit-learn para ver o que ele faz depois de calcular a matriz de afinidade? Talvez possa "copiar" o código após essa parte para aplicá-lo diretamente à sua matriz de adjacência.
Tasos
Obrigado por seu comentário! Então, na verdade, é isso que estou fazendo atualmente, mas algumas partes do código que preciso modificar para atender às minhas necessidades são um tanto enigmáticas. Receio que reescrever essas partes levará a erros. Eu esperava que houvesse um método mais direto.
Thibaud Martinez
11
O código fonte em github.com/scikit-learn/scikit-learn/blob/7389dba/sklearn/… - diz que as implementações devem substituir o método _build_graph. Então, naturalmente, você deve tentar criar uma classe derivada que aceite matriz pré-computada.
Mikalai 14/02/19

Respostas:

2

Respondendo minha própria pergunta aqui, pois espero que seja útil para alguns leitores.

O Scikit-learn foi desenvolvido principalmente para lidar com dados estruturados de vetor. Portanto, se você deseja executar a propagação / propagação de rótulos nos dados estruturados em gráficos, provavelmente é melhor reimplementar o método sozinho, em vez de usar a interface Scikit.

Aqui está uma implementação de Propagação de rótulo e Propagação de rótulo no PyTorch.

No geral, os dois métodos seguem as mesmas etapas algorítmicas, com variações em como a matriz de adjacência é normalizada e como os rótulos são propagados em cada etapa. Vamos, portanto, criar uma classe base para nossos dois modelos.

from abc import abstractmethod
import torch

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

    Parameters
    ----------
    adj_matrix: torch.FloatTensor
        Adjacency matrix of the graph.
    """
    def __init__(self, adj_matrix):
        self.norm_adj_matrix = self._normalize(adj_matrix)
        self.n_nodes = adj_matrix.size(0)
        self.one_hot_labels = None 
        self.n_classes = None
        self.labeled_mask = None
        self.predictions = None

    @staticmethod
    @abstractmethod
    def _normalize(adj_matrix):
        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
        unlabeled_mask = (labels == -1)
        labels = labels.clone()  # defensive copying
        labels[unlabeled_mask] = 0
        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)
        self.one_hot_labels[unlabeled_mask, 0] = 0

        self.labeled_mask = ~unlabeled_mask

    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

O modelo toma como entrada a matriz de adjacência do gráfico, bem como os rótulos dos nós. Os rótulos estão na forma de um vetor de um número inteiro, indicando o número da classe de cada nó com -1 na posição de nós não rotulados.

O algoritmo de propagação de rótulo é apresentado abaixo.

W: matriz de adjacência do gráfico Calcular a matriz de graus diagonal D por DEuEujWEuj Inicializar Y^(0 0)(y1 1,,yeu,0 0,0 0,,0 0) Iterar  1 Y^(t+1 1)D-1 1WY^(t) 2) Y^eu(t+1 1)Yeu até convergência para Y^() Ponto de etiqueta xEu pelo sinal de y^Eu()

De Xiaojin Zhu e Zoubin Ghahramani. Aprendendo com dados rotulados e não rotulados com propagação de rótulo. Relatório Técnico CMU-CALD-02-107, Carnegie Mellon University, 2002

Temos a seguinte implementação.

class LabelPropagation(BaseLabelPropagation):
    def __init__(self, adj_matrix):
        super().__init__(adj_matrix)

    @staticmethod
    def _normalize(adj_matrix):
        """Computes D^-1 * W"""
        degs = adj_matrix.sum(dim=1)
        degs[degs == 0] = 1  # avoid division by 0 error
        return adj_matrix / degs[:, None]

    def _propagate(self):
        self.predictions = torch.matmul(self.norm_adj_matrix, self.predictions)

        # Put back already known labels
        self.predictions[self.labeled_mask] = self.one_hot_labels[self.labeled_mask]

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

O algoritmo de propagação de rótulo é:

W: matriz de adjacência do gráfico Calcular a matriz de graus diagonal D por DEuEujWEuj Calcular o gráfico normalizado Laplaciano euD-1 1/2WD-1 1/2 Inicializar Y^(0 0)(y1 1,,yeu,0 0,0 0,,0 0) Escolha um parâmetro α[0 0,1 1) Iterar Y^(t+1 1)αeuY^(t)+(1 1-α)Y^(0 0) até convergência para Y^() Ponto de etiqueta xEu pelo sinal de y^Eu()

De Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston e Bernhard Schoelkopf. Aprendendo com consistência local e global (2004)

A implementação é, portanto, a seguinte.

class LabelSpreading(BaseLabelPropagation):
    def __init__(self, adj_matrix):
        super().__init__(adj_matrix)
        self.alpha = None

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

    def _propagate(self):
        self.predictions = (
            self.alpha * torch.matmul(self.norm_adj_matrix, 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)

Vamos agora testar nossos modelos de propagação em dados sintéticos. Para fazer isso, escolhemos usar um gráfico de homem das cavernas .

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)
adj_matrix = nx.adjacency_matrix(caveman_graph).toarray()

# 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
adj_matrix_t = torch.FloatTensor(adj_matrix)
labels_t = torch.LongTensor(labels)

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

# Learn with Label Spreading
label_spreading = LabelSpreading(adj_matrix_t)
label_spreading.fit(labels_t, alpha=0.8)
label_spreading_output_labels = label_spreading.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()]
lspread_labels_colors = [color_map[l] for l in label_spreading_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")
ax3.title.set_text("Label Spreading")

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)
nx.draw(caveman_graph, ax=ax3, pos=pos, node_color=lspread_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()

Os modelos implementados funcionam corretamente e permitem detectar as comunidades no gráfico.

Implementações de propagação e espalhamento de etiquetas testadas em um gráfico de homens das cavernas

Nota: Os métodos de propagação apresentados devem ser usados ​​em gráficos não direcionados.

O código está disponível como um bloco de anotações Jupyter interativo aqui .

Encadernador

Thibaud M
fonte