Pith. sign in

REVIEW 4 major objections 5 minor 84 references

The Spectral Barycentre of a Set of Graphs with Community Structure

T0 review · 4 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A barycentre graph can be rebuilt from eigenvalues alone by choosing a greedy Soules basis; for balanced stochastic block models it converges almost surely to the population mean as the graph grows.

desk verdict A clever Soules-basis algorithm for spectral barycentres whose advertised convergence guarantee is only proved for the population matrix, not the sample input—worth refereeing but needs a finite-sample gap fixed. read the letter →

arxiv 2502.00038 v3 pith:3D4P6FBD submitted 2025-01-26 cs.SI cs.LGphysics.data-anstat.ML

François G. Meyer This is my paper · ORCID
classification cs.SIcs.LGphysics.data-anstat.ML MSC 05C5060B2062H30
keywords barycentregraphFréchetmeanSoulesbasisnormalizedLaplacianspectralpseudo-distancestochasticblockmodelgraph-valueddatacommunitystructure
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper attacks a practical obstacle in machine learning on graph-valued data: the natural spectral distance between graphs determines only the eigenvalues of the average graph, never its eigenvectors, so the 'barycentre graph' that minimizes that distance is not uniquely determined. The proposal is to pin down the missing eigenvectors with a structural constraint: choose an orthonormal basis from the library of Soules bases, greedily splitting index intervals so that each new vector's zero-crossing falls on a community boundary of the sample. The central claim is that for graphs drawn from a balanced stochastic block model, this recipe produces a barycentre whose normalized Laplacian matches the population mean, and the barycentre itself converges to the population mean adjacency matrix as the graph size grows, with probability tending to one. If true, this gives a fast, principled way to summarize a dataset of networks, recovering class or community structure that a plain entrywise average of adjacency matrices washes out.

What carries the argument

The machinery is the Soules basis: an orthonormal basis of $\mathbb{R}^n$ generated recursively by splitting an index interval into two sub-intervals and creating a vector that is piecewise constant and changes sign exactly at the split. Every Soules basis satisfies $\sum_{k=1}^n \psi_k\psi_k^T = I$ and, for decreasing eigenvalue sequences, $\Psi\operatorname{diag}(\lambda)\Psi^T$ has the sign pattern of a graph Laplacian, which makes the family a ready-made solution set for the inverse eigenvalue problem. The load-bearing property is the alignment of zero-crossings with block boundaries: Lemma 7 computes $|\langle \psi\psi^T, P\rangle|^2$ for a two-block edge-probability matrix and shows it is maximized exactly when the split point equals the block boundary, and Lemma 9 proves by induction that $M$ greedy splits of the population mean $P = \sum_m (p_m-q)\mathbf{1}_{B_m}\mathbf{1}_{B_m}^T + qJ$ recover all $M$ blocks. A second component is the regularized spectrum: the $M$ smallest sample-mean eigenvalues are kept, while the noisy bulk eigenvalues are replaced by the deterministic limits $l_m = Mq/(p+(M-1)q)$ for $2 \le m \le M$ and $l_m = 1$ for $m > M$, so the reconstruction is driven by community structure rather than sampling noise.

What would settle it

Two concrete checks would settle the claim. First, in Monte Carlo experiments on balanced stochastic block models, record the fraction of trials in which the first $M$ splits selected by Algorithm 1 from the sample mean $\widehat{\mathbb{E}}_T[P]$ coincide with the true block boundaries as $n$ grows: the claimed convergence requires this fraction to tend to one, while the deferred finite-sample analysis predicts a misalignment rate that should decay with $n$ and $T$. Second, measure $\|\widehat{L}_M - \mathcal{L}\|_F$ numerically at increasing $n$: the proof derives a decay of order $\sqrt{\log n / n}$, whereas the lemma as stated only promises $O(1)$, so the measured exponent settles which statement is true, and splits that systematically land off the block boundaries near the community-detection threshold would falsify the central claim.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the inverse problem behind the spectral barycentre — given the sample-mean eigenvalues $\widehat{\mathbb{E}}_T[\lambda]$, find an orthonormal $\Psi$ satisfying $\Psi \operatorname{diag}(\widehat{\mathbb{E}}_T[\lambda])\Psi^T = \mathcal{L}$, the normalized Laplacian of the population mean — is solvable by a customized Soules basis. Algorithm 1 builds $\Psi$ level by level: starting from $\psi_1 = n^{-1/2}\mathbf{1}$, each new Soules vector is the split of an existing index interval that maximizes $|\langle \psi \psi^T, \widehat{\mathbb{E}}_T[P]\rangle|^2$. Lemma 5 shows that when the input is the population mean $P$ of a stochastic block model, the first $M$ such vectors recover exactly the $M$ blocks; Lemma 2 shows that with the $n-M$ bulk eigenvalues replaced by their deterministic limits, the reconstructed Laplacian converges to $\mathcal{L}$ with probability tending to one. The paper concludes that the barycentre $\widehat{\mu}^M_T = \widehat{D}^{1/2}(I - \widehat{L}_M)\widehat{D}^{1/2}$ converges to $\mathbb{E}[\mathbb{P}]$ asymptotically almost surely for balanced stochastic block models.

Load-bearing premise

The proof that the greedy splits recover the true community blocks is run on the exact population mean of the random model, not on the noisy sample mean, so the claimed convergence stands or falls on the deferred finite-sample analysis showing that sampling noise cannot shift the splits.

Editorial extensions

If this is right

  • For a sample of graphs drawn from a balanced stochastic block model, the algorithm's barycentre converges to the population mean adjacency matrix as the graph size grows, with probability tending to one.
  • The eigenvector search runs in time linear in the number of vertices — about $Mn$ operations — so the barycentre can be computed for large graphs.
  • The regularization step, replacing the noisy bulk eigenvalues with their deterministic limits, is what keeps sampling noise from contaminating the reconstruction, and the paper's convergence proof relies on it.
  • On the primary-school contact graphs, the barycentre recovers the ten classes even though the entrywise sample-mean adjacency matrix washes the class structure out.
  • The same inverse-eigenvalue construction opens a route to spectral graph synthesis with theoretical guarantees, which the paper identifies as a payoff of the approach.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension the paper explicitly defers is the finite-sample analysis: the reconstruction error should split into a spectral term of order $\sqrt{\log n/n}$ and a term driven by misaligned spectral clustering, and the outlier at $n=374$ in the paper's own convergence measurement is where the second term should show up.
  • Because the distance uses normalized-Laplacian eigenvalues, which live on the fixed interval $[0,2]$, the same construction could average graphs of different sizes by interpolating their spectra, making the barycentre independent of node correspondence — the paper mentions this direction but does not develop it.
  • The greedy Soules splitter is in effect a hierarchical community-detection procedure that maximizes spectral energy at each cut; if the block-recovery lemma is as robust as claimed, the same algorithm could serve as a consistency-certified graphon or stochastic-block-model estimator rather than only a barycentre routine.
  • The paper's convergence statement is asymptotic in graph size with the sample size $T$ held fixed; a check it does not perform is whether the barycentre also converges as $T \to \infty$ at fixed $n$, which is the regime most practitioners would actually encounter.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper defines a barycentre graph for graph-valued data using a spectral pseudo-distance based on ordered normalized Laplacian eigenvalues, and addresses the missing-eigenvector problem by constraining the barycentre eigenvectors to lie in a Soules basis. For balanced stochastic block models, it claims in the abstract and in Section 1.6 that the proposed Algorithm 1 returns a barycentre converging asymptotically almost surely to the population mean. The theoretical sections prove block recovery for a greedy Soules split algorithm when the input is the population mean matrix P, and the experimental sections report Monte Carlo and real-data results.

Significance. If the main claim were fully established, this would be a useful contribution: the Soules-basis formulation is elegant, the inverse-eigenvalue framing is principled, and the public code and real-data demonstrations are valuable. The paper also makes a concrete, falsifiable prediction about the behaviour of a spectral barycentre under a balanced SBM. However, the advertised guarantee is currently proved only for an idealized oracle input, not for the sample mean matrix that Algorithm 1 actually receives, and the exact equality statement in Eq. (13) is not supported by the norm bounds that are proved. The contribution at this stage is therefore a promising heuristic algorithm with a partial theoretical analysis rather than a proven estimator.

major comments (4)
  1. [§4.3, Lemmas 5 and 9] The central convergence claim in the abstract and in Section 1.6 concerns Algorithm 1 run on T random realizations, but the only recovery results, Lemma 5 and Lemma 9, assume that Algorithm 1 is given the population mean matrix P, not the sample mean ĥ𝔼_T[ℙ]. Section 4.3 states this explicitly and defers finite-sample analysis to future work. Consequently, no argument controls the event that the greedy argmax splits in Algorithm 1 remain aligned with the true block boundaries under sample noise; the numerical evidence in Fig. 8-left is a mean-squared-error curve, not a split-recovery frequency. This is load-bearing because the random data enter the algorithm exactly at this split-selection step, and the spectral-clustering pre-processing of Section 4.2 is acknowledged to be imperfect.
  2. [§2, Lemma 2 and §1.6] Lemma 2 states a Frobenius bound ||ĥL^M - L||_F = O(1) with probability converging to 1, and then concludes that Eq. (13) holds. An O(1) bound does not imply convergence, and even if the proof is corrected to the vanishing O(sqrt(log n / n)) rate that appears in Eq. (26), a high-probability norm bound does not imply the exact equality event in Eq. (13). The abstract's 'almost surely' is also stronger than the 'probability converging to 1' statements used in the proofs of Lemma 2 and Lemma 1.
  3. [Corollary 1 vs. Lemma 5] Lemma 5 states that the first M Soules vectors returned by Algorithm 1 satisfy ∑_{k=1}^M ψ_kψ_k^T(i,j) = 1/|J_m| inside the recovered blocks, whereas Eq. (19) in Lemma 2 requires the value M/n. These two expressions agree only in the balanced case with equal block sizes. Corollary 1 therefore overclaims that Lemma 5 solves Eq. (19) for general SBM; the lemma's extension to unbalanced SBM is not compatible with the sufficient condition used in the main convergence lemma.
  4. [§2, Eqs. (22)–(26)] The proof of Lemma 2 equates ĥL^M - L with ε_n, but the deterministic diagonal term arising from the identity-minus-block-projection in Eq. (24) has diagonal entries 1 - [(1-c)M + c]/n rather than 1, so the displayed equality in Eq. (25) is not correct as written. This discrepancy is O(1/sqrt n) in Frobenius norm and may not change the asymptotic rate, but it means the algebra in the central lemma must be repaired before the convergence statement can be accepted.
minor comments (5)
  1. [§1.8.3] The text 'an French primary school' should read 'a French primary school'.
  2. [Algorithm 1 and §4.2.1] Algorithm 1 contains a malformed expression `coeff)` on line 15 and does not reset the loop variable i* for each block; the pseudocode as printed would not execute cleanly. Separately, the complexity claim of O(Mn) assumes only M levels are processed, while the pseudocode loops over all n-1 levels; the stated linear-in-n complexity needs clarification or correction.
  3. [Lemma 7] The proof of Lemma 7 assumes p0 + p1 - 2q > 0 when concluding that the maximum occurs at i* = j; the statement should include the SBM condition p_m > q, since the squared objective can behave differently when that coefficient is negative.
  4. [Throughout] The symbol M is overloaded: it denotes the number of communities, the superscript in ĥbµ^M_T(ℙ), and the upper limit in the partial sum of Soules eigenprojectors. The paper would be easier to read with a distinct notation for at least one of these uses.
  5. [§1.9 and §7] The paper says the code is publicly shared and gives a repository URL, which is good, but the main theoretical claims are stated in the abstract without the caveat, explicitly acknowledged in Section 4.3, that the analysis applies to the population input P rather than the sample mean input ĥ𝔼_T[ℙ].

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main convergence claim is unproved for random inputs (Section 4.3 analyzes the population matrix instead), but this is a correctness or stability gap, not a reduction of the output to its input by construction.

full rationale

The paper's target P = E[P] is not the input to Algorithm 1 in the actual procedure: Algorithm 1 takes the sample mean bE_T[P] (Section 4.1), and Section 4.3 explicitly states that the analysis is performed under the assumption that the input is the population equivalent P, with finite-sample analysis left to future work. Consequently, the a.a.s. convergence advertised in the abstract does not follow from the lemmas as written; Lemma 5 and Lemma 9 establish that, when the input is P, the greedy Soules splits recover the SBM blocks. That is a substantive identifiability statement about the algorithm's objective (Eq. 32 maximizes alignment with the input matrix, without knowing block labels), not a tautology, since the output is not the identity function of the input. Equation (19) is a sufficient condition for the reconstruction error to vanish; proving that the algorithm produces a basis satisfying it is exactly the content of Lemma 5 and Lemma 9, and the condition is not hard-coded into Algorithm 1. Lemma 1 is an external eigenvalue concentration result, and the Soules-basis lemmas are cited from Elsner-Nabben-Neumann and Soules, not from the author's own prior work; self-references ([36], [57], [59]) are contextual and not load-bearing. The statement of Lemma 2 (||bL_M - L||_F = O(1)) as written cannot imply the exact equality in Eq. (13), and even a corrected o(1) norm bound would not imply exact equality; this is a correctness risk, not circularity. The honest non-finding is therefore that no circular step is exhibited, and the paper should be scored low on circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim rests on imported eigenvalue concentration results, on a balanced SBM with interval-aligned blocks, and on an oracle-input assumption that is explicitly outside the actual algorithm's data regime. The only fitted quantities are M and the regularized eigenvalues; no new entities are postulated.

free parameters (3)
  • Number of communities M = assumed known in theory; estimated with external methods in practice
    Eq. (18) rebuilds the Laplacian using only the first M sample eigenvalues and sets the rest to 1; Lemma 5 and Corollary 1 require the true M. Section 6.1.3 shows the reconstruction degrades when M grows.
  • Bulk eigenvalues lambda_m for m > M = 1
    Eq. (17) replaces the sample eigenvalues in the bulk with the deterministic SBM limit l_m=1, a regularization that is not derived from the original optimization problem Eq. (1).
  • Within-block degree estimates d_hat_m = sum of sample-mean edge weights inside each recovered block (Eq. 36)
    The adjacency matrix reconstruction Eq. (39) rescales the normalized Laplacian by these degree estimates; any error in block recovery changes the reported barycentre.
assumptions (4)
  • standard math Lemma 1 (Proposition 4.3 of reference 54): eigenvalues of the normalized Laplacian of an SBM concentrate around l_m with error O(sqrt(log n/n))
    Imported from cited literature; used in Lemma 2 to replace sample eigenvalues with deterministic limits.
  • domain assumption The SBM blocks are contiguous intervals in the node ordering used by Algorithm 1, and for the main theorem the SBM is balanced with equal within-block probabilities.
    Algorithm 1 splits ordered intervals only (Eq. 27); Lemma 5 concludes the discovered intervals equal the blocks, which requires blocks to be intervals in the algorithm's ordering. The balanced-SBM restriction is stated in the abstract and Section 1.8.1.
  • ad hoc to paper Algorithm 1 is analyzed on the population mean matrix P instead of the sample mean hat E_T[P].
    Section 4.3: 'Our analysis of Algorithm 1 is performed under the assumption that the input to the algorithm is not the sample mean adjacency matrix but its population equivalent.' This is not part of the actual data regime.
  • domain assumption Within-block edge probability p_i is much larger than the cross-block probability q, so communities are detectable.
    Section 5.1: 'Since we always have p_i >> q (when p_i is close to q, communities can no longer be detected).' This is needed for degree estimation and block recovery.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Spectral Barycentre of a Set of Graphs with Community Structure." pith.science (2026). https://pith.science/paper/3D4P6FBD

@misc{pith2026250200038,
  author       = {Pith},
  title        = {Pith review of: The Spectral Barycentre of a Set of Graphs with Community Structure},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3D4P6FBD}},
  note         = {Machine review of arXiv:2502.00038}
}
read the original abstract

The notion of barycentre graph is of crucial importance for machine learning algorithms that process graph-valued data. The barycentre graph is a "summary graph" that captures the mean topology and connectivity structure of a training dataset of graphs. The construction of a barycentre requires the definition of a metric to quantify distances between pairs of graphs. In this work, we use a multiscale spectral distance that is defined using the eigenvalues of the normalized graph Laplacian. The eigenvalues -- but not the eigenvectors -- of the normalized Laplacian of the barycentre graph can be determined from the optimization problem that defines the barycentre. In this work, we propose a structural constraint on the eigenvectors of the normalized graph Laplacian of the barycentre graph that guarantees that the barycentre inherits the topological structure of the graphs in the sample dataset. The eigenvectors can be computed using an algorithm that explores the large library of Soules bases. When the graphs are random realizations of a balanced stochastic block model, then our algorithm returns a barycentre that converges asymptotically (in the limit of large graph size) almost-surely to the population mean of the graphs. We perform Monte Carlo simulations to validate the theoretical properties of the estimator; we conduct experiments on real-life graphs that suggest that our approach works beyond the controlled environment of stochastic block models.

Figures

Figures reproduced from arXiv: 2502.00038 by the authors.

Figure 1
Figure 1. Dynamic face-to-face contact graphs (top: adjacency matrix; bottom: graphical representation). The nodes in [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Distribution of the eigenvalues of L in the morning (left) and afternoon (right). For both distributions the ten smallest eigenvalues are separated from the bulk. 1.9 Content of the paper: overview of the results The main contribution of this work is a fast algorithm to compute the barycentre of a set of graphs with community structure. The barycentre is determined using a Laplacian spectral pseudo-distance. We solv… view at source ↗
Figure 3
Figure 3. Left: ψl+1 is created by splitting the block of indicesI (l) q = [i0,i1] at levellinto two sub-blocks, [i0,i ∗ ]∪[i ∗+ 1,i1] at level l + 1. Right: a node in the Soules binary tree is triggered by the splitting of [i0,i1] = [i0,i ∗ ] ∪ [i ∗ + 1,i1]. The construction of the Soules vectors starts at the coarsest scale with ψ1 = √ n1. The next Soules vector, ψ2, is designed to detect the largest gradient between any pa… view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: Left: starting from level l = 1, one Soules vector ψl is constructed at each level l ⩾ 2 by selecting and then splitting an interval I (l) j over which ∀1 ⩽ k ⩽ l, ψk [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Left: the adjacency matrix of a random realization of the [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: Left: the realization of SBM p, q, n  shown in [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: Left: the edge probability matrix 𝔼 [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]
Figure 8
Figure 8. Figure 8: Left: mean squared error n −2 [PITH_FULL_IMAGE:figures/full_fig_p016_8.png]
Figure 9
Figure 9. Figure 9: Top to bottom, left to right: snapshots of the face-to-face contact graph at times (shown next to each graph) [PITH_FULL_IMAGE:figures/full_fig_p017_9.png]
Figure 10
Figure 10. Figure 10: Morning period. Left: graph of the sample mean adjacency matrix [PITH_FULL_IMAGE:figures/full_fig_p018_10.png]
Figure 11
Figure 11. Figure 11: Afternoon period. Left: graph of the sample mean adjacency matrix [PITH_FULL_IMAGE:figures/full_fig_p018_11.png]
Figure 12
Figure 12. Figure 12: The vector ψl (in blue) is created by splitting a block of indices [i0,i1] at level l − 1 into two sub-blocks, [i0,i ∗ ] ∪ [i ∗ + 1,i1] at level l. We consider the matrix P that is nonzero only on [i0,i1] × [i0,i1], and is piecewise constant on two blocks J0 × J0 (in …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

84 extracted references · 76 canonical work pages

  1. [1]

    Journal of Machine Learning Research 18(177), 1–86 (2018)

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

    2018

  2. [2]

    arXiv preprint arXiv:2305.06353 (2025)

    Agterberg, J., Cape, J.: An overview of asymptotic normality in stochastic blockmodels: Cluster analysis and inference. arXiv preprint arXiv:2305.06353 (2025)

    arXiv 2025

  3. [3]

    In: Advances in Neural Information Processing Systems

    Airoldi, E.M., Costa, T.B., Chan, S.H.: Stochastic blockmodel approximation of a graphon: Theory and consistent estimation. In: Advances in Neural Information Processing Systems. pp. 692–700 (2013)

    2013

  4. [4]

    Communications Physics 4(1), 24 (2021)

    Ferraz de Arruda, G., Tizzani, M., Moreno, Y.: Phase transitions and stability of dynamical processes on hypergraphs. Communications Physics 4(1), 24 (2021)

    2021

  5. [5]

    Sankhya A pp

    Athreya, A., Cape, J., Tang, M.: Eigenvalues of stochastic blockmodel graphs and random graphs with low-rank edge probability matrices. Sankhya A pp. 1–28 (2022)

    2022

  6. [6]

    Now Publishers (2022)

    Avrachenkov, K., Dreveton, M.: Statistical Analysis of Networks. Now Publishers (2022)

    work page 2022

  7. [7]

    arXiv preprint arXiv:2203.07546 (2022)

    Balan, R., Haghani, N., Singh, M.: Permutation invariant representations with applications to graph deep learning. arXiv preprint arXiv:2203.07546 (2022)

    arXiv 2022

  8. [8]

    IEEE/ACM Transactions on Networking27(5), 2125–2136 (2019)

    Baldesi, L., Markopoulou, A., Buttsc, C.T.: Spectral graph forge: A framework for generating synthetic graphs with a target modularity. IEEE/ACM Transactions on Networking27(5), 2125–2136 (2019)

    work page 2019

Show all 84 references
  1. [9]

    Science 286(5439), 509–512 (October 1999)

    Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (October 1999). https://doi.org/10.1.1.226.2025

    1999

  2. [10]

    Bernoulli 31(1), 432 – 456 (2025) 24

    Blanchard, M., Jaffe, A.Q.: Fréchet mean set estimation in the Hausdorff metric, via relaxation. Bernoulli 31(1), 432 – 456 (2025) 24

    2025

  3. [11]

    In: Building Bridges II: Mathematics of László Lovász, pp

    Borgs, C., Chayes, J.T., Cohn, H., Lovász, L.M.: Identifiability for graphexes and the weak kernel metric. In: Building Bridges II: Mathematics of László Lovász, pp. 29–157. Springer (2020)

    2020

  4. [12]

    The Journal of Machine Learning Research 15(1), 1455–1459 (2014)

    Boumal, N., Mishra, B., Absil, P.A., Sepulchre, R.: Manopt, a matlab toolbox for optimization on manifolds. The Journal of Machine Learning Research 15(1), 1455–1459 (2014)

    2014

  5. [13]

    Science advances 8(19), eabj3063 (2022)

    Bovet, A., Delvenne, J.C., Lambiotte, R.: Flow stability for dynamic community detection. Science advances 8(19), eabj3063 (2022)

    2022

  6. [14]

    Communications Physics 8(1), 159 (2025)

    Cencetti, G., Barrat, A.: Generating surrogate temporal networks from mesoscale building blocks. Communications Physics 8(1), 159 (2025)

    2025

  7. [15]

    Journal of Statistical Physics 181(5), 1746–1780 (2020)

    Chakrabarty, A., Chakraborty, S., Hazra, R.S.: Eigenvalues outside the bulk of inhomogeneous Erdős–Rényi random graphs. Journal of Statistical Physics 181(5), 1746–1780 (2020)

    2020

  8. [16]

    In: Conference on Learning Theory

    Chaudhuri, K., Chung, F., Tsiatas, A.: Spectral clustering of graphs with general degrees in the extended planted partition model. In: Conference on Learning Theory. pp. 35–1. JMLR Workshop and Conference Proceedings (2012)

    2012

  9. [17]

    American Mathematical Society (1997)

    Chung, F.R.: Spectral Graph Theory. American Mathematical Society (1997)

    1997

  10. [18]

    Applied and Computational Harmonic Analysis 10(1), 27–44 (2001)

    Coifman, R., Geshwind, F., Meyer, Y.: Noiselets. Applied and Computational Harmonic Analysis 10(1), 27–44 (2001)

    2001

  11. [19]

    Coifman, R., Lafon, S.: Diffusion maps. Appl. Comput. Harmon. Anal. 21(1), 5–30 (2006)

    2006

  12. [20]

    Nature communications 13(1), 7229 (2022)

    Contisciani, M., Battiston, F., De Bacco, C.: Inference of hyperedges and overlapping communities in hypergraphs. Nature communications 13(1), 7229 (2022)

    2022

  13. [21]

    Franco Saldaña, Y.Y., Feng, Y.: How many communities are there? Journal of Computational and Graphical Statistics 26(1), 171–181 (2017)

    D. Franco Saldaña, Y.Y., Feng, Y.: How many communities are there? Journal of Computational and Graphical Statistics 26(1), 171–181 (2017)

    2017

  14. [22]

    Information and Inference: A Journal of the IMA 8(1), 181–203 (2019)

    Damle, A., Minden, V., Ying, L.: Simple, direct and efficient multi-way spectral clustering. Information and Inference: A Journal of the IMA 8(1), 181–203 (2019)

    2019

  15. [23]

    Journal of Machine Learning Research 22(117), 1–44 (2021)

    Deng, S., Ling, S., Strohmer, T.: Strong consistency, graph laplacians, and the stochastic block model. Journal of Machine Learning Research 22(117), 1–44 (2021)

    2021

  16. [24]

    arXiv preprint arXiv:1909.11282 pp

    Devriendt, K., Lambiotte, R., Van Mieghem, P.: Constructing Laplacian matrices with Soules vectors: inverse eigenvalue problem and applications. arXiv preprint arXiv:1909.11282 pp. 1–26 (2019)

    2019 arXiv

  17. [25]

    Applied Network Science 10(1), 1 (2025)

    Djurdjevac Conrad, N., Tonello, E., Zonker, J., Siebert, H.: Detection of dynamic communities in temporal networks with sparse data. Applied Network Science 10(1), 1 (2025)

    2025

  18. [26]

    Journal of Combinatorial Theory, Series B 147, 252–298 (2021)

    Doležal, M., Grebík, J., Hladk `y, J., Rocha, I., Rozhoň, V.: Relating the cut distance and the weak∗ topology for graphons. Journal of Combinatorial Theory, Series B 147, 252–298 (2021)

    2021

  19. [27]

    The Annals of Applied Statistics 12(2), 971–1012 (2018)

    Donnat, C., Holmes, S.: Tracking network dynamics: A survey using graph distances. The Annals of Applied Statistics 12(2), 971–1012 (2018)

    2018

  20. [28]

    The Annals of Statistics 48(6), 3312–3335 (2020)

    Dubey, P., Müller, H.G.: Fréchet change-point detection. The Annals of Statistics 48(6), 3312–3335 (2020)

    2020

  21. [29]

    Linear Algebra and its Applications 271(1-3), 323–343 (1998)

    Elsner, L., Nabben, R., Neumann, M.: Orthogonal bases that lead to symmetric nonnegative matrices. Linear Algebra and its Applications 271(1-3), 323–343 (1998)

    1998

  22. [30]

    SIAM journal on matrix analysis and applications 31(3), 1227–1234 (2010) 25

    Eubanks, S., McDonald, J.J.: On a generalization of Soules bases. SIAM journal on matrix analysis and applications 31(3), 1227–1234 (2010) 25

    2010

  23. [31]

    Machine Learning 113(10), 7591–7615 (2024)

    Failla, A., Cazabet, R., Rossetti, G., Citraro, S.: Describing group evolution in temporal data using multi-faceted events. Machine Learning 113(10), 7591–7615 (2024)

    2024

  24. [32]

    Journal of the American Statistical Association 117(538), 996–1009 (2022)

    Fan, J., Fan, Y., Han, X., Lv, J.: Asymptotic theory of eigenvectors for random matrices with diverging spikes. Journal of the American Statistical Association 117(538), 996–1009 (2022)

    2022

  25. [33]

    In: Proc

    Fan, X., Yue, Y., Sarkar, P., Wang, Y.X.R.: On hyperparameter tuning in general clustering problems. In: Proc. of the 37th Int. Conf. on Machine Learning. vol. 119, pp. 2996–3007 (2020)

    2020

  26. [34]

    real-world

    Farkas, I.J.: Spectra of “real-world” graphs: Beyond the semicircle law. Physical Review E 64(2) (2001). https://doi.org/10.1103/PhysRevE.64.026704

    2001 doi

  27. [35]

    Scientific reports 8(1), 12997 (2018)

    Faskowitz, J., Yan, X., Zuo, X.N., Sporns, O.: Weighted stochastic block models of the human connectome across the life span. Scientific reports 8(1), 12997 (2018)

    2018

  28. [36]

    Information and Inference 12(3), 1347–1404 (03 2023)

    Ferguson, D., Meyer, F.G.: Theoretical analysis and computation of the sample Fréchet mean of sets of large graphs. Information and Inference 12(3), 1347–1404 (03 2023)

    2023

  29. [37]

    In: Pattern Recognition and Image Analysis

    Ferrer, M., Serratosa, F., Sanfeliu, A.: Synthesis of median spectral graph. In: Pattern Recognition and Image Analysis. pp. 139–146 (2005)

    2005

  30. [38]

    Internet Mathematics 2(1), 1–19 (2005)

    Flaxman, A., Frieze, A., Fenner, T.: High degree vertices and eigenvalues in the preferential attachment graph. Internet Mathematics 2(1), 1–19 (2005)

    2005

  31. [39]

    The Annals of Statistics 43(6), 2624–2652 (2015)

    Gao, C., Lu, Y., Zhou, H.H.: Rate-optimal graphon estimation. The Annals of Statistics 43(6), 2624–2652 (2015)

    2015

  32. [40]

    Journal of Scientific Computing 100(3), 89 (2024)

    Garner, C., Lerman, G., Zhang, S.: Spectrally constrained optimization. Journal of Scientific Computing 100(3), 89 (2024)

    2024

  33. [41]

    PloS one 9(1), e86028 (2014)

    Gauvin, L., Panisson, A., Cattuto, C.: Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach. PloS one 9(1), e86028 (2014)

    2014

  34. [42]

    BMC infectious diseases 14, 1–10 (2014)

    Gemmetto, V., Barrat, A., Cattuto, C.: Mitigation of infectious disease at school: targeted class closure vs school closure. BMC infectious diseases 14, 1–10 (2014)

    2014

  35. [43]

    Génois, M., Barrat, A.: Can co-location be used as a proxy for face-to-face contacts? EPJ Data Science 7(1), 1–18 (2018)

    2018

  36. [44]

    Science advances 4(7), eaaq1360 (2018)

    Gerlach, M., Peixoto, T.P., Altmann, E.G.: A network approach to topic models. Science advances 4(7), eaaq1360 (2018)

    2018

  37. [45]

    The Annals of Statistics 48(4), 2208–2229 (2020)

    Ghoshdastidar, D., Gutzeit, M., Carpentier, A., Von Luxburg, U.: Two-sample hypothesis testing for inhomogeneous random graphs. The Annals of Statistics 48(4), 2208–2229 (2020)

    2020

  38. [46]

    The Annals of Applied Statistics 11(2), 725–750 (2017)

    Ginestet, C.E., Li, J., Balachandran, P., Rosenberg, S., Kolaczyk, E.D.: Hypothesis testing for network data in functional neuroimaging. The Annals of Applied Statistics 11(2), 725–750 (2017)

    2017

  39. [47]

    In: International Conference on Artificial Intelligence and Statistics

    Haasler, I., Frossard, P.: Bures-Wassersteinmeans of graphs. In: International Conference on Artificial Intelligence and Statistics. pp. 1873–1881. PMLR (2024)

    2024

  40. [48]

    In: AAAI/Graphs and more Complex structures for Learning and Reasoning Workshop (2022)

    Haghani, N., Singh, M., Balan, R.: Graph regression and classification using permutation invariant representations. In: AAAI/Graphs and more Complex structures for Learning and Reasoning Workshop (2022)

    2022

  41. [49]

    In: International Conference on Machine Learning

    Han, X., Jiang, Z., Liu, N., Hu, X.: G-mixup: Graph data augmentation for graph classification. In: International Conference on Machine Learning. pp. 8230–8248. PMLR (2022) 26

    2022

  42. [50]

    The Annals of Statistics 48(1), 514–538 (2020)

    Kolaczyk, E.D., Lin, L., Rosenberg, S., Walters, J., Xu, J.: Averages of unlabeled networks: Geometric characteriza- tion and asymptotic behavior. The Annals of Statistics 48(1), 514–538 (2020)

    2020

  43. [51]

    In: Proceedings of the International Congress of Mathematicians

    Le, C.M., Levina, E., Vershynin, R.: Concentration of random graphs and application to community detection. In: Proceedings of the International Congress of Mathematicians. pp. 2925–2943. World Scientific (2018)

    2018

  44. [52]

    Journal of the ACM 61(6), 37 (2014)

    Lee, J., , Gharan, S., Trevisan, L.: Multiway spectral partitioning and higher-order Cheeger inequalities. Journal of the ACM 61(6), 37 (2014)

    2014

  45. [53]

    Lovász, L.: Large networks and graph limits, vol. 60. AMS Bookstore (2012)

    2012

  46. [54]

    arXiv preprint arXiv:2401.07896 pp

    Löwe, M., Terveer, S.: Hitting times for random walks on the stochastic block model. arXiv preprint arXiv:2401.07896 pp. 1–26 (2024)

    2024 arXiv

  47. [55]

    The Electronic Journal of Combinatorics pp

    Lu, L., Peng, X.: Spectra of edge-independent random graphs. The Electronic Journal of Combinatorics pp. P27–P27 (2013)

    2013

  48. [56]

    Journal of the American Statistical Association 116(536), 2023–2040 (2021)

    Lunagómez, S., Olhede, S.C., Wolfe, P.J.: Modeling network populations via graph distances. Journal of the American Statistical Association 116(536), 2023–2040 (2021)

    2021

  49. [57]

    Meyer, F.G.: https://github.com/francoismeyer/barycentre-network (2025)

    2025

  50. [58]

    Applied and Computational Harmonic Analysis 36(2), 326–334 (2014)

    Meyer, F.G., Shen, X.: Perturbation of the eigenvectors of the graph Laplacian: Application to image denoising. Applied and Computational Harmonic Analysis 36(2), 326–334 (2014)

    2014

  51. [59]

    Meyer, F.G.: When does the mean network capture the topology of a sample of networks? Frontiers in Physics 12, 1–11 (2024)

    2024

  52. [60]

    In: Conference on Learning Theory

    Mossel, E., Neeman, J., Sly, A.: Belief propagation, robust reconstruction and optimal recovery of block models. In: Conference on Learning Theory. pp. 356–370. PMLR (2014)

    2014

  53. [61]

    PNAS 111(41), 14722–14727 (2014)

    Olhede, S.C., Wolfe, P.J.: Network histograms and universality of blockmodel approximation. PNAS 111(41), 14722–14727 (2014)

    2014

  54. [62]

    arXiv preprint arXiv:0911.0600 (2009)

    Oliveira, R.I.: Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges. arXiv preprint arXiv:0911.0600 (2009)

    2009 arXiv

  55. [63]

    Massive graph analytics pp

    Penschuck, M., Brandes, U., Hamann, M., Lamm, S., Meyer, U., Safro, I., Sanders, P., Schulz, C.: Recent advances in scalable network generation 1. Massive graph analytics pp. 333–376 (2022)

    2022

  56. [64]

    The Annals of Statistics 47(2), 691–719 (2019)

    Petersen, A., Müller, H.G.: Fréchet regression for random objects with euclidean predictors. The Annals of Statistics 47(2), 691–719 (2019)

    2019

  57. [65]

    In: OPT2020 (2020)

    Redko, I., Sebban, M., Habrard, A.: Non-negative matrix factorization meets time-inhomogeneous markov chains. In: OPT2020 (2020)

    2020

  58. [66]

    The Annals of Statistics pp

    Rohe, K., Chatterjee, S., Yu, B.: Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics pp. 1878–1915 (2011)

    2011

  59. [67]

    Applied Network Science 8(1), 64 (2023)

    Sattar, N.S., Buluc, A., Ibrahim, K.Z., Arifuzzaman, S.: Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detection. Applied Network Science 8(1), 64 (2023)

    2023

  60. [68]

    Neuroimage 41(3), 886–902 (2008)

    Shen, X., Meyer, F.: Low-dimensional embedding of fMRI datasets. Neuroimage 41(3), 886–902 (2008)

    2008

  61. [69]

    Shine, A., Kempe, D.: Generative graph models based on Laplacian spectra? In: The World Wide Web Conference. pp. 1691–1701. ACM (2019) 27

    2019

  62. [70]

    W.: Constructing symmetric nonnegative matrices

    Soules, G. W.: Constructing symmetric nonnegative matrices. Linear and Multilinear Algebra13(3), 241–251 (1983)

    1983

  63. [71]

    PloS one 6(8), e23176 (2011)

    Stehlé, J., Voirin, N., Barrat, A., Cattuto, C., Isella, L., Pinton, J.F., Quaggiotto, M., Van den Broeck, W., Régis, C., Lina, B., Vanhems, P.: High-resolution measurements of face-to-face contact patterns in a primary school. PloS one 6(8), e23176 (2011)

    2011

  64. [72]

    Heat kernels and analysis on manifolds, graphs, and metric spaces 338, 357 (2003)

    Sturm, K.T.: Probability measures on metric spaces of nonpositive. Heat kernels and analysis on manifolds, graphs, and metric spaces 338, 357 (2003)

    2003

  65. [73]

    arXiv preprint arXiv:1803.11551 (2018)

    Tang, M.: The eigenvalues of stochastic blockmodel graphs. arXiv preprint arXiv:1803.11551 (2018)

    2018 arXiv

  66. [74]

    Nature Physics 20 (2), 294–302 (2024)

    Thibeault, V., Allard, A., Desrosiers, P.: The low-rank hypothesis of complex systems. Nature Physics 20 (2), 294–302 (2024)

    2024

  67. [75]

    Applied and Computational Harmonic Analysis 3(2), 91–99 (1996)

    Thiele, C.M., Villemoes, L.F.: A fast algorithm for adapted time–frequency tilings. Applied and Computational Harmonic Analysis 3(2), 91–99 (1996)

    1996

  68. [76]

    In: ICIAP 2007

    White, D., Wilson, R.C.: Spectral generative models for graphs. In: ICIAP 2007. pp. 35–42 (2007)

    2007

  69. [77]

    PLoS ONE 15(2), 1–54 (2020)

    Wills, P., Meyer, F.G.: Metrics for graph comparison: a practitioner’s guide. PLoS ONE 15(2), 1–54 (2020)

    2020

  70. [78]

    In: Proceedings of the AAAI Conference on Artificial Intelligence

    Xu, H., Luo, D., Carin, L., Zha, H.: Learning graphons via structured Gromov-Wasserstein barycenters. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 35 (12), pp. 10505–10513 (2021)

    2021

  71. [79]

    In: International Conference on Machine Learning

    Xu, J.: Rates of convergence of spectral methods for graphon estimation. In: International Conference on Machine Learning. pp. 5433–5442. PMLR (2018)

    2018

  72. [80]

    In: ICAIS

    Yan, B., Sarkar, P., Cheng, X.: Provable estimation of the number of blocks in block models. In: ICAIS. pp. 1185–1194 (2018)

    2018

  73. [81]

    Young, J.G., St-Onge, G., Desrosiers, P., Dubé, L.J.: Universality of the stochastic block model. Phys. Rev. E 98, 032309 (2018)

    2018

  74. [82]

    Yule, G.U.: A mathematical theory of evolution, based on the conclusion of dr. j. c. willis, f.r.s. Philisophical Transactions of the Royal Society B.213, 402–410 (1925)

    1925

  75. [83]

    IEEE Transactions on Signal Processing 67(24), 6327–6341 (2019)

    Zambon, D., Alippi, C., Livi, L.: Change-point methods on a sequence of graphs. IEEE Transactions on Signal Processing 67(24), 6327–6341 (2019)

    2019

  76. [84]

    Physical review E 89(4), 042816 (2014) 28

    Zhang, X., Nadakuditi, R.R., Newman, M.E.: Spectra of random graphs with community structure and arbitrary degrees. Physical review E 89(4), 042816 (2014) 28

    2014

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.