- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the symmetries of classic Hopfield Networks corresponding to signed permutations of neurons and stored memories. It develops some group theoretic characterizations of these symmetries, including a mechanism for "normalizing" sign flip operations so that they can be safely removed from subsequent analysis. This leads to an algorithm for checking if two Hopfield Network weight matrices are equivalent under these symmetries, based on solving a colored bipartite graph isomorphism problem. The algorithm is still worse than polynomial time because it enumerates row permutations, but is shown empirically to be orders of magnitude faster than a less sophisticated brute force check.
Critical strengths
-
For readers unfamiliar with common neural network symmetries, this paper is a potentially useful and current characterization.
-
As far as I could tell, the mathematics in this paper appears to be technically sound, although some is rather complex and difficult to check.
-
The sign flip normalization trick is potentially novel, and the contributed algorithm exhibits a clear empirical improvement in run time over a brute-force approach.
-
The submission includes some of the code needed reproduce the results, which does not require GPUs or any other prohibitive computational resources.
Critical weaknesses
-
The motivation and significance of this work is not clear. It would make the paper more compelling if it explained a concrete application in which multiple Hopfield weight matrices are present and one needs to determine their symmetry equivalence relationships.
-
I believe the symmetries discussed in this paper, and several of the derived theorems, are already well-studied and common knowledge to researchers in this area. For example, a quick search turned up the paper below that was not cited as related work. Combined with the fact that the contributed algorithm is still worse than polynomial time, it is unclear whether this paper makes a significant new contribution.
Dong J, Xu S, Chen Z, Wu B. On permutation symmetries of Hopfield model neural network. Discrete Dynamics in Nature and Society. 2001;6(2):129-36.
-
The provided code only includes function definitions for the core algorithms. It does not include the code that calls those functions to regenerate the empirical results.
-
Some of the mathematical jargon seems unnecessarily complicated and possibly misleading. For example, the paper uses "attractor degeneracy" to refer to the equivalent dynamics of two symmetric networks, but this term might be easily confused with issues related to spurious attractors.
Questions for authors
-
Theorem 7 only refers to a "target anchor" but immediately after it says "one source anchor suffices." what is the definition/role of the source anchor? is it (1,1)?
-
Can the authors elaborate on concrete motivations for this work? In what context would one have multiple Hopfield weight matrices, and want to determine if they are symmetric?
-
Can the authors expand on what their work contributes beyond what is already known about neural network symmetries, such as the paper cited above?
4 comments
Response to Reviewer K8cC
Responses to Questions
Q1. what is the definition/role of the source anchor? is it (1,1)?
Yes, you have identified the source anchor correctly. We fix in and use its row and column for sign normalization, making all entries in both positive. Their positions in are unknown. In Eq. (21), and map target indices to source indices. The target anchor satisfies , so .
Appendix B.4 gives , so the fixed source anchor corresponds to target anchor . Searching the target positions covers every possible correspondence while keeping one source anchor.
Q2. Can the authors elaborate on concrete motivations for this work? In what context would one have multiple Hopfield weight matrices, and want to determine if they are symmetric?
In our experiments, randomly sampled memory matrices sometimes looked quite different yet gave the same statistics. This led us to ask which changes to the stored patterns preserve the underlying dynamics. That question also arises when choosing memories for a retrieval study. Dong et al. (2001, Section 4), for example, construct a memory set whose patterns are stable and have attraction basins of equal size.
Consider selecting test cases for a comparison of retrieval kernels. One may want a reference set for which the classical Hebbian network stores every intended pattern as a fixed point and has few additional fixed points. Here we count a fixed point as spurious if it is neither a stored pattern nor the negative of one. Each candidate set generates its own weight matrix, and deciding whether to keep it requires checking these properties.
Our classification makes that decision once per memory orbit. The state relabeling maps fixed points bijective, and it also maps the stored patterns together with their negatives onto the corresponding set for the other candidate. The two candidates therefore agree on whether every stored pattern is stable and on how many spurious fixed points remain. Once a representative has been screened, every candidate in its orbit inherits the same decision. A researcher can then select representatives from the qualifying orbits for the subsequent kernel comparison.
Q3. Can the authors expand on what their work contributes beyond what is already known about neural network symmetries, such as the paper cited above?
One theoretical contribution is to describe memory equivalence through a group action and show which dynamical properties are shared by the networks in each orbit. Dong et al. show how a given neuron permutation relates two networks and use symmetry to construct stored patterns with equal basin sizes. The repeated statistics in our experiments led us to ask which memory matrices are related by changes to the stored patterns or neuron coordinates, and what those networks share throughout their dynamics.
Harrison’s work on counting classes of binary matrices suggested formulating this question as a group action on the memory space. Starting from one matrix, we can reorder memories, reverse the sign of a memory, permute neurons, or reverse one neuron’s sign across all memories. All matrices reachable by composing these operations form its orbit. This viewpoint lets us ask which dynamical properties can be determined from a single representative of each orbit. In the relation , the row operations in leave the Hebbian weights unchanged, and the column operations in relabel both the weights and the states.
The dynamical link is exact for the update rule studied here. Let denote the synchronous Hebbian update with spin retention at zero field. For any two memory matrices related as above, Theorems 1 and 6 give for every state . Thus two corresponding initial states follow corresponding trajectories at every update. The same map pairs the attractors and their basins. This is a stronger statement than agreement of the statistics we first observed.
In an exhaustive study, Theorem 5 tells us exactly how many representatives are needed under these four transformations. In a random search, Theorem 7 lets us decide whether a new memory matrix belongs to a class we have already tested and, on a match, recover a transformation that can be checked entry by entry. Lemma 7 explains why the earlier score can be used: each corrupted cue returns to its designated target if and only if the corresponding cue does.
I appreciate the authors' response, but I am planning to leave my score unchanged for the following reasons:
- The authors state they will make some changes, but it appears they did not actually post a revision to the manuscript
- The main motivation they provide is "comparing retrieval rules." However, depending on the structure of a retrieval rule, its properties may depend on the weight matrix itself in a way that is not invariant across the dynamical symmetry equivalence class. Furthermore, the super-polynomial time check still makes it difficult to apply the method in practice for this kind of comparison.
- I still feel that the types of symmetries studied (signed row/column permutations) are common knowledge to the ICLR community and this paper will not provide that community with much new information.
Response to Reviewer K8cC
Dear Reviewer K8cC:
Thank you for following up. We have uploaded the revised manuscript. Section 2 now cites Dong et al. (2001) and briefly explains how their result on neuron permutations relates to ours. We have also added their paper to the reference list. Thank you for bringing this work to our attention.
1.
In our example, we first select memory sets with a desired property under the Hebbian rule and then use those sets to compare retrieval rules. Our result makes the selection easier. One representative per memory orbit suffices to determine which candidates pass the Hebbian screening. The selected cases can then be tested under a different retrieval rule. Reusing that rule’s scores would require checking that its update and scoring procedure respect the same symmetry.
Consider these two memory matrices, each storing five patterns on four neurons:
In each matrix the first four rows contribute to the Gram matrix, and the fifth row is the same. Setting the diagonal to zero gives the same Hebbian weight matrix in both cases:
From any given initial state, the two networks follow exactly the same trajectory. To see what the choice of memories still changes, we enumerated all 16 initial states. For each state , we computed its minimum Hamming distance to a stored row or its negative:
d_{\pm}(V,\Xi)=\min_{1\le a\le 5}\min\bigl\\{d_H(V,\xi_a),\\,d_H(V,-\xi_a)\bigr\\}.
| Minimum distance | Number of states for | Number of states for |
|---|---|---|
| 0 | 8 | 10 |
| 1 | 8 | 6 |
| 2 | 0 | 0 |
The first and fifth rows of are negatives of each other, so its five rows represent four distinct pairs of the form . The five rows of represent five such pairs. This accounts for the eight versus ten states at distance zero. Signed row operations preserve the set of pairs, and signed column operations preserve Hamming distance under the corresponding relabeling of states. The distance histogram is therefore constant within a memory orbit. The two histograms distinguish two memory orbits with exactly the same .
This example explains why we keep track of the memories that generated . Within a memory orbit, Lemma 7 pairs each stored target and its perturbed cues with their counterparts. Whether a cue returns to its designated target is then the same in both networks, which is precisely the outcome we reuse.
2.
Direct enumeration has signed row and column transformations to try. Our general procedure can reject a pair before graph search if its row or column correlation multisets differ in absolute value. The candidate-bank experiment uses a simpler exact test. At a fixed memory count , the number of column types up to sign and the possible signed row actions depend only on . Computing the orbit key therefore takes time per matrix as the neuron count grows. For , we scan the columns and sort just four counts. Two candidates are in the same orbit exactly when those sorted counts agree. At , the median end-to-end speedup over signed-column caching was times across ten banks of 1,000 independently sampled candidates, including the cost of computing the keys.
3.
Even when a conclusion seems obvious, intuition can be wrong. Our proof shows when these symmetries preserve recall outcomes. Once we know the conditions, we can reuse recall results in networks that meet them and know what to check when we change the update rule. The group action gives an exact orbit count, and the recognition algorithm tells us when a new candidate belongs to an orbit we have already evaluated.
Response to Reviewer K8cC
Dear Reviewer K8cC:
Thank you for your comments on sign normalization and for pointing out the missing experiment scripts. Our study began with an observation: randomly drawn memory matrices could look quite different yet give the same statistics. This led us to look for symmetries in the memories themselves. We show that memory matrices related by these symmetries induce the same dynamics up to a relabeling of states, so evaluating one representative gives the recall score for the entire class.
Responses to Weaknesses
W1. About motivation and significance
When choosing test cases for a comparison of retrieval rules, a researcher may seek memory sets whose stored patterns are stable under the Hebbian rule and whose networks have few spurious fixed points. Each candidate set induces a Hebbian weight matrix. Our method identifies candidates in the same memory orbit, where both properties are preserved. Screening one representative therefore suffices for the whole orbit.
W2. About On permutation symmetries of Hopfield model neural network
We had not seen On permutation symmetries of Hopfield model neural network before submitting our paper. We thank the reviewer for drawing our attention to it. Their result shows that a given permutation of the neurons carries the attractors and basins of one network to those of the permuted network. This gives useful context for the neuron-permutation case of our dynamical result. If our paper is accepted, we will cite Dong et al. in the final version and explain this connection.
The complexity question matters because recognizing an equivalent candidate must cost less than evaluating it again to save time. The general procedure examines at most MN target anchors, with graph search that may branch at each one. It returns an exact answer and, on a match, a signed row and column transformation that can be checked entry by entry (Appendix B).
W3. About experimental code
You are right about the missing scripts. We included the core routines and overlooked the scripts that run Section 6. If the paper is accepted, we will make the experiment code public, with the scripts, settings, and commands needed to reproduce Figure 3 and the corresponding tables in Appendix C.
W4. About "attractor degeneracy"
We see how “attractor degeneracy” could suggest a spurious attractor. In Section 1 the term refers to the same attractor structure appearing in networks built from different memory matrices. A spurious attractor is judged against the memories stored within a single network. Definition 1 gives the precise equivalence relation used in the paper.