The Underappreciated Power of Vision Models for Graph Structural Understanding
Authors: Xinjian Zhao
Wei Pang
Zhongkai Xue
Xiangru Jian
Lei Zhang
Yaoyao Xu
Xiaozhuang Song
Shu Wu
Tianshu Yu
Venue: NeurIPS 2025 poster ()
Keywords: Visual-centric graph understanding
Graph visualization
Meta analysis
Graph positional encoding
Primary area: evaluation
TL;DR: Our meta-analysis reveals vision models' underappreciated potential for graph understanding, offering insights for developing more effective graph learning systems and foundation models based on global structural perception.

Abstract: Graph Neural Networks operate through bottom-up message-passing, fundamentally differing from human visual perception, which intuitively captures global structures first. We investigate the underappreciated potential of vision models for graph understanding, finding they achieve performance comparable to GNNs on established benchmarks while exhibiting distinctly different learning patterns.
These divergent behaviors, combined with limitations of existing benchmarks that conflate domain features with topological understanding, motivate our introduction of GraphAbstract. This benchmark evaluates models' ability to perceive global graph properties as humans do: recognizing organizational archetypes, detecting symmetry, sensing connectivity strength, and identifying critical elements. Our results reveal that vision models significantly outperform GNNs on tasks requiring holistic structural understanding and 
maintain generalizability across varying graph scales, while GNNs struggle with global pattern abstraction and degrade with increasing graph size. This work demonstrates that vision models possess remarkable yet underutilized capabilities for graph structural understanding, particularly for problems requiring global topological awareness and scale-invariant reasoning. These findings open new avenues to leverage this underappreciated potential for developing more effective graph foundation models for tasks dominated by holistic pattern recognition.

The Underappreciated Power of Vision Models for Graph Structural Understanding
Xinjian Zhao Wei Pang"" Zhongkai Xue"", Xiangru Jian Lei Zhang Yaoyao Xu Xiaozhuang Song Shu Wult, Tianshu Yu
& School of Data Science, The Chinese University of Hong Kong, Shenzhen
Institute of Automation, Chinese Academy of Sciences
Cheriton School of Computer Science, University of Waterloo
(xinjianzhaol,
wwwpanggzongkkiiiioe (enngaaaiuee@@ini. cuhk edu. xiangru. jian@uaaterloo.ca yaoyaoxx, xi aoozhuangsonggl/llnnk cuhk, edu. cn
shu wuenlpr ia. en, yutianshu@cuhk, edu. on
Abstract
Graph Neural Networks operate through bottom-up message-passing, fundamen- tally differing from human visual perception, which intuitively captures global structures first. We investigate the underappreciated potential of vision mod- els for graph understanding, finding they achieve performance comparable GNNs on established benchmarks while exhibiting distinctly different learning patterns. These divergent behaviors, combined with limitations existing bench- marks that conflate domain features with topological understanding, motivate our introduction of GraphAbstract. This benchmark evaluates models' ability to perceive global graph properties humans do: recognizing organizational archetypes, detecting symmetry, sensing connectivity strength, and identifying critical elements. Our results reveal that vision models significantly outperform GNNs on tasks requiring holistic structural understanding and maintain general- izability across varying graph scales, while GNNs struggle with global pattern abstraction and degrade with increasing graph size. This work demonstrates that vision models possess remarkable yet underutilized capabilities for graph structural understanding, particularly for problems requiring global topological awareness and scale-invariant reasoning. These findings open new avenues to leverage this underappreciated potential for developing more effective graph foundation mod- els for tasks dominated by holistic pattern recognition. The code is available httpa//ooooooooo-ooo/////aaaalp SaAa----UUSS///aaaaattttreee
https: / thub. com
1 Introduction
Graphs are powerful abstractions to represent complex relationships across entities like social networks [62] and molecular structures [0]. Learning effective representations of these graphs is crucial for node classification, graph classification, and link prediction tasks [51, 67, 42, 34, 54]. Over the past decade, Graph Neural Networks (GNNs) have become the dominant paradigm for graph representation learning, demonstrating impressive performance through their message-passing mechanism that iteratively aggregates local neighborhood information [37, 24, 27, 59, 71J. Despite its success, message passing faces several key limitations, such as limited expressiveness [71, 52, 78] and difficulty in capturing long-range dependencies [2]. Numerous efforts have been trying to address different aspects of the message passing mechanism limitations, graph transformer architectures have
Equal Contribution
Corresponding authors
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

enriched this paradigm by incorporating Long-range interactions across broader graph contexts [16, 39, 74, 68, 50], positional encodings [76, 17. 31] to inject structural priors to improve global topologiaal awareness and graph rewiring techniques mitigate structural bottlenecks in graphs by modifying the topology to enhance information diffusion [58, 48, 5].
However, these advances remain fundamentally constrained by a cognitive discrepancy: While humans intuitively perceive global structures through visual Gestalt principles understanding the whole before analyzing individual parts [57], GNNs and their variants operate through bottom-up processing. Humans instantly recognize ring structures, symmetric structures, and critical bridges in graph visualizations, yet even advanced architectures struggle with such basic topological under- standing [29, 79]. Therefore, although the existing graph learning architecture innovations have made significant progress from both theoretical and practical perspectives, the essence of these efforts is still to identify and repair different aspects of the inherent defects in the message passing mechanism, with limited exploration of vision-based approaches for graph learning despite their natural alignment with how humans perceive network structures.
The flourishing field of computer vision has produced a rich ecosystem of powerful models and techniques that excel at holistic pattern recognition and global structure understanding [45, 7, 36, 38). This vibrant research landscape provides fertile ground for re-imagining graph learning through a visual lens. Inspired by this potential, we explore a fundamentally different approach: leveraging powerful vision models by translating graph topology into the visual domain. By simply rendering graphs as images using standard layout algorithms [22. 14], we apply vision encoders to graph-level tasks without any graph-specific architectural modifications. This vision-based approach mirrors how humans perceive graph structures visually rather than through explicit peessage-passingg operations.
Our evaluations demonstrate that pure vision encoders perform comparably to specialized GNNs on established graph benchmarks, despite having no graph-specific inductive biases or architectural design. This finding is remarkable considering that these vision models operate solely on graph layouts without access node features or explicit connectivity information. However, these traditional benchmarks tightly couple domain knowledge with topology, making it difficult to quantitatively study their separate impacts. As shown by [4, 65]. models using fixed-structure expander graphs rather than the true molecular topology can match or exceed performance on multiple molecular benchmarks, suggesting that node features often dominate over structural information in standard datasets, potentially masking differences in how models perceive graph topology.
To rigorously evaluate topological understanding, we introduce GraphAbstran a benchmark designed to evaluate how well models perceive graph structures in ways that mirror human visual cognition. We present four carefully crafted tasks that challenge models to abstract critical global graph properties in ways humans naturally do: recognizing organizational archetypes, detecting symmetry patterns, sensing connectivity strength, and identifying critical structural elements. For each task, we meticulously design diverse graph families with well-controled topological properties. Our evaluation protocol directly tests -oit--i-iitititiionnn (OOD) generalization by systematically increasing graph sizes from training to testing, evaluating whether models can recognize the same structural patterns regardless of scale, a fundamental capability of human cognition.
Our experiments yield several key findings: On tasks requiring the abstraction of global graph properties, vision models demonstrate significant advantages and superior generalization capabilities across different graph scales compared to GNNs. For GNNs, we find that positional encoding methods that inject structural priors achieve substantial improvements over architectural innovations in message passing. These complementary findings point to a unified insight: successful graph understanding stems from accessing global topological information, either through structural priors or visual perception. This gglobal-first" approach aligns more closely with human cognitive processes for graph understanding, suggesting that future advances in graph representation learning and foundation models may benefit from prioritizing global structural perception over refining local pessage-passing mechanisms. These results open new perspectives for developing graph learning systems that are more effective, interpretable, and capable of generalizing to complex topological structures.
Our main contributions include: (1) demonstrating that vision-based models, which better align with human cognition, achieve strong performance without any graph-specifis architectural modifications; (2) introducing rigorously designed benchmark with diverse graph families that evaluates models' ability to understand graph structures and generalize across varying scales, which is a fundamental ca- pability of human cognition; and (3) revealing that "global-first" first" approaches significantly outperform

---

traditional message- passsing innovations, suggesting promising directions for visual-centric graph understanding.
Related Work
Graph visualization and graph learning. Graph visualization and graph learning have traditionally advanced along separate paths. Visualization focuses on creating human- interprttttr spatial repre- sentations that produce graph layouts through techniques like spectral methods and diree-dieected algorithms, while graph learning focuses on feature extraction with GNNs. Recent studies indicate a convergence between these domains [63, 82, 13, 40, 64). For example, GITA [63], GraphTMM [13], and DPR [40] incorporate visual graph layouts into vision-language models to improve graph rea- soning tasks, DEL [82] introduces probabilistic layout sampling enhance GNN expressivity, and domain-specific approaches explore visual representations for molecular graphs 177, 69J. However, these works directly introduced graph layout into existing architectures such as VLMs and GNNs, treating graph layouts and vision models as black boxes without exploring their fundamental cognitive differences in graph understanding.
Graph learning benchmarks. Graph representation learning has evolved through two complemen- tary benchmark traditions. The first utilizes weal-world datasets from citation networks [73], molecules [47], and comprehensive collections like OGB [30] to evaluate practical performance. The second employs synthetic expressivity tests probe theoretical limitations through challenges like graph isomorphism [1, 3, 61], substructure counting [9]. Recent LLM-oriented graph benchmarks focus on structural analysis tasks such as node counting, cycle detection, and path finding [60, 6, 44]. However, these benchmarks typically rely on a limited set of random graph generators (e.g., Erdös-Rényi, (atts-Strogatz) that inadequately capture topological diversity [60, 40, 19, 44, 8. 70J. The critical gap in existing benchmarks is their inability to assess human like graph cognition, specifically, the intuitive ability to recognize and abstract connectivity patterns across varying scales and contexts.
For brevity, we provide extended discussions of GNN architectures and graph positional encoding methods in Appendix B.
3 Visual vs. Message-Passing: Distinct Cognitive Patterns
We analyze the differences between two model families (GNNs and vision models) in graph tasks from three perspectives: prediction overlap, interpretability case study, and training dynamics & prediction confidence. All models are trained on five graph classification benchmarks [47]. with implementation details provided in Appendix J.1.
Prediction Overlap Analysis. Our experiments across five datasets show that vision models achieve performance competitive with GNNs, as shown in Table 1. However, Figure reveals that while GNN variants behave similarly to each other, GNNs and vision models show distinct prediction patterns: they not only differ in their correct predictions. but often succeed on samples where the other fails. This consistent pattern across all datasets suggests that these two model families develop fundamentally different strategies for processing graph information. The stark contrast in their prediction patterns indicates that GNNs and vision models might be capturing different aspects of graph structure, motivating a deeper investigation into their respective strengths and limitations.
Case Studies. We conduct case studies across multiple benchmark datasets, with detailed analysis presented here using the first three samples from the test set of PROTEINS dataset in Figure 3. We leverage GNN Explainer [75] for graph models and Grad-CAM [53] for vision models, generating visualizations across multiple network layers (2/3/4-layer for GNNs, and low/mid/high-leved features for vision models). The three cases represent distinct structural scenarios commonly found in protein graphs: hierarchical local-to-global patterns, critical bridge structures, and chain-like configurations. Through these visualizations, we observe vision models' remarkable adaptability: exhibiting progres- sive focus from local to regional features in hierarchical structures, maintaining consistent attention on critical bridges across all levels, and adopting a global- cenbriccentricccccoo strategy for chain-like patterns. This flexible processing strategy stands sharp contrast to GNNs, where GNN Explainer shows relatively uniform attention patterns constrained by local message passing. Notably, our studies on ENZYMES dataset (see Appendix J.3) reveal that vision models' attention regions align better with previously identified discriminative patterns [12] compared to GNN-based approaches.
3

---

Table 1: Performance comparison different datasets. Results show the accuracy (%) of different models, reported as mean + std over 5 runs.
Model
NCII
IMDB IMDB-MULTI MULTI
ENZYMES
IMDB-BINARY
PROTEINS
GNN Models
GAT
67.0 = 0.5
49.7 = 1.0
27.0 + 5.9
69.4 2.2
74.1 + 1.5
GIN
70,4 + 1.3
50,9 + 1.7
26.3 3.9
70.0 + 3.0
75.0 + 1.1
GCN
65.4 = 1.1
48.4 = 1.8
25.3 2.2
71.0 = 1.3
74.8 + 1.1
GPS
76.3 1 3.4
50.1 + 2.2
34.3 1:
69.8 1: 2.1
76.0 + 1.2
Vision Models
RESNET
67.7 1.0
51.2 1.1
36.3 1.6
72.2 + 2.2
79.6
2.5
VIT
1.4
50.8 = 3.3
27.3 3.9
71.8
2.8
83.1
0.9
SWIN
0.5
52.0 1 2.0
40.3 3.9
68.8 1
3.5
81.8
1 1.8
ConvNeXt
+.2
53.5 1.3
41.7 + 3.2
73.8
+ 1.6
80.7 + 2.6
Meaiitter Bileettae Duseaa Discantt REAANY
Presialion Flae Discards -NC0
Correct
Smaatay Elssand) PROTTEIE
479
Ereer Gearle (lereend
INDE- BIMARY
Ereer Overlep Olrceet MCI
Errer Oeertes Becord- PROTEIS
ADCE
LiM
CITE
L2T
4M
60 SAA
cale
Figure 1: Prediction overlap analysis across different datasets. Top row: correct prediction overlap; Bottom row: error pattern overlap. GNN variants show high internal consistency, suggesting homogeneous learning behavior, while GNN and Vision models exhibit distinct prediction patterns.
Training dynamics & confidence. We report the training curves in Figure 3 and provide detailed results for all datasets in Appendix J.2. The training dynamics reveal striking differences in learning behaviors across architectures. Vision models, regardless of their specific architectures, demonstrate strong memorization capabilities but with different learning speeds. CNN-based models show aggressive training dynamics, rapidly achieving near-perfect training accuracy while their training loss approaches zero. Transformer-basee models exhibit somewhat slower learning progression, but ultimately reach similar training performance levels. However, all vision models suffer from substantial generalization gaps, with validation accuracy significantly lower than their training performance. GNN variants display notably different learning patterns. Traditional GNNs show more modest training performance, with both training and validation metrics evolving gradually and plateauing lower levels. The GPS model, featuring additional global processing capabilities, achieves higher training accuracy but still exhibits limited validation performance similar to other GNN variants. These empirical observations suggest that the key challenge in vision-bart based graph learning lies not in improving models' pattern recognition capabilities, which are already remarkably strong. but in developing effective mechanisms to bridge the substantial eeemoriatiionggeerallll gap. This consistent pattern across all vision architectures points to fundamental challenge that may require solutions beyond architectural modifications alone, such as specialized pre-training strategies or graph-specific data augmentation techniques.

---

Neiinil funur
Low-tadd Bisd-CAn Pauttrita Vhlnn Hepiiett/eetiii
Dood CAR younolattion Wislen Medell
OCR GIN Saptaner
Wigg
Figure 2: Case Studies for PROTEINS dataset.
Why an intuitive topology benchmark essential. Our analysis shows that different types of models process graphs differently, but existing benchmarks fail to measure how closely these approaches align with human visual perception of graph structures. Current evaluations mix structural understanding with domain-specific features, leading cases where models perform well even with random graph topologies [4]. This gap between intuitive human understanding and current evaluation practices highlights the need for dedicated benchmark to specifically assess intuitive topological perception.
Thining Surnas GDD
Teaknnn Carves SICE
Thunday Caroes fyr dilice MCLL
Teating Carees NCLL
Epicks
Gpods
Thaldiy Carven Resdlct
Trinding Gow Cowkeett/ W1ll
Thiiinn MTT
Thenlin Curven H011
Figure 3: Training dynamics across different architectures NCII dataset. For each model, plot the training loss (bluc), training accuracy (red), and validation accuracy (green) over 100 epochs. The shaded areas represent the standard deviation across multiple runs.
A New Benchmark: GraphAbstract
4.1 Motivation and Design Principles
Building on our analysis of cognitive divergence between model families, we introduce GraphAb- stract, benchmark specifically designed to evaluate fundamental graph understanding capabilities that align with human visual reasoning. Traditional benchmarks in domains like molecular prediction, citation networks, and protein interaction graphs inadvertently couple domain-specific node features with topology, often allowing models to succeed through feature-based shorteuts rather than genuine

---

structural understanding. This limitation becomes particularly evident in recent studies [4, 65], where models using fixed-structure expander graphs rather than true molecular topologies match or exceed performance on multiple benchmarks. The theoretical evaluation of graph neural networks has primarily centered on the Leisaan (WI.) test, which measures a model's s ability to distinguish between pairs of non-isomorphic graphs of the same size. While valuable for theoretical analysis, this approach inherently limited to binary discrimination between fixed-size graph pairs rather than evaluating models' ability to recognize abstract structural patterns across varying scales and contexts. What remains missing is rigorous evaluation framework that targets explicitly models' ability perceive, abstract, and reason about fundamental graph properties in ways that mirror human visual cognition.
GraphAbstract addresses these limitations through four carefully designed tasks that isolate pure structural comprehension from domain-specific attributes. Each task evaluates different aspect of how humans intuitively perceive graphs: recognizing organizational archetypes, detecting symmetry patterns, sensing connectivity strength, and identifying critical structural elements. By focusing on these fundamental perceptual capabilities and systematically varying graph scale between training and testing, we can rigorously assess whether graph learning approaches develop the scale-invariant structural understanding that characterizes human visual cognition.
4.2 Benchmark Details
4.2.1
High-level Topology Classification
The first and core task of our benchmark is high-level topology classification, where models must identify the dominant topological pattern in graph 9 = (V, E). We carefully design six fundamental topological patterns commonly observed in real-world networks, each representing distinct organiza- tional principles that humans can readily identify through visual inspection. This task evaluates a model's ability to perceive global structural organization beyond local connectivity patterns, mirroring how humans naturally identify network archetypes across diverse domains.
The following six graph types represent our core taxonomy of high-level topological patterns: The Cyclic Structure is generated as an annular random geometric graph where nodes are distributed within ring-shaped region and connections are established based on spatial proximity [23]. The Random Geometric Graph structure emerges from spatial constraints, where connections are determined by the proximity of nodes in underlying metric space. This topology is ubiquitous in wireless sensor networks, urban infrastructure, and physical systems governed by geographical limitations [49]. Hierarchical Structures organize nodes into multiple levels where higher tiers have fewer, more densely connected nodes controlling numerous nodes in lower layers. Commu- nity Structures feature multiple densely connected subgroups with relatively sparse inter-group connections, representing common patterns in social networks and biological networks [25]. The Bottleneck Configuration contains critical narrow passages between larger substructures, similar to traffic networks, information flow channels, and metabolic networks. These structures are particularly important for testing models' ability identify crucial connecting components that often represent vulnerability points in real systems. Multicore-periphery Networks [72] exhibit multiple densely connected centers with their respective peripheral nodes, reflecting patterns found in distributed computing systems, multi-center urban structures, and neural networks.
4.2.2 Symmetry Classification
Symmetry perception represents one of the most fundamental pattern recognition capabilities in human cognition. Humans can readily identify symmetric patterns through visual inspection, even without explicit mathematical analysis, when examining graph structures. This capacity has pro- found practical importance across domains: in chemical structures, symmetry determines molecular properties and reactivity; in network design, engineers leverage symmetry for resilience and load balancing; while cryptographers specifically construct asymmetric structures to enhance security. Our Symmetry Classification task challenges models to develop this same intuitive capability by determining whether graph possesses non-trivial symmetry based on its automorphism properties.
To precisely characterize graph symmetry, we employ the concept of graph automorphism. Using the automorphism group, we can precisely categorize graphs based on their symmetry properties:

---

Definition 1 (Graph Automorphism), Given graph G = (V,E), an automorphism is a bijection Ø: V + V such that (u, v) E if and only if (olu). ((v)) E E. The set of all automorphisms forms a group (g) under composition:
Aut(g) ( V + V & bijective and (u, u) E = (o(u), E EE
(1)
Definition 2 (Symmetric and Asymmetric Graphs). A graph is classified symmetric if [
1, indicating the existence of at least one non-identiy automorphism, and asymmetric if Aul(G)] = where the only uutomorphism is the identity mapping.
To construct a diverse symmetry classification dataset, we implement several carefully designed generation strategies for both symmetric and asymmetric graphs. As part of our approach, also extract a collection of base graphs from real-world datasets using multiple sampling strategies to enhance structural diversity, as detailed in Appendix D.1.2. For symmetric graphs, we employ four principled approaches based on group-theoretic constructions. Our first symmetric graph generation method utilizes Cayley graphs, which are constructed from algebraic groups and naturally exhibit rich symmetry properties:
Definition (Cayley Graph). Given a group I and a generating set C where == S-1 (closed under inverses), the Cayley graph Cay(T, has vertices V = I and edges E = {(g gs) g S E S).
Using this definition, we construct Cayley graphs Cay S) where Z,, is the cyclic group of order n and S contains generators of the group (elements coprime to n)) These graphs inherently possess rich symmetry patterns with automorphism groups containing at least elements.
The second approach leverages bipartite double covers, which provide systematic way construct symmetric graphs from arbitrary base graphs:
Definition 4 (Bipartite Double Cover). For a graph G = EV, its bipartite double cover & (V, E) is defined as:
V V x (0.1) ((v,1) DE Vide {0,1)} E O), (v. 1)), ((u, 1), (v. 0)) (u, E F.)
(2)
We generate bipartite double covers from various base graphs, including random graphs, community graphs, bottleneck graphs, and real-world data. Each cover naturally possesses a non-trivial automor- phism a ((v, (v, i) that swaps the two layers, guaranteeing (Aut())] 2 and ensuring the graph is symmetric by definition. Appendix E provides a detailed proof of this property.
Our third method creates symmetric structures through the Cartesian product:
Definition 5 (Cartesian Product). For graphs G1 = (V1, E1) and G2 = (V2, E2), their Cartesian product G UG (V, E) is defined as:
V = 1/2 x 1/2 = {(u, v) u Vi,uE 1/2}
(4)
E' (((11, v). (u2, u)) (wi, u2) E En, V23 U ((l,, v1), (u, v2)) u V1, (v1, 02) E E2)
(5)
We create symmetric graphs through Cartesian products of known symmetric components (e.g., cycle graphs Cn, path graphs P.. star graphs S.), resulting in structures like prism graphs C, DK2 and torus grids C,, For products involving real-world graphs (which we also use to generate asymmetric graphs), we rigorously verify and filter based on the actual automorphism group properties, as the Cartesian product preserves symmetry only when both factor graphs are symmetric.
Additionally, we employ multi-layer cyclic covers using real-world data as base graphs. These covers possess natural cyclic symmetry where the automorphism r((v, i)) (v, (i+ 1) mod k) generates a cyclic group isomorphic to Zz. ensuring [Aut(G&) 2 k. The full mathematical definition and additional properties of these structures are provided in Appendix E.
For asymmetric graphs, we employ two primary strategies. First, we create perturbed graphs using Couble-Edge Swap perturbations [46], where we start with symmetric structures and systematically transform them through edge swaps. Specifically, we repeatedly select two edges (15, Uy) and (vs, v)) and replace them with (v,, v2) and (vk, vy) if these new edges don't 't already exist. After each swap,
7

---

verify both connectivity preservation and symmetry breaking using automorphism group computation. This method maintains the degree distribution of the original graph while disrupting its symmetry structure. Second, we leverage real-world graph patterns through Cartesian products of real-world graphs, whose inherent irregularity typically leads to asymmetric structures.
4.2.3 Spectral Gap Regression
While humans cannot directly "see" mathematical properties of networks, we intuitively perceive net- work conductance, bottleneck structures, and overall connectivity strength through visual inspection. These perceptual judgments closely align with what graph theory formalizes as the spectral gap (2 the second -maallest eigenvalue of the normalized Laplacian matrix [10]. This fundamental parameter quantifies a graph's 's global connectivity characteristics, determining how quickly random walks mix (Imix X 1/22) and providing lower bounds on critical connectivity measures. Our regression task challenges models to develop representations that can infer this abstract property directly from topology, mirroring human ability to estimate network efficiency without explicit computation.
To ensure diverse spectral properties, we generate graphs using stochastic block models with varying mixing parameters, geometric graphs with different connection radii, and configuration models with targeted degree distributions. This design forces models to develop structural intuitions equivalent to understanding that bottlenecked networks (low X²) exhibit restricted information flow, while expander-li like graphs (high X2) enable rapid diffusion. This reflects precisely the type of reasoning humans employ when analyzing network resilience in domains ranging from transportation systems to communication infrastructure.
4.2.4 Bridge Counting
Bridge counting evaluates model's ability to identify critical edges whose removal would increase the number of connected components in a graph. Formally, given graph G = (V, E), we define the
set of bridges B(G) as:
B = {e E E <( {c))> (G))
where k()) denotes the number of connected components in graph g. The objective is to predict [B())), the total number of bridges in the input graph.
This regression task requires models to understand both local edge importance and glohal connectivity patterns. Bridges serve as critical connectors between biconnected components of graph, with each bridge e = (u, r) satisfying the property that there exists no alternative path between u and when e is removed.
The bridge identification challenge varies systematically with graph structure, requiring models to adapt their reasoning across different topological contexts. Models lacking this capability face limitations in practical applications requiring critical connectivity awareness, such as molecular stability analysis and retrosynthetic planning [11, 56].
These four tasks systematically probe models' ability perceive and reason about fundamental graph properties. While representing a subset of human topological capabilities, they provide diagnostic tests for structural understanding that underlies many practical applications. Systematically measuring these capability gaps offers insights into current limitations and directions for developing more robust graph learning models.
4.3 Evaluation Protocol
To rigorously assess the generalization capabilities of graph learning models, we introduce a system- atic evaluation framework incorporating progressively challenging distribution shifts based on graph scale. This framework enables us to quantify how well models can transfer topological understanding across varying graph sizes, capability that humans demonstrate naturally.
Our evaluation includes three test settings of increasing difficulty: ID (I-DDisribuutinn setting uses test graphs containing 20-50 nodes, matching the training distribution. Near-OOD (Near Out-of-Distribution) setting contains graphs with 40-100 nodes, representing a moderate scale shift. Far-OOD (Far
setting features graphs with 60-150 nodes, constituting significant scale shift. These examples challenge models to recognize the same topological patterns at dramatically larger scales, testing their ability to abstract core structural principles independent of
8

---

Table 2: Performance comparison across different tasks and models. First and second best perfor- mances are highlighted in each setting and model family.
Tapulap
Spected
Brstge
-1:mm:3 341
ba 153
1.00 d 1912
GA4 Allgge
5189 1101
4846--5 3.0
40380
60 b01
012511
13975 R1M47
1.9V1-- 360
03.87
0108
71033
1025
GIN--Lgg
4862
1.09 16.15
3.17
67.37
88217
0.1368 RUMES
2.647
8.336
GAI-Lapp
12.09 4.15
06.94
02.35
8.376
5,778 4.3655
445
72.0 6.77
0000 20.30
00.00 4145
8820
24267
0-313
6,340 1,500
GIN-SkaPP4
13:0
14:77 4..50
78.03 8.40
03.9
63.3 2211
00277
5803
03715400115
2.476440330 0-3013
7,0022 4 1/079
GEN-aTE
1333-3210
4477
12:5
61351 101N
ELOED B807T
33632 61344
15.54
12.33 14.5
60.78
1328
1,496 0.9313
LJM43
94.22 1:76
13:85 4.39
1333 12.00
700 L.L
1:1
(8.33 6897
68270 5002
DACEE BL124)
2/2455
GAT
1.5176
4.140
19:38 0.344
07.28 1-46
10.03 20.5
14.0 10.77
88379
0 R
6.006 E3847
BADEA & 86712
1.344
4-3307
4,1000 41.212
VIT
14.00 4190
08:22 1130
9--41:11
9400 LM
10.7
E094 0046
03774 0096
0.154 CUES)
1.30 0.3079
4,7765 4NI2
scale. This evaluation framework serves as an analog to human cognitive flexibility, where people can seamlessly recognize familiar patterns at vastly different scales. For instance, humans can readily identify the same community structure whether it appears in small departmental network of dozens of people or a large organizational chart with hundreds of employees. The ability to maintain consistent performance across these distribution shifts reflects the kind of scale-invariant understanding that advanced graph reasoning systems should aspire to develop.
Baselines. We evaluate two primary model families: graph neural networks and rision-based models. For GNNs, we implement four architectures using one-hot degree encoding as node features: GCN [37], GIN [71], GAT [59], and GPS [50], combined with three positional encoding schemes:
LapPE [17]. SignNet [41]. SPE [31]. For vision-based approaches, we evaluate four backbone architectures: ResNet-50 [28], Swin Transformer- Tiny [43], ViT-B/16 [15], and ConvNeXtV2. Tiny [66], with three graph layout algorithms: Kamada- Kawai [35], Spectral layout [26], and
Kamada-Kawai
ForceAtlas2 [33]. Benchmark statistics, implementation details, and examples of graphs from all four tasks are provided in Appendices C, D, and H, respectively
4.4 Main Results
Our benchmark isolates the challenge of topology understanding from baatuee-based learning prevalent in tasks like node classification and molecular property prediction. This design enables us to focus specifically on evaluating models' capability to comprehend graph structural patterns. Our extensive experiments reveal several key findings.
Vision Models Exhibit Superior Scale-Invariant Understanding. Tables 2 and 3 demonstrate that pure vision-based models show remarkable proficiency abstracting global topological patterns across varying scales. Vision models maintain consistent performance across increasing distribution shifts, while GNNs exhibit severe degradation. On topology classification, vision models drop only 5-6% accuracy from ID to Far-OOD settings, while basic GNNs with one-hot degree feature experience dramatic declines of over 45%. This stark contrast highlights vision models' human- like ability to recognize organizational patterns regardless of scale. The vision advantage is particularly pronounced in symmetry detection, where vision models with spectral layouts achieve 20% higher accuracy than even the best GNN variants. This task directly evaluates a model's capacity to perceive global structural properties that humans naturally identify through visual inspection.
Layout Algorithms Critically Shape Visual Graph Understanding. Different layout algorithms significantly impact how casily humans and models perceive key structural properties. Spectral layouts, for instance, excel at symmetry detection (8-10% higher accuracy than force-directed approaches). Their use of Laplacian eigenvectors often leads to node overlap when visualizing graphs with symmetries or highly repetitive patterns. This simplification of complex structures into more recognizable forms makes global properties more apparent (detailed in Appendix 1.2). Similarly, circular layouts [21], with detailed performance reported in Appendix I.3, arrange nodes in perfect circles. This allows for straightforward symmetry assessment through edge density: symmetric graphs show uniform connections, while in asymmetric graphs, humans can easily spot irregular densities or specific edges that break the symmetry. contrast, force-directed methods like Kamada Kawai prioritize preserving the graph's 's intrinsic shape by optimizing for clear visual

---

Table 3: Performance comparison between KK, ForceAtlas2, and Spectral layout algorithms across different tasks and vision models
Madd
Spected
KX
Spectall
Syedtd AlereAlleed
Spectial
KX
Beste EveeeAliad
Spectrall
1D
Sein
53
2,333 DURIS
1LS520 BA547
1 CADAS
14.00 6.8.9
50.99 9-555
106
04441 C1MB
11843
Nowe 000
27 11440
10.341: 1.00
11. 11.03:00 1:01
00-30 3:143
09.15 & 8:57
01812- DINIZ
1 1.40 8:387
24011 211101
2 0.18
VIT
19.34 13.39:1.43 11.30
10.50 8385
02.07 1301
47 1.99
15.00-
11145 & 8:56
0.923 1UN132
2.636 TUKES
1.505 0.6079
2,0060
2111000
2.59012 0.1645
Fan0000
08.33 4.40
$7.87 0- 16
99:00 (6]
96-7 + 8:17
6. 0.2133
5.5007 +13355
5. 5:3800 - 16.00
13 97
28:08335 18
91.901 DW0
14
11555 OONEL
ILEG 2145
77706 6.1264
5.106 291190
3.M6 0.12.0
separation of nodes and sensible edge routing. This makes individual elements and local relationships more distinguishable, often excelling at revealing community structures and general topological arrangements. These observations highlight the importance of task-aware layout selection in visual graph understanding. Different layout algorithms naturally emphasize different structural properties, suggesting opportunities for developing adaptive visualization strategies that match layout choices to specific reasoning objectives. The intuitions behind how layout algorithms enable vision models to access structural information are discussed Appendix G.
Global Structural Priors Help GNNs Bridge the Cognitive Gap. Our experiments reveal that incorporating positional encodings (PEs) that inject pre-computed global structural information sig- nificantly outperforms innovations in message passing architectures alone. This approach represents an alternative "global-first" strategy within the message-passingg framework, providing GNNs with structural context before local propagation begins. All three PE schemes substantially improve performance and generalization capability, with some advanced PE-enhanced GNNs approaching vision model performance on topology tasks. This finding suggests a unified insight: successful graph understanding fundamentally requires access to global topological information, whether through visual perception or explicitly injected structural priors. It also indicates promising directions for future development where vision models could potentially benefit from more explicit structural priors through specialized pre-training or augmentation strategies that emphasize key topological features.
Computational Trade-offs and Model Capacity. Vision models require approximately 10x more computational time than GNN+PE approaches in our standard experimental setting (detailed in Table 5 of Appendix F). To better attribute the performance differences, we conducted parameter scaling experiments with GPS+SPE, expanding it to match or exceed the vision model capacity. Consistent with known challenges scaling GNNs, performance degraded rather than improved (full results in Table 6 of Appendix F). This confirms that the observed advantages stem from architectural differences, not simply parameter count. The two paradigms understand graph structure through fundamentally different mechanisms: GNNs process topology through abstract message passing and structural priors, while vision models directly recognize patterns in visual representations. The supe- rior out-of- -idt----istriutiion generalization of vision models on glohal structural understanding tasks aligns with this direct pattern recognition approach. When selecting approaches for practical applications, the computational overhead must be weighed against these advantages in scale generalization and structural reasoning.
5 Conclusion
Our work reveals the underappreciated power of vision models for graph structural understanding, demonstrating that vision-based methods better align with human cognitive processes in captur- ing global topological properties. Through GraphAbstract, we systematically quantified these advantages on tasks requiring holistic understanding and scale-invariant reasoning, particularly their ability to maintain consistent performance across varying graph scales. These findings establish visual processing as complementary pathway to traditional graph learning. While GNNs excel through explicit structural priors and domain-speciffe inductive biases, vision models offer distinctive strengths in perceiving global patterns through direct pattern recognition. This suggests promising directions for graph foundation models that integrate visual perception with structural reasoning, combining the strengths of both paradigms for more robust and generalizable graph understanding.
10

---

6 ACKNOWLEDGMENTS
This work is supported in part by the National Natural Science Foundation of China (Grant No. 92470113), and the Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (2023B121201000),
References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The sur- prising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01177 179, 2020.
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. ICLR, 2021.
[3] Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. International Conference Machine Learning, pages 599-608, PMLR, 2021.
[4] Maya Bechler- Speicher, Ido Amos, Ran networks use graphs when they shouldn't In Forty-first International Conference on Machine Learning, 2024.
and Amir Globerson. Graph neural
[5] Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In International Conference on Machine Learning, pages
PMLR, 2023.
[6] Ziwei Chai, Tianjie Zhang, Liang Wu, Kaiqiao Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. Graphllm: Boosting graph reasoning ability of large language model. arXiv preprint 1000v:2310.05845. 2023.
[7] Kai Chen, Jiaqi Wang. Jiangmiao Pang, Yuhang Cao, Yu Xiong, Xiaoxiao Li, Shuyang Sun, Wansen Feng, Ziwei Liu, Jiarui Xu, et al. Mmdetection: Open mmlab detection toolbox and benchmark. arXiv preprint urXiv:1906. 07155,, 2019.
[8] Nuo Chen, Yuhan Li, Jianheng Tang, and Jia Li. Graphwiz: An instruction-followii language model for graph computational problems. In Proceedings of KDD 2024, 2024.
[9] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33: 10100108333953 2020.
[10] Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[11] Connor W Coley, Wengong Jin, Luke Rogers, Timothy F Jamison, Tommi S Jaakkola, William H Green, Regina Barzilay, and Klavs Jensen. A graph-convolutional neural network model for the prediction of chemical reactivity. Chemical science, 10(2):370-377, 2019,,
[12] Xinnan Dai, Haohao Qu, Yifen Shen, Bohang Zhang, Qihao Wen, Wenqi Fan, Dongsheng Li, Jiliang Tang, and Caihua Shan. How do large language models understand graph patterns? a benchmark for graph pattern comprehension. arXiv preprint arXiv:2410.05298, 2024.
[13] Debarati Das, Ishaan Gupta, Jaideep Srivastava, and Dongyeop Kang. Which modality should use text, motif, or image? Understanding graphs with large language models, 2024.
arXiv:2311.099% 1.096622..
[14] Sara Di Bartolomeo, Tarik Crnovrsanin David Saffo, Eduardo Puerta, Connor Wilson, and Cody Dunne. Evaluating graph layout algorithms: A systematic review of methods and best practices. In Computer Graphics Forum, volume 43, page e15073. Wiley Online Library, 2024.
[15] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. image is worth 16x16 words: Transformers for image recognition scale, arXiv preprint 201...000011999 2020.

---

[16] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint M0Xx:20012.09699 2020.
[17] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1 48, 2023.
[18] Peter Eades and Xuemin Lin. Spring algorithms and symmetry. Theoretical Computer Science, 240(2):379 405, 2000.
[19] Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like graph: Encoding graphs for large language models. In Proceedings of ICLRR 2024.
[20] Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems, 35:31376-31390, 2022.
[21] Emden Gansner and Yehuda Koren. Improved circular layouts. In International Symposium on Graph Drawing, pages 386-398. Springer, 2006.
[22] Helen Gibson, Joe Faith, and Paul Vickers. A survey of two-dimensional graph layout techniques for information visualisation. Information visualization, 12(3-4):324-3577 2013.
[23] Alexander P Giles, Orestis Georgiou, and Carl Dettmann. Connectivity of soft random geometric graphs over annuli. Journal of Statistical Physics, 162: 2016.
[24] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. International conference on machine learning. pages 1272. PMLR, 2017.
[25] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks Proceedings of the national academy of sciences, -9812) 2002.
[26] Kenneth M Hall. An r-dimensional quadratic placement algorithm. Management science, 17(3):219-229, 1970.
[27] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[28] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[29] Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. International Conference on Learning Repre- sentations, 2022.
[30] Weihua Hu, Matthias Fey, Marinka Zitiik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 12-2233,,, 2020.
[31] Yinan Huang, William Lu, Joshua Robinson, Yu Yang. Muhan Zhang, Stefanie Jegelka, and Pan
Li. On the stability of expressive positional encodings for graphs. International Conference on Learning Representations, 2024.
[32] Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with i2-gnns. arXiv preprint
2022.
[33] Mathieu Jacomy, Tommaso Venturini, Sebastien Heymann, and Mathieu Bastian. Forceatlas2, a continuous graph layout algorithm for handy network visualization designed for the gephi software. PloS one, 96))998 2014.
[34] Xiangru Jian, Xinjian Zhao, Wei Pang, Chaolong Ying, Yimu Wang, Yaoyao Xu, and Tian- shu Yu. Rethinking spectral augmentation for contrast-based graph self-supervised learning. Transactions on Machine Learning Research, 2025.
12

---

[35] Tomihisa Kamada, Satoru Kawai, et al. An algorithm for drawing general undirected graphs. Information processing letters, 31(1):7-15, 1989.
[36] Salman Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah. Transformers in vision: A survey. ACM computing surveys (CSUR), 54(10s):1-41, 2022.
[37] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.
[38] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C. Berg, Wan- Lo, Piotr Dollár, and Ross Girshick. Segment anything. arXiv:2304.02644 026444400043, 2023.
[39] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létoumeau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Pro- cessing Systems, 34:21618-216233 2021.
[40] Yunxin Li, Baotian Hu, Haoyuan Shi, Wei Wang. Longyue Wang, and Min Zhang. Visiongraph: Leveraging large multimodal models for graph theory problems in visual context. arXiv preprint arXiv:2405.004 04455, 2024.
[41] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. International Conference on Learning Representations, 2023.
[42] Lu Lin, Jinghui Chen, and Hongning Wang. Spectral augmentation for self-supervised learning on graphs. arXiv preprint arXiv:2210.0064. 2022.
[43] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference computer vision, pages 10012-10022, 2021.
[44] Zihan Luo, Xiran Song, Hong Huang, Jianxun Lian, Chenhao Zhang, Jinqi Jiang, and Xing Xie. Graphinstruct: Empowering large language models with graph understanding and reasoning capability, 2024. Ttt1:2403.04448330
[45] Sébastien Marcel and Yann Rodriguez. Torchvision the machine-visse package of torch. In Proceedings of the 18th ACM international conference on Multimedia, pages 1485-1488, 2010.
[46] Sergei Maslov and Kim Sneppen. Specificity and stability in topology of protein networks. Science, 296(5569);910 913, 2002.
[47] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumano. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.086663 2020.
[48] Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning, pages 25956-25979. PMLR, 2023.
[49]
Mathew Penrose. Random geometric graphs, volume 5. OUP Oxford, 2003.
[50] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35: 45011-4555, 2022.
[51] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint 1907: 10903, 2019.
[52] Ryoma Sato. survey on the expressive power of graph neural networks. arXiv preprint a7X1v:2003.04078, 2020.
13

---

[53] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In Proceedings of the IEEE international conference on computer vision, pages 618- 626, 2017.
[54] Harry Shomer, Yao Ma, Haitao Mao, Juanhui Li, Bo Wu, and Jiliang Tang. Lpformer: An adaptive graph transformer for link prediction. In Proceedings of the 30th ACM SICKDD conference on knowledge discovery and data mining, pages 2686-2698, 2024.
[55] Jianheng Tang, Qifan Zhang, Yuhan Li, Nuo Chen, and Jia Li. Grapharena: Evaluating and exploring large language models on graph computation. In The Thirteenth International Conference on Learning Representations, 2025.
[56] Amol Thakkar, Alain C Vaucher, Andrea Byekwaso, Philippe Schwaller, Alessandra Toniato, and Teodoro Laino. Unbiasing retrosynthesis language models with disconnection prompts. ACS Central Science, 9()): ((7):1488-144) 1498, 2023.
[57] Dejan Todorovic. Gestalt principles. Scholarpedia, 3(12):5345, 2008.
[58] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111. 2021.
[59] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 1710. 10903, 2017.
[60] Heng Wang. Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? Advances in Neural Informa- fion Processing Systems,
00808400308611 2023.
[61] Yanbo Wang and Muhan Zhang. An empirical study of realized gnn expressiveness. In Proceedings of the 41st International Conference on Machine Learning, pages 22113-55155, 2024.
[62] Stanley Wasserman and Katherine Faust. Social network analysis: Methods and applications. 1994.
[63] Yanbin Wei, Shuai Fu, Weisen Jiang, Zejian Zhang, Zhixiong Zeng, Qi Wu, James Kwok, and Yu Zhang. Gita: Graph to visual and textual integration for vision- language graph reasoning. Advances in Neural Information Processing Systems, 37:44-72, 2024.
[64] Yanbin Wei, Xuchao Wang, Zhan Zhuang, Yang Chen, Shuhao Chen, Yulong Zhang, Yu Zhang, and James Kwok. Open your eyes: Vision enhances message passing neural networks in link prediction. arXiv preprint 250.:::500000666 2025.
[65] JJ Wilson, Maya Bechler-Speicherr, and Petar Veličković. Cayley graph propagation. arXiv preprint arX0v:2410.033424 2024.
[66] Sanghyun Woo, Shoubhik Debnath, Ronghang Hu, Xinlei Chen, Zhuang Liu, In So Kweon, and Saining Xie. Convnext v2: Co-designing and scaling convnets with masked autoencoders. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 16133-16142, 2023.
[67] Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-27401, 2022.
[68] Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing longerange context for graph neural networks with global attention. Advances in neural information processing systems, 34:13266-13279, 2021.
[69] Hongxin Xiang, Shuting Jin, Jun Xia, Man Zhou, Jianmin Wang, Li Zeng, and Xiangxiang Zeng. An image-enhanced molecular graph representation learning framework. In Proceedings of the Thirty-Thire International Joint Conference on Artificial Intelligence, pages 6107-6115,
2024.
14

---

[70] Hao Xu, Xiangru Jian, Xinjian Zhao, Wei Pang, Chao Zhang, Suyuchen Wang, Qixin Zhang, Zhengyuan Dong, Joao Monteiro, Bang Liu, et al. Graphomni: A comprehensive and extendable benchmark framework for large language models on graph-theoretic tasks. arXiv preprint arXiv:2504. 12764, 2025.
[71] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 2018.
[72] Bowen Yan and Jianxi Luo. Multicores-periphery structure in networks. Nenwork Science, 7(1):70-87, 2019.
[73] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[74] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888. 2021.
[75] Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
[76] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In Interna- tional conference on machine learning, pages 7134-7143. PMLR, 2019.
[77] Xiangxiang Zeng, Hongxin Xiang. Linhui Yu, Jianmin Wang, Kenli Li, Ruth Nussinov, and Feixiong Cheng. Accurate prediction of molecular properties and drug targets using self- supervised image representation learning framework. Nature Machine Intelligence, 4(11): 1004 1016, 2022.
[78] Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, and Zhong Liu. The expressive power of graph neural networks: A survey. IEEE Transactions Knowledge and Data Engineering, 2024.
[79] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. arXiv preprint arXiv:2301.099. 2023.
[80] Muhan Zhang and Pan Li. Nested graph neural networks. Advances Neural Information Processing Systems, 34:15734-15747, 2021.
[81] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. arXiv preprint arXiv:2/ 10.03753, 2021.
[82] Xinjian Zhao, Chaolong Ying. Yaoyao Xu, and Tianshu Yu. Graph learning with distributional edge layouts. In Proceedings of the 31st ACM SIGKDD Conference Knowledge Discovery and Data Mining 1, pages 2066, 2025.
15

---

Appendix
Contents
A Limitations and Future Work
18
A.1 Limitations
18
A.2 Future Work
18
Extended Related Work
18
C Benchmark Statistics
18
Implementation Details
19
D.I Dataset Generation
19
D.1.1
Topology Classification Dataset Generation
................................
19
D.1.2
Symmetry Classification Dataset Generation
20
D.1.3
Spectral Gap Regression
21
D.1.4 Bridge Counting Dataset Generation
................................
22
D.2
Node Features and Positional Encodings
22
D.3
Model Architecture and Hyperparameters
22
D.4
Training Protocol
22
D.5 Graph Image Generation for Vision Models
22
Proof of Symmetry Graph Coverings
23
E.1
Definitions..
23
E.2
Symmetry of Bipartite Double Cover
23
E.3
Symmetry of k-fold Cyclic Cover
................................
24
E,4
Algorithmic Implementation
25
Extended Experimental Results
26
G Discussion: Visual vs. Message-Passing Paradigms
28
H Visualization Examples from GraphAbstract
29
Analysis of Graph Layout Algorithms
31
L.1 Layout Algorithm Details..
31
I.2 Visualizing Asymmetric Graphs
31 ................................
I.3 Characteristics and Performance of Circular Layout
32
Preliminary Experiments and Implementation
33
J.1 Implementation Details of Preliminary Experiments
33
J.2 Training dynamics and confidence
33
16

---

J.3 Case Studies
37
J.4 Heatmap
40
17

---

A Limitations and Future Work
A.1 Limitations
Theoretical Foundations for Layout Algorithms. While our experiments demonstrate that layout algorithms critically shape performance, we lack complete theoretical characterizations of why certain layouts benefit particular reasoning tasks. The relationship between geometric properties of layouts and their learnability by neural networks remains open theoretical question. Early work by Eades Lin [18] connected spring algorithms to geometric automorphisms, but the graph visualization community has since focused primarily on human aesthetics rather than machine learning objectives. Establishing rigorous theoretical frameworks connecting layout properties to learning guarantees represents essential direction for bridging graph visualization and machine learning research.
Human Cognition Alignment: While tasks in Graph are designed to mirror human cognitive capabilities, we do not directly compare model performance with human behavior on these tasks. Future studies could incorporate human experiments (e.g., eye-tracking studies or timed reasoning tasks) to establish quantitative benchmarks for cognitive alignment.
A.2 Future Work
Vision-centric Graph Foundation Models. Our work establishes visual processing viable pathway for graph understanding. demonstrating competitive performance and superior scale general- ization on structural reasoning tasks. Realizing this potential requires developing comprehensive ecosystem for vision-based graph learning, ultimately enabling vision-centric graph foundation models.
Key directions include curating large-scale pretraining datasets of graph visualizations across diverse domains, designing graph-specifie augmentation strategies that preserve topological properties in the visual domain, developing visual encoding schemes for node and edge attributes (e.g., color mapping, size encoding, visual markers), creating specialized architectures optimized for processing graph images, and exploring new application scenarios such as interactive graph visualization and visual graph analytics. Such infrastructure could enable foundation models that leverage visual perception for robust and generalizable structural understanding while incorporating rich semantic information.
B Extended Related Work
Graph Neural Networks and Positional Encodings. Graph Neural Networks have achieved remarkable success across diverse domains through learnable aggregation of neighborhood infor- mation [37, 24, 27, 59, 71J. The field has developed various architectural innovations to enhance structural understanding capabilities. Subgraph-based methods [81, 20, 80, 32] extract features from local structural patterns around nodes. Graph transformers [16, 39, 74, 50] enable broader context aggregation through global attention mechanisms. Particularly relevant to work are positional encodings (PE) that augment graph models with pre-computed global information. Spec- tral approaches [17, 39] leverage Laplacian eigenvectors encode global connectivity patterns. SPE [31] learns continuous soft soft-partition mappings that weight each eigenvector by its eigenvalue, ensuring both provable Lipschitz stability under graph perturbations and universal expressivity for basis-invariant functions. SignNet [41] addresses the ambiguity of eigenvectors by computing node-wise features through learned function, followed by MIPs to produce sign-invariant represen- tations. These methods demonstrate that injecting pre-computed global structural information can substantially improve performance tasks requiring holistic graph understanding.
C Benchmark Statisties
Table 4 provides comprehensive overview of our benchmark statistics across all four tasks. Each task carefully designed with appropriate sample sizes and node ranges to enable robust evaluation. To gain deeper insights into the distribution characteristics of our regression tasks, we visualized the distributions of bridge counts and spectral gaps across different graph types and dataset splits in Figures 4 and 5.
18

---

Table Dataset statistics across our four benchmark tasks. Each cell shows the number of graphs followed by the node count range in parentheses. Topology Classification is a 6-way classification task, Symmetry Classification a 2-way classification task, while Spectral Gap and Bridge Count are regression tasks.
Split
Topology
Symmetry
Spectral Gap
Bridge Count
Train
3000
2000
3000
2500
(20-50)
(30-60)
(20-50)
(20-50)
Val
300
200
300
250
(20-50)
(30-60)
(20-50)
(20-50)
Test (ID)
300
600
300
250
(20-50)
(30-60)
(20-50)
(20-50)
Test (Near-OOD)
300
600
300
250
(40-100)
(50-100)
(40-100)
(40-100)
Test (Far-OOD)
300
600
300
250
(60-150)
(70-150)
(60-150)
(60-150)
arage Ditriactio acress Draph Types Chand
Brigge Disiiaattonn
mddgee Saage--Diirtttttta 1Pw.aeawwwaa.Paaaooooocc (Par-D0))
Figure 4: Distribution of bridge counts across different graph types under various settings (Train, ID, Near-OOD, and Far-OOD). The plots reveal distinct bridge count patterns for each graph structure (Geometric, Community, Hierarchical, Bottleneck, and Multicore). Notably, the distributions exhibit shifts graph sizes increase, particularly visible in the OOD scenarios.
D Implementation Details
This appendix provides comprehensive implementation details for our benchmark tasks, including dataset generation methodology, model architectures, and training protocols.
D.1
Dataset Generation
Our benchmark consists of four distinct graph understanding tasks. For each task, we generate three test sets with varying difficulty: ID (same distribution training), Near-OOD (moderate distribution shift), and Far-OOD (significant distribution shift). All datasets are implemented using Py PyTorc Geometric.
D.1.1 Topology Classification Dataset Generation
For the topology classification task, we implemented six distinct topology generators, each producing graphs with visually and structurally distinct patterns.
Cyclic Structure. We generate annular random geometric graphs (ARGG) with inner radius randomly sampled from [0.7,1.2 1.2]. outer radius set as Pinner + random (0.05, (0.05, 0.3), and connection radius randomly sampled from [0.5, 0.8].
Random Geometric Graph. Nodes are distributed uniformly unit square with connection radius randomly sampled from 10.15, 0.25). Connections are established between nodes within this radius of each other. We ensure connectedness by adding edges between disconnected components necessary.
19

---

Spentraat Sup
deneen coapiig Reunee Road
Keder Becraii
dedeecttio Rale
Rode
Figure 5: Distribution of spectral gaps across different graph types under various settings (Train, ID, Near-OOD, and Far-OOD). The plots reveal distinct spectral gap patterns for each graph structure. Notably, the distributions exhibit shifts as graph sizes increase.
Community Structure. We generate communities with 3 to 5 groups (based on graph size), intra- community edge probability from [0.6, 0.8]. and inter-community edge probability from [0.01, 0.05]. This creates densely connected communities with sparse connections between them, reflecting real-world community structures.
Hierarchical Hub Structure. We implement a multi-level hierarchical organization with levels. Level size ratio decreases by a factor of approximately 0.4 with higher levels. Intra-level connectivity decreases for lower levels, calculated as 0.7 x num levels-lese Each node connects to 1-3 num levels
nodes in the level above it, creating graphs with clear hierarchical organization from top to bottom.
Bottleneck Structure, We generate bottleneck topologies with 2 to 4 communities, intra-community edge probability from [0.4. 0.6], and bottleneck width of 1 to 3nodes connecting adjacent communities. This creates graphs with distinct modules connected by narrow pathways.
Multi-core Periphery Structure. We generate multi-core networks with 2 to 3 cores occupying 50-60% of total nodes (minimum 4 nodes per core). Core internal probability ranges from [0.6, 0.8) with 1-2 bridging nodes between each core pair. Periphery nodes are randomly connected to 1-2 nodes in a randomly selected core, creating structures with multiple highly connected centers surrounded by sparsely connected peripheral nodes.
D.1.2 Symmetry Classification Dataset Generation
For symmetry classification, we employ several theoretically grounded approaches to generate both symmetric and asymmetric graphs.
Real-world Base Graph Extraction. To enhance diversity and realism in our generated graphs, we
extracted collection of base graphs from real-world datasets. For MUTAG, we directly utilized the molecular graphs. For Cora, which is a large citation network, we employed three different sampling techniques obtain diverse set of subgraphs: (1) BFS sampling from random starting nodes. (2)
Random walks with restart probability a 0.2, which were explored by previous work [55]. (3) TraphSAGE-styylle neighborhood sampling with controlled layer expansion. For each target node size range (5-50 nodes), we ensured sufficient number of base graphs (approximately 30 graphs per size) to support subsequent operations like Cartesian products and graph covers. These real-world base graphs were cached and reused across different generation methods, providing consistent structural patterns while maintaining diversity. All base graphs were processed to ensure connectedness, and their node indices were normalized to ensure compatibility with our generation pipelines.
We implemented five distinct methods generate symmetric graphs:
Cayley Cyclic Graphs. We construct Cayley graphs based on cyclic groups Z,,, For a given node count n, we identify valid generators (clements coprime to n), randomly select 1-3 generators, and create connections according to the Cayley graph definition. Each node i E Z,, is connected to nodes (i+ g) mod n and (i g) mod n for each generator g. ensuring that the graph exhibits the algebraic symmetry of the cyclic group
We create bipartite double covers from various base graphs (random graphs, community structures, bottleneck structures, and real-world data). For a base graph 9 = (V, F), the bipartite double cover ğ = (V, Æ) is constructed with V V 0, 1 and edges (u,, 0), (v, 1)), ((,, 1), (v. 0)) (u, v) E. Base graphs have approximately half the target node
Bipartite Double Cover.
20

---

count. For random base graphs, edge probability is from [0.15, 0.3]. For Community-based graphs, intra-community probability is from [0.3, 0.7] and momem-communtty probability from [0.05, 0.15]. For bottleneck base graphs, internal connectivity probability is from [0.3, 0.6, with bottleneck width of 1-3 nodes.
Cartesian Product. We generate cartesian products of known symmetric components with combina- tions including cycle graphs C, (cycle L path), C,, (cycle [J cycle), and US (path D star). The cartesian product G G2 contains vertices (GG) x V(2) with edges between (u,, v1) and (u2, U2)) if either 11 = Ug and (#1. 02) E E(G2), or 01 = 02 and (u1, U2) E E(G)). Factors are chosen to optimize the product size to be close to the target node count.
Cartesian Product with Real Data. We compute Cartesian products using real-world graph data, selected from the MUTAG and Cora datasets. is important to note that the Cartesian product preserves symmetry only when both base graphs are symmetrie. Since real-world graphs typically lack perfect symmetry, we use the pynauty' library to verify the symmetry of each generated graph and filter accordingly. The introduction of wooldworld& graphs enables to generate more diverse and structurally realistic graphs, including both symmetric and asymmetric variants with complex topological features that purely synthetic generators cannot easily produce.
Real Data Cyclic Cover. We construct k-fold cyclic covers using real data as base graphs, with the number of layers (k) from 2 to 5 based on target size. For base graph G = EV. the k-fold cyclic cover creates & copies of with edges connecting corresponding vertices across consecutive layers in cyclic pattem. Formally, vertices in the cover are V x Zk. and for each edge (u, v) E F,, we add edges ((u, i). (t, (i + 1) mod k:) and ((v, i), (u, (i + 1) mod k)) for all E Z4.-
We implemented two primary approaches to generate asymmetric graphs:
Perturbed Asymmetric Graphs. We start with symmetric graphs and apply targeted edge perturba- tions via double-edge swap operations. We select two edges (a, b) and (c, d) and replace them with edges (a, d) and (c, b) if they don't already exist. This operation maintains the degree distribution while potentially breaking symmetry. We verify that connectivity is preserved and symmetry is broken, applying up to 20 swap attempts. Each generated graph is verified to ensure [Aut(G)| 1. meaning the only automorphism is the identity mapping.
Cartesian Products with Real Graphs. We leverage the inherent asymmetry of real-world data through Cartesian products involving the previously extracted wollw networks. It's important to note that while the Cartesian product operation naturally creates repeating structural patterns (as each vertex from one graph is combined with every vertex from the other graph), these repeating patterns do not necessarily translate into mathematical symmetry (automorphisms) The resulting structure may contain similar local neighborhoods but still lack the global permutation invariance required for true symmetry. This distinction is crucial Cartesian products create structural regularity that can be challenging for models to analyze, but often without introducing the simplifying symmetry properties that might make the task easier. All generated graphs are rigorously verified using pynauty to confirm their asymmetric nature (lAut(G)) 1) before inclusion in the dataset.
D.1.3 Spectral Gap Regression
For spectral gap regression, we employed mixture of techniques to generate graphs with diverse spectral properties:
Using Stochastic Block Models(SBM) with controlled mixing, including SBM- dumbbell structure (two equal-sized communities) and SBM-multi communities structure (3-5 communities). Within-block probability ranges from [0.6, 0.8]. Between-block probability varies with mixing parameter μ E [0, 1]: [0.001, 0.02] when μ < 0.1, [0.02, 0.1] when μ < 0.3, [0.1, 0.3] when μ < 0.7, and [0.3, /4] when μ 2 0.7. The spectral gap X2 of these graphs is strongly influenced by the netween-block connectivity.
SBM Evolution.
Modified random geometric graphs with base radius calculated to ensure basic connectivity. Additional connections added based on mixing parameter μ. with the number of extra connections approximately equal to μ x 0.1 x n x In(n). Higher μ values create more small-world-lik properties, affecting the spectral gap.
Geometric Evolution.
'nngss//gthub.ccm///bbbaa/yyy
21

---

Configuration Model. Starting with an SBM or geometric base graph, we rewire edges using the configuration model while preserving the degree distribution. The randomization level controls the fraction of edges rewired, ranging from [0.3. 0.8]. This process disrupts the original structure while maintaining the degree sequence, often resulting in graphs with different spectral properties.
To ensure comprehensive coverage of the spectral gap value range, we strategically sample the mixing parameter y., with 40% of samples using low connectivity (μ < 0.2), 30% using medium connectivity (p E [0.2, 0.5)), and 30% using higher connectivity (μ E [0.5, 0.8)). The spectral gap X2 is computed as the second-smallest eigenvalue of the normalized Laplacian matrix L = 1 D-1--------- where the degree matrix and the adjacency matrix.
D.1.4 Bridge Counting Dataset Generation
For the bridge counting task, we generate diverse graph structures using five topology generators similar those used in the topology classification task. These include Random Geometric Graphs with connection radius E [0.15, 0.25], Community Structures with 3-5 communities and controlled density parameters, Hierarchical Structures with 2-4 levels, Bottleneck Configurations with single- connection bottlenecks between adjacent communities, and Multi-core Structures with 2-3 cores and peripheral attachments. For each graph, we compute the exact number of bridges using NetworkX's bridge detection algorithm", which identifies edges whose removal would increase the number of connected components in the graph.
D.2 Node Features and Positional Encodings
All positional encodings are incorporated into our GNN models with 16 dimensions. For node features, we use one-hot degree encoding with a maximum degree of 100 across all graph datasets.
D.3 Model Architecture and Hyperparameters
For our graph neural network models, we experiment with varying numbers of layers ranging from 2 to 4, with consistent hidden dimension size of 128 across all architectures. Dropout with rate of 0.5 is applied throughout the networks to prevent overfitting. For vision-based models, we use standard architectures: ResNet-50, ViT-B/16, Swin Transformer-Tnng and ConvNeXIV2-Ting All models resize graph images to 224x224 resolution as input.
D.4 Training Protocol
All models are trained with batch size of 128 for maximum of 200 epochs, employing early stopping with patience of 30 epochs to prevent overfitting. We use the Adam optimizer with different learning rates: le for vision backbone parameters, 1e - for GNN models and classifier heads. Weight decay is set to le 1e-4 for vision models. For classification tasks (Topology, Symmetry), use cross-entropy loss, while for regression tasks (Spectral Gap. Bridge Counting), we employ mean squared error loss. All experiments are conducted on NVIDIA A800 GPUs. For consistent evaluation, measure accuracy for classification tasks, while regression tasks use Mean Absolute Error (MAE). To ensure reproducibility, we set fixed random seeds e [0, 1, 2, 4] for all experiments, controlling the initialization of model parameters, data splitting.
D.5 Graph Image Generation for Vision Models
For vision-based models, we render graph visualizations with specific parameters to ensure visual consistency. Nodes rendered skyblue circles with white borders and size 50, while edges rendered as white lines with width 1.5 and alpha 0.8. Each graph is rendered once for each dataset split, ensuring consistent visual representation across training and evaluation.
hhtps://networkx.org
22

---

E Proof of Symmetry in Graph Coverings
In this section, we provide formal proofs of the symmetry properties stated in the main text. For notational simplicity, we use H to denote cover graph throughout these proofs. This corresponds to G (bipartite double cover) and Gj (k-fold cyclic cover) in the main text.
E.1 Definitions
Definition (Automorphiss). An automorphism of a graph & is bijection Φ V(G) V()) such that for any E (G):
(u, E F(g) = (ó(u), ((v)) E F(G)
(7)
Definition (Automorphism Group). The set of all automorphisms g, denoted (am group under function composition.
Definition 3 (Symmetry). A graph G is symmetric if [Aut(G)) > 1, i.e., it admits at least one non-identity automorphism.
Definition 4 (Bipartite Double Cover). For graph G, its bipartite double cover H is constructed by:
Creating two vertices (v, 0) and (v, 1) in H for each vertex v in G
Creating edges ((u, 0), (v, 1)) and ((u, 1), (v, 0)) in H for each edge (u, v) in G
Definition (I--fold Cyclic Cover). For a graph G (without self-loops), its k-fold cyclic cover H is constructed by:
Creating k vertices (v, 0), (v,, 1),..., ,.....,,, (v, - 1) in H for each vertex u in G
Creating edges ((u, i), (v, (i + 1) mod k)) and ((v, 1), (u, (i+ 1) mod k)) in for each edge (u, v) in G and each i {0, 10,1,...,44
E.2 Symmetry of Bipartite Double Cover
Theorem 1. For any graph G, its bipartite double cover H satisfies [Aut(H)] >
Proof. We define mapping o V(H) - (HH as follows:
d((,,)) (v.
Ve V 10,
(8)
Step 1: We prove a is bijection.
Since for each (v, i) (HH,, maps exactly element (v, 1 i) V(H), and since (oo((v, i))) = ((v i)) = (), a is its own inverse. Therefore, is a bijection.
Step 2:
We verify preserves edges.
For any edge ((u, i). (v, E E(H), by the definition double cover:
(u,v) E E(g) and j
(9)
Applying to both endpoints:
a(u, i)) = 1- and o(v.j)) o(1v, - 1)) -0,,)
(10)
Since (u,w) E E(g), by the definition of double cover:
((v, 1- (1, E E(H)
(11)
Thus, (a(u, ((,,)) E B(H).
Step 3: We verify preserves non-edges. For any non-edge ((u, i), (v,j)) & E(H). there are two cases:
1. (u, E(G): Then ((u, i), (v, 1-
- 5)) & E(H) by definition of double cover.
23

---

2. (u, E E(g) but j + 1 i: Then either = = 0 or i = = 1. After applying ø, we have ((u, i)) (u, and (((e,)) (v, j].. Since - 1--3 J. have (a(u, (1,,)) F(H).
Step 4: We show is not the identity mapping. For any vertex (v, 0) E V(H):
or ((v. 0)) = (v, 1) (v,0)
(12)
Therefore, is a non-identity automorphism of H, which proves [Aut(H)) > 1.
Corollary 1. Afl m, then (Au 2 2m.
Proof. Every automorphism @ Au)(G) induces two automorphisms on H:
((v, i)) ()( and Φ2((v, (o(v),
(13)
These 2m automorphisms all distinct, hence [Aut(H)] 2 2m.
E.3
Symmetry of k--fold Cyelic Cover
Lemma 1. For k 2 2, the map V(H) + (HH defined by ((v, i)) = (v, (i+ mod k) is an automorphism of the k-fold cyclic cover H of any graph g.
Proof. Step 1: We prove is a bijection,
For each (v E VHH), T maps to exactly one element (u, (i + 1) mod k). The inverse is defined by 7- ((,, i)) (v, (i - 1) mod k). Hence, is bijection.
Step 2: We verify 7 preserves edges.
Let e ((u, i), (v. 1) mod k)) EH). By definition of k-fold cover, (u, e) E(G).
Applying 7 to both endpoints:
T(u,, i)) (u, (i 1) mod k)
(14)
T(vu, (i+ 1) mod k)) (v, (i 2) mod k)
Since (u, v) E E(G), by definition of k-fold cover:
(u,, (i + 1) mod k),, (v, (i + 2) mod k)) E E(H)
(15)
Step 3: We verify 7 preserves non-edges.
For any non-edge ((u, i), (v,j)) & E(H), there two
1. (u, E(G): Then ((u, (t + 1) mod k), (v. (j + 1) mod k)) & E(H) by definition.
2. v, F(G)) but j * (i + 1) mod k: After applying 7, we have
T((u, i)) (u. (i 1) mod k) +((,,)) (v, 1) mod k))
(16)
Since (j+1) mod k # (i+2) mod k when j * (i+1) mod k, we have (r(u, i), (v) E(H)).
g
Step 4: For k > 2, T not the identity mapping.
For any vertex (v,0) 0) E (HH):
T((U, 0)) (v. 1) + (v.0)
(17)
Therefore, is non-identity automorphism of H.
Theorem 2. For any graph G and 2 2, the k-fold cyclic cover H admits an automorphism group containing subgroup isomorphic to Lt, thus satisfying AAut(H) (H) 2 k.
24

---

Proof. Consider the mappings T, T. ..... ,k. , where T is the automorphism defined in the lemma above. We have:
((v, (v, (i+ mod k))
(18)
Step 1:
The mappings 7" id. ,1,,,,,? . are all distinct.
For j1 < j2 k, there exists (v, 0) (H) such that:
(" 0)) = (v. + (u. = (2. ((v,0)))))
(19)
Step 2: These mappings form cyclic subgroup of order k. Since ("v i)) = (u. (i + k) mod k) = (u, i), we have 7*t = id. This means 7 generates a cyclic group of order l isomorphic to Σμ.
Therefore, Au)(H) contains subgroup isomorphic to Zu. implying [ut((H) 2
E,4 Algorithmic Implementation
The implementation of graph coverings in our code precisely follows the mathematical constructions in the above definitions:
Algorithm Generate Bipartite Double Cover
Require: Base graph G(V, E)) Ensure: Double cover graph
1: Initialize H as empty graph
2: for each E V do
3: Add vertices (v, 0) and (v, 1) to H
4: end for
5: for each v) E E do
6: Add edges ((u, 0), (v, 1)) and ((u, 1), (u, 0)) to
7: end for
8: return H
Algorithm 2 Generate k-fold Cyclic Cover from Real-world Network
Require: Real-world base graph GVV, E), integer k 2 2
Ensure: k-fold cyclic cover graph H
1: Initialize H as empty graph
2: for each v E V do
to k do 4: Add vertex (v. i) to H
3: for
5: end for
6: end for
7: for each (u, E E do
8: for = 0 k do
9: Add edges (uu, i), (v, (i + 1) mod k)) and ((v,2), (u, (i 1) mod k)) to
10: end for
11: end for
12: return H
25

---

F Extended Experimental Results
This section provides detailed experimental results that support our main findings, including compre- hensive computational cost analysis, model scaling experiments, advanced GNN comparisons, and resolution robustness studies.
Computational Cost Analysis. Table 5 presents a detailed breakdown of computational requirements across all four benchmark tasks. We report both time per epoch and total time reach best validation accuracy. Vision models require approximately 10x more time per epoch than GNN+SPE models across all tasks, with the ratio ranging from 8.2x 12.2x depending computational overhead primarily stems from the larger model capacity and more complex feature extraction in vision backbones compared compact GNN architectures.
the specific task. This
Model Scaling Analysis. To investigate whether performance differences stem from model capacity, conducted systematic scaling experiments with GPS+SPE. Table 6 shows results for models with 53.2M and 212.2M parameters, substantially exceeding vision model sizes (ResNet-50) 25.6M). Con- sistent with known limitations of cessage-passingg architectures, performance degraded rather than improved with increased capacity across all tasks. For topology classification, accuracy dropped from 84.80% (baseline) to 82.53% (212.2M model) Near-OOD tasks. This confirms that architectural differences, rather than parameter count, drive the observed advantages of vision models.
Comparison with Advanced GNNs. Table 7 compares results with I2-GNN [32], an advanced structure-aware GNN. While F-GNN achieves competitive in-distribution performance, shows significantly worse generalization demonstrates that even advanced GNN architectures with enhanced expressiveness face challenges in scale generalization compared vision vision-based approaches.
out-of-distribution tasks, particularly Far-OOD settings. This
Resolution Robustness. Table 8 examines how image resolution affects vision model performance. Performance remains relatively stable across different resolutions (64x64 to 448x448),, with some tasks even performing better at lower resolutions. This suggests that the structural patterns captured by vision models robust to resolution changes, and extremely high resolution may not be necessary for graph structural understanding tasks.
Table 5: Computational cost analysis across all benchmark tasks, showing time per epoch and time to best validation accuracy.
Model
Taoch (s)
Topelogy
Time Best
TamerEpoch (s)
Symmetry
Time to Best (5)
Time
Bridge
Time to Best (5)
Time/Epocha (s)
Spectral Gap
Time to Bes (5)
ConyNeXt
13.1
329.5
9.4
245.2
11.2
533.6
13.2
717.7
RedNet
5.5
130.7
4.2
76.5
4A
137.5
5.6
$12.0
Swin
11.5
368.9
123.1
9.3
227.1
11.6
348.1
VIT
23.1
509.9
15.8
127,0
19.5
858.5
23.2
1129.7
GAT-SPE
1.2
16.3
2.5
1.2
107.7
GCN-SPE
35.1
$6.0
GPS-SPE
Ang. Vision
446.7
629.4
Agg. SNE+SPE
51.5
10.5x
26

---

Table 6: Model scaling analysis across all benchmark tasks. Scaled GPS+SPE models show degraded performance compared to baseline, confirming that architectural constraints rather than parameter count limit GNN performance.
Task
Model
Near-OOD
Far-OOD
Bascline GPS+SPE
84.80 13.75
84.07 16.04
72.20 14.51
GPS+SPE (53.2M)
87.73 + 6.87
70.13 = 13.03
40.33 # 11.06
Topology (%)
GPS+SPE (212.2M)
82.53 + 5.58
66.20 = 11.42
34,80 + 8.16
ResNet (25.6M)
95,87 + 0.62
96.27 1.02
87.40 3.33
Baseline GPS+SPE
71.97 = 1.65
70,67 = 1.23
67.70 + 1.37
GPS+SPE (53.2M)
65.83 2.21 2.21
65,83 2.83
67.63 3.94
Symmetry (%)
GPS+SPE (212.2M)
56.10 4.47
55.67 5.75
54,97
ResNet (25.6M)
93.47 = 0.66
88.83 0.64
84.20 + 0.39
Baseline GPS+SPE
0.0681 0.0298
0.1537 = 0.0839
0.6716 + 0.2709
GPS+SPE (53.2M)
0.1483 0.0210
0.1901 # 0.0167
0.7497 # 0.4243
Spectral Gap (MAE)
GPS+SPE (212.2M)
0.1214 0.0365
0.2125 = 0.0373
0.9101 = 0.5625
ResNet (25.6M)
0.0335 0.0021
0.0600 0.0063
0.1102 0.0100
Bascline GPS+SPE
0.6402 + 0.1753
1.4666 # 0.0713
3.8021 # 1.0492
GPS+SPE (53.2M)
1.4502 0.2315
0.5616
5.6101 # 0.8129
Bridge Count (MAE)
GPS+SPE (212.2M)
2.1581 = 0,8106
3.3334 = 0.7540
5.7994 = 1.1003
ResNet (25.6M)
0.7771 + 0.1095
1.656 = 0.1643
3.6814 # 0.1217
Table 7: Comparison with P2-GNN across all benchmark tasks. P-GNN shows strong symmetry detection but poor scale generalization.
Task
Model
ID
Near-OOD
Far-OOD
P--GNN
94.67 1.49
87.87 4.90
63.33 5.83 90.33 + 4.60
Topology (%)
Best Vision
95.87 + 0.62
97.73 + 0.57
P-GNNN
90.80 = 3.49
84.00 2.53
83.40 + 3.56
Symmetry (%)
Best Vision
94.03 + 1.04
91.03 0.56
85.67 1.06
J--NNN
0.1044 = 0.0091
0.3315 + 0.0941
0.7893 # 0.2709
Spectral (MAE)
Best Vision
0.0279 0.0047
0.0578 0.0056
0.0946 0.0094
P-GNN
0.4580 0.1131
1.0459 0.1523
3,7353 1.0961
Bridge (MAE)
Best Vision
0.6261 0.0702
1.6338 0.1675
3.6814 + 0.1217
Table Impact of image resolution on vision model performance (ResNet on Symmetry classifica-
tion).
Resolution
Near-OOD
Far-OOD
Kamada-Kawall Layout
448x448
80.87 1.80
76.27 2.99
72.60 4.15
224x224
84.30 0.36
81.07 0.56
75.60 2.19
128x128
84.50 + 0.46
82.73 0.90
74.77 # 1.60
64x64
86.20 + 0.69
81.03 1.50
72.73 + 2.22
Spectral
Layout
448x448
93.97 0.96
91.53 0.71
85.93 0.23
224x224
93.17 + 1.15
89.47 0.46
83.20 0.97
128x128
93.53 + 0.69
88.30 + 0.40
81.23 + 0.88
64x64
91.97 1.27
87.17 + 1.48
80.93 + 1.08
27

---

G Discussion: Visual vs. Message-Passing Paradigms
In this section, we provide an informal analysis of why vision models achieve strong performance on graph structural understanding despite lacking graph-specific inductive biases. While we lack formal theoretical proofs, several observations from our community's own research practices offer intuitions about the complementary computational mechanisms underlying these approaches.
Different Computational Paradigms. The two paradigms solve fundamentally different problems. GNNs take graph structure (adjacency matrices, edge lists) as input and build understanding through iterative local message passing. Layout algorithms, contrast, perform global computations upfront: cigendecomposition for spectral layouts, energy minimization for force-directed methods. Once graphs are rendered as images, the task transforms from graph analysis visual pattern recognition. Vision models then process geometric patterns where structural properties manifest as directly observable visual features: symmetric graphs produce symmetric layouts, clustered graphs show dense regional connections, bridges appear as narrow connectors between substructures.
Evidence from Known GNN Limitations. This difference becomes evident when examining tasks where GNNs face theoretical limitations. When researchers construct counterexamples for the Weisfeiler-Lehnnee test and its k-dimensional variants, they invariably graph visualizations to illustrate why graphs are non-isomorphic despite fooling the WI. algorithm [61]. Visual represen- tations make structural distinctions immediately apparent that iterative refinement procedures miss. Horn et al. [29] explicitly present datasets containing graphs they describe as "easily distinguished by humans" visually. Their NECKLACES dataset shows graphs with identical cycle counts but different connectivity patterns: two individual cycles versus merged one. While humans immediately see this difference, standard message -aasggggpannngggg approaches fail to distinguish them, requiring sophisticated persistent homology calculations. Similarly, Zhang et al. [79] proved that standard GNNs cannot identify bridges, yet these structures manifest as obvious visual bottlenecks in graph layouts.
These observations suggest that layout algorithms and vision models provide a complementary pathway to graph understanding: layout algorithms convert abstract topological properties into spatial patterns through global computation, while vision models recognize these geometric features through hierarchical processing. This explains why vision models maintain strong performance despite lacking graph-specific inductive biases: they access structural information through a fundamentally different computational mechanism than message passing.
28

---

H
Visualization Examples from GraphAbstract
In this section, we provide visualizations of representative graphs in our benchmark. Figures 6-8 illustrate the diverse topological patterns across the four tasks: topology classification, symmetry classification, and spectral gap regression.
(a) Cyclic
(b) Random geometric
(c) Hierarchical hub
(d) Community
(c) Bottleneck
(f) Multi-core
Figure 6: Training examples of topology classification. For bridge counting task, similar graph structures used except for the cyclic structure, bridge counting focuses identifying edges whose removal would disconnect the graph.
(a) Cayley cyclic
(b) Bipartite double cover
(c) Cartesian product
(d) Cartesian w/ real (S)
(e) Real data cover
(f) Cartesian w/ real (NS)
(g) Perturbed graph
Figure 7: Training examples of symmetric classification. (a)-(e) are symmetric graphs, while (f)((g
asymmetric graphs. S: symmetric, NS: non-symmetric.
29

---

(a) SBM-DB, A22 0.04
(b) SBM-DB. À
0.35
(c) SBM-M. A2
0.01
(d) SBM-M. A 0.25
(e) Gco, d 0.12
(f) Geo, A2 0.16
(g) Cfg. À2 0.62
(h) Cfg. A2 0.78
Figure 8: Training examples of spectral gap regression, where X2 is the second smallest eigenvalue of the normalized Laplacian. SBM-DB: SBM dumbbell, SBM-M: SBM multi-community, Geo: Geometric, Cfg: Configuration model.
30

---

Analysis of Graph Layout Algorithms
I.1
Layout Algorithm Details
Graph layout algorithms aim to produce 2D (or 3D) representations of graphs that are interpretable and reveal underlying structures. Different algorithms employ distinct heuristics and optimization criteria, leading to varied visual outputs. In this work, we primarily consider four common layout types:
Kamada-Kawai. This a force-directed algorithm that models the graph as system of springs. aims position nodes such that the geometric distance between them in the layout is proportional to their graph-theoretic distance (shortest path length). This often results in aesthetically pleasing layouts that emphasize the overall shape and connectivity.
FolceA Another popular force-directed algorithm, particularly well-suited for larger graphs. simulates attraction forces between connected nodes and repulsion forces between all nodes, often effectively revealing clusters and community structures within the network.
Spectral Layout. This method uses the eigenvectors of the graph Laplacian (or related matrix) as coordinates for the nodes. Typically, the eigenvectors corresponding the smallest non-zero eigenvalues are used. Spectral layouts are mathematically principled and often highlight global symmetries and Cheeger-type cuts. A characteristic feature that structurally equivalent or highly similar nodes can overlap in the visualization.
Circular Layout. One of the simplest layout algorithms, it places all nodes equidistant on the circumference of a circle. The ordering of nodes around the circle can be arbitrary, based on node IDs, or determined by other properties like node degree.
1.2 Visualizing Asymmetric Graphs
To illustrate how different layout algorithms can affect the visual perception of graph properties, particularly symmetry and structural regularity, we present visualizations non-symmetric graph in Figure 9. This graph is generated via the Cartesian product of two distinct real-world graphs, resulting structure with high local regularity but no global symmetry. As detailed in the caption, force-directed layouts (Kamada-Ko) Kawai and ForceAtlas2) tend to faithfully represent the resulting complex structure. Consequently, determine its asymmetry, one might need to mentally deconstruct the layout to infer the properties of the underlying, distinct base graphs and recognize that their product would not yield simple visual symmetry. In contrast, the spectral and circular layouts render the graph such that its lack of global symmetry is more immediately visually evident.
Figure 9: Visualizations a non-symmetric graph generated by the Cartesian product of real-world base graphs. Despite its high structural regularity, this graph lacks symmetry. In Kamada Kawai (first) and ForceAtlas2 (second) layouts, determining asymmetry requires mentally reconstructing the base graphs and analyzing their properties. In contrast, the Spectral layout (third) reveals the grid-like product structure. However, critical visual cues about its asymmetry are evident in the lack of perfect geometric regularity and the varying thickness/rrightnes. of lines due edge overlap. These imperfections prevent global geometric symmetry axis (like vertical line through the center) from mapping the graph onto itself, serving as clear visual signals of the underlying asymmetry. Circular layout (fourth) displays nodes on circle and visually emphasizes the lack of uniformity in edge distribution, also clearly indicating the absence of symmetry. Both Spectral and Circular layouts facilitate a more direct visual assessment of asymmetry.
31

---

1.3 Characteristics and Performance of Circular Layout
We present the performance of vision models using circular-layout generated graph visualization in Table 9. Despite circular layouts significantly disrupting many visual topological properties, evidenced by the sharp performance drop on Topology classification in Far-OOD settings, they prove remarkably effective for tasks like symmetry detection. This effectiveness stems from how symmetry (or its absence) becomes visually apparent: for symmetric graphs, edge densities are balanced across the circle, while for asymmetric graphs, humans can readily perceive uneven edge densities or specific edges that break the expected uniform pattern. This allows both humans and models to assess symmetry without needing discern complex topological features that the circular layout inherently obscures.
Table Performance comparison of circular layout across different tasks and models
Task/Model
Swin
ConvNeXtV2
ResNet
ViT
Topology
ID
92.00 + 0.56
90.89 + 1.29
92.27 + 1.00
91.47 + 0.98
Near-OOD
81.13 1.09
79.22 2.01
75.40 2.35
80.33 2.80
Far-OOD
58.93 + 2.17
56.22 4.84
47.87 5,46
59.13 + 3.31
Symmetry
ID
85.17 1.12
85.08 1.25
86.07 0.95
83.87 0.88
Near-OOD
85.07 + 1.03
83.67 + 1.33
82.17 = 1.05
84.53 + 0.87
Far-OOD
83.67 0.73
82.50 1.00
76.00 2.74
80.13 1.86
Spectral
ID
0.0503 0.0030
0.0454 = 0.0017
0.0627 0.0057
0.0538 - 0.0020
Near-OOD
0.1330 0.0111
0.1503
0.0149
0.1569 0.0078
0.1457 0.0139
Far-OOD
0.2090 0.0141
0.2325 0.0127
0.2296 0.0083
0.2194 + 0.0184
Bridge
ID
1.1834 0.1239
1.1461 0.0842
1.2615 0.0825
1.2484 0,0609
Near-OOD
2.5184 0.2428
2.8263 0.1644
2.8143 # 0.1015
2.3876 + 0.1618
Far-OOD
6.1317 0.2053
6.7032 0.1245
6.8447 0.1495
5.8798 0.2176
32

---

J Preliminary Experiments and Implementation
J.1 Implementation Details of Preliminary Experiments
We implemented eight neural architectures adapted to graph data. For GNNs, we used GCN, GIN, GAT, and GPS. with 2-5 layers. 128 hidden units, ReLU activation, dropout with 0.5, and global mean pooling. GIN and GPS included MLPs in each block, GAT used multi-head attention, and GPS combined local GIN aggregation with global attention. For vision models (ResNet-50, ViT-B/16, Swin-Tiny, ConvNeXtV2-Ting Tiny), graphs were converted to 2D image representations (e.g.. adjacency layouts or distance matrices). Models were initialized with ImageNet- 1K weights, classification heads replaced by MLPs, and inputs resized to 224x224. All dataset splits were generated using seed O, with experiments conducted across five random seeds E [0, 1, 2, 4] for robust evaluation. Models were trained using Adam optimizer (learning rate 5e - 6, weight decay le 4) with batch size 64 and early stopping. For early stopping, the patience settings are set as: 30 epochs for all GNN models, and for vision models, 5 epochs on PROTEINS and 15 epochs on all other datasets.
J.2 Training dynamics and confidence
Figures 10-13 present training dynamics across four datasets, showing model differences in conver- gence and generalization. Figures 14 and 15 display confidence distributions for two representative datasets, one from the biological domain (PROTEINS) and one from social networks (IMDB- BINARY), highlighting the contrast between GNNs and vision models in prediction certainty.
Tarning Canues Reatial PROTBNS
Tuavry Curven CHSVERLOEE PROTTE
Thandaa Curina PASTUNN
Tuking Curves PROTEES
Figure 10: Training dynamics across different architectures on PROTEINS datasets. For each model, plot the training loss (blue), training accuracy (red), and validation accuracy (green) over 100 epochs. The shaded areas represent the standard deviation across multiple runs.
33

---

Palding Cerves INDS AHMRY
Tradding Curven MTX SANAY
Tradiing Carves MER BRAM
Tridiigg Curr for WrEA. B
Figure 11: Training dynamics across different architectures on IMDB-BINARY datasets. For each model, we plot the training loss (blue), training accuracy (red), and validation accuracy (green) over 100 epochs. The shaded areas represent the standard deviation across multiple runs.
trainig carves sualec (np0-41011
Traning Carnes for Co (433-MA
Taslfng CLTIEE PRP--1311
Traring CEPAE Swth (103-10011
Figure 12: Training dynamics across different architectures on IMDB-MULT and enzymes datasets. For each model, we plot the training loss (blue), training accuracy (red), and validation accuracy (green) over 100 epochs. The shaded areas represent the standard deviation across multiple runs.
mekrigg ENIYMIS
Traliing
DREYMESS
Trahiing EXCPRES
Figure 13: Training dynamics across different architectures on ENZYMES dataset. For each model, we plot the training loss (blue), training accuracy (red), and validation accuracy (green) over 100 epochs. The shaded areas represent the standard deviation across multiple runs.
34

---

Cestiercc Duttibesian of Juinet
Corfaanca Deptsatia SIHOL
Coddenss al
het
Pork
Figure 14: Confidence distribution across different model architectures on the PROTEINS dataset. The first two rows show results from the training set, while the last two present the test set. Vision models demonstrate a strong tendency toward high-confidence predictions (0.8-1.0) in both splits, while traditional GNNs typically make lower-confidence predictions. The GPS model, featuring global message passing, uniquely exhibits high-confidence predictions among GNN variants.
35

---

Codeese
Oodone her
Carlitee Sitrhatee grr.gre
Shirkelas grr.ad
Gataarr gm
Saton Burkkla PoRTTOAA
Meng (usttorih))
(1.35)
6.5%
Centdenns Hnttibation
Cooldence
Figure 15: Confidence distribution across different model architectures on the IMDB-BINARY dataset. The first two rows show results from the training set, while the last two rows present the test set.
36

---

J.3 Case Studies
To understand how different models make decisions in graph classification, we explore interpretability methods for both GCN and ConvNeXtV2 as examples. For GCN, we used the GNNExplainer to identify important substructures within input graphs. This approach optimizes masks over edges to highlight influential connections for classification decisions, with visualizations created using NetworkX to display node and edge importance. Results across different model depths were compared side by side. For ConvNeXtV2,, we applied Grad-CAA-basse approach by registering hooks on target layers to extract activation maps and gradients. The resulting class-specific heatmaps were overlaid on the imput images and uniformly displayed to highlight attention differences between models. Figures 16-19 illustrate additional explanation results for GNNs (via GNNExplainer) and vision models (via Grad-CAM) in the first three samples in the testing set of four datasets.
To delve deeper into how these models utilize underlying graph structures for prediction. especially in the presence of known important features, we highlight specific case study on the ENZYMES dataset. Amongst the datasets considered in our study, ENZYMES offers unique opportunity for this detailed interpretability analysis, as prior work by [12] has already identified and characterized discriminative pattern for it. This pre-existing knowledge allows us to assess alignment with established important features. Figure 16 presents this analysis:
Lawe hard Paaturs
Partures
OEN OWN Expldwer
les lod Paltes
Mi Patures
The Gred-cAn Vhuslaedee Vittnn Model
Figure 16: Comparison of GNN explainer (left) and Vision Model Grad-CAM (right) on ENZYMES dataset. The discriminative pattern, defined in [12] as square with two diagonal connections that appears in >90% of graphs within one class but <10% in others, is are key feature for classification. In the top row, where two discriminative patterns exist (one at each end of the graph), while both approaches identify these patterns, the Vision model's Grad-CAM shows particularly sharp focus on them at high-level features, compared the GNNExplainer's more uniform attribution. In the middle row, the Vision model effectively highlights multiple discriminative patterns near cut-vertices and cut-edges where the graph structure narrows. In contrast, the GNNExplainer shows scattered attention without emphasizing these critical patterns. The bottom row, containing no pre-defined discriminative patterns, demonstrates the different attention patterns of both approaches on non- characteristic structures. These results suggest that Vision models have leamee to effectively leverage these discriminative patterns as reliable shortcuts for classification, while GNNExplainers maintain relatively uniform attention distributions.
37

---

Lew Pastass
Nilico Fanure
Glod CAN Voud Vhuddaiiiae Whin Medeh
GON
Gred CAR vinddiatiin Vhiln Model
GEN CIN Repldner
Figure 17: Case Studies for NCI1 dataset.
Leteoan Fastures
1624ana Futurst
United Waudacilae Whlne
Good C&R Prnddoctiin Vhiles Medal
SER GIR Eapliter
Figure 18: Case Studies for IMDB-BINE BINARY dataset.
38

---

Lsw festures
Mddiaaal furures
YA uodadaaaa Viln
Dise-CM yunderea Vhil Hodel
SCR GUR Eaplaber
Figure 19: Case Studies for IMDB-MULTI dataset.
39

---

J.4 Heatmap
In this section, we present detailed prediction overlap analysis for all evaluated models across five benchmark datasets. Figures 20-24 illustrate the prediction overlap patterns between GNN models of varying depths (1-6 layers) and vision- based models. Consistent with our main findings, the results show high intra-family similarity among GNNs regardless of layer depth, while maintaining distinctly different prediction patterns compared to vision models.
Prod aifur Duartie Deecand: ENZIINE
Duarity Dancandd EXZYNEE
Food Atber Ouarlie Diecantd ENDPAEE
hest
44
(a) ENZYMES (1 layers) - Correct
(h) ENZYMES (2 layers) Correct
(c) ENZYMES (3 layers) Correct
Connect Frod sthen Dveriee Dervand: EN27INE
Conest Food vihun Overloy Diecand) EVSINNE
Conrect Frodi stfen Dervant: EN27INE
1.000
(d) ENZYMES (4 layers) Correct
(e) ENZYMES (5 layers) Correct
(i) ENZYMES (6 layers)- Correct
CA2 Ldtt 3.00 4.51
KMM CJM.
5.01
CTm X3M
445 1401
ENZYMES (1 layers) Error
(h) ENZYMES (2 layers) Error
ENZYMES (3 layers) Error
4.20
6230
ARM
<TC
(i) ENZYMES (4 layers) Error
(k) ENZYMES (5 layers) Error
()) ENZYMES (6 layers) - Error
Figure 20: Prediction overlap patterns for ENZYMES dataset with varying GNN layer depths. Top row shows correct prediction overlap, while bottom row shows error overlap patterns across different layer configurations.
40

---

Coren Prodicion thee rise Lecrent -CC
Correct Prockation live perrents -NC
Corrnct Prodition tiee rish Decrentt -C-
64M
47
1.00
(a) NCII (1 layers) Correct
(b) NCI1 (2 layers) Correct
(c) NCII (3 layers) Correct
Correct Proditton Giee Lierenti
Correct Prodiatonn Sie Dierend) -NC
Corract Prodition tiee Lieranti INCO
50.
0:00
11:0
1100 AMS
(d) NCII (4 layers)- Correct
NCI (5 layers) Correct
(1) NCI1 (6 layers)- Correct
LAN A234 0,00 4,31 5.04
off
KIH
0.00
Aia 4am kasi 4126
KaN
sau 410
(g) NCH (1 layers) Frror
(b) NCI1 (2 layers) Error
(i) NCTI (3 layers) Error
LAVE A311 1:24 0.31 1.00
off AZ2 428 A311
of Aan
AMH
1307
off A.M CIM
BAM cale Kail
of ane
(i) NCII (4 layers) Error
(k) NCII (5 layers) Error
()) NCII (6 layers) Error
Figure 21: Prediction overlap patterns for NCTI dataset with varying GNN layer depths. Top row shows correct prediction overlap, while bottom row shows error overlap patterns across different layer configurations.
41

---

Correct treathe Uercands PRISTERS MES
Comeec Frodictio Breakee Uercando- PRLTEE
Cornect Freet treatiey Darcand) PRISTEII
444 0.00
(a) PROTEINS (1 layers) Correct
(b) PROTEINS (2 layers) Correct
(c) PROTEINS (3 layers) Correct
Correct Seartay Eirrandd PRLSTEISS
Correct Prodlction Divaliy Lirnand POOOTER
Correct Searthy Dirranti PPw.PPEEE WeS
$4:00
430
422
428
444
kde
can1
11:00
1.00
140
(d) PROTEINS (4 layers) Correct
(e) PROTEINS (5 layers)- Correct
(1) PROTEINS (6 layers) Correct
CIV
LAN
5.24
GAM AJM 6.00
AJN
4112
PROTEINS (1 layers) Error
(h) PROTHINS (2 layers) Frror
PROTHINS (3 layers) Error
A21L 5220
14th
of. A.M CIM A36
or A2H
A30
1337
off 417
BAM cam
6f. AAl 4m
(i) PROTEINS (4 layers) Error
(k) PROTEINS (5 layers)- Error
() PROTEINS (6 layers) Error
Figure 22: Prediction overlap patterns for PROTEINS dataset with varying GNN layer depths. Top row shows correct prediction overlap, while bottom row shows error overlap patterns across different layer configurations.
42

---

424
(a) IMDB-BINARY (1 (layees)- Cor-
(b) IMDB-BINARY (2 layers) - Cor- (c) IMDB-BINARY (3 layees))-Coo Cor-
rect
rect
rect
Durcand
Cuertap Stevared LNESS BIAATYY
(d) BMDB-BINARY (4 layerr)) Cor-
(e)
IMDB-BINN BINARY (5 layers) Cor-
(f) IMDB-BINAR (6 layers) Cor- rect
recl
rect
5.54
CO
K7
SAN
(g) IMDR-BINARY (1 layers) Fi- (h) IMDB-BINARY (2 layers) Er- (i) IMDB-BINARY (3 layers) Fr--
Deartep (ieccand
byp (ieccand -NE0- EIMARYY
Oeartey (jecondd
SAIT
4.50 0:300
1:300
1.300
4.41 0.441
1.00
A30
AJN
1.00
()) IMDB-BINARY (4 layers)- Er- (k) IMDB-BINARY (5 layers) Er- (l) IMDB-BINARY (6 layers) Er- ror
ror
ror
Figure 23: Prediction overlap patterns for IMDB- BINARY dataset with varying GNN layer depths.
Top row shows correct prediction overlap, while bottom row shows error overlap patterns across different layer configuration nuniguuaaiion..
43

---

Comaet Diertey CAU IEDD-NN
Prodiction Courlap Diuaard INE0--M2.22
(a) IMDB-MULTI (1 layers) Cor-
(b) IMDB-MULTI (2 layers) Cor-
(c) IMDB-MULTI (3 layers) Cor-
rect
rect
rect
Prodectio Uirrannds Milil--- N4
Production Eoerice Diroarts. M418- NMLE7T
Frodd Uirrannds MMit 2MA
400%
A-52
X/L
(d) IMDB-MULTI (4 layers)- Cor- (e) IMDB-MULTI (5 layers)- Cor-
(l) IMDB-MULTI (6 layers) Cor- rect
rect
rect
Overity Darrann LMS8- MULTI
Emtor Overity Barrene (ND0 MULTI
Overity Darrerd
SPES MELTT
1.67
CTM
6.7
47M APM 472
A7N
LAN
CTM A2D
4714
(g) IMDR-MULTI (1 layers) - Error (h) IMDB-MULTI (2 layers)- Error (i) IMDB-MULTT (3 layers) Error
Overies Dacoardd- 1M006
Uarzare HULTT
Overiea Dacarrd -M400
Iase CAN
0.50
4.50
47%
C40
GUI
0.50
CTM
6.35
6
(i) IMDB-MULTI (4 layers) Error (k) IMDB-MULTI (5 layers)- Error ()) IMDB-MULTI (6 layers) Emror
Figure 24: Prediction overlap patterns for IMDB-MULTI dataset with varying GNN layer depths. Top row shows correct prediction overlap, while bottom row shows error overlap patterns across different layer configurations.
44

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In Section and 4.4, provide comprehensive experimental evidence and case studies to support our claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
In Appendix A, We discuss the limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
45

---

Justification:
In Section E, we provide the full set of assumptions and a complete proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We present the implementation detail Appendix D and also submit the code in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
46

---

Answer: [Yes]
Justification: The code for generating the datasets and running the experiments will be submitted via the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https: CoodeSubmiis
httpps.cccpubiic//eec / ssi asionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We state the experimental setup in Section 4.4 and Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All experiments were run multiple times using multiple random seeds, with the final mean and standard deviation reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the eтror bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
47

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide sufficient information on the computer resources Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https :ttp::///eeurre http///eerrpp...eee cc wwtppblic/tthiiaececececeeceeeee
Answer: [Yes]
Justification: We make sure that the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact on the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
48

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Properly credited.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
49

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We will release the code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
50

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLM is used only for writing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https /attps://re 220 for what should or should not be described.
51


Reviews:
[{"review_id": "PsiLSTAF7d", "reviewer": "Reviewer_3Uke", "summary": "In this work, the authors perform a comparative analysis of graph neural networks (GNNs) and vision models on established graph benchmarks (graph classification only), and a newly introduced benchmark, GraphAbstract, to evaluate graph visual understanding capabilities. GraphAbstract is designed with four tasks to evaluate models’ ability to perceive graph properties in a way that mirrors human visual cognition: topology classification, symmetry classification (using Cayley graphs, bipartite double covers, and Cartesian products of graphs), spectral gap regression and bridge counting.\n\nExperimental results on the established benchmarks demonstrate that vision models achieve performance comparable with GNNs, despite not using graph features. \n\nResults on the novel GraphAbstract show that vision models scale more effectively on out of distribution tasks (graph varying by scale), rely on different layouts depending on the task at hand, and that global position encodings greatly affect GNN performanc", "questions": "Questions/Suggestions for actionable improvements that would convince me to update my score:\n\nQ1: Can you include a comprehensive analysis of the costs incurred by a vision model vs a GNN in terms of memory, runtime (per epoch, and total runtime) and compute? Could the vision models be more computationally expensive than GNNs, especially since each graph (in this case relatively small graphs) needs to be converted into an image and hence the comparison is not fully fair?\n\nQ2: Can you motivate why imitating human perception on GNNs to detect topological features is a relevant real world problem beyond the benchmarks introduced here? I find the connection to human intuition interesting but not well motivated and integrated into the work being done here. Additionally, this would help motivate why we would even be interested in situations where graph features are dropped. \n\nQ3: Can you provide a better mathematical grounding for why vision models and GNNs differ so greatly? The architectures of the two are not discussed or compared. CNNs are in fact doing message passing, thus why wouldn’t they suffer from the same locality problem as GNNs?\n\nQ4: There are graph neural networks that are targeting graph structure as well (Boosting the Cycle Counting Power of Graph Neural Networks with I^2-GNNs), such as can you provide an overview of these in related work, and/or include any models specifically designed to excel at these tasks in your benchmarking? Can you include more recent GNN with message passing innovations to show how they would perform?\n\nQ5: Can you share the datasets and the code in a publicly available anonymous github repo?\n\nQ6: Can you clearly show which performance results are within 1std of the best ones?\n\nNit: The caption for Figure 2 can be improved so that the figure is standalone. Additionally, the captions for Table 1 can be improved to make it clear what each of the columns is illustrating. \nNit: Table 3 should be in the main body since the comparable performance on standard benchmarks is a central part of the first part of your paper. The tables in Figure 1 are symmetric so can be greatly reduced in size to make room.\nNit: Examples of graph structures shown in Appendix should be in the main text, as they illustrate well what GraphAbstract can propose.", "limitations": "The authors include a (short) limitations section, but focus it on comparing their models to human experiments. While interesting, this does not seem extremely relevant to the paper which is about GNNs vs vision models. Authors should discuss limitations in the models they evaluated and scope of their results.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\nS1. The paper is well written with a clear and original contribution. I appreciate the presentation of the methodology which featured a good mix of mathematical formulations and plain English.\nS2. The paper presents a comprehensive array of empirical results across a range of different real-world datasets.\nS3. The paper introduces a new benchmarking suite, GraphAbstract, made of synthetic graphs designed to separate the challenge of understanding graph topology from learning based on node or edge features, and compare vision models and GNNs.\n\n\nWeaknesses (see Questions for actionable improvement suggestions to address these)\nW1. This paper lacks empirical evidence of the computational efficiency (model complexity, memory, and convergence time) brought on by the method, and how these aspects vary between GNNs and vision models. \nW2. The paper does not ground their analysis in real world examples. I am interested in 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 (OOD experiments). The motivation for why these are desiderata for learning on graphs is not quite clear to me.\nW3. CNNs also first compute local features by message passing, while the global features only appear at the last layer. Hence, the argument that vision models capture global features seems debatable from the very start.\nW4. The GNNs compared are mostly from before 2020 (precisely: 2016, 2017, 2018 and 2022)  while the vision models are mostly from after 2020 (precisely: 2016, 2021, 2020, 2023). In order to conclude that vision models outperform GNNs, or to claim that injecting “pre-computed global structural information significantly outperforms innovations in message passing architectures alone” it would be more fair to include the latest GNNs with appropriate “innovation”.\nW5. The dataset and the code are not publicly available, which is a weakness for a benchmark paper.\n\nThis paper would have been better suited for the NeurIPS Benchmarks and Dataset Track: Why not submitting there?", "was_revised": true, "final_justification": "The authors convinced me about the premise of the paper by their comparison of CNN/GNN and the added experiments addressed my concerned on the computational differences.", "rebuttal": "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.\n\n**W1 & Q1: Computational cost analysis**\n\nThank 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. \n\n| Model | GPU Memory (MB) | Parameters (M) | Time/Epoch (s) | Time to Best Val Acc (s) |\n|-------|-----------------|----------------|----------------|------------------|\n| CONVNEXT | 22980 | 28.2 | 13.1 | 329.5 |\n| RESNET| 10916 | 25.6 | 5.5 | 120.7 |\n| SWIN | 13515 | 27.8 | 11.5 | 368.9 |\n| VIT | 18510 | 86.1 | 23.1 | 509.9 |\n| GAT+SPE | 326 | 0.1 | 1.2 | 43.2 |\n| GCN+SPE | 325 | 0.1 | 1.2 | 45.1 |\n| GIN+SPE | 327 | 0.1 | 1.1 | 47.0 |\n| GPS+SPE | 376 | 0.5 | 1.4 | 26.9 |\n| | | | | |\n| *Avg. Vision* | 16480 | 41.9 | 13.3 | 332.2 |\n| *Avg. GNN+SPE* | 338 | 0.2 | 1.2 | 40.6 |\n| **Ratio (V/G)** | **48.7×** | **209.6×** | **10.9×** | **8.2×** |\n\nThese 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.\n\n**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.**\n\nThank you for pushing us to clarify the practical relevance.\n\n**\"Scenarios in which we would want to predict symmetry or bridge counting\":**\n\nThese 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: \n\n * **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. \n\n* **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]. \n\n**\"Why we would want the prediction to generalize from small graphs to bigger graphs\":**\n\nScale 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. \n\nIn 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.\n\nIn the revised manuscript, we will: \n - Add a dedicated section discussing the relationship between fundamental capabilities and practical limitations\n - Clearly position our work as diagnostic rather than immediately applicable \n- Expand limitations to acknowledge the gap between our benchmark and real-world impact\n\n[1] When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach. ICLR 2025.\n\n[2] Unbiasing retrosynthesis language models with disconnection prompts. ACS Central Science 2023.\n\n**W3 & Q3: CNNs also perform local operations. Why don't they suffer from the same locality problem as GNNs?**\n\nYou 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.\n\nWhen 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.\n\nSo 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.).\n\nThis \"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.\n\n**W4 & Q4: Coverage of recent GNN developments**\n\nThank 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: \n| Task | ID | Near-OOD | Far-OOD |\n|------|-------|----------|---------|\n| Topology | 94.67 ± 1.49 | 87.87 ± 4.90 | 63.33 ± 5.83 |\n| Symmetry | 90.80 ± 3.49 | 84.00 ± 2.53 | 83.40 ± 3.56 |\n| Spectral | 0.1044 ± 0.0091 | 0.3315 ± 0.0941 | 0.7893 ± 0.2709 |\n| Bridge | 0.4580 ± 0.1131 | 1.0459 ± 0.1523 | 3.7353 ± 1.0961 |\n*Table 1: I²-GNN Performance*\n\nThe 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.\n\n\nI²-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.\n\n\nIn our revision, we will: \n- Add a comprehensive related work section covering subgraph GNNs, graph transformers, and positional encoding methods \n- Include I²-GNN results in our main comparison tables \n\n**W5 & Q5: Code and Dataset Availability**\n\nOur 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.\n\n**Q6: Statistical Significance**\n\nWe will clearly mark (bold/underline) all results within 1 standard deviation of the best performance.\n\n**Limitations**\n\nYou'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.\n\n**Why not Benchmark Track**\n\nWe 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.\n\n**Nits**\n\nThank 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."}, {"review_id": "r6vh19iJSx", "reviewer": "Reviewer_Aeju", "summary": "This paper discusses the challenges associated with current benchmarks used to evaluate graph AI. Traditional benchmarks, such as node classification and link prediction, entangle node/edge features with the graph's structural properties, making it difficult to assess which aspects contribute most to performance. To address this issue, the authors propose GraphAbstract, a benchmark designed to evaluate models based purely on structural characteristics.\n\nGraphAbstract encompasses tasks such as topology classification, symmetry detection, spectral gap regression, and bridge count regression, with a focus on structural understanding. Moreover, it incorporates evaluation on larger graphs than those seen during training, to assess whether structurally meaningful patterns can be recognized visually at scale.\n\nUsing this benchmark, the authors show that vision-based models, which operate on images generated from graph layouts, significantly outperform traditional GNNs. They also demonstrate that incorporating image-style positional encodings into GNNs dramatically improves their performance. These findings suggest that integrating visual and intuitive processing into graph AI could lead to more robust and flexible models for structural understanding.", "questions": "1. Can you demonstrate that the graph layouts capture structural features in a fundamentally different way from conventional GNNs? Without a sufficient explanation of this distinction, it is difficult to convincingly argue that GNNs fail to understand structural properties.\n\n2. 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?", "limitations": "As noted above, the processing pipeline of vision models involves many intertwined factors, including structural interpretation through graph layouts, layout adjustments, image resolution, and more. Because of this complexity, the claim that “GNNs are poor at capturing structural features while vision models are superior” lacks sufficient persuasiveness. A more careful analysis and discussion of these individual components is necessary to convincingly identify the specific limitations of GNNs in understanding structural properties.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\nThis paper introduces a new benchmark designed to purely evaluate the understanding of structural properties in graphs, which has been difficult to assess with conventional benchmarks. Rather than merely proposing evaluation metrics, the authors go further by detailing how synthetic datasets are generated to faithfully represent the intended structural properties, making the benchmark both practical and conceptually sound. Moreover, the finding that vision models outperform traditional GNNs on this benchmark provides compelling insights into the future direction of graph AI, suggesting the potential power of integrating visual, intuitive reasoning into structural graph understanding.\n\nWeaknesses:\nWhile the proposal of a new benchmark represents a significant contribution, there remain serious concerns regarding the vision-based evaluation used to validate its utility. The most critical issue is the lack of sufficient discussion on the role of graph layout algorithms, which inherently embed structural information into visual representations. Since any layout method captures structural features in some way, failing to analyze how these layouts influence the outcome raises substantial doubts. As a result, evaluating model performance on rendered layouts introduces numerous confounding factors, including layout algorithm biases, resolution effects, and spatial adjustments, making it difficult to isolate the model's structural understanding. Therefore, concluding that vision models inherently understand graph structure seems premature. More careful experimental design and thorough analysis could greatly enhance the credibility and impact of this work.", "was_revised": true, "final_justification": "The rebuttal has provided a clearer explanation of how graph visualization can capture features that GNNs cannot. I also understand that, while specific problems can indeed be solved using specialized methods, this work aims to develop a method that can be applied broadly, regardless of the problem type. I hope these explanations will be sufficiently reflected in the final manuscript, and I am inclined to raise my rating by one point.", "rebuttal": "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.\n\n**Weakness & Q1:Can you demonstrate that the graph layouts capture structural features in a fundamentally different way from conventional GNNs?**\n\nThank you for raising this fundamental question. These two approaches represent different computational pipelines: \n- **GNNs**: Take graph structure (adjacency matrices, edge lists) as input and build understanding through iterative local message passing \n- **Layout + Vision**: Perform global computations upfront (eigendecomposition, energy minimization) to embed graphs in 2D space, then process the resulting geometric patterns\n\nThis 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.\n\nWhile 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. \n\nIn 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.\n\n[1] Wang, Y., & Zhang, M. (2023). An empirical study of realized GNN expressiveness. ICML 2024.\n\n[2] Horn, Max, et al. \"Topological graph neural networks.\"  ICLR 2022.\n\n[3] Zhang, Bohang, et al. \"Rethinking the expressive power of GNNs via graph biconnectivity.\" ICLR 2023\n\n[4] Eades, P., & Lin, X.\"Spring algorithms and symmetry.\" Theoretical Computer Science 2000.\n\n\n**Q2 (Limitation 1): Regarding the processing pipeline and confounding factors:**\nThank 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.\n\n**Regarding layout algorithm biases, resolution effects, and spatial adjustments:**\n\nWe 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:\n\n**1. Layout Algorithm Diversity:** \nWe 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.\n\nAs 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:\n- Spectral layouts excel at symmetry detection (8-10% higher accuracy) by naturally manifesting symmetries through geometric arrangements\n- Circular layouts enable straightforward symmetry assessment through edge density patterns  \n- Force-directed methods excel at revealing community structures\n\nThis diversity helps practitioners understand which layout-task combinations are most effective, providing practical guidance for future applications.\n\n**2. Resolution Robustness:** \nFollowing your suggestion, we conducted systematic resolution experiments. We selected the challenging symmetry task as a representative example:\n\n| Resolution | ID | Near-OOD | Far-OOD |\n|------------|-------|----------|---------|\n| 448×448 | 80.87 ± 1.80 | 76.27 ± 2.99 | 72.60 ± 4.15 |\n| 224×224 | 84.30 ± 0.36 | 81.07 ± 0.56 | 75.60 ± 2.19 |\n| 128×128 | 84.50 ± 0.46 | 82.73 ± 0.90 | 74.77 ± 1.60 |\n| 64×64 | 86.20 ± 0.69 | 81.03 ± 1.50 | 72.73 ± 2.22 |\n\n*Table 1. ResNet Resolution Study - Kamada-Kawai Layout (Symmetry Task)*\n\n\n| Resolution | ID | Near-OOD | Far-OOD |\n|------------|-------|----------|---------|\n| 448×448 | 93.97 ± 0.96 | 91.53 ± 0.71 | 85.93 ± 0.23 |\n| 224×224 | 93.17 ± 1.15 | 89.47 ± 0.46 | 83.20 ± 0.97 |\n| 128×128 | 93.53 ± 0.69 | 88.30 ± 0.40 | 81.23 ± 0.88 |\n| 64×64 | 91.97 ± 1.27 | 87.17 ± 1.48 | 80.93 ± 1.08 |\n\n*Table 2. ResNet Resolution Study - Spectral Layout (Symmetry Task)*\n\nThe 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.\n\n**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. \n\n**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:\n - Developing layout algorithms specifically optimized for machine perception\n - Establishing theoretical connections between geometric properties and learnability\n - Creating hybrid approaches that combine visual and message-passing strengths \n\n**Manuscript Revision Plans**: We will enhance our manuscript to better communicate our findings and limitations:\n - 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 \n- In the Introduction, we will more clearly articulate that visual and message-passing approaches offer complementary pathways for graph understanding\n - We will expand our limitations section to explicitly discuss the confounding factors you raised \n\nThese revisions will help present a more balanced view of our contribution while maintaining the value of our empirical findings.\n\n**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?**\n\nYou 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."}, {"review_id": "XT4SIGhJ4X", "reviewer": "Reviewer_ofCS", "summary": "This paper explores the use of visual machine learning models, e.g., ResNet, on graph-based applications, addressing the fundamental question of whether existing state-of-the-art graph neural network (GNN) models fully capture global graph properties. To this end, the paper follows a simple strategy: Convert graph structures into visualizations following standard algorithms, and train vision models on the same tasks. Unlike graph models, vision models lose graph structural inductive bias and access to node or graph-level features. Nonetheless, the paper shows that vision models can achieve remarkable performance, often comparable with GNNs, despite these disadvantages. The paper then justifiably asserts that existing benchmarks in the graph learning space conflate global structure learning with low-level feature learning, which effectively offer an alternative means of achieving good performance while ignoring the higher-level structures and patterns that humans intuitively perceive from visualizations. To confirm this point, the paper also reports a comparative study on several graph learning benchmarks, highlighting that GNNs and vision models' predictions differ substantially. \n\nTo better study the performance of graph learning models towards structural understanding, the paper proposes a carefully designed set of structure-oriented tasks, namely graph structure classification, symmetry detection, bridge counting, and spectral gap regression, and builds the benchmarks using a series of graph generation and perturbation methods. The paper then conducts an empirical study, highlighting the improved robustness and generalization of vision models, the importance of feature initialization in GNNs as a mitigator for the lack of global feature representations, and highlighting that visual representation choices, i.e., how graphs are converted into images, are critical for obtaining strong vision model performance.", "questions": "No questions. Please address suggestions in previous section.", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- Very foundational work, which is well-justified, rigorously presented, and methodically executed. \n- Addresses a very intuitive question in the graph learning space, and proposes a benchmark that could prove very valuable for the field.\n- The discussion on vision models and layout algorithms is insightful, and paves the way for further research on how to inject global structure into state-of-the-art graph representation learning approaches.\n- The comparative analysis of vision and graph models is comprehensive and offers a new perspective that can help guide future model design.\n\nWeaknesses: \n- The paper proposes a benchmark for structure understanding that is well-justified, but falls short of providing any model-oriented solutions to bridge the gap between vision and graph models. Naturally, this is a research direction in its own right, but I feel that this work would be stronger with experiments that add further nuance. Examples include feature representation through images (e.g., discrete labels as colors), better validating general structural understanding through robustness studies (corrupting graphs and images through e.g, blur / noisy edges and measuring performance change).\n\n- [Minor] The paper makes claims about the conflation of features and structures as means to achieve high-level performance on a series of established benchmarks. I believe the paper would be stronger if it provides results on these benchmarks showcasing the drop-off when features are discarded.\n\nOverall, I think this paper sets up a promising direction for further investigation, which can stimulate research into alternative means for encoding structural graph properties. While there are clear avenues to improve the work (e.g., model proposals for combining features and global visual structure, more studies), I still believe the dataset contribution and insights provided in this work merit publication as-is.", "was_revised": true, "final_justification": "I remain positive about this paper's contributions.", "rebuttal": "We sincerely thank you for your encouraging review and thoughtful suggestions. We have carefully considered each of your points and provide our responses below.\n\n**1. Feature representation through images:**\n\nWe 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.\n\nWe tested this approach across multiple real-world datasets:\n\n| Model | NCI1 | IMDB-MULTI | ENZYMES | IMDB-BINARY | PROTEINS |\n|-------|------|------------|---------|-------------|----------|\n| **Vision Models (with color encoding)** |\n| ResNet | 69.7±1.0 (+2.0) | 50.1±1.1 (-1.1) | 38.7±1.2 (+2.4) | 72.4±1.0 (+0.2) | 77.8±1.5 (-1.8) |\n| ViT | 67.0±0.9 (+3.5) | 47.1±2.6 (-3.7) | 33.0±4.5 (+5.7) | 72.6±2.7 (+0.8) | 81.6±1.5 (-1.5) |\n| Swin | 73.0±1.0 (+4.0) | 51.2±1.4 (-0.8) | 40.3±5.5 (0.0) | 71.0±1.8 (+2.2) | 82.2±1.1 (+0.4) |\n| ConvNeXt | 73.1±1.3 (+2.9) | 50.4±1.9 (-3.1) | 33.0±5.2 (-8.7) | 67.6±3.3 (-6.2) | 81.1±2.7 (+0.4) |\n\n*Numbers in parentheses indicate change from baseline (without color encoding)*\n\nWe observed dataset-specific patterns in these preliminary results:\n- **Consistent improvements** on NCI1 (all models: +2.0 to +4.0%) and IMDB-BINARY (3 out of 4 models positive)\n- **Consistent degradation** on IMDB-MULTI (all models: -0.8 to -3.7%) \n- **Mixed results** on ENZYMES and PROTEINS depending on the model\n\nAs 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).\n\nImportantly, 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.\n\n\n**2. Robustness studies (corrupting graphs and images):**\n\n 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.\n\n**3. Minor comment on benchmark conflation:** \n\nThank 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.\nRecent 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:\n\n| Model | NCI1 | ENZYMES | PROTEINS |\n|-------|------|---------|----------|\n| **GNN Models (with random features)** |\n| GCN | 52.7±2.7 (-12.7) | 14.3±1.3 (-11.0) | 73.0±3.9 (-1.8) |\n| GAT | 54.7±1.4 (-12.3) | 14.3±4.8 (-12.7) | 75.5±2.4 (+1.4) |\n| GIN | 54.5±3.8 (-15.9) | 15.3±2.2 (-11.0) | 74.6±2.1 (-0.4) |\n| GPS | 54.2±1.4 (-22.1) | 16.3±4.1 (-18.0) | 74.2±1.3 (-1.8) |\n\n*Numbers in parentheses indicate change from baseline (with original features)*\n\nThese 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.\n\n[1] Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks. ICML 2025.\n\n\n[2] Graph Neural Networks Use Graphs When They Shouldn’t. ICML 2024.\n\n\n**4. Future directions for hybrid models :** \n\nWe 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.\n\nThank 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."}]

Author rebuttal:

Meta-review: This paper explores the potential of vision models for graph structural understanding, introducing the GraphAbstract benchmark to evaluate global topological reasoning across tasks like symmetry detection and bridge counting. Reviewers found the work original and rigorous, with ofCS highlighting its foundational contributions and 3Uke and Aeju appreciating the benchmark's conceptual clarity. Initial concerns about computational fairness and layout-induced confounds were addressed through thorough rebuttals and experiments, including scaling studies and resolution analysis. While limitations remain in formalizing the role of layout algorithms, the paper convincingly demonstrates that vision models offer complementary strengths to GNNs. Given its empirical depth and conceptual novelty, this paper is recommended for poster presentation, and future work should pursue theoretical grounding and hybrid modeling strategies.
Decision: Accept (poster)