{'fraction_non_alphanumeric': 0.059228044177915676, 'fraction_numerical': 0.013359883303618977, 'mean_word_length': 3.8381315111459617, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 28, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 31, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Generalized quasirandom properties of expanding graph sequencesedding

We consider special multiclass spectral, discrepancy, degree, and codegree properties of expanding graph sequences. As we can prove equivalences and implications between them and the definition of the generalized quasirandomness of Lov\'asz--S\'os (2008), they can be regarded as generalized quasirandom properties akin to the equivalent quasirandom properties of the seminal Chung--Graham--Wilson paper (1989) in the one-class scenario. Since these properties are valid for certain deterministic graph sequences, irrespective of stochastic models, the partial implications also justify for law-dimensional embedding of large-scale graphs and for discrepancy minimizing spectral clustering.


Introduction
Our motivation comes from the multivariate statistical analysis. The basic idea of factor analysis (static or dynamic) is to make low-dimensional embedding of high-dimensional data. For this purpose, the so-called k-factor model is investigated, where k is the hidden rank of the covariance structure and it is much less than the number n of the variables. The so-called factor scores also give rise to partition the variables into k clusters. In the fundamental models, k is fixed, whereas n → ∞ together with the sample size N in the static or the time T in the dynamic case. If our data form a graph, then n is the number of its vertices, N is the number of its edges, and the usual condition that n and N tend to infinity in a prescribed way (N is superlinear in n) implies that our graph is dense enough. Given a real-life graph on n vertices, that is an instance of an expanding sequence, with the help of graph based matrices, our purpose is to make inference on the number k of the hidden clusters of vertices if there are any.
Graph based matrices together with eigenvalues and eigenvectors have been intensively studied since the 1970s. For example, Fiedler [24] used the eigenvector, corresponding to the smallest positive Laplacian eigenvalue of a connected graph (the famous Fiedler vector) to find a bipartition of the vertices which approximates the minimum cut problem. From the two-clustering point of view (k = 2), this eigenvector becomes important when the corresponding eigenvalue is not separated from the trivial zero eigenvalue, but it is separated from the second smallest positive Laplacian eigenvalue. On the contrary, when there is a large spectral gap between the trivial zero and the smallest positive Laplacian eigenvalue (or equivalently, between the trivial 1 and the second largest positive eigenvalue of the transition probability matrix in the random walk view), there is no use of partitioning the vertices, the whole graph forms a highly connected cluster. This k = 1 case has frequently been studied since Cheeger [18], establishing a lot of equivalent or near equivalent advantageous features of these graphs. There are many results about the relation between this gap and different kinds of expansion constants of the graph (see e.g., [26,30]), including random walk view of [5,22,33]. The vertex-subsets of such graphs have a large boundary compared to their volumes characterized by the isoperimetric number, see Mohar [34]. They also show quasirandom properties discussed in Thomason [40,41], Bollobás [14], and Chung, Graham, Wilson [19,20]. For these favorable characteristics, they are indispensable in communication networks.
However, less attention has been paid to graphs with a small spectral gap, when several cases can occur: among others, the graph can be a bipartite expander of Alon [2] or its vertices can be divided into two sparsely connected clusters, but the clusters themselves can be good expanders (see [29] and [36]). In case of several clusters of vertices the situation is even more complicated. The pairwise relations between the clusters and the within-cluster relations of the vertices of the same cluster show a great variety. Depending on the number and sign of the so-called structural eigenvalues of the normalized modularity matrix, to be defined in Section 2, we can make inferences on the number of the underlying clusters and the type of connection between them. Furthermore, based on spectral and singular value decompositions (in the sequel, SD and SVD), low dimensional embedding of the vertices is performed, and classical and modern techniques of the multivariate statistical analysis (analysis of variance and kmeans clustering) are used to find the clusters. The notion of the multiway discrepancy [13] also plays a crucial role in identifying the clusters, and it is related to the spectral properties of the graph.
In the worst case scenario, when there are no k structural eigenvalues with a moderate k, the Szemerédi regularity lemma guarantees the existence of a universal k (independent of n, it only depends on the discrepancy bound to be attained) such that the vertices of a dense graph can be classified into k (equitable, and a 'small' exceptional) parts such that the between-cluster discrepancies are less than the error bound. This theorem has overwhelming theoretical importance (in combinatorics and analytical number theory), whereas our purpose is to give equivalent conditions for the existence of a k-cluster structure with a moderate k. For this purpose, in Section 3 we consider k-class (generalized) random and quasirandom graphs, introduced in [31], and in Section 4 we establish equivalent properties (including discrepancies and spectra) of them.

Notation
Let G = (V, A) be an undirected, edge-weighted graph on the n-element vertexset V with the n×n symmetric weighted adjacency matrix A; the entries satisfy a ij = a ji ≥ 0, a ii = 0 and they are similarities between the vertex-pairs. If we have a simple graph G, then A is the usual 0-1 adjacency matrix.
The modularity matrix of G is defined as M = A − dd T (see [35]), where the entries of d are the generalized vertex-degrees d i = n j=1 a ij (i = 1, . . . , n), and A is normalized in such a way that n i=1 n j=1 a ij = 1; this assumption does not hurt the generality, since neither the forthcoming normalized modularity matrix nor the multiway discrepancies to be defined are affected by the scaling of the entries of A. The normalized modularity matrix of G (see [8]) is T has unit norm. We will assume that G is connected, i.e., A is irreducible, in which case, the generalized vertex-degrees are all positive. For the relation between the normalized modularity and Laplacian matrices, see [10].
Let 1 < k < n be a fixed integer. Usual spectral clustering techniques use the k bottom Laplacian or normalized Laplacian eigenvalues together with the corresponding eigenvectors to find k 'loosely' connected clusters of the vertices. More generally, in the modularity based spectral clustering, we look for the proper k-partition U 1 , . . . , U k of the vertices such that the within-and between cluster discrepancies are minimized. We refer to U i 's as clusters. To motivate the introduction of the exact discrepancy measure observe that the ij entry of M is a ij − d i d j , which is the difference between the actual connection of the vertices i, j and the connection that is expected under independent attachment of them with probabilities d i and d j , respectively. Consequently, the difference between the actual and the expected connectedness of the subsets X, Y ⊂ V is i∈X j∈Y where a(X, Y ) = i∈X j∈Y a ij is the weighted cut between X and Y , and Vol(X) = i∈X d i is the volume of the vertex-subset X. When A is the 0-1 adjacency matrix, a(X, Y ) = e(X, Y ) is the number of cut-edges between X and Y , counting the possible edges in X ∩ Y twice. Further, let ρ(X, Y ) := The minimum k-way discrepancy of G is where P k denotes the set of proper k-partitions of V .
Observe that md(X, Y ; U i , U j ) is unaffected under scaling the edge-weights: if a ij 's are multiplied with the same constant c, then md(X, Y ; U i , U j ) remains unchanged, unlike the densities ρ( n j=1 a ij .) Also note that md(G; U 1 , . . . , U k ) is the smallest α such that for every U i , U j pair and for every X holds. It resembles the notion of volume-regular cluster pairs of [4] or the ǫregular pairs in the Szemerédi regularity lemma [39], albeit with given number of vertex-clusters, which are usually not equitable; further, with volumes, instead of cardinalities.
The weighted k-variance of these representatives is defined as where c i = 1 Vol(Ui) v∈Ui d v r v is the weighted center of the cluster U i . It is the weighted k-means algorithm that provides this minimum. We will also need the plain k-variance of the representatives r 1 , . . . , r n ∈ R k that are row-vectors of the matrix, the columns of which are the unit-norm, pairwise orthogonal eigenvectors corresponding to the k largest (in absolute value) eigenvalues of A. This k-variance is where c i = 1 |Ui| v∈Ui r v is the center of the cluster U i . It is the usual k-means algorithm that finds this minimum. By an easy analysis of variance argument it follows that the optimum S k is just the minimum distance between the subspace spanned by the eigenvectors corresponding to the k largest (in absolute value) eigenvalues of A and the one of the step-vectors over the k-partitions of V . Similar holds forS k with the transformed eigenvectors.
Note that finding a global minimizer for the k-means problem is NP-hard. However, there are efficient polynomial time algorithms for finding an approximate solution whose value is within a constant fraction of the optimal value, under certain conditions, see, e.g., [27,37]. In Theorem 4.6 of [37], the authors prove that if the data satisfy the k-clusterable criterion (S 2 k ≤ ǫ 2 S 2 k−1 with a small enough ǫ), then there is a PTAS (polynomial time approximation scheme) for the k-means problem. Our conditions for the k-variances in Theorems 1 and 2 do comply with this requirement.
The spectral relaxation means that we can approximately find discrepancy minimizing clustering via applying the unweighted or weighted k-means algorithm to the k-or (k − 1)-dimensional vertex representatives. This is supported by former theorems cited in Section 4. Based on existing results between discrepancies and spectra, and the equivalences between quasirandom properties in the k = 1 case, our purpose is to establish similar properties of graph sequences in the multiclass scenario, when k is fixed and n → ∞ under some balancing conditions for the cluster sizes. We will intensively use the results of the Chung-Graham-Wilson [19] and the Lovász-Sós [31] papers.

Generalized random and quasirandom graphs
We start with the following definition (see [1,31,38]) of a generalized random graph sequence.

Definition 2
We are given a model graph H on k vertices with vertex-weights r 1 , . . . , r k (r i > 0, k i=1 r i = 1) and edge-weights p ij = p ji , 1 ≤ i ≤ j ≤ k (entries of the k×k symmetric probability matrix P of rank k, where 0 ≤ p ij ≤ 1, 1 ≤ i ≤ j ≤ k, and the diagonal entries correspond to loops at every vertex). G n is the general term of a generalized random graph sequence on the model graph H if • it has n vertices; • to each vertex v a cluster membership c v ∈ {1, . . . , k} is assigned according to the probability distribution r 1 , . . . , r k ; • given the memberships, each pair v = u is connected with probability p cvcu ; • further, all these decisions are made independently.
Let (U 1 , . . . , U k ) be the so obtained clustering of the vertices (they also depend on n, however we will not denote this dependence, unless necessary). The definition implies the following strong balancing condition on the growth of the cluster sizes n i = |U i |, i = 1, . . . , k ( k i=1 n i = n): if n → ∞, then ni n → r i (i = 1, . . . , k). The following theorem is the consequence of already known facts and large deviations.
Theorem 1 Let (G n ) be a generalized random graph sequence on the model graph H; G n has n vertices with vertex-classes U 1 , . . . , U k of sizes n 1 , . . . n k . Let H, and so k be kept fixed, i.e., the k × k probability matrix P of rank k and the 'blow-up' ratios r 1 , . . . , r k are fixed, while n → ∞ under the strong balancing condition. Then the following properties hold almost surely for the homorphism densities of simple graphs in G n , for the adjacency matrix A n = (a (n) ij ), the normalized modularity matrix M D,n , the multiway discrepancies, and the within-and between-cluster codegrees of G n . 0. G n → W H , where W H is the step-function graphon corresponding to H, and the convergence is meant in the sense of the convergence of homomorphism densities of any simple graph F into G n .

1.
A n has exactly k so-called structural eigenvalues that are Θ(n), while the remaining eigenvalues are O( √ n) (in absolute value). Further, the kvariance S 2 k,n (see (3)) of the k-dimensional vertex representatives, based on the eigenvectors corresponding to the structural eigenvalues of A n , is There exists a positive constant 0 < δ < 1 independent of n (it only depends on k) such that M D,n has exactly k − 1 structural eigenvalues of absolute value greater than δ, while all the other eigenvalues are O(n −τ ) for every 0 < τ < 1 2 . Further, the weighted k-varianceS 2 k,n (see (2)) of the (k−1)-dimensional vertex representatives, based on the transformed eigenvectors corresponding to the structural eigenvalues of where N 1 (u; U j ) denotes the number of neighbors of u in U j .
where N 2 (u, v; U j ) denotes the number of common neighbors of u, v in U j .
Note that these properties are far not equivalent. Property 0 was proved in [9], while Property 1 in [6], and Property 2 in [7] in a more general framework of the SVD of rectangular arrays of nonnegative entries, they are summarized in [10]. The basic idea of the proofs is that the adjacency matrix A n of a generalized random graph can be decomposed as a deterministic block-matrix B n (blown-up of P with sizes n 1 , . . . , n k ) plus a so-called Wigner-noise W n , see [6]. The Wigner-noise has spectral norm O( √ n) almost surely, while the blown-up matrix has as many non-zero eigenvalues of order n as the rank of P (in our case, k) with eigenvectors that are stepwise constant over U 1 , . . . , U k . The proof of Property 0 relies on the easy fact that the cut-norm of the stepfunction graphon assigned to W n tends to 0 as n → ∞. For the notion of the convergence of a graph sequence to a graphon, see [16] and Chapter 4 of [10]. Note that to prove Properties 1 and 2, even the following weak balancing condition suffices: n → ∞ in such a way that ni n ≥ c (i = 1, . . . , k) with some constant 0 < c ≤ 1 k . Property 3 is the consequence of Property 2, by the the back and forth statements between discrepancy and normalized modularity spectra, see the forthcoming Lemma 5 and Proposition 1 of Section 4. Property 4 is proved by large deviations. Indeed, by the Bernstein inequality, the within-and between-cluster average degrees and codegrees are highly concentrated on their expectations as n → ∞ under even the weak balancing condition on the cluster sizes. The meaning of Property 4 is the following. The induced subgraph of G n , induced by U i and denoted by G ii,n , is the general term of an Erdős-Rényi type random graph sequence with edge probability p ii , for every i = 1, . . . , k. The induced bipartite subgraph of G n , induced by the U i , U j pair and denoted by G ij,n , is the general term of a bipartite random graph sequence with edge probability p ij , for every i, j = 1, . . . , k and i = j pair. Therefore, the subgraphs are almost surely regular, while the bipartite subgraphs are almost surely biregular. Consequently, the vertex-degrees are of order Θ(n), almost surely. Further, the codegrees are as expected: every two vertices in U i have approximately the same number of common neighbors in any U j (i = j can be).
Note that the above generalized random graph in another context is discussed as the stochastic block model or planted partition model, see, e.g., [21,25,32], though these papers work with a fixed n and do not consider any condition for the growth of the cluster sizes. Indeed, Definition 2 provides us with a random graph model without the hidden (planted) clusters revealed. For this purpose, there are algorithms available, e.g., in [21,32]; however, one wonders whether a large and dense enough real-life graph can be 'close' to a one coming from this model. In the sequel, we will define precisely some properties that are weaker than those of Definition 2, but can characterize a class of graphs, given k. These will be called generalized quasirandom properties. Note that some other papers, e.g., [1,15] scale the probability matrix with n, and prove the consistency of the clusters under these conditions.
Based on the Lovász-Sós [31] paper, the following definition of a generalized quasirandom graph sequence is formulated.
Definition 3 Given a model graph H on k vertices with vertex-weights r 1 , . . . , r k and edge-weights Property 0 of Theorem 1 ensures that a generalized random graph sequence is also generalized quasirandom on the same model graph H. However, a generalized quasirandom graph sequence (G n ) is deterministic, such that for every fixed finite graph F , the number of copies of F in G n is asymptotically the same as the number of copies of F in a generalized random graph on n vertices and the same model graph H. Note that a generalized quasirandom graph sequence typically converges much slowly than a generalized random one.
Let us recall the definition of graph convergence, e.g., by [16]. We say that G n → W H if for any simple graph F , If |V (F )| = s, then we also have an integral formula for the homomorphism density of the simple graph F in the graphon W H , which is the same as its homomorphism density in H: Note that the G n → W H convergence is also equivalent to the following: the cut-distance between the graphons W Gn and W H tends to 0 as n → ∞.

Generalized quasirandom properties
Properties, reminiscent of those of the generalized random graphs, see Theorem 1, are now formulated for expanding deterministic graph sequences, and we show that there are many equivalences and implications between them, irrespective of stochastic models. First we recall the main results of the Chung-Graham-Wilson [19] paper about quasirandom properties that apply to the k = 1, p = 1 2 case; the authors also anticipate that instead of 1 2 , any fixed 0 < p < 1 can be considered. Hereby, we enlist only those properties that will be used later for our purposes, and together with the original formulation (with p = 1 2 ) we give the analogous form with a general p, while we use the notation of the original paper.
Let (G n ) be a sequence of graphs as n → ∞. The vertex-set of the general term G n is V n , and |V n | = n; whereas, the number of edges of G n is e(G n ). Consider the following properties.
) denotes the number of labelled induced subgraphs of G n , isomorphic to M (s). With a general p it reads: where e(M (s)) is the number of edges in M (s).
where C t is the cycle with t edges and N Gn (C t ) is the number of its occurrences as a (not necessarily induced) subgraph of G n , i.e., the number of the C t → G n homomorphisms. (Note that a relation between N and N * is given in [19].) With a general p it reads: where λ 1 and λ 2 are the largest and the second largest (in absolute value) eigenvalues of the adjacency matrix of G n . (Because of the Frobenius theorem, λ 1 is always positive.) With a general p it reads: • P 4 : ∀S ⊆ V n , e(S) = 1 4 |S| 2 + o(n 2 ). With a general p: ∀X ⊆ V n , e(X, X) = p|X| 2 + o(n 2 ).
Note that e(X, X) = 2e(X), where the authors of [19] use the notation e(X) for the number of edges in the subgraph (of G n ) induced by X, and e(X, X) was already defined in Section 2.
. With a general p: where N 2 (u, v) is the number of common neighbors of u, v in G n . (With our former notation, it is N 2 (u, v; V ).) The main theorem of [19] states that for s ≥ 4 and t ≥ 4 even, The authors of [19] called a graph quasirandom if it satisfies any, and therefore all, of the above properties. In the k-class scenario we have two statements of similar vein: Theorem 2 states mainly implications, whereas Theorem 3 states equivalences.
Theorem 2 Let G n be the general term of a sequence of simple graphs with vertex-set V n , adjacency matrix A n = (a (n) ij ), and normalized modularity matrix M D,n . Let k be a fixed positive integer, whereas |V n | = n → ∞. Consider the following properties: P0. There exists a vertex-and edge-weighted graph H on k vertices with vertexweights r 1 , . . . , r k and edge-weights where the k × k symmetric probability matrix P = (p ij ) has rank k, such that G n → W H as n → ∞.
The k-variance S 2 k,n of the k-dimensional vertex representatives, based on the eigenvectors corresponding to the structural eigenvalues of A n , is o(1). The k-partition (U 1 , . . . , U k ) minimizing this k-variance satisfies the strong balancing condition.
PII. G n has no dominant vertices: there are constants 0 < c < C < 1 such that the vertex-degrees are between cn and Cn, except of possibly o(n) vertices; further, there exists a constant 0 < δ < 1 (independent of n) such that M D,n has k − 1 structural eigenvalues that are greater than δ (in absolute value), while the remaining eigenvalues are o(1).
The weighted k-varianceS 2 k,n of the (k − 1)-dimensional vertex representatives, based on the transformed eigenvectors corresponding to the structural eigenvalues of M D,n , is o(1). The k-partition (U 1 , . . . , U k ) minimizing this k-variance satisfies the strong balancing condition.
PIV. There are vertex-classes U 1 , . . . , U k of sizes n 1 , . . . , n k obeying the strong balancing condition, and there is a k × k symmetric probability matrix P = (p ij ) of rank k such that, with them, the following holds: Then P0 is equivalent to PIV, and they imply PI and PII; further, PII implies PIII. We also consider the following strengthening of property PI: PI+. A n has k structural eigenvalues λ 1,n , . . . , λ k,n such that the normalized eigenvalues converge: 1 n λ i,n → q i as n → ∞ (i = 1, . . . , k) with some non-zero reals q 1 , . . . , q k , and the remaining eigenvalues are o( √ n).
The k-variance S 2 k,n of the k-dimensional vertex representatives, based on the eigenvectors corresponding to the structural eigenvalues of A n , is o( 1 n ). The k-partition P k,n = (U 1n , . . . , U kn ) of the vertices of G n minimizing this k-variance not only satisfies the strong balancing condition, but we also assume that there is a k × k symmetric probability matrix P = (p ij ) of rank k such that (I.e., the within-and between-cluster edge densities converge to the entries of P.) Then PI+ implies P0.
Note that properties P0-PIV are in many ways weaker than those of the generalized random graphs. For example, the generalized quasirandom graphs may converge much more slowly than the generalized random ones that can be decomposed as a deterministic block-matrix plus a Wigner-noise. The Wignernoise has spectral norm O( √ n), therefore converges very quickly. In case of a generalized quasirandom graph, the noise has spectral norm o(n) only. Also, in the generalized random case, the codegree condition holds for any pair of the vertices (of the same cluster toward those of a given own or other cluster), whereas in the general quasirandom case, it only holds on average, see (6). However, PI+ is even stronger than Property 1 of Theorem 1: it requires o( √ n) magnitude of the non-structural eigenvalues, whereas those of a generalized random graph are of order O( √ n). However, except of o(n) ones, the latter are also of order o( √ n), in view of concentration results on the eigenvalues, see, e.g., [3]. In summary, the above P0 is stronger than PI, but weaker than PI+. In the k = 1 case, property P 3 of the Chung-Graham-Wilson [19] paper is equivalent to P 1 (s) for every s (our P0). But there, above the separation in the spectrum, a lower bound for the edge-density should be satisfied. In the k > 1 scenario, the inter-and intra-cluster edge-densities can be bounded only at the expense of each other, so we have to require the convergence of these edge-densities too.
Proof of P0 => PIV: we use the results of [19,31]. By [31], the vertex set of the generalized quasirandom graph G n (defined by P0) can be partitioned into classes U 1 , . . . , U k in such a way that |Ui| n → r i (i = 1, . . . , k), that gives the strong balancing; the subgraph G ii,n is the general term of a quasirandom graph sequence with edge-density tending to p ii (i = 1, . . . , k), whereas G ij,n is the general term of a bipartite quasirandom graph sequence with edge-density tending to p ij (i = j) as n → ∞. Therefore, for the subgraphs the equivalent statements of [19] of the usual (one-class) quasirandomness are applicable, and similar considerations can be made for the bipartite subgraphs as well, see [14,28,41]. We also need two simple lemmas.
Proof of Lemma 1: We drop the index n of the adjacency entries. u,v∈Ui where e(U i ) is the number of edges within the subgraph G ii,n of G n , induced by U i . In the first inequality we used the Cauchy-Schwarz, and in the second one, the first part of the equivalent quasirandom property P 2 of [19], see (4).
Proof of Lemma 2: We drop the index n of the adjacency entries.
where recall that e(U i , U j ) is the number of cut-edges between U i and U j , i.e., the number of edges in the bipartite subgraph G ij,n of G n , induced by the U i , U j pair. Here, in the first inequality we used the Cauchy-Schwarz, and in the second one, the equivalent quasirandom property of bipartite quasirandom graphs.
In view of the lemmas, we estimate the square of the left-hand side of (6) by the Cauchy-Schwarz inequality for every i, j = 1, . . . k, with n 2 i terms: where to estimate u,v∈Ui N 2 (u, v; U j ) we used Lemma 1 in the i = j, and Lemma 2 in the i = j case; further, utilized that u,v∈Ui [N 2 (u, v; U j )] 2 is asymptotically hom(C 4 , G ij,n ), the number of the C 4 → G ij,n homomorphisms, where C 4 is the 4-cycle graph. Indeed, in the i = j case, the equivalent property P 2 (4) of [19] guarantees that hom(C 4 , G ii,n ) ≤ (1 + o(1))p 4 ii n 4 i , the latter is what is expected in an Erdős-Rényi type random graph with edge-density p ii . In the i = j case a similar property (see [31]) for bipartite quasirandom graphs implies that the C 4 → G ij,n homomorphism density is Here hom(C 4 , G ij,n ) = u,v∈Ui [N 2 (u, v; U j )] 2 asymptotically, as by [31] only 4-cycles in the above bipartition have to be considered; these 4-cycles have two vertices from U i and two from U j , and any two of the common neighbors of u, v ∈ U i in U j are possible candidates to close a (labelled) 4-cycle with them.
Proof of PIV => P0: If the average codegree condition (6) holds for the subgraphs (i = j), then by the P 7 → P 1 (s) (s = 1, 2, . . . ) implication of the equivalent quasirandom properties of [19], the subgraphs G ii,n are quasirandom (in terms of the isomorphisms, and so of the homomorphism densities). Likewise, in the i = j case, the bipartite subgraphs G ij,n are bipartite quasirandom. Therefore, G n is built of quasirandom and bipartite quasirandom blocks, so under the strong balancing condition, they together form a generalized quasirandom graph sequence on k classes and model graph H, the vertex-weights of which are r 1 , . . . , r k of the strong balancing condition, and the edge-weights are entries of the probability matrix P in the condition (6).
Proof of P0 => PII: We will use the following results proved in former papers.
Lemma 3 (Theorem 8 of [11]) Let G n = (V n , W n ) be the general term of a convergent sequence of connected edge-weighted graphs whose edge-weights are in [0,1] and the vertex-weights are the generalized degrees. Assume that there are no dominant vertices. Let W denote the limit graphon of the sequence (G n ), and let |µ n,1 | ≥ |µ n,2 | ≥ · · · ≥ |µ n,n | = 0 be the normalized modularity spectrum of G n (the eigenvalues are indexed by their decreasing absolute values). Further, let µ i (P W ) be the i-th largest (in absolute value) eigenvalue of the integral operator P W : L 2 (ξ ′ ) → L 2 (ξ) taking conditional expectation with respect to the joint measure W embodied by the normalized limit graphon W , and ξ, ξ ′ are identically distributed random variables with the marginal distribution of their symmetric joint distribution W, whereas L 2 (ξ) denotes the Hilbert space of the measurable functions of ξ with 0 expectation and finite variance. Then for every i ≥ 1, Lemma 4 (Theorem 9 of [11]) Assume that there are constants 0 < ε < δ ≤ 1 such that the normalized modularity spectrum of any G n satisfies |µ n,1 | ≥ · · · ≥ |µ n,k−1 | ≥ δ > ε ≥ |µ n,k | ≥ · · · ≥ |µ n,n | = 0.
With the notation of Lemma 3, and assuming that there are no dominant vertices of G n , the subspace spanned by the vectors D −1/2 n u n,1 , . . . ,D −1/2 n u n,k−1 , where u n,1 , . . . , u n,k−1 are orthonormal eigenvectors belonging to the k−1 largest absolute value eigenvalues of the normalized modularity matrix of G n , also converges to the corresponding (k−1)-dimensional subspace of P W . More exactly, if P n,k−1 denotes the projection onto the subspace spanned by the vectors D −1/2 n u n,1 , . . . ,D −1/2 n u n,k−1 , and P k−1 denotes the projection onto the analogous eigensubspace of P W , then P n,k−1 − P k−1 → 0 as n → ∞ (in spectral norm).
So the proof of P0 => PII is as follows. Since by P0, (G n ) converges to the limit graphon W H , and the eigenvalues µ i (P WH ) of Lemma 3 consist of k − 1 non-zero numbers, and the others are zeros, the statement for the convergence of the modularity spectrum follows. As for the weighted k-variances, we use Lemma 4, which implies that the subspace spanned by the transformed eigenvectors corresponding to the structural eigenvalues of M D,n converges to the subspace of step-vectors; further, the steps are proportional to r i 's, so the strong balancing also follows. As the weighted k-variance depends continuously on the above subspaces, Lemma 4 implies the convergence of the weighted k-variance as well. Note that here P n,k−1 − P k−1 F ≤ √ k − 1 P n,k−1 − P k−1 → 0 as n → ∞, where · F denotes the Frobenius norm.
Proof of P0 => PI: We use Theorem 6.7 of [17], where the authors prove that if the sequence (W Gn ) of graphons converges to the limit graphon W , then both ends of the spectra of the integral operators, induced by W Gn 's as kernels, converge to the ends of the spectrum of the integral operator induced by W as kernel. We apply this argument to the step-function graphon corresponding to G n (the eigenvalues of the induced integral operator are the normalized eigenvalues of G n ) and for the limit graphon W H of (G n ). The same argument as in P0 => PII can be applied for the convergence of the spectral subspaces, so by the above considerations, the convergence of the k-variances is also obtained. Since the steps of the emerging step-vectors are proportional to r i 's, the strong balancing condition also follows.
Proof of PII => PIII: We will use the following estimates between the multiway discrepancy and spectra.
Lemma 5 (Theorem 7 of [13]) Let G = (V, A) be an edge-weighted, undirected graph, A is irreducible. Then for any integer 1 ≤ k < rank(A), holds, provided 0 < md k (G) < 1, where µ k is the k-th largest eigenvalue (in absolute value) of the normalized modularity matrix M D of G.
The above lemma is a certain converse of the multi-class expander mixing lemma. In the forward direction, in the k = 1 case, the following result is considered as the extension of the expander mixing lemma to irregular graphs.
Lemma 6 (Lemma 1 of [20]) where M D is the spectral norm of the normalized modularity matrix of G.
Note that md 1 (G) is called disc(G) in [20]. When k ≥ 1, we are able to prove a stronger version of a theorem stated in [11].
Proposition 1 (strengthening the result of Theorem 3 of [11]) Let G n be the general term of a connected simple graph sequence, G n has n vertices.
The partition (U 1 , . . . , U k ) of V is defined so that it minimizes the weighted kvariance s 2 =S 2 k of the optimal (k − 1)-dimensional vertex representatives of G n . Assume that (U 1 , . . . , U k ) satisfies the strong balancing condition. Then The statement of Proposition 1 implies that md k (G) ≤ md(G; U 1 , . . . , U k ) = O( √ 2kS k + |µ k |). For the k = 1 case, ε = |µ 1 |,S 1 = 0 (based on the coordinates of the D −1/2 u 1 = D −1/2 √ d = 1 vector), and so, we get back Lemma 6 up to a constant factor. In the k = 2 bipartite, biregular case we get the statement of [23], see [13] for further explanation. Consequently, a 'small' |µ k | andS k is an indication of k clusters with 'small' within-and between-cluster discrepancies. Note that, by subspace perturbation theorems, a 'large' gap between |µ k | and |µ k−1 | is an indication, but not necessarily a cause of a 'small'S k .
Observe that the degree-condition of Proposition 1 means that our graph is dense (even the condition with 0 < c < 1 and C = 1 would suffice). Since there are o(n) exceptional vertices, the average degree is Θ(n). Note that the original version of Proposition 1 (see [11]) was formulated for the edge-weighted case, with edge-weights summing to 1, and we required that the so normalized degrees satisfy c ′ 1 n ≤ d v ≤ C ′ 1 n , v = 1, . . . , n with some constants 0 < c ′ < 1 < C ′ . With this normalization our assumption that there are no dominant vertices means that all the vertex-degrees are of order Θ( 1 n ), however the underlying graph can as well be sparse. Further, in [11] a weaker notion of volume-regularity was used.
So the proof of PII => PIII is as follows. Assume that there is a constant 0 < δ < 1 such that M D,n has k − 1 eigenvalues that are greater than δ in absolute value, while the remaining eigenvalues are o(1); further, the squareroot of weighted k-varianceS 2 k,n is also o(1). Using that there are no dominant vertices, we apply Proposition 1. According to this, md(G n ; U 1 , . . . , U k ) = o(1). Indirectly, assume that there is no absolute constant 0 < θ < 1 such that md 1 (G n ) > θ, . . . , md k−1 (G n ) > θ. Then there is an 1 ≤ i ≤ k − 1 with md i (G n ) ≤ ε for any 0 < ε < 1. But Lemma 5 estimates |µ n,i | with a (near zero) strictly increasing function of md i (G n ). In view of this, there should be an 0 < ε ′ < 1 so that |µ n,i | ≤ ε ′ , where ε ′ can be any small positive number (depending on ε). This contradicts to the |µ n,i | > δ assumption.
Proof of PI+ => P0: Under the assumptions of PI+, by Theorem 3.1.17 of [10] we are able to find a blown-up matrix B n of rank k and an error-matrix E n with E n = o( √ n) such that A n = B n + E n (n = k, k + 1, . . . ). Say, B n is the blown-up matrix of the k × k pattern matrix P n , the ij entry p (n) ij of which is the common entry of the U in × U jn block of B n .
Then using the relation between the cut-norm of a graphon and a matrix, further, between the cut-norm and the spectral norm of a matrix, and the transformation of a graph into graphon, we get that where E n is the spectral-norm, E n is the matrix cut-norm of E n , and W En denotes the graphon corresponding to the symmetric matrix E n of uniformly bounded entries. (The sides of the unit square are divided into n equidistant intervals, and the step-function over the small squares of the unit square takes on values corresponding to the matrix entries.) Though, these entries can be negative, the theory of bounded graphons applies to W En , too.
Using the Steiner equality, we get that the squared Frobenius norm of A n − B n , restricted to the ij block, is where the edge-density d(U in , U jn ) of (7) is now viewed as the average of the entries of A n in the U in × U jn block. Then by the inequality between the Frobenius and spectral norms, Therefore, for every 1 ≤ i ≤ j ≤ k pair: as |Uin| n → r i when n → ∞ (i = 1, . . . , k). Consequently, p ij 's are nonnegative, provided there are no constantly zero blocks in A n .
Eventually, we prove the G n → W H convergence by verifying that the cutdistance between the corresponding graphons tends to 0. Using the triangle inequality, we get were G n /P k,n is the factor graph of G n with respect to the k-partition P k,n = (U 1n , . . . , U kn ). This is an edge-and vertex-weighted graph on k vertices, with vertex-weights |Uin| n and edge-weights d(U in , U jn ), i, j = 1, . . . , k. The first term is W En = o(n −1/2 ). To estimate the second term, we use that B n is the blown-up matrix of P n with respect to the k-partition P k,n , after conveniently permuting its rows (and columns, accordingly). The graphon W Bn is also stepwise constant over the unit square, where the sides are divided into k parts: the interval I j has lengths |Ujn| n (j = 1, . . . , k), and over I i × I j the stepfunction takes on the value p (n) ij . By its nature, the graphon W Gn/P k,n is stepwise constant with the same subdivision of the unit square, and over I i × I j it takes on the value d(U in , U jn ), i, j = 1, . . . , k. But in view of (9), W Bn − W Gn/P k,n = √ no(n −1/2 ) = o(1). The third term is o(1), because of the assumptions |Uin| n → r i (i = 1, . . . , k) and d(U in , U jn ) → p ij , i, j = 1, . . . , k. Therefore, W Gn − W H = o(1) and so, G n → H, which finishes the proof. Summarizing: we proved that PIV <=> P0 => PI , and PI+ => P0. So PI is weaker and PI+ is stronger than P0. We should find something between PI and PI+ which is equivalent to P0, what is an open question yet. Further, P0 => PII => PIII. We are also able to prove equivalences by strengthening PII and PIII.
Theorem 3 Let us define PII+ and PIII+ as PII and PIII of Theorem 2 together with the following additional assumptions, respectively. The k-partition (U 1 , . . . , U k ) emerging in PII and PIII of Theorem 2 not only satisfies the strong balancing condition, but there is a k × k symmetric probability matrix P = (p ij ) of rank k such that (the same as (7)), and for every 1 ≤ i ≤ j ≤ k and u ∈ U i , holds. Then P0 => PII+ => PIII+ => PIV => P0, so they are all equivalent.
For the proof we need the following lemma.
Lemma 7 Under P0, the following holds for except o(n i ) vertices u ∈ U i , and for every 1 ≤ i ≤ j ≤ k: The statement of the lemma follows from the P 1 (s) (∀s) => P ′ 0 implication of the Chung-Graham-Wilson [19] paper (if i = j) and its bipartite analogue (if i = j). In the multiclass scenario, Lemma 7 implies that there are no dominant vertices, i.e., the vertex degrees are of order Θ(n), except for at most o(n) vertices. Also, except at most o(n) vertices, the clusters are asymptotically regular, and the cluster pairs are asymptotically biregular. Note that this property, even in the k = 1 case, is weaker than the equivalent properties of quasirandomness, in particular, than that for the codegrees.
Proof of P0 => PII+ => PIII+: These implications hold in view of the proof of Theorem 2, as the extra conditions follow from P0, automatically. Indeed, P0 implies the convergence of the edge-densities (see [31], the end of the proof of Theorem 2.2) and that of the within-and between-cluster vertexdegrees (see Lemma 7).
Proof of PIII+ => PIV: We will prove that P 4 , and the analogous statement of [41] holds, whenever PIII+ holds. Here we cite the notion of (p − β)-jumbled and bi-jumbled graphs based on [14,28,40,41] with 0 < p ≤ 1 < β and e(X) denotes the number of edges of the underlying graph with both endpoints in X. In the random graph G n (p), which is best possible (see [14]), and for a quasirandom G n , β = o(n), in view of P 4 of [19]. Likewise, a bipartite graph is It makes sense for bipartite graphs with the partition of vertices (U 1 , U 2 ), where X ⊂ U 1 and Y ⊂ U 2 . For bipartite quasirandom graphs, β = o(n) again, see [41]. Under the degree-conditions, Vol(X) is approximately n times |X|, so the right hand side constant, analogous to β, will be o(1) in our case, when we use volumes instead of cardinalities.

Conclusions
In course of proving equivalences between generalized quasirandom properties, we have characterized spectra and spectral subspaces of generalized quasirandom graphs; further, used a version of the expander mixing lemma to the kcluster case and its certain converse. These theorems can give a hint for practitioners about the choice of the number of clusters. The original expander mixing lemma and its converse (for simple, regular graphs) treat the k = 1 case only, whereas the Szemerédi regularity lemma applies to the worst case scenario: even if there is not an underlying cluster structure, we can find cluster pairs with small discrepancy with an enormously large k (which does not depend on the number of vertices, it only depends on the discrepancy to be attained). Here we rather treat the intermediate case, and show that a moderate k suffices if our graph has k structural eigenvalues and a hidden k-cluster structure that can be revealed by spectral clustering tools. Under good clustering we generally understand clusters with small within-and between-cluster discrepancies.
In [12], through rectangular matrices of nonnegative entries, we also considered the following particular cases, as for the structural eigenvalues of the normalized modularity matrix.
• When the k − 1 largest absolute value eigenvalues of the normalized modularity matrix M D are all positive, then the discrepancy minimizition also solves the minimum normalized cut problem. In this special situation, the optimal k-clustering favors so-called community structure: k-partitions with 'low' inter-cluster and 'high' intra-cluster edge-densities, see [35].
• When the k − 1 largest absolute value eigenvalues of M D are all negative, then the discrepancy minimizing k-clustering rather favors so-called anticommunity structure: k-partitions of the vertices with 'low' intra-cluster and 'high' inter-cluster edge-densities, see [35].
In most of the real-life problems, we want just to find regular partitions that minimize discrepancies both within and between clusters, such that vertices of the same cluster behave similarly towards vertices of the same (own or other) cluster. This new paradigm for structural decomposition relies on minimizing the within-and between-cluster discrepancies by means of the normalized modularity matrix. Depending on the number and sign of the so-called structural eigenvalues of this matrix, inferences can be made on the number of the underlying clusters and the type of connection between them. Furthermore, based on SD or SVD, the structure of the actual data set can be explored. The problem can as well be generalized to rectangular arrays, e.g., for biclustering genes and conditions of microarrays at the same time, when we want to find clusters of similarly functioning genes that equally (not especially weakly or strongly) influence conditions of the same cluster.