Graphs

The pygsp.graphs module implements the graph class hierarchy. A graph object is either constructed from an adjacency matrix, or by instantiating one of the built-in graph models.

Interface

The Graph base class allows to construct a graph object from any adjacency matrix and provides a common interface to that object. Derived classes then allows to instantiate various standard graph models.

Matrix operators

Graph.W
Graph.L
Graph.U	Fourier basis (eigenvectors of the Laplacian).
Graph.D	Differential operator (for gradient and divergence).

Checks

Graph.check_weights(self)	Check the characteristics of the weights matrix.
Graph.is_connected(self[, recompute])	Check the strong connectivity of the graph (cached).
Graph.is_directed(self[, recompute])	Check if the graph has directed edges (cached).

Attributes computation

Graph.compute_laplacian(self[, lap_type])	Compute a graph Laplacian.
Graph.estimate_lmax(self[, recompute])	Estimate the Laplacian’s largest eigenvalue (cached).
Graph.compute_fourier_basis(self[, recompute])	Compute the Fourier basis of the graph (cached).
Graph.compute_differential_operator(self)	Compute the graph differential operator (cached).

Differential operators

Graph.grad(self, s)	Compute the gradient of a graph signal.
Graph.div(self, s)	Compute the divergence of a graph signal.

Localization

Graph.modulate(self, f, k)	Modulate the signal f to the frequency k.
Graph.translate(self, f, i)	Translate the signal f to the node i.

Transforms (frequency and vertex-frequency)

Graph.gft(self, s)	Compute the graph Fourier transform.
Graph.igft(self, s_hat)	Compute the inverse graph Fourier transform.
Graph.gft_windowed(self, g, f[, lowmemory])	Windowed graph Fourier transform.
Graph.gft_windowed_gabor(self, s, k)	Gabor windowed graph Fourier transform.
Graph.gft_windowed_normalized(self, g, f[, …])	Normalized windowed graph Fourier transform.

Plotting

Graph.plot(self, \*\*kwargs)	Plot the graph.
Graph.plot_signal(self, signal, \*\*kwargs)	Plot a signal on that graph.
Graph.plot_spectrogram(self, \*\*kwargs)	Plot the graph’s spectrogram.

Others

Graph.get_edge_list(self)	Return an edge list, an alternative representation of the graph.
Graph.set_coordinates(self[, kind])	Set node’s coordinates (their position when plotting).
Graph.subgraph(self, ind)	Create a subgraph given indices.
Graph.extract_components(self)	Split the graph into connected components.

Graph models

Airfoil(**kwargs)	Airfoil graph.
BarabasiAlbert([N, m0, m, seed])	Barabasi-Albert preferential attachment.
Comet([N, k])	Comet graph.
Community([N, Nc, min_comm, min_deg, …])	Community graph.
DavidSensorNet([N, seed])	Sensor network.
ErdosRenyi([N, p, directed, self_loops, …])	Erdos Renyi graph.
FullConnected([N])	Fully connected graph.
Grid2d([N1, N2])	2-dimensional grid graph.
Logo(**kwargs)	GSP logo.
LowStretchTree([k])	Low stretch tree.
Minnesota([connect])	Minnesota road network (from MatlabBGL).
Path([N])	Path graph.
RandomRegular([N, k, maxIter, seed])	Random k-regular graph.
RandomRing([N, seed])	Ring graph with randomly sampled nodes.
Ring([N, k])	K-regular ring graph.
Sensor([N, Nc, regular, n_try, distribute, …])	Random sensor graph.
StochasticBlockModel([N, k, z, M, p, q, …])	Stochastic Block Model (SBM).
SwissRoll([N, a, b, dim, thresh, s, noise, …])	Sampled Swiss roll manifold.
Torus([Nv, Mv])	Sampled torus manifold.

Nearest-neighbors graphs constructed from point clouds

NNGraph(Xin[, NNtype, use_flann, center, …])	Nearest-neighbor graph from given point cloud.
Bunny(**kwargs)	Stanford bunny (NN-graph).
Cube([radius, nb_pts, nb_dim, sampling, seed])	Hyper-cube (NN-graph).
ImgPatches(img[, patch_shape])	NN-graph between patches of an image.
Grid2dImgPatches(img[, aggregate])	Union of a patch graph with a 2D grid graph.
Sphere([radius, nb_pts, nb_dim, sampling, seed])	Spherical-shaped graph (NN-graph).
TwoMoons([moontype, dim, sigmag, N, sigmad, …])	Two Moons (NN-graph).

class pygsp.graphs.Graph(W, gtype='unknown', lap_type='combinatorial', coords=None, plotting={})

Base graph class.

• Provide a common interface (and implementation) to graph objects.

• Can be instantiated to construct custom graphs from a weight matrix.

• Initialize attributes for derived classes.

Parameters

Wsparse matrix or ndarray

The weight matrix which encodes the graph.

gtypestring

Graph type, a free-form string to help us recognize the kind of graph we are dealing with (default is ‘unknown’).

lap_type‘combinatorial’, ‘normalized’

The type of Laplacian to be computed by compute_laplacian() (default is ‘combinatorial’).

coordsndarray

Vertices coordinates (default is None).

plottingdict

Plotting parameters.

Examples

>>> W = np.arange(4).reshape(2, 2)
>>> G = graphs.Graph(W)

Attributes

Nint

the number of nodes / vertices in the graph.

Neint

the number of edges / links in the graph, i.e. connections between nodes.

Wsparse matrix

the weight matrix which contains the weights of the connections. It is represented as an N-by-N matrix of floats. \(W_{i,j} = 0\) means that there is no direct connection from i to j.

gtypestring

the graph type is a short description of the graph object designed to help sorting the graphs.

Lsparse matrix

the graph Laplacian, an N-by-N matrix computed from W.

lap_type‘normalized’, ‘combinatorial’

the kind of Laplacian that was computed by compute_laplacian().

coordsndarray

vertices coordinates in 2D or 3D space. Used for plotting only. Default is None.

plottingdict

plotting parameters.

check_weights(self)

Check the characteristics of the weights matrix.

Returns

A dict of bools containing informations about the matrix

has_inf_valbool

True if the matrix has infinite values else false

has_nan_valuebool

True if the matrix has a “not a number” value else false

is_not_squarebool

True if the matrix is not square else false

diag_is_not_zerobool

True if the matrix diagonal has not only zeros else false

Examples

>>> W = np.arange(4).reshape(2, 2)
>>> G = graphs.Graph(W)
>>> cw = G.check_weights()
>>> cw == {'has_inf_val': False, 'has_nan_value': False,
...        'is_not_square': False, 'diag_is_not_zero': True}
True

compute_differential_operator(self)

Compute the graph differential operator (cached).

The differential operator is a matrix such that

\[L = D^T D,\]

where \(D\) is the differential operator and \(L\) is the graph Laplacian. It is used to compute the gradient and the divergence of a graph signal, see grad() and div().

The result is cached and accessible by the D property.

See also

grad

compute the gradient

div

compute the divergence

Examples

>>> G = graphs.Logo()
>>> G.N, G.Ne
(1130, 3131)
>>> G.compute_differential_operator()
>>> G.D.shape == (G.Ne, G.N)
True

compute_fourier_basis(self, recompute=False)

Compute the Fourier basis of the graph (cached).

The result is cached and accessible by the U, e, lmax, and mu properties.

Parameters

recompute: bool

Force to recompute the Fourier basis if already existing.

Notes

‘G.compute_fourier_basis()’ computes a full eigendecomposition of the graph Laplacian \(L\) such that:

\[L = U \Lambda U^*,\]

where \(\Lambda\) is a diagonal matrix of eigenvalues and the columns of \(U\) are the eigenvectors.

G.e is a vector of length G.N containing the Laplacian eigenvalues. The largest eigenvalue is stored in G.lmax. The eigenvectors are stored as column vectors of G.U in the same order that the eigenvalues. Finally, the coherence of the Fourier basis is found in G.mu.

References

See [Chu97].

Examples

>>> G = graphs.Torus()
>>> G.compute_fourier_basis()
>>> G.U.shape
(256, 256)
>>> G.e.shape
(256,)
>>> G.lmax == G.e[-1]
True
>>> G.mu < 1
True

compute_laplacian(self, lap_type='combinatorial')

Compute a graph Laplacian.

The result is accessible by the L attribute.

Parameters

lap_type‘combinatorial’, ‘normalized’

The type of Laplacian to compute. Default is combinatorial.

Notes

For undirected graphs, the combinatorial Laplacian is defined as

\[L = D - W,\]

where \(W\) is the weight matrix and \(D\) the degree matrix, and the normalized Laplacian is defined as

\[L = I - D^{-1/2} W D^{-1/2},\]

where \(I\) is the identity matrix.

Examples

>>> G = graphs.Sensor(50)
>>> G.L.shape
(50, 50)
>>>
>>> G.compute_laplacian('combinatorial')
>>> G.compute_fourier_basis()
>>> -1e-10 < G.e[0] < 1e-10  # Smallest eigenvalue close to 0.
True
>>>
>>> G.compute_laplacian('normalized')
>>> G.compute_fourier_basis(recompute=True)
>>> -1e-10 < G.e[0] < 1e-10 < G.e[-1] < 2  # Spectrum in [0, 2].
True

div(self, s)

Compute the divergence of a graph signal.

The divergence of a signal \(s\) is defined as

\[y = D^T s,\]

where \(D\) is the differential operator D.

Parameters

sndarray

Signal of length G.Ne/2 living on the edges (non-directed graph).

Returns

s_divndarray

Divergence signal of length G.N living on the nodes.

See also

compute_differential_operator

grad

compute the gradient

Examples

>>> G = graphs.Logo()
>>> G.N, G.Ne
(1130, 3131)
>>> s = np.random.normal(size=G.Ne)
>>> s_div = G.div(s)
>>> s_grad = G.grad(s_div)

estimate_lmax(self, recompute=False)

Estimate the Laplacian’s largest eigenvalue (cached).

The result is cached and accessible by the lmax property.

Exact value given by the eigendecomposition of the Laplacian, see compute_fourier_basis(). That estimation is much faster than the eigendecomposition.

Parameters

recomputeboolean

Force to recompute the largest eigenvalue. Default is false.

Notes

Runs the implicitly restarted Lanczos method with a large tolerance, then increases the calculated largest eigenvalue by 1 percent. For much of the PyGSP machinery, we need to approximate wavelet kernels on an interval that contains the spectrum of L. The only cost of using a larger interval is that the polynomial approximation over the larger interval may be a slightly worse approximation on the actual spectrum. As this is a very mild effect, it is not necessary to obtain very tight bounds on the spectrum of L.

Examples

>>> G = graphs.Logo()
>>> G.compute_fourier_basis()
>>> print('{:.2f}'.format(G.lmax))
13.78
>>> G = graphs.Logo()
>>> G.estimate_lmax(recompute=True)
>>> print('{:.2f}'.format(G.lmax))
13.92

extract_components(self)

Split the graph into connected components.

See is_connected() for the method used to determine connectedness.

Returns

graphslist

A list of graph structures. Each having its own node list and weight matrix. If the graph is directed, add into the info parameter the information about the source nodes and the sink nodes.

Examples

>>> from scipy import sparse
>>> W = sparse.rand(10, 10, 0.2)
>>> W = utils.symmetrize(W)
>>> G = graphs.Graph(W=W)
>>> components = G.extract_components()
>>> has_sinks = 'sink' in components[0].info
>>> sinks_0 = components[0].info['sink'] if has_sinks else []

get_edge_list(self)

Return an edge list, an alternative representation of the graph.

The weighted adjacency matrix is the canonical form used in this package to represent a graph as it is the easiest to work with when considering spectral methods.

Returns

v_invector of int

v_outvector of int

weightsvector of float

Examples

>>> G = graphs.Logo()
>>> v_in, v_out, weights = G.get_edge_list()
>>> v_in.shape, v_out.shape, weights.shape
((3131,), (3131,), (3131,))

gft(self, s)

Compute the graph Fourier transform.

The graph Fourier transform of a signal \(s\) is defined as

\[\hat{s} = U^* s,\]

where \(U\) is the Fourier basis attr:U and \(U^*\) denotes the conjugate transpose or Hermitian transpose of \(U\).

Parameters

sndarray

Graph signal in the vertex domain.

Returns

s_hatndarray

Representation of s in the Fourier domain.

Examples

>>> G = graphs.Logo()
>>> G.compute_fourier_basis()
>>> s = np.random.normal(size=(G.N, 5, 1))
>>> s_hat = G.gft(s)
>>> s_star = G.igft(s_hat)
>>> np.all((s - s_star) < 1e-10)
True

gft_windowed(self, g, f, lowmemory=True)

Windowed graph Fourier transform.

Parameters

gndarray or Filter

Window (graph signal or kernel).

fndarray

Graph signal in the vertex domain.

lowmemorybool

Use less memory (default=True).

Returns

Cndarray

Coefficients.

gft_windowed_gabor(self, s, k)

Gabor windowed graph Fourier transform.

Parameters

sndarray

Graph signal in the vertex domain.

kfunction

Gabor kernel. See pygsp.filters.Gabor.

Returns

sndarray

Vertex-frequency representation of the signals.

Examples

>>> G = graphs.Logo()
>>> s = np.random.normal(size=(G.N, 2))
>>> s = G.gft_windowed_gabor(s, lambda x: x/(1.-x))
>>> s.shape
(1130, 2, 1130)

gft_windowed_normalized(self, g, f, lowmemory=True)

Normalized windowed graph Fourier transform.

Parameters

gndarray

Window.

fndarray

Graph signal in the vertex domain.

lowmemorybool

Use less memory. (default = True)

Returns

Cndarray

Coefficients.

grad(self, s)

Compute the gradient of a graph signal.

The gradient of a signal \(s\) is defined as

\[y = D s,\]

where \(D\) is the differential operator D.

Parameters

sndarray

Signal of length G.N living on the nodes.

Returns

s_gradndarray

Gradient signal of length G.Ne/2 living on the edges (non-directed graph).

See also

compute_differential_operator

div

compute the divergence

Examples

>>> G = graphs.Logo()
>>> G.N, G.Ne
(1130, 3131)
>>> s = np.random.normal(size=G.N)
>>> s_grad = G.grad(s)
>>> s_div = G.div(s_grad)
>>> np.linalg.norm(s_div - G.L.dot(s)) < 1e-10
True

igft(self, s_hat)

Compute the inverse graph Fourier transform.

The inverse graph Fourier transform of a Fourier domain signal \(\hat{s}\) is defined as

\[s = U \hat{s},\]

where \(U\) is the Fourier basis U.

Parameters

s_hatndarray

Graph signal in the Fourier domain.

Returns

sndarray

Representation of s_hat in the vertex domain.

Examples

>>> G = graphs.Logo()
>>> G.compute_fourier_basis()
>>> s_hat = np.random.normal(size=(G.N, 5, 1))
>>> s = G.igft(s_hat)
>>> s_hat_star = G.gft(s)
>>> np.all((s_hat - s_hat_star) < 1e-10)
True

is_connected(self, recompute=False)

Check the strong connectivity of the graph (cached).

It uses DFS travelling on graph to ensure that each node is visited. For undirected graphs, starting at any vertex and trying to access all others is enough. For directed graphs, one needs to check that a random vertex is accessible by all others and can access all others. Thus, we can transpose the adjacency matrix and compute again with the same starting point in both phases.

Parameters

recompute: bool

Force to recompute the connectivity if already known.

Returns

connectedbool

True if the graph is connected.

Examples

>>> from scipy import sparse
>>> W = sparse.rand(10, 10, 0.2)
>>> G = graphs.Graph(W=W)
>>> connected = G.is_connected()

is_directed(self, recompute=False)

Check if the graph has directed edges (cached).

In this framework, we consider that a graph is directed if and only if its weight matrix is non symmetric.

Parameters

recomputebool

Force to recompute the directedness if already known.

Returns

directedbool

True if the graph is directed.

Notes

Can also be used to check if a matrix is symmetrical

Examples

>>> from scipy import sparse
>>> W = sparse.rand(10, 10, 0.2)
>>> G = graphs.Graph(W=W)
>>> directed = G.is_directed()

modulate(self, f, k)

Modulate the signal f to the frequency k.

Parameters

fndarray

Signal (column)

kint

Index of frequencies

Returns

fmndarray

Modulated signal

plot(self, \*\*kwargs)

Plot the graph.

See pygsp.plotting.plot_graph().

plot_signal(self, signal, \*\*kwargs)

Plot a signal on that graph.

See pygsp.plotting.plot_signal().

plot_spectrogram(self, \*\*kwargs)

Plot the graph’s spectrogram.

See pygsp.plotting.plot_spectrogram().

set_coordinates(self, kind='spring', \*\*kwargs)

Set node’s coordinates (their position when plotting).

Parameters

kindstring or array-like

Kind of coordinates to generate. It controls the position of the nodes when plotting the graph. Can either pass an array of size Nx2 or Nx3 to set the coordinates manually or the name of a layout algorithm. Available algorithms: community2D, random2D, random3D, ring2D, line1D, spring. Default is ‘spring’.

kwargsdict

Additional parameters to be passed to the Fruchterman-Reingold force-directed algorithm when kind is spring.

Examples

>>> G = graphs.ErdosRenyi()
>>> G.set_coordinates()
>>> G.plot()

subgraph(self, ind)

Create a subgraph given indices.

Parameters

indlist

Nodes to keep

Returns

sub_GGraph

Subgraph

Examples

>>> W = np.arange(16).reshape(4, 4)
>>> G = graphs.Graph(W)
>>> ind = [1, 3]
>>> sub_G = G.subgraph(ind)

translate(self, f, i)

Translate the signal f to the node i.

Parameters

fndarray

Signal

iint

Indices of vertex

Returns

fttranslate signal

property A

Graph adjacency matrix (the binary version of W).

The adjacency matrix defines which edges exist on the graph. It is represented as an N-by-N matrix of booleans. \(A_{i,j}\) is True if \(W_{i,j} > 0\).

property D

Differential operator (for gradient and divergence).

Is computed by compute_differential_operator().

property U

Fourier basis (eigenvectors of the Laplacian).

Is computed by compute_fourier_basis().

property d

The degree (the number of neighbors) of each node.

property dw

The weighted degree (the sum of weighted edges) of each node.

property e

Eigenvalues of the Laplacian (square of graph frequencies).

Is computed by compute_fourier_basis().

property lmax

Largest eigenvalue of the graph Laplacian.

Can be exactly computed by compute_fourier_basis() or approximated by estimate_lmax().

property mu

Coherence of the Fourier basis.

Is computed by compute_fourier_basis().