arXiv research

New matrix reveals cluster info in sparse directed graphs.

Spectral method detects communities in sparse hypergraphs, achieving detection threshold.

A new graph neural network (NBA-GNN) avoids revisiting nodes to improve accuracy.

This paper presents VEC-NBT, a variation on the unsupervised graph clustering technique VEC, which improves upon the performance of the original algorithm significantly for sparse graphs. VEC employs a novel application of the state-of-the-art word2vec model to embed a graph in Euclidean space via random walks on the n…

Spectral clustering is a standard approach to label nodes on a graph by studying the (largest or lowest) eigenvalues of a symmetric real matrix such as e.g. the adjacency or the Laplacian. Recently, it has been argued that using instead a more complicated, non-symmetric and higher dimensional operator, related to the n…

Unified spectral clustering for sparse networks with heterogeneous degrees.

Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here we introduce a…

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 $Φ…

A distinguishing property of communities in networks is that cycles are more prevalent within communities than across communities. Thus, the detection of these communities may be aided through the incorporation of measures of the local "richness" of the cyclic structure. In this paper, we introduce renewal non-backtrac…

New method detects communities in complex hypergraphs, matching theoretical limits.

There have been several spectral bounds for the percolation transition in networks, using spectrum of matrices associated with the network such as the adjacency matrix and the non-backtracking matrix. However they are far from being tight when the network is sparse and displays clustering or transitivity, which is repr…

New findings support a new community recovery threshold for Stochastic Block Model with many communities.

HollowFlow speeds up likelihood evaluation for large-scale models.

We consider the problem of clustering partially labeled data from a minimal number of randomly chosen pairwise comparisons between the items. We introduce an efficient local algorithm based on a power iteration of the non-backtracking operator and study its performance on a simple model. For the case of two clusters, w…

New formula refutes random CSPs with fewer constraints.

New findings on community recovery in SBM with many communities.

Community detection is a fundamental problem in network analysis with many methods available to estimate communities. Most of these methods assume that the number of communities is known, which is often not the case in practice. We study a simple and very fast method for estimating the number of communities based on th…

We say that a subset $S\subseteq F_N$ is \emph{spectrally rigid} if whenever $T_1, T_2\in cv_N$ are points of the (unprojectivized) Outer space such that $||g||_{T_1}=||g||_{T_2}$ for every $g\in S$ then $T_1=T_2$ in $\cvn$. It is well-known that $F_N$ itself is spectrally rigid; it also follows from the result of Smil…

Spectral methods are popular in detecting global structures in the given data that can be represented as a matrix. However when the data matrix is sparse or noisy, classic spectral methods usually fail to work, due to localization of eigenvectors (or singular vectors) induced by the sparsity or noise. In this work, we …

New Bethe-Hessian method improves community detection in sparse networks.

Traditionally, community detection in graphs can be solved using spectral methods or posterior inference under probabilistic graphical models. Focusing on random graph families such as the stochastic block model, recent research has unified both approaches and identified both statistical and computational detection thr…

This paper investigates the behavior of the Min-Sum message passing scheme to solve systems of linear equations in the Laplacian matrices of graphs and to compute electric flows. Voltage and flow problems involve the minimization of quadratic functions and are fundamental primitives that arise in several domains. Algor…

Graph energy helps detect communities in networks better than traditional methods.

Several probabilistic models from high-dimensional statistics and machine learning reveal an intriguing --and yet poorly understood-- dichotomy. Either simple local algorithms succeed in estimating the object of interest, or even sophisticated semi-definite programming (SDP) relaxations fail. In order to explore this p…

The paper describes the K-theory of $C^*$-algebras of locally finite graphs.

AI methods often fail to outperform classical CPU-based solvers on Maximum Independent Set problems.

The paper proves geometric and spectral alignment for deep neural networks.

Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the …

This paper analyzes DeepWalk and node2vec for community detection in large networks.

In \cite{KSS06} it was shown that with respect to the simple non-backtracking random walk on the free group $F_N=F(a_1,\dots,a_N)$ the Whitehead algorithm has strongly linear time generic-case complexity and that "generic" elements of $F_N$ are "strictly minimal" in their $Out(F_N)$-orbits. Here we generalize these res…