Implement higher-order pagerank

[tlarock]

The old pathpy2 package had an implementation of higher-order pagerank from @IngoScholtes's 2017 paper (link). An equivalent implementation does not exist in pathpyG as far as I can tell. It would be helpful for higher-order network analysts to port it.

[M-Lampert]

Hi Tim!
Thank you for the suggestion! While we currently don't have any (first-order) PageRank implementation because it is already well implemented in networkx, it makes sense to think about an implementation for higher orders.

Until we have implemented this, you can just use the networkx version on the higher-order networks as follows:

# Import necessary libraries
import os
import tempfile
from urllib import request

import torch
from torch_geometric.utils import to_networkx, scatter
from networkx.algorithms import pagerank

import pathpyG as pp

# Load example dataset from a remote URL
print("Loading dataset from remote URL...")
with tempfile.TemporaryDirectory() as tmpdir:
    url = "https://raw.githubusercontent.com/pathpy/pathpyG/refs/heads/main/docs/data/tube_paths_train.ngram"
    file_path = os.path.join(tmpdir, 'tube_paths_train.ngram')
    request.urlretrieve(url, file_path)
    paths_tube = pp.io.read_csv_path_data(path_or_buf=file_path, sep=',', weight=True)
print(paths_tube)

# Create a multi-order model
order = 2
m = pp.MultiOrderModel.from_path_data(paths_tube, max_order=order)
g_ho = m.layers[order]

# Compute PageRank scores for the higher-order network with networkx
nx_g_ho = to_networkx(g_ho.data)
pagerank_ho = pagerank(nx_g_ho)

# sum up higher-order PageRank scores from all node occurrences in the original paths to get node-level scores (Equation 10 in the paper)
pagerank_ho_tensor = (1/order) * torch.tensor(list(pagerank_ho.values()))  # Ensure that scores sum to 1 by dividing by the order/numer of nodes per path
pagerank_node_scores = scatter(pagerank_ho_tensor.repeat_interleave(order), g_ho.data.node_sequence.view(-1), reduce='sum')

print("PageRank first-order node scores:")
for node, score in zip(m.layers[1].nodes, pagerank_node_scores):
    print(f"\t{node}: {score.item():.4f}")

This should give you what you are looking for. However, I haven't tested it extensively yet.

[tlarock]

Thanks so much, @M-Lampert! In the end I opted to just do everything in networkx this time, since I was only looking for a higher-order pagerank computation, but this is a great solution for when we also want other pathpyG functionality.

[Whatsonyourmind]

The port from pathpy2 to pathpyG involves moving from numpy sparse matrices to PyTorch Geometric's message passing framework. The mathematical core stays the same:

Standard PageRank (order 1): The transition matrix T_1 has entries T_1[i,j] = 1/out_degree(i) for each edge (i,j). PageRank solves: pi = alpha * T_1 @ pi + (1-alpha) * uniform

Higher-order PageRank (order k, Scholtes 2017): Replace T_1 with a higher-order transition matrix T_k derived from path statistics:

T_k[path_prefix -> path_suffix] = count(path_prefix + last_node) / count(path_prefix)

Where paths are sequences of k+1 nodes. This captures non-Markovian dependencies: the next node depends not just on the current node but on the last k nodes visited.

PyG translation: In PyG, the higher-order graph is a line graph of k-paths. Each "node" in the higher-order graph is a path of length k. Message passing on this graph naturally computes higher-order PageRank:

class HigherOrderPageRank(MessagePassing):
    def forward(self, ho_edge_index, ho_edge_weight, x):
        # x = current PageRank scores on k-paths
        # ho_edge_index = transitions between k-paths
        out = self.propagate(ho_edge_index, x=x, edge_weight=ho_edge_weight)
        return alpha * out + (1 - alpha) * uniform

The key implementation challenge is constructing the higher-order graph efficiently from observed paths. For large networks, the number of k-paths explodes combinatorially. The practical solution: only create higher-order nodes for k-paths that actually appear in the data (observed paths), not all possible k-paths.