cluster() community-splitting pass is nondeterministic across PYTHONHASHSEED (_partition itself is not; edge-count loss appears fixed since 0.9.6)

[AlexisDavid1989]

Localised: _partition is deterministic, cluster() post-processing is not

Same graph object, graphifyy 0.9.42, 4 unpinned runs + 2 with PYTHONHASHSEED=0:

_partition(G)   61 communities, identical partition hash in all 6 runs
cluster(G)      345 / 342 / 346 / 350 unpinned
                344 / 344 with PYTHONHASHSEED=0

_partition's sorted node/edge construction and hardcoded seed=42 work
correctly - it never varies, pinned or not. The variance is introduced
downstream, in cluster()'s community-splitting pass
(_MAX_COMMUNITY_FRACTION / _MIN_SPLIT_SIZE / _COHESION_SPLIT_THRESHOLD /
_COHESION_SPLIT_MIN_SIZE), which expands 61 communities to ~345 - about 85%
of the final structure - without inheriting _partition's ordering
guarantees.

Caveat on the numbers above: measured on a synthetic 4,000-node /
9,000-edge fixture, on Linux / Python 3.11 - not the ORE corpus this issue
was originally opened against.

Re-ran the same _partition-vs-cluster comparison on our frozen ORE
extraction to check it holds there too (graphifyy 0.9.42, Windows, Python
3.12.4, same .graphify_extract.json as every measurement in this issue), 4
unpinned runs + 2 pinned:

_partition(G)   83 communities, identical hash all 6 runs (eaaaf43442be)
cluster(G)      230 / 230 / 231 / 229 unpinned
                231 / 231 with PYTHONHASHSEED=0

Same shape on a completely different, real-world input: _partition never
moves, cluster() does, PYTHONHASHSEED=0 fixes it. This localises the bug
inside cluster()'s splitting/re-splitting passes rather than in
_partition, build_from_json, or Leiden/Louvain itself.

Suggested direction: apply the same normalisation _partition already
does - iterate communities and their members in a sorted, deterministic
order when deciding what to split and how, in _split_community and the
cohesion-based second pass in cluster().

Correction to the hypothesis in the previous update: the json.dumps
list-ordering theory is refuted - G.edges() yield order and edge
orientation were byte-stable across hash seeds, so the sort key passed into
_partition was never the variable. Posting as a correction rather than
editing the earlier text away.

---

Update: edge loss looks fixed since 0.9.6; clustering nondeterminism remains on 0.9.42

Re-ran the same frozen-input repro below against graphifyy 0.9.42 in a
clean venv (0.9.6 left untouched). On our real extraction input:

	edges (3 unpinned runs)	communities (3 unpinned runs)	pinned (PYTHONHASHSEED=0, 3 runs)
0.9.6	7513 / 7518 / 7519 (varies)	212 / 208 / 210 (varies)	7522 edges, 209 communities — identical all 3
0.9.42	7095 / 7095 / 7095 (stable)	230 / 230 / 231 (varies)	7095 edges, 231 communities — identical all 3

Edge count is no longer a source of nondeterminism in 0.9.42 on this input —
only the Louvain partition still is, and by a much narrower margin than 0.9.6
(1 community of drift here vs. up to 4). Retitled this issue to lead with the
clustering nondeterminism, since that's the part still open; the edge-loss
numbers below are kept for the record and to show the delta between
versions. PYTHONHASHSEED=0 still fully fixes it on 0.9.42 (3/3 identical
runs) — required, not just historically.

One correction to the original report below: it claimed cluster() is
"deterministic on its own" without a test that actually isolates hash-seed
effects (the in-process check described doesn't - the seed is fixed for the
lifetime of a process either way, so running it multiple times in one process
proves nothing about hash-seed sensitivity specifically; sorry for the
imprecision). Looking at the source instead: cluster.py's _partition()
already rebuilds the input into a stable graph with nodes and edges sorted
by str() / json.dumps(attrs, sort_keys=True) before calling Louvain with
a hardcoded seed=42 - so given an identical networkx.Graph object, that
function should already be order-independent. If that's right, the residual
0.9.42 variance is more likely upstream of _partition: an edge attribute
holding a list (e.g. a relation-type list collapsed from a set somewhere in
build_from_json) would still sort inconsistently under
json.dumps(..., sort_keys=True), since that only orders dict keys, not list
contents - which would perturb _partition's edge sort order even though the
edge set is now stable. Haven't traced this to a specific line, but it
would explain why edges converged in 0.9.42 while communities didn't.

---

Original report (graphifyy 0.9.6)

Summary

Given byte-identical extraction input, graphify.build.build_from_json() followed by graphify.cluster.cluster() produces a different graph (edge count) and a different Louvain partition (community count and membership) on every process run, unless PYTHONHASHSEED is pinned. This makes any pipeline built on graphify's public API non-reproducible by default: two people building from the same commit get different community structure, and any downstream artifact keyed by community id (labels, anchors, reports) silently drifts.

Environment

• graphifyy 0.9.6 (PyPI)
• Python 3.12.4, Windows
• networkx 3.6.1
• Reproduces with default bufsize/no other flags; not specific to our extraction pipeline (see minimal repro below, which calls only stock graphify functions on a frozen input file).

Minimal reproduction

extract.json below is a .graphify_extract.json produced once by graphify.extract.extract() and then frozen to disk, so every run reads the exact same bytes as input — no re-extraction, no filesystem variance, no code from our project.

import json
from graphify.build import build_from_json
from graphify.cluster import cluster

ex = json.load(open("extract.json", encoding="utf-8"))
G = build_from_json(ex, root="/path/to/repo", directed=False)
comm = cluster(G)
print(G.number_of_nodes(), G.number_of_edges(), len(comm))

Run three times without PYTHONHASHSEED set:

4047 nodes  7513 edges  212 communities
4047 nodes  7518 edges  208 communities
4047 nodes  7519 edges  210 communities

Run three times with PYTHONHASHSEED=0:

4047 nodes  7522 edges  209 communities   (identical all three times)

Node count is stable across all six runs (4047) — only edges and the resulting partition vary. The edge-count delta (7513–7519, up to 6 edges short relative to the pinned run) and the community-count delta (208–212) are both consistent with iteration over an unordered/hash-ordered collection (a set or dict keyed by node/edge identity strings) somewhere in edge construction or deduplication inside build_from_json, before the graph is handed to cluster().

We separately confirmed cluster() is deterministic on its own: clustering one already-built, byte-identical networkx.Graph object in-process three times gave identical results each time. The drift enters earlier, while build_from_json is still constructing the graph.

Impact

Any project that clusters a build_from_json graph and treats community ids or edge sets as stable — labelling, diffing, caching, reporting — gets silent drift instead of a reproducibility guarantee. We worked around it downstream by relaunching under PYTHONHASHSEED=0 for any command that builds or clusters, but that's a workaround at the call site, not a fix — anyone calling these functions without knowing to pin the seed will hit this with no warning.

At full pipeline scale (90k nodes, our real corpus) the same pattern held: unpinned runs varied between 190,503 and roughly 190,550 edges with correspondingly different community counts; three pinned full builds were byte-identical.

Suggested fix direction

Somewhere in the edge construction/dedup path of build_from_json, an unordered set/dict keyed by node-id strings appears to be iterated to decide edge order or dedup precedence. Sorting that iteration (or using an insertion-ordered structure keyed consistently) before building the edge list should make the output invariant to PYTHONHASHSEED, without needing every caller to pin it.

Happy to share the exact repro script and the frozen .graphify_extract.json input if useful.

[abhay-codes07]

Reproduced on a different corpus (graphify's own package, 2287 nodes / 5396 edges, Windows / Python 3.12), and I think I have the mechanism.

seed=0 partition=24 hash=58168d027bc6  cluster=134
seed=1 partition=24 hash=58168d027bc6  cluster=129
seed=2 partition=24 hash=58168d027bc6  cluster=132
seed=3 partition=24 hash=58168d027bc6  cluster=137

Same shape you measured: _partition byte-identical across seeds, cluster() moving.

Narrowing further — it is _split_community, and it varies on an identical input list:

seed=0 biggest=592 splits=9  hash=0726f50ae073
seed=1 biggest=592 splits=10 hash=49882a1aef1e
seed=2 biggest=592 splits=10 hash=1aee8b8404d0

Which is odd at first glance, because _split_community calls the same _partition that never moves on the full graph. The difference is that it calls it on a subgraph view.

_partition normalises node order (add_nodes_from(sorted(...))) but sorts edges on (str(row[0]), str(row[1]), ...) without normalising orientation. On an undirected graph G.edges() yields each edge with whichever endpoint the adjacency walk reached first, and for G.subgraph(nodes) that follows the induced node order — which comes from raw[cid], built by iterating partition.items(). So the same edge arrives as (a, b) in one run and (b, a) in the next, sorts to a different position, and Leiden gets a differently-ordered graph.

That also fits your correction: on the full graph the yield order and orientation genuinely are stable, which is why _partition looked innocent — the instability only appears once it is handed a subgraph.

So the fix is a bit further up than the splitting passes: normalise edge orientation in _partition's sort key (and when re-adding to stable), which is safe because stable is an undirected nx.Graph built only for partitioning — orientation is already meaningless there, and _src/_tgt ride along in the attrs. Sorting the member lists in the splitting passes would help too, but on its own it would only move the problem rather than remove it.

Working on a PR with that plus a cross-seed determinism test.

[abhay-codes07]

Correcting my previous comment — the mechanism I proposed is wrong, and I would rather say so before anyone builds on it.

I claimed the instability came from unnormalised edge orientation in _partition's sort key, leaking in through the subgraph views _split_community uses. Two checks refute it, both on the real 2287-node graph:

_partition(G) vs _partition(G with every edge's endpoints swapped)
  orientation-stable = True      (24 communities vs 24)

_split_community(G, sorted(nodes)) vs _split_community(G, reversed(nodes))
  same 592-node set, forward splits = 10, reversed splits = 10, identical = True

So _partition is orientation-stable, and _split_community is insensitive to the order of the node list it is handed. Neither of the two things I pointed at is the variable. Your original localisation — that it is inside cluster() — still stands; my attempt to narrow it further does not.

I did try normalising orientation anyway, and it appeared to work — cluster() returned 101 communities with an identical signature across PYTHONHASHSEED 0–4, against 134 / 129 / 132 / 137 before. But it also changed the partition itself (24 communities to 23), and since the mechanism I used to justify it turns out not to hold, I cannot tell whether that determinism is the fix working or a structural coincidence on this particular graph. I am not going to open a PR on that basis, so this is still open for whoever picks it up.

What I can add that is solid, as a starting point for the next person:

• The variance survives with _partition byte-identical, so it enters after the initial partition — confirmed on a second corpus (graphify's own package, Windows / Python 3.12), matching your ORE and synthetic results.
• _split_community is deterministic in both the orientation and the node-order dimensions, so the remaining candidates are inside the graspologic/Leiden call it makes on a subgraph, or in something else cluster() does between the partition and the return.
• The reproduction is cheap on any repo: _partition hash versus cluster() signature across four seeds, no fixture needed.

Sorry for the noise — better a retraction than a plausible-sounding wrong lead sitting under an open issue.

[febryo-sc]

Non-synthetic data point for the cluster() variance, on a real ~5,450-node / ~14,300-edge
TypeScript corpus (0.9.56, macOS, Python 3.12), identical content across all three runs:

graphify update .   (unpinned)   508 communities
graphify update .   (unpinned)   496 communities
PYTHONHASHSEED=0 graphify update .   273 communities   <- also stable on repeat

So the same corpus lands anywhere between 273 and 508 communities depending only on the hash
seed, which matches your _partition-is-fine / cluster()-post-processing-is-not
localisation: the split pass is where the count inflates.

The operational cost lands on labels, which is the part that surprised me: every unpinned run
invalidated the saved .graphify_labels.json and re-derived names from hub filenames, so a
freshly LLM-labelled graph reverted to requireCmsUser, cn, next as community names after
one hand-run update — the effect #2298 describes, but triggered by nothing more than the seed
rather than by any content change.

One practical note for anyone hitting this before the fix: the installed post-commit hook
exports PYTHONHASHSEED=0 itself, so hook-driven rebuilds are stable and only manual
graphify update / graphify label invocations churn. Setting it inside the CLI (or at least
in the --update runbook) would close that gap.

[snandan93]

I checked this on current v8 (0.9.65) and it looks fixed by 2709681, which shipped in v0.9.51.

• graphify update . on graphify's own package with PYTHONHASHSEED 0–3: 287 communities each time, with the same membership hash. Calling cluster() directly on that graph is also stable on both backends (Leiden 283 communities, Louvain fallback 299, identical hashes across seeds).
• On a TypeScript corpus (zod packages/, 6408 nodes), node, edge and community hashes were identical on every seed.

The existing test only covers _partition orientation. I opened #3761 with a cross-process PYTHONHASHSEED test on the full cluster() output. It fails on 2709681^ for both backends and passes on HEAD, so this shouldn't regress silently. @febryo-sc, if you can re-run your corpus on ≥0.9.51 and confirm, I think this can be closed.