{"id":"b0983c21-882d-4767-b0af-7d6ad0255880","arxiv_id":"1908.02096","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A Hermitian-matrix spectral clustering algorithm provably recovers clusters defined by edge orientation in directed stochastic block models and reveals migration flow imbalances in US county data.","lead":"This paper proposes a spectral clustering method for directed graphs that encodes edge directions in a complex Hermitian matrix, with theoretical guarantees on a stochastic block model and promising results on US migration data. The method surfaces directional imbalance between clusters, which standard symmetrization-based methods miss.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 2 misstates the row-separation scale of the projection Q; as written it does not establish the claimed misclassification bound.","rationale":"The paper's headline theoretical contribution is Theorem 2; the real-data section is exploratory, so a bug in the proof of Theorem 2 is the most load-bearing issue I can identify. The flaw is not an external disagreement with consensus; it is an internal scale error in the projection matrix. I verified the row-distance calculation directly from the definitions in Sections 2 and 4. The paper deserves credit for a clear DSBM, an interesting Hermitian formulation, and a broad set of experiments on synthetic data (Figures 3-4, 10-11). The proof can likely be repaired by carrying the \\sqrt{n} factor through and using the rank bound on the Frobenius norm, so I do not recommend rejection. However, the current manuscript does not provide a valid proof of its central guarantee as printed. The reader's concern about the DSBM p = q assumption versus real data is legitimate but secondary; the proof bug is more central. The verdict remains conditional, with the additional explicit condition that the proof of Theorem 2 be corrected or the theorem restated with a valid proof.","tokens_in":15553,"tokens_out":23139,"duration_ms":258317,"concrete_test":"Independently re-derive the proof of Theorem 2 with the correct normalization: set Q = (1/n) U P_{Im(\\tilde F)} U^T, note that \\|c_j - c_l\\| = theta / \\sqrt{n}, replace the k-means cost upper bound by \\|P-Q\\|_F^2 ≤ 2k\\|P-Q\\|^2, and re-run the separation/misclassification argument to see whether the stated O(k^2 log n / (rho^2 theta^2 p)) bound still follows. Also run a numerical sanity check: for k = 2, n = 100, and perfect orientation F_{01} = 1, the rows of Q for the two clusters are about \\sqrt{2/n} ≈ 0.141 apart, not \\sqrt{2} ≈ 1.414. If the corrected derivation does not yield the claimed bound, Theorem 2 is unproven.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central theoretical guarantee rests on the proof of Theorem 2 in Appendix A.1. That proof asserts that rows of Q = P_{Im(EA)} corresponding to different clusters are at least theta apart. This is false under the paper's own definitions. Since EA = p U \\tilde F U^T with U the n-per-cluster indicator matrix and U^T U = nI, the projection is Q = (1/n) U P_{Im(\\tilde F)} U^T. Hence the row for a vertex in C_j equals (1/n) times the j-th row of P_{Im(\\tilde F)} repeated over coordinates, and the Euclidean distance between rows of clusters j and l is \\|P_{Im(\\tilde F)}(j,·) - P_{Im(\\tilde F)}(l,·)\\| / \\sqrt{n} = theta / \\sqrt{n}, not theta. Equation (10) and the lower bound n theta^2 / 32 that follow use the theta scale, while equation (11) upper-bounds the k-means cost by \\|P-Q\\|^2 · kn. These are two compensating errors: the row separation is overestimated by a factor \\sqrt{n}, and the cost upper bound is overestimated by a factor n. Replacing (11) with the rank-based bound \\|P-Q\\|_F^2 ≤ 2k\\|P-Q\\|^2 appears to restore the stated O(k^2 log n / (rho^2 theta^2 p)) bound, so the theorem may be repairable; but the printed proof does not prove it. A separate inconsistency remains: Section 3 sets epsilon = 10 sqrt(pn log(pn)), while Lemma 7 uses epsilon = 20 sqrt(pkn log n).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a spectral clustering algorithm for directed graphs based on a complex-valued Hermitian adjacency matrix whose off-diagonal entries are ±i according to edge direction. The algorithm computes the projection onto the eigenspace of the eigenvalues with absolute value above a threshold and applies k-means to the rows of this projection. The authors introduce a directed stochastic block model (DSBM) in which cluster structure is encoded primarily in edge orientations through a matrix F, and they prove a misclassification bound for the algorithm under a spectral gap condition when p=q (Theorem 2). The paper also reports experiments on synthetic DSBM graphs and on US migration and political blog networks, arguing that the Hermitian method uncovers cut-imbalance structures that symmetrized spectral methods miss. An appendix contains the proof of Theorem 2 and additional experiments.","tokens_in":15881,"tokens_out":7350,"duration_ms":74658,"significance":"If the proof is corrected, the paper makes a useful contribution: it gives a spectral method that targets orientation-based cluster structure rather than density-based structure, and it provides a model in which this signal is theoretically identifiable. The explicit DSBM, the use of concentration and Davis-Kahan perturbation arguments, and the breadth of the experimental comparison are strengths. A correct recovery guarantee for a directed clustering algorithm with a non-symmetric objective would be a real advance. However, the proof as printed contains two compensating scaling errors, and the real-data evaluation is built on a score aligned with the method's own objective, so the empirical conclusions need additional support before the claims can be accepted.","major_comments":[{"comment":"The proof of Theorem 2 misstates the scale of the row separation of Q. Since Q = (1/n) U P_{Im(\\tilde F)} U^T, the Euclidean distance between the rows of Q for vertices in clusters j and l is ||P_{Im(\\tilde F)}(j,·) - P_{Im(\\tilde F)}(l,·)|| / sqrt(n) = theta / sqrt(n), not theta as claimed in the text before Eq. (10). Consequently Eq. (10) overestimates the separation by a factor sqrt(n). Eq. (11) then upper-bounds the k-means cost by ||P-Q||^2 · kn, whereas the correct rank-based bound is ||P-Q||_F^2 ≤ 2k ||P-Q||^2, which is smaller by a factor n. These two errors compensate: replacing both by their correct values preserves the stated O(k^2 log n / (\\tilde\\rho^2 \\theta^2 p)) bound. The proof therefore needs to be rewritten with the correct scales; as printed it does not establish the theorem.","section":"Appendix A.1, proof of Theorem 2, Eqs. (10) and (11)"},{"comment":"The parameter epsilon is defined inconsistently. Section 3 states epsilon = 10 sqrt(pn log(pn)), while Lemma 7 and the proof of Theorem 2 use epsilon = 20 sqrt(pkn log n). Since Lemma 6 gives ||A - EA|| ≤ 10 sqrt(pkn log n), the Davis-Kahan argument in Lemma 7 requires epsilon to exceed this noise level. The main-text value does not match the analysis and also depends on pn rather than pkn. The authors should use a single consistent definition and state explicitly which threshold is used in Algorithm 1 and in the theorem.","section":"Section 3 and Appendix A.1, Lemma 7"},{"comment":"The real-data comparison is circular. The cut-imbalance scores CI, CIsize, and CIvol measure precisely the type of directed imbalance that the Hermitian method is designed to expose and that the DSBM encodes. Comparing against algorithms that optimize symmetrized density-based objectives on this metric is favorable to the proposed method by construction. The socio-economic interpretation in the abstract and Section 1 is not supported by quantitative external data; no county-level economic variables are used to validate the claim that recovered clusters share similar socio-economic profiles. For the BLOG network, party labels are available and the paper could report external accuracy (e.g., ARI or NMI against Conservative/Liberal labels) rather than relying only on the method-specific score.","section":"Section 5, Eqs. (6)-(8)"},{"comment":"The theoretical guarantee in Theorem 2 assumes p=q and equal cluster sizes, but all real-world networks considered in Section 5 violate these assumptions (e.g., the US migration network has heterogeneous edge densities and cluster sizes). The paper should explicitly acknowledge this gap between the theory and the real-data experiments, and ideally add a robustness study, such as DSBM simulations with p≠q or with unbalanced cluster sizes, to indicate whether the method's performance degrades gracefully outside the theorem's regime.","section":"Section 4, Theorem 2, and Section 5"}],"minor_comments":[{"comment":"The same symbol c_j is used both for a row of Q and for the mean of the rows of P restricted to cluster C_j. Please use distinct notation (for example, q_j and μ_j) to avoid confusion.","section":"Appendix A.1, proof of Theorem 2"},{"comment":"The text refers to Figure 2 for the cyclic flow structure, but the figure is not visible in the manuscript version provided. Please verify that the figure is included in the compiled PDF.","section":"Section 2, example"},{"comment":"The matrix A_rw = D^{-1} A is not itself Hermitian; the statement that it 'has N real eigenvalues' should be phrased as 'is similar to a Hermitian matrix and therefore has real eigenvalues and a complete set of eigenvectors.'","section":"Eq. (4) and surrounding text"},{"comment":"The text states that Figure 4 reports the ARI of 'a randomly generated graph,' while Figures 3 and 11 report averages over 10 runs. Please clarify whether Figure 4 is a single instance or an average, and if it is a single instance, add error bars or a note on variability.","section":"Section 5, Figure 4"},{"comment":"In Algorithm 1, the threshold epsilon is an input parameter, but the subsequent paragraph recommends a specific value. Please state explicitly whether the theoretical guarantees require the specific value or hold for any epsilon above the noise bound.","section":"Section 3, Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The proof error in Theorem 2 is serious but appears to be a repairable scaling mistake; the fact that the two errors compensate suggests the stated bound is likely correct. I would not recommend rejection on that basis alone. The main revision should provide a corrected proof and address the metric-alignment issue in the real-data evaluation. The paper's central idea is interesting and potentially publishable in a good journal once these points are resolved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know — the Hermitian adjacency matrix idea is worth a look, and the synthetic results are strong, but the proof of the main theorem has a scale error that is currently unaddressed. It looks repairable, but as printed the theorem does not follow.\n\nWhat's actually new: the paper applies the complex Hermitian adjacency matrix from Guo–Mohar and Singer–Wu to directed spectral clustering, and studies a DSBM with p=q where the cluster structure is entirely in edge orientations. That's a clean model, and the synthetic comparison against symmetrization baselines is genuinely convincing: on cyclic and complete meta-graphs the Hermitian method substantially outperforms DI-SIM, Bi-Sym, and DD-Sym. The US migration example provides a nice qualitative illustration of orientation-based structure.\n\nThe soft spot is the proof of Theorem 2. In Appendix A.1, the projection Q = P_{Im(EA)} has rows that are constant on clusters but with magnitude 1/n per entry, so the Euclidean distance between rows from different clusters is theta/sqrt(n), not theta. Equation (10) thus overestimates the separation by a factor sqrt(n). The proof then upper-bounds the k-means cost by ||P-Q||^2 * kn, which is a factor n too large for a rank-constrained projector. The stress-test note is right: these two errors plausibly compensate — replace (11) with the rank-based bound ||P-Q||_F^2 <= 2k||P-Q||^2 and the stated O(k^2 log n/(rho^2 theta^2 p)) bound comes back. So the theorem may be true, but the printed proof doesn't show it. That's worth fixing before the theory is cited.\n\nThe real-data evaluation is the second soft spot, and here the abstract oversells. The cut-imbalance score is specifically designed to reward the structure the Hermitian method targets, so it's not a neutral benchmark against methods optimizing a different objective. The socio-economic profile claim is visual, and the top-pair comparisons lack error bars or a null model. None of this is fatal, but it should be dialed back. Also minor: epsilon is 10 sqrt(pn log pn) in Section 3 and 20 sqrt(pkn log n) in Lemma 7.\n\nBottom line: this is a paper for anyone working on directed community detection. It deserves a serious referee — I'd send it out, but with a request for major revision focused on the proof repair and the calibration of the empirical claims.","headline":"Hermitian clustering is promising and the theorem is likely fixable, but the printed proof has a sqrt(n) scale error that must be addressed.","tokens_in":16401,"tokens_out":8436,"would_cite":true,"duration_ms":86998,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Direction-only clusters yield to a complex adjacency matrix.","keywords":["spectral clustering","directed graphs","Hermitian adjacency matrix","directed stochastic block model","edge orientation","cut imbalance","migration networks","community detection"],"falsifier":"Take a DSBM with $p=q$, a cyclic meta-graph with $k=5$, $n=1000$, $\\eta=0.2$, and $p$ above the theorem's lower bound; if the number of misclassified vertices does not match $O(k^4\\log n/((1-2\\eta)^2p))$ over many trials, or if on the migration data the recovered clusters correlate only with geography and not with any county economic indicators, the central claims would be in doubt.","tokens_in":15360,"feed_emoji":"🧭","tokens_out":9859,"duration_ms":91961,"temperature":0.7,"pith_summary":"The paper argues that clusters in a directed graph can be encoded entirely in the direction edges point, with every vertex having the same expected degree, and that this kind of structure is destroyed by the symmetrization step used by standard spectral clustering. It proposes to work instead with a complex Hermitian adjacency matrix $A$ defined by $A_{uv}=\\mathrm{i}$ for an edge $u\\to v$, whose eigenvalues are real, and to cluster the rows of the projection onto the leading eigenspaces. In a directed stochastic block model with equal edge probabilities $p=q$, the paper proves that this algorithm recovers the planted clusters up to $O(k^2/(\\tilde\\rho^2\\theta^2 p)\\log n)$ misclassified vertices, provided the meta-graph matrix $F$ satisfies a spectral-gap condition and has a $\\theta$-distinguishing image. On US county-to-county migration data, the method clusters counties with similar socio-economic profiles even when geographically distant, revealing net movement from rural to more urbanized areas, something the paper says prior symmetrization-based methods cannot see.","feed_headline":"Direction-only clusters yield to a complex adjacency matrix","feed_subtitle":"The paper proves a recovery bound and finds rural-to-urban migration flows that symmetrization misses.","key_machinery":"The load-bearing object is the Hermitian adjacency matrix $A$, defined by $A_{uv}=\\mathrm{i}$ when $u\\to v$ and $A_{vu}=-\\mathrm{i}$; because it is Hermitian, its eigenvalues are real even though it encodes directed edges through $\\mathrm{i}$. The second ingredient is the meta-graph matrix $F$ and its derived matrix $\\tilde F=(2F-\\mathbf{1}_{k\\times k})\\mathrm{i}$; $\\tilde F$ has a $\\theta$-distinguishing image when the projection rows for different clusters are at least $\\theta$ apart, and its spectral gap $\\tilde\\rho$ measures how far its nonzero eigenvalues are from zero. The argument uses concentration of $A$ around its expectation, a bound on how much the projection onto leading eigenspaces shifts under this perturbation, and a $k$-means cost argument showing that well-separated rows force most vertices to be assigned to the correct cluster.","core_discovery":"The central discovery is that the direction-only cluster structure of a digraph is carried by the low-rank meta-graph matrix $F$, and that this structure is visible in the top eigenspaces of the Hermitian matrix $A=(M-M^{\\top})\\mathrm{i}$. For a graph from the DSBM with $p=q$, the expected matrix $\\mathbb{E}A$ is block-constant on clusters, and Algorithm 1's projection $P$ is close to the ideal projection $P_{\\mathrm{Im}(\\tilde F)}\\otimes \\tfrac{1}{n}\\mathbf{1}_{n\\times n}$. Because $\\tilde F=(2F-\\mathbf{1}_{k\\times k})\\mathrm{i}$ has a $\\theta$-distinguishing image, rows of the ideal projection belonging to different clusters are separated by at least $\\theta$; perturbation control then leaves a separation of $\\theta/2$ in the computed embedding, and $k$-means misclassifies only the stated number of vertices. The same logic makes $A$ implicitly weight pairs of vertices by their common parents and offspring while penalizing mismatched directional relations, which is why the method surfaces asymmetric flow between clusters rather than internally dense communities.","pith_inferences":["A natural extension is to prove a normalized version of Theorem 2 for $A_{\\mathrm{rw}}=D^{-1}A$; the experiments suggest it works better on skewed data, but the paper's guarantee only covers the unnormalized setting.","The $\\theta$-distinguishing-image condition could be checked in practice by estimating the eigenvalues of $\\tilde F$ from the outliers of the empirical spectrum, giving a data-driven way to choose the number of clusters $k$.","Because the core object is the skew-symmetric part of a weighted matrix, the same approach could apply to pairwise comparison and tournament data where cycles of dominance, not density, define the structure.","The socio-economic interpretation of the US migration clusters is an inference from the recovered partition; a direct validation would regress cluster membership on county income and urbanization covariates."],"forward_implications":["Clusters that are invisible to degrees, because every vertex has the same expected in- and out-degree, become recoverable through the Hermitian eigenspace.","In the cyclic block model, the misclassification bound is $O(k^4\\log n/((1-2\\eta)^2p))$ once $p=\\omega(k^3\\log n/((1-2\\eta)^2n))$, giving concrete parameter thresholds for guaranteed recovery.","The cut-imbalance ratio $\\mathrm{CI}(X,Y)$ gives a quantitative, direction-aware objective for pairs of clusters, so the method can name which pairs exchange asymmetric flow.","On migration networks the clusters trace flows from rural to urbanized areas, so the same pipeline can be applied to other origin-destination flow data to expose asymmetric exchange.","Using $A$ avoids forming $M^{\\top}M+MM^{\\top}$, so directional information is captured without expensive matrix multiplications."],"supporting_citations":[{"why":"Introduces the Hermitian adjacency matrix and its real-eigenvalue spectral theory, the matrix the algorithm is built on.","marker":"[11, 25]"},{"why":"Defines the co-clustering directed stochastic block model that the paper's DSBM specializes and supplies the comparison baselines.","marker":"[22]"},{"why":"Supplies the classical stochastic block model whose planted-cluster structure the DSBM generalizes to directed edges.","marker":"[12]"},{"why":"Provides the eigenvector perturbation bound used to control the distance between the empirical and ideal projections.","marker":"[8]"},{"why":"Gives the matrix concentration inequality that shows A is close to its expectation with high probability.","marker":"[4]"},{"why":"Establishes that spectral gap governs stochastic block model recovery, the precedent for the spectral-gap condition in Theorem 2.","marker":"[15]"},{"why":"Describes symmetrization approaches whose loss of directional information motivates the new matrix.","marker":"[23]"},{"why":"Provides the US county-to-county migration data used for the main real-world demonstration.","marker":"[3, 20]"}],"fun_headline_variants":["Complex Hermitian matrix exposes direction-only clusters","Spectral clustering that respects edge direction in digraphs","Hermitian trick finds migration clusters symmetrization misses","Direction-aware clustering for directed graphs","Rural-to-urban flow revealed by complex adjacency"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee assumes every cluster has the same size, every vertex has the same expected degree, and all cluster information lives in edge directions ($p=q$), so real digraphs with heterogeneous degrees or cluster sizes do not directly inherit the theorem.","fun_headline_variants_meta":{"raw":{"variants":["Complex Hermitian matrix exposes direction-only clusters","Spectral clustering that respects edge direction in digraphs","Hermitian trick finds migration clusters symmetrization misses","Direction-aware clustering for directed graphs","Rural-to-urban flow revealed by complex adjacency"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000249,"raw_usage":{"total_tokens":1572,"prompt_tokens":988,"completion_tokens":584,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":513}},"tokens_in":604,"tokens_out":584,"duration_ms":6367,"temperature":1.0,"reasoning_tokens":513,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:53:33.245301+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a DSBM with $p=q$, a cyclic meta-graph with $k=5$, $n=1000$, $\\eta=0.2$, and $p$ above the theorem's lower bound; if the number of misclassified vertices does not match $O(k^4\\log n/((1-2\\eta)^2p))$ over many trials, or if on the migration data the recovered clusters correlate only with geography and not with any county economic indicators, the central claims would be in doubt.","supporting_citations":[{"cited_title":"Co-clustering directed graphs to discover asymmetries and directional communities.Proceedings of the National Academy of Sciences, 113(45):12679– 12684, 2016","cited_arxiv_id":null,"evidence_quote":"Defines the co-clustering directed stochastic block model that the paper's DSBM specializes and supplies the comparison baselines."},{"cited_title":"Stochasticblockmodels: first steps.Social Networks, 5(2):109–137, 1983","cited_arxiv_id":null,"evidence_quote":"Supplies the classical stochastic block model whose planted-cluster structure the DSBM generalizes to directed edges."},{"cited_title":"Davis and W","cited_arxiv_id":null,"evidence_quote":"Provides the eigenvector perturbation bound used to control the distance between the empirical and ideal projections."},{"cited_title":"On the spectra of general random graphs.Electronic Journal of Combinatorics, 18(1), 2011","cited_arxiv_id":null,"evidence_quote":"Gives the matrix concentration inequality that shows A is close to its expectation with high probability."},{"cited_title":"Symmetrizations for clustering directed graphs","cited_arxiv_id":null,"evidence_quote":"Describes symmetrization approaches whose loss of directional information motivates the new matrix."}],"review_version":1}