Candidate Structure Ranking

candidate-structure-ranking

Summary

Rank in silico fragmentation candidate structures by propagating spectral library match identities through the candidate graph using random walk with restart (RWR). This skill redistributes confidence scores from known spectral matches across structurally related candidates, improving annotation precision when a direct spectral library hit is ambiguous or absent.

When to use

Apply this skill when you have (1) a set of candidate structures generated by in silico fragmentation (e.g., MetFrag output), (2) one or more seed nodes with known spectral library matches or identity scores, and (3) a fragmentation relationship graph connecting candidates. Use it to propagate identity confidence from high-confidence seeds to structurally proximal candidates, especially when direct spectral matching is uncertain or multiple candidates have similar mass spectra.

When NOT to use

• Candidate structures lack fragmentation relationships or structural connectivity; RWR requires a connected or near-connected graph to propagate scores meaningfully.
• No reliable seed nodes exist; RWR depends on high-confidence seeds to initialize the restart vector—random or uniformly uncertain seeds will produce uninformative rankings.
• Input is already a fully annotated, ranked candidate list from a single spectral library query; RWR is designed to enhance ambiguous or multi-candidate scenarios, not post-process final results.

Inputs

• candidate structure graph (edge-list format: source\ttarget or source\ttarget\tweight)
• seed node identifiers with spectral library match scores
• fragmentation relationship metadata (parent–fragment pairs, structural similarity edges)

Outputs

• ranked candidate structures with RWR scores
• node-to-node proximity matrix (optional)
• propagated identity confidence scores per candidate

How to apply

Construct a directed graph where nodes are candidate structures and edges represent fragmentation relationships (e.g., parent–fragment, isomer, or structural similarity links). Map spectral library matches to seed nodes with their associated match scores (e.g., cosine similarity). Initialize a Random Walk with Restart (RWR) engine using pyrwr with the candidate graph and a restart probability (typically c=0.15). Execute RWR starting from one or multiple seed nodes to compute personalized node scores across the graph; nodes nearer to high-scoring seeds accumulate higher scores. Rank all candidate structures by their final RWR scores. The restart probability controls the balance between propagating scores from seeds and local graph structure; lower restart probability allows more exploration.

Related tools

• pyrwr (Executes Random Walk with Restart (RWR) computation on the candidate structure graph to propagate seed node scores; supports both single-seed RWR and multi-seed Personalized PageRank queries.) — https://github.com/jinhongjung/pyrwr
• MetFrag (Generates candidate structures via in silico fragmentation; ChemWalker consumes MetFrag output (candidate structures and fragmentation trees) as input.) — https://ipb-halle.github.io/MetFrag/projects/metfragcl/
• ChemWalker (Python package integrating in silico fragmentation results with RWR-based ranking; orchestrates graph construction, seed mapping, and RWR execution.) — https://github.com/computational-chemical-biology/ChemWalker

Examples

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

Evaluation signals

• RWR score vector has length equal to the number of candidate nodes; all scores are non-negative and sum to approximately 1.0 (normalized probability distribution).
• Seed nodes have higher or equal RWR scores than non-seed candidates in the immediate neighborhood, reflecting the restart bias toward seeds.
• Ranking changes monotonically with restart probability (c): lower c values produce more dispersed scores (more exploration); higher c concentrates scores near seeds (more localization).
• Scores decrease with graph distance from seed nodes; a candidate two edges away typically scores lower than one edge away, unless alternative high-scoring paths exist.
• Convergence criterion (epsilon, typically 1e-9) is satisfied; power iteration stops within max_iters (typically ≤100), confirming numerical stability.

Limitations

• RWR requires a connected or weakly connected graph; isolated subgraphs or candidates unrelated to seed nodes receive near-zero scores and are not ranked meaningfully.
• Restart probability (c) and convergence tolerance (epsilon) are hyperparameters sensitive to the graph topology and must be tuned; no adaptive selection strategy is provided in ChemWalker or pyrwr.
• Score propagation is undirected with respect to chemical plausibility; RWR ranks by graph proximity alone and does not validate whether propagated candidates are chemically or biologically feasible analogs of seeds.
• Multiple seed nodes with conflicting scores may dilute the ranking signal; Personalized PageRank (multiple seeds) averages contributions, which can suppress minority hypotheses.
• Computational cost scales with graph size and number of iterations; large fragmentation trees (>10,000 nodes) may require GPU acceleration (PyRWR supports PyTorch GPU backend).

Evidence

• [readme] ChemWalker is a python package to propagate spectral library match identities through candidate structures provided by in silico fragmentation, using random walk: "ChemWalker is a python package to 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). 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). 3. Initialize a random walk engine using pyrwr with the"
• [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.: "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"
• [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 (networks)."
• [other] Collect and rank candidate structures by propagated match scores.: "Collect and rank candidate structures by propagated match scores."