# Fractal-Inspired Message Passing Neural Networks with Fractal Nodes ## Reviewer bGxS (2025-03-11) ### Summary The paper presents a scheme that combines local and global graph information, addressing the limitations of both MPNNs and graph Transformers. ## update after rebuttal Based on the authors' rebuttal, I believe this work still lacks a clear motivation, provides only incremental contributions, and is missing essential evaluations. The authors claim their method aims to mitigate over-squashing, yet they do not compare it against any rewiring-based approaches designed for this purpose—not even the several methods they cite and reference in the rebuttal. Additionally, they argue that their approach offers a lightweight alternative to transformers for incorporating global information. However, the performance gains presented are minimal compared to the baselines they evaluate against. This modest improvement, combined with the absence of theoretical justification and a compelling narrative to support the method, limits the relevance and potential impact of the work for the community. ### Claims and evidence The authors initially claim that GNNs struggle to capture local and global information. As the intro quickly mentions, this statement is not correct as GraphGPS, which is cited in the paper, solved this issue with global attention layers, and very effectively. Then, the authors claim that GraphGPS is not efficient enough, which is not the claim made in the abstract to motivate the paper. Therefore, the motivation that is stated, which is global vs local capturing, is IMHO not convincing, not IMHO true. Also, regarding the efficiency of GraphGPS - it is a flexible framework that allows the user to adjust the complexity, so it is not true that it is inherently computationally complex. To support this claim, one must show that to actually achieve a sota result, excessive computation is required. This was not shown or discussed. ### Methods and evaluation criteria The method is clear, and the evaluation criteria are standard - adding to multiple GNNs and comparing to Graph Transformers ### Theoretical claims The theoretical claims are concerned with oversquashing, although oversquashing is not mentioned as motivation, nor in the intro. I did not check the proofs. ### Experimental designs or analyses The experimental design is fair, yet the proposed approach does not seem to provide any exciting advancements over existing approaches, specifically graph transformers like GRIT, which very successfully capture local and global properties. As this was supposed to be the motivation for the paper, I do not see how the experiment supports this claim. **Supplementary material:** No **Relation to broader scientific literature:** The paper proposes a new scheme for GNNs therefore it relates well to the literature. ### Essential references not discussed Oversquashing references not provided or discussed, although theoretical claims are made wrt to oversquashing. No reference is provided to support the claim that existing models struggle with combining local and global properties, which is the main claim of the paper. ### Other strengths and weaknesses IMHO, the method requires further motivation to justify. The central claim is not demonstrated, nor do the empirical results show promising direction. The proposed method is novel, yet it is not clear which problem it solves and why it excels with others. Results marked as seconds and first are roughly the same in most cases, and no statistical significance was examined. ### Other comments or suggestions IMHO, the method requires further motivation to justify. The central claim is not demonstrated, nor do the empirical results show promising direction. ### Questions for authors Please provide further motivation for the method. Why did you added FN only to simple GNNs and not to the transformers as well? **Overall recommendation:** 1 ## Reviewer Q92H (2025-03-13) ### Summary In this paper, the authors propose a community-centered approach to extract and mix high-frequency and low-frequency information from connected components in the graph. By assigning a virtual node (referred to as a fractal node in this paper) to each community and allowing information mixing between virtual nodes, the authors aim to enhance the information propagation process for capturing long-range dependencies and mitigating the over-squashing problem. **Post Rebuttal**: I appreciate the authors for providing further results during the rebuttal phase. However, given the similarity between the proposed work and existing methods, the authors have not sufficiently explained why models with fractal nodes can outperform similar approaches, especially CoBFormer, where the only difference lies in the use of the attention mechanism. Compared to DRew and even standard virtual node methods (On the connection between MPNN and graph transformer, ICML23), the proposed approach does not show a clear advantage on the Peptides dataset, with these methods achieving comparable performance. I recommend that the authors further explore the differences between their method and related approaches, and include additional analytical experiments to better demonstrate the advantages of the proposed method. Based on these concerns, I will maintain my score. ### Claims and evidence - The authors mention that the community-centered graph coarsening in this paper enhances self-similarity. They should further explain and demonstrate why self-similarity is necessary—what happens if it is absent? Does self-similarity always matter? - In graph pooling/coarsening research, numerous methods (R1–R5) have been proposed to extract hierarchical graph features through learning-based approaches. Compared to these methods, what are the advantages of using the METIS-based approach in this paper? Why is adhering to self-similarity preferable to adaptive virtual nodes (R6, R7)? R1. Hierarchical Graph Representation Learning with Differentiable Pooling. NeurIPS'18 R2. Accurate Learning of Graph Representations with Graph Multiset Pooling. ICLR'22 R3. Self-Attention Graph Pooling. ICML'19 R4. Graph U-Nets. ICML'19 R5. Structural entropy guided graph hierarchical pooling. ICML'22 R6. Exphormer: Sparse Transformers for Graphs. ICML'23 R7. Towards Dynamic Message Passing on Graphs. NeurIPS'24 ### Methods and evaluation criteria - The fractal node can be seen as a special type of virtual/pseudo node under community constraints. How does the proposed method compare to other pseudo-node-based approaches (R6-R8)? The authors should provide a methodological comparison and experimental validation. - The authors claim that graph transformer methods tend to overlook local information. However, many recent approaches have attempted to address this issue, particularly CoBFormer (R9), which identifies the over-globalizing problem in graph transformers and also employs the METIS method for community partitioning. The authors should compare their method with CoBFormer in terms of both methodology and experimental results to highlight its advantages. R8. Boosting Graph Structure Learning with Dummy Nodes. ICML'23 R9. Less is More: on the Over-Globalizing Problem in Graph Transformers. ICML'24 ### Theoretical claims Fig. 2 shows that the high-frequency response of the fractal node is better than that of self-attention. Why does this happen? ### Experimental designs or analyses - The proposed method emphasizes the self-similarity between the coarsened fractal nodes and the original graph, which is a prior assumption more suited for homophilic graph data. The authors should provide validation results on heterophilic benchmarks to demonstrate the general effectiveness of their approach. - R10 also attempts to address the over-squashing problem and has achieved promising results on the LRGB dataset. The authors are encouraged to include it in their comparisons. - The experimental results show that the fractal node achieves better performance when combined with GINE and GatedGCN. The authors should provide memory consumption and runtime analysis for the model under these two backbones. R10. DRew: Dynamically Rewired Message Passing with Delay. ICML'23 **Supplementary material:** Yes **Relation to broader scientific literature:** N/A **Essential references not discussed:** As discussed above with R1-R10. ### Other strengths and weaknesses In this paper, the authors investigate how to balance global and local feature extraction in MPNNs, which has always been a crucial issue in graph research. Moreover, the proposed method effectively enhances the performance of baseline models. **Other comments or suggestions:** N/A **Questions for authors:** Please refer to the content above. **Overall recommendation:** 2 ## Reviewer qPzE (2025-03-14) ### Summary This submission states that the graph neural networks (GNNs) struggle to balance local and global information processing and that the graph Transformers neglect the inherent locality of Message Passing Neural Networks (MPNNs). The submission introduces the ‘fractal nodes’ to address the limitations of both MPNN and graph Transformer. The submission claims that the proposed method enforces feature self-similarity into nodes by creating fractal nodes that coexist with the original nodes. Fractal nodes adaptively summarize subgraph information and are integrated into MPNN. ### Claims and evidence + The paper introduces the concept of “fractal nodes” to address limitations in MPNN. + The authors claim that their proposed fractal nodes alleviate the over-squashing problem by providing direct shortcuts to pass fractal information over long distances. ### Methods and evaluation criteria The authors report that their experiments show that the proposed method achieves comparable or better performance to the graph Transformers while maintaining the computational efficiency of MPNN by improving the long-range dependencies of MPNN. **Theoretical claims:** I check the main arguments and they seem ok. **Experimental designs or analyses:** Analysis is somewhat incomplete as I will detail under main review. **Supplementary material:** Yes, the supplementary material is useful. **Relation to broader scientific literature:** There have been works in the fractal analysis which should be discussed. **Essential references not discussed:** See main review. ### Other strengths and weaknesses 1. The following sentence “Unlike renormalization, which replaces node groups with super-nodes, our method partitions the given graph into subgraphs and, for each subgraph, creates fractal nodes … that coexist with the original nodes (see Fig. 1(b)). Each subgraph has similar connectivity characteristics with those of the full graph, i.e., structural self-similarity (see Fig. 3)” is unclear. Do we need to have exact connectivity or some deviations are allowed? It is unlikely all real world networks look like trees right? 2. The discussion on page 4 on how fractal nodes is a bit confusing and here is why: the text states “each fractal node serves two purposes: (i) representing structural patterns of a subgraph that potentially mirror the whole graph’s topology and (ii) enabling feature self-similarity by adaptively integrating low and high-frequency components from the node features within the subgraph”. Initially I thought that a perfect self-similarity is enforced across all scales but in the above sentence we read “representing structural patterns of a subgraph that potentially mirror the whole graph’s topology” which implies that the self-similarity is not exactly the same but some heterogeneity is allowed which means that we do not deal with a single fractal but with a multifractal approach. Yet, this is not discussed. Also, what is “feature self-similarity”? What are the “low and high-frequency components from the node features within the subgraph”? How are they computed? Can you please provide some examples? 3. While this is minor, the following sentence “Our inspiration comes from the fractal nature (Mandelbrot, 1983) of real-world networks (Dill et al., 2002; Kim & Kahng, 2010; Chen et al., 2020b).” needs to be corrected. As far as I know Mandelbrot was a mathematician and he is considered the father of fractal geometry not fractal nature. The wording of “fractal nature” means nothing, there are many fractals observed in nature like ferns, cauliflower, various trees, canyons, etc, but there is a debate whether all nature is fractal. Also Mandelbrot has not investigated nor demonstrated that networks are fractal. Here are some of the works demonstrating the fractality of real world networks or exploited the fractality of networks for various machine learning tasks: "How to calculate the fractal dimension of a complex network: the box coveringalgorithm." Journal of Statistical Mechanics: Theory and Experiment 2007, no. 03 (2007): P03006; "Small-world to fractal transition in complex networks: a renormalization group approach." Physical review letters 104, no. 2 (2010): 025701. "Reliable multi-fractal characterization of weighted complex networks: algorithms and implications." Scientific reports 7, no. 1 (2017): 7487; "Hidden network generating rules from partially observed complex networks." Communications Physics 4, no. 1 (2021): 199; "Deciphering the generating rules and functionalities of complex networks." Scientific reports 11, no. 1 (2021): 22964; "Network science characteristics of brain-derived neuronal cultures deciphered from quantitative phase imaging data." Scientific reports 10, no. 1 (2020): 15078; "Graph Theoretical Description of Phase Transitions in Complex Multiscale Phases with Supramolecular Assemblies." Advanced Science 11, no. 33 (2024): 2402464; Neuron-based Multifractal Analysis of Neuron Interaction Dynamics in Large Models, ICLR 2025. In general the discussion of related work need to be enhanced since now it refers to very old and unrelated works. 4. Can the concept of fractality be formally integrated into the framework to better capture heterogeneous structures? The current description suggests that the method enforces a single type of self-similarity, but many real-world networks exhibit multifractal properties, meaning different regions of the graph may have varying scaling behaviors. Could the authors discuss whether the method could be extended to incorporate multifractal analysis, potentially by assigning fractal nodes with different scaling parameters based on local connectivity patterns? 5. How do fractal nodes impact computational complexity compared to standard message passing approaches? The paper claims that the proposed method maintains the efficiency of traditional MPNNs while improving long-range dependency modeling. However, since fractal nodes introduce additional computations, such as feature aggregation across multiple scales, it would be useful to clarify the computational cost in terms of time and memory complexity. How does the method scale with increasing graph size compared to standard MPNNs or graph Transformers? 6. Would an ablation study help isolate the effect of fractal nodes from the base MPNN framework? The results indicate performance improvements, but it is unclear how much of this gain is specifically due to fractal nodes versus other factors. Would an ablation study where fractal nodes are selectively removed provide clearer insights into their contribution? Additionally, does the improvement hold consistently across different graph structures and tasks? 7. Does the method generalize well to graphs that do not exhibit clear fractal-like properties? Since the approach is inspired by fractal geometry, it would be useful to understand whether it still provides benefits for graphs that do not follow fractal scaling laws, such as random graphs, small-world networks, or dense graphs with uniform connectivity distributions. Could the authors discuss whether the method’s advantages persist across different graph topologies? 8. Could the method be extended to dynamic or temporal graphs? Many real-world networks, such as social and biological networks, evolve over time. Since fractal structures may emerge only at specific stages of network evolution, would the proposed approach be applicable to dynamic graphs where node interactions change over time? If so, how could fractal nodes be updated dynamically to reflect structural changes? 9. How does the choice of subgraph partitioning affect the performance of the method? The framework relies on dividing the input graph into subgraphs, where each subgraph has similar structural characteristics to the full graph. However, different partitioning strategies (e.g., spectral clustering, modularity-based partitioning, random sampling) may lead to different fractal representations. Could the authors discuss how sensitive the model is to the choice of subgraph construction method and whether different partitioning techniques impact model performance? **Other comments or suggestions:** n/a ### Questions for authors 1. Can the concept of fractality be formally integrated into the framework to better capture heterogeneous structures? The current description suggests that the method enforces a single type of self-similarity, but many real-world networks exhibit multifractal properties, meaning different regions of the graph may have varying scaling behaviors. Could the authors discuss whether the method could be extended to incorporate multifractal analysis, potentially by assigning fractal nodes with different scaling parameters based on local connectivity patterns? 2. How do fractal nodes impact computational complexity compared to standard message passing approaches? The paper claims that the proposed method maintains the efficiency of traditional MPNNs while improving long-range dependency modeling. However, since fractal nodes introduce additional computations, such as feature aggregation across multiple scales, it would be useful to clarify the computational cost in terms of time and memory complexity. How does the method scale with increasing graph size compared to standard MPNNs or graph Transformers? 3. Would an ablation study help isolate the effect of fractal nodes from the base MPNN framework? The results indicate performance improvements, but it is unclear how much of this gain is specifically due to fractal nodes versus other factors. Would an ablation study where fractal nodes are selectively removed provide clearer insights into their contribution? Additionally, does the improvement hold consistently across different graph structures and tasks? 4. Does the method generalize well to graphs that do not exhibit clear fractal-like properties? Since the approach is inspired by fractal geometry, it would be useful to understand whether it still provides benefits for graphs that do not follow fractal scaling laws, such as random graphs, small-world networks, or dense graphs with uniform connectivity distributions. Could the authors discuss whether the method’s advantages persist across different graph topologies? 5. Could the method be extended to dynamic or temporal graphs? Many real-world networks, such as social and biological networks, evolve over time. Since fractal structures may emerge only at specific stages of network evolution, would the proposed approach be applicable to dynamic graphs where node interactions change over time? If so, how could fractal nodes be updated dynamically to reflect structural changes? 6. How does the choice of subgraph partitioning affect the performance of the method? The framework relies on dividing the input graph into subgraphs, where each subgraph has similar structural characteristics to the full graph. However, different partitioning strategies (e.g., spectral clustering, modularity-based partitioning, random sampling) may lead to different fractal representations. Could the authors discuss how sensitive the model is to the choice of subgraph construction method and whether different partitioning techniques impact model performance? **Overall recommendation:** 2 ## Discussion, meta-review and decision (in time order) ### Rebuttal -- Authors (2025-03-31) ### Rebuttal We sincerely thank Reviewer Q92H for the thoughtful feedback. --- **Response to Claims and Evidence** **(1)** We would like to clarify that our paper does not claim that graph coarsening enhances self-similarity. Rather, we use graph partitioning to create fractal nodes, which enable message passing between original nodes and fractal nodes within subgraphs. This design injects structural and feature-level self-similarity into the model without assuming it as a prerequisite. In our framework, self-similarity acts as a soft inductive bias. As shown in Theorems 4.1 and 4.2, fractal nodes reduce effective resistance by connecting directly to subgraph nodes, thereby improving long-range propagation. Even in cases where self-similarity is weak or absent, the model adapts through the learnable parameter $\omega_c$, which controls the influence of subgraph-level signals and allows local information to dominate when necessary. **(2)** Unlike pooling-based methods that coarsen the graph by removing nodes, our approach augments the graph by adding fractal nodes, while preserving the original structure. This allows us to maintain the full expressiveness of the base MPNN and inject global context without the risk of information loss. Using METIS provides a practical advantage — it preserves structurally coherent subgraphs that reflect approximate self-similarity, and does so with linear complexity $\mathcal{O}(|E|)$, making it suitable for large-scale graphs. Compared to adaptive virtual node approaches, our methods adaptively combine low- and high-frequency components within structurally consistent regions. This can also be advantageous in heterophilous graphs, which we will later address in **Response to Experimental Designs**. --- **Response to Methods and Evaluation Criteria** Compared to Exphormer (R6), which relies on sparse attention, our method remains within the MPNN framework and uses fractal nodes to summarize and propagate subgraph-level context. This preserves both locality and efficiency, as included in our results (Tables 1 and 3). Unlike pseudo-node methods such as R7 and R8, which insert global or dummy nodes without structural alignment, our fractal nodes are explicitly tied to partitioned subgraphs. Each fractal node adaptively combines low- and high-frequency signals within a subgraph. On large-scale datasets, our method remains competitive and efficient: - ogbn-arxiv - GCN+FN:73.03±0.37 - N$^2$:70.01±0.65 - ogbn-products - GCN+FN:81.29±0.21 - N$^2$:79.55±0.79 Furthermore, as shown below, our methods achieve higher accuracy than N$^2$ (R7) on new additional datasets. ||Computer|Photo|CS|Physics|WikiCS| |-|-|-|-|-|-| |N$^2$|92.51±0.13|95.75±0.34|94.44±0.45|97.56±0.28|-| |CobFormer-G|91.53±0.24|94.65±0.22|94.35±0.40|96.16±0.54|73.02±0.64| |CobFormer-T|91.81±0.33|94.61±0.22|94.39±0.27|96.57±0.68|73.97±0.76| |GCN+FN|93.59±0.17|95.87±0.26|95.54±0.16|97.38±0.07|78.41±0.56| |GraphSAGE+FN|93.13±0.24|96.46±0.33|96.09±0.27|97.04±0.19|80.27±0.58| While CoBFormer (R9) also uses METIS, it remains Transformer-based architecture and introduces attention layers over learned community tokens. In contrast, our method extends MPNNs by injecting global context via fractal nodes and avoids the quadratic overhead of full attention. Our comparative results above show our advantage. --- **Response to Theoretical Claims** Self-attention tends to average across all nodes, which suppresses high-frequency signals. In contrast, our method explicitly incorporates a high-pass filtering term that accentuates local variations. This design choice explains the improved frequency response seen in Fig. 2. --- **Response to Experimental Designs** 1. We evaluated GCN+FN on heterophilic benchmarks. Our method consistently improves performance on all datasets, often outperforming GraphGPS. ||Squirrel|Chameleon|Amazon-ratings|Roman-empire|Minesweeper|Questions| |-|-|-|-|-|-|-| |GraphGPS|39.67±2.84|40.79±4.03|53.10±0.42|82.00±0.61|90.63±0.67|71.73±1.47| |GCN|38.67±1.84|41.31±3.05|48.70±0.63|73.69±0.74|89.75±0.52|76.09±1.27| |GCN+FN|44.52±1.50|44.72±4.89|53.58±0.45|88.13±0.20|97.51±0.43|78.32±0.53| 2. We also compared our method to DRew. As shown below, GINE+FN$_M$ achieves higher or competitive performance on both Peptide datasets. ||Peptide-func|Peptide-struct| |-|-|-| |Drew-GCN|0.7150±0.0044|0.2536±0.0015| |Drew-GINE|0.6940±0.0074|0.2606±0.0014| |GCN+FN|0.6802±0.0043|0.2530±0.0004| |GCN+FN$_M$|0.6787±0.0043|0.2464±0.0014| |GINE+FN|0.6815±0.0059|0.2515±0.0020| |GINE+FN$_M$|0.7018±0.0074|0.2446±0.0018| 3. We report the runtime and memory usage of GINE and Gated GCN backbones on Peptide-func below. Compared to Transformer-based models, both variants remain highly efficient. We will include the full results in the revised version. ||Time/Epoch(s)|Memory(MB)| |-|-|-| |GCN|6.13|333| |Trans.+LapPE|10.01|6,661| |GraphGPS|12.01|6,904| |GCN+FN$_M$|6.37|667| |GINE+FN$_M$|7.10|950| |GatedGCN+FN$_M$|7.63|885| ### Rebuttal -- Authors (2025-04-01) ### Rebuttal We sincerely thank Reviewer qPzE for the thoughtful review. --- **Response to Q1: Fractal vs. Multifractal Structures** Our current design already allows heterogeneity via learnable scaling parameters $\omega_c$ per subgraph. This flexibility can be interpreted as an implicit form of multifractality. Moreover, in our evaluation on heterophilous graphs (see `"Response to Experimental Designs" rebuttal to Reviewer Q92H`), our model outperforms baseline MPNNs and even GraphGPS. These datasets inherently exhibit regionally diverse connectivity and feature patterns, which aligns with the multifractal nature of real-world networks. **Response to Q2: Computational Cost and Scalability** The addition of fractal nodes introduces only minimal overhead. We provide a detailed analysis of runtime, memory usage, and complexity in `Section 4.2`, `Section 5.4` and `Appendix H` (Scalability Analysis of Fractal Nodes). As shown in `Table 4`, the runtime and memory usage of GCN+FN is nearly identical to base GCN. **Response to Q3: Contribution of Fractal Nodes (Ablation Studies)** We have already conducted ablations in `Section 5.5` and `Appendix I`. We show that removing the HPF (i.e., setting $\omega_c = 0$) or fractal node interactions leads to a drop in performance. This confirms that fractal nodes directly contribute to performance improvements. Moreover, these improvements are consistent with datasets with different structural properties. **Response to Q4: Applicability to Non-fractal Graphs** Our design does not rely on strict fractal structures. In practice, many datasets we tested do not exhibit strong self-similarity, yet our methods consistently improve performance. Moreover, we show that it mitigates over-squashing that occurs in repetitive fractal structures in tree structures, such as in the TreeNeighbourMatch task. This suggests our method is robust on any structures. **Response to Q5: Temporal Graphs** Since fractal nodes are based on local subgraphs, they can be dynamically updated with changes in graph structure. For example, subgraphs could be maintained over temporal snapshots or incrementally adjusted. We plan to mention it in the revised conclusion section as future work. **Response to Q6: Subgraph Partitioning Strategy** As discussed in `Appendix N` and `I.5`– `I.6`, we tested alternative strategies and different numbers of subgraphs. As shown in `Tables 15 & 16`, our method performs consistently well across various partitioning stratiges (Random, Louvain, and Girvan-Newman partitionings). While METIS yields the best performance overall, other methods also produce comparable results. Thus, our model is robust to the choice of partitioning algorithm. As shown in `Fig 9`, increasing the number of subgraph $C$ consistently improves performance across datasets. This aligns with our theoretic result in `Corollary B.4`, which shows that the total resistance decreases as $C$ increases due to additional eigenvalues contributing to the effective resistance. **Response to Weakness: Is exact Matching Needed?** We do not assume exact structural matching between subgraphs and the full graph. Instead, we adopt a relaxed notion of approximate self-similarity, where subgraphs reflect high-level structural patterns (e.g., degree or clustering as in `Fig.3`) without being identical. This approximate resemblance motivates message passing within subgraphs, allowing fractal nodes to summarize subgraph-level structure. These structural summaries then guide feature self-similarity, where each fractal node integrates low- and high-frequency components of node features in its subgraph. **Response to Weakness: Feature Self-Similarity and Frequency Components** Feature self-similarity refers to capturing both global and local feature patterns within a subgraph — a concept grounded in signal processing. As noted after Theorem 3.1, the low-frequency component is the subgraph mean (DC component), and the high-frequency component is the deviation from this mean (see `Eqs 14 to 16`). Each fractal node combines these two components via $\omega_c$, allowing the model to adaptively integrate local variations and subgraph-level global information. This results in a representation that reflects feature-level self-similarity across scales. For example, in molecular graphs like Peptides, nodes in a functional group may share overall chemical properties (low-frequency) but differ in local charge (high-frequency). **Response to Weakness: Terminology and Related Work** We appreciate the suggestion. We will revise the phrase “fractal nature” to “fractal geometry” and clarify that Mandelbrot introduced the mathematical theory, not its application to networks. We will also incorporate the reviewer’s suggested citations. ### Rebuttal -- Authors (2025-04-01) ### Rebuttal We sincerely thank Reviewer bGxS for the thoughtful review. --- **Response to Motivation and Global/Local Claim** We appreciate your point regarding GraphGPS. While it combines local and global signals via attention and LapPE, it does so using Transformer modules that can incur significant overhead, especially when using the vanilla architecture. Our claim is not that no model captures both aspects, but that standard MPNNs struggle to do so, and global mechanisms often trade off scalability. As discussed in Sections 1 and 2, our method offers a scalable alternative by injecting global structural context into MPNNs via lightweight fractal nodes—without relying on costly attention. Notably, as shown in Table 3, GraphGPS fails to process ogbn-products due to OOM. Table 4 further shows that achieving competitive performance with GraphGPS incurs high memory usage (e.g., 38.91 GB vs. 16.49 GB for ours on ogbn-arxiv). Although GraphGPS uses sparse attention to mitigate overhead, it still faces scaling challenges. Moreover, it is primarily effective on graph classification benchmarks with small graphs (~200 nodes on average). Prior works [1–4] have also reported scalability limitations on large graphs. > [1] ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment, arXiv preprint arXiv:2412.01519 > > [2] Stronger Graph Transformer with Regularized Attention Scores, arXiv preprint arXiv:2312.11730 > > [3] Anchorgt: Efficient and flexible attention architecture for scalable graph transformers, IJCAI 2024 > > [4] Best of Both Worlds: Advantages of Hybrid Graph Sequence Models, arXiv preprint arXiv:2411.15671. **Response to Theoretical Claims: Oversquashing** Oversquashing is mentioned in the introduction and related work (Sections 1–2) as a key limitation of MPNNs. Our method addresses it by introducing fractal nodes that reduce path lengths and enhance message propagation. Theoretical support is given in Section 4 and Appendix B, showing how fractal nodes reduce effective resistance. We will revise the Intrudction to make this connection more explicit. **Response to Experimental Designs Or Analyses** We appreciate the emphasis on strong baselines such as GRIT. Our goal is to show that simple MPNNs with fractal nodes can achieve competitive or outperform graph Transformers with significantly better scalability. This is especially important for large-scale graphs, such as ogbn-arxiv and ogbn-products, where many Transformer-based models - including GRIT- often fail to OOM, as also reported in Table 9 from [4]. Our approach enables long-range propagation without attention, offering a scalable, practical alternative. This reduces reliance on Transformer frameworks, which is critical for real-world settings. Regarding evaluation, we followed standard protocols by reporting the mean and standard deviation over multiple runs, as done in prior works. For ogbn-arxiv, we conducted Welch’s t-tests comparing our best variants (GCN+FN and GraphSAGE+FN$_M$) against strong baselines including PolyNormer, SGFormer, and their respective vanilla models. All comparisons yielded statistically significant differences with p-values < 0.01. This supports the empirical validity of our method, especially in large-scale settings. We will include full tests in the revised version. **Response to Essential References** We acknowledge the need for more visible citations. While related work on oversquashing is already cited in the introduction and Appendix B, we will make these references more visible in the main text. Additionally, we will cite works discussing the challenge of capturing both local and global information in MPNNs and Transformers[5-8]. > [5] LG-GNN: local-global adaptive graph neural network for modeling both homophily and heterophily, IJCAI 2024. > > [6] Global-local graph neural networks for node-classification, Pattern Recognition Letters 184, 2024 > > [7] LGI-GT: Graph Transformers with Local and Global Operators Interleaving, IJCAI 2023. > > [8] Less is more: on the over-globalizing problem in graph transformers, ICML 2024 **Response to Weakness: What Problem Does This Method Solve?** Our method addresses: 1. Oversquashing in MPNNs that degrades long-range modeling. 2. Inefficiency of graph Transformer-based models on large-scale graphs. Fractal nodes provide a simple, principled way to inject global structure into MPNNs while preserving linear complexity. Both theory and experiments support this. **Response to Q1.** See `Response to Motivation and Global/Local Claim` **Response to Q2.** We focused on MPNN backbones to highlight the benefit of fractal nodes in message-passing settings, where oversquashing is more severe. However, fractal nodes are modular and can be integrated into Transformer-based models as well. We plan to explore this in future work and will mention it in Conclusion. ### Rebuttal Acknowledgement -- Reviewer Q92H (2025-04-04) ### Rebuttal Acknowledgement -- Reviewer qPzE (2025-04-05) ### Decision -- Program Chairs (2025-05-01) **Decision:** Reject ### Comment The authors aim to improve the quality of deep learning models via better local and global information exchange in deep neural networks. This is done via adding nodes that make GNNs and MPNNs look and behave more like networks observed in real life, ie those exhibiting multi-scale similarity, aka self-similar or fractal networks. Even though there is much intriguing research, computation and observations in this paper which make it a pleasant read, the main conclusion -- serious improvement in classification and inference over GNNs and MPNNs -- is not born out of the benhcmarking exercise. Table 1 makes this abundently clear that the improvement over SOTA (red over blue), nearly always less than 1 percentage point, are just too small to make much difference. The authors need to find and exhibit real datatsets with more compelig evidence of the impact of their methodology.