Paper compares graph and set partition measures for graph clustering.
problem Comparing graph clustering methods using different similarity measures.
method Introduces graph-aware partition similarity measures and compares them with set partition measures.
result Graph-aware measures provide complementary information to set partition measures.
Survey of mass partition problems in geometry and topology.
problem Inducing partitions on measures or sets by dividing space.
method Recent progress in topology, discrete geometry, and computer science.
result Connections between different fields.
New proof of a unique 3-part partition in 8D space.
problem Existence of a non-standard isoperimetric partition in high dimensions.
method Analytical proof showing existence of a specific partition.
result Existence of a non-standard isoperimetric partition in 8D space.
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.
Study identifies partitions of probability distributions using multi-armed bandits.
problem Identifying the correct partition of a vector of probability distributions.
method Developed sample complexity bounds and proposed algorithms for multi-armed bandit settings.
result Characterized lower bounds on mean number of samples and proposed algorithms matching these bounds.
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.
A new multilabel classification framework improves ANN search performance.
problem Efficiently finding approximate nearest neighbors in large datasets.
method Formulated ANN search as a multilabel classification problem, using partitioning classifiers.
result Natural classifier leads to strictly improved performance in ANN search.
This paper presents Sparse Partitioning, a Bayesian method for identifying predictors that either individually or in combination with others affect a response variable. The method is designed for regression problems involving binary or tertiary predictors and allows the number of predictors to exceed the size of the sa…
Algorithms learn and test variable partitions in various groups and error metrics.
problem Learning and testing variable partitions in different groups and error metrics.
method Algorithms for agnostically learning and testing k-partitionability over various groups and error metrics. result Learning algorithms for k-partitionability with polynomial time complexity and testing with adaptive queries. New partition designs reduce star discrepancy in high-dimensional sampling.
problem Improving the expected star discrepancy in high-dimensional sampling.
method Developed non-equal volume partitions to achieve lower expected star discrepancy.
result Explicit upper bounds for expected star discrepancy under non-equal volume partitions.
New findings on maximizing noise stability in partitions of Gaussian space.
problem Maximizing noise stability in partitions of Gaussian space.
method Analyzing the correlation between sets and their noise stability, proving conditional conjectures and hardness results.
result Hyperstable partitions maximize noise stability and have specific properties.
New method unifies and formalizes data partitioning using a single vector.
problem Data partitioning and clustering methods.
method Rank-one matrix factorization and denoising of piecewise constant signals.
result Demonstrates robustness of denoising step in partitioning.
New framework for differential privacy in vertically partitioned multiparty learning.
problem Challenges in preserving differential privacy under multiparty, especially vertically partitioned, settings.
method Functional mechanism with noise addition and secure aggregation.
result Released model achieves the same utility as centralized setting with one round of noise addition and secure aggregation.
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.
Although consistency is a minimum requirement of any estimator, little is known about consistency of the mean partition approach in consensus clustering. This contribution studies the asymptotic behavior of mean partitions. We show that under normal assumptions, the mean partition approach is consistent and asymptotic …
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.
Improved supervised EM learning for shared kernel models with feature space partitioning.
problem Lack of rigour in EM derivation and high computational complexity.
method Detailed derivation of EM for Gaussian shared kernel model, feature space partitioning to reduce complexity.
result Improved performance at reduced complexity achieved.
Efficiently calculates PL model likelihood for partitioned preference data.
problem Computational infeasibility of calculating PL model likelihood for partitioned preference data.
method Random utility model formulation and efficient numerical integration approach.
result Proposed method outperforms existing LTR baselines and scales to real-world tasks.
Paper generalizes reward distribution in multi-armed bandits with temporally-partitioned rewards.
problem Handling partial rewards distributed over multiple rounds in multi-armed bandits.
method Introduces Beta-spread property to generalize reward distribution, derives lower bound, and provides TP-UCB-FR-G algorithm.
result Improves regret upper bound for some scenarios using Beta-spread property.
New framework links fractal complexity to separation dimension.
problem Quantifying the complexity of fractal partitions.
method Introducing Separation Dimension ($\sepdim$) and Geometrically Regular Partitions (GRPs).
result Sharp upper bound for chromatic number of fractal partitions.
In this paper, we extend Roe's cyclic 1-cocycle to relative settings. We also prove two relative index theorems for partitioned manifolds by using its cyclic cocycle, which are generalizations of index theorems on partitioned manifolds. One of these theorems is a variant of [M. Karami-A.H.S. Sadegh-M.E. Zadeh, arXiv:…
Recently, there has been an increasing interest in designing distributed convex optimization algorithms under the setting where the data matrix is partitioned on features. Algorithms under this setting sometimes have many advantages over those under the setting where data is partitioned on samples, especially when the …
Study on covering probability of random balls in bounded open sets.
problem Probability of covering a bounded open set E with random balls of radius δ. method Geometric conditions and partition of E; lower bounds using good partitions. result Lower bounds to the probability of covering E with balls tend to 1 as Nexp(−δn). A new method for smoothing and parameter inference of Markov jump processes.
problem Approximate inference for Markov jump processes with latent variables.
method Moment-based variational inference with partitioning of transition classes.
result Expressed KL divergence in terms of moment functions.
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 …
Standard bubbles and partitions are stable in various model spaces.
problem Stability of standard bubbles and partitions in different model spaces.
method New conjugated Brascamp-Lieb inequality and conformally flattening boundary potential.
result Stability of standard bubbles and partitions in Rn, Sn, and Hn. Graphical heuristic reduces and partitions large datasets for faster supervised training.
problem Training large datasets for classification tasks.
method Clustering and information graph construction for dataset reduction and partitioning.
result Significant speed-up in training run-time without compromising prediction accuracy.
Study on estimating Gaussian mean from coarse data, resolving identifiability and computational efficiency questions.
problem Estimating the mean of a Gaussian distribution from coarse data (sets containing true samples rather than exact values).
method Analyzes the conditions for mean identifiability and computable estimation under convex partitions.
result Resolves the identifiability and computational efficiency questions for Gaussian mean estimation from coarse data.
Study exact partition recovery with same-cluster oracle, bounded error.
problem Exact recovery of partitions with same-cluster oracle in adversarial error.
method Novel connection to correlation clustering, Rényi-Ulam framework, upper and lower bounds, randomized algorithm analysis, adaptivity-query complexity study.
result Upper and lower bounds on worst-case query complexity, expected performance bounds of randomized algorithm.
The study explores continuous noncrossing partitions and their relation to weighted circular factorizations.
problem Understanding the structure of continuous noncrossing partitions on the unit circle.
method Analyzes degree-d continuous noncrossing partitions and their equivalence classes of weighted linear factorizations.
result Maximal elements in the poset of continuous noncrossing partitions form a subspace homeomorphic to the dual Garside classifying space for the d-strand braid group.
Paper improves neural network robustness analysis for safety-critical systems.
problem Uncertainty in neural network outputs for safety-critical systems.
method Unified propagation and partition approaches to provide tighter bounds.
result Proposed algorithms give tighter bounds than existing methods for the same computation time.
Proposes SPFB method for optimizing partition functions in stochastic learning.
problem Optimizing partition functions in stochastic learning settings.
method Stochastic Gradient Bound (SPFB) method based on upper-bounding the partition function with a quadratic surrogate.
result Sub-linear convergence rate of SPFB method and efficient training of deep learning models.
New study shows limits of low-degree algorithms in finding large independent sets in sparse hypergraphs.
problem Finding large independent sets in sparse random hypergraphs.
method Low-degree polynomial algorithms are analyzed to determine their limits.
result Low-degree algorithms can find independent sets of density up to \(\left(\frac{\log d}{(r-1)d}
ight)^{1/(r-1)}\), but no larger.
Survey of Bayesian nonparametric space partition models and their applications.
problem Partitioning high-dimensional spaces into homogeneous regions.
method Various strategies for generating partitions in a D-dimensional space.
result Review of current progress in BNSP research.
HPREF algorithm visualizes clustering results.
problem Visualizing parameter effects in clustering.
method Hierarchical partitioning of clusterings.
result Geometric structure of clustering results.
Bayesian nonparametric method partitions shapes using curves.
problem Capturing complex shapes in multi-dimensional data.
method Proposes a novel spline partitioning approach using curves.
result Demonstrates improved shape modeling compared to existing methods.
The paper extends localisation technique to multiple constraints in Euclidean spaces.
problem Proving log-concavity of conditional measures in decomposed convex sets.
method Defining partitions of maximal closed convex sets and proving log-concavity of conditional measures.
result Existence of a partition and log-concavity of conditional measures for almost every set of the partition.
Analyzes properties of transnormal Finsler functions on compact manifolds.
problem Properties of transnormal Finsler functions on compact manifolds.
method Analyzes critical level sets and partition properties of transnormal functions.
result Critical level sets of an analytic transnormal function are submanifolds, and the partition of M into level sets is a Finsler partition. A new method for multi-task learning improves performance without weakening inductive bias.
problem Joint optimization of parameters for multiple tasks remains challenging.
method Maximum Roaming, a novel parameter partitioning method inspired by dropout.
result Maximum Roaming improves performance compared to recent multi-task learning formulations.
The output scores of a neural network classifier are converted to probabilities via normalizing over the scores of all competing categories. Computing this partition function, Z, is then linear in the number of categories, which is problematic as real-world problem sets continue to grow in categorical types, such as …
Improved taxi demand-supply forecasts using graph-based LSTM.
problem Accurate taxi demand-supply forecasting with complex spatial and temporal patterns.
method Investigated impact of spatial partitioning techniques (Voronoi vs. Geohash) on LSTM network performance.
result GraphLSTM offers competitive performance against ConvLSTM, at lower complexity, across real-world data sets.
MREC efficiently matches and aligns point clouds, useful for single cell molecular data.
problem Comparing and aligning large datasets across various domains.
method Recursive decomposition algorithm for matching data sets, optimizing over partitioning and matching algorithms.
result Demonstrates flexibility and power in applying MREC to single cell molecular data alignment problems.
RIPE predicts and explains continuous/discrete data with sparse rule sets.
problem Predicting and explaining continuous/discrete data.
method RIPE infers a model from a sample, extracting a sparse set of hyperrectangles (rules) to partition the feature space.
result RIPE efficiently predicts and explains data, superior to other algorithms.
The method learns to partition event time space for better prediction.
problem Improving event time prediction in clinical settings with limited data.
method Develops a method to learn cut points for partitioning event time space.
result Improved prediction performance on real-world datasets.
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 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…
An element in Artin's braid group Bn is called periodic if it has a power which lies in the center of Bn. The conjugacy problem for periodic braids can be reduced to the following: given a divisor 1≤d<n−1 of n−1 and an element α in the super summit set of εd, find γ∈Bn such that γ−1αγ=εd, …
Paper proposes a new method to learn EBMs and their partition function.
problem Intractability of exact MLE for EBMs due to partition function computation.
method Jointly learns an energy model and its log-partition function using neural networks.
result First tractable method for optimizing sparsemax loss in large spaces.