# Source code for karateclub.node_embedding.neighbourhood.grarep

```import math
import numpy as np
import networkx as nx
from scipy import sparse
from sklearn.decomposition import TruncatedSVD
from karateclub.estimator import Estimator

[docs]class GraRep(Estimator):
r"""An implementation of `"GraRep" <https://dl.acm.org/citation.cfm?id=2806512>`_
from the CIKM '15 paper "GraRep: Learning Graph Representations with Global
Structural Information". The procedure uses sparse truncated SVD to learn
embeddings for the powers of the PMI matrix computed from powers of the

Args:
dimensions (int): Number of individual embedding dimensions. Default is 32.
iteration (int): Number of SVD iterations. Default is 10.
order (int): Number of PMI matrix powers. Default is 5.
seed (int): SVD random seed. Default is 42.
"""

def __init__(
self, dimensions: int = 32, iteration: int = 10, order: int = 5, seed: int = 42
):
self.dimensions = dimensions
self.iterations = iteration
self.order = order
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_base_matrix(self, graph):
"""
Creating a tuple with the normalized adjacency matrix.

Return types:
* **(A_hat, A_hat)** *(Tuple of SciPy arrays)* - Normalized adjacency matrices.
"""
D_inverse = self._create_D_inverse(graph)
A_hat = D_inverse.dot(A)
return (A_hat, A_hat)

def _create_target_matrix(self):
"""
Creating a log transformed target matrix.

Return types:
* **target_matrix** *(SciPy array)* - The PMI matrix.
"""
self._A_tilde = sparse.coo_matrix(self._A_tilde.dot(self._A_hat))
scores = np.log(self._A_tilde.data) - math.log(self._A_tilde.shape[0])
rows = self._A_tilde.row[scores < 0]
cols = self._A_tilde.col[scores < 0]
scores = scores[scores < 0]
target_matrix = sparse.coo_matrix(
(scores, (rows, cols)), shape=self._A_tilde.shape, dtype=np.float32
)

return target_matrix

def _create_single_embedding(self, target_matrix):
"""
Fitting a single SVD embedding of a PMI matrix.
"""
svd = TruncatedSVD(
n_components=self.dimensions, n_iter=self.iterations, random_state=self.seed
)
svd.fit(target_matrix)
embedding = svd.transform(target_matrix)
self._embeddings.append(embedding)

[docs]    def fit(self, graph: nx.classes.graph.Graph):
"""
Fitting a GraRep model.

Arg types:
* **graph** *(NetworkX graph)* - The graph to be embedded.
"""
self._set_seed()
graph = self._check_graph(graph)
self._A_tilde, self._A_hat = self._create_base_matrix(graph)
self._embeddings = []
target_matrix = self._create_target_matrix()
self._create_single_embedding(target_matrix)
for step in range(self.order - 1):
target_matrix = self._create_target_matrix()
self._create_single_embedding(target_matrix)

[docs]    def get_embedding(self) -> np.array:
r"""Getting the node embedding.

Return types:
* **embedding** *(Numpy array)* - The embedding of nodes.
"""
embedding = np.concatenate(self._embeddings, axis=1)
return embedding
```