Pith Number

pith:RT5JXJYJ

pith:2026:RT5JXJYJNFXU223RWSSY56IUKV

not attested not anchored not stored refs resolved

Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds

Ethan D'souza, Laurentiu Marchis, Po-Ling Loh, Tom\'a\v{s} Fl\'idr

Consistent community recovery in stochastic block models is achievable under node differential privacy using new polynomial-time algorithms that require the privacy parameter epsilon to grow at a controlled rate.

arxiv:2605.15943 v1 · 2026-05-15 · math.ST · stat.ML · stat.TH

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{RT5JXJYJNFXU223RWSSY56IUKV}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We develop novel algorithms based on (1) sampling from an exponential mechanism with a Lipschitz extension and (2) a general framework for constructing smooth projections from the space of undirected graphs to the space of bounded-degree graphs, which can then be combined with various edge-private algorithms. [...] We also develop novel lower bounds on the growth rate of ε required in order to achieve consistent community estimation under node privacy.

C2weakest assumption

The analysis assumes that the underlying stochastic block model parameters (edge probabilities within and between communities) are such that consistent community recovery is possible even in the non-private case; the privacy mechanisms are then shown to preserve this consistency provided ε grows sufficiently fast. This modeling choice is stated in the problem setup and is used to define the target accuracy level for the private estimators.

C3one line summary

Develops tractable node-differentially private algorithms for community estimation in fixed-community stochastic block models together with lower bounds on the privacy parameter ε needed for consistency.

References

74 extracted · 74 resolved · 6 Pith anchors

[1] E. Abbe. Community detection and stochastic block models: recent developments.Journal of Machine Learning Research, 18(177):1–86, 2018 2018

[2] On Maximal Correlation, Hypercontractivity, and the Data Processing Inequality studied by Erkip and Cover 2013 · arXiv:1304.6133

[3] Avella-Medina 2021

[4] M. Avella-Medina, C. Bradshaw, and P. Loh. Differentially private inference via noisy optimization. The Annals of Statistics, 51(5):2067–2092, 2023 2067

[5] J. Blocki, A. Blum, A. Datta, and O. Sheffet. The Johnson-Lindenstrauss transform itself preserves differential privacy. In2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 410 2012

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-05-20T00:01:46.021984Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

8cfa9ba709696f4d6b71b4a58ef9145554408aa12dc556f97faa9eca3eb0dc8c

Aliases

arxiv: 2605.15943 · arxiv_version: 2605.15943v1 · doi: 10.48550/arxiv.2605.15943 · pith_short_12: RT5JXJYJNFXU · pith_short_16: RT5JXJYJNFXU223R · pith_short_8: RT5JXJYJ

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/RT5JXJYJNFXU223RWSSY56IUKV \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 8cfa9ba709696f4d6b71b4a58ef9145554408aa12dc556f97faa9eca3eb0dc8c

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "a991b671ffe87ab43e1210c145f2b6bcba097759a78e950fb86e934fa65621fd",
    "cross_cats_sorted": [
      "stat.ML",
      "stat.TH"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "math.ST",
    "submitted_at": "2026-05-15T13:27:24Z",
    "title_canon_sha256": "e1641f9fa931143bd8bb533d779774600240d4e14583c5d232ad59ce1da6a832"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.15943",
    "kind": "arxiv",
    "version": 1
  }
}