{ "cells": [ { "cell_type": "markdown", "id": "87d91a42", "metadata": {}, "source": [ "# Align all and Compute for Graphs\n", "\n", "$\\textbf{Lead Author: Anna Calissano}$" ] }, { "cell_type": "markdown", "id": "0e4098a0", "metadata": {}, "source": [ "Dear learner, \n", "\n", "the aim of the current notebook is to introduce the align all and compute as a learning method for graphs. The align all and compute allows to estimate the Frechet Mean, the Generalized Geodesic Principal Components and the Regression. In this notebook you will learn how use all the learning methods." ] }, { "cell_type": "code", "execution_count": 1, "id": "319481d6", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "INFO: Using numpy backend\n" ] } ], "source": [ "import random\n", "\n", "import networkx as nx\n", "\n", "import geomstats.backend as gs\n", "\n", "from geomstats.geometry.symmetric_matrices import MatricesMetric as SymmetricMatricesMetric\n", "from geomstats.geometry.stratified.graph_space import GraphSpace\n", "from geomstats.learning.aac import AAC\n", "\n", "gs.random.seed(2020)" ] }, { "cell_type": "markdown", "id": "e476384d", "metadata": {}, "source": [ "Let's start by creating simulated data using `networkx`." ] }, { "cell_type": "code", "execution_count": 2, "id": "5d2c46cb", "metadata": {}, "outputs": [], "source": [ "graphset_1 = gs.array([nx.to_numpy_array(nx.erdos_renyi_graph(n=5, p=0.6, directed=True)) for i in range(10)])\n", "graphset_2 = gs.array([nx.to_numpy_array(nx.erdos_renyi_graph(n=5, p=0.6, directed=True)) for i in range(100)])\n", "graphset_3 = gs.array([nx.to_numpy_array(nx.erdos_renyi_graph(n=3, p=0.6, directed=True)) for i in range(1000)])" ] }, { "cell_type": "markdown", "id": "d766dd07", "metadata": {}, "source": [ "### A primer in space, metric and aligners" ] }, { "cell_type": "markdown", "id": "e0e65cec", "metadata": {}, "source": [ "The first step is to create the embedding space. By default, it comes equipped with a metric." ] }, { "cell_type": "code", "execution_count": 3, "id": "bade9271", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space = GraphSpace(n_nodes=5)\n", "\n", "graph_space.metric" ] }, { "cell_type": "markdown", "id": "36336c04", "metadata": {}, "source": [ "By default, the space also comes with a total space (`Matrices`), which in turn comes equipped with a matrix (`MatricesMetric`)." ] }, { "cell_type": "code", "execution_count": 4, "id": "9f0f2adb", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space.total_space.metric" ] }, { "cell_type": "markdown", "id": "305a7bf9", "metadata": {}, "source": [ "(`total_metric` can also be accessed from metric: `graph_space.metric.total_space_metric`.)" ] }, { "cell_type": "markdown", "id": "fdcf2f32", "metadata": {}, "source": [ "The default aligner is 'ID' (identity), which means the graphs are not permuted. To set 'FAQ', do:" ] }, { "cell_type": "code", "execution_count": 5, "id": "aa8debc7", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space.metric.set_aligner('FAQ')" ] }, { "cell_type": "markdown", "id": "a8656a77", "metadata": {}, "source": [ "With the FAQ alignment and the default Frobenious norm, we match two graphs and a set of graphs to a base graph:" ] }, { "cell_type": "code", "execution_count": 6, "id": "4074d7e9", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[[0., 1., 1., 1., 0.],\n", " [0., 0., 1., 1., 1.],\n", " [1., 0., 0., 0., 0.],\n", " [1., 1., 1., 0., 0.],\n", " [1., 0., 1., 1., 0.]],\n", "\n", " [[0., 1., 1., 1., 1.],\n", " [0., 0., 1., 0., 0.],\n", " [0., 0., 0., 1., 1.],\n", " [0., 1., 1., 0., 0.],\n", " [1., 0., 1., 1., 0.]]])" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_permuted = graph_space.metric.align_point_to_point(base_graph=graphset_1[0], graph_to_permute=graphset_1[1])\n", "\n", "graph_space.metric.align_point_to_point(base_graph= graphset_1[0], graph_to_permute =graphset_1[1:3])" ] }, { "cell_type": "markdown", "id": "5d7bfb1e", "metadata": {}, "source": [ "To compute the distance we can either call the distance function:" ] }, { "cell_type": "code", "execution_count": 7, "id": "abe70991", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2.0" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space.metric.dist(graphset_1[0], graphset_1[1])" ] }, { "cell_type": "markdown", "id": "440de4b1", "metadata": {}, "source": [ "Or, if the matching has been already run, we can use the identity matcher in the distance, to avoid computing the matching twice:" ] }, { "cell_type": "code", "execution_count": 8, "id": "8fb68953", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2.0" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space.metric.set_aligner('ID')\n", "\n", "graph_space.metric.dist(graphset_1[0], graph_permuted)" ] }, { "cell_type": "markdown", "id": "f113cc4b", "metadata": {}, "source": [ "Alternatively, use can use the total space metric instead." ] }, { "cell_type": "code", "execution_count": 9, "id": "3b32bc9d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2.0" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space.metric.total_space_metric.dist(graphset_1[0], graph_permuted)" ] }, { "cell_type": "markdown", "id": "feecf768", "metadata": {}, "source": [ "We can change the total space metric by doing:" ] }, { "cell_type": "code", "execution_count": 10, "id": "e67645dd", "metadata": {}, "outputs": [], "source": [ "graph_space.total_space.equip_with_metric(SymmetricMatricesMetric)" ] }, { "cell_type": "markdown", "id": "aefc53f6", "metadata": {}, "source": [ "For the point to geodesic aligner, there's no default set. In fact, if you try something like `graph_space.metric.align_point_to_geodesic(geodesic, point)`, a (hopefully) meaningful error will be raised, explaining how to set the point to geodesic aligner." ] }, { "cell_type": "code", "execution_count": 11, "id": "242626c0", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space.metric.set_point_to_geodesic_aligner(\"default\", s_min=-1., s_max=1., n_points=10)" ] }, { "cell_type": "code", "execution_count": 12, "id": "488ff262", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.0" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "init_point, end_point = graph_space.random_point(2)\n", "\n", "geodesic_func = graph_space.metric.geodesic(init_point, end_point)\n", "\n", "aligned_init_point = graph_space.metric.align_point_to_geodesic(geodesic_func, init_point)\n", "\n", "graph_space.metric.total_space_metric.dist(init_point, aligned_init_point)" ] }, { "cell_type": "markdown", "id": "18fe3623", "metadata": {}, "source": [ "This short introduction should be enough to set you up for experimenting with the learning algorithms on graphs." ] }, { "cell_type": "markdown", "id": "7dc0c7a5", "metadata": {}, "source": [ "### Frechet Mean\n", "Reference: Calissano, A., Feragen, A., & Vantini, S. (2020). Populations of unlabeled networks: Graph space geometry and geodesic principal components. MOX Report.\n", "\n", "Given $\\{[X_1], \\dots, [X_k]\\}, [x_i] \\in X/T$, we estimate the Frechet Mean using AAC consisting on two steps:\n", "1. Compute $\\hat{X}$ as arithmetic mean of $\\{X_1, \\dots, X_k\\}, X_i \\in X$ \n", "2. Using graph to graph alignment to find $\\{X_1, \\dots, X_k\\}, X_i \\in X$ optimally aligned with $\\hat{X}$" ] }, { "cell_type": "markdown", "id": "cfbe01a3", "metadata": {}, "source": [ "Let's instantiate the graph space and set the aligner." ] }, { "cell_type": "code", "execution_count": 13, "id": "e1b4b3d1", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space = GraphSpace(n_nodes=5)\n", "\n", "graph_space.metric.set_aligner('FAQ')" ] }, { "cell_type": "markdown", "id": "fa8ede70", "metadata": {}, "source": [ "And now create the estimator, and fit the data." ] }, { "cell_type": "code", "execution_count": 14, "id": "5073938a", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "WARNING: Maximum number of iterations 20 reached. The estimate may be inaccurate\n" ] }, { "data": { "text/plain": [ "array([[0. , 0.83, 0.66, 0.56, 0.63],\n", " [0.63, 0. , 0.82, 0.77, 0.2 ],\n", " [0.73, 0.95, 0. , 0.95, 0.7 ],\n", " [0.15, 0.62, 0.4 , 0. , 0.23],\n", " [0.05, 0.81, 0.56, 0.75, 0. ]])" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "aac_fm = AAC(estimate='frechet_mean', metric=graph_space.metric)\n", "\n", "fm = aac_fm.fit(graphset_2)\n", "\n", "fm.estimate_" ] }, { "cell_type": "markdown", "id": "83e636a5", "metadata": {}, "source": [ "### Principal Components\n", "Reference: Calissano, A., Feragen, A., & Vantini, S. (2020). Populations of unlabeled networks: Graph space geometry and geodesic principal components. MOX Report.\n", "\n", "We estimate the Generalized Geodesics Principal Components Analysis (GGPCA) using AAC. Given $\\{[X_1], \\dots, [X_k]\\}, (s_i,[X_i]) \\in X/T $ we are searching for:\n", "$$\\gamma: \\mathbb{R}\\rightarrow X/T$$ generalized geodesic principal component capturing the majority of the variability of the dataset. The AAC for ggpca works in two steps: \n", "\n", "1. finding $\\delta: \\mathbb{R}\\rightarrow X$ principal component in the set of adjecency matrices $\\{X_1, \\dots, X_k\\}, X_i \\in X$ \n", "2. finding $\\{X_1, \\dots, X_k\\}, X_i \\in X$ as optimally aligned with respect to $\\gamma$. The estimation required a point to geodesic aligment defined in the metric." ] }, { "cell_type": "markdown", "id": "1386fe6c", "metadata": {}, "source": [ "As before:" ] }, { "cell_type": "code", "execution_count": 15, "id": "c51dea7f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space = GraphSpace(n_nodes=5)\n", "\n", "graph_space.metric.set_aligner('FAQ')" ] }, { "cell_type": "markdown", "id": "7d2c0141", "metadata": {}, "source": [ "For GGPCA, we also need to set the pont to geodesic aligner." ] }, { "cell_type": "code", "execution_count": 16, "id": "41c11987", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space.metric.set_point_to_geodesic_aligner('default', s_min=0, s_max=2)" ] }, { "cell_type": "markdown", "id": "9754a5aa", "metadata": {}, "source": [ "Again, create the estimator and fit the data." ] }, { "cell_type": "code", "execution_count": 17, "id": "434fef57", "metadata": { "scrolled": true }, "outputs": [], "source": [ "aac_ggpca = AAC(estimate='ggpca', metric=graph_space.metric, n_components=2)\n", "\n", "aac_ggpca.fit(graphset_3);" ] }, { "cell_type": "markdown", "id": "7c85724c", "metadata": {}, "source": [ "## Regression\n", "Reference: Calissano, A., Feragen, A., & Vantini, S. (2022). Graph-valued regression: Prediction of unlabelled networks in a non-Euclidean graph space. Journal of Multivariate Analysis, 190, 104950.\n", "\n", "We estimate a graph-to-value regression model to predict graph from scalar or vectors. Given $\\{(s_1,[X_1]), \\dots, (s_k, [X_k])\\}, (s_i,[X_i]) \\in \\mathbb{R}^p\\times X/T $ we are searching for:\n", "$$f: \\mathbb{R}^p\\rightarrow X/T$$\n", "where $f\\in \\mathcal{F}(X/T)$ is a generalized geodesic regression model, i.e., the canonical projection onto Graph Space of a regression line $h_\\beta : \\mathbb{R}^p\\rightarrow X$ of the form $$h_\\beta(s) = \\sum_{j=1}^{p} \\beta_i s_i$$\n", "The AAC algorithm for regression combines the estimation of $h_\\beta$ given $\\{X_1, \\dots, X_k\\}, X_i \\in X$\n", "$$\\sum_{i=0}^{k} d_X(h_\\beta(s_i), X_i)$$\n", "and the searching for $\\{X_1, \\dots, X_k\\}, X_i \\in X$ optimally aligned with respect to the prediction along the current regression model:\n", "$$\\min_{t\\in T}d_X(h_\\beta(s_i),t^TX_it)$$" ] }, { "cell_type": "code", "execution_count": 18, "id": "893da39b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_space = GraphSpace(n_nodes=5)\n", "\n", "graph_space.metric.set_aligner('FAQ')" ] }, { "cell_type": "code", "execution_count": 19, "id": "6f33d152", "metadata": {}, "outputs": [], "source": [ "s = gs.array([random.randint(0,10) for i in range(10)])" ] }, { "cell_type": "code", "execution_count": 20, "id": "a4cb1e48", "metadata": {}, "outputs": [], "source": [ "aac_reg = AAC(estimate='regression', metric=graph_space.metric)" ] }, { "cell_type": "code", "execution_count": 21, "id": "0a2152ae", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "WARNING: Maximum number of iterations 20 reached. The estimate may be inaccurate\n" ] } ], "source": [ "aac_reg.fit(s, graphset_1);" ] }, { "cell_type": "markdown", "id": "46835c03", "metadata": {}, "source": [ "The coefficients are saved in the following attributes and they can be changed into a graph shape." ] }, { "cell_type": "code", "execution_count": 22, "id": "9b71203c", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[-0. ],\n", " [-0.10691824],\n", " [-0.03459119],\n", " [-0.03773585],\n", " [-0. ],\n", " [ 0.02515723],\n", " [-0. ],\n", " [-0.05345912],\n", " [ 0.01886792],\n", " [ 0.10377358],\n", " [ 0.13836478],\n", " [-0. ],\n", " [-0. ],\n", " [-0.04716981],\n", " [-0.05660377],\n", " [-0.00628931],\n", " [-0.01257862],\n", " [-0.10377358],\n", " [-0. ],\n", " [-0.02830189],\n", " [-0.04402516],\n", " [ 0.1163522 ],\n", " [-0. ],\n", " [-0. ],\n", " [-0. ]])" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "aac_reg.total_space_estimator.coef_" ] }, { "cell_type": "markdown", "id": "874fefa2", "metadata": {}, "source": [ "A graph can be predicted using the fit model and the corresponding prediction error can be computed:" ] }, { "cell_type": "code", "execution_count": 23, "id": "b03476b8", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "18.529577862561773" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_pred = aac_reg.total_space_estimator.predict(s)\n", "\n", "gs.sum(graph_space.metric.dist(graphset_1, graph_pred))" ] } ], "metadata": { "backends": [ "numpy" ], "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.15" } }, "nbformat": 4, "nbformat_minor": 5 }