boostorg / boostorg/graph

Implementing personalized PageRank for graph node scoring.

Open
#493 22 comments 1 reaction 2 assignees Claimed by @Becheler View on GitHub
algorithm
Dominant language
C++
Stars
392
Forks
239
Avg merge
1d 11m
Merged PRs (30d)
20

Description

### Before filing

- [x] I searched the [existing issues](https://github.com/boostorg/graph/issues?q=is%3Aissue) and did not find a duplicate.
- [x] This is a concrete proposal, not an open-ended design question.

### Kind of addition

- [x] New algorithm
- [ ] New data structure
- [ ] New property map or utility
- [ ] New I/O format reader or writer
- [ ] Extension to an existing component
- [ ] Performance improvement
- [ ] Other (specify below)

### Motivation

Following preliminary discussion in #492 , this proposal aims to bring the popular personalized node scoring/ranking algorithm to BGL. Personalized node scoring can be used to score nodes with respect to their structural proximity to a (weighted) set of seed nodes, so it can be used for overlapping community member scoring and ranking. It can also be used as a building block for more complex community detection schemes that satisfy theoretical properties like finding structural communities of low conductance given that the seed nodes lie closely together. Finally, node scores can be used for link prediction by starting from one node and finding structural close alternatives.

The proposal below presents some basic information for bringing these kinds of methods, and can be used as future basis for also implementing more spectral graph filters (not to be confused with full-blown spectral processing in that spectral filters act on eigenvalue-based properties by actually working only on the vertex domain for near-linear instead of quadratic time complexity).

### Proposed addition

In linear algebra terms, the algorithm implements the iterative scheme:

$p = (1-dmp)Ap+dmp p_0$

where A is broadly a normalized graph adjacency matrix, dmp is the equivalent of the dampening factor (equal to 1-restart probability of equivalent random walk with restart schemes), and $p_0$ a starting personalization vector. As an API, this would mainly follow the existing `page_rank` interface:

```cpp
template
void personalized_page_rank(const Graph& g, RankMap rank_map, Done done,
typename property_traits::value_type damping,
typename graph_traits::vertices_size_type n,
Normalization normalization,
Optimizer optimizer,
RankMap1 rank_map1,
RankMap2 rank_map2);
```

Simplifications analogous to `page_rank`'s will be added, for example so that `done` uses some common default (see below for planned options for convergence tracking; it is not as simple a problem as it appears).

**Important differences:**

A. `rank_map` will hold both input personalization $p_0$ and the eventually outputted $p$, in alignment with `page_rank`'s interface. This can change but I think it's elegant. Two more storage containers for node values are inserted, as we need to keep track the previous and next node values, as well s the personalization. All vertex value containers would be `ReadWritePropertyMap`s.

B. I am proposing that the default for `done` should not be a fixed number of iterations, as this creates a high computational overhead or may not be enough for robustness in scoring or rank order. Since I have worked on research determining robust stopping orders [2], I am proposing implementation of three different schemes, of which the first one would be the default, the second an alternative when correct ranking order does not matter as much as correct scoring, and the third is a practically unknown but a more theoretically rigorous version of the first:

- Run for `max(10, ceil(1/dmp))` iterations to account for most random walks of the equivalent random walk with restart scheme per [2]
- Use `mean(abs(p-p_previous))

This is similar to the `page_rank` algorithm.

### Prior art

- [x] Reference paper or textbook (cite below)
- [x] Implementation in another library (link below)
- [ ] None / original idea

References:

Introductory paper is [1], but the proposal aims to follow the implementation of [3], which different from the original paper by adding options for more recent esearch results (see above). The stopping criteria would be determined per [2].

1. https://api.semanticscholar.org/CorpusID:1508503
2. 10.1109/ASONAM49781.2020.9381435
3. https://github.com/MKLab-ITI/pygrank/blob/master/pygrank/algorithms/filters/adhoc/pagerank/pagerank.py

### Are you willing to contribute?

- [x] I'd like to submit the implementation as a pull request.
- [ ] I can help with review or testing, but not the implementation.
- [ ] I'm only proposing the idea.

**Edit:** typo fixing

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.