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.
New Karger-like algorithms solve graph cuts, useful for image segmentation.
Algorithms based on spectral graph cut objectives such as normalized cuts, ratio cuts and ratio association have become popular in recent years because they are widely applicable and simple to implement via standard eigenvector computations. Despite strong performance for a number of clustering tasks, spectral graph cu…
A novel hypergraph partitioning method using tensor eigenvalue decomposition captures super-dyadic interactions.
Study shows convergence rates for Cheeger cuts on data clouds.
Spectral clustering (SC) and graph-based semi-supervised learning (SSL) algorithms are sensitive to how graphs are constructed from data. In particular if the data has proximal and unbalanced clusters these algorithms can lead to poor performance on well-known graphs such as -NN, full-RBF, -graphs. This is becaus…
It has been recently shown that a large class of balanced graph cuts allows for an exact relaxation into a nonlinear eigenproblem. We review briefly some of these results and propose a family of algorithms to compute nonlinear eigenvectors which encompasses previous work as special cases. We provide a detailed analysis…
We propose a new method to model multi-way similarities into hypergraphs for clustering.
In this paper, we develop a novel weighted Laplacian method, which is partially inspired by the theory of graph Laplacian, to study recent popular graph problems, such as multilevel graph partitioning and balanced minimum cut problem, in a more convenient manner. Since the weighted Laplacian strategy inherits the virtu…
This paper establishes the consistency of a family of graph-cut-based algorithms for clustering of data clouds. We consider point clouds obtained as samples of a ground-truth measure. We investigate approaches to clustering based on minimizing objective functionals defined on proximity graphs of the given sample. Our f…
New algorithm for multiway spectral clustering on Grassmann manifolds.
Min-cut clustering, based on minimizing one of two heuristic cost-functions proposed by Shi and Malik, has spawned tremendous research, both analytic and algorithmic, in the graph partitioning and image segmentation communities over the last decade. It is however unclear if these heuristics can be derived from a more g…
Paper connects probability density cuts to graph theory eigenfunctions.
A new kernel for ranked data tackles computational challenges.
Spectral Clustering as a relaxation of the normalized/ratio cut has become one of the standard graph-based clustering methods. Existing methods for the computation of multiple clusters, corresponding to a balanced -cut of the graph, are either based on greedy techniques or heuristics which have weak connection to th…
Unified framework for differentiable graph partitioning with probabilistic cuts.
Graph cuts find global optima for Potts models in slight perturbations.
Spectral clustering has become one of the most widely used clustering techniques when the structure of the individual clusters is non-convex or highly anisotropic. Yet, despite its immense popularity, there exists fairly little theory about performance guarantees for spectral clustering. This issue is partly due to the…
Tangles improve clustering in various datasets.
The maximum a posteriori (MAP) configuration of binary variable models with submodular graph-structured energy functions can be found efficiently and exactly by graph cuts. Max-product belief propagation (MP) has been shown to be suboptimal on this class of energy functions by a canonical counterexample where MP conver…
A biclustering algorithm finds dense disjoint subgraphs in weighted bipartite graphs.
Summarizing large-scaled directed graphs into small-scale representations is a useful but less studied problem setting. Conventional clustering approaches, which based on "Min-Cut"-style criteria, compress both the vertices and edges of the graph into the communities, that lead to a loss of directed edge information. O…
We showed in another paper [arXiv:1103.1759] that every connected graph can be realized as the cut locus of some point on some riemannian surface . Here, criteria for the orientability of are given, and are applied to classify the distinct, orientable, cut locus structures on graphs with four generating cycles.
We study the scenario of graph-based clustering algorithms such as spectral clustering. Given a set of data points, one first has to construct a graph on the data points and then apply a graph clustering algorithm to find a suitable partition of the graph. Our main question is if and how the construction of the graph (…
Proves a generalized Whitehead cut vertex lemma for tree groups.
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…
Proves bounds on spanning two-forests and random cut sizes.
Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for graph sparsification. This choice is motivated by the observation…
Spectral clustering methods which are frequently used in clustering and community detection applications are sensitive to the specific graph constructions particularly when imbalanced clusters are present. We show that ratio cut (RCut) or normalized cut (NCut) objectives are not tailored to imbalanced cluster sizes sin…
A new reinforcement learning method improves Max-Cut solutions without needing training data.
TokenCut detects and segments objects in images and videos without supervision.
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. …
Algorithm determines spatial graph isomorphism with vertex, edge colorings and orientations.
The paper optimizes spatial experimental designs to improve causal effect estimation.
We proved in another paper that every connected graph can be realized as the cut locus of some point on some riemannian surface. Here we give upper bounds on the number of such realizations.
We prove that every connected graph can be realized as the cut locus of some point on some Riemannian surface which, in some cases, has constant curvature. We study the stability of such realizations, and their generic behavior.
Integer programming (IP) is a general optimization framework widely applicable to a variety of unstructured and structured problems arising in, e.g., scheduling, production planning, and graph optimization. As IP models many provably hard to solve problems, modern IP solvers rely on many heuristics. These heuristics ar…
This research introduces dynamic portfolio cuts using a spectral approach for graph-theoretic diversification.
Spectral clustering is a popular and versatile clustering method based on a relaxation of the normalised graph cut objective. Despite its popularity, however, there is no single agreed upon method for tuning the important scaling parameter, nor for determining automatically the number of clusters to extract. Popular he…
Graph construction is a crucial step in spectral clustering (SC) and graph-based semi-supervised learning (SSL). Spectral methods applied on standard graphs such as full-RBF, -graphs and -NN graphs can lead to poor performance in the presence of proximal and unbalanced data. This is because spectral methods based…
New invariant defined for Weinstein domains, related to Kirby-Thompson's invariant.
Investment returns naturally reside on irregular domains, however, standard multivariate portfolio optimization methods are agnostic to data structure. To this end, we investigate ways for domain knowledge to be conveniently incorporated into the analysis, by means of graphs. Next, to relax the assumption of the comple…
We investigate Legendrian graphs in . We extend the classical invariants, Thurston-Bennequin number and rotation number to Legendrian graphs. We prove that a graph can be Legendrian realized with all its cycles Legendrian unknots with and if and only if it does not contain as a mi…
This dissertation uses ILP to learn Bayesian network structures efficiently.
We give polynomial-time algorithms for the exact computation of lowest-energy (ground) states, worst margin violators, log partition functions, and marginal edge probabilities in certain binary undirected graphical models. Our approach provides an interesting alternative to the well-known graph cut paradigm in that it …
Paper provides a performance guarantee for spectral clustering.
The paper studies grid homology for spatial graphs and proves a Künneth formula for connected sums.
Method learns graphons from graphs via Gromov-Wasserstein barycenters.
New method reduces errors in causal discovery from data.