Why the Starting Point Matters
A graph-clustering algorithm does not always find its answer in one step. Many methods repeatedly consider changes to a current partition, such as moving a vertex or merging groups, and accept changes according to an objective or update rule. The sequence of these decisions can depend on the order in which vertices are visited, the initial labels assigned to them, and random choices made along the way. Different paths can lead to different final partitions even when the graph and the nominal algorithm settings are unchanged.
This is not necessarily a software error. A greedy method may reach a local optimum: a partition for which none of the allowed individual changes improves the objective, even though a different sequence of changes would have reached another result. A random seed can make one run repeatable under a fixed implementation, but it does not make the optimization path uniquely determined by the graph alone.
The earlier material on stochasticity in community detection introduced variation across runs. Here the focus is on tracing that variation to initialization and execution order, and on recording enough information to repeat a run responsibly.
How Order and Initialization Alter an Optimization Path
Suppose an algorithm considers a candidate change to a partition and accepts it when that change improves an objective. Write the objective as \(Q(P)\), where \(P\) denotes a partition. For a proposed change from \(P\) to \(P'\), its gain is
If several changes are available, selecting one first changes the current partition and therefore changes which candidate gains are considered next. In a greedy algorithm, the order of consideration can also decide which equally good move is accepted first. Consequently, two paths can reach distinct stopping states. Stopping states need not have the same objective value, and even when their objective values match, their group memberships may differ.
A short justification makes the role of order explicit. Let \(T_u\) denote the update that considers vertex \(u\) in the current state. Updating \(u\) can change the labels or neighboring groups examined when processing \(v\). In general, therefore, applying the updates in opposite orders need not have the same result:
This noncommutativity is the basic reason that a different vertex order can produce a different path. A random seed may determine the order or tie-breaking choices, but it does not remove the path dependence. If the algorithm begins from a supplied partition, changing that partition can alter the candidate moves from the first iteration onward.
Worked Example: Two Different Partitions With the Same Modularity
Consider a hypothetical unweighted four-cycle with vertices \(A,B,C,D\) and edges \(AB, BC, CD, DA\). There are \(m=4\) edges, and every vertex has degree 2. For an undirected graph, modularity of a partition \(P\) is
where \(l_c\) is the number of edges internal to community \(c\), and \(d_c\) is the sum of degrees of vertices in that community.
Compare \(P_1=\{\{A,B\},\{C,D\}\}\) with \(P_2=\{\{A,D\},\{B,C\}\}\). In \(P_1\), each group has one internal edge and degree sum 4. Substitution gives
For \(P_2\), each group also has one internal edge and degree sum 4, so
The objective value does not distinguish these partitions. If a procedure starts in \(P_1\) and accepts no non-improving moves, it can retain \(P_1\); a different initialization or tie-breaking path may retain \(P_2\). The example does not say that every implementation will behave this way. It shows why an objective value alone does not encode the full route taken or identify a unique partition.
Seeds, Random Number Generators, and Exact Reruns
A seed is useful only in relation to the random-number generator and the way the software uses it. For a fixed generator and a fixed sequence of calls, setting the same seed ordinarily recreates the same pseudorandom sequence. But if the algorithm consumes those values in a different order, makes a different number of random calls, or uses parallel workers with separate random streams, the run can diverge despite having the same displayed seed.
The seed is not a complete record of a clustering analysis. A rerun can differ if the graph changes, vertex identifiers are reordered, weights are altered, the algorithm implementation changes, or settings such as the resolution parameter, stopping tolerance, or iteration limit are different. Parallel scheduling and differences between software or hardware environments can also affect results. Therefore, record the seed together with the run configuration and the exact graph input.
Worked Example: Interpreting Two Seeded Runs
Suppose a hypothetical program applies the same greedy modularity procedure to the same graph, but shuffles the vertex visitation order using its pseudorandom generator. In a documented run, seed 41 produces partition \(P_A\) with \(Q(P_A)=0.312\). Seed 42 produces partition \(P_B\) with \(Q(P_B)=0.305\). The objective difference is
This calculation says that the first reported partition has modularity higher by 0.007 for this graph and this objective. It does not establish that \(P_A\) is biologically correct, nor does it show that changing the seed alone caused the difference unless all other inputs and settings were held fixed. The two seeds are evidence that this procedure can follow different paths under the stated setup.
Now rerun seed 41. If it again returns \(P_A\), that supports repeatability for the recorded configuration. If it returns another partition, investigate whether the generator, vertex order, graph representation, software version, parallel execution, or other settings changed. Merely recording “seed 41” is not enough to diagnose the discrepancy.
A Reproducible Recording and Rerun Procedure
A useful record allows another analyst—or the same analyst later—to distinguish a changed seed from a changed graph or implementation. Preserve machine-readable inputs where possible, not just prose descriptions. For a graph clustering run, record at least the following:
- Graph input: the edge list or adjacency representation, vertex identifiers, edge weights, directedness, and any preprocessing or filtering that produced the graph.
- Algorithm configuration: method and implementation, objective and resolution setting where applicable, initialization choice, stopping rule, iteration limit, and any tie-breaking rule exposed by the software.
- Randomness controls: seed, pseudorandom generator or library when available, and whether random streams or parallel workers were used.
- Execution environment: software and dependency versions, relevant hardware or parallel settings, and the command or code used to run the analysis.
- Output: the membership of every vertex, the reported objective value, warnings, and a stable identifier or checksum for the graph input.
When comparing runs, hold the graph, method, settings, and environment fixed while changing only the factor being investigated. To examine initialization, vary the starting partition while keeping the seed and remaining settings fixed where possible. To examine seed sensitivity, keep the initialization and all other settings fixed while varying the seed. To investigate order effects, explicitly control or record the vertex order if the implementation permits it. These comparisons identify which control changed; they do not by themselves establish which resulting partition is preferable.
Save the exact vertices and edges, including weights and preprocessing decisions. Use stable vertex identifiers rather than relying on incidental row order.
Record initial labels or the initialization option, visitation order if available, tie-breaking behavior, and the seed and generator settings.
Record algorithm, objective settings, stopping conditions, parallel settings, software versions, and the executable command or code.
With all recorded conditions unchanged, rerun the procedure and compare vertex memberships and objective values. Investigate any mismatch rather than assuming that the seed alone guarantees an identical result.
Worked Example: Checking Whether a Rerun Matches
A hypothetical analysis records five cells, \(c_1,\ldots,c_5\), their graph, the algorithm version, and seed 7301. The saved output assigns \(c_1,c_2,c_3\) to group 1 and \(c_4,c_5\) to group 2. A rerun gives the same memberships but reports an objective of 0.284 instead of 0.281.
The membership comparison matches for all five cells, while the objective difference is
Thus the partition is the same as recorded, but the run is not an exact match in all reported output. Check whether the objective was rounded, evaluated under a different convention, or computed from a changed graph or setting. A suitable record should preserve enough precision and the exact input to test these possibilities. If the memberships differed, compare labels by vertex identity; numerical cluster labels themselves can be permuted without changing a partition.
Diagnostics, Alternatives, and Limits
Warning signs of uncontrolled path dependence include different partitions after a rerun that was expected to be exact, results that change when vertex rows are reordered, and output that varies with the number of parallel workers. First check for mismatched graph inputs, software settings, and label alignment. Then determine whether the implementation is expected to be deterministic under the recorded conditions. A different result across deliberate seed changes is not, by itself, a failure; it is a reason to report the run conditions and avoid presenting one outcome as inevitable.
Common ways to control the path answer different questions. Fixing one initial partition and one order can make an execution easier to replay, but the resulting partition may depend strongly on that choice. Multiple seeded runs can reveal whether the method returns different outcomes, but selecting only the largest objective value can conceal that variation and does not establish biological validity. An algorithm with deterministic tie-breaking can reduce run-to-run randomness, yet may still depend on vertex ordering and can still settle at a local optimum. No seed or initialization strategy removes the need to retain the graph and configuration.
| Approach | What it controls | Main limitation |
|---|---|---|
| Fixed seed and configuration | Repeats pseudorandom choices under a compatible execution | Does not ensure identical results across changed software, parallel schedules, or inputs |
| Fixed initialization and vertex order | Controls the starting state and update sequence where supported | Can make results specific to that chosen start and order |
| Multiple runs with different seeds | Shows how outputs vary across randomized paths | Requires reporting the run plan and outputs; one selected run is not the whole picture |
| Deterministic tie-breaking | Makes ambiguous choices follow a stated rule | Does not guarantee a unique optimum or independence from vertex ordering |
A frequent mistake is to say, “The same seed was used, so the run must be identical.” That reasoning omits the generator, call sequence, graph ordering, software, and execution settings. The correction is to treat the seed as one item in a reproducibility record and to state the conditions under which the rerun matched. Another mistake is to interpret the highest objective among several runs as proof of the best biological clustering. An objective ranks partitions according to its own definition; it does not, by itself, validate cell-type interpretation.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- Why can two update orders produce different final partitions even when they use the same graph and objective?
- For the four-cycle example, what is the modularity of either adjacent-pair partition, and what does equality of the values establish?
- A rerun with the same seed gives a different result after a software update. Name two plausible reasons and one item to check first.
- What should be held fixed when investigating the effect of a seed on the output?
Solutions. (1) An update changes the current state, so it can change the candidates available to later updates; in general \(T_v(T_u(P))\ne T_u(T_v(P))\). (2) Each partition has two groups with one internal edge and degree sum 4, so \(Q=2(1/4-(4/8)^2)=0\). Equality establishes only that the objective gives these two partitions the same value, not that their memberships are identical. (3) The update sequence or random-number handling may have changed, or tie-breaking and implementation details may differ. First compare the recorded software version and configuration, along with the exact graph input. (4) Hold the graph, algorithm implementation and settings, initialization, vertex order if controllable, and execution environment fixed; vary only the seed and record the generator and parallel settings.