# Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs ## Reviewer Uk9C (2025-08-28) ### Review **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. **Quality:** This is a fairly good paper. The fractal node method appears, at least in the sense discussed in the paper, a favorable alternative to the costly attention architecture used in graph transformers. The experiments are thorough and demonstrate the strengths of fractal nodes. The paper is well-written and fits into the scope of AAAI. To the extent of the reviewer's understanding, the work appears technically sound, although the lack of proof sketches for the theoretical results is disappointing and gets in the way of verification. **Clarity:** The paper is mostly clear and easy to understand. Some notations are unclear; for example, the function names LPF and HPF are given without explanation for what exactly is abbreviated by these notations. **Originality:** To the knowledge of the reviewer, the theoretical results and experiments in the paper appear novel. **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. **Rating:** 7 **Confidence:** 4 ## Reviewer VQV4 (2025-08-31) ### 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. **Rating:** 5 **Confidence:** 5 ## Reviewer B32V (2025-09-03) ### 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? **Rating:** 6 **Confidence:** 3 ## Reviewer xEhn (2025-10-05) ### 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 **Rating:** 7 **Confidence:** 4 ## Reviewer iTGn (2025-10-05) ### 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? **Rating:** 8 **Confidence:** 3 ## Discussion, meta-review and decision (in time order) ### AI Review -- Reviewer AI (2025-08-27) ### Review **Synopsis of the paper** The paper proposes augmenting message-passing graph neural networks with “fractal nodes,” one per graph partition, that coexist with original nodes and act as subgraph-level representatives. Each fractal node aggregates low- and high-frequency components of its subgraph’s features and then broadcasts back to nodes, creating single-hop shortcut paths that reduce long-range bottlenecks. A final-layer MLP-Mixer optionally mixes the subgraph representatives to enable inter-subgraph interactions without multi-hop message passing. The paper argues this design mitigates over-squashing, increases expressivity beyond standard message passing, and achieves performance competitive with graph Transformers while preserving message-passing efficiency. **Summary of Review** This work tackles a significant problem: enabling long-range interactions in graph learning without incurring the quadratic cost of global attention. The idea of partition-conditioned representative nodes that enforce feature similarity and create shortcuts is elegant, broadly applicable, and empirically compelling across synthetic expressivity tasks, over-squashing benchmarks, LRGB/superpixel/OGB graph-level tasks, and large-scale node classification, with favorable runtime/memory. The resistance-based analysis aligns with known theory and provides a principled lens for the design. That said, several central definitions in Section 3 are ambiguous or internally inconsistent (aggregation set for fractal-node updates, high-pass pooling into a single vector, and final readout for the mixer variant), and the MLP-Mixer complexity analysis omits the token-mixing cost and weight shapes. These issues are correctable without changing the story, and addressing them—along with adding a few clarifications and targeted comparisons—would materially strengthen the paper. **Strengths** - Clear problem formulation and motivation: - The work articulates the tension between local, efficient message passing and the global modeling capacity of graph Transformers, and proposes a concrete, scalable mechanism to bridge this gap by adding subgraph-level representatives derived from graph partitions. - The connection to over-squashing via effective resistance is well chosen, providing a principled grounding for the shortcut design (Black et al., 2023). - Simple, general, and orthogonal plug-in: - Fractal nodes are easily integrated into different message-passing backbones (e.g., GCN, GINE, GatedGCN), with only a per-partition representative and one-hop edges from representatives to subgraph nodes, plus an optional final MLP-Mixer over subgraph tokens. - The “frequency” perspective motivates the combination of low-pass and high-pass components in the subgraph representation. - Theoretical alignment with the design: - The paper states a resistance reduction result $R\_f(u,v) \le R(u,v)$ after augmenting the graph with fractal nodes and uses it to argue improved long-range signal propagation; this leverages a well-established monotonicity of effective resistance under edge additions. - The “mean pooling as low-pass” observation gives an intuitive rationale for augmenting subgraph aggregation with high-frequency components. - Broad and generally strong empirical results: - On synthetic expressivity benchmarks (CSL, EXP, SR25), the fractal-node variant surpasses base MPNNs, supporting the claim that subgraph-aware aggregation increases discriminative power beyond $1$–$3$ WL regimes. - On TreeNeighbourMatch, the methods generalize to deeper trees than base MPNNs, consistent with alleviating over-squashing. - On LRGB, superpixel MNIST/CIFAR-10, and OGB molecular datasets, fractal-node variants tend to improve upon their base MPNNs and are competitive with strong Transformer baselines, including Graph-ViT/MLP-Mixer (He et al., 2023) and Exphormer (Shirzad et al., 2023). - On large-scale node classification (ogbn-arxiv, ogbn-products), the approach scales where some Transformer variants run out of memory and shows accuracy improvements over base GCN/GraphSAGE while reporting training time and memory close to the base models; results include comparisons to SGFormer (Wu et al., 2023b) and PolyNormer (Deng et al., 2024). - Comparisons beyond Transformers: - The paper contrasts against virtual-node and rewiring baselines, with fractal nodes typically outperforming recent virtual node variants and state-of-the-art rewiring methods under the specified budgets. **Weaknesses** - Core mathematical definitions need correction/clarification (important for reproducibility but likely fixable): - Aggregation set for fractal-node update: In Section 3, the update for $f\_c^{(\ell+1)}$ is described as aggregating over all nodes in subgraph $c$, but the equation uses $\mathcal{N}\_v$ (neighbors of an unspecified node) rather than the subgraph node set $V\_c$. This is ill-defined given $f\_c$ is not tied to a particular $v$. The aggregator should be over $V\_c$. - High-pass pooling mismatch: HPF is defined per node as $h\_{v,c}^{(\ell+1)} - \text{LPF}(\cdot)$, but the fractal-node representation adds LPF (a single vector) to a scaled HPF “set,” which is a shape mismatch. If HPF is averaged over $V\_c$, it collapses to $0$ by construction. A non-vanishing pooling over residuals must be specified to produce a single subgraph-level vector (e.g., attention-weighted sum of residuals, mean absolute deviation, variance, or learnable pooling). - Mixer readout: For graph-level prediction with FN\_M, $h\_G$ is written as $\tilde{F}^{(L)}$, which is a $C \times d$ matrix. A pooling over subgraph tokens (e.g., mean, max, or attention pooling) is required to form a vector before the final MLP. - MLP-Mixer specification and complexity: - The equations for the MLP-Mixer omit tensor shapes and do not clearly identify the token- versus channel-mixing steps. With $F^{(L)} \in \mathbb{R}^{C \times d}$, standard MLP-Mixer has token-mixing weights of shape $C \times r$ and $r \times C$ (cost $O(d C r)$, or $O(d C^2)$ without bottleneck) and channel-mixing weights of shape $d \times s$ and $s \times d$ (cost $O(C d s)$, or $O(C d^2)$ without bottleneck). The complexity section only accounts for $O(C d^2)$ and omits the token-mixing term. - Missing assumptions and potential ambiguity in the theoretical presentation: - The “mean pooling as low-pass” statement and the resistance-based signal propagation bound are stated without assumptions in the main text. Typical assumptions include graph connectivity, nonnegative edge weights, and Lipschitz/normalization conditions on the message passing updates. The “signal propagation” inequality, as written, bounds the contraction of pairwise differences, which can be conflated with over-smoothing; the intended notion of “propagation” as influence spread under bottlenecks would benefit from a careful explanation to avoid misinterpretation. - Underspecified implementation details that affect replicability: - The exact aggregation/update functions for fractal nodes and the mechanism to inject $f\_c^{(\ell)}$ back into node states (additive/concatenation/gated/attention) are left abstract; a concrete baseline instantiation in the main text (e.g., for a GCN backbone) would greatly help. - The edge weights on connections between fractal nodes and subgraph nodes are not specified; this matters for both implementation and the resistance analysis. - The definitions of the “signal propagation” metric plotted in Figure 4 and the pipeline for the “normalized frequency response” in Figure 2 are not given in the main text. - Baseline context that would further strengthen positioning: - While many strong Transformer baselines are included (e.g., Graph-ViT/MLP-Mixer, Exphormer, SGFormer, PolyNormer, HSGT, NAGphormer), a closely related bi-level Transformer that explicitly balances intra/inter-cluster interactions (Xing et al., 2024) is not included in the main tables. Given the paper’s partition-based design, a discussion or comparison to such cluster-aware attention would be informative. - Minor presentation issues: - There are a few typos and inconsistencies in table entries and references (e.g., “MOLT2O21” vs. “MOLTOX21,” “GEICO” vs. “GECO,” “CRAWI” vs. “CRaWl,” “Expformer” vs. “Exphormer”). While cosmetic, these make cross-referencing harder. **Suggestions for Improvement** - Correct and make explicit the core equations and readout: - Fractal-node update should aggregate over the subgraph: for example, $f\_c^{(\ell+1)} = \psi\_{FN}^{(\ell)}(f\_c^{(\ell)}, \{ \tilde{h}\_{u,c}^{(\ell+1)} : u \in V\_c \})$. - Define a subgraph-level pooling for the high-pass component that does not collapse to zero. One option is a variance-style or mean-absolute-deviation pooling, e.g., $P(\{r\_v\}) = \frac{1}{|V\_c|}\sum\_{v \in V\_c} |r\_v|$ with $r\_v = h\_{v,c}^{(\ell+1)} - \text{LPF}(\{h\_{u,c}^{(\ell+1)}\})$, or an attention-weighted sum $P(\{r\_v\}) = \sum\_{v \in V\_c} \alpha\_v r\_v$ where $\alpha\_v$ is learned from $r\_v$. Then $f\_c^{(\ell+1)} = \text{LPF}(\{h\_{v,c}^{(\ell+1)}\}) + \omega\_c^{(\ell)} \cdot P(\{r\_v\})$. - For FN\_M, specify $h\_G = \text{Pool}(\tilde{F}^{(L)})$ (e.g., mean/attention pooling across $C$ tokens) followed by $y\_G = \text{MLP}(h\_G)$. - Specify the MLP-Mixer shapes and refine the complexity analysis: - With $F^{(L)} \in \mathbb{R}^{C \times d}$, describe the token-mixing and channel-mixing steps with weight shapes (e.g., token $W\_1 \in \mathbb{R}^{C \times r}$, $W\_2 \in \mathbb{R}^{r \times C}$; channel $W\_3 \in \mathbb{R}^{d \times s}$, $W\_4 \in \mathbb{R}^{s \times d}$), and state the resulting costs $O(d C r)$ and $O(C d s)$. If a bottleneck ($r \ll C$, $s \ll d$) is used, report the chosen $r,s$ per dataset, and add a runtime-vs-$C$ plot to substantiate the “negligible overhead” claim. - State assumptions and clarify the interpretation of the theory: - For the low-pass result, state the conditions (e.g., connected subgraphs and standard graph-Fourier basis). For resistance reduction, explicitly cite Rayleigh monotonicity and specify that added edges are nonnegative. For the signal-propagation bound, list the Lipschitz/normalization assumptions on the message-passing maps, and clarify that the bound is about mitigating information bottlenecks (influence transmission) rather than preserving pairwise feature differences (to avoid confusion with over-smoothing). - Improve replicability by moving one concrete instantiation to the main text: - Present a minimal, complete instantiation for a GCN backbone showing: (i) how $f\_c^{(\ell)}$ is computed (LPF + pooled HPF), (ii) how $f\_c^{(\ell)}$ is injected back into $h\_{v,c}^{(\ell)}$ (e.g., additive residual, concatenation plus linear, gated fusion, or attention), (iii) the edge weights between fractal node $c$ and nodes $v \in V\_c$ (fixed vs. learnable, normalized or not), and (iv) the final FN/FN\_M readout. A compact pseudocode box with tensor shapes would further aid reimplementation. - Define the analysis metrics in the main text: - For Figure 4’s “signal propagation,” specify the exact metric (e.g., how influence is quantified relative to total effective resistance, or how aggregated feature change per unit “resistance mass” is computed). For the “normalized frequency response,” describe the graph-Fourier transform used (eigenbasis, normalization), how responses are aggregated across nodes/graphs, and the normalization procedure. - Broaden context where most relevant and calibrate claims: - Since the design is partition-centric, briefly discuss or, where feasible, compare against bi-level cluster-aware Transformers that explicitly balance intra/inter-cluster interactions (Xing et al., 2024). Even without full experiments, a qualitative positioning (when partition-enforced similarity is advantageous vs. when cluster-level attention helps) would be valuable. - On datasets where Transformer baselines still have an edge (e.g., certain superpixel tasks), phrase claims as “comparable or better in many cases” and discuss potential causes (e.g., limitations of fixed partitioning, need for learnable partitions, or sensitivity to $C$). - Provide practical guidance on partitioning and $C$: - Summarize in the main text the typical $C$ used per dataset, METIS parameters, and a rule-of-thumb for choosing $C$ relative to $|V|$ and graph structure. Highlight the sensitivity findings and partitioning alternatives briefly (e.g., Louvain, Girvan–Newman) and point to the most robust settings observed. - Minor polish: - Standardize names and fix typos in tables and references (e.g., MOLTOX21, GECO, CRaWl, Exphormer). Where two variants (FN vs. FN\_M) are reported, ensure the text consistently attributes improvements to the correct variant. **References** - Black, M., Wan, Z., Nayyeri, A., & Wang, Y. (2023). Understanding oversquashing in GNNs through the lens of effective resistance. In Proceedings of the 40th International Conference on Machine Learning (pp. 2528–2547). PMLR. - Chen, J., Gao, K., Li, G., & He, K. (2023). NAGphormer: A tokenized graph transformer for node classification in large graphs. In The Eleventh International Conference on Learning Representations. - Deng, C., Yue, Z., & Zhang, Z. (2024). PolyNormer: Polynomial-expressive graph transformer in linear time. In International Conference on Learning Representations. - He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., & Bresson, X. (2023). A generalization of ViT/MLP‑Mixer to graphs. In Proceedings of the 40th International Conference on Machine Learning (pp. 12724–12745). PMLR. - Ma, L., Lin, C., Lim, D., Romero‑Soriano, A., Dokania, P. K., Coates, M., Torr, P., & Lim, S.‑N. (2023). Graph inductive biases in transformers without message passing. In Proceedings of the 40th International Conference on Machine Learning (pp. 23321–23337). PMLR. - Rosenbluth, E., Tönshoff, J., Ritzert, M., Kisin, B., & Grohe, M. (2024). Distinguished in uniform: Self-attention vs. virtual nodes. In The Twelfth International Conference on Learning Representations. - Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., & Sinop, A. K. (2023). Exphormer: Sparse transformers for graphs. In Proceedings of the 40th International Conference on Machine Learning (pp. 31613–31632). PMLR. - Wu, Q., Zhao, W., Yang, C., Zhang, H., Nie, F., Jiang, H., Bian, Y., & Yan, J. (2023). SGFormer: Simplifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems, 36. - Xing, Y., Wang, X., Li, Y., Huang, H., & Shi, C. (2024). Less is more: On the over-globalizing problem in graph transformers. In Proceedings of the 41st International Conference on Machine Learning (pp. 54656–54672). PMLR. - Zhu, W., Wen, T., Song, G., Ma, X., & Wang, L. (2023). Hierarchical transformer for scalable graph learning. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (pp. 4702–4710). IJCAI. ### Rebuttal -- 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 ### Phase 2 SPC Recommendation -- Senior Program Committee 2RkJ (2025-10-23) ### 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.) **Confidence:** 4 ### Phase 2 AC Recommendation -- Area Chairs (2025-10-30) **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.) **Confidence:** 4 ### Decision -- Program Chairs (2025-11-07) **Decision:** Oral