The paper explains how regularization improves spectral clustering by reducing sensitivity to noise.
problem Spectral clustering's sensitivity to noise in sparse and stochastic graphs.
method Using graph conductance and regularization to improve spectral clustering.
result Regularization reduces sensitivity to small cuts in the graph, improving clustering accuracy and speed.
New algorithm speeds up spectral clustering for dynamic graphs.
problem Prohibitive complexity of spectral clustering for dynamic graphs.
method Reuse past cluster assignments and use fast Chebyshev graph filtering.
result Achieves clustering quality approximating spectral clustering with significant complexity benefits.
Enhanced spectral clustering for geometric graphs improves clustering accuracy.
problem Ineffective standard spectral clustering for geometric graphs.
method Higher-order spectral clustering using higher-order eigenvectors.
result Established weak and strong consistency for Soft Geometric Block Model.
Improved spectral clustering algorithm for better performance.
problem Improving the performance of spectral clustering algorithms.
method Developed a new performance guarantee under a weaker assumption and evaluated using a different spectral embedding map.
result Better performance guarantee under a weaker assumption and evaluation of a new spectral embedding map.
Two embedding methods in spectral graph clustering yield different but valid groupings.
problem Clustering vertices of a graph without true groupings.
method Spectral graph clustering using Laplacian or Adjacency spectral embedding.
result Laplacian embedding captures left hemisphere/right hemisphere structure, while adjacency embedding captures gray matter/white matter structure.
Paper analyzes spectral clustering for large graphs using random signals.
problem Complex eigen decomposition for large graphs.
method Graph filtering of random signals for approximate spectral embedding.
result Consistency of spectral clustering in stochastic block model.
This paper provides theoretical guarantees for spectral clustering using graph cuts.
problem Lack of performance guarantees for spectral clustering.
method Convex relaxation of graph cuts, spectral proximity condition, algebraic connectivity, inter-cluster connectivity.
result Deterministic bounds for successful spectral clustering are derived.
A novel multi-view spectral clustering model fuses and clusters data views.
problem Fusing and clustering multi-view data effectively.
method Simultaneously fuses and clusters views into a single graph.
result The proposed method outperforms existing techniques.
Consistent spectral clustering with fairness constraints on representation graphs.
problem Finding balanced clusters in similarity graphs with fairness constraints.
method Developed variants of unnormalized and normalized spectral clustering for fair planted partitions.
result Consistency results for constrained spectral clustering under fair planted partitions.
Spectral clustering for directed graphs using likelihood estimation.
problem Clustering directed graphs with edge directions.
method Maximum likelihood estimation on stochastic block models.
result Significant performance gains over existing methods.
New method reduces spectral clustering complexity by sparsifying graphs.
problem Computational bottleneck in spectral clustering due to eigendeomposition of NN graph Laplacian matrices.
method Spectrum-preserving graph sparsification via low-stretch spanning trees and spectral off-tree embedding.
result Ultra-sparse NN graphs with preserved first few eigenvectors for scalable spectral clustering.
AMOS automates model order selection for spectral graph clustering.
problem Automated selection of the correct number of clusters in spectral graph clustering.
method Incrementally increases the number of clusters, estimates cluster quality, and provides reliability tests.
result AMOS outputs clusters of minimal model order with statistical guarantees.
Graph pooling method uses GNN to cluster graphs efficiently.
problem Efficiently cluster graphs for graph pooling.
method Formulates a continuous relaxation of minCUT, trains GNN to minimize it.
result GNN-based clustering learns fast and performs well.
Dual regularized graph Laplacian improves spectral clustering for community detection.
problem Detecting clusters in networks with improved spectral clustering methods.
method Proposes dual regularized graph Laplacian for three spectral clustering approaches.
result Theoretical analysis shows DRSC and DRSLIM yield stable consistent community detection.
New methods for clustering graphs using spectral analysis.
problem Graph clustering for complex systems.
method Transfer operators and spectral properties.
result Spectral clustering can be interpreted using Koopman operators.
A new spectral clustering algorithm uses convex programming for better cluster identification.
problem Improving spectral clustering for better cluster identification in well-clustered graphs.
method Uses convex programming in the grouping stage of spectral clustering.
result The algorithm can find clusters of nodes with minimal conductance for well-clustered graphs.
New spectral clustering method using LASSO regularization for robust graph partitioning.
problem Lack of theoretical guarantees for spectral clustering on general graph models.
method 1-spectral clustering on a new random model with LASSO regularization.
result Effective and robust to small noise perturbations, validated by simulations and real data.
New spectral clustering method for graphs with uneven node degrees.
problem Challenges in community detection for graphs with heterogeneous degree distributions.
method Spectral clustering on spherical coordinates with degree correction.
result Improved performance in representing computer networks.
This paper explains spectral clustering and its equivalence to PCA, breaking it into fully connected and multi-connected cases.
problem Understanding the mathematics behind spectral clustering and its equivalence to PCA.
method Dividing spectral clustering into two categories based on graph connectivity and proving the equivalence to PCA.
result Spectral clustering and PCA are equivalent, with specific proofs for fully connected and multi-connected graphs.
New method finds balanced clusters in graphs using auxiliary information.
problem Finding balanced clusters in graphs with population-level constraints.
method Proposes individual-level balancing constraint and develops spectral clustering algorithms.
result Establishes first statistical consistency result for constrained spectral clustering.
The paper analyzes the Spectral Method for clustering data points on Union of Subspaces.
problem Clustering data points on Union of Subspaces.
method Constructing a Random Geometry Graph (Subspace Clustering) and analyzing it using spectral methods.
result Established a theory to analyze the Spectral Method's efficiency on Union of Subspaces.
Interpolates mean shift and spectral clustering on graphs.
problem Data clustering algorithms.
method Fokker-Planck equations on data graphs.
result New theoretical insights on diffusion maps and mean shift dynamics.
New spectral clustering for directed graphs reveals socio-economic patterns.
problem Spectral clustering for directed graphs is unsatisfactory due to edge directionality.
method Proposes a complex-valued matrix representation and analysis for directed graphs.
result Our approach reveals socio-economic patterns in internal migration data.
Biological and social systems consist of myriad interacting units. The interactions can be represented in the form of a graph or network. Measurements of these graphs can reveal the underlying structure of these interactions, which provides insight into the systems that generated the graphs. Moreover, in applications s…
SASE improves attributed graph clustering for large graphs with linear time and space complexity.
problem Challenges in clustering large attributed graphs due to high computational and memory costs.
method SASE combines node features smoothing, scalable spectral clustering, and adaptive order selection.
result SASE achieves a 6.9% improvement in ACC and a 5.87x speedup on the ArXiv dataset.
Root Laplacian Eigenmaps help in spectral embedding of graphs.
problem Efficient spectral embedding of graphs.
method Square root of graph-Laplacian operator.
result Improved spectral embedding techniques.
Spectral clustering achieves strong consistency in the stochastic block model under certain conditions.
problem Achieving strong consistency in spectral clustering for the stochastic block model.
method Entrywise analysis of the Fielder eigenvector of graph Laplacians.
result Spectral clustering achieves exact recovery of hidden communities under matching information-theoretic limits.
Two spectral algorithms detect clusters in directed graphs with cyclic or acyclic patterns.
problem Detecting clusters in directed graphs with cyclic or acyclic patterns.
method Computation of extremal eigenvalues of the transition matrix associated with the directed graph.
result The proposed methods outperform state-of-the-art methods on synthetic datasets and real-world networks.
KCoreMotif clusters large networks efficiently by exploiting k-core decomposition and motifs.
problem Efficiently clustering large networks for trust evaluation.
method Exploits k-core decomposition and motifs to perform motif-based spectral clustering on k-core subgraphs.
result The proposed algorithm is accurate and efficient for large networks.
This paper speeds up spectral clustering for large graphs by dilating their eigenspectrum.
problem Slow convergence in spectral clustering due to small eigengaps in graph Laplacians.
method Polynomial approximations to matrix operations that dilate the spectrum without changing eigenvectors.
result Significant acceleration of convergence in spectral clustering.
Optimizes graph spectral density learning for large networks.
problem Ad-hoc kernel function and bandwidth selection in graph spectral techniques.
method Maximum Entropy approach to learn a smooth graph spectral density.
result Outperforms comparable iterative spectral approaches on synthetic and real graphs.
New method clusters directed and undirected graphs without losing directional information.
problem Clustering directed graphs due to asymmetry in edge connectivity.
method Generalized Dirichlet Energy (GDE) and generalized spectral clustering (GSC).
result GSC outperforms existing methods in clustering accuracy and robustness.
This paper develops a multilayer spectral clustering method for heterogeneous data.
problem Clustering in multilayer graphs with varying layer weights and structures.
method Convex layer aggregation for multilayer spectral graph clustering (SGC).
result Phase transition analysis and automated cluster assignment with statistical guarantees.
This paper tackles multilayer graph clustering via convex layer aggregation.
problem Challenges in clustering multilayer graphs and combining information from each layer.
method Theoretical framework for multilayer spectral graph clustering via convex layer aggregation.
result Establishes a critical value on the noise level for reliable cluster separation.
Laplacian Eigenvectors of the graph constructed from a data set are used in many spectral manifold learning algorithms such as diffusion maps and spectral clustering. Given a graph constructed from a random sample of a d-dimensional compact submanifold M in RD, we establish the spectral convergence rate…
LOBPCG speeds up spectral clustering for streaming graphs, reducing computation time and memory usage.
problem Efficiently partitioning large graphs in streaming environments.
method Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) for graph Laplacians.
result LOBPCG reduces computation time by 100-1000x for streaming graphs compared to static graph partitioning.
Network Lasso clusters sparse graph clusters efficiently.
problem Local graph clustering of sparse and chain-like clusters.
method Network Lasso minimizes total variation of cluster indicator signals.
result Network Lasso handles sparse clusters difficult for spectral clustering.
Paper solves spectral clustering's dimensionality and complexity model selection issues.
problem Model selection problems in spectral graph clustering.
method Developed a probabilistic model and simultaneous model selection framework.
result Consistent estimates of model parameters for embedding dimension and number of clusters.
New method clusters evolving networks using spatio-temporal graph Laplacian.
problem Clustering communities in time-varying graphs.
method Extends spectral clustering to dynamic graphs using CCA and spatio-temporal graph Laplacian.
result The spatio-temporal graph Laplacian clearly interprets cluster evolution over time.
Unified spectral clustering improves on traditional methods by optimizing similarity graph and reducing information loss.
problem Traditional spectral clustering steps lead to information loss and performance degradation.
method Automatically learns optimal similarity graph and integrates continuous and discrete label learning.
result Unified framework optimizes clustering performance and reduces information loss.
GRASPEL learns large graphs from data efficiently.
problem Learning meaningful graphs from data for various applications.
method Highly scalable spectral approach using graph Laplacians and coarsening techniques.
result Ultra-sparse graphs with improved efficiency and accuracy in spectral clustering and t-SNE.
Paper provides a performance guarantee for spectral clustering.
problem Finding the global solution to the minimum ratio cut problem.
method Two-step spectral clustering method with a rounding step, analyzed using two-to-infinity norm perturbation bounds.
result Spectral clustering is guaranteed to output the global solution under certain conditions.
This paper establishes the consistency of spectral approaches to data clustering. We consider clustering of point clouds obtained as samples of a ground-truth measure. A graph representing the point cloud is obtained by assigning weights to edges based on the distance between the points they connect. We investigate the…
New algorithm for multiway spectral clustering on Grassmann manifolds.
problem Efficiently computing multiple eigenvectors of a nonlinear graph Laplacian.
method Direct multiway spectral clustering in p-norm, reformulated as minimization on Grassmann manifold. result Monotonic decrease of balanced graph cuts leads to optimal solutions.
This paper analyzes various graph clustering methods and their applications.
problem Dividing graphs into homogeneous groups for diverse applications.
method Traditional and deep learning-based clustering methods are compared.
result Deep learning techniques improve clustering accuracy.
This paper reduces graph-Laplacian dimensionality for spectral clustering of subsets.
problem High computational cost of graph-Laplacian spectral embedding for large data sets.
method Develops two algorithms for low-dimensional graph-Laplacian representation of target subsets.
result Ensures consistency of target subset clustering with full data set spectral clustering.
We define a class of Euclidean distances on weighted graphs, enabling to perform thermodynamic soft graph clustering. The class can be constructed form the "raw coordinates" encountered in spectral clustering, and can be extended by means of higher-dimensional embeddings (Schoenberg transformations). Geographical flow …
Efficient spectral clustering using autoencoders and landmarks.
problem High computational complexity of spectral clustering.
method Build adjacency matrix using landmarks, define efficient Laplacian matrix, perform eigen decomposition using autoencoder.
result Overall complexity of O(np), where n is data points and p is landmarks.