A2I: Adjacency-to-Image Structural Encodings for Graph Learning

Graph representation learning often relies on message passing or spectral/positional encodings to summarize graph structure, but these indirect summaries can collapse structurally distinct graphs, including non-isomorphic cospectral pairs. We propose A2I, a structural encoding framework that renders BFS--degree-ordered local adjacency patterns as fixed-resolution images and embeds them with a frozen pre-trained vision encoder. The resulting structural tokens are mapped to learnable prototypes and aggregated with node embeddings via a lightweight Transformer. We provide a conditional analysis with two related findings: a stability result, showing that two orderings of the same graph yield embeddings that converge under bounded-degree assumptions, and a separability result, showing that two distinct graphs yield embeddings whose gap grows at least linearly with the difference in their BFS profiles. Empirically, A2I is competitive with recent GNN, Graph Transformer, and structural-encoding baselines on six node-classification benchmarks, with pronounced gains for GCN-based models on heterophilous graphs and under partial feature masking.