The Underappreciated Power of Vision Models for Graph Structural Understanding

We sincerely thank you for your encouraging review and thoughtful suggestions. We have carefully considered each of your points and provide our responses below.

1. Feature representation through images:

We appreciate your suggestion about encoding discrete labels as colors. Following your recommendation, we implemented a color encoding scheme where node features (e.g., atom types in molecular graphs) were mapped to distinct colors using hash-based assignment for consistency.

We tested this approach across multiple real-world datasets:

Numbers in parentheses indicate change from baseline (without color encoding)

We observed dataset-specific patterns in these preliminary results:

• Consistent improvements on NCI1 (all models: +2.0 to +4.0%) and IMDB-BINARY (3 out of 4 models positive)
• Consistent degradation on IMDB-MULTI (all models: -0.8 to -3.7%)
• Mixed results on ENZYMES and PROTEINS depending on the model

As preliminary results, these patterns show some promise. The consistent improvements on certain datasets suggest that visual feature encoding has potential for specific graph types. The effectiveness appears to be related to the nature of node features (e.g., discrete atom types in NCI1 vs. degree-based features in IMDB datasets).

Importantly, these experiments used our baseline hyperparameters without any tuning for the color encoding scheme. The dataset-specific patterns, combined with the fact that we achieved improvements without optimization, suggest that more sophisticated visual encoding methods with proper hyperparameter tuning could yield better results. We believe developing effective methods to encode node and edge features for visual graph representation remains a promising direction for future research.

2. Robustness studies (corrupting graphs and images):

We greatly appreciate this insightful suggestion. Robustness analysis through systematic corruption of both graph structures and visual representations would indeed provide valuable insights into the different failure modes of GNNs versus vision models. We agree this is an important direction and are currently working on comprehensive robustness experiments involving both graph structural corruptions and visual perturbations. Given the scope of this analysis, we will do our best to provide preliminary results during the discussion phase.

3. Minor comment on benchmark conflation:

Thank you for this suggestion. In Section 4.1, we claim that traditional benchmarks "inadvertently couple domain-specific node features with topology, often allowing models to succeed through feature-based shortcuts." You are right that this deserves empirical validation. Recent work [1,2] provides compelling evidence: replacing molecular graph structures with fixed Cayley graphs resulted in minimal performance drops or even improvements, suggesting that models may sometimes rely more on node features than structural patterns. We conducted complementary feature ablation experiments to further investigate this phenomenon:

Numbers in parentheses indicate change from baseline (with original features)

These preliminary results support [1,2]'s findings, showing varying degrees of feature dependence across benchmarks. This evidence strengthens our motivation for GraphAbstract's pure topology focus.

[1] Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks. ICML 2025.

[2] Graph Neural Networks Use Graphs When They Shouldn’t. ICML 2024.

4. Future directions for hybrid models :

We appreciate your suggestion about combining features and global visual structure. While our current work focuses on establishing the benchmark and demonstrating the potential of visual processing, we agree that hybrid approaches represent an exciting future direction. We will add this to our future work discussion.

Thank you again for your encouraging review. Your constructive suggestions have helped us better articulate our contributions and identify promising extensions. We greatly appreciate your thorough feedback.

We sincerely thank you for your thoughtful and constructive feedback. Your questions highlight important aspects of our work and provide valuable opportunities to better articulate our approach and findings. We address each point below.

Weakness & Q1:Can you demonstrate that the graph layouts capture structural features in a fundamentally different way from conventional GNNs?

Thank you for raising this fundamental question. These two approaches represent different computational pipelines:

• GNNs: Take graph structure (adjacency matrices, edge lists) as input and build understanding through iterative local message passing
• Layout + Vision: Perform global computations upfront (eigendecomposition, energy minimization) to embed graphs in 2D space, then process the resulting geometric patterns

This difference becomes particularly evident when we consider tasks where GNNs have known theoretical limitations. It's noteworthy that when researchers construct counterexamples for the Weisfeiler-Lehman test and its k-dimensional variants, they almost invariably use graph visualizations to illustrate why these graphs are non-isomorphic despite fooling the WL algorithm [1]. This reveals an important truth: visual representations can make structural distinctions immediately apparent that formal iterative refinement procedures miss. Another example comes from the TOGL [2]. In their Figure 1, they claim to present datasets "whose graphs can be easily distinguished by humans." Their NECKLACES dataset shows both classes have the same number of cycles but differ in how these cycles are connected (two individual cycles versus a merged one). According to their theoretical analysis, while humans can immediately see this difference visually, standard message-passing approaches fail to distinguish them. TOGL addresses this by learning sophisticated topological features through persistent homology calculations, but this illustrates our point: what requires complex mathematical machinery for algorithms is claimed to be immediately apparent to human visual perception. Similarly, a set of GNNs provably cannot identify bridges [3]. However, when graphs are visualized, these structures often manifest as immediately recognizable geometric patterns.

While these examples suggest that visual processing can access structural information differently than message passing, establishing rigorous theoretical proof remains challenging. The field currently lacks formal characterizations of what layout algorithms preserve or how this affects learning. Early work like Eades & Lin [4] connected layouts to graph properties, proving that spring algorithms can display geometric automorphisms. However, over the past decades, the graph visualization field has shifted focus toward human aesthetics rather than developing rigorous theory for machine learning applications. This evolution makes establishing a formal theoretical framework challenging at present. Establishing these theoretical foundations remains essential future work.

In our revised manuscript, we will expand our discussion of both the current limitations and future opportunities. Developing formal connections between geometric properties of layouts and learnability guarantees, and designing layouts optimized for machine perception rather than human aesthetics, could establish a new research area bridging graph visualization and machine learning. We believe this represents an exciting direction for the community to explore.

[1] Wang, Y., & Zhang, M. (2023). An empirical study of realized GNN expressiveness. ICML 2024.

[2] Horn, Max, et al. "Topological graph neural networks." ICLR 2022.

[3] Zhang, Bohang, et al. "Rethinking the expressive power of GNNs via graph biconnectivity." ICLR 2023

[4] Eades, P., & Lin, X."Spring algorithms and symmetry." Theoretical Computer Science 2000.

Q2 (Limitation 1): Regarding the processing pipeline and confounding factors: Thank you for your thoughtful analysis regarding the potential confounding factors in our layout-based approach. We appreciate the opportunity to clarify our methodology and provide additional experimental evidence.

Regarding layout algorithm biases, resolution effects, and spatial adjustments:

We understand your concerns about these factors potentially confounding our results. However, we view these not as limitations but as integral components of the visual processing pipeline that provide valuable insights:

1. Layout Algorithm Diversity: We deliberately employed multiple layout algorithms (Kamada-Kawai, ForceAtlas2, Spectral, and Circular) with fundamentally different design principles. An important insight is that these algorithms, despite their diversity, are all designed with human visual preferences in mind - they aim to make graph structures interpretable to human vision. Our finding that vision models outperform basic GNNs across these diverse layouts suggests they successfully exploit this common foundation of visual encoding principles that make graphs comprehensible to human perception, regardless of the specific algorithm used.

As discussed in Section 4.4 and Appendix F, our experiments across multiple layouts serve to provide an initial understanding of which approaches suit different tasks:

• Spectral layouts excel at symmetry detection (8-10% higher accuracy) by naturally manifesting symmetries through geometric arrangements
• Circular layouts enable straightforward symmetry assessment through edge density patterns
• Force-directed methods excel at revealing community structures

This diversity helps practitioners understand which layout-task combinations are most effective, providing practical guidance for future applications.

2. Resolution Robustness: Following your suggestion, we conducted systematic resolution experiments. We selected the challenging symmetry task as a representative example:

Table 1. ResNet Resolution Study - Kamada-Kawai Layout (Symmetry Task)

Table 2. ResNet Resolution Study - Spectral Layout (Symmetry Task)

The approach maintains reasonable performance across different resolutions. Notably, even at 64×64 resolution, both layouts achieve over 70% accuracy on Far-OOD tasks, suggesting practical viability at various computational budgets.

Spatial Encoding: Layout algorithms indeed encode structural information spatially. This is precisely the insight we aim to highlight: different computational pathways (iterative message-passing vs. visual pattern recognition after global layout computation) provide complementary strengths for graph understanding.

Given the exploratory nature of our work, we recognize that we cannot yet provide exhaustive theoretical analysis for all variables in the visual processing pipeline. The graph visualization field has primarily evolved around human aesthetics rather than machine learning objectives, leaving opportunities for future theoretical development. Our empirical evidence across diverse settings points to several promising research directions:

• Developing layout algorithms specifically optimized for machine perception
• Establishing theoretical connections between geometric properties and learnability
• Creating hybrid approaches that combine visual and message-passing strengths

Manuscript Revision Plans: We will enhance our manuscript to better communicate our findings and limitations:

• In Section 4.4, we will emphasize that optimal layout selection for different tasks requires both theoretical foundations and empirical exploration, positioning our work as an initial step in this direction
• In the Introduction, we will more clearly articulate that visual and message-passing approaches offer complementary pathways for graph understanding
• We will expand our limitations section to explicitly discuss the confounding factors you raised

These revisions will help present a more balanced view of our contribution while maintaining the value of our empirical findings.

Q3: Many of the structural features included in your benchmark can be effectively addressed using task-specific optimization methods, such as modularity-based approaches. Can you explain what types of problems cannot be solved simply by selecting and applying such specialized methods tailored to each task?

You correctly note that specialized algorithms (nauty for automorphism, modularity optimization) solve specific tasks optimally. Our focus is different: we examine whether neural models can develop general structural understanding, a capability important for graph foundation models. While specialized algorithms excel at individual tasks, many real-world applications require reasoning about multiple structural properties simultaneously. A unified model that understands various topological patterns could be more practical than maintaining separate algorithms for each property. Our benchmark measures progress toward this general capability, complementing rather than replacing specialized algorithms.

Dear Reviewer Aeju,

As we're in the final day of the discussion period, we hope our rebuttal has helped address your questions.

We truly appreciated your essential question about layout algorithms and have provided detailed explanations and additional experiments in response. Similar questions also arose in our Response Part 2 to Reviewer 3Uke, where we further clarified these points. During this discussion phase, our additional experiments and clarifications helped address other reviewers' concerns, and we hope they have similarly addressed yours.

We're grateful that reviewers recognized our work as having clear and original contributions (Reviewer 3Uke) and being foundational work that addresses an intuitive question in graph learning (Reviewer ofCS). These perspectives resonate with your observation about the "compelling insights into the future direction of graph AI" that our work provides.

If you have any remaining questions about our responses, we'd be happy to discuss further. Of course, we understand if time constraints prevent further engagement.

Thank you again for your valuable review.

Best regards,

The Authors

We sincerely thank the reviewer for the comprehensive and insightful feedback. Your thoughtful comments have been invaluable in helping us improve the quality and clarity of our manuscript. We address each point below.

W1 & Q1: Computational cost analysis

Thank you for this suggestion. We conducted comprehensive experiments on a single A100 GPU across all datasets. Due to space constraints, we present topology classification results as a representative example. The complete analysis will be included in the revised manuscript.

These results help readers understand the computational tradeoffs between model families. While vision models require more resources, their larger capacity and complex architectures also provide opportunities for incorporating diverse graph-specific inductive biases through pre-training or architectural design. The complete cost analysis across all tasks will be included in the revised manuscript.

W2 & Q2: Scenarios in which we would want to predict symmetry or bridge counting that extend beyond GraphAbstract, or why we would want the prediction to generalize from small graphs to bigger graphs.

Thank you for pushing us to clarify the practical relevance.

"Scenarios in which we would want to predict symmetry or bridge counting":

These capabilities serve as diagnostic tests for structural understanding, similar to using arithmetic to assess mathematical reasoning. While not always the direct goal, models lacking these basic capabilities face significant limitations in practice:

• Symmetry blindness: In combinatorial optimization, models unable to recognize symmetries cannot naturally prune equivalent solutions, requiring separate preprocessing to perceive symmetry [1]. This lack of intrinsic understanding prevents the development of truly powerful end-to-end neural solvers.

• Bridge insensitivity: In retrosynthesis, models without awareness of critical connections cannot autonomously identify strategic disconnection points or stability-critical structures. This forces reliance on hand-crafted rules or extensive feature engineering, limiting their ability to discover novel strategies [2].

"Why we would want the prediction to generalize from small graphs to bigger graphs":

Scale generalization tests whether models truly understand structural concepts. Real-world graphs vary dramatically in size, from small molecular fragments with dozens of atoms to large protein complexes with thousands, from local social groups to entire online networks with millions of nodes. A model that cannot recognize fundamental topological properties across these scales hasn't truly learned what defines these structures. This scale-invariant understanding is a hallmark of genuine comprehension: just as humans recognize a chair whether it's a toy or full-sized furniture, a capable graph model should recognize structural patterns regardless of size. Models that fail this test likely rely on superficial pattern matching rather than deep structural understanding.

In summary, our benchmark represents an initial exploration into the vast space of topological capabilities that humans naturally possess. We selected only a small subset of these abilities for early investigation, believing that systematically identifying and measuring these capability gaps provides insights into the current state of graph learning models. Understanding these fundamental capabilities may prove essential as graph learning evolves toward tasks demanding genuine structural reasoning beyond current approaches.

In the revised manuscript, we will:

• Add a dedicated section discussing the relationship between fundamental capabilities and practical limitations
• Clearly position our work as diagnostic rather than immediately applicable
• Expand limitations to acknowledge the gap between our benchmark and real-world impact

[1] When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach. ICLR 2025.

[2] Unbiasing retrosynthesis language models with disconnection prompts. ACS Central Science 2023.

W3 & Q3: CNNs also perform local operations. Why don't they suffer from the same locality problem as GNNs?

You make an important point - CNNs do perform local operations that could be viewed as a form of spatial message passing. The key insight is not that CNNs are fundamentally different in operation, but that the combination of layout preprocessing and CNN processing creates a different computational pathway.

When we examine how CNNs succeed at global tasks in computer vision (scene understanding, object detection), it's through hierarchical feature learning - local edges combine into textures, then shapes, then objects. For graphs, the crucial difference is that layout algorithms already perform global computations before the CNN ever sees the image. Spectral layouts use eigenvectors of the graph Laplacian. Force-directed layouts simulate global energy minimization. These global computations get "baked into" the 2D positions.

So when a CNN processes a graph layout, its local operations are processing the results of global computations. A symmetric graph produces a symmetric layout not by chance, but because the layout algorithm preserves this global property in the spatial arrangement. The CNN then detects this geometric symmetry through local filters(We kindly refer to Weakness & Q1 to Reviewer Aeju for illustrative examples of how this enables visual models to recognize patterns that challenge message-passing approaches.).

This "global-first" approach contrasts with GNNs that must build global understanding from local operations. Interestingly, this explains why positional encodings (PE) help GNNs - they inject pre-computed global information before message passing begins, providing another form of "global-first" mechanism. Our results confirm this insight: PE-enhanced GNNs show significant improvements, though vision models still excel at tasks requiring holistic pattern recognition.

W4 & Q4: Coverage of recent GNN developments

Thank you for this important suggestion about coverage of recent developments. You're right that we should include structure-aware GNNs like subgraph GNNs. We tested I²-GNN as a representative of this approach. The results show it significantly outperforms vanilla GNNs and achieves competitive performance with PE-enhanced models:

The results show that I²-GNN achieves strong performance compared to vanilla message-passing GNNs. Your intuition about pre-computed global information proves particularly insightful here. Regarding your questions about whether "vision models outperform GNNs" or "pre-computed global structural information significantly outperforms innovations in message passing architectures alone," our experiments confirm both: comparing with Table 1 in our paper, vision models maintain overall advantages (e.g., 90.33% vs 63.33% on Far-OOD topology), AND pre-computed global information is indeed crucial for these tasks.

I²-GNN, PE methods, and vision models all benefit from different forms of global structure awareness. We view these not as competing approaches but as complementary paradigms: GNN innovations focus on identifying and addressing theoretical limitations (e.g., WL-expressivity, substructure counting), while vision approaches explore human-like pattern recognition. Each offers unique advantages for different aspects of graph understanding.

In our revision, we will:

• Add a comprehensive related work section covering subgraph GNNs, graph transformers, and positional encoding methods
• Include I²-GNN results in our main comparison tables

W5 & Q5: Code and Dataset Availability

Our apologies for the confusion. Code and datasets are in the supplementary materials. We will add a prominent URL in the abstract and introduction for easier access in the next version.

Q6: Statistical Significance

We will clearly mark (bold/underline) all results within 1 standard deviation of the best performance.

Limitations

You're absolutely right that our limitations section should focus more on model limitations rather than human experiments. We will revise it to discuss: the computational overhead of vision models, and the lack of theoretical foundation connecting layout algorithms to learning guarantees. Establishing such a theory represents an exciting future direction.

Why not Benchmark Track

We chose the main track because our contribution extends beyond the benchmark itself - we provide fundamental insights into how different computational paradigms (message-passing vs. visual pattern recognition) access graph structure. The benchmark serves to validate these insights rather than being the sole contribution.

Nits

Thank you for these helpful suggestions. We will move Table 3 to the main body, improve Figure 2 and Table 1 captions for standalone clarity, and include example graphs from the appendix in the main text.

W3 & Q3: CNNs also perform local operations

You correctly note that CNNs also use local operations. Our scaling experiments suggest that the key difference lies not in model size but in what problem each architecture is solving.

Once graphs are rendered as images via layout algorithms, the task transforms from graph analysis to visual pattern recognition. This is a domain where CNNs inherently excel at capturing global patterns, whether classifying complex objects in ImageNet, understanding entire scene layouts in semantic segmentation, or recognizing faces across different poses and conditions. Just as humans can immediately perceive global patterns in visualized graphs (seeing symmetries, clusters, connectivity strength, and critical bridges at a glance), CNNs process these geometric patterns through their hierarchical architecture. From a computer vision perspective, detecting symmetric patterns, identifying clustered regions, or recognizing bottleneck structures are basic geometric pattern recognition tasks that CNNs handle effectively across many applications.

Supporting observations from our response to Reviewer Aeju: As we detailed in their Weakness & Q1, the difference between these approaches becomes evident when considering tasks with known GNN limitations:

• When researchers construct counterexamples for the WL test, they invariably use visualizations to show why graphs are non-isomorphic, because visual representations make structural distinctions immediately apparent that iterative refinement procedures miss [1]
• Horn et al. [2] explicitly present datasets "whose graphs can be easily distinguished by humans" visually, where structural differences require complex mathematical machinery (persistent homology) for GNNs but are immediately visible to humans
• Bridges, which GNNs provably cannot identify [3], often manifest as obvious visual bottlenecks in layouts

These examples from our community's own practices suggest that layout algorithms transform the problem: from iterative message passing through graph edges to pattern recognition in geometric space, where structural properties become directly observable patterns. We hope this perspective helps explain our findings. While both architectures use local operations, they access and process structural information through different pathways.

We greatly appreciate your thoughtful feedback which motivated these important experiments. We hope this additional analysis addresses your concern about model size being the primary factor and is helpful for your evaluation. Thank you again for your valuable insights that have strengthened our work.

[1] Wang, Y., & Zhang, M. An empirical study of realized GNN expressiveness. ICML 2024.

[2] Horn, Max, et al. "Topological graph neural networks." ICLR 2022.

[3] Zhang, Bohang, et al. "Rethinking the expressive power of GNNs via graph biconnectivity." ICLR 2023.