graphslim.coarsening package

graphslim.coarsening.coarsening_base

class graphslim.coarsening.coarsening_base.Coarsen(setting, data, args)[source]

Bases: object

Graph Coarsening

This class provides methods to coarsen a graph, which involves reducing the number of nodes while preserving certain properties of the original graph.

Parameters:

setting (str) – The setting for coarsening.
data (object) – The data to be coarsened.
args (Namespace) – Arguments containing configurations and device information.
**kwargs (dict, optional) – Additional keyword arguments.

reduce(data, verbose=True, save=True)[source]: Reduces the data by coarsening the graph.

coarsening(H)[source]: Performs the coarsening process on the graph H.

process_coarsened(data, candidate, C_list, Gc_list)[source]: Processes the coarsened graphs and returns the features, labels, masks, and edges.

coarsening(H)[source]

Performs the coarsening process on the given graph.

Parameters:

H (object) – The graph to be coarsened.

Returns:

candidate (list) – List of subgraphs sorted by size.
C_list (list) – List of coarsening matrices.
Gc_list (list) – List of coarsened graphs.

process_coarsened(data, candidate, C_list, Gc_list)[source]

Processes the coarsened graph to extract relevant features and labels.

Parameters:

data (object) – The original data.
candidate (list) – List of candidate subgraphs.
C_list (list) – List of coarsening matrices.
Gc_list (list) – List of coarsened graphs.

Returns:

coarsen_features (torch.Tensor) – The coarsened features.
coarsen_train_labels (torch.Tensor) – The coarsened training labels.
coarsen_train_mask (torch.Tensor) – The coarsened training mask.
coarsen_edge (torch.Tensor) – The coarsened edges.

reduce(data, verbose=True, save=True)[source]

Reduces the data by coarsening the graph.

Parameters:

data (object) – The data to be reduced.
verbose (bool, optional) – If True, prints verbose output. Defaults to True.
save (bool, optional) – If True, saves the reduced data. Defaults to True.

Returns:

The reduced data with updated attributes adj_syn, feat_syn, and labels_syn.

Return type:

object

graphslim.coarsening.affinity_gs module

class graphslim.coarsening.affinity_gs.AffinityGs(setting, data, args)[source]

Bases: Coarsen

coarsen(G)[source]

graphslim.coarsening.algebraic_jc module

class graphslim.coarsening.algebraic_jc.AlgebraicJc(setting, data, args)[source]

Bases: Coarsen

coarsen(G)[source]

graphslim.coarsening.heavy_edge module

class graphslim.coarsening.heavy_edge.HeavyEdge(setting, data, args)[source]

Bases: Coarsen

coarsen(G, method)[source]

graphslim.coarsening.kron module

class graphslim.coarsening.kron.Kron(setting, data, args)[source]

Bases: Coarsen

coarsen(G)[source]

graphslim.coarsening.variation_cliques module

class graphslim.coarsening.variation_cliques.VariationCliques(setting, data, args)[source]

Bases: Coarsen

coarsen(G)[source]

graphslim.coarsening.variation_edges module

class graphslim.coarsening.variation_edges.VariationEdges(setting, data, args)[source]

Bases: Coarsen

coarsen(G)[source]

graphslim.coarsening.variation_neighborhoods module

class graphslim.coarsening.variation_neighborhoods.VariationNeighborhoods(setting, data, args)[source]

Bases: Coarsen

coarsen(G)[source]

graphslim.coarsening.averaging module

class graphslim.coarsening.averaging.Average(setting, data, args)[source]

Bases: Coarsen

A structure-free coarsening method that also serves as initialization for condensation methods. Outputs synthesized features (feat_syn) and labels (label_syn).

Parameters:

setting (str) – Configuration setting.
data (object) – Data object containing the graph and feature information.
args (object) – Arguments containing various settings for the coarsening process.
**kwargs (dict, optional) – Additional keyword arguments.

prepare_select(data, args)[source]

Prepares and selects synthetic labels and features for coarsening.

Parameters:

data (object) – The data to be processed.
args (object) – Arguments containing various settings for the coarsening process.

Returns:

A tuple containing: - labels_syn : ndarray

Synthesized labels.

labels_traintensor
Training labels.
feat_traintensor
Training features.

Return type:

tuple

reduce(data, verbose=True, save=True)[source]

Reduces the data by averaging features for each class.

Parameters:

data (object) – The data to be reduced.
verbose (bool, optional) – If True, prints verbose output. Defaults to True.
save (bool, optional) – If True, saves the reduced data. Defaults to True.

Returns:

The reduced data with synthesized features and labels.

Return type:

object

graphslim.coarsening.clustering module

class graphslim.coarsening.clustering.Cluster(setting, data, args)[source]

Bases: Coarsen

A structure-free coarsening method that also serves as initialization for condensation methods. Outputs synthesized features (feat_syn) and labels (label_syn).

Parameters:

setting (str) – Configuration setting.
data (object) – Data object containing the graph and feature information.
args (object) – Arguments containing various settings for the coarsening process.
**kwargs (dict, optional) – Additional keyword arguments.

prepare_select(data, args)[source]

Prepares and selects synthetic labels and features for coarsening.

Parameters:

data (object) – The data to be processed.
args (object) – Arguments containing various settings for the coarsening process.

Returns:

A tuple containing: - labels_syn : ndarray

Synthesized labels.

labels_traintensor
Training labels.
feat_traintensor
Training features.

Return type:

tuple

reduce(data, verbose=True, save=True)[source]

Reduces the data by clustering features for each class using Bisecting K-means.

Parameters:

data (object) – The data to be reduced.
verbose (bool, optional) – If True, prints verbose output. Defaults to True.
save (bool, optional) – If True, saves the reduced data. Defaults to True.

Returns:

The reduced data with synthesized features and labels.

Return type:

object

graphslim.coarsening.clusteringagg module

class graphslim.coarsening.clusteringagg.ClusterAgg(setting, data, args)[source]

Bases: Coarsen

ClusteringAgg is a variant of Clustering, which clustering aggregated features instead of original features. A structure-free coarsening method that also serves as initialization for condensation methods. Outputs synthesized features (feat_syn) and labels (label_syn).

Parameters:

setting (str) – Configuration setting.
data (object) – Data object containing the graph and feature information.
args (object) – Arguments containing various settings for the coarsening process.
**kwargs (dict, optional) – Additional keyword arguments.

prepare_select(data, args)[source]

Prepares and selects synthetic labels and features for coarsening.

Parameters:

data (object) – The data to be processed.
args (object) – Arguments containing various settings for the coarsening process.

Returns:

A tuple containing: - labels_syn : ndarray

Synthesized labels.

labels_traintensor
Training labels.

Return type:

tuple

reduce(data, verbose=True, save=True)[source]

Reduces the data by aggregating features using a pre-convolution step and clustering.

Parameters:

data (object) – The data to be reduced.
verbose (bool, optional) – If True, prints verbose output. Defaults to True.
save (bool, optional) – If True, saves the reduced data. Defaults to True.

Returns:

The reduced data with synthesized features and labels.

Return type:

object

graphslim.coarsening.vng module

class graphslim.coarsening.vng.VNG(setting, data, args, **kwargs)[source]

Bases: object

A class that implements Virtual Node Graph (VNG) reduction for coarsening graphs. Refer to paper “Serving Graph Compression for Graph Neural Networks” https://openreview.net/forum?id=T-qVtA3pAxG.

Parameters:

setting (str) – Configuration setting.
data (object) – Data object containing the graph and feature information.
args (object) – Arguments containing various settings for the coarsening process.
**kwargs (dict, optional) – Additional keyword arguments.

reduce(data, verbose=False)[source]

Reduces the data by applying Virtual Node Graph (VNG) method.

Parameters:

data (object) – The data to be reduced.
verbose (bool, optional) – If True, prints verbose output. Defaults to False.

Returns:

The reduced data with synthesized adjacency, features, and labels.

Return type:

object

vng(X_tr_0, embeds, adj, labels, verbose=False)[source]

Virtual Node Graph (VNG) method to coarsen the graph.

Parameters:

embeds (list of tensors) – List of embeddings.
adj (tensor) – Adjacency matrix.
labels (tensor) – One-hot encoded labels.
verbose (bool, optional) – If True, prints verbose output. Defaults to False.

Returns:

A tuple containing:

coarsen_edgetensor
Coarsened adjacency matrix.
coarsen_featurestensor
Coarsened features.
coarsen_labelstensor
Coarsened labels.

Return type:

tuple

graphslim.coarsening.utils module

graphslim.coarsening.utils.coarsen_matrix(W, C)[source]

Coarsen the input adjacency matrix W using the coarsening matrix C.

Parameters:

W (scipy.sparse.csr_matrix or array_like) – The original adjacency matrix to be coarsened.
C (scipy.sparse.csr_matrix or array_like) – The coarsening matrix used to reduce the size of the original matrix.

Returns:

coarsened_W – The coarsened adjacency matrix obtained after applying the coarsening process.

Return type:

scipy.sparse.csr_matrix or numpy.ndarray

Examples

>>> from scipy.sparse import csr_matrix
>>> import numpy as np
>>> W = csr_matrix([[0, 1, 0], [1, 0, 1], [0, 1, 0]])
>>> C = csr_matrix([[1, 0], [0, 1], [1, 1]])
>>> coarsen_matrix(W, C)
matrix([[0.5, 0.5],
        [0.5, 0.5]])

graphslim.coarsening.utils.coarsen_vector(x, C)[source]

Coarsen a vector by applying the square of a matrix and then performing a dot product.

Parameters:

x (array_like) – Input vector to be coarsened.
C (scipy.sparse.csr_matrix or array_like) – Matrix used to coarsen the vector. The matrix is squared before the dot product is performed.

Returns:

The resulting vector after coarsening.

Return type:

numpy.ndarray

Examples

>>> from scipy.sparse import csr_matrix
>>> import numpy as np
>>> x = np.array([1, 2, 3])
>>> C = csr_matrix([[1, 0, 0], [0, 2, 0], [0, 0, 3]])
>>> coarsen_vector(x, C)
array([ 1,  8, 27])

graphslim.coarsening.utils.coarsening_quality(G, C, kmax=30, Uk=None, lk=None)[source]

Measures the quality of a coarsening.

Parameters:

G (pygsp.graphs.Graph) – The original graph to be coarsened.
C (np.array) – The coarsening matrix of shape (n, N).
kmax (int, optional) – The maximum number of eigenvalues/eigenvectors to consider. Default is 30.
Uk (np.array, optional) – Precomputed eigenvectors of the graph Laplacian. Default is None.
lk (np.array, optional) – Precomputed eigenvalues of the graph Laplacian. Default is None.

Returns:

metrics – A dictionary containing various metrics for coarsening quality:

’error_eigenvalue’np.array
Relative error of eigenvalues.
’error_subspace’np.array
Subspace error.
’error_sintheta’np.array
Sine of the principal angles between subspaces.
’angle_matrix’np.array
Matrix of angles between eigenvectors.
’r’int
Reduction ratio.
’m’int
Number of edges in the coarsened graph.

Return type:

dict

Examples

>>> from pygsp import graphs
>>> import numpy as np
>>> G = graphs.Sensor(20)
>>> C = np.random.rand(10, 20)
>>> metrics = coarsening_quality(G, C)

graphslim.coarsening.utils.contract_variation_edges(G, A=None, K=10, r=0.5, algorithm='greedy')[source]

Perform sequential contraction with local variation and edge-based families.

This is a specialized implementation for the edge-based family, optimized for faster performance compared to the general contract_variation() function.

Parameters:

G (pygsp.graphs.Graph) – The original graph to be coarsened.
A (np.array, optional) – A matrix used in the subgraph cost function. Default is None.
K (int, optional) – The number of clusters or partitions. Default is 10.
r (float, optional) – The reduction ratio. Default is 0.5.
algorithm (str, optional) – The algorithm used for edge contraction. Can be “greedy” or “optimal”. Default is “greedy”.

Returns:

coarsening_list – A list of edges to be contracted based on the selected algorithm.

Return type:

list

Notes

This function is designed for edge-based families and works slightly faster than the contract_variation() function, which is more general.

Examples

>>> from pygsp import graphs
>>> G = graphs.Sensor(20)
>>> A = np.random.rand(20, 20)
>>> coarsening_list = contract_variation_edges(G, A, K=5, r=0.3, algorithm="greedy")

graphslim.coarsening.utils.contract_variation_linear(G, A=None, K=10, r=0.5, mode='neighborhood')[source]

Perform sequential contraction with local variation and general families.

This implementation improves running speed at the expense of being more greedy, potentially resulting in slightly larger errors.

Parameters:

G (pygsp.graphs.Graph) – The original graph to be coarsened.
A (np.array, optional) – A matrix used in the subgraph cost function. If None, it will be computed. Default is None.
K (int, optional) – The number of clusters or partitions. Default is 10.
r (float, optional) – The reduction ratio. Default is 0.5.
mode (str, optional) – The mode of contraction. Can be “neighborhood”, “cliques”, “edges”, or “triangles”. Default is “neighborhood”.

Returns:

coarsening_list – A list of node sets to be contracted based on the selected mode.

Return type:

list

Notes

This function is designed for general families and aims to speed up the process by being more greedy, potentially at the cost of higher error.

Examples

>>> from pygsp import graphs
>>> import numpy as np
>>> G = graphs.Sensor(20)
>>> A = np.random.rand(20, 10)
>>> coarsening_list = contract_variation_linear(G, A, K=5, r=0.3, mode="neighborhood")

graphslim.coarsening.utils.eig(A, order='ascend')[source]

Perform eigenvalue decomposition on a symmetric matrix and sort the eigenvalues and eigenvectors in ascending or descending order.

Parameters:

A (np.ndarray) – A symmetric matrix.
order (str, optional) – The order in which to sort the eigenvalues and eigenvectors. Can be ‘ascend’ (default) for ascending order or ‘descend’ for descending order.

Returns:

X (np.ndarray) – Matrix of eigenvectors, where each column is an eigenvector.
l (np.ndarray) – Array of eigenvalues, sorted in the specified order.

graphslim.coarsening.utils.generate_test_vectors(G, num_vectors=10, method='Gauss-Seidel', iterations=5, lambda_cut=0.1)[source]

Generate test vectors for graph processing using different iterative methods.

Parameters:

G (pygsp.graphs.Graph) – The input graph.
num_vectors (int, optional) – The number of test vectors to generate. Default is 10.
method (str, optional) – The iterative method to use for generating the test vectors. Options are “Gauss-Seidel”, “Jacobi”, and “Chebychev”. Default is “Gauss-Seidel”.
iterations (int, optional) – The number of iterations to perform for the iterative methods. Default is 5.
lambda_cut (float, optional) – The eigenvalue cutoff for the Chebychev method. Default is 0.1.

Returns:

X – An array containing the generated test vectors.

Return type:

np.ndarray

Examples

>>> from pygsp import graphs
>>> G = graphs.Sensor(20)
>>> X = generate_test_vectors(G, num_vectors=5, method="Jacobi", iterations=10)

graphslim.coarsening.utils.get_S(G)[source]

Construct the N x E gradient matrix S.

Parameters:: G (pygsp.graphs.Graph) – The input graph.
Returns:: S – The gradient matrix of shape (N, E), where N is the number of nodes and E is the number of edges.
Return type:: np.ndarray

graphslim.coarsening.utils.get_coarsening_matrix(G, partitioning)[source]

Build the coarsening matrix C for a given graph G based on the specified partitioning.

Parameters:

G (Graph) – The graph to be coarsened. The graph should have an attribute N representing the number of nodes.
partitioning (list of lists) – A list of subgraphs, where each subgraph is represented as a list of node indices to be contracted.

Returns:

C – The coarsening matrix.

Return type:

scipy.sparse.csc_matrix

Example

>>> from gsp.graphs import sensor
>>> G = sensor(20)
>>> partitioning = [[0, 1], [2, 3, 4], [5, 6, 7, 8]]
>>> C = get_coarsening_matrix(G, partitioning)

graphslim.coarsening.utils.get_proximity_measure(G, name, K=10)[source]

Calculate a proximity measure for edges in the graph based on various heuristics.

Parameters:

G (pygsp.graphs.Graph) – The input graph.
name (str) – The name of the proximity measure to be calculated. Options include “heavy_edge”, “algebraic_JC”, “affinity_GS”, “heavy_edge_degree”, “min_expected_loss”, “min_expected_gradient_loss”, “rss”, “rss_lanczos”, “rss_cheby”, “algebraic_GS”.
K (int, optional) – The number of clusters or partitions. Default is 10.

Returns:

proximity – An array containing the proximity measure for each edge in the graph.

Return type:

np.array

Examples

>>> from pygsp import graphs
>>> G = graphs.Sensor(20)
>>> proximity = get_proximity_measure(G, "heavy_edge", K=5)

graphslim.coarsening.utils.graph_sparsify(M, epsilon, maxiter=10)[source]

Sparsifies a graph by sampling edges based on their resistance distance.

Parameters:

M (pygsp.graph or scipy.sparse matrix) – The graph or its Laplacian matrix to be sparsified.
epsilon (float) – Sparsification parameter, should be in the range [1/sqrt(N), 1).
maxiter (int) – Maximum number of iterations for the sparsification process.

Returns:

Mnew – The sparsified graph or its Laplacian matrix.

Return type:

pygsp.graph or scipy.sparse matrix

graphslim.coarsening.utils.kron_coarsening(G, r=0.5, m=None)[source]

Perform Kronecker coarsening on a graph G.

Parameters:

G (pygsp.graph) – The input graph.
r (float, optional) – The coarsening ratio (r = 1 - n/N). Default is 0.5.
m (int, optional) – The target number of edges for sparsification. Default is None.

Returns:

Gc (pygsp.graph) – The coarsened graph.
Gs[0] (pygsp.graph) – The original graph.

Notes

If the coarsening fails, the function returns (None, None).

graphslim.coarsening.utils.kron_interpolate(G, Gc, x)[source]

Interpolates a signal from the coarse graph to the original graph.

Parameters:

G (pygsp.graph) – The original graph.
Gc (pygsp.graph) – The coarsened graph.
x (np.array) – The signal defined on the coarse graph nodes.

Returns:

The interpolated signal on the original graph nodes.

Return type:

np.array

Notes

The function uses the interpolation method from the reduction module.

graphslim.coarsening.utils.kron_quality(G, Gc, kmax=30, Uk=None, lk=None)[source]

Evaluate the quality of Kronecker coarsening.

Parameters:

G (pygsp.graph) – The original graph.
Gc (pygsp.graph) – The coarsened graph.
kmax (int, optional) – The maximum number of eigenvalues/eigenvectors to consider. Default is 30.
Uk (np.array, optional) – Precomputed eigenvectors of the original graph. Default is None.
lk (np.array, optional) – Precomputed eigenvalues of the original graph. Default is None.

Returns:

metrics – A dictionary containing various quality metrics of the coarsening.

Return type:

dict

Notes

The function may fail, indicated by metrics[‘failed’] being True.

graphslim.coarsening.utils.lift_matrix(W, C)[source]

Lift the input adjacency matrix W using the lifting matrix C.

Parameters:

W (scipy.sparse.csr_matrix or array_like) – The original adjacency matrix to be lifted.
C (scipy.sparse.csr_matrix or array_like) – The lifting matrix used to expand the size of the original matrix.

Returns:

lifted_W – The lifted adjacency matrix obtained after applying the lifting process.

Return type:

scipy.sparse.csr_matrix or numpy.ndarray

Examples

>>> from scipy.sparse import csr_matrix
>>> import numpy as np
>>> W = csr_matrix([[0, 1], [1, 0]])
>>> C = csr_matrix([[1, 0], [0, 1], [1, 1]])
>>> lift_matrix(W, C)
matrix([[0., 1., 0.],
        [1., 0., 1.],
        [0., 1., 0.]])

graphslim.coarsening.utils.lift_vector(input_vector, C)[source]

Lift a vector by applying a transformation involving a matrix and its pseudoinverse.

Parameters:

input_vector (array_like) – Input vector to be lifted.
C (scipy.sparse.csr_matrix or array_like) – Matrix used in the lifting process. A pseudoinverse transformation is applied to this matrix.

Returns:

The resulting vector after lifting.

Return type:

numpy.ndarray

Notes

The function creates a diagonal matrix D based on the inverse of the sum of C along the columns. It then computes Pinv, the transpose of the product of C and D. The final lifted vector is obtained by performing a dot product of Pinv and the input vector.

Examples

>>> from scipy.sparse import csr_matrix
>>> import numpy as np
>>> input_vector = np.array([1, 2, 3])
>>> C = csr_matrix([[1, 2, 0], [0, 1, 3], [4, 0, 1]])
>>> lift_vector(input_vector, C)
array([0.57142857, 0.14285714, 0.85714286])

graphslim.coarsening.utils.matching_greedy(G, weights, r=0.4)[source]

Generates a matching greedily by selecting at each iteration the edge with the largest weight and then removing all adjacent edges from the candidate set.

Parameters:

G (pygsp graph) – The input graph.
weights (np.array(M)) – A weight for each edge.
r (float, optional) – The desired dimensionality reduction (r = 1 - n/N). Default is 0.4.

Returns:

matching – An array of shape (k, 2) where each row represents a matched pair of nodes.

Return type:

np.array

Notes

The complexity of this algorithm is O(M).
Depending on G, the algorithm might fail to return ratios > 0.3.

graphslim.coarsening.utils.matching_optimal(G, weights, r=0.4)[source]

Generates a matching optimally with the objective of minimizing the total weight of all edges in the matching.

Parameters:

G (pygsp graph) – The input graph.
weights (np.array(M)) – A weight for each edge.
r (float, optional) – The desired dimensionality reduction (ratio = 1 - n/N). Default is 0.4.

Returns:

matching – An array of shape (k, 2) where each row represents a matched pair of nodes.

Return type:

np.array

Notes

The complexity of this algorithm is O(N^3).
Depending on G, the algorithm might fail to return ratios > 0.3.

graphslim.coarsening.utils.maxWeightMatching(edges, maxcardinality=False)[source]

Compute a maximum-weighted matching in the general undirected weighted graph given by “edges”. If “maxcardinality” is true, only maximum-cardinality matchings are considered as solutions.

Edges is a sequence of tuples (i, j, wt) describing an undirected edge between vertex i and vertex j with weight wt. There is at most one edge between any two vertices; no vertex has an edge to itself. Vertices are identified by consecutive, non-negative integers.

Return a list “mate”, such that mate[i] == j if vertex i is matched to vertex j, and mate[i] == -1 if vertex i is not matched.

This function takes time O(n ** 3).

graphslim.coarsening.utils.my_graph_multiresolution(G, levels, r=0.5, sparsify=True, sparsify_eps=None, downsampling_method='largest_eigenvector', reduction_method='kron', compute_full_eigen=False, reg_eps=0.005)[source]

Compute a pyramid of graphs (by Kron reduction).

‘my_graph_multiresolution(G, levels)’ computes a multiresolution of a graph by repeatedly downsampling and performing graph reduction. The default downsampling method is the largest eigenvector method based on the polarity of the components of the eigenvector associated with the largest graph Laplacian eigenvalue. The default graph reduction method is Kron reduction followed by a graph sparsification step. param is a structure of optional parameters.

Parameters:

G (pygsp.graph) – The graph to reduce.
levels (int) – Number of levels of decomposition.
r (float) – Dimensionality reduction ratio (default is 0.5).
sparsify (bool) – Whether to perform a spectral sparsification step immediately after the graph reduction (default is True).
sparsify_eps (float) – Parameter epsilon used in the spectral sparsification (default is min(10/sqrt(G.N), 0.3)).
downsampling_method (string) – The graph downsampling method (default is ‘largest_eigenvector’).
reduction_method (string) – The graph reduction method (default is ‘kron’).
compute_full_eigen (bool) – Whether to compute the graph Laplacian eigenvalues and eigenvectors for every graph in the multiresolution sequence (default is False).
reg_eps (float) – The regularized graph Laplacian is L + epsilon * I. A smaller epsilon may lead to better regularization, but will also require a higher order Chebyshev approximation (default is 0.005).

Returns:

Gs – A list of graph layers.

Return type:

list

Examples

>>> from pygsp import reduction
>>> levels = 5
>>> G = graphs.Sensor(N=512)
>>> G.compute_fourier_basis()
>>> Gs = my_graph_multiresolution(G, levels, sparsify=False)
>>> for idx in range(levels):
...     Gs[idx].plotting['plot_name'] = 'Reduction level: {}'.format(idx)
...     Gs[idx].plot()

graphslim.coarsening.utils.zero_diag(A)[source]

Set the diagonal elements of a matrix to zero.

Parameters:: A (np.ndarray or scipy.sparse matrix) – The input matrix.
Returns:: A – The matrix with diagonal elements set to zero.
Return type:: np.ndarray or scipy.sparse matrix