# Tutorial

This notebook gives an overview of scikit-network, a open-source Python package for machine learning on graphs.

## 1. Installation

The easiest way to install scikit-network is through pip.

:

# uncomment to install
# !pip install scikit-network


## 2. Data

Each graph with $$n$$ nodes is represented by a square adjacency matrix $$A$$ of size $$n \times n$$. In its simplest form, the matrix $$A$$ is binary and we have $$A_{ij} =1$$ if and only if there is a link from node $$i$$ to node $$j$$. If the graph is undirected, the matrix $$A$$ is symmetric.

:

import numpy as np

:

adjacency = np.array([[0, 1, 1, 1, 0], [1, 0, 0, 0, 1], [1, 0, 0, 1, 0], [1, 0, 1, 0, 1], [0, 1, 0, 1, 0]])

:

adjacency

:

array([[0, 1, 1, 1, 0],
[1, 0, 0, 0, 1],
[1, 0, 0, 1, 0],
[1, 0, 1, 0, 1],
[0, 1, 0, 1, 0]])


### Sparse matrix

In scikit-network, the adajcency matrix is represented in the sparse CSR format of scipy.

:

from scipy import sparse

:

adjacency = sparse.csr_matrix(adjacency)

:

adjacency

:

<5x5 sparse matrix of type '<class 'numpy.int64'>'
with 12 stored elements in Compressed Sparse Row format>


### Visualization

Here is the visualization of the above graph.

:

from IPython.display import SVG
from sknetwork.visualization import svg_graph

:

# name nodes by indices
names = np.arange(n_nodes)

:

# visualization

: ### Directed graphs

The adjacency matrix is not necessarily symmetric. There might be a link from node $$i$$ to node $$j$$ but not from node $$j$$ to node $$i$$.

:

adjacency = np.array([[0, 1, 1, 1, 0], [0, 0, 0, 1, 1], [0, 1, 0, 0, 0], [1, 0, 0, 0, 1], [0, 1, 0, 0, 0]])

:

adjacency

:

array([[0, 1, 1, 1, 0],
[0, 0, 0, 1, 1],
[0, 1, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 1, 0, 0, 0]])

:

adjacency = sparse.csr_matrix(adjacency)

:

# visualization

: ### Bipartite graphs

Bipartite graphs are special graphs with edges between two sets of nodes. A bipartite graph can be represented by its biadjacency matrix $$B$$, a rectangular matrix of links between the two sets of nodes. We have $$B_{ij}=1$$ if and only if there is an edge between node $$i$$ of the first set (represented by the rows of $$B$$) and node $$j$$ of the second set (represented by the columns of $$B$$).

:

biadjacency = np.array([[1, 1, 0, 1, 0], [0, 0, 1, 0, 1], [1, 1, 1, 1, 0], [0, 0, 0, 1, 1]])

:

biadjacency

:

array([[1, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[1, 1, 1, 1, 0],
[0, 0, 0, 1, 1]])

:

biadjacency = sparse.csr_matrix(biadjacency)

:

biadjacency

:

<4x5 sparse matrix of type '<class 'numpy.int64'>'
with 11 stored elements in Compressed Sparse Row format>

:

from sknetwork.visualization import svg_bigraph

:

# name nodes by indices
names_row = np.arange(n_row)
names_col = np.arange(n_col)

:

# visualization

: ### Weighted graphs

Weights on edges can be represented by an adjacency matrix with non-negative entries (or a biadjacency matrix for a bipartite graph).

:

adjacency = np.array([[0, 2, 1, 3, 0], [2, 0, 0, 0, 3], [1, 0, 0, 2, 0], [3, 0, 2, 0, 1], [0, 3, 0, 1, 0]])

:

adjacency

:

array([[0, 2, 1, 3, 0],
[2, 0, 0, 0, 3],
[1, 0, 0, 2, 0],
[3, 0, 2, 0, 1],
[0, 3, 0, 1, 0]])

:

adjacency = sparse.csr_matrix(adjacency)

:

# visualization

: ### Subgraphs

Subgraphs can easily be obtained by slicing the adjacency matrix.

:

index = [0, 2, 3, 4]

:

# visualization

: ## 3. Algorithms

### Basic tools

Some basic tools for loading, processing and visualizing graphs are available as functions.

Module

Description

Functions

Data

from_cs, save, load, load_netset, …

Topology

Connectivity and structure

get_connected_components, is_acyclic, …

Path

Shortest paths and distances

get_distances, get_shortest_path, …

Linear algebra

Matrix operations

normalize, diagonal_pseudo_inverse, …

Utils

Useful tools

directed2undirected, get_degrees, get_neighbors, …

Visualization

Visualization tools

svg_graph, svg_bigraphs, …

:

from sknetwork.data import karate_club
from sknetwork.utils import get_degrees

:

adjacency = karate_club()

:

get_degrees(adjacency)

:

array([16,  9, 10,  6,  3,  4,  4,  4,  5,  2,  3,  1,  2,  5,  2,  2,  2,
2,  2,  3,  2,  2,  2,  5,  3,  3,  2,  4,  3,  4,  4,  6, 12, 17],
dtype=int32)


### Machine learning

Scikit-network is suitable for machine learning on graphs.

Each algorithm is available as an object with some methods among the following:

• fit: fit the algorithm to the graph. This method is mandatory.

• predict: predict the output (e.g., labels of nodes).

• predict_proba: predict the output with probability (e.g., probability distribution over labels).

• transform: transform the graph.

• fit_predict: apply fit + predict.

• fit_predict_proba: apply fit + predict_proba.

• fit_transform: apply fit + transform.

The output is an attribute of the object with an underscore (e.g., labels_).

Module

Description

Algorithms

Output

Clustering

Form clusters of nodes

Louvain, PropagationClustering

labels_

Classification

Classify nodes

DiffusionClassifier, NNClassifier, …

labels_

GNN

Graph neural networks

GNNClassifier

labels_

Regression

Assign values to nodes

Diffusion, Dirichlet

values_

Hierarchy

Get a hierarchical representation of nodes

Paris, LouvainHierarchy

dendrogram_

Embedding

Get a vectorial representation of nodes

Spectral, SVD, LouvainEmbedding, …

embedding_

Ranking

Give importance scores to nodes

PageRank, Katz, Betweenness, …

scores_

NNLinker

links_

:

from sknetwork.data import karate_club
from sknetwork.classification import DiffusionClassifier

:

dataset = karate_club(metadata=True)
position = dataset.position
labels = dataset.labels

:

classifier = DiffusionClassifier()
classifier.fit(adjacency, {node: labels[node] for node in [0, 1, 33]})

:

DiffusionClassifier(n_iter=10, centering=True, scale=5)

:

labels_pred = classifier.predict()

:

SVG(svg_graph(adjacency, position, labels=labels_pred))

: :

probs = classifier.predict_proba()

:

scores = probs[:, 1]

:

SVG(svg_graph(adjacency, position, scores=scores))

: ## 4. Example

We here show how to use scikit-network to cluster a graph, initially stored in a text file as a list of edges.

### Data

:

# show first lines
with open('miserables.tsv', 'r') as f:
print(''.join(data[:5]))

Myriel  Napoleon
Myriel  Mlle Baptistine
Myriel  Mme Magloire
Myriel  Countess de Lo
Myriel  Geborand



:

from sknetwork.data import from_csv

:

graph = from_csv('miserables.tsv')

:

adjacency = graph.adjacency
names = graph.names

:

adjacency

:

<77x77 sparse matrix of type '<class 'numpy.int64'>'
with 508 stored elements in Compressed Sparse Row format>


### Embedding

We here compute a 2D embedding for visualization.

:

from sknetwork.embedding import Spring

:

algorithm = Spring()

:

position = algorithm.fit_transform(adjacency)

:

SVG(svg_graph(adjacency, position, names=names))

: ### Clustering

Finally, we cluster the graph by the Louvain algorithm.

:

from sknetwork.clustering import Louvain

:

algorithm = Louvain()

:

SVG(svg_graph(adjacency, position, names=names, labels=labels))

: ### Bipartite graphs

Observe that most algorithms apply to bipartite graphs, with the fit method applied to the biadjacency matrix. We show an example with a bipartite graph between movies and actors.

:

# show first lines
with open('movie_actor.tsv', 'r') as f:
print(''.join(data[:5]))

Inception       Leonardo DiCaprio
Inception       Marion Cotillard
Inception       Joseph Gordon Lewitt
The Dark Knight Rises   Marion Cotillard
The Dark Knight Rises   Joseph Gordon Lewitt


:

graph = from_csv('movie_actor.tsv', bipartite=True)

:

biadjacency = graph.biadjacency
movies = graph.names_row
actors = graph.names_col

:

algorithm = Louvain()

:

SVG(svg_bigraph(biadjacency, names_row=movies, names_col=actors, labels_row=labels_row, labels_col=labels_col))

: 