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 …
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 “Hypergraph partitioning”
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.
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…
In a series of recent works, we have generalised the consistency results in the stochastic block model literature to the case of uniform and non-uniform hypergraphs. The present paper continues the same line of study, where we focus on partitioning weighted uniform hypergraphs---a problem often encountered in computer …
We consider the community detection problem in sparse random hypergraphs. Angelini et al. (2015) conjectured the existence of a sharp threshold on model parameters for community detection in sparse hypergraphs generated by a hypergraph stochastic block model. We solve the positive part of the conjecture for the case of…
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.
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.
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.
Spectral clustering is a celebrated algorithm that partitions objects based on pairwise similarity information. While this approach has been successfully applied to a variety of domains, it comes with limitations. The reason is that there are many other applications in which only \emph{multi}-way similarity measures ar…
SDP approach recovers communities in multilayer hypergraphs from aggregated similarity matrices.
problem Community recovery in multilayer hypergraphs using aggregated similarity matrices.
method Semidefinite programming (SDP) approach.
result Information-theoretic conditions for exact recovery in both assortative and disassortative cases.
We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization (QDSFM), which allows to model a number of learning tasks on graphs and hypergraphs. The problem exhibits close ties to decomposable submodular function minimization (DSFM), yet is much more challenging to sol…
We introduce a new quasi-isometry invariant of 2-dimensional right-angled Coxeter groups, the hypergraph index, that partitions these groups into infinitely many quasi-isometry classes, each containing infinitely many groups. Furthermore, the hypergraph index of any right-angled Coxeter group can be directly computed f…
Paper finds exact recovery threshold in general hypergraph model.
problem Exact recovery of communities in general hypergraph model.
method Developed a two-stage polynomial-time algorithm for exact recovery.
result Sharp threshold for exact recovery in terms of generalized Chernoff-Hellinger divergence.
We provide a novel analysis of low-rank tensor completion based on hypergraph expanders. As a proxy for rank, we minimize the max-quasinorm of the tensor, which generalizes the max-norm for matrices. Our analysis is deterministic and shows that the number of samples required to approximately recover an order- tensor…
We consider the exact recovery problem in the hypergraph stochastic block model (HSBM) with blocks of equal size. More precisely, we consider a random -uniform hypergraph with vertices partitioned into clusters of size . Hyperedges are added independently with probability if is…
Geometry of the Space of Partitioned Networks: A Unified Theoretical and Computational Frameworkmath.MG
Unified framework for higher-order network analysis.
problem Complex structure of space of networks.
method Measure-theoretic formalism, Gromov-Wasserstein distance, co-optimal transport distance.
result Unified theoretical treatment of generalized networks.
Binary classification is one of the most common problem in machine learning. It consists in predicting whether a given element belongs to a particular class. In this paper, a new algorithm for binary classification is proposed using a hypergraph representation. The method is agnostic to data representation, can work wi…
Hypergraphs allow one to encode higher-order relationships in data and are thus a very flexible modeling tool. Current learning methods are either based on approximations of the hypergraphs via graphs or on tensor methods which are only applicable under special conditions. In this paper, we present a new learning frame…
Study compares hypergraph and graph-level models for higher-order relational learning.
problem Evaluating effectiveness of hypergraph-level vs. graph-level models in relational learning.
method Systematic evaluation of various hypergraph and graph-level architectures.
result Graph-level models applied to hypergraph expansions outperform hypergraph-level models.
Develops a Markov Random Field model for hypergraphs to improve machine learning tasks.
problem Modeling data generation processes on hypergraphs for better machine learning.
method Hypergraph Markov Random Field model using multivariate Gaussian distribution.
result Proposed model enhances algorithm design and outperforms existing methods in structure inference and node classification.
HyperBERT enhances BERT for node classification on text-attributed hypergraphs.
problem Challenges in capturing hypergraph structure and text attributes in node classification.
method Mixing hypergraph-aware layers with BERT for improved node classification.
result HyperBERT achieves state-of-the-art results on text-attributed hypergraph benchmarks.
A new hypergraph expansion method treats vertices and hyperedges equally, improving node classification.
problem Information loss in hypergraph expansions on either vertex or hyperedge level.
method Proposes a new hypergraph formulation named line expansion (LE) that treats vertices and hyperedges symmetrically.
result The proposed line expansion method outperforms state-of-the-art baselines on five hypergraph datasets.
Extends graph theory to hypergraphs with manifold-valued nodes.
problem Representing complex N-ary relationships on manifolds.
method Defined function spaces and symmetric products for manifold-valued nodes and edges.
result Generalized hypergraph Laplacians to manifold-valued hypergraphs.
The graph Laplacian plays key roles in information processing of relational data, and has analogies with the Laplacian in differential geometry. In this paper, we generalize the analogy between graph Laplacian and differential geometry to the hypergraph setting, and propose a novel hypergraph -Laplacian. Unlike the …
Extends Borsuk-Ulam theorem with applications in sphere coverings and colorings.
problem Complexity bounds and structural insights for triangulated sphere mappings.
method Combinatorial labeling and order type analysis of finite point sets.
result New topological Hall theorem and generalizations of hypergraph Hall theorems.
Paper introduces a noise-robust classification method using hypergraph neural networks.
problem Noisy label learning problem in image datasets.
method PCA for dimensionality reduction, then applies graph-based semi-supervised learning methods including hypergraph neural network.
result Our proposed hypergraph neural network achieves the best performance when noise level increases.
New method detects communities in hypergraphs by embedding them into a vector space.
problem Detecting communities in hypergraphs with multi-way interactions.
method Augmenting non-uniform hypergraphs, embedding into a vector space, using an alternative updating scheme.
result Asymptotic consistencies in community detection and hypergraph estimation established.
Perfect clustering achieved in hypergraphs with enough interactions.
problem Complexity and lack of tractable models for analyzing hypergraphs.
method Introduced an interaction hypergraph model for analyzing hypergraphs, defined latent embeddings, and analyzed spectral estimators.
result A spectral estimate of interaction latent positions can achieve perfect clustering with enough interactions.
Hypergraphs are used in machine learning to model higher-order relationships in data. While spectral methods for graphs are well-established, spectral theory for hypergraphs remains an active area of research. In this paper, we use random walks to develop a spectral theory for hypergraphs with edge-dependent vertex wei…
Recently, graph neural networks have attracted great attention and achieved prominent performance in various research fields. Most of those algorithms have assumed pairwise relationships of objects of interest. However, in many real applications, the relationships between objects are in higher-order, beyond a pairwise …
Unified LLY Ricci curvature defined for hypergraphs.
problem Defining Ricci curvature for hypergraphs.
method Unified framework for LLY Ricci curvature on hypergraphs, establishing bounds and proving properties.
result Bonnet-Myers-type theorem for hypergraphs, highlighting curvature's potential in hypergraph analysis.
Paper learns hypergraph structures from signals with smoothness priors.
problem Learning hypergraph structures from signals with high-order relationships.
method Proposes HGSL framework with dual smoothness prior to map signals to hypergraph structure.
result HGSL efficiently infers meaningful hypergraph topologies from signals.
Develops neural network for directed hypergraphs for node classification.
problem Irregular data structure, particularly directed graphs.
method Directed hypergraph neural network and semi-supervised learning method.
result Novel directed hypergraph neural network achieves highest accuracies on node classification tasks.
In many real-world network datasets such as co-authorship, co-citation, email communication, etc., relationships are complex and go beyond pairwise. Hypergraphs provide a flexible and natural modeling tool to model such complex relationships. The obvious existence of such complex relationships in many real-world networ…
Derives a Matern Gaussian process on hypergraphs for regression and embedding.
problem Regression and embedding of vertices in hypergraphs with uncertainty.
method Derives a Matern Gaussian process on hypergraphs, embeds vertices into latent space, identifies inducing vertices for scalable inference.
result Enables estimation of regression models with hypergraph structure informed correlation and uncertainty.
Information Theoretic Limits of Exact Recovery in Sub-hypergraph Models for Community Detectionstat.ML
Study information limits for community detection in sub-hypergraphs.
problem Identify limits for exact community detection in sub-hypergraphs.
method Use Fano's inequality to define model parameters and identify success and failure regions.
result Identify regions where algorithms succeed or fail in exact recovery.
The study connects hypergraphs to strong homotopy Lie algebras.
problem Characterizing hypergraphs with a system of distinct representatives.
method Describing a procedure to attach nilpotent strong homotopy Lie algebras to hypergraphs.
result Isomorphic hypergraphs correspond to isomorphic strong homotopy Lie algebras.
New method clusters hypergraphs using weighted random walks and Laplacians.
problem Clustering hypergraph data with edge-dependent weights.
method Random walks with edge-dependent vertex weights, constructing hypergraph Laplacians for clustering.
result Proposed methods outperform existing hypergraph clustering algorithms.
HNHN learns from hypergraphs with hyperedge neurons for better classification.
problem Learning from hypergraphs with complex relationships.
method Hypergraph convolution network with hyperedge neurons and adaptive normalization.
result Improved classification accuracy and speed compared to state-of-the-art methods.
We propose a new method to model multi-way similarities into hypergraphs for clustering.
problem Clustering real-valued data using hypergraphs with multi-way similarities.
method Formulate multi-way similarities using kernel functions, establish connections to hypergraph cut, and develop a fast spectral clustering algorithm.
result Our method outperforms existing graph and heuristic modeling methods in clustering performance.
New hypergraph neural network learns variable-sized hyperedges.
problem Learning representations for non-uniform hypergraphs with variable cardinalities.
method Developed a hypergraph neural network exploiting incidence structure.
result Significant improvement in accuracy on real-world hypergraph datasets.
HYVINT generates hypergraphs with intensity-driven incidence formation and variational learning.
problem Challenges in generating hypergraphs with mechanistic interpretation and limited latent space.
method HYVINT uses intensity-driven incidence formation and a lower-bound variational estimator for latent representations.
result HYVINT achieves strong fidelity and novelty on synthetic and real-world hypergraphs.
HLRC offers a new curvature metric for hypergraphs that balances interpretability and efficiency.
problem Challenges in geometric characterization of hypergraphs with higher-order interactions.
method Hypergraph lower Ricci curvature (HLRC) defined in closed form.
result HLRC consistently reveals meaningful higher-order organization in diverse hypergraph datasets.
Unified curvature for hypergraphs from Ollivier-Ricci.
problem Generalizing curvature to hypergraphs.
method Developed ORCHID framework to generalize Ollivier-Ricci curvature to hypergraphs.
result ORCHID curvatures have favorable theoretical properties and are scalable for hypergraph tasks.
HyperSAGE learns node representations in hypergraphs without losing information.
problem Learning node representations in hypergraphs is complex due to higher-order relations.
method Two-level neural message passing strategy for accurate information propagation.
result HyperSAGE outperforms state-of-the-art methods on benchmark datasets.
New topological methods for hypergraph data improve community detection and pattern recognition.
problem Community detection and pattern recognition in hypergraph data.
method Introducing a new topological space structure of hypergraph data, proposing modified nearest neighbors methods.
result Improved methods for community detection and pattern recognition in hypergraph data.
New method uses Ricci curvature for hypergraph clustering, outperforming existing techniques.
problem Community detection in hypergraphs with large hyperedges.
method Extending Ricci flow to hypergraphs by defining edge probability measures and transporting them on the line expansion.
result Enhanced sensitivity to hypergraph structure, especially in large hyperedges.
Generative model for hypergraph clustering improves detection of higher-order structure.
problem Detecting clusters in complex relational systems modeled as hypergraphs.
method Poisson degree-corrected hypergraph stochastic blockmodel (DCHSBM) and Louvain-type algorithms.
result AON hypergraph Louvain algorithm efficiently detects higher-order structure in large hypergraphs.