Skip to content

About

A research project on the detectability transition of the Network Alignment Problem. We use an MCMC algorithm with parallel tempering to sample from the distribution of alignments and maximize the posterior probability of the correct alignment.

Topics

Resources

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

Detectability Transition in Network Alignment

Code and results for a research project studying the detectability phase transition in the network alignment problem, using a Bayesian / statistical-physics approach solved with MCMC parallel tempering.

Problem

Given a "blueprint" graph and several noisy, unlabeled copies of it, network alignment tries to recover the node correspondence (alignment) between the copies. This project models the problem as finding the alignment that minimizes an energy function $H$ (a mismatch score between the observed noisy copies), sampled with a Metropolis MCMC parallel-tempering scheme.

There is a temperature threshold $T_{crit}$, below which the MCMC replicas find equilibrium around the true alignment energy $H_{true}$, and above which they escape to a higher energy level. As the noise level used to generate the copies increases, the problem undergoes a detectability phase transition: after a certain nosie level threshold is surpassed, the true alignment of the networks becomes statistically undetectable, even for replicas below $T_{crit}$. This repository contains the simulation code, configuration sweeps, and analysis notebook used to locate and characterize said transition.

Relation to prior work

This study builds on the probabilistic network alignment model and MCMC parallel-tempering algorithm from Lázaro, Guimerà & Sales-Pardo, "Probabilistic alignment of multiple networks", Nature Communications 16, 3949 (2025). There, an unknown blueprint graph $L$ generates each observed copy by independently flipping edges with two error rates: $q$, the probability that a true edge is not copied, and $p$, the probability that a spurious edge is added where none exists in $L$. The algorithm samples the posterior $p(L, {\pi^k} \mid {A^k})$ via an energy $H = -\log p(\ldots)$, using MCMC with parallel tempering across replicas at different temperatures.

This study uses the same model and sampler, but restricted to a single-error-rate noise model: $p = 0$, i.e. noise acts only as non-observed (missing) edges, never as incorrectly added ones (remove_only=True throughout configs/). This is a meaningful special case since, in the $p \to 0$ limit, the posterior collapses to depend only on the edge overlap $O_{11}$, so the most plausible alignment reduces to maximizing shared edges with the blueprint. Studying the detectability transition in this limit isolates how the transition behaves under a "missing-data" noise model, decoupled from the additional information the general model gets from correctly-aligned non-edges ($O_{00}$).

Main finding: what actually drives the transition

The detectability transition is, at its core, about whether the ground-truth energy $H_{true}$ is still a statistically meaningful minimum at all.

For a graph with $N$ nodes, define $H_{1/N!}$ as the energy level at which $p(H) = 1/N!$. This is an energy so low that, searching blindly across all $N!$ possible node alignments at random, you'd expect to find at most one alignment reaching it. It is effectively the floor of what an uninformed random search over alignments can achieve. As the noise level increases, this floor drops relative to $H_{true}$.

  • While $H_{true} < H_{1/N!}$ (lower noise), the true alignment sits below the floor: it is a genuine, statistically rare minimum. Replicas at temperatures below $T_{crit}$ can equilibrate there, and the true alignment is detectable.
  • Once $H_{1/N!}$ crosses below $H_{true}$ (higher noise), the floor itself becomes lower than the ground truth. $H_{true}$ is no longer an exceptional minimum — an equally good or better energy is expected to be reachable by chance alone. From this point on, $H_{true}$ becomes undetectable by any replica at any temperature, i.e. lowering the temperature no longer helps, because the problem isn't thermal escape, it's that the signal itself has been swamped by the noise floor. Replicas below $T_{crit}$ stabilize around $H_{1/N!}$ instead of $H_{true}$.

In other words, $T_{crit}$ governs when a replica can find the true alignment given that it is still the best available minimum; the $H_{true}$ vs. $H_{1/N!}$ crossing governs whether there is still a true alignment left to find. The latter is the fundamental, temperature-independent limit on detectability. This comparison is computed in plots/theor_H_true.dat, plots/theor_H_lowend_gauss.dat / plots/theor_H_lowend_hypergeom.dat, and plots/avg_H_lowend_fit.dat, and visualized in figures/lowend_energs.pdf.

Repository structure

Path Description
functions.py Core library: noisy-copy generation, energy function $H$, MCMC parallel-tempering sampler, and plotting/analysis utilities.
run_mcmc.py CLI entry point to run the MCMC parallel-tempering algorithm from a JSON config.
sample_energy_distribution.py CLI entry point to sample the energy distribution of random (uninformed) alignments, used to estimate the noise floor $H_{1/N!}$ from the main finding above.
configs/ Configuration files for each experiment (noise level, graph size, replica count, etc.). default_config.json is the template — see configs/README.md for a full parameter reference.
plotting.ipynb Notebook that generates every figure in the study from the precomputed summary data in plots/.
plots/ Precomputed summary statistics (.dat) — theoretical/empirical accuracy, critical temperature, energy vs. temperature, etc. Sufficient to reproduce all main figures without the raw sweep data.
figures/ Final result figures (PDF): alignment accuracy, energy statistics per temperature.
test_run.csv Example output of a single MCMC run, for reference on the results format.
requirements.txt Python dependencies.

Data availability

The raw parameter-sweep output (LowTemp/, one CSV per noise level/replica/seed, ~10 GB total) and intermediate energy-distribution samples (Dists/, ~80 MB) are not included in this repository due to their size. They can be:

  • regenerated locally with run_mcmc.py / sample_energy_distribution.py and the configs in configs/, or
  • made available on request (dadi.svet@gmail.com).

The .dat files in plots/ already contain the summary statistics extracted from that raw data, so all figures in plotting.ipynb are reproducible without it.

Setup

python -m venv .venv && source .venv/bin/activate
pip install -r requirements.txt

Usage

Run a single MCMC parallel-tempering experiment, after setting up its parameters inside a config file:

python run_mcmc.py -config configs/default_config.json -filename my_run.csv

To estimate the energy distribution for a given configuration, run the following command after setting up the corresponding config file:

python sample_energy_distribution.py -config configs/default_config.json -filename my_dist.csv

Modify or create a config file in configs/ to change the noise level, graph size, number of replicas, or number of MCMC steps. Results are written as CSV to the output_dir specified in the config, details on every parameter can be found in the .md file inside configs/.

Set load_pkl/pkl_path in the config to reuse the exact blueprint and observations pickled by a prior run, so the sampled distribution is directly comparable to that run's $H_{true}$.

To explore results and regenerate figures, open plotting.ipynb.

License

MIT — see LICENSE.

About

A research project on the detectability transition of the Network Alignment Problem. We use an MCMC algorithm with parallel tempering to sample from the distribution of alignments and maximize the posterior probability of the correct alignment.

Topics

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages