inverse_approx_multihop_chain_interdependence

Bases: chain_interdependence

An approximate multihop chain interdependence function using matrix inversion.

Notes

To further optimize the computations, we propose approximating the accumulative interdependence function using Taylor's polynomial expansion series. Considering the Taylor's expansions of the reciprocal function \(\frac{1}{1-x}\):

\[
    \begin{equation}
    \frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots = \sum_{h=0}^{\infty} x^h.
    \end{equation}
\]

Based on them, we define the reciprocal structural interdependence function and exponential structural interdependence function for approximating the above multi-hop chain-structured topological interdependence relationships as:

\[
    \begin{equation}
    \xi(\mathbf{x}) = (\mathbf{I} - \mathbf{A})^{-1} \in R^{m \times m} \text{, and } \xi(\mathbf{x}) = \exp(\mathbf{A}) \in R^{m \times m}.
    \end{equation}
\]

Methods:

Name	Description
__init__	Initializes the approximate multihop chain interdependence function.
calculate_A	Computes the approximate multihop interdependence matrix.

Source code in tinybig/interdependence/topological_interdependence.py

class inverse_approx_multihop_chain_interdependence(chain_interdependence):
    r"""
        An approximate multihop chain interdependence function using matrix inversion.

        Notes
        -------
        To further optimize the computations, we propose approximating the accumulative interdependence function using Taylor's polynomial expansion series.
        Considering the Taylor's expansions of the reciprocal function $\frac{1}{1-x}$:

        $$
            \begin{equation}
            \frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots = \sum_{h=0}^{\infty} x^h.
            \end{equation}
        $$

        Based on them, we define the reciprocal structural interdependence function and exponential structural interdependence function for approximating the above multi-hop chain-structured topological interdependence relationships as:

        $$
            \begin{equation}
            \xi(\mathbf{x}) = (\mathbf{I} - \mathbf{A})^{-1} \in R^{m \times m} \text{, and } \xi(\mathbf{x}) = \exp(\mathbf{A}) \in R^{m \times m}.
            \end{equation}
        $$

        Methods
        -------
        __init__(...)
            Initializes the approximate multihop chain interdependence function.
        calculate_A(...)
            Computes the approximate multihop interdependence matrix.
    """
    def __init__(self, name: str = 'inverse_approx_multihop_chain_interdependence', normalization: bool = False, normalization_mode: str = 'row', *args, **kwargs):
        """
            Initializes the approximate multihop chain interdependence function using matrix inversion.

            Parameters
            ----------
            name : str, optional
                Name of the interdependence function. Defaults to 'inverse_approx_multihop_chain_interdependence'.
            normalization : bool, optional
                Whether to normalize the interdependence matrix. Defaults to False.
            normalization_mode : str, optional
                The mode of normalization ('row', 'column', etc.). Defaults to 'row'.
            *args : tuple
                Additional positional arguments.
            **kwargs : dict
                Additional keyword arguments.
        """
        super().__init__(name=name, normalization=normalization, normalization_mode=normalization_mode, *args, **kwargs)

    def calculate_A(self, x: torch.Tensor = None, w: torch.nn.Parameter = None, device: str = 'cpu', *args, **kwargs):
        """
            Computes the approximate multihop interdependence matrix using matrix inversion.

            Parameters
            ----------
            x : torch.Tensor, optional
                Input tensor of shape `(batch_size, num_features)`. Defaults to None.
            w : torch.nn.Parameter, optional
                Parameter tensor. Defaults to None.
            device : str, optional
                Device for computation ('cpu', 'cuda'). Defaults to 'cpu'.
            *args : tuple
                Additional positional arguments.
            **kwargs : dict
                Additional keyword arguments.

            Returns
            -------
            torch.Tensor
                The computed approximate multihop interdependence matrix.

            Raises
            ------
            AssertionError
                If the computed matrix shape is invalid.
        """
        if not self.require_data and not self.require_parameters and self.A is not None:
            return self.A
        else:
            adj, mappings = self.chain.to_matrix(normalization=self.normalization, normalization_mode=self.normalization_mode, device=device)
            self.node_id_index_map = mappings['node_id_index_map']
            self.node_index_id_map = mappings['node_index_id_map']

            if self.is_bi_directional():
                A = accumulative_matrix_power(adj, n=adj.shape[0] - 1)
                A = degree_based_normalize_matrix(mx=A, mode='column')
            else:
                A = torch.inverse(torch.eye(adj.shape[0], device=device) - adj)

            A = self.post_process(x=A, device=device)

            if self.interdependence_type in ['column', 'right', 'attribute', 'attribute_interdependence']:
                assert A.shape == (self.m, self.calculate_m_prime())
            elif self.interdependence_type in ['row', 'left', 'instance', 'instance_interdependence']:
                assert A.shape == (self.b, self.calculate_b_prime())

            if not self.require_data and not self.require_parameters and self.A is None:
                self.A = A

            return A

__init__(name='inverse_approx_multihop_chain_interdependence', normalization=False, normalization_mode='row', *args, **kwargs)

Initializes the approximate multihop chain interdependence function using matrix inversion.

Parameters:

Name	Type	Description	Default
name	str	Name of the interdependence function. Defaults to 'inverse_approx_multihop_chain_interdependence'.	'inverse_approx_multihop_chain_interdependence'
normalization	bool	Whether to normalize the interdependence matrix. Defaults to False.	False
normalization_mode	str	The mode of normalization ('row', 'column', etc.). Defaults to 'row'.	'row'
*args	tuple	Additional positional arguments.	()
**kwargs	dict	Additional keyword arguments.	{}

Source code in tinybig/interdependence/topological_interdependence.py

def __init__(self, name: str = 'inverse_approx_multihop_chain_interdependence', normalization: bool = False, normalization_mode: str = 'row', *args, **kwargs):
    """
        Initializes the approximate multihop chain interdependence function using matrix inversion.

        Parameters
        ----------
        name : str, optional
            Name of the interdependence function. Defaults to 'inverse_approx_multihop_chain_interdependence'.
        normalization : bool, optional
            Whether to normalize the interdependence matrix. Defaults to False.
        normalization_mode : str, optional
            The mode of normalization ('row', 'column', etc.). Defaults to 'row'.
        *args : tuple
            Additional positional arguments.
        **kwargs : dict
            Additional keyword arguments.
    """
    super().__init__(name=name, normalization=normalization, normalization_mode=normalization_mode, *args, **kwargs)

calculate_A(x=None, w=None, device='cpu', *args, **kwargs)

Computes the approximate multihop interdependence matrix using matrix inversion.

Parameters:

Name	Type	Description	Default
x	Tensor	Input tensor of shape (batch_size, num_features). Defaults to None.	None
w	Parameter	Parameter tensor. Defaults to None.	None
device	str	Device for computation ('cpu', 'cuda'). Defaults to 'cpu'.	'cpu'
*args	tuple	Additional positional arguments.	()
**kwargs	dict	Additional keyword arguments.	{}

Returns:

Type	Description
Tensor	The computed approximate multihop interdependence matrix.

Raises:

Type	Description
AssertionError	If the computed matrix shape is invalid.

Source code in tinybig/interdependence/topological_interdependence.py

def calculate_A(self, x: torch.Tensor = None, w: torch.nn.Parameter = None, device: str = 'cpu', *args, **kwargs):
    """
        Computes the approximate multihop interdependence matrix using matrix inversion.

        Parameters
        ----------
        x : torch.Tensor, optional
            Input tensor of shape `(batch_size, num_features)`. Defaults to None.
        w : torch.nn.Parameter, optional
            Parameter tensor. Defaults to None.
        device : str, optional
            Device for computation ('cpu', 'cuda'). Defaults to 'cpu'.
        *args : tuple
            Additional positional arguments.
        **kwargs : dict
            Additional keyword arguments.

        Returns
        -------
        torch.Tensor
            The computed approximate multihop interdependence matrix.

        Raises
        ------
        AssertionError
            If the computed matrix shape is invalid.
    """
    if not self.require_data and not self.require_parameters and self.A is not None:
        return self.A
    else:
        adj, mappings = self.chain.to_matrix(normalization=self.normalization, normalization_mode=self.normalization_mode, device=device)
        self.node_id_index_map = mappings['node_id_index_map']
        self.node_index_id_map = mappings['node_index_id_map']

        if self.is_bi_directional():
            A = accumulative_matrix_power(adj, n=adj.shape[0] - 1)
            A = degree_based_normalize_matrix(mx=A, mode='column')
        else:
            A = torch.inverse(torch.eye(adj.shape[0], device=device) - adj)

        A = self.post_process(x=A, device=device)

        if self.interdependence_type in ['column', 'right', 'attribute', 'attribute_interdependence']:
            assert A.shape == (self.m, self.calculate_m_prime())
        elif self.interdependence_type in ['row', 'left', 'instance', 'instance_interdependence']:
            assert A.shape == (self.b, self.calculate_b_prime())

        if not self.require_data and not self.require_parameters and self.A is None:
            self.A = A

        return A