Investigating Hopfield networks on graphs: learning invariance and storing orbits

Building on prior work focused on the clique and hyperclique sub-cases, we investigate the capacity of classical Hopfield networks for storing the orbit of a graph under graph isomorphism. Our key observation is that the orbits of many natural classes of graphs can be efficiently stored in a Hopfield network by minimizing a convex objective, called the Energy Flow. Moreover, only a vanishingly small fraction of examples from the orbit are required for the Hopfield network to strictly memorize the entire orbit. We remark that this phenomenon does not appear to hold for modern Hopfield networks.