Random Walk Graph Propagation

---
name: random-walk-graph-propagation
description: 'Use when you have: (1) a set of spectral library matches (seed identities)
  mapped to molecular structures, (2) a candidate structure graph derived from in
  silico fragmentation (e.'
license: CC-BY-4.0
metadata:
  edam_operation: http://edamontology.org/operation_3357
  edam_topics:
  - http://edamontology.org/topic_0593
  - http://edamontology.org/topic_3172
  - http://edamontology.org/topic_3520
  tools:
  - Python
  - pyrwr
  - MetFrag
  - ChemWalker
  techniques:
  - mass-spectrometry
  license_tier: open
  provenance_tier: literature
derived_from:
- doi: 10.1093/bioinformatics/btad078
  title: ChemWalker
evidence_spans:
- ChemWalker is a python package
- using [random walk](https://github.com/jinhongjung/pyrwr)
claims: []
provenance:
  collection: https://w3id.org/holobiomicslab/asb-skill/collection/metabolomics/v2
  assembled_by: scripts/collect_metabolomics_collection.py
  sources:
  - build: coll_chemwalker_cq
    doi: 10.1093/bioinformatics/btad078
    title: ChemWalker
  dedup_kept_from: coll_chemwalker_cq
schema_version: 0.2.0
attribution:
  generator: AgenticScienceBuilder
  original_doi: 10.1093/bioinformatics/btad078
  all_source_dois:
  - 10.1093/bioinformatics/btad078
  zenodo_doi: 10.5281/zenodo.20794027
  curators: []
  promoter: Louis-Félix Nothias
  sponsor: CNRS & Université Côte d'Azur
---

# random-walk-graph-propagation

## Summary

Propagate spectral library match identities through candidate structures generated by in silico fragmentation using random walk with restart (RWR) algorithms. This skill enables personalized node ranking across molecular structure networks to improve annotation confidence by diffusing known spectral matches through structurally related candidates.

## When to use

Apply this skill when you have: (1) a set of spectral library matches (seed identities) mapped to molecular structures, (2) a candidate structure graph derived from in silico fragmentation (e.g., MetFrag output) where edges represent fragmentation relationships, and (3) a need to propagate confidence scores or annotations from high-confidence matches to related but unconfirmed structures to improve metabolite annotation coverage and ranking.

## When NOT to use

- Input graph is not acyclic or fragmentation relationships are not already established; RWR requires a well-formed graph structure.
- Spectral library matches are absent or too sparse (< 5–10% of candidate structures); propagation requires sufficient seed coverage to diffuse meaningfully.
- Candidate structures and fragmentation relationships are not available; this skill requires both node and edge definitions from in silico fragmentation tools.

## Inputs

- Candidate structure graph (nodes=structures, edges=fragmentation relationships; tab-separated edge list or adjacency format)
- Spectral library match seeds (node IDs mapped to known compound identities)
- Graph type specification (directed or undirected; fragmentation graphs are typically directed)
- RWR parameters: restart probability c (default 0.15), error tolerance epsilon (default 1e-9), max iterations

## Outputs

- RWR score vector (node ID vs. propagated match score) for each seed or seed set
- Ranked candidate structures by propagated identity score
- Annotated structure list with propagated confidence scores
- Identity assignment improvements (structures elevated from unmatched to matched status)

## How to apply

Construct a graph representation where nodes are candidate structures and edges are fragmentation relationships. Load spectral library matches as seed nodes with known identities. Initialize a random walk engine (e.g., pyrwr RWR class) on the candidate structure graph, specifying the restart probability (c parameter, typically 0.15). Execute the RWR computation from each seed node to generate a score vector across all candidate structures, propagating match confidence proportional to proximity in the fragmentation graph. Rank candidates by their propagated scores and filter by a similarity or restart probability threshold to balance sensitivity and specificity. Collect and export ranked structures with their propagated identity scores for downstream validation.

## Related tools

- **pyrwr** (Implements Random Walk with Restart (RWR) and Personalized PageRank (PPR) algorithms on arbitrary graph types; used to compute personalized node ranking and score propagation from seed nodes.) — https://github.com/jinhongjung/pyrwr
- **MetFrag** (Generates candidate structures and in silico fragmentation relationships (edges in the candidate structure graph) used as input to RWR propagation.) — https://ipb-halle.github.io/MetFrag/projects/metfragcl/
- **ChemWalker** (Orchestrates spectral library match propagation through in silico fragmentation candidates using RWR; combines MetFrag fragmentation output with spectral library seeds and pyrwr propagation.) — https://github.com/computational-chemical-biology/ChemWalker

## Examples

```
from pyrwr.rwr import RWR; rwr = RWR(); rwr.read_graph('candidate_structures.tsv', 'directed'); scores = rwr.compute(seed=10982, c=0.15, epsilon=1e-9, max_iters=100)
```

## Evaluation signals

- Propagated scores are non-negative and sum to a predictable total (related to restart probability and graph structure); verify via scoring vector invariants.
- Seed nodes (known spectral matches) retain high scores (typically > 0.5 × mean score or > restart probability c); seeds should not be downranked by propagation.
- Structurally similar candidates (neighbors in fragmentation graph) receive higher scores than distant structures; verify via correlation between graph distance and score rank.
- Propagated identities improve over baseline (in silico fragmentation alone); measured by increase in annotation recall and precision on a held-out validation set.
- Algorithm convergence is achieved within max_iters and error tolerance epsilon; monitor iteration count and residual norm from power iteration output.

## Limitations

- RWR is defined on positively weighted networks only; negative or zero edge weights are not supported and will cause incorrect propagation.
- Graph sparsity affects propagation reach: isolated components or poorly connected subgraphs may not receive scores if seeds are absent in their component.
- Restart probability (c) is a critical tuning parameter; low c (< 0.05) favors distant neighbors (high diffusion) while high c (> 0.5) concentrates scores near seeds, and no universal optimum exists across all datasets.
- Redundant edges in the input graph have their weights summed; multiple fragmentation pathways to the same structure will be collapsed, potentially overweighting common fragments.
- Computational cost scales with graph size and iteration count; large candidate pools (> 100,000 structures) or dense fragmentation graphs may exceed memory or runtime constraints.

## Evidence

- [readme] ChemWalker is a python package to propagate spectral library match identities through candidate structures provided by _in silico_ fragmentation, using [random walk]: "propagate spectral library match identities through candidate structures provided by _in silico_ fragmentation, using random walk"
- [other] Load candidate structures from in silico fragmentation as a graph representation (nodes=structures, edges=fragmentation relationships). Load spectral library matches as seed identities mapped to initial structures. Initialize a random walk engine using pyrwr with the candidate structure graph. Execute random walk propagation starting from seed nodes (spectral matches) to propagate identity scores through the graph.: "Load candidate structures from in silico fragmentation as a graph representation (nodes=structures, edges=fragmentation relationships). Load spectral library matches as seed identities mapped to"
- [readme] Random Walk with Restart (RWR) is one of famous link analysis algorithms, which measures node-to-node proximities in arbitrary types of graphs (networks).: "Random Walk with Restart (RWR) is one of famous link analysis algorithms, which measures node-to-node proximities in arbitrary types of graphs"
- [readme] pyrwr aims to implement algorithms for computing RWR scores based on *Power Iteration* using numpy and scipy in Python. More specifically, pyrwr focuses on computing a single source RWR score vector w.r.t. a given query (seed) node, which is used for a personalized node ranking w.r.t. the querying node.: "computing a single source RWR score vector w.r.t. a given query (seed) node, which is used for a personalized node ranking w.r.t. the querying node"
- [readme] If there are redundant edges in an weighted network, their weights will be summed, e.g., 1   2   3 and 1   2   5 becomes 1   2   8: "If there are redundant edges in an weighted network, their weights will be summed"