10 papers
Beyond Structural Symmetries: Linear Mode Connectivity via Neuron Identifiability
Vincent Bürgin, Vincent Bürgin, Daniel Herbst +2
Many striking phenomena in deep learning, such as linear mode connectivity and the structured behavior of training dynamics, are closely tied to parameter symmetries: transformatio…
Neural Networks With Dense Weights Are Not Universal Approximators
Levi Rauchwerger, Stefanie Jegelka, Ron Levie
We investigate the approximation capabilities of dense neural networks. While universal approximation theorems establish that sufficiently large architectures can approximate arbit…
Learning to Approximate Uniform Facility Location via Graph Neural Networks
Chendi Qian, Christopher Morris, Stefanie Jegelka +1
Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based met…
Any-Subgroup Equivariant Networks via Symmetry Breaking
Abhinav Goel, Derek Lim, Hannah Lawrence +2
The inclusion of symmetries as an inductive bias, known as equivariance, often improves generalization on geometric data (e.g. grids, sets, and graphs). However, equivariant archit…
Learning Linear Attention in Polynomial Time
Morris Yau, Ekin Akyürek, Jiayuan Mao +3
Previous research has explored the computational expressivity of Transformer models in simulating Boolean circuits or Turing machines. However, the learnability of these simulators…
Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs
Levi Rauchwerger, Stefanie Jegelka, Ron Levie
We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs, i.e., with node attributes. To this end, we propose pseudometrics over the spac…