topo.spectral.eigen

Module Contents

Classes

EigenDecomposition

Scikit-learn flavored class for computing eigendecompositions of sparse symmetric matrices.

Functions

eigendecompose(G[, n_components, eigensolver, ...])

Eigendecomposition of a graph matrix.

spectral_layout(graph, dim, random_state[, ...])

Given a graph compute the spectral embedding of the graph. This is

component_layout(W, n_components, component_labels, dim)

Provide a layout relating the separate connected components. This is done

multi_component_layout(graph, n_components, ...)

Attributes

EIGEN_SOLVERS

PYAMG_LOADED

topo.spectral.eigen.EIGEN_SOLVERS = ['dense', 'arpack', 'lobpcg']
topo.spectral.eigen.PYAMG_LOADED = True
topo.spectral.eigen.eigendecompose(G, n_components=8, eigensolver='arpack', largest=True, eigen_tol=0.0001, random_state=None, verbose=False)

Eigendecomposition of a graph matrix.

Parameters:

  • G (array-like or sparse matrix, shape (n_vertices, n_vertices).) –

  • n_components (int (optional, default 8).) – Number of eigenpairs to compute.

  • eigensolver (string (optional, default 'arpack').) –

    Method for computing the eigendecomposition. Can be either ‘arpack’, ‘lobpcg’, ‘amg’ or ‘dense’. * ‘dense’ :

    use standard dense matrix operations for the eigenvalue decomposition. For this method, G must be an array or matrix type. This method should be avoided for large problems.

    • ’arpack’ :

      use arnoldi iteration in shift-invert mode. For this method, M may be a dense matrix, sparse matrix, or general linear operator.

    • ’lobpcg’ :

      Locally Optimal Block Preconditioned Conjugate Gradient Method. A preconditioned eigensolver for large symmetric positive definite (SPD) generalized eigenproblems.

    • ’amg’ :

      Algebraic Multigrid solver (requires pyamg to be installed) It can be faster on very large, sparse problems, but may also lead to instabilities.

  • largest (bool (optional, default True).) – If True, compute the largest eigenpairs. If False, compute the smallest eigenpairs.

  • eigen_tol (float (optional, default 1e-4).) – Error tolerance for the eigenvalue solver. If 0, machine precision is used.

  • random_state (int or numpy.random.RandomState() (optional, default None).) – A pseudo random number generator used for the initialization of the lobpcg eigen vectors decomposition when eigen_solver == ‘amg’. By default, arpack is used.

Returns:

  • eigen_values (array, shape (n_vertices,)) – Eigenvalues of the graph matrix.

  • eigen_vectors (array, shape (n_vertices, n_vertices)) – Eigenvectors of the graph matrix.

class topo.spectral.eigen.EigenDecomposition(n_components=10, method='DM', eigensolver='arpack', eigen_tol=0.0001, drop_first=True, weight=True, laplacian_type='random_walk', anisotropy=1, t=1, random_state=None, return_evals=False, estimate_eigengap=True, enforce_min_eigs=True, verbose=False)

Bases: sklearn.base.BaseEstimator, sklearn.base.TransformerMixin

Scikit-learn flavored class for computing eigendecompositions of sparse symmetric matrices. and exploring the associated eigenvectors and eigenvalues. Takes as main input a topo.tpgraph.Kernel() object or a symmetric matrix, which can be either an adjacency/affinity matrix, a kernel, a graph laplacian, or a diffusion operator.

Parameters:

  • n_components (int (optional, default 10).) – Number of eigenpairs to be computed.

  • method (string (optional, default 'DM').) – Method for organizing the eigendecomposition. Can be either ‘top’, ‘bottom’, ‘msDM’, ‘DM’ or ‘LE’. * ‘top’ : computes the top eigenpairs of the matrix. * ‘bottom’ : computes the bottom eigenpairs of the matrix. * ‘msDM’ : computes the eigenpairs of the diffusion operator on the matrix, and multiscales them. If a Kernel() object is provided, will use the computed diffusion operator if available. * ‘DM’ : computes the eigenpairs of the diffusion operator on the matrix. If a Kernel() object is provided, will use the computed diffusion operator if available. * ‘LE’ : computes the eigenpairs of the graph laplacian on the matrix. If a Kernel() object is provided, will use the computed graph laplacian if available.

  • eigensolver (string (optional, default 'arpack').) –

    Method for computing the eigendecomposition. Can be either ‘arpack’, ‘lobpcg’, ‘amg’ or ‘dense’. * ‘dense’ :

    use standard dense matrix operations for the eigenvalue decomposition. For this method, M must be an array or matrix type. This method should be avoided for large problems.

    • ’arpack’ :

      use arnoldi iteration in shift-invert mode. For this method, M may be a dense matrix, sparse matrix, or general linear operator.

    • ’lobpcg’ :

      Locally Optimal Block Preconditioned Conjugate Gradient Method. A preconditioned eigensolver for large symmetric positive definite (SPD) generalized eigenproblems.

    • ’amg’ :

      Algebraic Multigrid solver (requires pyamg to be installed) It can be faster on very large, sparse problems, but requires setting a random seed for better reproducibility.

  • laplacian_type (string (optional, default 'normalized')) – The type of Laplacian to compute. Possible values are: ‘normalized’, ‘unnormalized’, ‘random_walk’ and ‘geometric’.

  • anisotropy (float (optional, default 0).) – The anisotropy (alpha) parameter in the diffusion maps literature for kernel reweighting.

  • eigen_tol (float (optional, default 0.0).) – Error tolerance for the eigenvalue solver. If 0, machine precision is used.

tint (optional, default 1).

Time parameter for the diffusion operator, if ‘method’ is ‘DM’. The diffusion operator will be powered by t. Ignored for other methods.

return_evalsbool (optional, default False).

Whether to return the eigenvalues along with the eigenvectors.

random_stateint or numpy.random.RandomState() (optional, default None).

A pseudo random number generator used for the initialization of the lobpcg eigen vectors decomposition when eigen_solver == ‘amg’. By default, arpack is used.

__repr__()

Return repr(self).

fit(X)

Computes the eigendecomposition of the kernel matrix X following the organization set by ‘method’.

Parameters:

X (array-like, shape (n_samples, n_samples)) – Matrix to be decomposed. Should generally be an adjacency, affinity/kernel/similarity, Laplacian matrix or a diffusion-type operator.

Returns:

self (object) – Returns the instance itself, with eigenvectors stored at EigenDecomposition.eigenvectors and eigenvalues stored at EigenDecomposition.eigenvalues. If method is ‘DM’, stores Diffusion Maps at EigenDecomposition.embedding. If ‘method’ is ‘DM’ or ‘LE’, the diffusion operator or graph laplacian is stored at EigenDecomposition.diffusion_operator or EigenDecomposition.graph_laplacian, respectively.

rescale(use_eigs=50)

If using multiscale diffusion maps, this rescales the mapping to a new number of eigenvectors.

results(return_evals=None)

Returns the results of the decomposition.

Returns:

  • evecs (array-like, shape (n_samples, n_components)) – Eigenvectors of the matrix. If using ‘msDM’, returns the multiscaled eigenvectors.

  • evals (array-like, shape (n_components, )) – Eigenvalues of the matrix. Returned only if return_evals is True.

transform(X=None)

Here for scikit-learn compability.

Parameters:

X (array-like, shape (n_samples, n_features)) – Data matrix. Here for scikit-learn compability.

Returns:

  • evecs (array-like, shape (n_samples, n_components)) – Eigenvectors of the matrix. If using ‘msDM’, returns the multiscaled eigenvectors.

  • evals (array-like, shape (n_components, )) – Eigenvalues of the matrix. Returned only if return_evals is True.

fit_transform(X)

Here for scikit-learn compability. Returns the eigenvectors learned during fitting. :param X: Kernel matrix or Kernel() object. Ignored, here for consistency with scikit-learn API. :type X: array-like, shape (n_samples, n_samples).

Returns:

  • evecs (array-like, shape (n_samples, n_components)) – Eigenvectors of the matrix.

  • evals (array-like, shape (n_components, )) – Eigenvalues of the matrix. Returned only if return_evals is True.

spectral_layout(X, laplacian_type='normalized', return_evals=False)

Given a graph compute the spectral embedding of the graph. This function calls specialized routines if the graph has several connected components.

Parameters:

  • X (sparse matrix) – The (weighted) adjacency matrix of the graph as a sparse matrix.

  • laplacian_type (string (optional, default 'normalized').) – The type of laplacian to use. Can be ‘unnormalized’, ‘symmetric’ or ‘random_walk’.

  • return_evals (bool) – Whether to also return the eigenvalues of the laplacian.

Returns:

  • embedding (array of shape (n_vertices, dim)) – The spectral embedding of the graph.

  • evals (array of shape (dim,)) – The eigenvalues of the laplacian of the graph. Only returned if return_evals is True.

plot_eigenspectrum()

Plots the eigenspectrum.

topo.spectral.eigen.spectral_layout(graph, dim, random_state, laplacian_type='normalized', eigen_tol=0.001, return_evals=False)

Given a graph compute the spectral embedding of the graph. This is simply the eigenvectors of the laplacian of the graph. Here we use the normalized laplacian. :param graph: The (weighted) adjacency matrix of the graph as a sparse matrix. :type graph: sparse matrix :param dim: The dimension of the space into which to embed. :type dim: int :param random_state: A state capable being used as a numpy random state. :type random_state: numpy RandomState or equivalent

Returns:

embedding (array of shape (n_vertices, dim)) – The spectral embedding of the graph.

topo.spectral.eigen.component_layout(W, n_components, component_labels, dim, laplacian_type='normalized', eigen_tol=0.001, return_evals=False)

Provide a layout relating the separate connected components. This is done by taking the centroid of each component and then performing a spectral embedding of the centroids. :param W: Affinity or adjacency matrix. :type W: numpy.ndarray, pandas.DataFrame or scipy.sparse.csr_matrix. :param n_components: The number of distinct components to be layed out. :type n_components: int :param component_labels: For each vertex in the graph the label of the component to

which the vertex belongs.

Parameters:

  • dim (int) – The chosen embedding dimension.

  • laplacian_type (string, optional (default='normalized')) – The type of laplacian to use. Can be ‘unnormalized’, ‘normalized’ or ‘random_walk’.

Returns:

component_embedding (array of shape (n_components, dim)) – The dim-dimensional embedding of the n_components-many connected components.

topo.spectral.eigen.multi_component_layout(graph, n_components, component_labels, dim, laplacian_type, random_state, eigen_tol, return_eval_list)