# DARTS-GT: Differentiable Architecture Search for Graph Transformers with Quantifiable Instance-Specific Interpretability Analysis

arXiv: https://arxiv.org/abs/2510.14336 · HTML: https://mlsanity.com/paper/2510.14336/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 41 of its 55 references that are in the map.
- First posted on arXiv 16 Oct 2025.

## Builds on (most cited first, 30 of 41)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Are Sixteen Heads Really Better than One?](https://mlsanity.com/paper/1905.10650/) (2019)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Towards Best Practices of Activation Patching in Language Models: Metrics and Methods](https://mlsanity.com/paper/2309.16042/) (2023)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Mesh Graphormer](https://mlsanity.com/paper/2104.00272/) (2021)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [How to use and interpret activation patching](https://mlsanity.com/paper/2404.15255/) (2024)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Directional Graph Networks](https://mlsanity.com/paper/2010.02863/) (2020)
- [Accurate Learning of Graph Representations with Graph Multiset Pooling](https://mlsanity.com/paper/2102.11533/) (2021)
- [Global Self-Attention as a Replacement for Graph Convolution](https://mlsanity.com/paper/2108.03348/) (2021)
- [GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks](https://mlsanity.com/paper/2206.09677/) (2022)
- [Search to aggregate neighborhood for graph neural network](https://mlsanity.com/paper/2104.06608/) (2021)

## Abstract (arXiv)

Graph Transformers (GTs) have emerged as powerful architectures for graph-structured data, yet remain constrained by rigid designs and lack quantifiable interpretability. Current state-of-the-art GTs commit to fixed GNN types across all layers, missing potential benefits of depth-specific component selection, while their complex architectures become opaque where performance gains cannot be distinguished between meaningful patterns and spurious correlations. We redesign GT attention through asymmetry, decoupling structural encoding from feature representation: queries derive from node features while keys and values come from GNN transformations. Within this framework, we use Differentiable ARchiTecture Search (DARTS) to select optimal GNN operators at each layer, enabling depth-wise heterogeneity inside transformer attention itself (DARTS-GT). To understand discovered architectures, we develop the first quantitative interpretability framework for GTs through causal ablation. Our metrics (Head-deviation, Specialization, and Focus), identify which heads and nodes drive predictions while enabling model comparison. Experiments across eight benchmarks show DARTS-GT achieves state-of-the-art on four datasets while remaining competitive on others, with discovered architectures revealing dataset-specific patterns. Our interpretability analysis reveals that visual attention salience and causal importance do not always correlate, indicating widely used visualization approaches may miss components that actually matter. Crucially, heterogeneous architectures found by DARTS-GT consistently produced more interpretable models than baselines, establishing that Graph Transformers need not choose between performance and interpretability.