Source code for karateclub.node_embedding.neighbourhood.randne

import numpy as np
import networkx as nx
from scipy import sparse
from karateclub.estimator import Estimator

[docs]class RandNE(Estimator): r"""An implementation of `"RandNE" <https://zw-zhang.github.io/files/2018_ICDM_RandNE.pdf>`_ from the ICDM '18 paper "Billion-scale Network Embedding with Iterative Random Projection". The procedure uses normalized adjacency matrix based smoothing on an orthogonalized random normally generate base node embedding matrix. Args: dimensions (int): Number of embedding dimension. Default is 128. alphas (list): Smoothing weights for adjacency matrix powers. Default is [0.5, 0.5]. seed (int): Random seed. Default is 42. """ def __init__( self, dimensions: int = 128, alphas: list = [0.5, 0.5], seed: int = 42 ): self.dimensions = dimensions self.alphas = alphas self.seed = seed def _create_D_inverse(self, graph): """ Creating a sparse inverse degree matrix. Arg types: * **graph** *(NetworkX graph)* - The graph to be embedded. Return types: * **D_inverse** *(Scipy array)* - Diagonal inverse degree matrix. """ index = np.arange(graph.number_of_nodes()) values = np.array( [1.0 / graph.degree[node] for node in range(graph.number_of_nodes())] ) shape = (graph.number_of_nodes(), graph.number_of_nodes()) D_inverse = sparse.coo_matrix((values, (index, index)), shape=shape) return D_inverse def _create_smoothing_matrix(self, graph): """ Creating the normalized adjacency matrix. Arg types: * **graph** *(NetworkX graph)* - The graph to be embedded. Return types: * **(A_hat, A_hat, A_hat, D_inverse)** *(SciPy arrays)* - Normalized adjacency matrices. """ A = nx.adjacency_matrix(graph, nodelist=range(graph.number_of_nodes())) D_inverse = self._create_D_inverse(graph) A_hat = D_inverse.dot(A) return A_hat def _create_embedding(self, A_hat): """ Using the random orthogonal smoothing. """ sd = 1 / self.dimensions base_embedding = np.random.normal(0, sd, (A_hat.shape, self.dimensions)) base_embedding, _ = np.linalg.qr(base_embedding) embedding = np.zeros(base_embedding.shape) alpha_sum = sum(self.alphas) for alpha in self.alphas: base_embedding = A_hat.dot(base_embedding) embedding = embedding + alpha * base_embedding embedding = embedding / alpha_sum embedding = (embedding - embedding.mean(0)) / embedding.std(0) return embedding
[docs] def fit(self, graph: nx.classes.graph.Graph): """ Fitting a NetMF model. Arg types: * **graph** *(NetworkX graph)* - The graph to be embedded. """ self._set_seed() graph = self._check_graph(graph) A_hat = self._create_smoothing_matrix(graph) self._embedding = self._create_embedding(A_hat)
[docs] def get_embedding(self) -> np.array: r"""Getting the node embedding. Return types: * **embedding** *(Numpy array)* - The embedding of nodes. """ return self._embedding