Skip to content

About

No description or website provided.

Topics

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

90 Commits

Folders and files

Repository files navigation

The University of St Andrews

Understanding and Evaluating Variants of the McSplit Algorithm for the Maximum Common Subgraph Problem

Tara Relan (250016623)

Supervisor: Dr. Ruth Hoffmann

August 11th 2026

Contents

Acknowledgements

This repository contains reimplementations of the following algorithms:

All implementations were re-written in C++ based on the published papers and validated against the authors' reference binaries. Reference binaries are included in reference/ for validation purposes only and remain the property of their respective authors.

Reference Implementations

Original author code used for validation (Section 4.1 of the dissertation) was sourced as follows:

Algorithm Source
McSplit ijcai2017-partitioning-common-subgraph
McSplit+RL McSplit-RL
McSplit+LL McSplit-LL
McSplit+DAL SIGMOD25-MCSS (./McSplitDAL subfolder)
McSplit+DSB mcsplit-dsb
RRSplit SIGMOD25-MCSS (./RRSplit subfolder)
SymSplit symsplit
McSplit-down No separate code: the McSplit reference run with -b (--big-first)

McSplit+RL Pair, McSplit+RL Rate and McSplit+RL-down have no reference implementation; they are validated by solution-size agreement and switch-off tests instead (see the dissertation).

Your local reference/ folder should be laid out as:

reference/
├── mcsplit/
│   └── mcsp      # compiled reference binary
├── mcsplit-rl/
│   └── mcsp+RL
├── mcsplit-ll/
│   └── mcsp+ll
├── mcsplit-dal/
│   └── mcspDAL
├── mcsplit-dsb/
│   └── bin/
│       └── run.o
├── rrsplit/
│   └── mcsp
└── symsplit/
    └── bin/
        └── run.o

These paths match what hpc/run_instance.sh calls in --with-ref mode - if a reference binary isn't at the expected path, that algorithm's ref-mode comparison will silently return empty reference fields rather than erroring, so it's worth checking each path exists after building.

User Manual

This manual describes how to build and run the unified MCS solver framework. The framework implements seven algorithms (McSplit, McSplit+RL, McSplit+LL, McSplit+DAL, McSplit+DSB, RRSplit, SymSplit) and their ablation variants within a single binary.


Requirements

  • g++ 11.4.1 or later with C++17 support
  • The MIVIA/BI/LV instance set, unzipped into instances/
  • GNU Make
  • POSIX-compatible shell (bash)
  • Boost library (for HPC submission scripts only)

Building

From the project root:

make -C solvers

This produces solvers/bin/mcsp. To rebuild from scratch:

rm -f solvers/bin/mcsp
make -C solvers

Running a Single Instance

./solvers/bin/mcsp -A <algorithm> -t <timeout> [-l] [-i] [-s] -q <graph1> <graph2>

Options

Flag Long form Description
-q --quiet Suppress per-instance output; print only the solution size
-d --dimacs Read graphs in DIMACS format (default: MIVIA binary)
-l --lad Read graphs in LAD format (default: MIVIA binary)
-i --directed Treat graphs as directed
-a --labelled Use both vertex and edge labels
-x --vertex-labelled Use vertex labels only (no edge labels)
-t <seconds> --timeout Abort search after this many seconds (0 = no limit)
-A <algo> --algorithm Algorithm to run (see algorithm table below)
-s --swap-smaller Uniform preprocessing: make the smaller graph G for every algorithm (see Validation Runs vs Comparison Runs). Without it, each algorithm follows its reference: only RRSplit and SymSplit swap
-p <prefix> --proof Write a VeriPB model and proof to <prefix>.opb and <prefix>.pbp (see Proof Logging)

Available Algorithms

Flag Algorithm
mcsplit McSplit (baseline)
down McSplit-down (top-down / "big-first" search)
rl McSplit+RL
rl_pair McSplit+RL with per-pair (v,w) scoring instead of per-vertex
rl_rate McSplit+RL with rate-normalised reward
rl_down McSplit+RL branching combined with McSplit-down's search strategy
ll McSplit+LL (full: LSM + LUM)
ll_lsm McSplit+LL with LSM only
ll_lum McSplit+LL with LUM only
dal McSplit+DAL (hybrid alternating policy)
dal_rl McSplit+DAL with RL policy locked
dal_dal McSplit+DAL with DAL policy locked
dsb McSplit+DSB (RL-gated bound)
dsb_always McSplit+DSB with bound always on
dsb_never McSplit+DSB with bound always off
rrsplit RRSplit (all three reductions)
rrsplit_noveq RRSplit without vertex-equivalence reduction
rrsplit_nomax RRSplit without maximality reduction
rrsplit_nobound RRSplit without tighter bound
symsplit SymSplit (variable + value symmetry)
symsplit_varonly SymSplit with variable symmetry only
symsplit_valonly SymSplit with value symmetry only

Examples

MIVIA binary format:

./solvers/bin/mcsp -A mcsplit -t 1000 -q \
    instances/MIVIA/mcs10/bvg/b03/mcs10_b03_s40.A00 \
    instances/MIVIA/mcs10/bvg/b03/mcs10_b03_s40.B00

SIP LAD format (BI - biochemical reactions, directed):

./solvers/bin/mcsp -A rrsplit -t 1000 -l -i -q \
    instances/SIP/biochemicalReactions/001.txt \
    instances/SIP/biochemicalReactions/002.txt

SIP LAD format (LV):

./solvers/bin/mcsp -A dal_dal -t 0 -l -q \
    instances/SIP/LV/g2 \
    instances/SIP/LV/g5

Output Format

One line, space-separated:

<unified_size> <unified_edges> <unified_nodes> <unified_time> <unified_aborted> <unified_nodes_to_best> <unified_time_to_best> <unified_cut_branches> <unified_bound_pruned> <unified_sym_pruned> <unified_bidomain_mean> <unified_bidomain_max>
Field Description
unified_size Solution size (MCS vertex count)
unified_edges Edges in the common subgraph
unified_nodes Search tree nodes explored
unified_time Wall-clock time in seconds
unified_aborted 1 if timed out before proving optimality, 0 if completed
unified_nodes_to_best Nodes explored before best incumbent found
unified_time_to_best Time at which best incumbent was found (seconds)
unified_cut_branches Total branches pruned
unified_bound_pruned Branches pruned by the algorithm's bound
unified_sym_pruned Branches pruned by symmetry or redundancy reduction
unified_bidomain_mean Mean number of bidomains per search node
unified_bidomain_max Largest number of bidomains at any search node

When run with --with-ref on HPC (see below), six extra fields are appended: ref_size, ref_nodes, ref_time, ref_bidomain_mean, ref_bidomain_max, match (PASS/FAIL/MISSING_DATA).


Validation Runs vs Comparison Runs

The framework is used in two ways, which need different setups:

  • Validation (fidelity): does each re-implementation match its reference? Every algorithm copies its reference's preprocessing exactly, so any difference in nodes explored can only be an implementation mistake. This is the default (no -s), run with --with-ref on HPC.
  • Comparison (performance): which algorithm design is actually better? Here every algorithm should get the same preprocessing, otherwise part of a difference can come from setup rather than search. In particular, the RRSplit and SymSplit references put the smaller graph first and the others do not. -s / --swap applies that step to every algorithm. Swapping never changes the solution size (MCS(G, H) = MCS(H, G)), only the search effort. Comparison runs don't need the reference.

Directed graphs (BI): the RRSplit and SymSplit references ignore edge direction and can return invalid solutions on directed instances. The re-implementations here are direction-aware (direction-split bidomains and direction-aware equivalence classes), so on BI they deliberately differ from their references: validate them there against McSplit's solution sizes, not against the reference. On undirected datasets (MIVIA, LV) they behave exactly as before.

Proof Logging

With -p <prefix>, the solver writes a pseudo-Boolean model of the instance to <prefix>.opb and a VeriPB 3 proof to <prefix>.pbp. The proof certifies the reported solution size independently of the solver:

./solvers/bin/mcsp -A mcsplit -d -q -p proof g1.dimacs g2.dimacs
veripb proof.opb proof.pbp

The model has a variable x<v>_<w> for each label-compatible pair (vertex v of the smaller graph mapped to w) and x<v>_null for v left unmapped, and minimises the number of unmapped vertices. On undirected unlabelled graphs, it's exactly the encoding used by CakePB's verified checker for maximum common induced subgraph, cake_pb_mcis, so proofs can also be checked end to end by a formally verified checker that builds the model from the LAD files itself:

./solvers/bin/mcsp -A rrsplit -l -q -p proof g1.lad g2.lad
veripb --elaborate proof.elab.pbp proof.opb proof.pbp
cake_pb_mcis g1.lad g2.lad proof.elab.pbp

Here the smaller graph must come first, since cake_pb_mcis doesn't swap them. A complete run ends with s VERIFIED BOUNDS k <= obj <= k, so the maximum common induced subgraph has |V(G)| - k vertices. A run stopped by -t only certifies its best solution (0 <= obj <= k).

Proof logging is supported for every algorithm. The RRSplit and SymSplit variants work on undirected unlabelled graphs only, since those algorithms ignore labels and direction:

  • McSplit's bidomain bound (all supported algorithms) is justified by summing at-least-one and at-most-one constraints.
  • DSB's bound (dsb*): the logger recomputes the edge and non-edge counting bounds itself, and justifies them by degree reasoning inside each bidomain.
  • LUM's leaf matching (ll, ll_lum, dal, dal_dal): each leaf pair is justified by redundance under the current branch. The leaf's alternatives are ruled out one at a time, each by moving the leaf onto its partner.
  • RRSplit's vertex-equivalence reduction and its tighter bound (rrsplit_nomax), and SymSplit's variable symmetry (symsplit_varonly), which is the same ordering. With these, the proof first loads a lexicographic order on the images, in branching order, so that it can use dominance. Before search, dominance derives an ordering on each class of twins (vertices with the same neighbourhood), with the swap of two twins as the witness. The tighter bound is then a counting argument over that ordering.
  • SymSplit's value symmetry (symsplit_valonly, symsplit): at each node, before any branch is explored, each value that has a smaller twin still available is ruled out, with the swap of the two twins in H as the witness. On its own, that's redundance under the current branch. With variable symmetry as well (symsplit), the smaller twin can lie below the image of v's previous twin, and then the symmetric solution that respects the twin ordering is in an earlier branch, which redundance can't appeal to. So for symsplit, value symmetry is by dominance under the lexicographic order. This works because SymSplit always branches on the smallest vertex of a bidomain, so each rewrite makes that vertex's image smaller and otherwise only touches later vertices.
  • The maximality reduction (rrsplit*, symsplit*): when matching v to w splits no bidomain, v->w is forced under the current branch. As for LUM, v's alternatives are ruled out one at a time, each by moving v onto w. With the twin ordering, only v's later values (and, for SymSplit, which skips the exclude branch, leaving v unmapped) are ruled out, by dominance under the lexicographic order: v is the smallest vertex of its bidomain, and whoever held w is in the same bidomain. The proof uses one clause per incompatible pair of assignments, so it grows as O(|V(G)|² |V(H)|²) and is practical for graphs up to a few dozen vertices.

To test proof logging, solvers/test/check_proofs.py runs every algorithm with -p on generated instances (random, directed, labelled, MIVIA binary, trees with many leaves, and stars with large twin classes) and on the stored instances in solvers/test/instances, and checks that VeriPB certifies exactly the size the solver reports. With --cake, it also checks the undirected unlabelled ones with cake_pb_mcis. solvers/test/mutants.py builds mutated solvers and loggers, each wrong in a different way, and checks that every one is caught:

cd solvers
make check-proofs                                      # or: python3 test/check_proofs.py -n 3 -A symsplit
make check-proofs CAKE_PB_MCIS=~/cakepb-dev/graph/cake_pb_mcis
make check-mutants

Apart from tiny, the smallest instance where it happens at all, the stored instances are ones where full SymSplit's value symmetry skips a value in favour of a twin below the image of v's previous twin, and the search below that value can't be refuted by unit propagation, so they're the cases that need dominance rather than redundance.


Running Experiments on HPC (Hypatia)

1. Sync files to Hypatia

rsync -avu --progress \
  "[source-directory]/" \
  [account]@hypatia.st-andrews.ac.uk:work/[target-directory]/

2. Connect to Hypatia

ssh [account]@hypatia.st-andrews.ac.uk

3. Build on Hypatia

cd ~/work/[target-directory]/solvers && rm -f bin/mcsp && make

4. Submit scripts

Submit one algorithm at a time so as not to hit the QOS limits. Each script accepts an optional --with-ref flag (validation) and an optional --swap flag (uniform preprocessing for comparison runs - see Validation Runs vs Comparison Runs); the two can be combined. Swap runs write to separate ..._swap result folders. --with-ref also runs the corresponding reference binary and record a PASS/FAIL/MISSING_DATA comparison alongside the unified solver's results.

cd ~/work/[target-directory]

# plain mode
bash hpc/submit_mivia.sh mcsplit
bash hpc/submit_bi.sh dsb
bash hpc/submit_lv.sh symsplit

# with reference comparison (validation)
bash hpc/submit_mivia.sh mcsplit --with-ref
bash hpc/submit_bi.sh dsb --with-ref
bash hpc/submit_lv.sh symsplit --with-ref

# uniform preprocessing (comparison) - results in hpc/results/<algo>_<dataset>_swap/
bash hpc/submit_bi.sh dsb --swap
bash hpc/submit_lv.sh symsplit --swap

run_instance.sh skips any instance pair whose output CSV already exists, so to re-run an algorithm, first move its old result folder aside (e.g. mv hpc/results/dsb_bi_with_ref hpc/results_old/).

Wait for each array to finish (squeue -u [account]) before submitting the next, to stay within QOS limits.

5. Monitoring progress

squeue -u [account]                                    # job status
ls hpc/results/<algo>_<dataset>/ | wc -l               # instances completed (plain mode)
ls hpc/results/<algo>_<dataset>_with_ref/ | wc -l      # instances completed (ref mode)
ls hpc/results/<algo>_<dataset>_swap/ | wc -l          # instances completed (swap mode)
head -5 -q hpc/results/<algo>_<dataset>/*.csv          # spot-check output

e.g. ls hpc/results/mcsplit_mivia/ | wc -l or ls hpc/results/dsb_bi_with_ref/ | wc -l.

6. Collect and merge results

Per-instance CSVs (one file per instance pair, no header) are merged into a single file with the correct header using hpc/merge_results.sh:

bash hpc/merge_results.sh <algo> <dataset> [--with-ref] [--swap]

e.g.:

bash hpc/merge_results.sh dsb bi                   # → hpc/results/dsb_bi_all.csv
bash hpc/merge_results.sh symsplit lv --with-ref   # → hpc/results/symsplit_lv_with_ref_all.csv
bash hpc/merge_results.sh dsb bi --swap            # → hpc/results/dsb_bi_swap_all.csv

Plain-mode and swap-mode header (15 columns):

instance_a,instance_b,algo,unified_size,unified_edges,unified_nodes,unified_time,unified_aborted,unified_nodes_to_best,unified_time_to_best,unified_cut_branches,unified_bound_pruned,unified_sym_pruned,unified_bidomain_mean,unified_bidomain_max

Ref-mode header (21 columns):

instance_a,instance_b,algo,unified_size,unified_edges,unified_nodes,unified_time,unified_aborted,unified_nodes_to_best,unified_time_to_best,unified_cut_branches,unified_bound_pruned,unified_sym_pruned,unified_bidomain_mean,unified_bidomain_max,ref_size,ref_nodes,ref_time,ref_bidomain_mean,ref_bidomain_max,match

7. Copy results back to local machine

scp [account]@hypatia.st-andrews.ac.uk:work/[target-directory]/hpc/results/*_all.csv \
    "[source-directory]/"

Adding a New Algorithm

  1. Implement the algorithm in a new .cpp file in solvers/src/, following the pattern of existing implementations (entry point returning std::vector<VtxPair>).
  2. Register the dispatch in solvers/src/main.cpp - add an else if (algo == "my_algo") branch.
  3. Add the file to the compiler command in solvers/Makefile.
  4. If a reference binary exists, add it under reference/my_algo/ (see Reference Implementations for the expected layout) and add a case for it in hpc/run_instance.sh under the WITH_REF=1 block.
  5. Rebuild and validate:
make -C solvers
bash hpc/submit_mivia.sh my_algo --with-ref

About

No description or website provided.

Topics

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages