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:
- 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, Universidade Carnegie Mellon, 2002 http://pages.cs.wisc.edu/~jerryzhu/pub/CMU-CALD-02-107.pdf
- Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston e Bernhard Schoelkopf. Aprendendo com consistência local e global (2004) http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.3219
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!
fonte
Respostas:
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.
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.
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.
O algoritmo de propagação de rótulo é:
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.
Vamos agora testar nossos modelos de propagação em dados sintéticos. Para fazer isso, escolhemos usar um gráfico de homem das cavernas .
Os modelos implementados funcionam corretamente e permitem detectar as comunidades no gráfico.
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 .
fonte