# Fractal-Inspired Message Passing Neural Networks with Fractal Nodes ## Reviewer 7Tfo (2025-06-23) ### 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. **Quality:** 2 **Clarity:** 3 **Significance:** 2 **Originality:** 2 ### 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. **Rating:** 2 **Confidence:** 4 **Paper formatting concerns:** - **Responsible reviewing acknowledgement:** Yes ## Reviewer EzmK (2025-07-03) ### 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 and weaknesses ### 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 **Quality:** 2 **Clarity:** 3 **Significance:** 1 **Originality:** 1 **Questions:** Please refer to the weaknesses. **Limitations:** The authors have addressed the limitations and potential negative societal impact of their work. **Rating:** 2 **Confidence:** 4 **Paper formatting concerns:** N/A **Responsible reviewing acknowledgement:** Yes ## Reviewer hcYU (2025-07-03) ### 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 **Quality:** 2 **Clarity:** 2 **Significance:** 2 **Originality:** 2 ### 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 **Rating:** 2 **Confidence:** 3 **Paper formatting concerns:** No concerns. **Responsible reviewing acknowledgement:** Yes ## Reviewer aBpf (2025-07-15) ### 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. **Quality:** 2 **Clarity:** 3 **Significance:** 2 **Originality:** 2 **Questions:** See Weaknesses. **Limitations:** yes **Rating:** 3 **Confidence:** 3 **Paper formatting concerns:** N/A **Responsible reviewing acknowledgement:** Yes ## Discussion, meta-review and decision (in time order) ### Withdrawal -- 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.