Hypergraph partitioning is an important problem in machine learning, computer vision and network analytics. A widely used method for hypergraph partitioning relies on minimizing a normalized sum of the costs of partitioning hyperedges across clusters. Algorithmic solutions based on this approach assume that different p…
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “structured partitioning”
Graph partitioning is the problem of dividing the nodes of a graph into balanced partitions while minimizing the edge cut across the partitions. Due to its combinatorial nature, many approximate solutions have been developed, including variants of multi-level methods and spectral clustering. We propose GAP, a Generaliz…
Study on detecting hierarchical community structures in networks.
problem Detecting hierarchical community structures in networks.
method Analysis of planted hierarchies of partitions in networks, identifying additional detectability phases.
result There are additional phases in which the presence of multiple consistent partitions can either help or hinder detection of hierarchical structures.
Manifolds from Partitionsmath.GT
Maps discrete manifolds to partitions to define new manifolds.
problem Creating manifolds from discrete structures.
method Mapping discrete d-manifolds onto (k+1)-partite complexes to define new manifolds.
result Defines a (d-k)-manifold from simplices in G mapped to P.
The paper introduces the concept of a cluster structure to define a joint distribution of the sample size and its exchangeable random partitions. The cluster structure allows the probability distribution of the random partitions of a subset of the sample to be dependent on the sample size, a feature not presented in a …
Markov partitions for the geodesic flow on compact Riemann surfaces of constant negative curvaturemath.DG
The paper constructs Markov partitions for geodesic flow on hyperbolic surfaces.
problem Understanding Markov partitions for general hyperbolic flows.
method Rigorous construction of Markov partitions for geodesic flow on Riemann surfaces of constant negative curvature.
result Explicit forms of rectangles and local cross sections provided for the geodesic flow.
This research designs a data-driven partition to test independence between continuous variables.
problem Testing independence between continuous random variables.
method Empirical log-likelihood statistic and data-driven tree-structured partition.
result Strongly consistent test of independence over probability families.
In this paper we propose a novel Bayesian methodology for Value-at-Risk computation based on parametric Product Partition Models. Value-at-Risk is a standard tool to measure and control the market risk of an asset or a portfolio, and it is also required for regulatory purposes. Its popularity is partly due to the fact …
We review the polynomial structure of the topological string partition functions as solutions to the holomorphic anomaly equations. We also explain the connection between the ring of propagators defined from special Kähler geometry and the ring of almost-holomorphic modular forms defined on modular curves.
Exact partitioning of high-order planted models achieved through convex optimization.
problem Efficiently partitioning hypergraphs generated by high-order planted models.
method Solving a computationally efficient convex optimization problem with a tensor nuclear norm constraint.
result Exact recovery of true underlying cluster structures with high probability.
Online BSP-Forest improves space partitioning for large-scale classification and regression.
problem Efficient space partitioning for large-scale classification and regression problems.
method Developed an online BSP-Forest framework that expands space coverage and refines partition structure in real-time.
result Guaranteed universal consistency for both classification and regression problems.
New model of vague knowledge without strict partitions or transitivity.
problem Standard economic models of information fail to capture real-world vague knowledge.
method Relaxing assumptions of transitivity and partition structure to formalize vague knowledge.
result Vague knowledge can distinguish some states but not partition the state space.
We consider isotropic non lower semicontinuous weighted perimeter functionals defined on partitions of domains in . Besides identifying a condition on the structure of the domain which ensures the existence of minimizing configurations, we describe the structure of such minima, as well as their regularity…
A dependent partition-valued process for multitask clustering and time evolving network modellingstat.ML
The fundamental aim of clustering algorithms is to partition data points. We consider tasks where the discovered partition is allowed to vary with some covariate such as space or time. One approach would be to use fragmentation-coagulation processes, but these, being Markov processes, are restricted to linear or tree s…
We learn the structure of a Markov Network between two groups of random variables from joint observations. Since modelling and learning the full MN structure may be hard, learning the links between two groups directly may be a preferable option. We introduce a novel concept called the \emph{partitioned ratio} whose fac…
New methods reveal consensus and dissensus in network partitions.
problem Degenerate community detection methods often yield multiple competing answers.
method Comprehensive set of methods to characterize and summarize complex populations of partitions.
result It is not possible to obtain a consistent answer from point estimates when the distribution is heterogeneous.
We present a new method for articulating scale-dependent topological descriptions of the network structure inherent in many complex systems. The technique is based on "Partition Decoupled Null Models,'' a new class of null models that incorporate the interaction of clustered partitions into a random model and generaliz…
Both supervised and unsupervised machine learning algorithms have been used to learn partition-based index structures for approximate nearest neighbor (ANN) search. Existing supervised algorithms formulate the learning task as finding a partition in which the nearest neighbors of a training set point belong to the same…
Partition-wise Linear Modelsstat.ML
Region-specific linear models are widely used in practical applications because of their non-linear but highly interpretable model representations. One of the key challenges in their use is non-convexity in simultaneous optimization of regions and region-specific models. This paper proposes novel convex region-specific…
Summing over 3-manifolds using TQFT partition functions.
problem Summing over all 3-manifolds with fixed boundary.
method Rewriting the sum over 3-manifolds as a sum over homology groups, using TQFT partition functions and topological boundary conditions.
result Existence of a distribution of 2d TQFTs whose ensemble average equals the sum over 3-manifolds.
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.
Recent theory work has found that a special type of spatial partition tree - called a random projection tree - is adaptive to the intrinsic dimension of the data from which it is built. Here we examine this same question, with a combination of theory and experiments, for a broader class of trees that includes k-d trees…
We study the localization of a cluster of activated vertices in a graph, from adaptively designed compressive measurements. We propose a hierarchical partitioning of the graph that groups the activated vertices into few partitions, so that a top-down sensing procedure can identify these partitions, and hence the activa…
Novel hybrid method for Bayesian network structure learning reduces computational time without sacrificing accuracy.
problem Bayesian network structure learning efficiency and accuracy trade-off.
method Partitioned PC (pPC), -value adjacency thresholding (PATH), hybrid greedy initialization (HGI).
result pHGS achieves significant computational reductions compared to the PC algorithm without sacrificing structure learning accuracy.
Improved neural network robustness certification through tighter convex relaxations.
problem Certifying neural network robustness to perturbed and adversarial inputs.
method Exploiting ReLU network structure, novel partition-based certification procedure.
result Tightens existing linear programming relaxations to achieve zero relaxation error asymptotically.
Novel method recursively partitions sample space for density estimation.
problem Estimating complex density functions efficiently and accurately.
method Recursive partitioning of the sample space, asymptotically exact.
result Asymptotically exact approximation of any density function.
The Mondrian process represents an elegant and powerful approach for space partition modelling. However, as it restricts the partitions to be axis-aligned, its modelling flexibility is limited. In this work, we propose a self-consistent Binary Space Partitioning (BSP)-Tree process to generalize the Mondrian process. Th…
This thesis classifies pseudo-Anosov homeomorphisms using geometric Markov partitions.
problem Classifying pseudo-Anosov homeomorphisms up to topological conjugacy.
method Algorithmic approach using geometric Markov partitions.
result Geometric type is a complete invariant of conjugation.
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 combinatorial approach to Goldman-Turaev Lie bialgebra using cyclic word partitions.
problem Defining the Goldman bracket and Turaev cobracket combinatorially.
method Focus on partitions of cyclic words to define the bracket and cobracket.
result Combinatorial definition of the bracket and cobracket.
Bayesian approach for multifile record linkage and duplicate detection.
problem Challenges in merging overlapping datafiles with duplicates.
method Bayesian approach with novel partition representation and loss functions.
result Proposes a flexible prior for partitions and uncertain unresolved portions.
We study the problem of estimating a temporally varying coefficient and varying structure (VCVS) graphical model underlying nonstationary time series data, such as social states of interacting individuals or microarray expression profiles of gene networks, as opposed to i.i.d. data from an invariant model widely consid…
A new multi-view clustering method using deep matrix decomposition and partition alignment.
problem Improving multi-view clustering methods to better utilize data representations and view-specific structures.
method Deep matrix decomposition for partition representations, joint use of partition representations, and alternating optimization.
result Demonstrated effectiveness on six benchmark datasets compared to state-of-the-art methods.
We propose a new outline for adaptive dictionary learning methods for sparse encoding based on a hierarchical clustering of the training data. Through recursive application of a clustering method, the data is organized into a binary partition tree representing a multiscale structure. The dictionary atoms are defined ad…
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…
Multi-view clustering is an important yet challenging task due to the difficulty of integrating the information from multiple representations. Most existing multi-view clustering methods explore the heterogeneous information in the space where the data points lie. Such common practice may cause significant information …
Structure learning of Bayesian networks has always been a challenging problem. Nowadays, massive-size networks with thousands or more of nodes but fewer samples frequently appear in many areas. We develop a divide-and-conquer framework, called partition-estimation-fusion (PEF), for structure learning of such big networ…
New stratification reveals intrinsic singularity types of orbit spaces.
problem Understanding the intrinsic structure of orbit spaces under Lie group actions.
method Introduced the isostabilizer decomposition and established a map to Klein strata.
result A new canonical stratification on the manifold clarifies the relationship with classical structures.
Topological twists for 4d N=2 theories depend on spacetime type, gerbe connections, and generalized spin-c structures.
problem Defining topologically twisted partition functions for 4d N=2 theories.
method Topological twisting for general 4d N=2 theories, introducing generalized spin-c structures.
result Topological partition functions depend on spacetime type, gerbe connections, and generalized spin-c structures.
This study proposes a graph partitioning method to improve spatial prediction models.
problem Improving interpretability of spatial prediction models in industries.
method Graph partitioning problem to minimize within-segment variances, formulated as mixed-integer quadratic programming.
result Approximation scheme efficiently identifies spatial segments, improving computational efficiency.
Clustering is an essential technique for discovering patterns in data. The steady increase in amount and complexity of data over the years led to improvements and development of new clustering algorithms. However, algorithms that can cluster data with mixed variable types (continuous and categorical) remain limited, de…
Accurate taxi demand-supply forecasting is a challenging application of ITS (Intelligent Transportation Systems), due to the complex spatial and temporal patterns. We investigate the impact of different spatial partitioning techniques on the prediction performance of an LSTM (Long Short-Term Memory) network, in the con…
We introduce an innovative theoretical framework to model derivative transactions between defaultable entities based on the principle of arbitrage freedom. Our framework extends the traditional formulations based on Credit and Debit Valuation Adjustments (CVA and DVA). Depending on how the default contingency is accoun…
In a previous paper, we showed how certain orientations of the edges of a graph G embedded in a closed oriented surface S can be understood as discrete spin structures on S. We then used this correspondence to give a geometric proof of the Pfaffian formula for the partition function of the dimer model on G. In the pres…
Bounds on the log partition function are important in a variety of contexts, including approximate inference, model fitting, decision theory, and large deviations analysis. We introduce a new class of upper bounds on the log partition function, based on convex combinations of distributions in the exponential domain, th…
We study the effects of having multiple Spin structures on the partition function of the spacetime fields in M-theory. This leads to a potential anomaly which appears in the eta-invariants upon variation of the Spin structure. The main source of such spaces are manifolds with nontrivial fundamental group, which are als…
We propose an algorithm, HPREF (Hierarchical Partitioning by Repeated Features), that produces a hierarchical partition of a set of clusterings of a fixed dataset, such as sets of clusterings produced by running a clustering algorithm with a range of parameters. This gives geometric structure to such sets of clustering…
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…