Symmetries and discriminability in feedforward network architectures

Area of Science:

• Artificial Intelligence
• Machine Learning
• Graph Theory

Background:

• Neural networks often struggle with tasks requiring invariance to input transformations.
• Efficient training is crucial for complex problems like graph recognition.

Purpose of the Study:

• To investigate the impact of incorporating symmetries into feedforward neural networks (symmetry networks).
• To explore the application of symmetry networks in graph recognition problems, specifically distinguishing isomorphic graphs.
• To determine the theoretical limits of what inputs symmetry networks can distinguish.

Main Methods:

• Developing and analyzing 'symmetry networks' that incorporate input transformation invariances.
• Applying these networks to the problem of graph recognition.
• Formulating a mathematical theorem to characterize input distinguishability by symmetry networks.

Main Results:

• Symmetry networks enable more efficient training for invariance-requiring tasks.
• A theorem is presented that defines when two inputs are distinguishable by a symmetry network.
• A specific network design's ability to distinguish nonisomorphic graphs is linked to the graph reconstruction conjecture.

Conclusions:

• Introducing symmetries into neural networks offers a pathway to more efficient and specialized learning.
• Symmetry networks provide a theoretical framework for understanding input distinguishability in invariant systems.
• The effectiveness of certain symmetry network designs for graph recognition is theoretically bounded by the graph reconstruction conjecture.