Graph classification on a randomly generated dataset of Erdos-Renyi graphs.

Script makes use of grakelx.Graph and grakelx.ShortestPath

from __future__ import print_function

print(__doc__)


from random import random

from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC

from grakelx import Graph
from grakelx.kernels import ShortestPath

# Generates 3 sets of Erdos-Renyi graphs. Each edge is included in the graph with probability p
# independent from every other edge. The probability p is set equal to 0.25, 0.5 and 0.75 for
# the graphs of the 1st, 2nd and 3rd set, respectivery
Gs = list()
y = list()
probs = [0.25, 0.5, 0.75]
for i in range(len(probs)):
    for j in range(5, 35):
        edges = list()
        for n1 in range(j):
            for n2 in range(n1 + 1, j):
                if random() <= probs[i]:
                    edges.append((n1, n2))
                    edges.append((n2, n1))

        Gs.append(Graph(edges))
        y.append(i)

# Splits the dataset into a training and a test set
G_train, G_test, y_train, y_test = train_test_split(Gs, y, test_size=0.1, random_state=42)

# Uses the shortest path kernel to generate the kernel matrices
gk = ShortestPath(normalize=True, with_labels=False)
K_train = gk.fit_transform(G_train)
K_test = gk.transform(G_test)

# Uses the SVM classifier to perform classification
clf = SVC(kernel="precomputed")
clf.fit(K_train, y_train)
y_pred = clf.predict(K_test)

# Computes and prints the classification accuracy
acc = accuracy_score(y_test, y_pred)
print("Accuracy:", str(round(acc * 100, 2)) + "%")