Usage

The public API.

page_rank(*, adj=None, edge_index=None, num_nodes=None, add_identity=False, max_iter=1000, alpha=0.05, epsilon=0.0001, x0=None, use_tqdm=False, device=None)

Compute page rank by power iteration.

Parameters

• adj (Optional[Tensor]) – the adjacency matrix, cf. torch_ppr.utils.prepare_page_rank_adjacency(). Preferred over edge_index.

• edge_index (Optional[LongTensor]) – shape: (2, m) the edge index of the graph, i.e, the edge list. cf. torch_ppr.utils.prepare_page_rank_adjacency()

• num_nodes (Optional[int]) – the number of nodes used to determine the shape of the adjacency matrix. If None, and adj is not already provided, it is inferred from edge_index.

• add_identity (bool) – whether to add an identity matrix to A to ensure that each node has a degree of at least one.

• max_iter (int) – max_iter > 0 the maximum number of iterations

• alpha (float) – 0 < alpha < 1 the smoothing value / teleport probability

• epsilon (float) – epsilon > 0 a (small) constant to check for convergence

• x0 (Optional[Tensor]) – shape: (n,) the initial value for x. If None, set to a constant $1/n$ vector, cf. torch_ppr.utils.prepare_x0(). Otherwise, the tensor is checked for being valid using torch_ppr.utils.validate_x().

• use_tqdm (bool) – whether to use a tqdm progress bar

• device (Union[None, str, device]) – the device to use, or a hint thereof

Return type

Tensor

Returns

shape: (n,) or (batch_size, n) the page-rank vector, i.e., a score between 0 and 1 for each node.

personalized_page_rank(*, adj=None, edge_index=None, add_identity=False, num_nodes=None, indices=None, device=None, batch_size=None, **kwargs)

Personalized Page-Rank (PPR) computation.

Note

this method supports automatic memory optimization / batch size selection using torch_max_mem.

Parameters

• adj (Optional[Tensor]) – shape: (n, n) the adjacency matrix, cf. torch_ppr.utils.prepare_page_rank_adjacency()

• edge_index (Optional[LongTensor]) – shape: (2, m) the edge index, cf. torch_ppr.utils.prepare_page_rank_adjacency()

• num_nodes (Optional[int]) – the number of nodes used to determine the shape of the adjacency matrix. If None, and adj is not already provided, it is inferred from edge_index.

• add_identity (bool) – whether to add an identity matrix to A to ensure that each node has a degree of at least one.

• indices (Optional[Tensor]) – shape: (k,) the node indices for which to calculate the PPR. Defaults to all nodes.

• device (Union[None, str, device]) – the device to use

• batch_size (Optional[int]) – batch_size > 0 the batch size. Defaults to the number of indices. It will be reduced if necessary.

• kwargs – additional keyword-based parameters passed to torch_ppr.utils.batched_personalized_page_rank()

Return type

Tensor

Returns

shape: (k, n) the PPR vectors for each node index

The following shows an example where a custom adjacency matrix is provided. For illustrative purposes, we randomly generate one:

>>> import torch
>>> adj = (torch.rand(300, 300)*10).round().to_sparse()

Next, we need to ensure that the matrix is row-normalized, i.e., the individual rows sum to 1. Here, we re-use a utility method provided by the library:

>>> from torch_ppr.utils import sparse_normalize
>>> adj_normalized = sparse_normalize(adj, dim=0)

Finally, we can use this matrix to calculate the personalized page rank for some nodes

>>> from torch_ppr import personalized_page_rank
>>> indices = torch.as_tensor([1, 2], dtype=torch.long)
>>> ppr = personalized_page_rank(adj=adj_normalized, indices=indices)