# Linear algebra¶

Tools of linear algebra.

## Polynomes¶

class sknetwork.linalg.Polynome(*args, **kwargs)[source]

Polynome of an adjacency matrix as a linear operator

$$P(A) = \alpha_k A^k + ... + \alpha_1 A + \alpha_0$$.

Parameters

• coeffs (np.ndarray) – Coefficients of the polynome by increasing order of power.

Examples

>>> from scipy import sparse
>>> from sknetwork.linalg import Polynome
>>> x = np.ones(2)
>>> polynome.dot(x)
array([3., 3.])
>>> polynome.T.dot(x)
array([3., 3.])


Notes

The polynome is evaluated using the Ruffini-Horner method.

property H

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

property T

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

adjoint()

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

dot(x)

Matrix-matrix or matrix-vector multiplication.

Parameters

x (array_like) – 1-d or 2-d array, representing a vector or matrix.

Returns

Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.

Return type

array

matmat(X)

Matrix-matrix multiplication.

Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.

Parameters

X ({matrix, ndarray}) – An array with shape (N,K).

Returns

Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.

Return type

{matrix, ndarray}

Notes

This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.

matvec(x)

Matrix-vector multiplication.

Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (N,) or (N,1).

Returns

y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.

rmatmat(X)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.

Parameters

X ({matrix, ndarray}) – A matrix or 2D array.

Returns

Y – A matrix or 2D array depending on the type of the input.

Return type

{matrix, ndarray}

Notes

This rmatmat wraps the user-specified rmatmat routine.

rmatvec(x)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (M,) or (M,1).

Returns

y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.

transpose()

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

## Sparse + Low Rank¶

class sknetwork.linalg.SparseLR(*args, **kwargs)[source]

Class for matrices with “sparse + low rank” structure. Example:

$$A + xy^T$$

Parameters
• sparse_mat (scipy.spmatrix) – Sparse component. Is converted to csr format automatically.

• low_rank_tuples (list) – Single tuple of arrays of list of tuples, representing the low rank components [(x1, y1), (x2, y2),…]. Each low rank component is of the form $$xy^T$$.

Examples

>>> from scipy import sparse
>>> from sknetwork.linalg import SparseLR
>>> slr = SparseLR(adjacency, (np.ones(2), np.ones(2)))
>>> x = np.ones(2)
>>> slr.dot(x)
array([3., 3.])
>>> slr.sum(axis=0)
array([3., 3.])
>>> slr.sum(axis=1)
array([3., 3.])
>>> slr.sum()
6.0


References

De Lara (2019). The Sparse + Low Rank trick for Matrix Factorization-Based Graph Algorithms. Proceedings of the 15th International Workshop on Mining and Learning with Graphs (MLG).

property H

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

property T

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

adjoint()

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

astype(dtype: Union[str, numpy.dtype])[source]

Change dtype of the object.

dot(x)

Matrix-matrix or matrix-vector multiplication.

Parameters

x (array_like) – 1-d or 2-d array, representing a vector or matrix.

Returns

Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.

Return type

array

left_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)[source]

Left dot product with a sparse matrix.

matmat(X)

Matrix-matrix multiplication.

Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.

Parameters

X ({matrix, ndarray}) – An array with shape (N,K).

Returns

Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.

Return type

{matrix, ndarray}

Notes

This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.

matvec(x)

Matrix-vector multiplication.

Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (N,) or (N,1).

Returns

y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.

right_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)[source]

Right dot product with a sparse matrix.

rmatmat(X)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.

Parameters

X ({matrix, ndarray}) – A matrix or 2D array.

Returns

Y – A matrix or 2D array depending on the type of the input.

Return type

{matrix, ndarray}

Notes

This rmatmat wraps the user-specified rmatmat routine.

rmatvec(x)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (M,) or (M,1).

Returns

y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.

sum(axis=None)[source]

Row-wise, column-wise or total sum of operator’s coefficients.

Parameters

axis – If 0, return column-wise sum. If 1, return row-wise sum. Otherwise, return total sum.

transpose()

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

## Operators¶

class sknetwork.linalg.RegularizedAdjacency(*args, **kwargs)[source]

Regularized adjacency matrix as a Scipy LinearOperator.

The regularized adjacency is formally defined as $$A_{\alpha} = A + \alpha 11^T$$, or $$A_{\alpha} = A + \alpha d^{+}(d^{-})^T$$ where $$\alpha$$ is the regularization parameter.

Parameters

• regularization (float) – Constant implicitly added to all entries of the adjacency matrix.

• degree_mode (bool) – If True, the regularization parameter for entry (i, j) is scaled by out-degree of node i and in-degree of node j. If False, the regularization parameter is applied to all entries.

Examples

>>> from sknetwork.data import star_wars
array([3.6, 1.8, 5.4, 3.6])

property H

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

property T

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

adjoint()

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

astype(dtype: Union[str, numpy.dtype])

Change dtype of the object.

dot(x)

Matrix-matrix or matrix-vector multiplication.

Parameters

x (array_like) – 1-d or 2-d array, representing a vector or matrix.

Returns

Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.

Return type

array

left_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)

Left dot product with a sparse matrix.

matmat(X)

Matrix-matrix multiplication.

Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.

Parameters

X ({matrix, ndarray}) – An array with shape (N,K).

Returns

Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.

Return type

{matrix, ndarray}

Notes

This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.

matvec(x)

Matrix-vector multiplication.

Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (N,) or (N,1).

Returns

y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.

right_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)

Right dot product with a sparse matrix.

rmatmat(X)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.

Parameters

X ({matrix, ndarray}) – A matrix or 2D array.

Returns

Y – A matrix or 2D array depending on the type of the input.

Return type

{matrix, ndarray}

Notes

This rmatmat wraps the user-specified rmatmat routine.

rmatvec(x)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (M,) or (M,1).

Returns

y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.

sum(axis=None)

Row-wise, column-wise or total sum of operator’s coefficients.

Parameters

axis – If 0, return column-wise sum. If 1, return row-wise sum. Otherwise, return total sum.

transpose()

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

class sknetwork.linalg.LaplacianOperator(*args, **kwargs)[source]

Regularized Laplacian matrix as a Scipy LinearOperator.

The Laplacian operator is then defined as $$L = D - A$$.

Parameters

• regularization (float) – Constant implicitly added to all entries of the adjacency matrix.

Examples

>>> from sknetwork.data import house
array([0., 0., 0., 0., 0.])

property H

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

property T

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

adjoint()

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

astype(dtype: Union[str, numpy.dtype])[source]

Change dtype of the object.

dot(x)

Matrix-matrix or matrix-vector multiplication.

Parameters

x (array_like) – 1-d or 2-d array, representing a vector or matrix.

Returns

Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.

Return type

array

matmat(X)

Matrix-matrix multiplication.

Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.

Parameters

X ({matrix, ndarray}) – An array with shape (N,K).

Returns

Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.

Return type

{matrix, ndarray}

Notes

This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.

matvec(x)

Matrix-vector multiplication.

Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (N,) or (N,1).

Returns

y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.

rmatmat(X)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.

Parameters

X ({matrix, ndarray}) – A matrix or 2D array.

Returns

Y – A matrix or 2D array depending on the type of the input.

Return type

{matrix, ndarray}

Notes

This rmatmat wraps the user-specified rmatmat routine.

rmatvec(x)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (M,) or (M,1).

Returns

y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.

transpose()

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

class sknetwork.linalg.NormalizedAdjacencyOperator(*args, **kwargs)[source]

Regularized normalized adjacency matrix as a Scipy LinearOperator.

The normalized adjacency operator is then defined as $$\bar{A} = D^{-1/2}AD^{-1/2}$$.

Parameters

• regularization (float) – Constant implicitly added to all entries of the adjacency matrix.

Examples

>>> from sknetwork.data import house
True

property H

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

property T

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

adjoint()

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

astype(dtype: Union[str, numpy.dtype])[source]

Change dtype of the object.

dot(x)

Matrix-matrix or matrix-vector multiplication.

Parameters

x (array_like) – 1-d or 2-d array, representing a vector or matrix.

Returns

Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.

Return type

array

matmat(X)

Matrix-matrix multiplication.

Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.

Parameters

X ({matrix, ndarray}) – An array with shape (N,K).

Returns

Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.

Return type

{matrix, ndarray}

Notes

This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.

matvec(x)

Matrix-vector multiplication.

Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (N,) or (N,1).

Returns

y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.

rmatmat(X)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.

Parameters

X ({matrix, ndarray}) – A matrix or 2D array.

Returns

Y – A matrix or 2D array depending on the type of the input.

Return type

{matrix, ndarray}

Notes

This rmatmat wraps the user-specified rmatmat routine.

rmatvec(x)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (M,) or (M,1).

Returns

y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.

transpose()

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

class sknetwork.linalg.CoNeighborOperator(*args, **kwargs)[source]

• Graphs

• Digraphs

• Bigraphs

$$\tilde{A} = AF^{-1}A^T$$, or $$\tilde{B} = BF^{-1}B^T$$.

where F is a weight matrix.

Parameters

• normalized – If True, F is the diagonal in-degree matrix $$F = \text{diag}(A^T1)$$. Otherwise, F is the identity matrix.

Examples

>>> from sknetwork.data import star_wars
>>> np.allclose(d_out, coneigh.dot(np.ones(4)))
True

property H

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

property T

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

adjoint()

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

astype(dtype: Union[str, numpy.dtype])[source]

Change dtype of the object.

dot(x)

Matrix-matrix or matrix-vector multiplication.

Parameters

x (array_like) – 1-d or 2-d array, representing a vector or matrix.

Returns

Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.

Return type

array

left_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)[source]

Left dot product with a sparse matrix

matmat(X)

Matrix-matrix multiplication.

Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.

Parameters

X ({matrix, ndarray}) – An array with shape (N,K).

Returns

Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.

Return type

{matrix, ndarray}

Notes

This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.

matvec(x)

Matrix-vector multiplication.

Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (N,) or (N,1).

Returns

y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.

right_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)[source]

Right dot product with a sparse matrix

rmatmat(X)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.

Parameters

X ({matrix, ndarray}) – A matrix or 2D array.

Returns

Y – A matrix or 2D array depending on the type of the input.

Return type

{matrix, ndarray}

Notes

This rmatmat wraps the user-specified rmatmat routine.

rmatvec(x)

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (M,) or (M,1).

Returns

y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.

transpose()

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

## Solvers¶

class sknetwork.linalg.LanczosEig(which='LM', maxiter: Optional[int] = None, tol: float = 0.0)[source]

Eigenvalue solver using Lanczos method.

Parameters
• which (str) –

Which eigenvectors and eigenvalues to find:

• 'LM' : Largest (in magnitude) eigenvalues.

• 'SM' : Smallest (in magnitude) eigenvalues.

• maxiter (int) – Maximum number of Arnoldi update iterations allowed. Default: n*10.

• tol (float) – Relative accuracy for eigenvalues (stopping criterion). The default value of 0 implies machine precision.

Variables
• eigenvectors_ (np.ndarray) – Two-dimensional array, each column is an eigenvector of the input.

• eigenvalues_ (np.ndarray) – Eigenvalues associated to each eigenvector.

scipy.sparse.linalg.eigsh

fit(matrix: Union[scipy.sparse.csr.csr_matrix, scipy.sparse.linalg.interface.LinearOperator], n_components: int, v0: Optional[numpy.ndarray] = None)[source]

Perform eigenvalue decomposition on symmetric input matrix.

Parameters
• matrix – Matrix to decompose.

• n_components (int) – Number of eigenvectors to compute

• v0 (np.ndarray) – Starting vector for iteration. Default: random.

Returns

self

Return type

EigSolver

class sknetwork.linalg.HalkoEig(which='LM', n_oversamples: int = 10, n_iter='auto', power_iteration_normalizer: Optional[str] = 'auto', random_state=None, one_pass: bool = False)[source]

Eigenvalue solver using Halko’s randomized method.

Parameters
• which (str) –

Which eigenvectors and eigenvalues to find:

• 'LM' : Largest (in magnitude) eigenvalues.

• 'SM' : Smallest (in magnitude) eigenvalues.

• n_oversamples (int (default=10)) – Additional number of random vectors to sample the range of matrix so as to ensure proper conditioning. The total number of random vectors used to find the range of matrix is n_components + n_oversamples. Smaller number can improve speed but can negatively impact the quality of approximation of singular vectors and singular values.

• n_iter (int or 'auto' (default is 'auto')) – See randomized_range_finder()

• power_iteration_normalizer ('auto' (default), 'QR', 'LU', None) – See randomized_range_finder()

• random_state (int, RandomState instance or None, optional (default=None)) – See randomized_range_finder()

• one_pass (bool (default=False)) – whether to use algorithm 5.6 instead of 5.3. 5.6 requires less access to the original matrix, while 5.3 is more accurate.

fit(matrix: Union[scipy.sparse.csr.csr_matrix, scipy.sparse.linalg.interface.LinearOperator, sknetwork.linalg.sparse_lowrank.SparseLR], n_components: int)[source]

Perform eigenvalue decomposition on input matrix.

Parameters
• matrix – Matrix to decompose.

• n_components (int) – Number of eigenvectors to compute

Returns

self

Return type

EigSolver

class sknetwork.linalg.LanczosSVD(maxiter: Optional[int] = None, tol: float = 0.0)[source]

SVD solver using Lanczos method on $$AA^T$$ or $$A^TA$$.

Parameters
• maxiter (int) – Maximum number of Arnoldi update iterations allowed. Default: n*10.

• tol (float) – Relative accuracy for eigenvalues (stopping criterion). The default value of 0 implies machine precision.

Variables
• singular_vectors_left_ (np.ndarray) – Two-dimensional array, each column is a left singular vector of the input.

• singular_vectors_right_ (np.ndarray) – Two-dimensional array, each column is a right singular vector of the input.

• singular_values_ (np.ndarray) – Singular values.

scipy.sparse.linalg.svds

fit(matrix: Union[scipy.sparse.csr.csr_matrix, scipy.sparse.linalg.interface.LinearOperator], n_components: int, v0: Optional[numpy.ndarray] = None)[source]

Perform singular value decomposition on input matrix.

Parameters
• matrix – Matrix to decompose.

• n_components (int) – Number of singular values to compute

• v0 (np.ndarray) – Starting vector for iteration. Default: random.

Returns

self

Return type

SVDSolver

class sknetwork.linalg.HalkoSVD(n_oversamples: int = 10, n_iter='auto', transpose='auto', power_iteration_normalizer: Optional[str] = 'auto', flip_sign: bool = True, random_state=None)[source]

SVD solver using Halko’s randomized method.

Parameters
• n_oversamples (int (default=10)) – Additional number of random vectors to sample the range of M so as to ensure proper conditioning. The total number of random vectors used to find the range of M is n_components + n_oversamples. Smaller number can improve speed but can negatively impact the quality of approximation of singular vectors and singular values.

• n_iter (int or 'auto' (default is 'auto')) – See randomized_range_finder()

• power_iteration_normalizer ('auto' (default), 'QR', 'LU', None) – See randomized_range_finder()

• transpose (True, False or 'auto' (default)) – Whether the algorithm should be applied to matrix.T instead of matrix. The result should approximately be the same. The ‘auto’ mode will trigger the transposition if matrix.shape[1] > matrix.shape[0] since this implementation of randomized SVD tends to be a little faster in that case.

• flip_sign (boolean, (default=True)) – The output of a singular value decomposition is only unique up to a permutation of the signs of the singular vectors. If flip_sign is set to True, the sign ambiguity is resolved by making the largest loadings for each component in the left singular vectors positive.

• random_state (int, RandomState instance or None, optional (default=None)) – See randomized_range_finder()

Variables
• singular_vectors_left_ (np.ndarray) – Two-dimensional array, each column is a left singular vector of the input.

• singular_vectors_right_ (np.ndarray) – Two-dimensional array, each column is a right singular vector of the input.

• singular_values_ (np.ndarray) – Singular values.

fit(matrix: Union[scipy.sparse.csr.csr_matrix, scipy.sparse.linalg.interface.LinearOperator, sknetwork.linalg.sparse_lowrank.SparseLR], n_components: int)[source]

Perform singular value decomposition on input matrix.

Parameters
• matrix – Matrix to decompose.

• n_components (int) – Number of singular values to compute

Returns

self

Return type

SVDSolver

sknetwork.linalg.ppr_solver.get_pagerank(adjacency: Union[scipy.sparse.csr.csr_matrix, scipy.sparse.linalg.interface.LinearOperator], seeds: numpy.ndarray, damping_factor: float, n_iter: int, tol: float = 1e-06, solver: str = 'piteration')numpy.ndarray[source]

Solve the Pagerank problem. Formally,

$$x = \alpha Px + (1-\alpha)y$$,

where $$P = (D^{-1}A)^T$$ is the transition matrix and $$y$$ is the personalization probability vector.

Parameters

• seeds (np.ndarray) – Personalization array. Must be a valid probability vector.

• damping_factor (float) – Probability to continue the random walk.

• n_iter (int) – Number of iterations for some of the solvers such as 'piteration' or 'diteration'.

• tol (float) – Tolerance for the convergence of some solvers such as 'bicgstab' or 'lanczos' or 'push'.

• solver (str) – Which solver to use: 'piteration', 'diteration', 'bicgstab', 'lanczos', ̀'RH', 'push'.

Returns

pagerank – Probability vector.

Return type

np.ndarray

Examples

>>> from sknetwork.data import house
>>> seeds = np.array([1, 0, 0, 0, 0])
>>> scores = get_pagerank(adjacency, seeds, damping_factor=0.85, n_iter=10)
>>> np.round(scores, 2)
array([0.29, 0.24, 0.12, 0.12, 0.24])


References

## Randomized methods¶

sknetwork.linalg.randomized_methods.randomized_range_finder(matrix: numpy.ndarray, size: int, n_iter: int, power_iteration_normalizer='auto', random_state=None, return_all: bool = False)Union[numpy.ndarray, Tuple[numpy.ndarray, numpy.ndarray, numpy.ndarray]][source]

Compute an orthonormal matrix $$Q$$, whose range approximates the range of the input matrix.

$$A \approx QQ^*A$$.

Parameters
• matrix – Input matrix

• size – Size of the return array

• n_iter – Number of power iterations. It can be used to deal with very noisy problems. When ‘auto’, it is set to 4, unless size is small (< .1 * min(matrix.shape)) in which case n_iter is set to 7. This improves precision with few components.

• power_iteration_normalizer ('auto' (default), 'QR', 'LU', None) – Whether the power iterations are normalized with step-by-step QR factorization (the slowest but most accurate), None (the fastest but numerically unstable when n_iter is large, e.g. typically 5 or larger), or 'LU' factorization (numerically stable but can lose slightly in accuracy). The 'auto' mode applies no normalization if n_iter <= 2 and switches to 'LU' otherwise.

• random_state (int, RandomState instance or None, optional (default= None)) – The seed of the pseudo random number generator to use when shuffling the data. If int, random_state is the seed used by the random number generator; If RandomState instance, random_state is the random number generator; If None, the random number generator is the RandomState instance used by np.random.

• return_all (if True, returns (range_matrix, random_matrix, random_proj)) – else returns range_matrix.

Returns

• range_matrix (np.ndarray) – matrix (size x size) projection matrix, the range of which approximates well the range of the input matrix.

• random_matrix (np.ndarray, optional) – projection matrix

• projected_matrix (np.ndarray, optional) – product between the data and the projection matrix

Notes

Follows Algorithm 4.3 of Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions Halko, et al., 2009 (arXiv:909)

sknetwork.linalg.randomized_svd(matrix, n_components: int, n_oversamples: int = 10, n_iter='auto', transpose='auto', power_iteration_normalizer: Optional[str] = 'auto', flip_sign: bool = True, random_state=None)[source]

Truncated randomized SVD

Parameters
• matrix (ndarray or sparse matrix) – Matrix to decompose

• n_components (int) – Number of singular values and vectors to extract.

• n_oversamples (int (default=10)) – Additional number of random vectors to sample the range of M so as to ensure proper conditioning. The total number of random vectors used to find the range of M is n_components + n_oversamples. Smaller number can improve speed but can negatively impact the quality of approximation of singular vectors and singular values.

• n_iter (int or 'auto' (default is 'auto')) – See randomized_range_finder()

• power_iteration_normalizer ('auto' (default), 'QR', 'LU', None) – See randomized_range_finder()

• transpose (True, False or 'auto' (default)) – Whether the algorithm should be applied to matrix.T instead of matrix. The result should approximately be the same. The ‘auto’ mode will trigger the transposition if matrix.shape[1] > matrix.shape[0] since this implementation of randomized SVD tends to be a little faster in that case.

• flip_sign (boolean, (default=True)) – The output of a singular value decomposition is only unique up to a permutation of the signs of the singular vectors. If flip_sign is set to True, the sign ambiguity is resolved by making the largest loadings for each component in the left singular vectors positive.

• random_state (int, RandomState instance or None, optional (default=None)) – See randomized_range_finder()

Returns

• left_singular_vectors (np.ndarray)

• singular_values (np.ndarray)

• right_singular_vectors (np.ndarray)

Notes

This algorithm finds a (usually very good) approximate truncated singular value decomposition using randomization to speed up the computations. It is particularly fast on large matrices on which you wish to extract only a small number of components. In order to obtain further speed up, n_iter can be set <=2 (at the cost of loss of precision).

References

• Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions Halko, et al., 2009 http://arxiv.org/abs/arXiv:0909.4061 (algorithm 5.1)

• A randomized algorithm for the decomposition of matrices Per-Gunnar Martinsson, Vladimir Rokhlin and Mark Tygert

• An implementation of a randomized algorithm for principal component analysis A. Szlam et al. 2014

sknetwork.linalg.randomized_eig(matrix, n_components: int, which='LM', n_oversamples: int = 10, n_iter='auto', power_iteration_normalizer: Optional[str] = 'auto', random_state=None, one_pass: bool = False)[source]

Truncated randomized eigenvalue decomposition.

Parameters
• matrix (ndarray or sparse matrix) – Matrix to decompose

• n_components (int) – Number of singular values and vectors to extract.

• which (str) – which eigenvalues to compute. 'LM' for Largest Magnitude and 'SM' for Smallest Magnitude. Any other entry will result in Largest Magnitude.

• n_oversamples (int (default=10)) – Additional number of random vectors to sample the range of matrix so as to ensure proper conditioning. The total number of random vectors used to find the range of matrix is n_components + n_oversamples. Smaller number can improve speed but can negatively impact the quality of approximation of singular vectors and singular values.

• n_iter (int or 'auto' (default is 'auto')) – See randomized_range_finder()

• power_iteration_normalizer ('auto' (default), 'QR', 'LU', None) – See randomized_range_finder()

• random_state (int, RandomState instance or None, optional (default=None)) – See randomized_range_finder()

• one_pass (bool (default=False)) – whether to use algorithm 5.6 instead of 5.3. 5.6 requires less access to the original matrix, while 5.3 is more accurate.

Returns

• eigenvalues (np.ndarray)

• eigenvectors (np.ndarray)

References

Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions Halko, et al., 2009 http://arxiv.org/abs/arXiv:0909.4061

## Miscellaneous¶

sknetwork.linalg.diag_pinv(weights: numpy.ndarray)scipy.sparse.csr.csr_matrix[source]

Compute $$W^+ = \text{diag}(w)^+$$, the pseudo inverse of the diagonal matrix with diagonal the weights $$w$$.

Parameters

weights – The weights to invert.

Returns

$$W^+$$

Return type

sparse.csr_matrix

sknetwork.linalg.normalize(matrix: Union[scipy.sparse.csr.csr_matrix, numpy.ndarray, scipy.sparse.linalg.interface.LinearOperator], p=1)[source]

Normalize rows of a matrix. Null rows remain null.

Parameters
• matrix – Input matrix.

• p – Order of the norm

Returns

normalized matrix

Return type

same as input