Source code for geomstats.geometry.stratified.graph_space

"""Graph Space.

Lead author: Anna Calissano.
"""

import functools
import itertools
from abc import ABCMeta, abstractmethod

import networkx as nx
import scipy

import geomstats.backend as gs
from geomstats.errors import check_parameter_accepted_values
from geomstats.geometry.matrices import Matrices
from geomstats.geometry.stratified.point_set import (
    Point,
    PointSet,
    PointSetMetric,
    _vectorize_point,
)


def _pad_graph_points_with_zeros(points, n_nodes, copy=False):
    """Pad graphs point with zeros.

    Graph space is an embedding for adjacency matrices of the same dimension. Smaller
    graphs can be padded adding zero nodes and edges, i.e., block of zero rows and
    columns.

    Parameters
    ----------
    points : GraphPoint
        Graph of the original dimension to be augmented.
    n_nodes : int
        A positive number representing the number of desired nodes.

    Returns
    -------
    points : GraphPoint
        Set of Graphs with the new number of nodes.
    """
    if type(points) is GraphPoint:
        if copy:
            points = GraphPoint(points.adj)

        n = n_nodes - points.n_nodes
        if n > 0:
            points.adj = gs.pad(points.adj, [[0, n], [0, n]])
    else:
        points = [
            _pad_graph_points_with_zeros(point, n_nodes, copy=copy) for point in points
        ]

    return points


def _pad_array_with_zeros(array, n_nodes):
    """Pad graphs represented as array with zeros.

    Graph space is an embedding for adjacency matrices of the same dimension. Smaller
    graphs can be padded adding zero nodes and edges, i.e., block of zero rows and
    columns.

    Parameters
    ----------
    array : array-like, shape=[..., n_original_nodes, n_original_nodes]
        Adjacency matrices of the original dimension to be augmented.
    n_nodes : int
        A positive number representing the number of desired nodes.

    Returns
    -------
    array : array-like, shape=[..., n_nodes, n_nodes]
        Set of adjacency matrices with the new number of nodes.
    """
    if array.shape[-1] < n_nodes:
        n = n_nodes - array.shape[-1]
        paddings = [[0, 0]] + [[0, n]] * 2 if array.ndim > 2 else [[0, n]] * 2
        array = gs.pad(array, paddings)

    return array


def _pad_points_with_zeros(points, n_nodes, copy=True):
    """Pad graphs with zeros.

    Graph space is an embedding for adjacency matrices of the same dimension.
    Smaller graphs can be padded adding zero nodes and edges, i.e., block of
    zero rows and columns.

    Parameters
    ----------
    points : array-like, shape=[..., n_original_nodes, n_original_nodes] or GraphPoint
        Adjacency matrices or GraphPoint of the original dimension to be augmented.
    n_nodes : int
        A positive number representing the number of desired nodes.

    Returns
    -------
    array : array-like, shape=[..., n_nodes, n_nodes] or GraphPoint
        Set of adjacency matrices or GraphPoint with the new number of nodes.
    """
    if type(points) in [list, tuple, GraphPoint]:
        points = _pad_graph_points_with_zeros(points, n_nodes, copy=copy)
    else:
        points = _pad_array_with_zeros(points, n_nodes)

    return points


def _vectorize_graph(*args_positions):
    """Vectorize GraphPoint or array into array.

    Turns GraphPoint or array into an array of adjacency matrices. This way all
    the methods only need to work for the set of points case (output shape
    should be returned accordingly to the input though).

    Parameters
    ----------
    points : array-like, shape=[..., n_nodes, n_nodes] or GraphPoint
        Adjacency matrix or GraphPoint.

    Returns
    -------
    array : array-like, shape=[..., n_nodes,  n_nodes]
        Array of vectorized adjacency matrices.
    """

    def _manipulate_input(arg):
        if type(arg) not in [list, tuple, GraphPoint]:
            return arg

        if type(arg) is GraphPoint:
            return arg.adj

        return gs.array([graph.adj for graph in arg])

    return _vectorize_point(*args_positions, manipulate_input=_manipulate_input)


def _vectorize_graph_to_points(*args_positions):
    """Vectorize GraphPoint or array into a list of GraphPoint.

    This way all the methods only need to work for the set of points case (output
    shape should be returned accordingly to the input though).

    Parameters
    ----------
    points : array-like, shape=[..., n_nodes, n_nodes] or GraphPoint
        Adjacency matrix or GraphPoint.

    Returns
    -------
    graph-set : list of GraphPoint points, shape=[...]
        List of GraphPoint.
    """

    def _manipulate_input(arg):
        if type(arg) in [list, tuple]:
            return arg

        if type(arg) is GraphPoint:
            return [arg]

        if arg.ndim == 2:
            return [GraphPoint(arg)]

        return [GraphPoint(point) for point in arg]

    return _vectorize_point(*args_positions, manipulate_input=_manipulate_input)


def _pad_with_zeros(*args_positions, copy=True):
    """Pad graphs with zeros."""

    def _dec(func):
        def _manipulate_input(points, n_nodes):
            return _pad_points_with_zeros(points, n_nodes, copy=copy)

        @functools.wraps(func)
        def _wrapped(*args, **kwargs):
            args = list(args)

            n_nodes = args[0].n_nodes
            for pos, name in args_positions:
                if name in kwargs:
                    kwargs[name] = _manipulate_input(kwargs[name], n_nodes)
                else:
                    args[pos] = _manipulate_input(args[pos], n_nodes)

            return func(*args, **kwargs)

        return _wrapped

    return _dec


class _BaseAligner(metaclass=ABCMeta):
    """Base class for point to point aligner.

    Attributes
    ----------
    perm_ : array-like, shape=[..., n_nodes]
        Node permutations where in position i we have the value j meaning
        the node i should be permuted with node j.
    """

    def __init__(self):
        self.perm_ = None

    @abstractmethod
    def align(self, space, base_graph, graph_to_permute):
        """Align graphs.

        Parameters
        ----------
        space : GraphSpace
        base_graph : array-like, shape=[..., n_nodes, n_nodes]
            Base graph.
        graph_to_permute : array-like, shape=[..., n_nodes, n_nodes]
            Graph to align.

        Returns
        -------
        permuted_graph : array-like, shape=[..., n_nodes, n_nodes]
            Permuted graph as to be aligned with respect to the geodesic.
        """
        raise NotImplementedError("Not implemented")

    def _broadcast(self, base_graph, graph_to_permute):
        base_graph, graph_to_permute = gs.broadcast_arrays(base_graph, graph_to_permute)
        is_single = gs.ndim(base_graph) == 2
        if is_single:
            base_graph = gs.expand_dims(base_graph, 0)
            graph_to_permute = gs.expand_dims(graph_to_permute, 0)

        return base_graph, graph_to_permute, is_single

    def _permute(self, space, graph_to_permute, perm):
        return space.permute(graph_to_permute, perm)


[docs] class FAQAligner(_BaseAligner): """Fast Quadratic Assignment for graph matching (or network alignment). References ---------- .. [Vogelstein2015] Vogelstein JT, Conroy JM, Lyzinski V, Podrazik LJ, Kratzer SG, Harley ET, Fishkind DE, Vogelstein RJ, Priebe CE. “Fast approximate quadratic programming for graph matching.“ PLoS One. 2015 Apr 17; doi: 10.1371/journal.pone.0121002. """
[docs] def align(self, space, base_graph, graph_to_permute): """Align graphs. Parameters ---------- space : GraphSpace base_graph : array-like, shape=[..., n_nodes, n_nodes] Base graph. graph_to_permute : array-like, shape=[..., n_nodes, n_nodes] Graph to align. Returns ------- permuted_graph : array-like, shape=[..., n_nodes, n_nodes] Permuted graph as to be aligned with respect to the geodesic. """ base_graph, graph_to_permute, is_single = self._broadcast( base_graph, graph_to_permute ) perm = [ gs.linalg.quadratic_assignment(x, y, options={"maximize": True}) for x, y in zip(base_graph, graph_to_permute) ] self.perm_ = gs.array(perm[0]) if is_single else gs.array(perm) return self._permute(space, graph_to_permute, self.perm_)
[docs] class IDAligner(_BaseAligner): """Identity alignment. The identity alignment is not performing any matching but returning the nodes in their original position. This alignment can be selected when working with labelled graphs. """
[docs] def align(self, space, base_graph, graph_to_permute): """Align graphs. Parameters ---------- space : GraphSpace base_graph : array-like, shape=[..., n_nodes, n_nodes] Base graph. graph_to_permute : array-like, shape=[..., n_nodes, n_nodes] Graph to align. Returns ------- permuted_graph : array-like, shape=[..., n_nodes, n_nodes] Permuted graph as to be aligned with respect to the geodesic. """ base_graph, graph_to_permute, is_single = self._broadcast( base_graph, graph_to_permute ) n_nodes = base_graph.shape[1] perm = gs.reshape(gs.tile(range(n_nodes), base_graph.shape[0]), (-1, n_nodes)) self.perm_ = gs.array(perm[0]) if is_single else gs.array(perm) return self._permute(space, graph_to_permute, self.perm_)
[docs] class ExhaustiveAligner(_BaseAligner): """Brute force exact alignment. Exact Alignment obtained by exploring the whole permutation group. Notes ----- Not recommended for large `n_nodes`. """ def __init__(self): super().__init__() self._all_perms = None self._n_nodes = None def _set_all_perms(self, space): n_nodes = space.n_nodes if self._all_perms is None or self._n_nodes != n_nodes: self._n_nodes = n_nodes self._all_perms = gs.array( list(itertools.permutations(range(n_nodes), n_nodes)) ) def _align_single(self, space, base_graph, graph_to_permute): permuted_graphs = space.permute(graph_to_permute, self._all_perms) dists = space.total_space.metric.dist(base_graph, permuted_graphs) return self._all_perms[gs.argmin(dists)]
[docs] def align(self, space, base_graph, graph_to_permute): """Align graphs. Parameters ---------- space : GraphSpace base_graph : array-like, shape=[..., n_nodes, n_nodes] Base graph. graph_to_permute : array-like, shape=[..., n_nodes, n_nodes] Graph to align. Returns ------- permuted_graph : array-like, shape=[..., n_nodes, n_nodes] Permuted graph as to be aligned with respect to the geodesic. """ self._set_all_perms(space) base_graph, graph_to_permute, is_single = self._broadcast( base_graph, graph_to_permute ) perms = [ self._align_single(space, base_graph_, graph_to_permute_) for base_graph_, graph_to_permute_ in zip(base_graph, graph_to_permute) ] self.perm_ = gs.array(perms[0]) if is_single else gs.array(perms) return self._permute(space, graph_to_permute, self.perm_)
class _BasePointToGeodesicAligner(metaclass=ABCMeta): """Base class for point to geodesic aligner. Attributes ---------- perm_ : array-like, shape=[..., n_nodes] Node permutations where in position i we have the value j meaning the node i should be permuted with node j. """ def __init__(self): self.perm_ = None @abstractmethod def align(self, geodesic, graph_to_permute): """Class for the Alignment of the geodesic with respect to a point.""" raise NotImplementedError("Not implemented") @abstractmethod def dist(self, geodesic, graph_to_permute): """Class to compute distance between the geodesic with respect to a point.""" raise NotImplementedError("Not implemented") def _get_n_points(self, graph_to_permute): return 1 if gs.ndim(graph_to_permute) == 2 else gs.shape(graph_to_permute)[0] def _permute(self, space, graph_to_permute, perm): return space.permute(graph_to_permute, perm)
[docs] class PointToGeodesicAligner(_BasePointToGeodesicAligner): """Class for the Alignment of the points with respect to a geodesic. Implementing the algorithm in [Huckemann2010]_ to select an optimal alignment to a point with respect to a geodesic. The algorithm sample discrete set of n_points along the geodesic between [s_min, s_max] and find the permutation that gets closer to the datapoints along the geodesic. Parameters ---------- space : GraphSpace s_min : float Minimum value of the domain to sample along the geodesics. s_max : float Minimum value of the domain to sample along the geodesics. n_points: int Number of points to sample between s_min and s_max. References ---------- .. [Calissano2020] Calissano, A., Feragen, A., Vantini, S. “Graph Space: Geodesic Principal Components for a Population of Network-valued Data.” Mox report 14, 2020. https://mox.polimi.it/reports-and-theses/publication-results/?id=855. .. [Huckemann2010] Huckemann, S., Hotz, T., Munk, A. "Intrinsic shape analysis: Geodesic PCA for Riemannian manifolds modulo isometric Lie group actions." Statistica Sinica, 1-58, 2010. """ def __init__(self, s_min, s_max, n_points=10): super().__init__() self.s_min = s_min self.s_max = s_max self.n_points = n_points self._s = None def __setattr__(self, attr_name, value): """Set attributes.""" if attr_name in ["s_min", "s_max", "n_points"]: self._s = None return object.__setattr__(self, attr_name, value) def _discretize_s(self): """Compute the domain distretization.""" return gs.linspace(self.s_min, self.s_max, num=self.n_points) @property def s(self): """Save the domain discretization.""" if self._s is None: self._s = self._discretize_s() return self._s def _get_geodesic_s(self, geodesic): """Evaluate the geodesic in s.""" return geodesic(self.s) def _compute_dists(self, space, geodesic, graph): geodesic_s = self._get_geodesic_s(geodesic) n_points = self._get_n_points(graph) if n_points > 1: geodesic_s = gs.repeat(geodesic_s, n_points, axis=0) rep_graph = gs.concatenate([graph for _ in range(self.n_points)]) else: rep_graph = graph dists = gs.reshape( space.metric.dist(geodesic_s, rep_graph), (self.n_points, n_points) ) min_dists_idx = gs.argmin(dists, axis=0) return dists, min_dists_idx, n_points
[docs] def dist(self, space, geodesic, graph_to_permute): """Compute the distance between the geodesic and the point. Parameters ---------- space : GraphSpace geodesic : function Geodesic function in GraphSpace. graph_to_permute : array-like, shape=[..., n_nodes, n_nodes] Graph to align. Returns ------- dist : array-like, shape=[..., n_nodes] Distance between the graph_to_permute and the geodesic. """ dists, min_dists_idx, n_points = self._compute_dists( space, geodesic, graph_to_permute ) return gs.take( gs.transpose(dists), min_dists_idx + gs.arange(n_points) * self.n_points, )
[docs] def align(self, space, geodesic, graph_to_permute): """Align the graph to the geodesic. Parameters ---------- geodesic : function Geodesic function in GraphSpace. graph_to_permute : array-like, shape=[..., n_nodes, n_nodes] Graph to align. Returns ------- permuted_graph : array-like, shape=[..., n_nodes] Permuted graph as to be aligned with respect to the geodesic. """ _, min_dists_idx, n_points = self._compute_dists( space, geodesic, graph_to_permute ) perm_indices = min_dists_idx * n_points + gs.arange(n_points) if n_points == 1: perm_indices = perm_indices[0] self.perm_ = gs.take(space.metric.perm_, perm_indices, axis=0) return self._permute(space, graph_to_permute, self.perm_)
class _GeodesicToPointAligner(_BasePointToGeodesicAligner): def __init__(self, method="BFGS", *, save_opt_res=False): super().__init__() self.method = method self.save_opt_res = save_opt_res self.opt_results_ = None def _objective(self, s, space, graph, geodesic): point = geodesic(s) dist = space.metric.dist(point, graph) return dist def _compute_dists(self, space, geodesic, graph_to_permute): n_points = self._get_n_points(graph_to_permute) if n_points == 1: graph_to_permute = gs.expand_dims(graph_to_permute, axis=0) perms = [] min_dists = [] opt_results = [] for graph in graph_to_permute: s0 = 0.0 res = scipy.optimize.minimize( self._objective, x0=s0, args=(space, graph, geodesic), method=self.method, ) perms.append(space.metric.perm_[0]) min_dists.append(res.fun) opt_results.append(res) if self.save_opt_res: self.opt_results_ = opt_results return gs.array(min_dists), gs.array(perms), n_points def dist(self, space, geodesic, graph_to_permute): dists, _, _ = self._compute_dists(space, geodesic, graph_to_permute) return dists def align(self, space, geodesic, graph_to_permute): _, perms, n_points = self._compute_dists(space, geodesic, graph_to_permute) new_graph = self._permute(space, graph_to_permute, perms) self.perm_ = perms[0] if n_points == 1 else perms return new_graph
[docs] class GraphPoint(Point): r"""Class for the GraphPoint. Points are represented by :math:`nodes \times nodes` adjacency matrices. Parameters ---------- adj : array-like, shape=[n_nodes, n_nodes] Adjacency matrix. References ---------- .. [Calissano2020] Calissano, A., Feragen, A., Vantini, S. “Graph Space: Geodesic Principal Components for a Population of Network-valued Data.” Mox report 14, 2020. https://mox.polimi.it/reports-and-theses/publication-results/?id=855. """ def __init__(self, adj): super().__init__() self.adj = adj @property def n_nodes(self): """Retrieve the number of nodes.""" return self.adj.shape[0] def __repr__(self): """Return a readable representation of the instance.""" return f"Adjacency: {self.adj}" def __hash__(self): """Return the hash of the instance.""" return hash(self.adj)
[docs] def to_array(self): """Return a copy of the adjacency matrix.""" return gs.copy(self.adj)
[docs] def to_networkx(self): """Turn the graph into a networkx format.""" return nx.from_numpy_array(self.adj)
[docs] class GraphSpace(PointSet): r"""Class for the Graph Space. Graph Space to analyse populations of labelled and unlabelled graphs. The space focuses on graphs with scalar euclidean attributes on nodes and edges, with a finite number of nodes and both directed and undirected edges. For undirected graphs, use symmetric adjacency matrices. The space is a quotient space obtained by applying the permutation action of nodes to the space of adjacency matrices. Notice that for computation reasons the module works with both the `gs.array` representation of graph and the `GraphPoint` representation. Points are represented by :math:`nodes \times nodes` adjacency matrices. Both the array input and the Graph Point type input work. Parameters ---------- n_nodes : int Number of graph nodes total_space : space Total Space before applying the permutation action. Default: Euclidean Space. References ---------- .. [Calissano2020] Calissano, A., Feragen, A., Vantini, S. “Graph Space: Geodesic Principal Components for a Population of Network-valued Data.” Mox report 14, 2020. https://mox.polimi.it/reports-and-theses/publication-results/?id=855. .. [Jain2009] Jain, B., Obermayer, K. "Structure Spaces." Journal of Machine Learning Research, 10(11), 2009. https://www.jmlr.org/papers/volume10/jain09a/jain09a.pdf """ def __init__(self, n_nodes, total_space=None, equip=True): super().__init__(equip=equip) self.n_nodes = n_nodes self.total_space = ( Matrices(n_nodes, n_nodes, equip=equip) if total_space is None else total_space )
[docs] @staticmethod def default_metric(): """Metric to equip the space with if equip is True.""" return GraphSpaceMetric
[docs] @_pad_with_zeros((1, "graphs")) def belongs(self, graphs, atol=gs.atol): """Check if the point belongs to the space. Parameters ---------- graphs : list of GraphPoint or array-like, shape=[..., n_nodes, n_nodes] Points to be checked. atol : float Tolerance. Optional, default: backend atol. Returns ------- belongs : array-like, shape=[..., n_nodes] Boolean denoting if graph belongs to the space. """ if type(graphs) in [list, tuple]: return gs.array([graph.n_nodes == self.n_nodes for graph in graphs]) if type(graphs) is GraphPoint: return graphs.n_nodes == self.n_nodes return self.total_space.belongs(graphs, atol=atol)
[docs] def random_point(self, n_samples=1, bound=1.0): """Sample in Graph Space. Parameters ---------- n_samples : int Number of samples. Optional, default: 1. bound : float Bound of the interval in which to sample in the tangent space. Optional, default: 1. Returns ------- graph_samples : array-like, shape=[..., n_nodes, n_nodes] Points sampled in GraphSpace(n_nodes). """ return self.total_space.random_point(n_samples=n_samples, bound=bound)
[docs] @_vectorize_graph((1, "points")) @_pad_with_zeros((1, "points")) def set_to_array(self, points): """Return a copy of the adjacency matrices. Parameters ---------- points : list of GraphPoint or array-like, shape=[..., n_nodes, n_nodes] Points to be turned into an array Returns ------- graph_array : array-like, shape=[..., n_nodes, n_nodes] An array containing all the Graphs. """ return gs.copy(points)
[docs] @_vectorize_graph_to_points((1, "points")) @_pad_with_zeros((1, "points")) def set_to_networkx(self, points): """Turn points into a networkx object. Parameters ---------- points : list of GraphPoint or array-like, shape=[..., n_nodes, n_nodes] Returns ------- nx_list : list of networkx object An array containing all the Graphs. """ networkx_objs = [pt.to_networkx() for pt in points] return networkx_objs if len(networkx_objs) > 1 else networkx_objs[0]
[docs] @_vectorize_graph((1, "graph_to_permute")) @_pad_with_zeros((1, "graph_to_permute")) def permute(self, graph_to_permute, permutation): """Permutation action applied to graph observation. Parameters ---------- graph_to_permute : list of GraphPoint or array-like, shape=[..., n_nodes, n_nodes] Input graphs to be permuted. permutation: array-like, shape=[..., n_nodes] Node permutations where in position i we have the value j meaning the node i should be permuted with node j. Returns ------- graphs_permuted : array-like, shape=[..., n_nodes, n_nodes] Graphs permuted. """ def _get_permutation_matrix(indices_): return gs.array_from_sparse( data=gs.ones(self.n_nodes, dtype=gs.int64), indices=list(zip(range(self.n_nodes), indices_)), target_shape=(self.n_nodes, self.n_nodes), ) if gs.ndim(permutation) == 1: perm_matrices = _get_permutation_matrix(permutation) else: perm_matrices = [] for indices_ in permutation: perm_matrices.append(_get_permutation_matrix(indices_)) perm_matrices = gs.stack(perm_matrices) permuted_graph = Matrices.mul( perm_matrices, graph_to_permute, Matrices.transpose(perm_matrices) ) if gs.ndim(permuted_graph) == 3 and gs.shape(permuted_graph)[0] == 1: return permuted_graph[0] return permuted_graph
[docs] @_pad_with_zeros((1, "points"), copy=False) def pad_with_zeros(self, points): """Pad points with zeros to match space dimension. Parameters ---------- points : list of GraphPoint or array-like, shape=[..., n_nodes, n_nodes] """ return points
[docs] class GraphSpaceMetric(PointSetMetric): r"""Class for the Graph Space Metric. Every metric :math:`d: X \times X \rightarrow \mathbb{R}` on the total space of adjacency matrices can descend onto the quotient space as a pseudo-metric: :math:`d([x_1],[x_2]) = min_{t\in T} d_X(x_1, t^Tx_2t)`. The metric relies on the total space metric and an alignment procedure, i.e., Graph Matching or Networks alignment procedure. Metric, alignment, geodesics, and alignment with respect to a geodesic are defined. By default, the alignment is the identity and the total space metric is the Frobenious norm. Parameters ---------- space : GraphSpace GraphSpace object. References ---------- .. [Calissano2020] Calissano, A., Feragen, A., Vantini, S. “Graph Space: Geodesic Principal Components for a Population of Network-valued Data.” Mox report 14, 2020. https://mox.polimi.it/reports-and-theses/publication-results/?id=855. """ MAP_ALIGNER = { "ID": IDAligner, "FAQ": FAQAligner, "exhaustive": ExhaustiveAligner, } def __init__(self, space): super().__init__(space=space) self.aligner = self._set_default_aligner() self.point_to_geodesic_aligner = None @property def perm_(self): """Permutation of nodes after alignment. Node permutations where in position i we have the value j meaning the node i should be permuted with node j. """ return self.aligner.perm_ def _set_default_aligner(self): return self.set_aligner("ID")
[docs] def set_aligner(self, aligner, **kwargs): """Set the aligning strategy. Graph Space metric relies on alignment. In this module we propose the identity matching, the FAQ graph matching by [Vogelstein2015]_, and exhaustive aligner which explores the whole permutation group. Parameters ---------- aligner : str 'ID' Identity 'FAQ' Fast Quadratic Assignment - only compatible with Frobenious norm 'exhaustive' all group exhaustive search References ---------- .. [Vogelstein2015] Vogelstein JT, Conroy JM, Lyzinski V, Podrazik LJ, Kratzer SG, Harley ET, Fishkind DE, Vogelstein RJ, Priebe CE. “Fast approximate quadratic programming for graph matching.“ PLoS One. 2015 Apr 17; doi: 10.1371/journal.pone.0121002. """ if isinstance(aligner, str): check_parameter_accepted_values( aligner, "aligner", list(self.MAP_ALIGNER.keys()) ) aligner = self.MAP_ALIGNER.get(aligner)(**kwargs) self.aligner = aligner return self.aligner
[docs] def set_point_to_geodesic_aligner(self, aligner, **kwargs): """Set the alignment between a point and a geodesic. Following the geodesic to point alignment in [Calissano2020]_ and [Huckemann2010]_, this function defines the parameters [s_min, s_max] and the number of points to sample in the domain. Parameters ---------- s_min : float Minimum value of the domain to sample along the geodesics. s_max : float Minimum value of the domain to sample along the geodesics. n_points: int Number of points to sample between s_min and s_max. References ---------- .. [Calissano2020] Calissano, A., Feragen, A., Vantini, S. “Graph Space: Geodesic Principal Components for a Population of Network-valued Data.” Mox report 14, 2020. https://mox.polimi.it/reports-and-theses/publication-results/?id=855. .. [Huckemann2010] Huckemann, S., Hotz, T., Munk, A. "Intrinsic shape analysis: Geodesic PCA for Riemannian manifolds modulo isometric Lie group actions." Statistica Sinica, 1-58, 2010. """ if aligner == "default": kwargs.setdefault("s_min", -1.0) kwargs.setdefault("s_max", 1.0) kwargs.setdefault("n_points", 10) aligner = PointToGeodesicAligner(**kwargs) self.point_to_geodesic_aligner = aligner return self.point_to_geodesic_aligner
@property def total_space_metric(self): """Retrieve the total space metric.""" return self._space.total_space.metric @total_space_metric.setter def total_space_metric(self, value): """Set the total space metric.""" self._space.total_space.metric = value @property def n_nodes(self): """Retrieve the number of nodes.""" return self._space.n_nodes
[docs] @_vectorize_graph((1, "graph_a"), (2, "graph_b")) @_pad_with_zeros((1, "graph_a"), (2, "graph_b")) def dist(self, graph_a, graph_b): """Compute distance between two equivalence classes. Compute the distance between two equivalence classes of adjacency matrices [Jain2009]_. Parameters ---------- graph_a : list of GraphPoint or array-like, shape=[..., n_nodes, n_nodes] graph_b : list of GraphPoint or array-like, shape=[..., n_nodes, n_nodes] Returns ------- distance : array-like, shape=[...] distance between equivalence classes. References ---------- .. [Jain2009] Jain, B., Obermayer, K. "Structure Spaces." Journal of Machine Learning Research 10.11 (2009). https://www.jmlr.org/papers/v10/jain09a.html. """ aligned_graph_b = self.align_point_to_point(graph_a, graph_b) return self.total_space_metric.dist( graph_a, aligned_graph_b, )
[docs] @_vectorize_graph((1, "base_point"), (2, "end_point")) @_pad_with_zeros((1, "base_point"), (2, "end_point")) def geodesic(self, base_point, end_point): """Compute geodesic between two equivalence classes. Compute the geodesic between two equivalence classes of adjacency matrices [Calissano2020]_. Parameters ---------- base_point : list of GraphPoint or array-like, shape=[..., n_nodes, n_nodes] Start . end_point : list of GraphPoint or array-like, shape=[..., n_nodes, n_nodes] Second graph to align to the first graph. Returns ------- geodesic : callable Geodesic function. References ---------- .. [Calissano2020] Calissano, A., Feragen, A., Vantini, S. “Graph Space: Geodesic Principal Components for a Population of Network-valued Data.” Mox report 14, 2020. https://mox.polimi.it/reports-and-theses/publication-results/?id=855. """ aligned_end_point = self.align_point_to_point(base_point, end_point) return self.total_space_metric.geodesic( initial_point=base_point, end_point=aligned_end_point )
[docs] @_vectorize_graph((1, "base_graph"), (2, "graph_to_permute")) @_pad_with_zeros((1, "base_graph"), (2, "graph_to_permute")) def align_point_to_point(self, base_graph, graph_to_permute): """Align graphs. Using the selected alignment technique, it returns the permuted graph_to_permute as optimally aligned to the base_graph. Parameters ---------- base_graph : list of Graph or array-like, shape=[..., n_nodes, n_nodes] Base graph. graph_to_permute : list of Graph or array-like, shape=[..., n_nodes, n_nodes] Graph to align. Returns ------- permuted_graph: list, shape = [..., n_nodes, n_nodes] """ return self.aligner.align(self._space, base_graph, graph_to_permute)
[docs] @_vectorize_graph( (2, "graph_to_permute"), ) @_pad_with_zeros( (2, "graph_to_permute"), ) def align_point_to_geodesic(self, geodesic, graph_to_permute): """Align graph to a geodesic. Using the selected alignment technique, it returns the permuted graph_to_permute as optimally aligned to the geodesic using [Huckemann2010]_. Parameters ---------- geodesic : function Geodesic in Graph Space function. graph_to_permute : list of Graph or array-like, shape=[..., n_nodes, n_nodes] Graph to align. Returns ------- permuted_graph: list, shape = [..., n_nodes, n_nodes] References ---------- .. [Huckemann2010] Huckemann, S., Hotz, T., Munk, A. "Intrinsic shape analysis: Geodesic PCA for Riemannian manifolds modulo isometric Lie group actions." Statistica Sinica, 1-58, 2010. """ if self.point_to_geodesic_aligner is None: raise UnboundLocalError( "Set point to geodesic aligner first (e.g. " "`metric.set_point_to_geodesic_aligner('default', " "s_min=-1., s_max=1.)`)" ) return self.point_to_geodesic_aligner.align( self._space, geodesic, graph_to_permute )