arXiv research

In Stochastic blockmodels, which are among the most prominent statistical models for cluster analysis of complex networks, clusters are defined as groups of nodes with statistically similar link probabilities within and between groups. A recent extension by Karrer and Newman incorporates a node degree correction to mod…

The paper corrects for node degree in spectral clustering using random walk Laplacian.

The proliferation of models for networks raises challenging problems of model selection: the data are sparse and globally dependent, and models are typically high-dimensional and have large numbers of latent variables. Together, these issues mean that the usual model-selection criteria do not work properly for networks…

Develops a new tensor model for clustering with degree correction.

We consider community detection in Degree-Corrected Stochastic Block Models (DC-SBM). We propose a spectral clustering algorithm based on a suitably normalized adjacency matrix. We show that this algorithm consistently recovers the block-membership of all but a vanishing fraction of nodes, in the regime where the lowes…

Community detection is a central problem of network data analysis. Given a network, the goal of community detection is to partition the network nodes into a small number of clusters, which could often help reveal interesting structures. The present paper studies community detection in Degree-Corrected Block Models (DCB…

New spectral clustering method for graphs with uneven node degrees.

The stochastic block model is a powerful tool for inferring community structure from network topology. However, it predicts a Poisson degree distribution within each community, while most real-world networks have a heavy-tailed degree distribution. The degree-corrected block model can accommodate arbitrary degree distr…

For the degree corrected stochastic block model in the presence of arbitrary or even adversarial outliers, we develop a convex-optimization-based clustering algorithm that includes a penalization term depending on the positive deviation of a node from the expected number of edges to other inliers. We prove that under m…

Motivated by community detection, we characterise the spectrum of the non-backtracking matrix $B$ in the Degree-Corrected Stochastic Block Model. Specifically, we consider a random graph on $n$ vertices partitioned into two equal-sized clusters. The vertices have i.i.d. weights $\{ φ_u \}_{u=1}^n$ with second moment $Φ…

Spectral clustering is a fast and popular algorithm for finding clusters in networks. Recently, Chaudhuri et al. (2012) and Amini et al.(2012) proposed inspired variations on the algorithm that artificially inflate the node degrees for improved statistical performance. The current paper extends the previous statistical…

Improved model for grouping nodes in bipartite networks.

Derives log-corrections in AdS4/CFT3 using supergravity localization.

Improved spectral clustering for community detection in networks.

Paper characterizes optimal graph clustering limits under a new model.

The stochastic block model (SBM) is a popular framework for studying community detection in networks. This model is limited by the assumption that all nodes in the same community are statistically equivalent and have equal expected degrees. The degree-corrected stochastic block model (DCSBM) is a natural extension of S…

Community detection or clustering is a fundamental task in the analysis of network data. Many real networks have a bipartite structure which makes community detection challenging. In this paper, we consider a model which allows for matched communities in the bipartite setting, in addition to node covariates with inform…

The purpose of this erratum is to correct a mistake in the proof of Theorem 4.1 of our paper \cite{CF}.

We propose and analyze a generic method for community recovery in stochastic block models and degree corrected block models. This approach can exactly recover the hidden communities with high probability when the expected node degrees are of order $\log n$ or higher. Starting from a roughly correct community partition …

Bayesian method corrects for model selection multiplicity in regression.

Corrects GCV for inconsistent risk estimation in finite ensembles of penalized estimators.

A goodness-of-fit test for DCSBM improves scalability and power for large sparse networks.

The paper proposes a new model to analyze directed networks and accurately estimate community memberships.

New method for community detection in graphs faster than DCBM inference.

We compute the sets of degrees of maps between principal $SU(2)$-bundles over $S^5$, i.e. between any of the manifolds $SU(2)\times S^5$ and $SU(3)$. We show that the Steenrod squares provide the only obstruction to the existence of a mapping degree between these manifolds, and construct explicit maps realizing each in…

We provide local expressions for Chern-Weil type forms built from superconnections associated with families of Dirac operators previously investigated in work by S. Scott and later work by S. Scott and the second author. When the underlying fibration of manifolds is trivial, the even degree forms can be interpreted as …

Stochastic block models (SBMs) have been playing an important role in modeling clusters or community structures of network data. But, it is incapable of handling several complex features ubiquitously exhibited in real-world networks, one of which is the power-law degree characteristic. To this end, we propose a new var…

We present a method to desingularize a compact G_2 manifold with isolated conical singularities by cutting out a neighbourhood of each singular point and glueing in an asymptotically conical G_2 manifold. Controlling the error on the overlap glueing region enables us to use a result of Joyce to conclude that the result…

A fast spectral algorithm detects community structure in evolving graphs.

Study improves understanding of network degree distributions using non-linear ERGs.

Anytime-valid confirmation of label-shift corrections

Develops a theory for equivariant networks with partial domain symmetry.

We describe a machine-learning approach to pitch correcting a solo singing performance in a karaoke setting, where the solo voice and accompaniment are on separate tracks. The proposed approach addresses the situation where no musical score of the vocals nor the accompaniment exists: It predicts the amount of correctio…

Closed formulas for η-corrections in the once-punctured torus identified.

Improves community detection in directed networks with theoretical guarantees.

Human input has enabled autonomous systems to improve their capabilities and achieve complex behaviors that are otherwise challenging to generate automatically. Recent work focuses on how robots can use such input - like demonstrations or corrections - to learn intended objectives. These techniques assume that the huma…

Network data is prevalent in many contemporary big data applications in which a common interest is to unveil important latent links between different pairs of nodes. Yet a simple fundamental question of how to precisely quantify the statistical uncertainty associated with the identification of latent links still remain…

Measures neural network complexity via effective degrees of freedom.

We study recursive-cube-of-rings (RCR), a class of scalable graphs that can potentially provide rich inter-connection network topology for the emerging distributed and parallel computing infrastructure. Through rigorous proof and validating examples, we have corrected previous misunderstandings on the topological prope…

A new method for community detection in networks is presented.

New algorithm recovers communities in broader network models.

We introduce a data-driven approach to automatic pitch correction of solo singing performances. The proposed approach predicts note-wise pitch shifts from the relationship between the respective spectrograms of the singing and accompaniment. This approach differs from commercial systems, where vocal track notes are usu…

We consider the Degree-Corrected Stochastic Block Model (DC-SBM): a random graph on $n$ nodes, having i.i.d. weights $(φ_u)_{u=1}^n$ (possibly heavy-tailed), partitioned into $q \geq 2$ asymptotically equal-sized clusters. The model parameters are two constants $a,b > 0$ and the finite second moment of the weights $Φ^{…

We study binary classification in the setting where the learner is presented with multiple corrupted training samples, with possibly different sample sizes and degrees of corruption, and introduce an approach based on minimizing a weighted combination of corruption-corrected empirical risks. We establish a generalizati…

The paper explores how different network architectures learn logical functions under GOTU, finding that a min-degree-interpolator is learned.

Vertex clustering in a stochastic blockmodel graph has wide applicability and has been the subject of extensive research. In thispaper, we provide a short proof that the adjacency spectral embedding can be used to obtain perfect clustering for the stochastic blockmodel and the degree-corrected stochastic blockmodel. We…

The paper reviews methods for determining the number of communities in network data.

A time-varying cointegration model for foreign exchange rates is presented. Unlike previous studies, we allow the loading matrix in the vector error correction (VEC) model to be varying over time. Because the loading matrix in the VEC model is associated with the speed at which deviations from the long-run relationship…