Source code for skfolio.distance._graph_distance

"""Graph distance estimator."""

# Copyright (c) 2023-2026
# Author: Hugo Delatte <hugo.delatte@skfoliolabs.com>
# Credits: Matteo Manzi, Ojas Arora
# SPDX-License-Identifier: BSD-3-Clause

from __future__ import annotations

from typing import ClassVar, Literal

import numpy as np
import pandas as pd
import scipy.sparse as sps
import sklearn.utils as sku
import sklearn.utils.validation as skv
from sklearn.utils.extmath import row_norms

from skfolio.containers import GraphSeries
from skfolio.distance._base import BaseDistance
from skfolio.distance._utils import _corr_to_distance
from skfolio.typing import CSRArray, FloatArray, IntArray
from skfolio.utils.tools import (
    _validate_bool,
    _validate_positive_integer,
    _validate_unit_interval,
)
from skfolio.utils.validation import _asset_positions

_FITTED_ATTR = "distance_"


[docs] class GraphDistance(BaseDistance): r"""Graph Distance estimator. The codependence is computed from cosine similarities between the assets' dependency profiles. The distance is then computed as :math:`\sqrt{1-S}`, where :math:`S` is the codependence matrix. A dependency profile contains the weights of an asset's direct and indirect dependencies. An edge from :math:`i` to :math:`j` represents a dependency of :math:`i` on :math:`j`. For adjacency matrix :math:`M`, after optional row normalization, the profiles are the asset rows of: .. math:: \sum_{h=1}^{H} \alpha^{h-1} M^h where :math:`H` = `max_hops` and :math:`\alpha` = `decay`. Parameters ---------- max_hops : int, default=2 Maximum number of edges traversed when computing dependencies. A value of 1 includes only direct dependencies and 2 also includes their dependencies. Must be at least 1. Nodes can be revisited through cycles. decay : float, default=0.5 Weight multiplier for each additional hop, in :math:`[0, 1]`. A value of zero includes only direct dependencies. normalize_adjacency : bool, default=True If True, the outgoing weights of each node are normalized to sum to one before propagation. If False, the original edge weights are used. Attributes ---------- codependence_ : ndarray of shape (n_assets, n_assets) Codependence matrix of cosine similarities between dependency profiles, with values in :math:`[0, 1]`. distance_ : ndarray of shape (n_assets, n_assets) Euclidean distances between dependency profiles normalized to unit length, divided by :math:`\sqrt{2}`. Values are in :math:`[0, 1]`, with a zero diagonal for assets with positive outgoing edge weights. n_features_in_ : int Number of assets seen during fitting. feature_names_in_ : ndarray of shape (`n_features_in_`,) Names of assets seen during fitting. Notes ----- Estimation uses the graph at the final observation. Graph observations are assumed to be chronological, with each graph containing only information available at that observation. Assets absent from the graph or without positive outgoing edges have NaN rows and columns in both fitted matrices, including their diagonals. The prior determines which assets are investable. Negative edge weights are not supported. For `max_hops=1` or `decay=0`, only direct dependencies are included and row normalization has no effect on the distances. Indirect dependencies can include graph nodes outside the investment universe. See Also -------- skfolio.containers.Graph : Weighted directed graph with named nodes. skfolio.containers.GraphSeries : Graphs indexed by observation. Examples -------- Asset B depends on two suppliers, with weights 3 and 1. It shares one supplier with A and the other with C: >>> import pandas as pd >>> from skfolio.containers import Graph, GraphSeries >>> from skfolio.distance import GraphDistance >>> X = pd.DataFrame({"A": [0.01], "B": [-0.02], "C": [0.03]}) >>> graph = Graph.from_edges( ... [ ... ("A", "Supplier 1", 1), ... ("B", "Supplier 1", 3), ... ("B", "Supplier 2", 1), ... ("C", "Supplier 2", 1), ... ], ... nodes=["A", "B", "C", "Supplier 1", "Supplier 2"], ... ) >>> graphs = GraphSeries([graph], observations=X.index) >>> model = GraphDistance().fit(X, graphs=graphs) >>> model.distance_.round(3) array([[0. , 0.227, 1. ], [0.227, 0. , 0.827], [1. , 0.827, 0. ]]) """ __metadata_request__fit: ClassVar[dict[str, bool]] = {"graphs": True} __metadata_request__partial_fit: ClassVar[dict[str, bool]] = {"graphs": True} def __init__( self, *, max_hops: int = 2, decay: float = 0.5, normalize_adjacency: bool = True, ) -> None: self.max_hops = max_hops self.decay = decay self.normalize_adjacency = normalize_adjacency
[docs] def fit( self, X: pd.DataFrame, y: None = None, *, graphs: GraphSeries | None = None ) -> GraphDistance: """Fit the Graph Distance estimator. Parameters ---------- X : pandas.DataFrame of shape (n_observations, n_assets) Asset returns with unique string column names identifying assets in the graph. At least one asset is required. Return values are not used and can contain NaN. y : Ignored Not used, present for API consistency by convention. graphs : GraphSeries, required Graphs for the training observations. The graph at the final observation must be present. Passing `graphs` through an optimizer or cross-validation requires scikit-learn metadata routing to be enabled. Returns ------- self : GraphDistance Fitted estimator. """ self._reset() return self.partial_fit(X, y, graphs=graphs)
[docs] def partial_fit( self, X: pd.DataFrame, y: None = None, *, graphs: GraphSeries | None = None ) -> GraphDistance: """Update distances using the latest graph. Parameters ---------- X : pandas.DataFrame of shape (n_observations, n_assets) New asset returns with unique string column names identifying assets in the graph. Columns must match previous calls. Return values are not used and can contain NaN. y : Ignored Not used, present for API consistency by convention. graphs : GraphSeries, required Graphs for the new observations. The graph at the final observation must be present. Passing `graphs` through an optimizer requires scikit-learn metadata routing to be enabled. Returns ------- self : GraphDistance Updated estimator. """ _validate_positive_integer(self.max_hops, "max_hops") _validate_unit_interval(self.decay, "decay") _validate_bool(self.normalize_adjacency, "normalize_adjacency") if graphs is None: raise ValueError( "GraphDistance requires graphs=. When fitting through an optimizer " "or cross-validation, enable metadata routing with " "sklearn.set_config(enable_metadata_routing=True) and pass graphs=." ) if not isinstance(graphs, GraphSeries): raise TypeError("graphs must be a GraphSeries.") if not len(graphs): raise ValueError("graphs must contain at least one observation.") graph = graphs[-1] if graph is None: raise ValueError("graphs has no graph at the last observation.") if not isinstance(X, pd.DataFrame): raise ValueError("X must be a pandas DataFrame.") first_call = not hasattr(self, _FITTED_ATTR) skv.validate_data(self, X, reset=first_call, skip_check_array=True) if not hasattr(self, "feature_names_in_"): raise ValueError("X must have string column names.") asset_node_positions = _asset_positions( names=self.feature_names_in_, coverage=graph.nodes, source="graph", allow_missing=True, ) adjacency = graph.adjacency edge_weights = ( adjacency.data if isinstance(adjacency, sps.csr_array) else adjacency ) if np.any(edge_weights < 0): raise ValueError( "GraphDistance requires non-negative weights throughout the graph." ) n_assets = self.n_features_in_ in_graph = asset_node_positions >= 0 matched_node_positions = asset_node_positions[in_graph] has_dependencies = np.zeros(n_assets, dtype=bool) if isinstance(adjacency, sps.csr_array): # Graph omits zero-weight edges, so nonempty rows have positive weights. has_dependencies[in_graph] = ( adjacency.indptr[matched_node_positions + 1] > adjacency.indptr[matched_node_positions] ) else: has_dependencies[in_graph] = adjacency[matched_node_positions].any(axis=1) if not has_dependencies.any(): self.codependence_ = np.full((n_assets, n_assets), np.nan) self.distance_ = np.full_like(self.codependence_, np.nan) return self similarity = _graph_similarity( adjacency=adjacency, asset_node_positions=asset_node_positions[has_dependencies], max_hops=self.max_hops, decay=self.decay, normalize_adjacency=self.normalize_adjacency, ) codependence, distance = _corr_to_distance(similarity, absolute=True, power=1) if has_dependencies.all(): self.codependence_ = codependence self.distance_ = distance else: asset_indices = np.ix_(has_dependencies, has_dependencies) self.codependence_ = np.full((n_assets, n_assets), np.nan) self.distance_ = np.full_like(self.codependence_, np.nan) self.codependence_[asset_indices] = codependence self.distance_[asset_indices] = distance return self
def _reset(self) -> None: """Reset fitted state for a new learning run.""" if hasattr(self, _FITTED_ATTR): delattr(self, _FITTED_ATTR) def __sklearn_tags__(self) -> sku.Tags: """Allow missing return values because only asset names are used.""" tags = super().__sklearn_tags__() tags.input_tags.allow_nan = True return tags
def _normalize_graph_rows( matrix: FloatArray | CSRArray, *, norm: Literal["l1", "l2"] ) -> None: """Normalize nonnegative rows in place. Parameters ---------- matrix : ndarray or scipy.sparse.csr_array of shape (n_rows, n_nodes) Writable float64 matrix of finite nonnegative weights. Zero rows remain zero. norm : {"l1", "l2"} Normalize rows to sum to one with "l1", or to unit Euclidean length with "l2". Notes ----- Rows are first divided by their largest entry to avoid overflow or underflow when computing the norms. """ if isinstance(matrix, sps.csr_array): row_lengths = np.diff(matrix.indptr) maxima = matrix.max(axis=1).toarray().ravel() matrix.data /= np.repeat(np.where(maxima > 0, maxima, 1), row_lengths) scales = ( row_norms(matrix) if norm == "l2" else np.asarray(matrix.sum(axis=1)).ravel() ) matrix.data /= np.repeat(np.where(scales > 0, scales, 1), row_lengths) else: maxima = matrix.max(axis=1, keepdims=True) matrix /= np.where(maxima > 0, maxima, 1) scales = ( row_norms(matrix)[:, None] if norm == "l2" else matrix.sum(axis=1, keepdims=True) ) matrix /= np.where(scales > 0, scales, 1) def _graph_similarity( *, adjacency: FloatArray | CSRArray, asset_node_positions: IntArray, max_hops: int, decay: float, normalize_adjacency: bool, ) -> FloatArray: """Compute cosine similarities between propagated dependency profiles. Parameters ---------- adjacency : ndarray or scipy.sparse.csr_array of shape (n_nodes, n_nodes) Adjacency matrix with finite nonnegative weights. The input is not modified. asset_node_positions : ndarray of shape (n_assets,) Positions of assets with positive outgoing weights in the adjacency matrix. max_hops : int Maximum number of edges traversed, at least one. decay : float Weight multiplier for each additional hop, between zero and one inclusive. normalize_adjacency : bool Whether to normalize outgoing weights to sum to one before propagation. Returns ------- similarity : ndarray of shape (n_assets, n_assets) Cosine similarities of dependency profiles, with a unit diagonal. Raises ------ ValueError If propagation overflows float64 arithmetic. """ if max_hops == 1 or decay == 0: # Row scaling does not change cosine similarity of direct dependencies, so # only asset rows are converted. dependency_weights = adjacency[asset_node_positions].astype( np.float64, copy=False ) else: adjacency = adjacency.astype(np.float64, copy=normalize_adjacency) if normalize_adjacency: _normalize_graph_rows(adjacency, norm="l1") dependency_weights = adjacency[asset_node_positions] hop_weights = dependency_weights.copy() with np.errstate(over="ignore", invalid="ignore"): for _ in range(1, max_hops): hop_weights = hop_weights @ adjacency hop_weights *= decay dependency_weights += hop_weights dependency_values = ( dependency_weights.data if isinstance(dependency_weights, sps.csr_array) else dependency_weights ) if not np.isfinite(dependency_values).all(): raise ValueError( "Graph propagation overflowed. Reduce weights, max_hops or decay, " "or enable normalize_adjacency." ) _normalize_graph_rows(dependency_weights, norm="l2") similarity = dependency_weights @ dependency_weights.T if isinstance(similarity, sps.csr_array): similarity = similarity.toarray() np.clip(similarity, 0, 1, out=similarity) np.fill_diagonal(similarity, 1.0) return similarity