PARD generates graphs efficiently and invariantly to node ordering.
problem Graph generation sensitivity to node ordering.
method Integrates autoregressive and diffusion models with a partial order for nodes and edges.
result PARD achieves state-of-the-art performance on molecular and non-molecular datasets.
New algorithm improves PPS for multi-object matching.
problem Efficiently synchronize partial permutations for multi-object matching.
method Proposed CEMP-Partial algorithm for partial permutation synchronization (PPS). Uses sparse matrix operations and nonconvex weighted projected power method.
result Proves CEMP-Partial can exactly classify corrupted and clean partial permutations under adversarial corruption.
PINE embeds graph nodes flexibly, capturing any neighbor dependency.
problem Learning flexible node representations from graph neighborhoods.
method PINE uses partial permutation invariant set functions to capture any possible neighbor dependencies.
result PINE outperforms state-of-the-art methods on various graph learning tasks.
Regularizes RNNs to be invariant to input order.
problem Making RNNs invariant to input order.
method Stochastic regularization to enforce permutation invariance.
result Improves model performance on permutation invariant tasks.
The paper uses belief propagation to analyze rankings and partial orders from partial information.
problem Analyzing rankings and partial orders from incomplete data.
method Continuous spin system and belief propagation algorithm.
result Computes marginal distribution and approximates number of linear extensions.
We consider a simple and overarching representation for permutation-invariant functions of sequences (or multiset functions). Our approach, which we call Janossy pooling, expresses a permutation-invariant function as the average of a permutation-sensitive function applied to all reorderings of the input sequence. This …
A new knot invariant uses permutations to extend Jones polynomials.
problem Extending Jones polynomials to classical and virtual knots and links.
method Colorings by permutations of a finite set to define new knot invariants.
result Established properties and computed polynomials for small cases.
Representations of sets are challenging to learn because operations on sets should be permutation-invariant. To this end, we propose a Permutation-Optimisation module that learns how to permute a set end-to-end. The permuted set can be further processed to learn a permutation-invariant representation of that set, avoid…
A new method learns graph distributions invariant to node ordering.
problem Graphs are hard to model due to node ordering invariance issues.
method Score-based generative modeling with permutation equivariant graph neural network.
result The method achieves better or comparable graph generation results.
4-Legendrian permutation racks can't distinguish knots but recover classical invariants.
problem Distinguishing Legendrian knots using permutation racks.
method Study of 4-Legendrian racks and their effectiveness.
result 4-Legendrian permutation racks cannot distinguish knots but recover classical invariants.
New model preserves graph structure in large datasets.
problem Lack of permutation invariance in graph generation models for large graphs.
method Uses graph embeddings to create a scalable generative model.
result Model maintains structure in large graphs without losing invariance.
Improves modeling of sets with permutation invariant densities.
problem Challenges in calculating trace limit practicality of current methods.
method Proposes an alternative approach to define permutation equivariant transformations with closed form trace.
result Improves both training and final performance.
Improves efficiency and scalability in multi-agent reinforcement learning.
problem Non-stationarity and inefficiency in critic networks due to agent permutations.
method Proposes a permutation invariant critic (PIC) to avoid changes in critic output due to agent permutations.
result Achieves improvements of test episode reward between 15% to 50% on challenging multi-agent particle environment (MPE).
Enhances GNNs by capturing node relationships, outperforming 2-WL test.
problem Inability of conventional GNNs to fully capture node relationships due to permutation invariance.
method Develops permutation-sensitive aggregation mechanism using permutation groups.
result Proves superior expressivity compared to 2-WL test and not less than 3-WL test.
New model learns graph spectra accurately, outperforming existing methods.
problem Graph diffusion models struggle to distinguish certain graph families and their spectra.
method Leveraged random matrix theory to analytically extract spectral properties, introducing Dyson Diffusion Model.
result Dyson Diffusion Model learns graph spectra accurately and outperforms existing models.
The paper examines when real matrix Schubert varieties are minimal submanifolds.
problem When are real matrix Schubert varieties minimal submanifolds?
method The authors establish minimality conditions using geometric arguments and partial permutations.
result The paper identifies specific conditions for real matrix Schubert varieties to be minimal submanifolds.
Permutation invariant network learns Wasserstein metrics.
problem Understanding the space of probability measures and comparing distributions.
method Permutation invariant network mapping samples to a low-dimensional space.
result Network can generalize to compute distances between unseen densities and learn moments.
Generative model for set-valued data using permutation invariant flows.
problem Modeling set-valued data with conditional generative models.
method Conditional generative probabilistic model using continuous normalizing flows with permutation equivariant dynamics.
result Significantly outperforms non-permutation invariant baselines in log likelihood and domain-specific metrics.
Improves full conformal prediction for stochastic non-conformity measures.
problem Inability of existing conditions to guarantee full conformal prediction validity under stochastic settings.
method Introduces a new sufficient condition: Conditional Independence & Permutation Invariance in Distribution.
result Corrects the insufficient condition and provides a new sufficient condition for full conformal prediction validity.
The paper models financial correlation matrices using permutation invariant Gaussian models and predicts market anomalies.
problem Modeling and predicting financial correlation matrices from high-frequency data.
method Constructing permutation invariant Gaussian matrix models with 4 parameters, using graph theory and polynomial functions.
result The permutation invariant Gaussian matrix model predicts the expectation values of cubic and quartic polynomials with strong evidence of fit.
LMC loss barrier decreases to zero with large network width.
problem Understanding the LMC phenomenon in neural networks.
method Fine-grained analysis of LMC for two-layer ReLU networks.
result LMC loss barrier decreases to zero at a rate of O(m^-1/2) for large network width.
We tackle permutation in linear regression with a new inference framework.
problem Statistical investigation of permutation in linear regression models.
method Localization step followed by conditional Monte Carlo test and coefficient inference.
result Valid statistical inference procedures for permutation and regression coefficients.
In this work we study permutation synchronisation for the challenging case of partial permutations, which plays an important role for the problem of matching multiple objects (e.g. images or shapes). The term synchronisation refers to the property that the set of pairwise matchings is cycle-consistent, i.e. in the full…
New tests detect high-order interactions without permutations.
problem Scalability issues in kernel-based tests for high-order interactions.
method Permutation-free high-order tests using V-statistics and cross-centring.
result Tests yield standard normal distribution under null hypothesis.
Researchers formalize PD and PFI to relate them to data generating process.
problem Lack of theory linking PD and PFI to data generating process.
method Formalize PD and PFI as estimators of ground truth estimands, account for model variance with learner-PD and learner-PFI.
result PD and PFI estimates deviate from ground truth due to statistical biases, model variance, and Monte Carlo approximation errors.
Permutation-equivariant neural networks improve auction mechanisms by reducing regret and sample complexity.
problem Designing optimal auction mechanisms that balance revenue and bidders' regret.
method Introduced permutation-equivariant neural networks to auction mechanisms.
result Permutation-equivariant neural networks decrease expected ex-post regret and improve model generalizability.
We study the problem of designing models for machine learning tasks defined on \emph{sets}. In contrast to traditional approach of operating on fixed dimensional vectors, we consider objective functions defined on sets that are invariant to permutations. Such problems are widespread, ranging from estimation of populati…
Variational inference struggles with weight symmetries in neural networks, leading to biased posteriors.
problem Weight space symmetries in neural networks cause multimodal posteriors, challenging variational inference.
method Developed a symmetrization mechanism to create permutation invariant variational posteriors.
result Symmetrized variational posteriors have a better fit to the true posterior and improved predictive performance.
Neural networks learn from ensemble forecasts without considering their order.
problem Improving reliability of probabilistic weather forecasts.
method Permutation-invariant neural networks for postprocessing ensemble forecasts.
result Models achieve state-of-the-art prediction quality in surface temperature and wind gust forecasts.
We introduce a simple permutation equivariant layer for deep learning with set structure.This type of layer, obtained by parameter-sharing, has a simple implementation and linear-time complexity in the size of each set. We use deep permutation-invariant networks to perform point-could classification and MNIST-digit sum…
In regression analysis of multivariate data, it is tacitly assumed that response and predictor variables in each observed response-predictor pair correspond to the same entity or unit. In this paper, we consider the situation of "permuted data" in which this basic correspondence has been lost. Several recent papers hav…
We consider the problem of noisy matrix completion, in which the goal is to reconstruct a structured matrix whose entries are partially observed in noise. Standard approaches to this underdetermined inverse problem are based on assuming that the underlying matrix has low rank, or is well-approximated by a low rank matr…
New model preserves symmetry in multivariate time series, improving performance.
problem Implicit ordering in MTS models violates inherent exchangeability.
method Permutation-equivariant 2D state space model with canonical architecture.
result Eliminates sequential dependency chains and simplifies stability analysis.
New algorithm uses GNNs to optimize rewards in graph-structured data.
problem Optimizing rewards in molecule design with graph-structured data.
method Embedding permutation invariance into GNNs and using GNTK for regret bounds.
result First GNN confidence bound and phased-elimination algorithm with sublinear regret.
Improved Bayesian neural network inference by selectively removing redundant modes.
problem Redundant modes in Bayesian neural network posteriors complicate approximate inference.
method Structured partial stochasticity and deterministic subset selection of weights.
result Improved performance of approximate inference schemes with simplified posterior distribution.
MEM learns set functions from permutation-invariant data.
problem Learning from sets of instances with labels only on sets, not instances.
method Memory-based Exchangeable Model (MEM) with self-attention mechanism.
result Achieved 84.84% accuracy on lung cancer classification.
In this paper, we consider the problem of learning functions over sets, i.e., functions that are invariant to permutations of input set items. Recent approaches of pooling individual element embeddings can necessitate extremely large embedding sizes for challenging functions. We address this challenge by allowing stand…
A formula for triangle area in Deep Sets form.
problem Finding a polynomial formula for triangle area in Deep Sets form.
method Expressing area as a permutation-invariant function and finding a suitable Deep Sets form.
result Explicit polynomial formula for triangle area in Deep Sets form.
Drinfel'd used associators to construct families of universal representations of braid groups. We consider semi-associators (i.e., we drop the pentagonal axiom and impose a normalization in degree one). We show that the process may be reversed, to obtain semi-associators from universal representations of 3-braids. We v…
The introduction of convolutional layers greatly advanced the performance of neural networks on image tasks due to innately capturing a way of encoding and learning translation-invariant operations, matching one of the underlying symmetries of the image domain. In comparison, there are a number of problems in which the…
We propose an end-to-end deep learning learning model for graph classification and representation learning that is invariant to permutation of the nodes of the input graphs. We address the challenge of learning a fixed size graph representation for graphs of varying dimensions through a differentiable node attention po…
In the modern age, rankings data is ubiquitous and it is useful for a variety of applications such as recommender systems, multi-object tracking and preference learning. However, most rankings data encountered in the real world is incomplete, which prevents the direct application of existing modelling tools for complet…
HistNetQ improves quantification tasks by optimizing loss functions and eliminating label requirements.
problem Quantification of class prevalence in bags of examples.
method Permutation-invariant Histograms and deep neural networks.
result HistNetQ outperforms other quantification methods and optimizes custom loss functions.
This paper improves model fusion by training-time neuron alignment, reducing barriers in multi-model fusion.
problem Diverse neuron permutations across different settings hinder model fusion performances.
method Training-time neuron alignment using fixed neuron anchors to reduce training-time permutations.
result Training-time neuron alignment improves fusion of pretrained models and federated learning performances.
We propose new positive definite kernels for permutations. First we introduce a weighted version of the Kendall kernel, which allows to weight unequally the contributions of different item pairs in the permutations depending on their ranks. Like the Kendall kernel, we show that the weighted version is invariant to rela…
This work improves multi-modal generative models by using permutation-invariant neural networks.
problem Improving multi-modal generative models with tighter variational objectives.
method Developed more flexible aggregation schemes based on permutation-invariant neural networks.
result Our variational objective and flexible aggregation models can better approximate the true joint distribution.
New basis for permutation equivariant layers reduces computation costs.
problem Efficiently computing permutation equivariant layers in neural networks.
method Generalized partition algebra basis with low-rank tensors.
result Low-rank tensors enable faster computation compared to orbit basis.
We propose a permutation-invariant loss function designed for the neural networks reconstructing a set of elements without considering the order within its vector representation. Unlike popular approaches for encoding and decoding a set, our work does not rely on a carefully engineered network topology nor by any addit…