Non-deterministic behavior when generating graph.json

[AhmedGenbai]

Across 4 runs of graphify update locally without changing my repo, I see minor differences:

Run	Nodes	Links	Communities	MD5
1	32,277	53,801	2,000	0009f1...
2	32,442	54,012	2,013	0dd515...
3	32,441	54,004	2,007	7c88e5...
4	32,441	54,004	2,003	1ed199...

I was under the impression that this initial step would be deterministic, but maybe the underlying Leiden algorithm is unseeded or something is in some way introducing some variability.

First time commenter- amazing tool @safishamsi

-Ahmed

[safishamsi]

Great catch @AhmedGenbai, and welcome!

You are right that it is non-determinism, but Leiden is not the culprit — it is properly seeded (random_seed=42, trials=1) and its input is canonically sorted before each run. The root cause is upstream.

Root cause: os.walk() in detect.py returns files in filesystem b-tree order, which shifts between runs depending on kernel cache state, recent directory writes, or mount. Several downstream passes are first-writer-wins (cross-file import resolution, label dedup, symbol resolution) so whichever file happened to be seen first would win name collisions — producing different node IDs, edge targets, and Leiden input edge attributes each run.

Why runs 3 and 4 had identical node/link counts but different community counts: the node and link totals stabilised (same files, same collision winners by chance) but the edge attribute values (source_location, confidence_score) still drifted slightly with traversal order. The Leiden sort key included the full edge attr JSON, so Leiden received a marginally different input and produced a different partition — even with the same seed.

Fix committed in 8db19d6: two lines added to detect() — sort all_files lexicographically after the os.walk loop, and sort each per-FileType list before returning. Every run now processes files in the same stable order, making first-writer-wins decisions deterministic without changing any graph semantics (parent-child edges are intra-file and unaffected; hub connectivity is structural and unaffected).

Will ship in the next PyPI release. Thanks again for the detailed reproduction table — the four-run comparison made the diagnosis straightforward.

[AhmedGenbai]

Thank you for the explanation and the quick turnaround!

[AhmedGenbai]

Upon checking once more locally, it looks like the file sorting stabilized the node/link count but the community count still varies from run to run:

Run 1: 25790 nodes | 47169 links | 1633 communities
Run 2: 25790 nodes | 47169 links | 1634 communities
Run 3: 25790 nodes | 47169 links | 1634 communities
Run 4: 25790 nodes | 47169 links | 1635 communities

And Im also seeing that the nodes assigned to each community also change:

Run 1 -> Run 2: 19873 nodes changed community (77.1%)
Run 2 -> Run 3: 22794 nodes changed community (88.4%)
Run 3 -> Run 4: 22016 nodes changed community (85.4%)

Would appreciate you taking a look into this as well @safishamsi !

[safishamsi]

Thanks for pushing on this @AhmedGenbai - two separate things here:

The 77-88% "changed community" is a labeling artifact, not real regrouping. Each node's community value is an integer ID assigned by sorting communities by size; equal-sized small communities (most of a sparse graph) were getting different IDs each run because graspologic doesn't return them in a stable order. The grouping was reproducible; only the labels permuted. Fixed by assigning IDs via a total order ((-size, sorted nodes)) - ships next release. To confirm, compare group membership (a co-membership signature), not IDs - that churn drops to ~0.

The ±1-2 community-count drift is a tiny real residual (~0.1%). I verified the graph fed to clustering is byte-identical across runs and the top-level partition is deterministic - the wobble is graspologic Leiden being slightly non-deterministic only when re-splitting small low-cohesion subgraphs. It doesn't affect god-nodes or overall structure. Note the default install uses Louvain, which is fully deterministic (verified 20/20 identical runs) - so if you need byte-stable graph.json, a default install (no [leiden] extra) gives it. We have a validated fix ready if strict Leiden reproducibility matters to you.

[AhmedGenbai]

Thanks @safishamsi for the quick fix!
Strict Leiden reproducibility does matter to me since I run some additional algorithms on top of the graph, and I was wondering why I was getting different results each time since my processes should have been deterministic themselves.

Ive since protected against this by caching the graph until theres a merge to main, but its good to know that a full deterministic refresh is possible in the meantime.

Thanks again,
Ahmed