Clustering graphs under the Stochastic Block Model (SBM) and extensions are well studied. Guarantees of correctness exist under the assumption that the data is sampled from a model. In this paper, we propose a framework, in which we obtain "correctness" guarantees without assuming the data comes from a model. The guarantees we obtain depend instead on the statistics of the data that can be checked. We also show that this framework ties in with the existing model-based framework, and that we can exploit results in model-based recovery, as well as strengthen the results existing in that area of research.

From neuroscience and genomics to systems biology and ecology, researchers rely on clustering similarity data to uncover modular structure. Yet widely used clustering methods, such as hierarchical clustering, k-means, and WGCNA, lack principled model selection, leaving them susceptible to noise. A common workaround sparsifies a correlation matrix representation to remove noise before clustering, but this extra step introduces arbitrary thresholds that can distort the structure and lead to unreliable results. To detect reliable clusters, we capitalize on recent advances in network science to unite sparsification and clustering with principled model selection. We test two Bayesian community detection methods, the Degree-Corrected Stochastic Block Model and the Regularized Map Equation, both grounded in the Minimum Description Length principle for model selection. In synthetic data, they outperform traditional approaches, detecting planted clusters under high-noise conditions and with fewer samples. Compared to WGCNA on gene co-expression data, the Regularized Map Equation identifies more robust and functionally coherent gene modules. Our results establish Bayesian community detection as a principled and noise-resistant framework for uncovering modular structure in high-dimensional data across fields.

The KPFM random graph model is as defined in lines 66-69 where ([n], S) is a weighted graph that admits a pref. What we **should have** said at the bottom of p.2 is that we use independent sampling of edges only to prove concentration of hat{L}. The result extends to other graph models with dependent edges (e.g graph lifts) if one can prove concentration. "Misclustered" is defined the usual way: p_err (1/n)*(min over all permutations of cluster labels of the Hamming distance between label vectors). Alg 1 is almost that of [13,21] (there, columns are normalized after step 3 not before).

Spectral clustering is a fast and popular algorithm for finding clusters in networks. Recently, Chaudhuri et al. [1] and Amini et al. [2] proposed inspired variations on the algorithm that artificially inflate the node degrees for improved statistical performance. The current paper extends the previous statistical estimation results to the more canonical spectral clustering algorithm in a way that removes any assumption on the minimum degree and provides guidance on the choice of the tuning parameter. Moreover, our results show how the "star shape" in the eigenvectors-a common feature of empirical networks-can be explained by the Degree-Corrected Stochastic Blockmodel and the Extended Planted Partition model, two statistical models that allow for highly heterogeneous degrees. Throughout, the paper characterizes and justifies several of the variations of the spectral clustering algorithm in terms of these models.

Clustering graphs under the Stochastic Block Model (SBM) and extensions are well studied. Guarantees of correctness exist under the assumption that the data is sampled from a model. In this paper, we propose a framework, in which we obtain "correctness" guarantees without assuming the data comes from a model. The guarantees we obtain depend instead on the statistics of the data that can be checked. We also show that this framework ties in with the existing model-based framework, and that we can exploit results in model-based recovery, as well as strengthen the results existing in that area of research.

The fundamental principle of Graph Neural Networks (GNNs) is to exploit the structural information of the data by aggregating the neighboring nodes using a `graph convolution' in conjunction with a suitable choice for the network architecture, such as depth and activation functions. Therefore, understanding the influence of each of the design choice on the network performance is crucial. Convolutions based on graph Laplacian have emerged as the dominant choice with the symmetric normalization of the adjacency matrix as the most widely adopted one. However, some empirical studies show that row normalization of the adjacency matrix outperforms it in node classification. Despite the widespread use of GNNs, there is no rigorous theoretical study on the representation power of these convolutions, that could explain this behavior. Similarly, the empirical observation of the linear GNNs performance being on par with non-linear ReLU GNNs lacks rigorous theory. In this work, we theoretically analyze the influence of different aspects of the GNN architecture using the Graph Neural Tangent Kernel in a semi-supervised node classification setting. Under the population Degree Corrected Stochastic Block Model, we prove that: (i) linear networks capture the class information as good as ReLU networks; (ii) row normalization preserves the underlying class structure better than other convolutions; (iii) performance degrades with network depth due to over-smoothing, but the loss in class information is the slowest in row normalization; (iv) skip connections retain the class information even at infinite depth, thereby eliminating over-smoothing. We finally validate our theoretical findings numerically and on real datasets such as Cora and Citeseer.

In this paper we propose a lightning fast graph embedding method called graph encoder embedding. The proposed method has a linear computational complexity and the capacity to process billions of edges within minutes on standard PC -- an unattainable feat for any existing graph embedding method. The speedup is achieved without sacrificing embedding performance: the encoder embedding performs as good as, and can be viewed as a transformation of the more costly spectral embedding. The encoder embedding is applicable to either adjacency matrix or graph Laplacian, and is theoretically sound, i.e., under stochastic block model or random dot product graph, the graph encoder embedding asymptotically converges to the block probability or latent positions, and is approximately normally distributed. We showcase three important applications: vertex classification, vertex clustering, and graph bootstrap; and the embedding performance is evaluated via a comprehensive set of synthetic and real data. In every case, the graph encoder embedding exhibits unrivalled computational advantages while delivering excellent numerical performance.

These approaches, however, concept (for which there are many). Historically, most are based on general mixing patterns, which include community detection methods proposed have focused on assortativity only as a special case. In many ways this the detection of assortative communities, i.e. groups of is useful, and in fact arguably superior, since if assortativity nodes that tend to be more connected to themselves than happens to be the dominating pattern, then the to other nodes in the network. However, there are also general approach will capture it, otherwise it will reveal a community detection methods that are more general, and different structure. However, having only a more general attempt to cluster together nodes that have similar patterns method at our disposal also has its shortcomings. First, of connection, regardless if they are assortative or if it is true that assortativity is the main pattern for a not [3-5]. The widespread use of assortative community class of networks, then the more general representation detection methods has lead to the belief that the presence is needlessly wasteful for them, since it not only gives us of communities is a pervasive feature of many different more than we need, but in doing so it prevents us from kinds of real networks [6]. Although the concept of assortativity focusing on the more central features, at the cost of algorithmic is a central one in the study of social networks precision. Second, with a more general method (known as "homophily" in that context) [7], and is also an it can be difficult to quantify precisely how much has appealing construct in biology [8-10], it is to some extent been wasted in the representation, and what is indeed unclear if the perceived assortativity of many networks the simpler pattern hiding inside it.

Stochastic block models (SBMs) are often used to find assortative community structures in networks, such that the probability of connections within communities is higher than in between communities. However, classic SBMs are not limited to assortative structures. In this study, we discuss the implications of this model-inherent indifference towards assortativity or disassortativity, and show that this characteristic can lead to undesirable outcomes for networks which are presupposedy assortative but which contain a reduced amount of information. To circumvent this issue, we introduce a constrained SBM that imposes strong assortativity constraints, along with efficient algorithmic approaches to solve it. These constraints significantly boost community recovery capabilities in regimes that are close to the information-theoretic threshold. They also permit to identify structurally-different communities in networks representing cerebral-cortex activity regions.

One of the most natural tasks in graph theory is community detection, i.e., the identification of similarity groups on a given network. Practically, for an unweighted and undirected graph G(V, E) with V n nodes and E edges, community detection consists in finding a non-overlapping partition of the nodes that identifies underlying communities in a completely unsupervised manner. There is no unique definition of a community, but a general criterion is to impose that nodes in the same community have more interconnections than nodes in different communities, as a consequence of the stronger affinity among members of the same community [17]. There exist many ways of formalizing this intuition, some of them under the form of a cost function to minimize, such as the MinCut, RatioCut, and NormalizedCut costs [53]. The resulting optimizations are however NPhard problems and, as a consequence, many algorithms consist in retrieving relaxed continuous solutions of the problem.