Network Propagation

A foundational algorithm that simulates a random walker traversing a biological network from a set of seed nodes, such as known drug targets. At each step, the walker has a fixed probability of returning to the seeds, ensuring the signal remains localized. This diffusion kernel computes a stationary distribution where nodes frequently visited by the walker receive higher scores, effectively prioritizing proteins in the local neighborhood of the seeds. The restart parameter controls the trade-off between exploration and localization.

A continuous-time analog of random walks modeled after the physical process of heat spreading through a material. The heat kernel solves the diffusion equation on the graph Laplacian, allowing information to flow outward from seed nodes over time. Unlike discrete random walks, the heat kernel provides a smooth, time-dependent ranking that captures multi-scale neighborhood structures. It is particularly effective for identifying disease modules—clusters of interconnected proteins that collectively contribute to a disease phenotype.

Biological interaction networks are inherently noisy, containing false positive and false negative edges. Network propagation acts as a low-pass graph filter, smoothing noisy node-level measurements by averaging signals across connected neighbors. This denoising property is critical when integrating genome-wide association study (GWAS) hits or differential expression data, where individual gene-level statistics are unreliable. The smoothed signal amplifies the true biological signal while suppressing spurious noise.

Advanced implementations propagate information across heterogeneous networks containing multiple node types, such as drugs, proteins, diseases, and side effects, and multiple edge types, such as physical binding, co-expression, and genetic association. Algorithms like Bi-Random Walk or Heterogeneous Graph Attention Networks learn layer-specific propagation weights, allowing the model to differentially prioritize information flow through protein-protein interaction edges versus drug-target edges. This captures complex polypharmacology relationships.

Standard propagation treats all edges equally, but biological interactions have varying confidence levels and tissue specificity. Edge-weighted propagation incorporates prior knowledge, such as interaction confidence scores from STRING or tissue-specific expression correlation, to bias the information flow. Edges with higher weights conduct more signal, ensuring that propagation respects context-specific biology. This prevents signal leakage through ubiquitously expressed housekeeping interactions and focuses the search on relevant tissue compartments.

After propagation scores are computed, a connected subgraph extraction step identifies tightly interconnected high-scoring nodes. Algorithms like heinz or local modularity optimization extract disease modules—functional units where the aggregated perturbation causes the disease phenotype. These modules are then screened against drug-target databases to identify compounds whose targets lie within or adjacent to the module, directly generating testable repurposing hypotheses.