We argue that the standard graph Laplacian is preferable for spectral partitioning of signed graphs compared to the signed Laplacian. Simple examples demonstrate that partitioning based on signs of components of the leading eigenvectors of the signed Laplacian may be meaningless, in contrast to partitioning based on th…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,181 papers · 148 categories
Trend · papers per month
48 results for “spectral partitioning”
Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partitioning to the case of hypergraphs. However, theoretical aspects of such methods have seldom received …
Topological recursion recovers a specific partition function for colored knots.
problem Recovering the extended Ooguri-Vafa partition function for colored HOMFLY-PT polynomials of torus knots.
method Applying topological recursion to the spectral curve of colored HOMFLY-PT polynomials of torus knots.
result Topological recursion reproduces the n-point functions of the extended Ooguri-Vafa partition function.
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.
Let φ(G) be the minimum conductance of an undirected graph G, and let 0=λ_1 <= λ_2 <=... <= λ_n <= 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k >= 2, φ(G) = O(k) λ_2 / \sqrt{λ_k}, and this performance guarantee is achieved by the spectral partitioning algorithm. …
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 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.
Spectral clustering approaches have led to well-accepted algorithms for finding accurate clusters in a given dataset. However, their application to large-scale datasets has been hindered by computational complexity of eigenvalue decompositions. Several algorithms have been proposed in the recent past to accelerate spec…
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.
New algorithm improves partition function approximation for graphical models.
problem Computing partition function of graphical models is computationally hard.
method Spectral mean-field scheme using FPTAS for low-rank matrices, and approximation of high-rank matrices.
result The proposed algorithm is more robust and accurate than previous methods.
New schemes improve vertex nomination in stochastic block models.
problem Ordering vertices with unknown labels in a network.
method Canonical sampling and extended spectral nomination schemes.
result Improved precision and scalability of vertex nomination schemes.
Unified framework for differentiable graph partitioning with probabilistic cuts.
problem Lack of general guarantees and principled gradients in prior probabilistic relaxations of graph cuts.
method Unified probabilistic framework covering a wide class of cuts, including Normalized Cut, with tight analytic upper bounds.
result Rigorous, numerically stable foundation for scalable, differentiable graph partitioning.
Improved spectral clustering via Gromov-Wasserstein Learning.
problem Optimizing graph partitioning performance.
method Bridge spectral clustering and GWL, using heat kernel for stable node correspondences.
result Improved graph partitioning results without compromising theoretical guarantees.
Enhances robustness of multi-view clustering via partition fusion.
problem Dealing with noises and inconsistency in multi-view data.
method Generates multiple partitions, integrates them, and co-evolves graph learning, partition generation, and view weight learning.
result Empirical results verify the effectiveness and robustness of the proposed approach.
Spectral clustering is widely used to partition graphs into distinct modules or communities. Existing methods for spectral clustering use the eigenvalues and eigenvectors of the graph Laplacian, an operator that is closely associated with random walks on graphs. We propose a new spectral partitioning method that exploi…
Spectral method for detecting communities in time-varying networks from noisy signals.
problem Detect communities in time-varying networks from noisy signals.
method Spectral algorithm based on latent stochastic blockmodel.
result Consistent recovery of community structure in time-varying networks.
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.
We review the concepts of the index of a Fredholm operator, the spectral flow of a curve of self-adjoint Fredholm operators, the Maslov index of a curve of Lagrangian subspaces in symplectic Hilbert space, and the eta invariant of operators of Dirac type on closed manifolds and manifolds with boundary. We emphasize var…
State space partitioning based on constrained spectral clustering for block particle filteringstat.ML
A new method for state space partitioning in block particle filtering reduces bias and variance.
problem Overcoming the curse of dimensionality in non-linear, non-Gaussian state space estimation.
method Formulates state space partitioning as a clustering problem and uses spectral clustering with constraints.
result The proposed method effectively groups correlated state variables into smaller blocks, reducing bias and variance.
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.
Develops algorithms for multi-way similarity clustering in hypergraphs.
problem Challenges of spectral clustering in multi-way similarity settings.
method Hypergraph Spectral Clustering (HSC) and Hypergraph Spectral Clustering with Local Refinement (HSCLR).
result Achieves optimal performance under the weighted stochastic block model.
The topological recursion of Eynard and Orantin governs a variety of problems in enumerative geometry and mathematical physics. The recursion uses the data of a spectral curve to define an infinite family of multidifferentials. It has been conjectured that, under certain conditions, the spectral curve possesses a non-c…
In this paper, we consider the problem of partitioning a small data sample drawn from a mixture of product distributions. We are interested in the case that individual features are of low average quality , and we want to use as few of them as possible to correctly partition the sample. We analyze a spectral tech…
A hierarchical community detection method using recursive partitioning.
problem Finding interpretable and accurate community structures in networks.
method Top-down recursive partitioning starting with spectral clustering.
result The algorithm correctly recovers community trees under mild assumptions.
Spectral algorithm recovers community structure in sparse hypergraphs.
problem Community detection in sparse random hypergraphs with community structure and higher-order interactions.
method Spectral algorithm with three steps: hyperedge selection, spectral partition, and correction/merging.
result Weak consistency achieved for weak signal-to-noise ratio.
PASCO speeds up graph clustering for large graphs.
problem Efficiently clustering large graphs with many communities.
method Overlay method combining coarsening and parallel clustering.
result PASCO accelerates clustering with improved efficiency and quality.
Two novel algorithms improve scalability and robustness of spectral clustering for large datasets.
problem Scalability and robustness of spectral clustering for large-scale datasets.
method Ultra-scalable spectral clustering (U-SPEC) and ultra-scalable ensemble clustering (U-SENC) algorithms.
result Robust and efficient clustering of ten-million-level datasets on a PC.
Spectral clustering is sensitive to how graphs are constructed from data particularly when proximal and imbalanced clusters are present. We show that Ratio-Cut (RCut) or normalized cut (NCut) objectives are not tailored to imbalanced data since they tend to emphasize cut sizes over cut values. We propose a graph partit…
A novel hypergraph partitioning method using tensor eigenvalue decomposition captures super-dyadic interactions.
problem Capturing super-dyadic interactions in k-uniform hypergraphs.
method Tensor-based representation and tensor eigenvalue decomposition for capturing interactions.
result Improved min-cut solution on 2-uniform hypergraphs (graphs) compared to standard spectral partitioning.
Framework clusters noisy MTS with robust fuzzy clustering, improving accuracy over existing methods.
problem Challenges in clustering multivariate time series due to non-stationary dependencies, noise, and state boundaries.
method Spectral fuzzy clustering using Kendall's tau-based canonical coherence for frequency-specific monotonic relationships.
result Framework outperforms existing methods in clustering noisy, high-dimensional MTS.
A new method for creating simpler models from complex ones.
problem Creating accurate approximations of complex models at reduced costs.
method Sequential adaptive surrogate modeling based on locally spectral expansions.
result Stochastic spectral embedding (SSE) shows good approximation capabilities and scalability.
Solves community detection in sparse hypergraphs above a threshold.
problem Community detection in sparse hypergraphs.
method Generalization of Massoulié's method for sparse random graphs to random hypergraphs.
result Above the threshold, a spectral algorithm constructs a partition correlated with the true partition.
Novel threefold partitioning of -spinor space on cone links.
problem Understanding equivariant Riemann-Roch defects in complex spaces with conic singularities.
method Investigates supertraces over local cohomology groups and spectral asymmetry.
result Novel complex equivariant and invariants defined.
Improved clustering algorithm for large datasets.
problem Finding alternative partitions in large datasets.
method Iterative Spectral Method (ISM) for alternative clustering.
result Significantly improved scalability and computation time.
GAP uses deep learning to efficiently partition graphs.
problem Graph partitioning to minimize edge cut.
method Deep learning approach with a differentiable loss function.
result GAP achieves competitive partitions and generalizes to unseen graphs.
A new method estimates rare failure events in complex systems.
problem Estimating the probability of rare failure events in non-linear systems.
method Stochastic Spectral Embedding (SSE) combined with modifications for efficient rare event estimation.
result Rare failure probability decomposed into conditional probabilities for easier computation.
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.
DPSM clusters nodes in data and graph spaces via density propagation and subcluster merging.
problem Automatic clustering of nodes in data and graph spaces.
method Density-based node clustering with propagation process and spectral clustering on subclusters.
result DPSM effectively clusters nodes in both data and graph spaces.
We study the problem of determining the optimal low dimensional projection for maximising the separability of a binary partition of an unlabelled dataset, as measured by spectral graph theory. This is achieved by finding projections which minimise the second eigenvalue of the graph Laplacian of the projected data, whic…
For a topological space , we introduce a criterion for the module to be finitely generated and give several applications. For instance, if is a finite connected complex, then satisfies the criterion. Our main tool is a spectral sequence that we der…
MSTs provide a fast and meaningful clustering method in low-dimensional data.
problem Quantifying the effectiveness of MSTs in low-dimensional clustering tasks.
method Identifying upper bounds for MST performance, reviewing and extending existing MST-based partitioning schemes.
result MST methods can be very competitive, often outperforming traditional clustering algorithms.
Let G=(V,E) be an undirected graph, lambda_k be the k-th smallest eigenvalue of the normalized laplacian matrix of G. There is a basic fact in algebraic graph theory that lambda_k > 0 if and only if G has at most k-1 connected components. We prove a robust version of this fact. If lambda_k>0, then for some 1\leq \ell\l…
Spectral clustering is robust to helpful model changes but not to random changes.
problem Robustness of spectral clustering in the presence of semirandom adversaries.
method Analysis of spectral clustering algorithms under semirandom adversaries.
result Spectral clustering with unnormalized Laplacian is strongly consistent under semirandom adversaries.
Researchers found the first and second eigenvalues are Courant-sharp on a Möbius strip.
problem Determining Courant-sharp eigenvalues on a Möbius strip.
method Analyzing the eigenvalues and nodal patterns of the Möbius strip.
result Only the first and second eigenvalues are Courant-sharp on the Möbius strip.
We consider a distributed learning approach in supervised learning for a large class of spectral regularization methods in an RKHS framework. The data set of size n is partitioned into disjoint subsets. On each subset, some spectral regularization method (belonging to a large class, including in particular K…
In this paper, we consider unsupervised partitioning problems, such as clustering, image segmentation, video segmentation and other change-point detection problems. We focus on partitioning problems based explicitly or implicitly on the minimization of Euclidean distortions, which include mean-based change-point detect…
Improved spectral clustering with fewer eigenvectors performs better.
problem Improving spectral clustering performance under weaker conditions.
method Tighter analysis and using fewer eigenvectors for embedding.
result Spectral clustering can produce better results with fewer eigenvectors.
The paper defines surface area for graphs and derives spectral estimates.
problem Understanding connectivity measures and spectral properties of graphs.
method Introducing surface area concepts related to inverse degree and deriving spectral bounds.
result An upper bound on the second eigenvalue for planar graphs.