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 builtin 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¶




Fourier basis (eigenvectors of the Laplacian). 

Differential operator (for gradient and divergence). 
Checks¶

Check the characteristics of the weights matrix. 

Check the strong connectivity of the graph (cached). 

Check if the graph has directed edges (cached). 
Attributes computation¶

Compute a graph Laplacian. 

Estimate the Laplacian’s largest eigenvalue (cached). 

Compute the Fourier basis of the graph (cached). 
Compute the graph differential operator (cached). 
Differential operators¶

Compute the gradient of a graph signal. 

Compute the divergence of a graph signal. 
Localization¶

Modulate the signal f to the frequency k. 

Translate the signal f to the node i. 
Transforms (frequency and vertexfrequency)¶

Compute the graph Fourier transform. 

Compute the inverse graph Fourier transform. 

Windowed graph Fourier transform. 

Gabor windowed graph Fourier transform. 

Normalized windowed graph Fourier transform. 
Plotting¶

Plot the graph. 

Plot a signal on that graph. 

Plot the graph’s spectrogram. 
Others¶

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

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

Create a subgraph given indices. 

Split the graph into connected components. 
Graph models¶

Airfoil graph. 

BarabasiAlbert preferential attachment. 

Comet graph. 

Community graph. 

Sensor network. 

Erdos Renyi graph. 

Fully connected graph. 

2dimensional grid graph. 

GSP logo. 

Low stretch tree. 

Minnesota road network (from MatlabBGL). 

Path graph. 

Random kregular graph. 

Ring graph with randomly sampled nodes. 

Kregular ring graph. 

Random sensor graph. 

Stochastic Block Model (SBM). 

Sampled Swiss roll manifold. 

Sampled torus manifold. 
Nearestneighbors graphs constructed from point clouds¶

Nearestneighbor graph from given point cloud. 

Stanford bunny (NNgraph). 

Hypercube (NNgraph). 

NNgraph between patches of an image. 

Union of a patch graph with a 2D grid graph. 

Sphericalshaped graph (NNgraph). 

Two Moons (NNgraph). 

class
pygsp.graphs.
Graph
(W, gtype='unknown', lap_type='combinatorial', coords=None, plotting={})[source]¶ 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 freeform 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 NbyN 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 NbyN 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)[source]¶ 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()
anddiv()
.The result is cached and accessible by the
D
property.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
, andmu
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')[source]¶ 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() >>> 1e10 < G.e[0] < 1e10 # Smallest eigenvalue close to 0. True >>> >>> G.compute_laplacian('normalized') >>> G.compute_fourier_basis(recompute=True) >>> 1e10 < G.e[0] < 1e10 < 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 (nondirected 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)[source]¶ 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)[source]¶ 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)[source]¶ 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) < 1e10) 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
Vertexfrequency 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 (nondirected 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)) < 1e10 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) < 1e10) True

is_connected
(self, recompute=False)[source]¶ 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)[source]¶ 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)[source]¶ Modulate the signal f to the frequency k.
 Parameters
 fndarray
Signal (column)
 kint
Index of frequencies
 Returns
 fmndarray
Modulated signal

plot_signal
(self, signal, \*\*kwargs)[source]¶ Plot a signal on that graph.
See
pygsp.plotting.plot_signal()
.

plot_spectrogram
(self, \*\*kwargs)[source]¶ Plot the graph’s spectrogram.
See
pygsp.plotting.plot_spectrogram()
.

set_coordinates
(self, kind='spring', \*\*kwargs)[source]¶ Set node’s coordinates (their position when plotting).
 Parameters
 kindstring or arraylike
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 FruchtermanReingold forcedirected algorithm when kind is spring.
Examples
>>> G = graphs.ErdosRenyi() >>> G.set_coordinates() >>> G.plot()

subgraph
(self, ind)[source]¶ 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 NbyN 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 byestimate_lmax()
.

property
mu
¶ Coherence of the Fourier basis.
Is computed by
compute_fourier_basis()
.