- 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
-
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.
-
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.
-
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
-
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.
-
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.
-
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.
-
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.
-
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
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 within the attraction basin of a particular stored memory . Although need not be exactly identical to , Theorem 3.3 establishes that they are exponentially close. Our spectral guarantees in Theorem 3.4 are therefore for this corresponding stored memory , 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 . 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 memories | Correct queries | Retrieval accuracy |
|---|---|---|
| 50 | 47/50 | 94% |
| 100 | 46/50 | 92% |
| 500 | 44/50 | 88% |
| 1,000 | 43/50 | 86% |
| 5,000 | 42/50 | 84% |
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 stored Laplacians. In the worst-case dense setting, exact eigendecomposition requires operations per comparison, resulting in time per retrieval step. Storing all dense Laplacians requires 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 is inherently task-dependent as it controls the trade-off between memorization and generalization (as in our response to Weakness 3 above). A larger favors selective retrieval of existing memories (i.e. memorization) while a smaller or moderate 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 . 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.
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
A key distinction is that although Graph-DAM reduces to nearest-neighbor (NN) retrieval as (β→∞), 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 β 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−α)Lj. For α=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.
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.
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 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$).