<jupyter_start><jupyter_text>Traditional Methods for ML on Graphs<jupyter_code>try:
    # Check if GraKeL is installed:
    import grakel
except ImportError:
    # If GraKeL is not installed, install it.
    %pip install grakel==0.1.8
import itertools
import random
import time
from collections import defaultdict
from typing import Callable, Dict, List, Optional, Tuple, Union

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
def seed_everything(seed: Optional[int] = None) -> None:
    random.seed(seed)
    np.random.seed(seed)


seed_everything(42)
def features_example(
    feature_extraction_fun: Callable[[nx.Graph], Dict[Union[str, Tuple[str, str]], Union[int, float]]],
    fig_size: Tuple[int, int] = (6, 3),
    node_color: str = "tab:orange",
    node_size: int = 1000,
    width: int = 2,
    seed: Optional[int] = None,
) -> None:
    edge_list = [("A", "C"), ("B", "C"), ("B", "D"), ("C", "D"), ("D", "E"), ("D", "H"), ("E", "F"), ("E", "G")]
    G = nx.Graph(edge_list)
    name = feature_extraction_fun.__name__.replace("_", " ").capitalize()
    features = feature_extraction_fun(G)
    pos = nx.spring_layout(G, seed=seed)

    plt.figure(figsize=fig_size)
    nx.draw(G, pos=pos, node_color=node_color, node_size=node_size, width=width, with_labels=True)
    plt.show()

    print(f"\n{name} values:")
    for key, value in sorted(features.items(), key=lambda item: item[0]):
        print(f"- {key}: {value:.2f}")<jupyter_output><empty_output><jupyter_text>Node Features: Node Degree<jupyter_code>def node_degree(G: nx.Graph) -> Dict[str, int]:
    return dict(G.degree)
features_example(node_degree, seed=42)<jupyter_output><empty_output><jupyter_text>Node Centrality (1) Eigenvector centrality<jupyter_code>features_example(nx.eigenvector_centrality, seed=42)<jupyter_output><empty_output><jupyter_text>Node Centrality (2) Betweenness centrality<jupyter_code>features_example(nx.betweenness_centrality, seed=42)<jupyter_output><empty_output><jupyter_text>Node Centrality (3) Closeness centrality<jupyter_code>features_example(nx.closeness_centrality, seed=42)<jupyter_output><empty_output><jupyter_text>Node Features: Clustering Coefficient<jupyter_code>features_example(nx.clustering, seed=42)<jupyter_output><empty_output><jupyter_text>Node Features: Graphlets<jupyter_code>def plot_graph(
    G: nx.Graph,
    root: str,
    graphlet_nodes: set = set(),
    node_size: int = 1000,
    width: int = 2,
    seed: Optional[int] = None,
) -> None:
    colors = {node: "tab:gray" for node in graphlet_nodes}
    colors[root] = "tab:red"
    node_color = [colors.get(node, "white") for node in G.nodes()]
    edgecolors = ["none" if node == root else "black" for node in G.nodes()]
    labels = {node: node if node == root else "" for node in G.nodes()}
    pos = nx.spring_layout(G, seed=seed)
    nx.draw(G, pos=pos, node_color=node_color, edgecolors=edgecolors, labels=labels, node_size=node_size, width=width)


def add_is_root_attr(G: nx.Graph, root: str) -> nx.Graph:
    is_root = {node: {"is_root": node == root} for node in G.nodes}
    nx.set_node_attributes(G, is_root)<jupyter_output><empty_output><jupyter_text>Possibile graphlets up to size 3<jupyter_code>edge_list = [("u", "B"), ("u", "C"), ("B", "C"), ("B", "D"), ("C", "E")]
G = nx.Graph(edge_list)
add_is_root_attr(G, "u")
possible_graphlets_up_to_size_3 = {
    "a": nx.Graph([("a", "B")]),
    "b": nx.Graph([("b", "B"), ("b", "C"), ("B", "C")]),
    "c": nx.Graph([("c", "B"), ("c", "C")]),
    "d": nx.Graph([("B", "d"), ("B", "C")]),
}
for root, possible_graphlet in possible_graphlets_up_to_size_3.items():
    add_is_root_attr(possible_graphlet, root)


plt.figure(figsize=(4, 3))
plot_graph(G, "u")
plt.title("Example:", fontsize=24)
plt.show()

plt.figure(figsize=(12, 4))

for idx, (root, graphlet) in enumerate(possible_graphlets_up_to_size_3.items(), 1):
    plt.subplot(1, 4, idx)
    plt.title(root, fontsize=24)
    plot_graph(graphlet, root, node_size=500)

plt.suptitle("Possibile graphlets up to size 3", fontsize=24)
plt.subplots_adjust(top=0.75)
plt.show()<jupyter_output><empty_output><jupyter_text>Graphlet instances of node u<jupyter_code>def _node_match(n1: Dict[str, bool], n2: Dict[str, bool]) -> bool:
    return n1["is_root"] and n2["is_root"] or not n1["is_root"] and not n2["is_root"]


def get_graphlet_instances(
    G: nx.Graph, node: str, possible_graphlets: Dict[str, nx.Graph], max_size: int = 3
) -> Dict[str, List[nx.Graph]]:
    graphlet_instances = defaultdict(list)
    for size in range(2, max_size + 1):
        for combination in itertools.combinations(G.nodes, size):
            if node in combination:
                subgraph = nx.subgraph(G, combination)
                if nx.is_connected(subgraph):
                    for key, graphlet in possible_graphlets.items():
                        if nx.is_isomorphic(subgraph, graphlet, node_match=_node_match):
                            graphlet_instances[key].append(subgraph)
                            break

    return dict(graphlet_instances)
graphlet_instances = get_graphlet_instances(G, "u", possible_graphlets_up_to_size_3)
num_rows = max(len(graphlets) for graphlets in graphlet_instances.values())
num_cols = len(possible_graphlets_up_to_size_3)

plt.figure(figsize=(12, 6))
for col_idx, key in enumerate(sorted(possible_graphlets_up_to_size_3.keys())):
    graphlets = graphlet_instances.get(key, {})
    for row_idx, graphlet in enumerate(graphlets):
        plt.subplot(num_rows, num_cols, row_idx * num_cols + col_idx + 1)
        plot_graph(G, "u", graphlet.nodes, node_size=500, seed=42)
        if row_idx == 0:
            plt.title(key, fontsize=24)

plt.suptitle("Graphlet instances of node u", fontsize=24)
plt.subplots_adjust(top=0.80)
plt.show()<jupyter_output><empty_output><jupyter_text>Graph Degree Vector (GDV) of node u<jupyter_code>def get_graph_degree_vector(G: nx.Graph, root: str, possible_graphlets: Dict[str, nx.Graph]) -> List[int]:
    graphlet_instances = get_graphlet_instances(G, "u", possible_graphlets)
    out = []
    for key in sorted(possible_graphlets.keys()):
        out.append(len(graphlet_instances.get(key, [])))

    return out
gdv = get_graph_degree_vector(G, "u", possible_graphlets_up_to_size_3)

print(f"GDV of a node u: {gdv}")<jupyter_output>GDV of a node u: [2, 1, 0, 2]<jupyter_text>Link-Level Features: Overview  Distance-Based Features Shortest-path distance between two nodes<jupyter_code>def shortest_path_length(G: nx.Graph) -> Dict[Tuple[str, str], int]:
    out = {}
    for node_pair in itertools.combinations(G.nodes, 2):
        out[node_pair] = nx.shortest_path_length(G, *node_pair)

    return out
features_example(shortest_path_length, seed=42)<jupyter_output><empty_output><jupyter_text>Local Neighborhood Overlap  Common neighbors<jupyter_code>def num_common_neighbors(G: nx.Graph) -> Dict[Tuple[str, str], int]:
    return {edge: len(list((nx.common_neighbors(G, *edge)))) for edge in itertools.combinations(G.nodes, 2)}
features_example(num_common_neighbors, seed=42)<jupyter_output><empty_output><jupyter_text>Jaccard's coefficient<jupyter_code>def jaccard_coefficient(G: nx.Graph) -> Dict[Tuple[str, str], float]:
    out = {}
    for item in nx.jaccard_coefficient(G, itertools.combinations(G.nodes, 2)):
        out[(item[:2])] = item[2]

    return out
features_example(jaccard_coefficient, seed=42)<jupyter_output><empty_output><jupyter_text>Adamic-Adar index<jupyter_code>def adamic_adar_index(G: nx.Graph) -> Dict[Tuple[str, str], float]:
    out = {}
    for item in nx.adamic_adar_index(G, itertools.combinations(G.nodes, 2)):
        out[(item[:2])] = item[2]

    return out
features_example(adamic_adar_index, seed=42)<jupyter_output><empty_output><jupyter_text>Global Neighborhood Overlap<jupyter_code>def get_katz_index_matrix(G: nx.Graph, beta: float) -> np.ndarray:
    A = nx.adjacency_matrix(G).todense()
    X = beta * A
    max_eigval = np.linalg.eigvals(X).max()
    if max_eigval >= 1.0:
        raise ValueError(
            "to apply the geometric series of matrices, the maximum eigenvalue of beta * A must be < 1, got "
            f"{max_eigval}"
        )

    I = np.eye(X.shape[0])
    S = np.linalg.inv(I - X) - I
    return S


def katz_index_beta_03(G: nx.Graph) -> Dict[Tuple[str, str], float]:
    S = get_katz_index_matrix(G, 0.3)
    nodes = list(G.nodes)
    ki = {}
    for node_pair in itertools.combinations(G.nodes, 2):
        row_idx = nodes.index(node_pair[0])
        col_idx = nodes.index(node_pair[1])
        ki[node_pair] = S[row_idx, col_idx]

    return ki


katz_index_beta_03.__name__ = "katz_index_(beta=0.3)"
features_example(katz_index_beta_03, seed=42)<jupyter_output><empty_output><jupyter_text>Graph-Level Features: Overview > The following part is an adaptation of a [tutorial](https://github.com/ysig/GraKeL/blob/master/tutorials/digit_classification/digit_classification.ipynb) from the [GraKeL](https://ysig.github.io/GraKeL/0.1a8/) library<jupyter_code>import grakel
from grakel.kernels import GraphletSampling, WeisfeilerLehman
from sklearn.datasets import load_digits
from sklearn.metrics import accuracy_score
from sklearn.svm import SVC
digits = load_digits()
images = digits.images
y = digits.target

for i in range(4):
    plt.subplot(1, 4, i + 1)
    plt.imshow(images[i], cmap=plt.cm.gray_r, interpolation="nearest")
    plt.title(f"Target: {y[i]}")
    plt.axis("off")
def images_to_graphs(images: np.ndarray) -> List[grakel.Graph]:
    num_images, height, width = images.shape
    graphs = []
    edges = []
    edge_labels = {}
    for row_idx in range(height):
        for col_idx in range(width):
            if col_idx < width - 1:
                edge = (row_idx * height + col_idx, row_idx * height + col_idx + 1)
                edges.append(edge)
                edge_labels[edge] = 1

            if row_idx < height - 1:
                edge = (row_idx * height + col_idx, (row_idx + 1) * height + col_idx)
                edges.append(edge)
                edge_labels[edge] = 2

    for image_idx in range(num_images):
        node_labels = dict()
        for row_idx in range(height):
            for col_idx in range(width):
                node_labels[row_idx * height + col_idx] = int(images[image_idx, row_idx, col_idx] / 4)

        graphs.append(grakel.Graph(edges, node_labels=node_labels, edge_labels=edge_labels))

    return graphs
graphs = images_to_graphs(images)

print("Splitting dataset into train/test (1000/100 instances)")
graphs_train, graphs_test = graphs[:1000], graphs[1000:1100]
y_train, y_test = y[:1000], y[1000:1100]<jupyter_output>Splitting dataset into train/test (1000/100 instances)<jupyter_text>Graphlet Kernel<jupyter_code>start_time = time.perf_counter()

gk = GraphletSampling(k=3)
K_train = gk.fit_transform(graphs_train)
K_test = gk.transform(graphs_test)

clf = SVC(kernel="precomputed")
clf.fit(K_train, y_train)

y_pred = clf.predict(K_test)

print(f"Classification accuracy: {accuracy_score(y_test, y_pred):.2f}")
print(f"Duration: {time.perf_counter() - start_time:.2f} s")<jupyter_output>Classification accuracy: 0.09
Duration: 26.17 s<jupyter_text>Weisfeiler-Lehman Kernel<jupyter_code>start_time = time.perf_counter()

gk = WeisfeilerLehman(n_iter=5)
K_train = gk.fit_transform(graphs_train)
K_test = gk.transform(graphs_test)

clf = SVC(kernel="precomputed")
clf.fit(K_train, y_train)

y_pred = clf.predict(K_test)

print(f"Classification accuracy: {accuracy_score(y_test, y_pred):.2f}")
print(f"Duration: {time.perf_counter() - start_time:.2f} s")<jupyter_output>Classification accuracy: 0.83
Duration: 1.81 s
{'fraction_non_alphanumeric': 0.13946893529260118, 'fraction_numerical': 0.016928761708344075, 'mean_word_length': 4.552480916030534, 'pattern_counts': {'":': 5, '<': 72, '<?xml version=': 0, '>': 86, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '18', 'dir': 'jupyter-structured-clean-dedup', 'id': '75305', 'license': 'MIT', 'n_tokens_mistral': 4487, 'n_tokens_neox': 4268, 'n_words': 861, 'path': 'notebooks/02-traditional-methods-for-ml-on-graphs.ipynb', 'repo_name': 'mnslarcher/cs224w-slides-to-code', 'size': '11637'}