Source-linked AI summary
Discretization-free exact recovery in geometric community detection
Maarten Hoeneveld, Moritz Otto, Raphaël Sala
TL;DR
Exact recovery in geometric networks is difficult because prior efficient GHCM methods discretize continuous space and impose stronger connectivity distinctions. This paper introduces polynomial-time recovery directly on continuous geometry, proves guarantees under weaker witness-connectivity conditions, and finds experimentally that the discretization-free method succeeds beyond the proven regime.
Problem
Prior efficient GHCM recovery methods discretize continuous space, while the restrictiveness of their structural distinctness assumptions remains unresolved.
Method
The paper develops polynomial-time exact-recovery algorithms that operate directly on continuous vertex locations using initialization, greedy or block-based propagation, and likelihood refinement.
Results
The algorithms achieve exact recovery under weaker witness-connectivity conditions, while experiments show the discretization-free algorithm succeeding beyond the theoretically analyzed regime.
Takeaways & Limitations
When information-theoretic recovery implies witness connectivity, the algorithms reach the necessary information-theoretic threshold.
Takeaways & Limitations
Removing the bounded log-likelihood difference assumption remains open because propagation can be disrupted by a single incorrectly labeled vertex when densities vanish.
Abstract
from arXiv · showhide
Geometric community detection seeks to recover latent communities in networks where connectivity depends jointly on community structure and continuous spatial geometry. Existing exact-recovery approaches typically discretize the underlying space, which can impose restrictive structural assumptions on the connectivity functions. We develop a polynomial-time, discretization-free algorithm for exact recovery in the Geometric Hidden Community Model (GHCM), operating directly on the continuous geometry. Our method succeeds even when connectivity functions coincide on a nontrivial portion of their visibility range and when two communities can be distinguished only through their connectivity to a third community. We prove exact recovery under these weaker conditions and provide experiments showing that the algorithm succeeds beyond the theoretically guaranteed regime.
1. Introduction
The paper targets exact community recovery in spatial networks while avoiding spatial discretization and weakening the structural distinctness assumptions used by prior efficient GHCM methods.
- GHCM models edge distributions using both endpoint communities and spatial distance in a continuous domain.
- Existing efficient GHCM recovery methods discretize space into cells and propagate labels across sufficiently occupied regions.
- The proposed polynomial-time algorithm operates directly on continuous vertex locations through initialization, greedy propagation, and local likelihood refinement.Its propagation phase uses O(n log2 n) operations.
- The analysis permits communities to be distinguished through witness communities rather than only through their direct pairwise connectivity.The guarantee applies to both the discretization-free and block-based propagation algorithms.
- Numerical experiments show the discretization-free algorithm succeeding beyond the theoretically guaranteed regime.The authors suggest the additional connectivity condition may reflect an analytical or block-propagation limitation rather than an intrinsic recovery barrier.
2. Model and Main Result
The GHCM combines continuous vertex geometry with community-dependent edge distributions, and Theorem 3 establishes polynomial-time exact recovery under identifiability, initialization, boundedness, and connectivity conditions.
- Model: In the GHCM, vertices occupy a continuous spatial domain and edge distributions depend on community labels and spatial distance.
- Model: Vertices arise from a Poisson point process, receive independent labels with prior π, and generate conditionally independent distance-dependent edge weights.
- Definitions: Exact recovery is defined as recovering all community labels up to permissible relabeling with probability tending to one.Permissible relabelings preserve community priors and pairwise edge-weight distributions.
- Definitions: The Chernoff–Hellinger divergence D+ measures average community distinguishability after averaging over distances and neighboring-community priors.
- Assumptions: Witness communities are those whose edge-weight distributions from two communities differ almost everywhere on a specified distance interval.
- Main result: Under Assumptions 1–3 and the theorem’s recovery condition, Algorithms A and B achieve exact recovery in polynomial time.The assumptions include identifiability, initialization separation, and bounded log-likelihood differences.
- Regimes: When pairwise distinctions hold throughout the visibility range, the witness-connectivity assumption becomes trivial in dimensions d ≥2 once the information-theoretic condition is met.
- Regimes: Theorem 3 covers the regime where both the refinement and witness-connectivity thresholds hold, while an intermediate region separates this regime from the information-theoretic threshold.
3. Exact Recovery Algorithms
The paper presents a discretization-free greedy algorithm and a block-based counterpart, both combining initialization, propagation, and refinement for exact recovery under weaker witness-based conditions.
- Initialization: Both algorithms begin with MAP estimation on an O(log n)-sized initial set, which remains polynomial because k is fixed.
- Algorithm A: The discretization-free propagation selects the unlabeled vertex with the greatest affinity to labeled neighbors and assigns its likelihood-maximizing label.
- Complexity: Incremental priority-queue maintenance reduces propagation selection from O(n2 log n) for a naïve implementation to O(n(log n)2).
- Algorithm B: Algorithm B partitions space into blocks, constructs a visibility graph of sufficiently occupied blocks, propagates from certified neighboring blocks, and applies the same refinement step.
- Algorithm B: Using all labeled blocks intersecting a target block’s visibility range enables propagation under the weaker assumption that distinctions may hold only on a small interval.The method also uses nodes from all communities rather than only the most prevalent label.
4. Proof Sketch
The proof establishes exact recovery by initializing labels, propagating them while preventing error accumulation, and applying a final likelihood refinement.
- Initialization: Initialization handles the random size of the initial region directly and yields exact recovery there.
- Propagation: Propagation shows that every processed vertex has sufficient labeled-neighbor affinity information unless a relevant neighborhood already contains too many errors.
- Propagation: As long as each relevant neighborhood has at most m previous errors, the probability of creating a new error is polynomially small in n.
- Propagation: With high probability, every neighborhood contains at most m incorrectly labeled vertices throughout propagation.
- Refinement: For sufficiently small δ, refinement makes each vertex error with probability o(1/n), so a union bound gives exact recovery.
5. Numerical Analysis
Experiments evaluate Algorithm A on a distance-dependent GHCM whose observations are informative only at short and long distances. Exact recovery extends into the regime where the block construction’s witness-connectivity condition fails.
- Model: The experiment uses a three-community Bernoulli GHCM with informative short and long distances and an uninformative intermediate interval.
- Thresholds: The exact-recovery threshold is λν_dr^dD+(p) = 1, while the block construction requires the witness-connectivity threshold λν_dℓ^dπ_wit = 1.
- Experiment: The study fixes n = 10 000, generates independent GHCM realizations across the phase diagram, and reports empirical exact-recovery frequency after refinement.
- Results: Algorithm A’s empirical transition occurs close to the information-theoretic boundary and extends well inside Region B.
- Results: Algorithm A achieves exact recovery where the sufficient witness-connectivity condition used by the block construction is violated.
6. Discussion and Open Problems
The paper proves exact recovery under weaker witness-connectivity assumptions, while experiments suggest the discretization-free method works beyond the current theorem and motivate unresolved robustness questions.
- Discussion: The analysis replaces previous global distinctness conditions with a weaker witness-connectivity condition for both discretization-free and block-based algorithms.
- Discussion: When information-theoretic recovery implies witness connectivity, exact recovery reaches the necessary information-theoretic threshold.
- Open Problems: In the intermediate regime, the information-theoretic condition holds but the paper’s witness-connectivity condition does not, leaving polynomial-time exact recovery without those assumptions open.
- Open Problems: Removing Assumption 3 remains open because vanishing densities can let one mislabeled vertex assign zero likelihood to the correct community and disrupt propagation.
AI statement
The authors used ChatGPT to explore proof ideas and assist with language polishing, while independently verifying the mathematical arguments and details.
- ChatGPT was used for proof-idea exploration and language polishing, not as a substitute for the authors’ independent verification.
Appendix B. Preliminaries
The preliminaries establish concentration tools for Poisson node counts and an informative interval used in later recovery arguments.
- Poisson Chernoff bounds provide concentration inequalities for Poisson-distributed quantities.They are used to control node counts in blocks.
- With high probability, every block contains at most Δ log n nodes for some constant Δ > 0.The bound follows from Poisson concentration and a union bound.
- The informative-interval lemma guarantees a constant γ ∈ (0, 1) under suitable interval conditions.The value of γ depends only on ε, t, and I.
- Annuli and the distance of a uniformly sampled point from the origin provide the geometric quantities used in these interval arguments.For an interval I ⊆ [0, r], the annulus is defined within the ball B_r.
Appendix C. Exact recovery on the initial set
The initial-set analysis proves that a restricted maximum-likelihood estimator recovers all labels in a logarithmic-sized cube with high probability.
- The restricted MLE on Binit achieves exact recovery with high probability under Assumptions 1, 2, and 3.The initial set is Binit = [−r(log n)^(1/d), r(log n)^(1/d)]^d.
- The proof handles the Poisson number of initial points directly, while informative marked points and concentration bounds control likelihood contributions.No initial sampling is required in this analysis.
- The proof compares every incorrect labeling’s log-likelihood with that of the true labeling using discrepancy, the Hamming distance modulo permissible relabelings.A labeling is correct exactly when its discrepancy from the truth is zero.
- For low discrepancy, incorrect labelings with 0 < DISC(σ, σ∗) < c log n have strictly smaller log-likelihood than the truth with high probability.The proof bounds the likelihood difference by a negative linear term plus a quadratic discrepancy term.
- For high discrepancy, Proposition 14 establishes the corresponding likelihood separation for labelings satisfying DISC(σ, σ∗) ≥ c log n.This complements the low-discrepancy analysis in the exact-recovery proof.
- The two discrepancy regimes, together with Lemma 11, make both failure probabilities tend to zero.This completes the high-probability exact-recovery argument for the initial set.
Appendix D. Propagation proof
The propagation proof prepares a block discretization of the continuous space using the parameters governing block proximity and spread.
- The space is partitioned into blocks whose volume is ℓ^dχ log n, with δ controlling the required node occupancy.These parameters define the block visibility structure used for propagation.
D.1. Block structure.
The block-structure analysis shows that sufficiently occupied, δ-spread blocks form a connected propagation backbone, with every block adjacent to it with high probability.
- For suitable χ, the number of ℓ-close neighboring blocks satisfies λπwitKdχℓ^d > 1.The quantity Kd depends only on χ and d.
- A δ-spread block is defined through the distribution of its community labels across nearby spatial regions.The definition is used to identify blocks suitable for propagation.
- Under the stated intensity conditions, the largest cluster of non-δ-spread blocks is controlled with high probability.This prevents large obstructing clusters in the block geometry.
- The connectivity result combines the absence of large non-spread clusters with the torus’s block-level topological property.The topological lemma supplies the contradiction needed for disconnectedness.
- The block visibility graph induced by δ-spread blocks is connected with high probability, and every block has at least one neighbor in it.This holds for d = 1 under λπwitℓ > 1 and for d ≥ 2 under λπwitνdℓ^d > 1.
D.2. Almost exact recovery in Phase II.
Phase II propagates labels through geometrically connected, certified blocks while controlling local errors and ensuring sufficient affinity information. This yields at most logarithmically many neighborhood errors, establishing almost-exact recovery with high probability.
- Propagation error control: The propagation analysis bounds each vertex’s mislabeling probability using errors among labeled neighbors and available affinity information.This is formalized by the propagation error bound and supports the later uniform error analysis.
- Inductive control: An inductive argument shows that controlling source errors and obtaining sufficient affinity information makes newly propagated labels likely to be correct.The proof combines the propagation error bound with the existence of spread proximity chains and enough-affinity-information guarantees.
- Geometric propagation: Proximity chains connect fully labeled spread blocks to unlabeled blocks, supplying past witness blocks for distinguishing communities.The chain construction underlies both the availability of witness communities and the progression of Phase II.
- Almost-exact recovery: After Phase II, every vertex neighborhood contains at most β log n incorrectly labeled vertices for arbitrarily small β, with high probability.The bound applies to Algorithms A and B and also accounts for vertices assigned the symbol ∗.
- Almost-exact recovery: Because δ can be chosen arbitrarily small, the resulting neighborhood error bound establishes almost-exact recovery.The conclusion follows from the bound on incorrectly labeled neighbors and the asymptotic recovery criterion.