PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust and computationally feasible community detection in the presence of arbitrary outlier nodes

T. Tony Cai, Xiaodong Li

arXiv:1404.6000v4math.STcs.ITmath.ITmath.OCstat.MLstat.TH

TL;DR

The paper asks whether fast community detection can have theoretical guarantees while remaining robust to arbitrary outlier nodes. It extends the SBM with a model for such nodes and proposes convex optimization followed by k-means; its guarantees cover growing cluster counts and adversarial outliers under stated settings.

  • Problem

    The paper asks whether a computationally fast community-detection method can remain robust to arbitrary outlier nodes while providing theoretical guarantees.

    Source: §1 · p. 4

  • Method

    The method models inlier nodes with the SBM, permits arbitrary outlier connections, and applies convex optimization followed by k-means with k = r.

    Source: §1.1 · p. 4, §1 · p. 4, §2.1 · pp. 10–11

  • Results

    O(n^1/2−ε) adversarial outliers are within the method's robustness guarantee when inlier edge density is O(1) and the number of clusters grows with n, for example O(n^1/4); without outliers, its theoretical result is consistent with state-of-the-art computationally feasible SBM results.

    Source: §5 · p. 24

  • Takeaways & Limitations

    The authors conclude that computationally feasible community detection can have theoretical guarantees under the GSBM, including settings with growing cluster counts and arbitrary outliers.

    Source: §1 · p. 4, §5 · p. 24

    The full SVD has O(N^3) computational complexity and a scalability issue at graph sizes of hundreds of thousands of nodes.

    Source: §2.1 · p. 13

Abstract

from arXiv · show

Community detection, which aims to cluster $N$ nodes in a given graph into $r$ distinct groups based on the observed undirected edges, is an important problem in network data analysis. In this paper, the popular stochastic block model (SBM) is extended to the generalized stochastic block model (GSBM) that allows for adversarial outlier nodes, which are connected with the other nodes in the graph in an arbitrary way. Under this model, we introduce a procedure using convex optimization followed by $k$-means algorithm with $k=r$. Both theoretical and numerical properties of the method are analyzed. A theoretical guarantee is given for the procedure to accurately detect the communities with small misclassification rate under the setting where the number of clusters can grow with $N$. This theoretical result admits to the best-known result in the literature of computationally feasible community detection in SBM without outliers. Numerical results show that our method is both computationally fast and robust to different kinds of outliers, while some popular computationally fast community detection algorithms, such as spectral clustering applied to adjacency matrices or graph Laplacians, may fail to retrieve the major clusters due to a small portion of outliers. We apply a slight modification of our method to a political blogs data set, showing that our method is competent in practice and comparable to existing computationally feasible methods in the literature. To the best of the authors' knowledge, our result is the first in the literature in terms of clustering communities with fast growing numbers under the GSBM where a portion of arbitrary outlier nodes exist.

1. Introduction.

The introduction asks whether fast community detection can remain robust to arbitrary outlier nodes while retaining theoretical guarantees. It presents the GSBM as a way to model such outliers alongside inlier communities.

1. Introduction.

  • Existing approaches involve trade-offs: greedy methods lack fully established statistical accuracy, while modularity and profile-likelihood methods are computationally NP hard.The introduction describes spectral clustering as fast and easy to implement, with consistency results when the number of groups grows.Source: §1 · p. 3
  • The paper asks whether a computationally fast community-detection method can robustly handle a portion of arbitrary outlier nodes with theoretical guarantees.The motivation is that existing generalized models focus on single latent structures, while graphs may contain several kinds of outliers that are difficult to model together.Source: §1 · p. 4

1.1. Generalized stochastic block model.

  • The GSBM keeps independent SBM edges among inliers but allows outlier connections to be arbitrary, including dependence on inlier connectivity.The inlier connectivity is represented by a symmetric matrix; outlier links may depend arbitrarily on the inlier graph.Source: §1.1 · pp. 4–5
  • The GSBM treats mixed-membership nodes, hubs, small clusters, and independent neutral nodes as possible outliers.The paper describes these as examples of outlier types covered by the model.Source: §1.1 · pp. 5–6
  • Modeling combinations of these cases precisely may require complex SBM extensions, which can increase overfitting risk and computational complexity.The paper gives political blogs as an example where a two-cluster SBM captures the main groups while leaving other groups outside them.Source: §1.1 · p. 6
  • The GSBM also provides a robustness criterion: a clustering algorithm should still cluster most nodes well when a small portion are outliers.The paper frames robustness in terms of performance under the GSBM when most nodes fit the adopted SBM.Source: §1.1 · p. 6

2. Methodology.

The section motivates a robust community-detection procedure by showing that ordinary spectral clustering can fail with a small number of outliers. It fits the GSBM with convex optimization and then applies k-means to recover the major clusters.

2. Methodology.

  • With no outliers, spectral clustering distinguishes two balanced communities, but adding 30 outliers yields over 30% inlier misclassification for Laplacian clustering with r = 3.The illustration uses 1,000 inliers in two balanced groups before adding the outliers.Source: §2 · pp. 7–8
  • The procedure fits the GSBM with semidefinite programming and then clusters normalized solution columns using k-means with k = r.The method is presented as computationally feasible with theoretical guarantees.Source: §2 · p. 7, §2.1 · pp. 9, 12

2.1. Convex optimization.

  • The convex relaxation starts from a same-community indicator matrix X, keeps positive semidefiniteness and entries in [0,1], and drops the rank constraint.The indicator matrix has rank r; the relaxation is derived from a parametric-model fitting view.Source: §2.1 · pp. 10–11
  • Unlike the nuclear-norm relaxation of Chen, Sanghavi and Xu (2012), this convex relaxation uses X's positive semidefinite structure as a constraint.The paper's stated distinction is that X is both low-rank and positive semidefinite.Source: §2.1 · p. 11
  • Positive α did not significantly improve clustering numerically, while a large α risks making E positive definite and forcing the useless zero solution; λ is the parameter tuned in practice.The paper also reports numerical robustness to the choice of λ.Source: §2.1 · p. 12
  • Each ADMM iteration's dominant subproblem requires a full SVD with O(N^3) complexity, creating a scalability issue at hundreds of thousands of nodes.A partial-SVD approach is suggested as a possible remedy, but large-scale computing is left for future work.Source: §2.1 · p. 13

3. Theoretical guarantees.

Under explicit parameter conditions, the SDP recovers the inlier community structure, and a subsequent k-means step has a controlled inlier misclassification rate. The guarantees include a setting where the number of clusters grows with the graph size.

3. Theoretical guarantees.

  • Under Theorem 3.1’s conditions, the SDP solution separates inlier pairs exactly: within-group entries are 1 and between-group entries are 0.The theorem gives explicit conditions on graph and tuning parameters for this structure.Source: §3 · p. 15
  • In a sparse example with r=O(1), the procedure works with average inlier degree on the order of O(log n), while α=log N allows m=log n outliers.The sparse-case comparison is described as consistent with a best-known result without outliers.Source: §3 · pp. 15–16
  • When r is approximately n^1/4 and nmin is approximately n^3/4, the conditions allow m=O(n^1/2−ε) outliers for any ε>0.This is an example with a growing number of clusters.Source: §3 · p. 16
  • With no outliers, the theorem’s condition is consistent with state-of-the-art community-detection results under the ordinary SBM.For fixed r, the discussion also gives a minimum-community-size condition relaxed to nmin≥O(√n) by modifying a lemma.Source: §3 · p. 16
  • The proof constructs a feasible boundary point with the target block structure and shows the objective’s level set is tangent to the constraint set there.The tangency argument establishes the selected point as the optimizer.Source: §3 · p. 17
  • When m<nmin/(2r+4), Theorem 3.2 guarantees with high probability that the inlier misclassification rate is controlled after k-means.The procedure clusters normalized columns of the SDP solution using k=r.Source: §3 · pp. 17, 19
  • Exact k-means minimization is NP-hard, and the cited polynomial-time approximation applies when r is constant; its availability for growing r remains open.The paper notes a (1+ε) approximation with polynomial runtime when r is constant.Source: §3 · pp. 19–20
  • When nmin>O(m^2), pairwise ℓ1 comparisons between rows of the SDP solution can recover inlier communities without knowing r, though simulations find this less effective than k-means.Rows from the same inlier community are less than m apart; rows from different communities are more than 2nmin apart.Source: §3 · p. 19

4. Numerical results.

The numerical studies test the convex-optimization-plus-k-means procedure on synthetic graphs and political blogs. It performs well in both settings, while the reported spectral baselines struggle to recover the major groups.

4.1. Synthesized data simulations.

  • Across 10 synthetic trials, convex optimization plus k-means had average inlier misclassification 0.0063, versus 0.4792 for Laplacian spectral clustering and 0.5000 for adjacency spectral clustering.The convex method's average runtime was 87.65 seconds.Source: §4.1 · pp. 20–21
  • Synthetic clustering remained robust for λ = 0.11–0.16 unless λ was too close to p = 0.17; the two groups were still well clustered at q = 0.11.The authors suggest sparsity and incomplete convergence after 100 iterations may explain the result at q.Source: §4.1 · p. 21
  • As the synthetic within-group density increased from 0.17 to 0.19–0.29, the optimization solutions appeared closer to the form predicted by Theorem 3.1.Even when the solution differed from that form, the subsequent k-means step still clustered the two groups successfully.Source: §4.1 · p. 21, Figure 5 · p. 22

4.2. Real data application.

  • For the political blogs application, the authors modified the optimization matrix to accommodate highly variable degrees, using a degree-based diagonal matrix instead of the scalar λI_N.They chose λ from the mean density of a graph trimmed to exclude nodes above the 80th or below the 20th degree percentile.Source: §4.1 · p. 20, §4.2 · pp. 23–24
  • On political blogs, the method misclassified 63/1222 nodes (about 0.052), comparable to reported methods near 0.05 and better than the nearly 0.2 rate for penalized spectral clustering.It took 137.16 seconds; ordinary spectral clustering also failed to distinguish the two political groups.Source: Figure 6 · p. 23, §4.2 · p. 24

5. Discussion.

The discussion states the conditions and open questions that bound the proposed method. In particular, the framework relies on a positive within- versus cross-group density gap and leaves tuning and cluster-count questions open.

5. Discussion.

  • The procedure and its guarantees require δ = p− − q+ > 0, an assumption the authors call strong and note may fail in real networks.For example, each group's within-group density may exceed its cross-group densities even though the largest cross-group density exceeds the smallest within-group density.Source: §5 · p. 25
  • When the largest cross-group density exceeds the smallest within-group density, no λ in the current framework can yield consistent community detection, so the optimization matrix E must be modified.The simulations use a degree-dependent diagonal replacement, but justifying it under degree-corrected SBM is left for future work.Source: §5 · p. 25
  • The authors leave open whether α is redundant and whether the number of major inlier clusters r can be inferred exactly from the data.Their numerical simulations worked with α = 0, although the theoretical guarantees use α values much smaller than the number of outliers m.Source: §5 · p. 25

6. Proofs.

The proof develops matrix and probability tools, constructs a feasible candidate solution, and uses a dual certificate to establish its optimality with high probability.

6.1. Notation.

  • The proof notation defines matrix and vector norms, entrywise inequalities, positive definiteness, and the diagonal-matrix operator used in later arguments.The authors also state that numerical constants may change between uses.Source: §6.1 · p. 26

6.2. Preliminaries.

  • The preliminaries collect eigenvalue inequalities and concentration tools, then derive properties of the random matrix K, a principal submatrix of the adjacency matrix A.The stated tools include matrix Bernstein concentration for bounding random-matrix spectral norms.Source: §6.2 · pp. 26–27, §6.3 · p. 28

6.3. Supporting lemmas.

  • The supporting lemmas establish bounds used in the theorem proof and show that, without outliers, the result is consistent with state-of-the-art computationally feasible SBM results.The discussion also notes a relaxed condition can permit smaller minimum community sizes in a specified setting.Source: §6.3 · p. 29

6.4. Proof of Theorem 3.1.

  • The theorem proof reduces to the identity permutation, uses feasibility and optimality inequalities, and establishes a sufficient condition that holds with high probability.These steps respectively construct a tight comparison matrix, characterize the optimizer's form, and verify the condition using earlier lemmas.Source: §6.4 · p. 29

6.4.1. Solution candidate.

  • The solution-candidate argument constructs a feasible matrix X from vectors x1,…,xr obtained under α ≥ 2m and 0 < λ < 1.The proof aims to show that this feasible candidate solves optimization (2.3) under mild technical conditions.Source: §6.4.1 · pp. 29–31

6.4.2. Sufficient condition for the optimality of X.

  • A dual certificate—matrices satisfying specified equalities and inequalities—ensures every optimizer has the target form and that X solves optimization (2.3).The certificate requires ΛV = 0, Λ ⪰ 0, Ψ_ii > 0, and Φ_jk > 0.Source: §6.4.2 · pp. 31–32

6.4.3. Construction of dual certificate.

  • Under the stated sufficiently large constant condition, the authors construct the dual-certificate matrices with probability at least 1 minus a stated error bound.The matrices satisfy the strict positivity conditions and make ΛV = 0 and Λ ⪰ 0.Source: §6.4.3 · p. 32

SUPPLEMENTARY MATERIAL

The supplementary article supplies proofs for several lemmas used in the paper.

SUPPLEMENTARY MATERIAL

  • The supplement is associated with the paper on robust community detection in the presence of arbitrary outlier nodes.It is identified by DOI 10.1214/14-AOS1290SUPP.Source: SUPPLEMENTARY MATERIAL · p. 33
  • The supplement to “Robust and computationally feasible community detection in the presence of arbitrary outliers nodes” provides proofs to Lemmas 6.6, 6.7, 6.8, 6.9, 6.10, and 6.11.Source: SUPPLEMENTARY MATERIAL · p. 33
  • The supplement is provided as a PDF.Source: SUPPLEMENTARY MATERIAL · p. 33

Related papers

Loading 1404.6000v4…