Linear algebra

Tools of linear algebra.

Polynomials

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
  • adjacency – Adjacency matrix of the graph

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

Examples

>>> from scipy import sparse
>>> from sknetwork.linalg import Polynome
>>> adjacency = sparse.eye(2, format='csr')
>>> polynome = Polynome(adjacency, np.arange(3))
>>> 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

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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()

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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)

Adjoint matrix-matrix multiplication.

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)

Adjoint matrix-vector multiplication.

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
>>> adjacency = sparse.eye(2, format='csr')
>>> 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

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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()

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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)

Adjoint matrix-matrix multiplication.

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)

Adjoint matrix-vector multiplication.

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.Regularizer(*args, **kwargs)[source]

Regularized matrix as a Scipy LinearOperator.

Defined by \(A + \alpha \frac{11^T}n\) where \(A\) is the input matrix and \(\alpha\) the regularization factor.

Parameters
  • input_matrix – Input matrix.

  • regularization (float) – Regularization factor. Default value = 1.

Examples

>>> from sknetwork.data import house
>>> adjacency = house()
>>> regularizer = Regularizer(adjacency)
>>> regularizer.dot(np.ones(5))
array([3., 4., 3., 3., 4.])
property H

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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()

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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)

Adjoint matrix-matrix multiplication.

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)

Adjoint matrix-vector multiplication.

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.Normalizer(*args, **kwargs)[source]

Normalized matrix as a Scipy LinearOperator.

Defined by \(D^{-1}A\) where \(A\) is the regularized adjacency matrix and \(D\) the corresponding diagonal matrix of degrees (sums over rows).

Parameters
  • adjacencyAdjacency matrix of the graph.

  • regularization (float) – Regularization factor. Default value = 0.

Examples

>>> from sknetwork.data import house
>>> adjacency = house()
>>> normalizer = Normalizer(adjacency)
>>> normalizer.dot(np.ones(5))
array([1., 1., 1., 1., 1.])
property H

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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()

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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)

Adjoint matrix-matrix multiplication.

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)

Adjoint matrix-vector multiplication.

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.Laplacian(*args, **kwargs)[source]

Laplacian matrix as a Scipy LinearOperator.

Defined by \(L = D - A\) where \(A\) is the regularized adjacency matrix and \(D\) the corresponding diagonal matrix of degrees.

If normalized, defined by \(L = I - D^{-1/2}AD^{-1/2}\).

Parameters
  • adjacencyAdjacency matrix of the graph.

  • regularization (float) – Regularization factor. Default value = 0.

  • normalized_laplacian (bool) – If True, use normalized Laplacian. Default value = False.

Examples

>>> from sknetwork.data import house
>>> adjacency = house()
>>> laplacian = Laplacian(adjacency)
>>> laplacian.dot(np.ones(5))
array([0., 0., 0., 0., 0.])
property H

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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()

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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)

Adjoint matrix-matrix multiplication.

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)

Adjoint matrix-vector multiplication.

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.CoNeighbor(*args, **kwargs)[source]

Co-neighborhood adjacency as a LinearOperator.

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

where F is a weight matrix.

Parameters
  • adjacency – Adjacency or biadjacency of the input graph.

  • 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
>>> biadjacency = star_wars(metadata=False)
>>> d_out = biadjacency.dot(np.ones(3))
>>> coneighbor = CoNeighbor(biadjacency)
>>> np.allclose(d_out, coneighbor.dot(np.ones(4)))
True
property H

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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()

Hermitian 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.

Can be abbreviated self.H instead of self.adjoint().

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)

Adjoint matrix-matrix multiplication.

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)

Adjoint matrix-vector multiplication.

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', n_iter: 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 modulus) eigenvalues.

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

    • 'LA' : Largest (algebraic) eigenvalues.

    • 'SA' : Smallest (algebraic) eigenvalues.

  • n_iter (int) – Maximum number of Arnoldi update iterations allowed. Default = 10 * nb of rows.

  • tol (float) – Relative accuracy for eigenvalues (stopping criterion). Default = 0 (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.

See also

scipy.sparse.linalg.eigsh

fit(matrix: Union[scipy.sparse._csr.csr_matrix, scipy.sparse.linalg._interface.LinearOperator], n_components: int = 2)[source]

Perform spectral decomposition on symmetric input matrix.

Parameters
  • matrix (sparse.csr_matrix or linear operator) – Matrix to decompose.

  • n_components (int) – Number of eigenvectors to compute

Returns

self

Return type

EigSolver

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

SVD solver using Lanczos method on \(AA^T\) or \(A^TA\).

Parameters
  • n_iter (int) – Maximum number of Arnoldi update iterations allowed. Default = 10 * nb or rows or columns.

  • tol (float) – Relative accuracy for eigenvalues (stopping criterion). Default = 0 (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.

See also

scipy.sparse.linalg.svds

fit(matrix: Union[scipy.sparse._csr.csr_matrix, scipy.sparse.linalg._interface.LinearOperator], n_components: int, init_vector: 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

  • init_vector (np.ndarray) – Starting vector for iteration. Default = random.

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
  • adjacency (sparse.csr_matrix) – Adjacency matrix of the graph.

  • 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
>>> adjacency = 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

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