pagerank_multihop_graph_interdependence

Bases: graph_interdependence

A multihop graph-based interdependence function using the PageRank algorithm.

Notes

In addition to these formulas that calculate powers of matrix \(\mathbf{A}\), existing graph studies also offer other approaches to calculate long-distance dependency relationships among data instances, such as the PageRank algorithm. Without delving into the step-wise derivation of PageRank updating equations, we define the PageRank multi-hop graph interdependence function as follows:

\[
    \begin{equation}
    \xi(\mathbf{x}) = \alpha \cdot \left( \mathbf{I} - (1- \alpha) \cdot {\mathbf{A}} \right)^{-1} \in R^{m \times m}.
    \end{equation}
\]

Here, \(\alpha \in [0, 1]\) is a hyper-parameter of the function, typically set to \(0.15\) by default. Usually, matrix \(\mathbf{A}\) is normalized before being used in this formula.

Attributes:

Name	Type	Description
c	float	Damping factor for the PageRank algorithm.

Methods:

Name	Description
__init__	Initializes the PageRank multihop graph interdependence function.
calculate_A	Computes the interdependence matrix using the PageRank algorithm.

Source code in tinybig/interdependence/topological_interdependence.py

class pagerank_multihop_graph_interdependence(graph_interdependence):
    r"""
        A multihop graph-based interdependence function using the PageRank algorithm.

        Notes
        ----------

        In addition to these formulas that calculate powers of matrix $\mathbf{A}$, existing graph studies also offer other approaches to calculate long-distance dependency relationships among data instances, such as the PageRank algorithm.
        Without delving into the step-wise derivation of PageRank updating equations, we define the PageRank multi-hop graph interdependence function as follows:

        $$
            \begin{equation}
            \xi(\mathbf{x}) = \alpha \cdot \left( \mathbf{I} - (1- \alpha) \cdot {\mathbf{A}} \right)^{-1} \in R^{m \times m}.
            \end{equation}
        $$

        Here, $\alpha \in [0, 1]$ is a hyper-parameter of the function, typically set to $0.15$ by default. Usually, matrix $\mathbf{A}$ is normalized before being used in this formula.

        Attributes
        ----------
        c : float
            Damping factor for the PageRank algorithm.

        Methods
        -------
        __init__(...)
            Initializes the PageRank multihop graph interdependence function.
        calculate_A(...)
            Computes the interdependence matrix using the PageRank algorithm.
    """
    def __init__(self, c: float = 0.15, name: str = 'pagerank_multihop_graph_interdependence', *args, **kwargs):
        """
            Initializes the PageRank multihop graph interdependence function.

            Parameters
            ----------
            c : float, optional
                Damping factor for the PageRank algorithm. Defaults to 0.15.
            name : str, optional
                Name of the interdependence function. Defaults to 'pagerank_multihop_graph_interdependence'.
            *args : tuple
                Additional positional arguments.
            **kwargs : dict
                Additional keyword arguments.
        """
        super().__init__(name=name, *args, **kwargs)
        self.c = c

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

            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 interdependence matrix using the PageRank algorithm.

            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.graph.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']

            A = self.c * torch.inverse((torch.eye(adj.shape[0], device=device) - (1.0 - self.c) * 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__(c=0.15, name='pagerank_multihop_graph_interdependence', *args, **kwargs)

Initializes the PageRank multihop graph interdependence function.

Parameters:

Name	Type	Description	Default
c	float	Damping factor for the PageRank algorithm. Defaults to 0.15.	0.15
name	str	Name of the interdependence function. Defaults to 'pagerank_multihop_graph_interdependence'.	'pagerank_multihop_graph_interdependence'
*args	tuple	Additional positional arguments.	()
**kwargs	dict	Additional keyword arguments.	{}

Source code in tinybig/interdependence/topological_interdependence.py

def __init__(self, c: float = 0.15, name: str = 'pagerank_multihop_graph_interdependence', *args, **kwargs):
    """
        Initializes the PageRank multihop graph interdependence function.

        Parameters
        ----------
        c : float, optional
            Damping factor for the PageRank algorithm. Defaults to 0.15.
        name : str, optional
            Name of the interdependence function. Defaults to 'pagerank_multihop_graph_interdependence'.
        *args : tuple
            Additional positional arguments.
        **kwargs : dict
            Additional keyword arguments.
    """
    super().__init__(name=name, *args, **kwargs)
    self.c = c

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

Computes the interdependence matrix using the PageRank algorithm.

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 interdependence matrix using the PageRank algorithm.

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 interdependence matrix using the PageRank algorithm.

        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 interdependence matrix using the PageRank algorithm.

        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.graph.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']

        A = self.c * torch.inverse((torch.eye(adj.shape[0], device=device) - (1.0 - self.c) * 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