Review history

How Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs got from its first submission to AAAI 2026: 4 submissions. Scores use each venue's own scale (hover a score for the reviewer's confidence; 3→5 = changed after the rebuttal). ← CV of Failures

Jan 2025ICLR 2025mean 5.5, rejected

May 2025ICML 2025mean 1.7, rejected

Sep 2025NeurIPS 2025mean 2.2, withdrawn

Nov 2025AAAI 2026mean 6.6, accepted

About the full reviews on this page. Reviews that are already public on OpenReview are only linked. For the other rounds I share the reviews my paper received myself, under three rules: only for papers that were eventually accepted, only conference reviews (never journal reviews), and only as received — reviewers appear under the anonymous IDs or numbers the venue gave them, and I do not know who they are. The venue rules I checked are quoted with each round; none of them prohibits authors from sharing the reviews of their own submission.

ICLR 2025 ✗ rejectedsubmitted 2024-09-27

6556mean 5.5

public reviews on OpenReview

What the reviewers raised

Borderline scores (6, 6, 5, 5): the idea was seen as interesting, the evidence as not yet convincing.
Novelty: fractal nodes read like a mix of cluster-based training (METIS partitions, as in Cluster-GCN) and virtual nodes.
The low-/high-pass filter interpretation of the fractal node features was questioned, since the averages are taken over node features rather than graph spectra.
Gains over baselines looked small, and the discussion of results was thin.
Missing: node-level benchmarks, ablations over partitioning strategies, cost of building the fractal nodes, and a sharper theoretical account of why they help over-squashing.

What changed for the next submission

Added theory on over-squashing (effective-resistance reduction) and expressive power.
Extended the experiments and ablations, including the cost of partitioning.

ICML 2025 ✗ rejectedsubmitted 2025-01-24, decision 2025-05-01

221mean 1.7

reviews not public on OpenReview — shared by the authors download as .md

What the reviewers raised

Low scores (1, 2, 2): the motivation was the main problem. The paper claimed MPNNs miss global information, but graph Transformers such as GraphGPS already capture it, so the case had to rest on efficiency.
Improvements over the strongest baselines were mostly under one percentage point, without significance tests; the decision cited this directly.
Positioning against graph pooling/coarsening and other virtual-node methods, and results on heterophilic graphs, were requested.

What changed for the next submission

Reframed the paper around a direct question -- are graph Transformers necessary? -- with MPNN efficiency as the point.
Added comparisons with virtual-node and coarsening approaches.

ICML 2025 publishes the reviews of accepted papers; reviews of rejected papers stay private unless the authors opt in (ICML 2025 Peer Review FAQ). The FAQ places no restriction on authors sharing the reviews of their own submission.

Full reviews and discussion

Reviewer bGxS: rating 1

Overall recommendation 1

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

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?

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.

Reviewer Q92H: rating 2

Overall recommendation 2

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.

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|

Reviewer Q92H, 2025-04-04

Reviewer qPzE: rating 2

Overall recommendation 2

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?

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.

Reviewer qPzE, 2025-04-05

Meta-review and decision

Decision by 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.

NeurIPS 2025 ↩ withdrawnsubmitted 2025-05-12

3222mean 2.2

reviews not public on OpenReview — shared by the authors download as .md

What the reviewers raised

Low scores (3, 2, 2, 2): novelty relative to virtual nodes and super-nodes was the dominant concern, and the theory was seen as extending known effective-resistance arguments.
Readability: key notions (frequency domain, effective resistance) were only defined in the appendix.
One reviewer pointed to recent evidence that well-tuned classic GNNs are strong graph-level baselines.

Outcome

Withdrawn after the reviews; revised for AAAI 2026 under the title "Are Graph Transformers Necessary?".

NeurIPS 2025 makes reviews, meta-reviews and author discussion public for accepted papers, and lets authors of rejected papers opt in (NeurIPS 2025 Call for Papers). Its confidentiality rules bind reviewers, area chairs and program chairs; nothing restricts authors from sharing the reviews of their own submission. This submission was withdrawn after the reviews.

Full reviews and discussion

Reviewer 7Tfo: rating 2, confidence 4

Quality 2, Clarity 3, Significance 2, Originality 2, Rating 2, Confidence 4

Summary

The authors introduce fractal nodes, an auxiliary set of “super-nodes” created by partitioning a graph into subgraphs and connecting each new node to all vertices in its subgraph. Each fractal node adaptively blends the low-frequency (global) and high-frequency (local) components of its members’ features, then passes this representation back to the originals; an optional MLP-Mixer layer lets the fractal nodes exchange information with one another. These single-hop shortcuts shorten effective path lengths, theoretically lowering effective resistance and mitigating over-squashing, while keeping the overall cost linear in edges like a vanilla Message Passing Neural Network. The paper supplies proofs of the resistance reduction, shows higher expressive power than plain MPNNs, and presents experiments on synthetic tasks, six medium-size graph benchmarks, and two OGB large-scale node-classification datasets where MPNNs augmented with fractal nodes match or surpass state-of-the-art graph Transformers yet train with the memory footprint of standard MPNNs.

Strengths and weaknesses

Strengths: The manuscript is well-structured and mathematically careful: it details how each fractal node is built from low- and high-frequency subgraph features, derives closed-form updates, and supplies complete proofs for theorems on effective-resistance reduction and expressive power in the supplementary material. The authors also report time complexity that remains linear in edges for the plain variant and only mildly super-linear when the Mixer layer is added. Empirically, they evaluate on six medium-size graph benchmarks plus two large OGB datasets, where a vanilla GCN or GraphSAGE augmented with fractal nodes matches or slightly surpasses transformer-style baselines while using less memory. Tables, ablations, and sensitivity plots further aid readability and reproducibility.

Weaknesses: Conceptually, fractal nodes amount to inserting subgraph “super-nodes” that broadcast pooled information—an idea that closely parallels long-standing virtual-node techniques and recent hierarchical or coarsened-graph modules; the paper itself acknowledges these similarities. Theoretical results on effective resistance and over-squashing extend earlier analyses rather than break new ground, and the claimed expressive-power gains rely on known subgraph-based arguments. Empirical improvements are modest (often one to two percentage points) and hinge on a sizeable hyper-parameter sweep for partition size, number of fractal nodes, Mixer depth, and frequency-blend weights—search spaces the authors list across two full tables. Moreover, the method requires an external METIS partitioning step and introduces an extra Mixer whose cost still scales quadratically in the number of fractal nodes, muting the claimed efficiency edge. Given these incremental advances and limited practical upside, the work feels more like an elaboration of established tricks than a contribution that will materially shift the trajectory of graph-network research.

Questions

Partitioning strategy and ablation depth: Your own “Limitations and future directions” section notes that the approach “relies on predefined graph partitioning” and suggests learnable partitioning as future work. Could you (i) extend the current METIS / random / Louvain comparison by plotting accuracy and wall-clock partition time versus the number of subgraphs on at least one large graph, and (ii) add a baseline with a single “virtual” node (no partitioning) to isolate how much of the gain comes from having multiple fractal nodes rather than from the extra shortcut itself? Even a small-scale study would clarify the trade-off between partition quality, preprocessing cost, and performance.

End-to-end computational overhead: Although METIS is linear in edges, it still takes ~15 minutes on ogbn-products and nearly a second on ogbn-arxiv, and the optional Mixer layer adds a quadratic term to each message-passing layer. Please provide end-to-end GPU memory and training-time curves that include the partitioning step—varying both graph size and the number of fractal nodes—so readers can judge whether the total cost remains competitive with graph Transformers in practical settings.

Hyper-parameter sensitivity and default guidance: The method introduces several new knobs (subgraph count, blend weight, Mixer depth, high-frequency flag) and tunes them over a broad grid. Could you add concise sensitivity plots showing performance versus each key parameter, and distil these into simple heuristics—perhaps linking C to the square root of the node count, or recommending a fixed \(\omega\) range—that let practitioners adopt fractal nodes without an exhaustive sweep? Clear default settings would strengthen the paper’s practical impact.

Limitations

Yes.

Paper formatting concerns

Responsible reviewing acknowledgement

Yes

Reviewer EzmK: rating 2, confidence 4

Quality 2, Clarity 3, Significance 1, Originality 1, Rating 2, Confidence 4

Summary

To enhance the ability of GNNs to capture long-range global features, the authors propose to perform message passing within subgraphs obtained via graph partitioning. This allows the model to extract representative local information for global message passing. The authors provide theoretical analysis to support the representativeness of features derived from subgraph partition, and conduct experiments on both node-level and graph-level datasets to demonstrate the effectiveness of the proposed method in alleviating over-squashing.

Strengths

- The authors provide both theoretical and empirical analyses to support the expressiveness of fractal nodes and their effectiveness in alleviating the over-squashing problem.
- The overall writing of the paper is clear and easy to follow.
- The authors have provided open-source code to support the reproducibility of their work.

Weaknesses

- Contributions and Related Works: The related work review in this paper is not sufficiently comprehensive. The insights and motivation presented show notable similarities to prior work, which somewhat diminishes the perceived novelty and contribution of this paper.
- For subgraph-based message passing, prior works have already explored partitioning the input graph and performing message passing within the resulting subgraphs (R1-R4). The authors are encouraged to provide a more thorough comparison with such methods, clarify how their approach differs from existing ones, and highlight the novel aspects and contributions introduced in this work.
- For the construction of virtual nodes/ pseudo nodes, many existing methods have explored end-to-end approaches (R5-R7) and analyzed their effectiveness in addressing issues such as over-squashing. The authors are encouraged to discuss the similarities and differences between these methods and the proposed fractal nodes, rather than briefly stating that prior work "has explored the role of virtual nodes in mitigating under-reaching and over-smoothing issues" (L109). In particular, the use of METIS-based graph partitioning in this paper results in a fixed, heuristic assignment of nodes to virtual (fractal) nodes. A comparison with prior work that employs learnable node-to-virtual-node assignment strategies would help clarify the advantages or trade-offs of the proposed approach.
- A particularly similar approach can be found in R4, which also uses METIS for graph partitioning and performs local message passing within subgraphs. The authors should explicitly clarify the similarities and differences between their method and R4, and highlight the novel contributions introduced in this work.
- Many prior works (e.g., R7–R9) have also proposed methods to address the over-squashing problem. The authors are encouraged to discuss and compare these approaches in the related work section to better position their contribution within the existing literature.
- Experiments
- The proposed method performs local message passing within partitioned subgraphs, which encourages information exchange primarily among locally connected nodes. This design is well-suited for feature extraction in homophilic graphs. To demonstrate the broader applicability of the method, the authors are encouraged to extend their experiments to heterophilic graph datasets.
- The paper does not clearly specify which backbone architectures were used in the reported baseline results. It would be helpful for the authors to clarify this point and discuss whether the model comparisons were conducted under fair and consistent settings.

R1. Graph partitioning and graph neural network based hierarchical graph matching for graph similarity computation, Neurocomputing'21

R2. A Variational Edge Partition Model for Supervised Graph Representation Learning, NeurIPS'22

R3. Partition-Based Active Learning for Graph Neural Networks, TMLR'23

R4. Less is More: on the Over-Globalizing Problem in Graph Transformers, ICML'24

R5. Exphormer: Sparse Transformers for Graphs, ICML'23

R6. Boosting Graph Structure Learning with Dummy Nodes, ICML'23

R7. Towards Dynamic Message Passing on Graphs, NeurIPS'24

R8. DRew: Dynamically Rewired Message Passing with Delay. ICML'23

R9. Even Sparser Graph Transformers, NeurIPS'24

Questions

Please refer to the weaknesses.

Limitations

The authors have addressed the limitations and potential negative societal impact of their work.

Paper formatting concerns

N/A

Responsible reviewing acknowledgement

Yes

Reviewer hcYU: rating 2, confidence 3

Quality 2, Clarity 2, Significance 2, Originality 2, Rating 2, Confidence 3

Summary

The authors propose an approach that enhances graph learning by leveraging information flow within and across local graph partitions. The main idea is to partition an input graph into a set of (overlapping) substructures and connect the nodes within each substructure to a newly introduced auxiliary node for each partition. Additionally, edges between auxiliary nodes allow for a long-range information propagation, with the goal of mitigating oversquashing issues. The authors introduce their idea as a general method that can be utilised with many standard MPNNs. They justify their approach both theoretically and finally experimentally, showing an improvement in standard benchmark scenarios.

Strengths and weaknesses

Strengths:
- The experimental evaluation is comprehensive and generally conducted well.
- The approach is general and can be used with most MPNNs.

Weaknesses:
- The article lacks self-containment. Much of the theory relies on notations that are not introduced in the main paper. For instance, terms like 'frequency domain' and 'Fourier domain' are never discussed, making Theorem 3.1 difficult to interpret. Similarly, while 'effective resistance' is defined in the appendix, it is not properly referenced in the main paper. These concepts should be addressed in the preliminaries section. If space is a concern, at least a brief outline or a rough overview should be provided to help readers grasp the ideas. Therefore, as of now, large parts of the theory remain somewhat unclear.
- The authors' idea is not novel. E.g. [1] has considered a similar approach, where information is propagated using auxiliary nodes for fragments. A more in-depth discussion of related work would help clarify how this paper’s contributions differ and extend on existing methods.
- There are some formal presentation issues. For instance, in Eq. (3), it states "u \in N_v", but it is unclear what v refers to in this context. Should it be "\V_c" instead?

Minor points:
- I would suggest discussing the parameter C, i.e. the number of partitions, in the main paper, as it is a quite central aspect of your approach.

[1] Wollschläger, T., & Kemper, N. Expressivity and Generalization: Fragment-Biases for Molecular GNNs. ICML 2024

Questions

- Did the authors study the theoretical expressiveness in more detail than what is mentioned in Sect 4.1?
- Concerning the FN_M method, did the authors consider simply adding edges between fractal nodes of neighbouring partitions?
- In the supplementary you mention that there is a parameter k that governs the overlap of partitions. Can you elaborate on how you chose this?

Limitations

yes

Paper formatting concerns

No concerns.

Responsible reviewing acknowledgement

Yes

Reviewer aBpf: rating 3, confidence 3

Quality 2, Clarity 3, Significance 2, Originality 2, Rating 3, Confidence 3

Summary

This paper proposes fractal-inspired message passing neural networks to balance local and global information while preserving scalability. Experiments demonstrate that our method improves the expressive power of MPNNs and achieves comparable or better performance to the graph Transformers, while maintaining the computational efficiency of MPNN by improving the long-range dependencies of MPNN.

Strengths and weaknesses

Strengths:

1. The proposed fractal nodes can improve the expressiveness of GNNs.
2. The authors conduct extensive experiments to support the claims.
3. This paper is well-written.

Weaknesses:

1. The concept of fractal nodes is similar to "super nodes" in [1].
2. The performance of the proposed VN is significantly lower than the classic GNN baselines [2].

[1] VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections. ICLR 2024.

[2] Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence. ICML 2025.

Questions

See Weaknesses.

Limitations

yes

Paper formatting concerns

N/A

Responsible reviewing acknowledgement

Yes

Rebuttal and other comments (in time order)

Authors, 2025-07-25

Withdrawal confirmation

I have read and agree with the venue's withdrawal policy on behalf of myself and my co-authors.

Comment

We appreciate the reviewers' valuable comments and will address these concerns in the revision. After careful consideration, we decided to withdraw this manuscript.

AAAI 2026 ✓ acceptedsubmitted 2025-07-25, decision 2025-11-07

87657mean 6.6

reviews not public on OpenReview — shared by the authors download as .md

What was discussed

Scores 8, 7, 7, 6, 5; accepted as an oral presentation.
Supportive reviewers found the method simple, compatible with standard MPNNs and well supported by experiments, including OGB-scale results.
Remaining concerns: overlap with virtual-node and subgraph methods, the dependence on a fixed METIS partitioning and on the number of fractal nodes, the lack of proof sketches in the main text, and how much of the gain comes from each component.
The rebuttal promised proof sketches and clarifications; one reviewer confirmed it addressed their concerns.

AAAI-26 does not publish reviews. The confidentiality pledge is in its ethical guidelines for reviewers (“I will maintain the confidentiality of the review process and respect the privacy of the authors”); the policies for authors say nothing against authors sharing the reviews of their own submission.

Full reviews and discussion

Reviewer Uk9C: rating 7, confidence 4

Quality This is a fairly good paper, Clarity The paper is mostly clear and easy to understand, Originality To the knowledge of the reviewer, Rating 7, Confidence 4

Summary

The paper introduces the notion of fractal nodes in MPNNs. The purpose of the fractal nodes is to enforce feature similarity within subgraphs and allow communication between nodes over large distances with only linear scaling instead of the quadratic scaling required by other architectures like graph transformers or GraphGPS. Theoretical results in the paper show that fractal nodes alleviate the over-squashing problem. Experimental results show an increase in expressive power compared to regular MPNNs and that MPNNs with fractal nodes have comparable or better performance compared to graph transformer-based models, while being as scalable and efficient as MPNNs.

Significance

The work proposes an improvement to MPNNs and an alternative to graph transformer architectures in the form of fractal nodes added to MPNNs. The upsides of this technique are discussed from various angles. Especially noteworthy are that the accuracy of the method is similar to graph transformers, but with a significant reduction in the amount of memory required.

Pros

- The proposed fractal nodes appear useful in light of both the theoretical and experimental results presented in the paper.
- The experiments seem very thorough and support the conclusions.

Cons

- There are seemingly no proof sketches or proof intuitions for the theoretical results of the paper.

Final decision

This is a nice paper that fits well into AAAI. The fractal node method for MPNNs seems novel and the theoretical and experimental results demonstrate its usefulness. The paper is well-written. The lack of proof sketches is a little troubling, and the reviewer would advice this to be revised.

Miscellaneous notes

- Is the notation \(\mathcal{N}_v\) correct in Equation (4)?
- Section 5.1 contains a strange reference to itself.

Reply to author rebuttal

I thank the authors for their rebuttal. It addresses many concerns, including my own about proof sketches; if the paper is accepted, I hope to see the promised revisions implemented with care. I stand by my original score.

Reviewer VQV4: rating 5, confidence 5

Rating 5, Confidence 5

Review

The paper introduces fractal nodes as an augmentation to MPNNs, claiming they alleviate over-squashing, preserve local/global information, and rival Graph Transformers in performance and scalability. The authors present theoretical proofs (resistance reduction, propagation bounds) and experiments on synthetic, medium-scale, and large-scale benchmarks.

The strengths include:
1. Addresses the timely question of whether Graph Transformers are truly necessary.
2. The fractal node idea is simple and compatible with standard MPNNs.
3. Theoretical analysis is provided and aligned with experiments.
4. Large-scale experiments (OGB) show scalability advantages over Graph Transformers.

The weaknesses include:
1. The motivation for this paper is framed around the idea that Graph Transformers capture long-range dependencies better than MPNNs, and that fractal nodes provide an efficient alternative. However, this is an oversimplification for GNNs.
a. In graph learning, long-range dependency is affected not only by oversquashing (information bottlenecks along narrow cuts) but also by issues such as over-smoothing (loss of feature diversity with depth) [A], heterophily (neighbors carrying dissimilar labels) [B], and noise introduced by indiscriminate global connections [C].
b. Transformers do not inherently solve these problems, in fact, their global attention can worsen over-globalization [D] and amplify noise. By reducing the problem to oversquashing alone, the authors both mischaracterize the challenge and overstate the relevance of Transformers as the baseline solution.
c. A more accurate framing would acknowledge that long-range dependency requires balancing structural bottlenecks, representation diversity, and robustness to noise, not just adding global shortcut paths.
[A] Chen, Deli, et al. "Measuring and relieving the over-smoothing problem for graph neural networks from the topological view." Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 04. 2020.
[B] Zhu, Jiong, et al. "Beyond homophily in graph neural networks: Current limitations and effective designs." Advances in neural information processing systems 33 (2020): 7793-7804.
[C] Dai, Enyan, Charu Aggarwal, and Suhang Wang. "Nrgnn: Learning a label noise resistant graph neural network on sparsely and noisily labeled graphs." Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining. 2021.
[D] Xing, Yujie, et al. "Less is More: on the Over-Globalizing Problem in Graph Transformers." Forty-first International Conference on Machine Learning.

2. The novelty of “fractal nodes” is overstated; the concept strongly overlaps with existing virtual node and subgraph-based methods.
a. The paper positions fractal nodes as novel, but the similarity to virtual node strategies is overwhelming. Virtual nodes [A,B,C] already introduce shortcut aggregation at graph-level. Extensions [D,E,F] directly tackle oversquashing and feature similarity. The paper admits a “single fractal node reduces to a virtual node” but still over-claims novelty.
b. Prior works [G,H,I,J] already leverage graph partitioning or hierarchical subgraphs for efficient propagation. The “fractal” terminology adds little beyond this line of research. The related work section barely acknowledges these connections.
[A] Hwang, EunJeong, et al. "An analysis of virtual nodes in graph neural networks for link prediction." The first learning on graphs conference. 2022.
[B] Fu, Xingbo, et al. "Virtual Nodes Can Help: Tackling Distribution Shifts in Federated Graph Learning." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 39. No. 16. 2025.
[C] He, Yongquan, et al. "VN network: Embedding newly emerging entities with virtual neighbors." Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.
[D] Alon, Uri, and Eran Yahav. "ON THE BOTTLENECK OF GRAPH NEURAL NETWORKS AND ITS PRACTICAL IMPLICATIONS." 9th International Conference on Learning Representations, ICLR 2021. 2021.
[E] Black, Mitchell, et al. "Understanding oversquashing in gnns through the lens of effective resistance." International Conference on Machine Learning. PMLR, 2023.
[F] Karhadkar, Kedar, Pradeep Kr Banerjee, and Guido Montufar. "FoSR: First-order spectral rewiring for addressing oversquashing in GNNs." The Eleventh International Conference on Learning Representations.
[G] Chiang, Wei-Lin, et al. "Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks." Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. 2019.
[H] Gao, Han, et al. "Patchgt: Transformer over non-trainable clusters for learning graph representations." Learning on graphs conference. PMLR, 2022.
[I] Dong, Honghua, et al. "MeGraph: capturing long-range interactions by alternating local and hierarchical aggregation on multi-scaled graph hierarchy." Advances in Neural Information Processing Systems 36 (2023): 63609-63641.
[J] Yeh, Pei-Kai, Hsi-Wen Chen, and Ming-Syan Chen. "Random walk conformer: Learning graph representation from long and short range." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 9. 2023

3. Another major weakness is that the so-called “theoretical contribution” is not genuinely new. The proofs around resistance reduction and signal propagation with fractal nodes are restatements of well-established analyses of oversquashing.
1. Prior works have already formalized effective resistance [A] as a measure of information bottlenecks, and shown that adding global shortcuts or virtual nodes reduces resistance and improves propagation.
2. The paper merely re-derives these results in the context of its specific construction, without offering new mathematical insight or fundamentally stronger guarantees. This makes the theoretical section incremental and more of an application of existing theorems than a novel contribution.
[A] Black, Mitchell, et al. "Understanding oversquashing in gnns through the lens of effective resistance." International Conference on Machine Learning. PMLR, 2023.

4. One missing theoretical component is a formal definition of the compactness of each fractal subgraph and the connectivity among the shortcut “highway” links. At present, the notion of “fractal” is purely descriptive, without a quantitative measure to verify whether the induced subgraphs are actually cohesive or representative. This weakens the theoretical clarity of the work. The authors are encouraged to:
a. Define compactness using standard graph-theoretic metrics such as average shortest-path length, conductance, clustering coefficient, or effective resistance within the subgraph versus across its boundary.
b. Characterize connectivity by measuring the strength of inter-subgraph links using effective resistance, edge expansion, or algebraic connectivity, thereby clarifying whether the shortcuts truly reduce bottlenecks rather than merely adding redundant paths.
c. Analyze the tradeoffs introduced by partition granularity, showing conditions under which the number and size of fractal subgraphs lead to provable improvements in long-range message passing. Without such definitions, the theoretical justification of fractal nodes remains incomplete.

5. The authors are also encouraged to compare with other techniques of long-range message passing (such as [CIKM24, AIStats24]), virtual node such as ([NIPS24, ICLR25]), or subgraph-based (such as [ICML25, AAAI24]) approaches literally and experimentally so that the superiority of fractal node-based MPNN can be revealed.
● Long-range message passing
○ [CIKM24] Jialong Chen, Tianchi Liao, Chuan Chen, and Zibin Zheng. 2024. Improving Message-Passing GNNs by Asynchronous Aggregation. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management (CIKM '24). Association for Computing Machinery, New York, NY, USA, 228–238.
○ [AIStats24] Justin M. Baker, Qingsong Wang, Martin Berzins, Thomas Strohmer, Bao Wang. Monotone Operator Theory-Inspired Message Passing for Learning Long-Range Interaction on Graphs. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:2233-2241, 2024.
● Virtual node-based approaches
○ [NIPS24] Chendi Qian, et al. "Probabilistic graph rewiring via virtual nodes." Advances in Neural Information Processing Systems 37 (2024): 28359-28392.
○ [ICLR25] Joshua Southern, et al. "Understanding Virtual Nodes: Oversquashing and Node Heterogeneity." The Thirteenth International Conference on Learning Representations.
● Subgraph-based approaches
○ [ICML25] Joshua Southern, et al. "Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality." Forty-second International Conference on Machine Learning.
○ [AAAI24] Xu, J., Zhang, A., Bian, Q., Dwivedi, V. P., & Ke, Y. (2024). Union Subgraph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 38(14), 16173-16183.

6. The experimental evaluation is insufficient.
a. The empirical gains are inconsistent and often negligible — improvements of around 1% on benchmarks are not strong enough to justify introducing an entirely new paradigm.
b. The runtime comparisons are misleading, as they ignore the non-trivial preprocessing costs of graph partitioning, which can become prohibitively expensive on large or dynamic graphs.
The chosen benchmarks are limited to small- or medium-scale datasets, offering no evidence that the proposed method generalizes to more diverse and challenging settings, such as heterophilous networks or dynamic graphs.

Reviewer B32V: rating 6, confidence 3

Rating 6, Confidence 3

Review

Summary:
The paper augments MPNNs with fractal nodes: one auxiliary node per partitioned subgraph that aggregates a low-pass (mean) and learnable high-pass residual, with an optional final MLP-Mixer over fractal nodes. This aims to mitigate over-squashing and capture longer-range dependencies at MPNN-like cost. Theory and experiments on benchmarks support the approach.

Strengths:
1. Simple, modular mechanism (LPF/HPF + optional mixer) that drops into standard MPNNs.
3. Clear motivation and a plausible resistance-based argument for alleviating over-squashing.
2. Competitive results vs. graph Transformers with lower memory/runtime; broad ablations.
4. Expressivity tests (e.g., SR25/EXP) show sizable gains over base MPNNs.

Weakness:
1. LPF/HPF interpretation leans on feature-space “mean = DC” rather than graph spectra; framing could confuse readers expecting Laplacian-based notions.
2. Incomplete attribution of gains among (i) shortcuts, (ii) LPF/HPF composition, and (iii) final mixer.
3. Scalability story omits partitioning wall-clock and reuse details; C is crucial but tuning guidance is light.

Questions:
1. What is the partitioning wall-clock on the largest graphs, and is the same partition reused across runs/seeds?
2. With a fixed backbone and C, how much lift comes from (a) LPF only, (b) HPF only, (c) shortcuts without mixer, (d) mixer only?
3. Rule-of-thumb for choosing C; C vs. average graph size where does over-partitioning hurt?

Reviewer xEhn: rating 7, confidence 4

Rating 7, Confidence 4

Review

__Summary__
This paper proposes _fractal nodes_ (FN) to enhance long-range message passing in graph neural networks (GNNs). The key idea is to augment graphs with fractal nodes, auxiliary nodes representing subgraphs, that enforce feature similarity within subgraphs and facilitate long-range information propagation through one-hop shortcut connections and an MLP-Mixer layer. The method leverages graph partitioning (via METIS) to identify subgraph structures reflecting the fractal nature of real-world networks. The authors derive theoretical results showing that fractal nodes reduce effective resistance, improving information flow. Empirical results across synthetic, molecular, image, and large-scale node classification benchmarks show that MPNNs with fractal nodes achieve comparable or superior performance to state-of-the-art Graph Transformers while maintaining linear-time scalability. The paper concludes that fractal nodes offer a practical, efficient alternative to Transformer-based graph models.

__Overall review__
Overall, the paper is technically sound, clearly written, and well-structured. The idea of enforcing subgraph-level feature similarity through fractal nodes is clearly explained, supported by convincing evidence that it mitigates over-squashing and preserves scalability. Experimentally, the breadth of datasets and baselines strengthens the empirical claims. Nonetheless, some aspects could be clarified or improved, including the dependence on the METIS partitioning, the interpretability of the frequency-domain intuition, and comparisons against more adaptive hierarchical approaches (e.g., MeGraph, Coarformer). Overall, I find this paper above the acceptance threshold, particularly for venues emphasizing scalability and theoretical insight in graph learning.

__Questions__
- The connection between fractal nodes and GNN is well explained. In contrast, I'm not sure how Graph Transformers comes into play.
- The idea of incorporating graph partitioning/clustering into GNN is not new - actually quite mature. The authors may consider to discuss the connection with [1,2], if they are related to the current work.

[1] Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. https://dl.acm.org/doi/abs/10.1145/3292500.3330925

[2] Chordal-GCN: Exploiting sparsity in training large-scale graph convolutional networks. https://openreview.net/forum?id=rJl05AVtwB

Reviewer iTGn: rating 8, confidence 3

Rating 8, Confidence 3

Review

This paper introduces Fractal Nodes, a plug-in mechanism that enhances message passing in Graph Neural Networks (GNNs). The core idea is to partition a graph into subgraphs (via METIS), introduce representative “fractal nodes” that aggregate both low- and high-frequency components of subgraph features, and connect these nodes to the original ones. These connections act as shortcuts that alleviate over-squashing while maintaining the efficiency of standard MPNNs. A final-layer MLP-Mixer enables long-range subgraph interactions. Theoretical results show reduced effective resistance and improved expressive power beyond 1-WL; experiments on synthetic, benchmark (LRGB, OGB), and large-scale graphs demonstrate comparable or superior performance to graph Transformers with significantly lower computational cost.

Strengths:

The paper tackles a fundamental problem - balancing local and global patterns in GNNs - and proposes a non-Transformer alternative that is theoretically grounded and empirically strong.

The paper is well-written, with the problem well-motivated and sufficient details for the reader to understand the method.

Weaknesses:

The method's performance relies on a pre-processing step of graph partitioning (using METIS by default). This step is non-learnable and based on heuristics, which may not be optimal for all graphs or tasks. The authors acknowledge this limitation and show robustness to different partitioning algorithms in the appendix, but it remains a dependency.

The number of subgraphs/fractal nodes, \(C\), is a hyperparameter that must be tuned. This lacks adaptivity to graphs of varying structure and scale, where an optimal \(C\) might differ.

Questions:

Could fractal nodes be learned end-to-end rather than pre-partitioned?

Rebuttal and other comments (in time order)

Authors, 2025-10-13

Rebuttal

iTGn
- Learnable partitions are future work, but the ω parameter already provides adaptive feature aggregation within the partition. This paper focuses on METIS.

VQV4, xEhn, iTGn
- Virtual node and cluster-based methods are compared/discussed in App.C and Tables 3&4.

VQV4, xEhn, AI
- METIS partitioning is \(O(|E|)\) and performed once per graph as preprocessing. App.M Table 17 shows that partitioning is trivial for Peptides at 0.71 μs. For ogbn-arxiv, it takes 8.57s, and the time cost is amortized over training.

VQV4, Uk9C, AI
- We apply resistance theory [Black et al. 2023]. Thm4.1-4.2 show fractal nodes reduce resistance via shortcuts (see our App.A&B). The details of signal propagation are in App.F.

xEhn
- Graph Transformers are the standard baseline for long-range dependencies, so we compare against them.

B32V, AI
- We use DFT, not GFT or graph spectral methods. We will clarify this distinction.
- Ablations in Appendix: LPF-only shows degraded performance (Table12); HPF-only is not applicable due to the loss of subgraph context; without-mixer is the FN baseline (Table 14); mixer-only degrades performance, to be added in paper.
- C=32 works robustly (Fig11). METIS balances partitions (Figs12-16). Under-partitioning hurts more than over-partitioning: virtual node (C=1) underperforms (Table4). Corollary B.4 shows that increasing C improves propagation until subgraphs become too small.

VQV4
- We will revise Sec.1 to address long-range dependency from multiple perspectives, emphasizing our RQ1&2.
- App.C quantifies subgraph similarity via centrality distributions, Thm4.1-4.2/App.L show reduced effective resistance, and App.E.5 analyzes partition granularity tradeoffs.
- Our method outperforms compared with other methods ([ICLR25] already in Table4):
- GINE+FN\(_M\) outperforms HyMN-GINE[ICML25] with AP of 0.7018 vs 0.6963 and MAE of 0.2446 vs 0.2457 on Peptides-func and struct, respectively.
- GCN+FN outperforms DRGNN[AIStats24] on CS (95.54 vs 94.89), Physics (97.38 vs 96.96), and Photo (95.87 vs 95.56); surpasses GCN+aSync[CIKM24] on WikiCS (78.41 vs 77.56), Physics (97.38 vs 95.15), and Computer (93.59 vs 87.21).

Uk9C
- Full proofs are in AppL.2-L.3; we will add intuitive sketches to the main paper.

AI - Content Already Addressed (Note: AI showed limited appendix access and hallucinations):
- Theory: App.A-B, App.F (signal propagation)
- MPNN instantiations: App.D
- Scalability: App.J
- Ablations: App.K
- Alternative partitioning: App.L

AI-generated review (AI Review, part of the venue's process)

Meta-review and decision

Phase 2 SPC Recommendation by Senior Program Committee 2RkJ, 2025-10-23

Confidence 4

Metareview

The paper presents an interesting alternative to graph transformers with better computational properties. It provides a strong theoretical grounding and broad, scalable empirical results versus graph transformers. The paper meets the AAAI quality standards.

Acceptance recommendation

This paper is in the bottom 25%-50% of papers presented at a top tier venue like AAAI. (Accept recommendation.)

Phase 2 AC Recommendation by Area Chairs, 2025-10-30

Confidence 4

Metareview

After analyzing the reviews, the rebuttal, and SPC metareview, I recommend acceptance of this paper.

Acceptance recommendation

This paper is in the bottom 25%-50% of papers presented at a top tier venue like AAAI. (Accept recommendation.)

Decision by Program Chairs, 2025-11-07

Decision

Oral