.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "auto_examples/gromov/plot_barycenter_fgw.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code. .. rst-class:: sphx-glr-example-title .. _sphx_glr_auto_examples_gromov_plot_barycenter_fgw.py: ================================= Plot graphs barycenter using FGW ================================= This example illustrates the computation barycenter of labeled graphs using FGW [18]. Requires networkx >=2 [18] Vayer Titouan, Chapel Laetitia, Flamary Rémi, Tavenard Romain and Courty Nicolas "Optimal Transport for structured data with application on graphs" International Conference on Machine Learning (ICML). 2019. .. GENERATED FROM PYTHON SOURCE LINES 18-23 .. code-block:: Python # Author: Titouan Vayer # # License: MIT License .. GENERATED FROM PYTHON SOURCE LINES 24-32 .. code-block:: Python import numpy as np import matplotlib.pyplot as plt import networkx as nx import math from scipy.sparse.csgraph import shortest_path import matplotlib.colors as mcol from matplotlib import cm from ot.gromov import fgw_barycenters .. GENERATED FROM PYTHON SOURCE LINES 33-131 .. code-block:: Python def find_thresh(C, inf=0.5, sup=3, step=10): """Trick to find the adequate thresholds from where value of the C matrix are considered close enough to say that nodes are connected The threshold is found by a linesearch between values "inf" and "sup" with "step" thresholds tested. The optimal threshold is the one which minimizes the reconstruction error between the shortest_path matrix coming from the thresholded adjacency matrix and the original matrix. Parameters ---------- C : ndarray, shape (n_nodes,n_nodes) The structure matrix to threshold inf : float The beginning of the linesearch sup : float The end of the linesearch step : integer Number of thresholds tested """ dist = [] search = np.linspace(inf, sup, step) for thresh in search: Cprime = sp_to_adjacency(C, 0, thresh) SC = shortest_path(Cprime, method="D") SC[SC == float("inf")] = 100 dist.append(np.linalg.norm(SC - C)) return search[np.argmin(dist)], dist def sp_to_adjacency(C, threshinf=0.2, threshsup=1.8): """Thresholds the structure matrix in order to compute an adjacency matrix. All values between threshinf and threshsup are considered representing connected nodes and set to 1. Else are set to 0 Parameters ---------- C : ndarray, shape (n_nodes,n_nodes) The structure matrix to threshold threshinf : float The minimum value of distance from which the new value is set to 1 threshsup : float The maximum value of distance from which the new value is set to 1 Returns ------- C : ndarray, shape (n_nodes,n_nodes) The threshold matrix. Each element is in {0,1} """ H = np.zeros_like(C) np.fill_diagonal(H, np.diagonal(C)) C = C - H C = np.minimum(np.maximum(C, threshinf), threshsup) C[C == threshsup] = 0 C[C != 0] = 1 return C def build_noisy_circular_graph( N=20, mu=0, sigma=0.3, with_noise=False, structure_noise=False, p=None ): """Create a noisy circular graph""" g = nx.Graph() g.add_nodes_from(list(range(N))) for i in range(N): noise = np.random.normal(mu, sigma, 1)[0] if with_noise: g.add_node(i, attr_name=math.sin((2 * i * math.pi / N)) + noise) else: g.add_node(i, attr_name=math.sin(2 * i * math.pi / N)) g.add_edge(i, i + 1) if structure_noise: randomint = np.random.randint(0, p) if randomint == 0: if i <= N - 3: g.add_edge(i, i + 2) if i == N - 2: g.add_edge(i, 0) if i == N - 1: g.add_edge(i, 1) g.add_edge(N, 0) noise = np.random.normal(mu, sigma, 1)[0] if with_noise: g.add_node(N, attr_name=math.sin((2 * N * math.pi / N)) + noise) else: g.add_node(N, attr_name=math.sin(2 * N * math.pi / N)) return g def graph_colors(nx_graph, vmin=0, vmax=7): cnorm = mcol.Normalize(vmin=vmin, vmax=vmax) cpick = cm.ScalarMappable(norm=cnorm, cmap="viridis") cpick.set_array([]) val_map = {} for k, v in nx.get_node_attributes(nx_graph, "attr_name").items(): val_map[k] = cpick.to_rgba(v) colors = [] for node in nx_graph.nodes(): colors.append(val_map[node]) return colors .. GENERATED FROM PYTHON SOURCE LINES 132-134 Generate data ------------- .. GENERATED FROM PYTHON SOURCE LINES 136-138 We build a dataset of noisy circular graphs. Noise is added on the structures by random connections and on the features by gaussian noise. .. GENERATED FROM PYTHON SOURCE LINES 138-149 .. code-block:: Python np.random.seed(30) X0 = [] for k in range(9): X0.append( build_noisy_circular_graph( np.random.randint(15, 25), with_noise=True, structure_noise=True, p=3 ) ) .. GENERATED FROM PYTHON SOURCE LINES 150-152 Plot data --------- .. GENERATED FROM PYTHON SOURCE LINES 154-170 .. code-block:: Python plt.figure(figsize=(8, 10)) for i in range(len(X0)): plt.subplot(3, 3, i + 1) g = X0[i] pos = nx.kamada_kawai_layout(g) nx.draw_networkx( g, pos=pos, node_color=graph_colors(g, vmin=-1, vmax=1), with_labels=False, node_size=100, ) plt.suptitle("Dataset of noisy graphs. Color indicates the label", fontsize=20) plt.show() .. image-sg:: /auto_examples/gromov/images/sphx_glr_plot_barycenter_fgw_001.png :alt: Dataset of noisy graphs. Color indicates the label :srcset: /auto_examples/gromov/images/sphx_glr_plot_barycenter_fgw_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 171-173 Barycenter computation ---------------------- .. GENERATED FROM PYTHON SOURCE LINES 175-176 Features distances are the euclidean distances .. GENERATED FROM PYTHON SOURCE LINES 176-189 .. code-block:: Python Cs = [shortest_path(nx.adjacency_matrix(x).toarray()) for x in X0] ps = [np.ones(len(x.nodes())) / len(x.nodes()) for x in X0] Ys = [ np.array([v for (k, v) in nx.get_node_attributes(x, "attr_name").items()]).reshape( -1, 1 ) for x in X0 ] lambdas = np.array([np.ones(len(Ys)) / len(Ys)]).ravel() sizebary = 15 # we choose a barycenter with 15 nodes A, C, log = fgw_barycenters(sizebary, Ys, Cs, ps, lambdas, alpha=0.95, log=True) .. GENERATED FROM PYTHON SOURCE LINES 190-192 Plot Barycenter ------------------------- .. GENERATED FROM PYTHON SOURCE LINES 194-200 .. code-block:: Python bary = nx.from_numpy_array( sp_to_adjacency(C, threshinf=0, threshsup=find_thresh(C, sup=100, step=100)[0]) ) for i, v in enumerate(A.ravel()): bary.add_node(i, attr_name=v) .. GENERATED FROM PYTHON SOURCE LINES 201-207 .. code-block:: Python pos = nx.kamada_kawai_layout(bary) nx.draw_networkx( bary, pos=pos, node_color=graph_colors(bary, vmin=-1, vmax=1), with_labels=False ) plt.suptitle("Barycenter", fontsize=20) plt.show() .. image-sg:: /auto_examples/gromov/images/sphx_glr_plot_barycenter_fgw_002.png :alt: Barycenter :srcset: /auto_examples/gromov/images/sphx_glr_plot_barycenter_fgw_002.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 1.598 seconds) .. _sphx_glr_download_auto_examples_gromov_plot_barycenter_fgw.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_barycenter_fgw.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_barycenter_fgw.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_barycenter_fgw.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_