acceptodds
Under review as a conference paper at ICLR 2027

Graph Memory: Spectral Associative Memory via Dirichlet Energy

Abstract

Dense associative memories have traditionally focused on storing and retrieving vector-valued patterns. Many modern machine learning problems, however, are naturally graph-structured, requiring memory mechanisms for relational patterns, graph diffusion geometries, community structures, and graph-based inductive biases. We propose a spectral dense associative memory for storage and retrieval of graph data, extending the classical vector-valued memories. Retrieval is performed through a log-sum-exp energy induced by Dirichlet energy with spectral norm distances, producing a softmax-weighted average of the stored Laplacians that remains a valid graph Laplacian. We prove exponential storage capacity and exponentially decaying retrieval error. Beyond graph retrieval, we establish theoretical guarantees for spectral quantities central to graph learning, including eigenvalues, eigenspaces, and diffusion operators. Experiments on synthetic graph data, real-world airline network and protein conformation data demonstrate robust graph retrieval while preserving the graph geometry of the data. Our framework provides a new associative memory paradigm for graph-structured data and bridges dense associative memory with modern graph learning and generative AI.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Associative memory, Graph Laplacians, Dirichlet energy, non-Euclidean data

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_f4NgOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Graph-DAM, a dense associative memory framework for storing and retrieving graph-structured patterns. Instead of representing graph Laplacians as ordinary Euclidean vectors, the method introduces a log-sum-exp energy based on operator-norm distances between Laplacians, motivated by the graph Dirichlet energy. A Gibbs-weighted retrieval operator combines stored Laplacians while ensuring that the retrieved result remains a valid weighted graph Laplacian. The authors establish theoretical guarantees for storage capacity, retrieval convergence, and the recovery of spectral properties, including eigenvalues, eigenspaces, and diffusion operators. Experiments on synthetic stochastic block models, airline networks, protein conformations, and wearable sensor data demonstrate improved retrieval performance over Euclidean associative memory baselines.

Critical strengths
  1. I find the extension of dense associative memory to graph-structured patterns interesting. Rather than treating graph Laplacians simply as flattened vectors, Graph-DAM defines similarity through operator-norm distances that have a clear interpretation in terms of graph Dirichlet energy. In particular, this distance characterizes the maximum difference between the Dirichlet energies of two graphs over unit graph signals. I think this provides a reasonable mathematical motivation for comparing graphs through their underlying operators. Another useful property is that the retrieval operator forms a convex combination of stored Laplacians, so the retrieved result remains a valid weighted graph Laplacian. These choices give the proposed framework a coherent formulation.

  2. The theoretical analysis is a notable strength of this work. The authors do not stop at introducing a graph-based retrieval rule but also investigate its storage and recovery properties. Theorem 3.1 establishes exponential storage capacity under a specified random weighted-graph model, while Theorems 3.2 and 3.3 provide convergence and retrieval-error guarantees. I also appreciate the additional analysis of eigenvalues, eigenspaces, and diffusion operators in Theorem 3.4. These quantities are directly relevant to spectral graph learning, so extending the analysis beyond simple retrieval accuracy is meaningful. Although the assumptions behind these guarantees need to be considered carefully, the theoretical development is relatively comprehensive.

  3. I also appreciate the experimental visualizations and the use of different application settings. The synthetic SBM experiment examines whether retrieved graphs preserve community-related spectral properties, while the airline and protein experiments demonstrate retrieval on more concrete relational data. Additional experiments involving wearable sensors further broaden the evaluation. Figures 1–4 are particularly helpful, as they illustrate the energy landscape, retrieval accuracy, and structural differences between correctly and incorrectly retrieved memories. I find the comparison of Fiedler vectors in Figure 2 especially informative, since it connects retrieval behavior to the spectral properties emphasized by the method. Overall, the results provide encouraging initial evidence that the proposed distance measure can be useful for graph retrieval.

Critical weaknesses
  1. My main concern is that the experiments do not sufficiently establish the additional value of the associative memory mechanism itself. Graph-DAM measures the operator-norm distance between a query Laplacian and each stored Laplacian, then uses these distances to compute softmax weights for retrieval. As the inverse temperature increases, the weights become increasingly concentrated on the nearest stored graph. This raises a natural question: how much of the improvement actually comes from the associative memory mechanism, rather than simply using a more suitable graph distance? The current Eu-DAM baseline uses Euclidean inner-product similarity, so the comparison changes both the similarity measure and the retrieval formulation. I think a direct nearest-neighbor baseline using the same operator-norm distance is particularly important. Comparisons with Frobenius-distance nearest-neighbor retrieval and Frobenius-distance softmax aggregation would also help isolate the effects of the distance measure and the retrieval dynamics. Without these controls, I find it difficult to determine what the proposed associative memory framework offers beyond spectral graph similarity-based retrieval.

  2. The discussion of closely related work could be more complete. The paper reviews classical and modern dense associative memories, but I think several relevant studies on graph-based associative learning and graph similarity deserve attention. Modern Hopfield Networks for Graph Embedding (Liang et al., 2022, https://doi.org/10.3389/fdata.2022.1044709) already explores the use of associative memory mechanisms for graph-structured information, although its focus is different from whole-graph retrieval. DeltaCon: A Principled Massive-Graph Similarity Function (Koutra et al., SDM 2013, https://doi.org/10.1137/1.9781611972832.18) is especially relevant because it studies graph similarity when node correspondence is known, which is also a central assumption of Graph-DAM. NetLSD: Hearing the Shape of a Graph (Tsitsulin et al., KDD 2018, https://doi.org/10.1145/3219819.3219991) provides another useful perspective on comparing graphs through Laplacian spectral information. I am not suggesting that these methods are equivalent to Graph-DAM. However, discussing their relationship to the proposed formulation would help clarify its position within existing research and motivate more informative comparison baselines.

  3. I think the practical scope of the theoretical guarantees deserves more discussion. The exponential storage-capacity result in Theorem 3.1 is mathematically interesting, but it is established for independently sampled dense weighted graphs with a common aligned node set and uniformly distributed edge weights. Real graph collections often contain sparse structures, strong correlations, and considerably smaller differences between stored memories. It is therefore unclear how well the theoretical capacity result reflects these practical settings. I also noticed that the convergence analysis distinguishes between the original stored Laplacian and a nearby fixed point of the retrieval operator. Theorem 3.3 provides an additional bound on the error relative to the stored memory, which is useful, but I think the relationship between these guarantees and the spectral recovery results could be explained more directly. In particular, the authors should clarify which properties are recovered with respect to the original graph and which are guaranteed relative to the retrieval fixed point. This would make the theoretical contribution easier to interpret without weakening its mathematical results.

  4. The experimental evaluation could be strengthened to better demonstrate the practical usefulness of Graph-DAM. Although several datasets are included, the experiments mainly examine whether a partially corrupted query can retrieve its corresponding graph from a relatively small collection of stored memories. For example, the synthetic SBM experiment stores 50 graphs with 120 nodes each, while the airline experiment involves only 11 networks with 45 nodes. These settings are useful for validating the proposed formulation, but they provide limited evidence of scalability to larger and more challenging graph-memory tasks. I would particularly like to see how performance changes as the number of stored memories increases and as the stored graphs become more structurally similar. Another important limitation is the requirement that all graphs share the same aligned node set. I appreciate that the authors acknowledge this assumption, but it excludes many common graph retrieval settings involving different graph sizes or unknown node correspondence. A clearer discussion of the intended application scenarios, together with additional memory-size or corruption-sensitivity analysis, would make the practical contribution more convincing.

  5. The computational cost and sensitivity to the inverse temperature parameter could be analyzed more thoroughly. Graph-DAM requires computing operator-norm distances between the query Laplacian and all stored Laplacians, potentially over multiple retrieval iterations. This could become computationally expensive as graph size and memory capacity increase, yet the experimental section focuses primarily on retrieval accuracy rather than runtime or memory usage. I would appreciate a comparison of computational cost against simpler graph-distance retrieval methods, especially the operator-norm nearest-neighbor baseline mentioned above. Another issue is the strong dependence on the inverse temperature parameter. In several experiments, retrieval accuracy changes sharply as this parameter increases, but the paper does not provide much practical guidance on choosing it for an unseen dataset. The theoretical sufficient conditions are useful, although they do not directly provide a general model-selection procedure. Additional sensitivity analysis, including the number of retrieval iterations, would help establish how robust and practical the proposed framework is.

Questions for authors

Please see Weaknesses 1–5 above. I would particularly appreciate a comparison with direct nearest-neighbor retrieval using the same operator-norm distance, since this would help clarify what the associative memory mechanism contributes beyond graph similarity measurement. I would also welcome further discussion of how the theoretical guarantees relate to realistic graph collections and how the retrieval fixed points relate to the original stored memories. Finally, additional evidence on scalability, inverse-temperature sensitivity, and computational cost would help establish the practical value of the proposed framework.

3 comments

We thank the reviewer for the valuable comments and hope our responses address the concerns and reconsideration of a score increase if so. Due to the space limit, the rest of the responses to other Weakness/Questions are in the separated comments.

Weaknesses

Weakness 1: The experiments do not sufficiently establish the additional value of the associative memory mechanism itself. How does Graph-DAM compare against direct nearest-neighbor retrieval using the same operator-norm distance? How does it compare with Frobenius-distance nearest-neighbor retrieval and Frobenius-distance softmax aggregation?

  1. Regarding comparison with NN retrieval

A key distinction is that although Graph-DAM reduces to nearest-neighbor (NN) retrieval as (β→∞\beta\rightarrow\infty), this limiting behavior does NOT characterize the full associative memory mechanism and the difference is fundamental to associative memories.

In our retrieval experiments, queries are masked or corrupted versions of stored ground-truth graphs. Thus, NN and Graph-DAM produce similar results at sufficiently large β\beta since both aim to recover an existing memory. However, this equivalence does not extend to queries that do NOT coincide with any stored memory. When the desired output lies between multiple stored memories, NN can only select one existing candidate but Graph-DAM can combine multiple memories through its attention-like softmax weights to produce an interpolated Laplacian, and the resulting convex combination remains a valid graph Laplacian.

More fundamentally, modern associative memory extends beyond storing and retrieving existing patterns. Recent work, Dense Associative Memory with Epanechnikov Energy (Hoover et al., NeurIPS 2025), demonstrates that DAM can simultaneously preserve stored memories and generate novel emergent memories as additional local minima. Besides generation, DAM provides an explicit energy landscape which enables energy-based computation and interpretation through memory interactions and attraction basins. Neither of these two attractive properties can be realized through NN retrieval.

Experimental setup: In our protein conformation dataset, we construct different queries from stored graph Laplacians: Lq=αLi+(1−α)LjL_q=\alpha L_i+(1-\alpha)L_j. For α=0.5\alpha=0.5, we compare Graph-DAM (one update and iterative retrieval) against nearest-neighbor retrieval (NN), measuring the mean relative operator error across different inverse temperatures.

Inverse temperatureGraph-DAMGraph-DAM (with only one update)NN
0.10.3770.3790.309
10.3650.3840.309
100.2490.3940.309
200.2370.3090.309
500.2530.3070.309
1000.2760.3090.309
10000.3090.3090.309

Graph-DAM achieves a lower mean relative operator error than Op-NN (for example, 0.237 vs. 0.309), demonstrating its advantage in retrieving interpolated graph structures beyond hard nearest-neighbor selection.

  1. Regarding Frobenius-based alternatives

Frobenius distance between Laplacians is exactly Euclidean distance between their vectorized representations. Its retrieval is therefore closely related (and very similar) to our Eu-DAM baseline, which fails to capture/preserve the graph structure. The squared Frobenius distance decomposes into two norm terms and an inner product term, making the corresponding retrieval mechanisms closely related since the only discrepancy term of these three is the inner product one and it coincides with the Eu-DAM.

More importantly, the two norms exhibit different sensitivities to noise. For a dense perturbation ΔL\Delta L affecting many independent directions, the Frobenius norm accumulates the perturbations across all these directions and can become substantially larger than the operator norm.

\leq \Vert \Delta L\Vert_F \leq \sqrt{\operatorname{rank}(\Delta L)} \Vert \Delta L\Vert_{\mathrm{op}}.$$ For high-rank perturbations, the Frobenius discrepancy can be amplified by a factor of up to $O(\sqrt n)$, making Frobenius-based retrieval more sensitive to distributed noise. **Experimental setup:** In our protein conformation dataset, we evaluate retrieval accuracy under three noise factors (0.25, 0.5, and 1.0) across a range of normalized inverse temperatures. | Noise factor | Graph-DAM β=4 | Fro-DAM β=4 | Graph-DAM β=6 | Fro-DAM β=6 | Graph-DAM β=8 | Fro-DAM β=8 | |:---:|---:|---:|---:|---:|---:|---:| | 0.25 | **100%** | 50% | **100%** | 82% | **100%** | 93% | | 0.50 | **96%** | 4% | **100%** | 20% | **100%** | 28% | | 1.00 | **9%** | 4% | **80%** | 4% | **91%** | 4% | The results show that Graph-DAM consistently outperforms Fro-DAM at matched inverse temperatures, with higher advantage under stronger noise (91% versus 4% retrieval accuracy at noise factor 1.0 and normalized $\beta=8$).

Weakness 2: The related-work discussion needs more detail. How does Graph-DAM relate to Modern Hopfield Networks for Graph Embedding (Liang et al., 2022), DeltaCon (Koutra et al., 2013), and NetLSD (Tsitsulin et al., 2018), and how do they differ from our formulation?

We thank the reviewer for pointing out these relevant studies. We agree that they provide important complementary perspectives on graph representation, similarity and associative learning that are related to our paper. We first clarify that these works address different objectives from ours: Liang et al. study node-level associative representation learning, while DeltaCon and NetLSD develop graph similarity measures. In contrast, Graph-DAM focuses on energy-based associative storage and retrieval of entire graph structures. The key design (and hence its most attractive property) is to integrate graph similarity into a retrieval dynamics with explicit, computable and interpretable energy landscape. In the framework of associative memory, it requires and offers more than just memorization or retrieval (Please see our response to Question 1 above; the third paragraph in 1. Regarding comparsion with NN retrieval).

More specifically, Liang et al. (2022) apply modern Hopfield networks to node-level representation learning and masked-node recovery while Graph-DAM stores and retrieves entire graph Laplacians. DeltaCon (Koutra et al., 2013) measures graph similarity through node-affinity matrices, but does not provide an associative-memory retrieval mechanism. NetLSD (Tsitsulin et al., 2018) compares graphs through compact Laplacian spectral signatures, and Graph-DAM directly operates on Laplacian operators and preserves their Dirichlet-energy geometry during retrieval.

We acknowledge that these methods offer valuable and complementary approaches to graph representation and comparison. We will incorporate these works into the related-work discussion to better clarify the scope and positioning of Graph-DAM.

Weakness 3: How applicable are Theorem 3.1's assumptions to real graphs? How do retrieval fixed points relate to stored memories, and which spectral properties are recovered?

We thank the reviewer for raising this important point. First, we emphasize that the i.i.d. assumption is a standard starting point in the DAM literature for theoretically characterizing storage capacity. Achieving exponential capacity even for independently sampled memories establishes the potential scalability of the associative memory mechanism. For example, Lucibello and Mézard (2024) establish exponential capacity for modern DAMs under independently sampled Gaussian and spherical patterns. However, we also acknowledge that practical data like images deviate considerably from this setup in several ways, as the reviewer pointed out, sparse connectivity, strong structural correlations, and small differences between stored graphs. While these factors may quantitatively affect memory separation, retrieval capacity, and attraction basin sizes, they do not fundamentally change the storage capability (and other behaviors) of associative memories. Our empirical studies of correlated patterns have shown that DAMs can retain substantial storage capacity even beyond the idealized i.i.d. setting (such as our protein conformation experiment). Rigorous theories under extension to non-i.i.d. are worth exploring and we leave it as future work.

Regarding the relationship between retrieval fixed points and stored memories, it is useful to distinguish two regimes in modern DAMs: memorization and generalization. In the memorization regime, retrieval converges to a fixed point Li⋆L_i^\star within the attraction basin of a particular stored memory LiL_i. Although Li⋆L_i^\star need not be exactly identical to LiL_i, Theorem 3.3 establishes that they are exponentially close. Our spectral guarantees in Theorem 3.4 are therefore for this corresponding stored memory LiL_i, including recovery of Laplacian eigenvalues, eigenspace, and graph diffusion operators.

Beyond memorization, DAMs can also exhibit a generalization regime, where in our case for example the combination of multiple stored Laplacians leads to a novel Laplacian staying from all stored ones. In this case, it also corresponds to a local minima of the energy landscape, known as emergent memories. Unlike memorization fixed points, these emergent memories do not correspond to any individual stored patterns. In this generalization regime, the retrieval fixed point itself corresponds to such a novel memory, and its spectral properties would characterize the eigenvalues, eigenspaces, and diffusion behavior of this newly emerged graph. While our current theoretical guarantees focus on the memorization regime, extending the spectral analysis to such emergent graph memories is an interesting direction for future work. We will make this relationship/distinction explicit in the revised manuscript.

Weakness 4: The experiments need stronger practical validation. How does performance change as memory size and the graph similarity increase? What limitations arise from the common aligned node-set assumption, and which applications are intended?

Regarding the common aligned node-set assumption, we acknowledge that it limits the current formulation from directly handling graphs with different numbers of nodes or unknown node correspondences. This assumption is necessary for our operator-based formulation since comparing two graph Laplacians through their operator-norm difference requires them to act on the same underlying node-signal space. This also makes sense that in many downstream tasks, graphs need to interact with signals on a common space. In practice, this setting is relevant to many practical applications where graphs describe different structures or states over a shared set of entities (such as network data and this is one of our motivation). For example, in our experiments, airline networks, protein conformations and wearable-sensor data are all of this type.

As a possible extension, graphs of different sizes could be embedded into a common-dimensional space through zero-padding of their Laplacian matrices, equivalently treating additional nodes as isolated vertices. Extending the framework to graphs with different sizes is an interesting direction for future work.

Experimental setup: In our protein conformation dataset, we additionlly change the memory banks to the size of 50, 100, 500, 1,000 and 5000 graphs with fixing the normalized inverse temperature at βn=100\beta_n=100. For 5000 graphs, we employ parallel exact symmetric eigensolvers for fast computation (Please also refer to our computational cost in Response to Weakness 5 below).

Number of stored memoriesCorrect queriesRetrieval accuracy
5047/5094%
10046/5092%
50044/5088%
1,00043/5086%
5,00042/5084%

Conclusion: Graph-DAM still retains considerable good retrieval accuracy when the memory bank increases, demonstrating graceful performance degradation and promising scalability to larger graph-memory collections. However, we also wanna point out that as our Theorem 3.1 showed, increasing the number of memory will lead to a worse separability and worse stability of the basin of stored memories.

Weakness 5: Analyze computational cost and inverse-temperature sensitivity. How do runtime and memory scale with graph size and memory capacity? How should inverse temperature be selected for unseen datasets, and how sensitive is retrieval to iteration count?

Computational complexity. At each retrieval step, Graph-DAM computes the operator-norm discrepancy between the query Laplacian and each of the NN stored Laplacians. In the worst-case dense setting, exact eigendecomposition requires O(n3)O(n^3) operations per comparison, resulting in O(Nn3)O(Nn^3) time per retrieval step. Storing all dense Laplacians requires O(Nn2)O(Nn^2) memory. However, exact eigendecomposition is not necessary in practice. Since Laplacian differences are symmetric, their operator norms can be efficiently approximated using iterative eigensolvers such as Lanczos. We will add a remark discussing these complexity bounds and practical acceleration strategies.

Inverse-temperature sensitivity. We emphasize that β\beta is inherently task-dependent as it controls the trade-off between memorization and generalization (as in our response to Weakness 3 above). A larger β\beta favors selective retrieval of existing memories (i.e. memorization) while a smaller or moderate β\beta allows multiple memory aggregation and interpolation (i.e. generalization). However, an appropriate trade-off depends on the downstream objective and its loss function. For example, medical record retrieval generally prioritizes identifying an existing disease pattern rather than generating an unsupported novel one when we select β\beta. In contrast, AI for PDE discovery may benefit from exploring new patterns to identify previously unseen local laws. In general, we recommend selecting it using validation performance under the target task's objective.

Number of retrieval iterations. This issue does not uniquely but broadly exist in DAM literature. The sensitivity to iteration count depends on the separation between stored memories and the contraction rate within the corresponding attraction basin (see Theorem 3.2). And actually, we already showed in our paper that a single update can already achieve exponentially small retrieval error for sufficiently well-separated memories while less separated patterns may require additional updates. In this case, it is not very sensitive to the number of iteration used, although more iterations may be necessary for closely spaced memories or queries near basin boundaries. Beyond convergence, additional iterations do not meaningfully change the retrieved graph.

Reviewer_dTAhOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

this paper proposes a spectral dense associative memory for storage and retrieval of graph data, extending the classical vector-valued memories. Experiments on synthetic graph data, real-world airline network, protein conformation data and wearable sensor data demonstrate robust graph retrieval while preserving the graph geometry of the data.

Critical strengths
  1. The paper provides several theoretical guarantees, including exponential storage capacity, contraction of the retrieval operator within attraction basins, and exponentially decreasing retrieval error.
  2. The reported results indicate that operator-norm similarity can provide useful graph retrieval behavior across different applications.
Critical weaknesses

The proposed retrieval operator computes softmax weights using the negative squared operator-norm distance between the query Laplacian and each stored Laplacian. As the inverse temperature approaches infinity, the weights concentrate on the nearest stored graph under this distance. Consequently, the proposed method essentially approaches nearest-neighbor retrieval in the space of graph Laplacians. This raises an important question: how much of the observed performance improvement comes from the associative-memory mechanism itself, rather than from using operator-norm distance as a graph similarity measure? The experiments compare Graph-DAM against Euclidean associative memory baselines, but do not include a direct nearest-neighbor baseline using the same operator-norm distance.

Questions for authors
  1. How does Graph-DAM compare against direct nearest-neighbor retrieval using the same squared operator-norm distance? Does iterating the retrieval operator provide improvements beyond selecting the nearest stored graph?
  2. Can the authors compare against a Frobenius-distance-based associative memory, rather than relying only on Euclidean inner-product similarity? How much of the reported improvement remains after this change?
2 comments

We thank the reviewer for the valuable comments and hope our responses address the concerns and reconsideration of a score increase if so.

Response to Questions

Question 1: How does Graph-DAM compare against direct nearest-neighbor retrieval using the same squared operator-norm distance? Does iterating the retrieval operator provide improvements beyond selecting the nearest stored graph?

Although Graph-DAM approaches nearest-neighbor (NN) retrieval as β→∞\beta\rightarrow\infty, this limiting behavior does not characterize its full associative-memory mechanism. In our original retrieval experiments, the ground-truth graph is an existing stored memory, while the query is obtained by masking or corrupting it. Thus, Graph-DAM and NN naturally behave similarly at sufficiently large β\beta, since both aim to recover an existing memory. However, this equivalence does not hold when the target is not among the stored memories. For example, when the desired graph lies between multiple memories, NN can only select one existing candidate, whereas Graph-DAM combines multiple memories through its attention-like Gibbs weights to produce an interpolated Laplacian. The convex combination remains a valid graph Laplacian.

More fundamentally, modern associative memory extends beyond storing and retrieving existing patterns. [1] demonstrated that DAMs can preserve stored memories while also generating novel emergent memories as additional local minima. Incorporating Graph-DAM into such generative AM frameworks could potentially enable graph generation. Moreover, its explicit energy landscape supports energy-based computation and interpretation through memory interactions and attraction basins, capabilities not provided by NN retrieval.

Experimental setup: On the protein conformation dataset, we construct interpolation queries from stored graph Laplacians: Lq=αLi+(1−α)LjL_q=\alpha L_i+(1-\alpha)L_j, with α=0.5\alpha=0.5. We compare Graph-DAM (one update and iterative retrieval) against operator-norm nearest-neighbor retrieval (Op-NN), measuring mean relative operator error across inverse temperatures.

Normalized inverse temperatureGraph-DAM (iterative)Graph-DAM (one update)Op-NN
0.10.3770.3790.309
10.3650.3840.309
100.2490.3940.309
200.2370.3090.309
500.2530.3070.309
1000.2760.3090.309
10000.3090.3090.309

Graph-DAM achieves a lower mean relative operator error than Op-NN (0.237 vs. 0.309, a 23% reduction), demonstrating the benefit of associative retrieval for interpolated graph structures beyond hard nearest-neighbor selection.

Question 2: Can the authors compare against a Frobenius-distance-based associative memory, rather than relying only on Euclidean inner-product similarity? How much of the reported improvement remains?

Frobenius distance between two Laplacians is exactly Euclidean distance between their vectorized representations, making Frobenius-based retrieval closely related to our Eu-DAM baseline. In particular, the squared Frobenius distance decomposes into two norm terms and an inner-product term, linking it to Euclidean inner-product similarity, because the only discrepancy term among them is the inner product, which is exactly Eu-DAM.

More importantly, the two norms exhibit different sensitivities to noise. For dense perturbations ΔL\Delta L, the Frobenius norm accumulates contributions across directions and can substantially exceed the operator norm. In particular,

\leq \Vert \Delta L\Vert_F \leq \sqrt{\operatorname{rank}(\Delta L)} \Vert \Delta L\Vert_{\mathrm{op}}.$$ For high-rank perturbations, it can be amplified by up to $O(\sqrt n)$, making Frobenius retrieval more sensitive to distributed noise. The operator norm instead measures maximum Dirichlet-energy distortion over unit-norm signals. **Experimental setup:** On the protein conformation dataset, we evaluate retrieval accuracy under three distributed-noise factors (0.25, 0.5, and 1.0), comparing Graph-DAM and Fro-DAM at matched normalized inverse temperatures. | Noise factor | Graph-DAM $\beta_n=4$ | Fro-DAM $\beta_n=4$ | Graph-DAM $\beta_n=6$ | Fro-DAM $\beta_n=6$ | Graph-DAM $\beta_n=8$ | Fro-DAM $\beta_n=8$ | |:---:|---:|---:|---:|---:|---:|---:| | 0.25 | **100%** | 50% | **100%** | 82% | **100%** | 93% | | 0.50 | **96%** | 4% | **100%** | 20% | **100%** | 28% | | 1.00 | 9% | 4% | **80%** | 4% | **91%** | 4% | Graph-DAM consistently outperforms Fro-DAM at matched inverse temperatures, with the largest advantage under strong noise: **91% vs. 4%** accuracy at noise factor 1.0 and normalized $\beta_n=8$. [1] Benjamin Hoover, Zhaoyang Shi, Krishnakumar Balasubramanian, Dmitry Krotov, and Parikshit Ram, "Dense Associative Memory with Epanechnikov Energy," NeurIPS 2025.

Dear Reviewer dTAh,

Sorry to bother you, but given that we are close to the discussion deadline we wanted to reach out and ask if you could please let us know whether these additions and clarifications (both the response and the revised paper with major changes in blue according to your comments) address your concerns? Thank you for your time!

Best, Authors

Reviewer_4iGXOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper extends dense associative models (DAM) to graph-structured data. By combining the general log-sum-exp energy formula for vector-valued data with the Dirichlet energy defined on graphs, this paper proposes Graph DAM to complete associative search on graphs.

Critical strengths
  1. The presentation is very clear and well structured, making it very easy to understand.
  2. The proposed method directly follows the motivations and related work, and the demonstrated experiments show clear advantages over the compared alternatives in search.
Critical weaknesses
  1. In Eq. (2), you drop the signal f by using the operator norm and instead focus on the worst possible signal by taking the supremum over all f. Do the search results defined this way generalize to all possible f?
  2. Candidates are needed or must be constructed before the search for this problem. Instead, graph searching can be understood as a conditional multimodal generation problem: given signal f, what is the most likely G among all possible candidates, rather than from a given set? Do you think graph search can achieve something similar to text-conditioned image generation? Or can you explain why this associative search is still feasible for real-world problems today?
  3. The computation in Step 4 of Algorithm 1 should be demanding. Report the computational cost in terms of storage and time as graph size N increases.
  4. Still, regarding the worst possible signal used in Graph-DAM, it might take into account some signal f′ that the underlying graph does not care about at all. So, I’m wondering how the method works differently for homophilic and heterophilic graphs. Also, regarding your introduction, how does the proposal work with different degrees of incompletion or noise?
Questions for authors
  1. Sections 2 and 4 are helpful, but there are different ways of constructing a matrix or vector from G. Alternatively, you may adopt the sparse storage format and store the coordinates of the relations; the resulting format is still a 2-by-|E| matrix. In this case, how is it different from images, given that both are vector-valued patterns? Alternatively, you might say that it is hard to construct high-level features from the coordinate format of a relational graph compared with images. It would be worthwhile to compare and discuss different ways of representing graph structures other than G.
  2. [Minor] Move notations to Sec. 2.
5 comments

We thank the reviewer for the valuable comments and hope our responses address the concerns and reconsideration of a score increase if so.

Weaknesses

Weakness 1: Does removing the signal ff through the operator norm make the search results generalize to all possible signals?

Our goal is to retrieve the graph structure itself, not a graph optimized for one signal, since downstream tasks and signals may vary. A signal-dependent comparison may overlook structural differences invisible to the chosen signal. The operator norm instead measures the maximum Dirichlet-energy discrepancy over all unit-norm signals. We acknowledge that a signal-adaptive energy could be more suitable when the target signal or its distribution is known or estimable; we leave this task-specific extension to future work.

Weakness 2: Why retrieve from a given candidate set rather than perform conditional graph generation?

A fundamental objective of associative memory (AM) is to retrieve stored patterns from partial or corrupted cues, unlike conditional generation, which synthesizes potentially unseen structures. For example, given a partially observed airline network, our goal is to recover the actual network of that carrier, not generate a different but plausible network. This distinction matters because associative retrieval prioritizes faithful recovery of observed structures while generation may produce a plausible but historically incorrect network. Conditional graph generation is valuable for generalizing beyond stored candidates. Recent modern AM work [1] also demonstrates generation through novel emergent memories. Attractively, its explicit energy landscape also offers interpretability and supports energy-based computation which conditional generation does not offer. We leave this extension to future work.

Weakness 3: Computational and storage costs of Step 4 as graph size increases.

For MM stored graphs of nn nodes, dense storage costs O(Mn2)O(Mn^2). Exact eigendecomposition costs O(n3)O(n^3) per comparison, or O(Mn3)O(Mn^3) per retrieval step. In practice, exact eigendecomposition is unnecessary: iterative eigensolvers such as Lanczos can efficiently approximate the largest-magnitude eigenvalues of symmetric Laplacian differences. For sparse graphs, Lanczos can further exploit sparse matrix-vector products to reduce practical computational costs. We will add these bounds and acceleration approaches.

Weakness 4: Effects of worst-case signals, homophily/heterophily, and different levels of incompleteness or noise.

Graph-DAM does not assume homophily or restrict signals to be smooth: it retrieves graph structures independently of a particular signal, considering all unit-norm signal directions. If the signal distribution is known or estimable, a signal-adaptive or distribution-weighted variant could better target task-relevant directions.

For incompleteness and noise, retrieval depends on the operator-norm perturbation between observed and underlying Laplacians relative to their separation from competing memories. Retrieval remains reliable while this perturbation is smaller than that separation; greater corruption can make memories harder to distinguish. Theorem 3.2 provides the corresponding robustness guarantee, and our experiments demonstrate retrieval under 20% random edge deletion.

Questions

Question 1: Alternative graph representations, including edge-coordinate matrices, and how they differ from image representations.

A 2×∣E∣2\times |E| edge-coordinate matrix is indeed a vector-valued representation. However, image pixels occupy a fixed spatial grid with consistent coordinate correspondence and meaningful local neighborhoods, enabling hierarchical feature extraction by standard vision architectures. In contrast, an edge-coordinate matrix is an unordered collection of relations whose columns have no intrinsic ordering and whose dimension depends on ∣E∣|E|. High-level properties (e.g., communities, diffusion, and spectral organization) arise from edge interactions, not raw edge coordinates.

Our choice of the Laplacian is deliberate: it is well established in modern graph learning, underlying graph convolution through graph Fourier bases and spectral filters, and providing spectral positional encodings in graph Transformers, as discussed in the Introduction. Other representations suit specific objectives: learned GNN embeddings capture task-specific features, while edge coordinates offer compact sparse storage and may enable sparse associative memories. We leave exploring these alternatives to future work.

Question 2 (Minor): Move notations to Section 2.

Thank you for the suggestion. We have moved the notations to Section 2 and highlighted the changes in blue.

[1] Benjamin Hoover, Zhaoyang Shi, Krishnakumar Balasubramanian, Dmitry Krotov, and Parikshit Ram, "Dense Associative Memory with Epanechnikov Energy," NeurIPS 2025.

Dear Authors,

Thank you for the responses. W1, W2 and Q1 are addressed, while W3 and W4 are only partially addressed. For W3, I asked for the storage and time cost as the graph size increases, and the response gives complexity bounds without measurements, which I also could not find in the revised PDF. And for W4, the response does not show how the method behaves on homophilic versus heterophilic graphs or at different levels of incompleteness.

I will therefore keep my current score.

Best,

Reviewer 4iGX

We again thank the reviewer for their time and efforts in reviewing our work and the valuable feedback. We are happy to see W1, W2 and Q1 are addressed. Below, we provide additional response to partially addressed W3 and W4.

W3: We now add experiments for storage and time cost varying the graph size in our protein conformation data.

Experimental setup. We focus on our NMR protein conformation data experiment across 11 graph sizes, ranging from 16 to 256 residue nodes. Here, we fix the normalized inverse temperature at 100 and report median retrieval time over three repetitions after warmup. For graphs with more than 100 nodes, we additionally evaluate it with a fast eigenvalue algorithm, say Lanczos [2], with tolerance 10−610^{-6}.

NodesMemory-bank storage (MiB)Exact solver (ms/query)Lanczos (ms/query)
160.0491.38—
320.1953.26—
480.43911.02—
640.78118.69—
801.22140.91—
961.75829.48—
1283.12553.1857.31
1604.88383.7664.98
1927.031124.0169.97
2249.570255.32121.95
25612.500232.6196.29

Here, storage measures the dense float64 memory bank, excluding temporary working memory. The measured storage follows O(Mn2)O(Mn^2) exactly: with M fixed, doubling the node count from 128 to 256 increases storage fourfold, from 3.125 to 12.500 MiB. Exact-solver runtime generally increases with graph size, consistent with the O(Mn3)O(Mn^3) per-update bound.

We also include the theoretical bound and this additional experiment in Section C.3 in Appendix.

W4: Graph-DAM regarding graph homophily/heterophily and different levels of graph incompleteness.

Homophilic versus heterophilic graphs. Graph-DAM is designed for graph-structure retrieval rather than downstream node-label prediction since its current formulation considers all unit-norm signal directions. We acknowledge the reviewer's concern that the worst-case signal direction may not necessarily be relevant to a particular graph-learning task. For example, homophilic tasks may primarily involve low-frequency or graph-smooth signals, whereas heterophilic tasks can involve substantially different spectral characteristics. Thus, the worst-case guarantee can be conservative when the actual task-relevant signal distribution occupies only a restricted portion of the signal space. This is also the motivation of our Graph-DAM as in many tasks, signals are NOT unknown.

However, for homophilic and heterophilic graph families that may exhibit different spectral structures and memory-separation margins, it can affect their practical retrieval performance. Under this case, it is potentially an interesting idea that one can first estimate the signal (if unknown) and incorporate graph filters with our operator norm energy for an adaptive associative memory system. This is an interesting extension and deserves future efforts. We have added a remark to clarify this issue as in Remark 2.1 in blue.

Different levels of graph incompleteness and noise. The robustness of Graph-DAM is characterized by the perturbation of the observed graph Laplacian relative to the separation between the underlying graph memory and competing memories.

Let LL and L~\widetilde L denote the underlying and observed graph Laplacians, respectively. The relevant perturbation is

ε=∣L~−L∣op.\varepsilon=\\|\widetilde L-L\\|_{\mathrm{op}}.

Theorems 3.1 and 3.2 established that retrieval remains reliable provided that this perturbation is sufficiently small relative to the memory-separation margin. As incompleteness or noise increases, the perturbation grows, eventually making competing memories harder to distinguish (this is exactly why there is a notion of memory capacity as stated in our paper). For example, our existing experiments demonstrate successful retrieval under 20% random edge deletion. We have added a remark to clarify this issue as in Remark 3.3.

We appreciate the reviewer’s suggestions, which help us clarify both the scope of the current theory and promising directions for signal-adaptive graph retrieval.

[2] Lanczos C. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators[J]. Journal of research of the National Bureau of Standards, 1950, 45(4): 255-282.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

Dear Area Chair,

We thank you and the reviewers for the careful evaluation of our work. We would like to highlight the paper's main contributions and summarize how we have addressed the key concerns raised during the review process:

  • Main contribution: extending dense associative memory to graph-structured data. We introduce Graph-DAM, a spectral associative memory framework based on graph Dirichlet energy and operator-norm distances. Unlike conventional vector-based associative memories, Graph-DAM directly operates on graph Laplacians and preserves valid graph structure throughout retrieval. Our theoretical results establish exponential storage capacity, convergence and retrieval guarantees with exponentially decaying error, and recovery guarantees for spectral quantities, including eigenvalues, eigenspaces, and graph diffusion operators.

  • Addressing the distinction between associative memory and nearest-neighbor retrieval. In response to the concern about the additional value of associative memory, we clarified the fundamental difference between Graph-DAM and operator-norm nearest-neighbor (NN) retrieval. While both become equivalent in the large-inverse-temperature limit, Graph-DAM can retrieve interpolated graph structures through iterative, softmax-weighted memory aggregation, beyond selecting a single stored graph. We further conducted new experiments on interpolated protein-conformation queries, where Graph-DAM achieves a lower mean relative operator error than NN retrieval (0.237 vs. 0.309), demonstrating the benefit of the associative memory mechanism beyond hard nearest-neighbor selection.

  • Additional comparisons with Frobenius-based alternatives. To address concerns about the choice of operator norm, we provided further theoretical explanations and direct experimental comparisons against Frobenius-distance associative memory (Fro-DAM). We clarified how the operator norm captures worst-case Dirichlet-energy distortion, whereas Frobenius distance accumulates perturbations across multiple directions. Our additional protein-conformation experiments show that Graph-DAM consistently outperforms Fro-DAM at matched inverse temperatures, particularly under stronger noise, achieving 91% versus 4% retrieval accuracy at noise factor 1.0 and normalized inverse temperature 8.

  • Theoretical and empirical significance. Beyond the additional baselines, our work provides a unified framework connecting graph Dirichlet geometry, energy-based associative retrieval, exponential storage capacity, and spectral stability. The experiments on synthetic stochastic block models, real-world airline networks, protein conformations, and wearable sensor data further demonstrate the applicability of Graph-DAM to graph-structured retrieval problems.

We have provided detailed responses to the reviewers' remaining questions and concerns in the rebuttal discussion. We hope these clarifications and additional experiments help address the main concerns regarding the necessity of the associative memory mechanism and the advantage of the operator-norm formulation, and provide stronger evidence for the novelty, theoretical contributions, and empirical effectiveness of our work.

We sincerely appreciate your time and consideration in the final assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.