End-to-End Subgraph Detection with GraphDETR
Dexiong Chen*
Till Hendrik Schulz*
Karsten Borgwardt
arXiv:2606.06364v1 [cs.LG] 4 Jun 2026
Max Planck Institute of Biochemistry, Martinsried, Germany * Equal contribution Code: will be released upon publication.
Abstract Subgraph detection seeks to identify whether and where instances of query patterns occur within a larger graph. This problem is fundamental across scientific domains and is closely related to subgraph isomorphism, which is NP-complete, limiting combinatorial approaches to small patterns or moderately sized graphs. We introduce GraphDETR, a deep learning framework that formulates subgraph detection as a set prediction problem, analogous to DETR in object detection. GraphDETR encodes the target graph with a graph neural network, and employs a fixed set of learnable query vectors, decoded via a transformer decoder, to predict all pattern occurrences jointly in a single forward pass. This is enabled by training the model end-to-end with bipartite matching. Unlike traditional combinatorial methods that only solve exact structural matching, GraphDETR naturally extends to approximate matching, enabling detection beyond exact pattern correspondence. Empirically, we show that GraphDETR can detect diverse patterns, such as molecular structures, cycles, cliques, and fuzzy patterns of up to 50 nodes, in target graphs with up to 1000 nodes. We further evaluate on molecular functional group detection over the ChEMBL dataset, where GraphDETR predicts the complete set of functional groups per molecule, achieving a strong performance of AP100 = 91.2.
1
Introduction
Subgraph detection is a fundamental problem in graph analysis that aims to identify whether and where specific patterns occur within a larger graph. It has applications in many domains such as molecular analysis [27, 32], and network science [24, 13]. A prominent instance of this problem is molecular functional group detection, where the goal is to locate all occurrences of chemically characteristic substructures such as hydroxyl or carbonyl groups within a molecule. Identifying these substructures plays a key role in tasks such as reaction prediction, retrosynthesis planning, and molecular property modeling. Figure 1A illustrates this task on an example molecule. Classical approaches to locating pattern occurrences in graphs rely on combinatorial search algorithms for subgraph isomorphism, which seek injective edge-preserving mappings from a pattern to a target graph. Methods such as Ullmann [29] and Cordella et al. [9] provide exact solutions but suffer from exponential worst-case complexity, which limits their applicability on large graphs. Recent neural approaches [34] attempt to address this limitation by learning representations of graphs or subgraphs using graph neural networks (GNNs). However, most existing methods decompose the task into local matching decisions or independent predictions of candidate substructures. As a result, they do not explicitly model the fact that a target graph typically contains a set of subgraphs that should be predicted jointly while avoiding duplicate detections. Subgraph detection thus calls for jointly predicting all occurrences in a target graph, each as a labeled set of nodes, without duplicate detections. Casting the problem this way reveals a direct parallel with object detection, where the goal is likewise to predict a variable-sized set of objects, each with Preprint.
a class and a location, without duplicates (Figure 1B). In fact, recent progress in computer vision has shown that object detection can be solved elegantly as set prediction. In particular, DETR [4] demonstrated this by training a fixed pool of learnable queries via a transformer decoder with bipartite matching. DETR removes many heuristic components of traditional detection pipelines and enables fully end-to-end training. In this work, we bring the set prediction perspective to graphs and introduce GraphDETR, an end-toend framework for subgraph detection. GraphDETR first encodes the target graph using a GNN. A fixed set of learnable query vectors then interacts with the graph representation through a transformer decoder to produce candidate subgraphs. Each query predicts a node-set mask representing a detected subgraph. GraphDETR is trained end-to-end with a bipartite matching loss that assigns predictions to ground-truth subgraphs, producing the complete set of detections in a single forward pass without duplicate predictions. Unlike combinatorial methods, which are inherently limited to exact structural matching, GraphDETR naturally extends to approximate matching, where a query pattern defines a class of subgraphs rather than a single exact structure. We evaluate GraphDETR in two settings. aromatic ring (A) (B) Graph Naproxen First, we apply GraphDETR to molecular Vision carboxylic acid pixels + bbox nodes + mask functional group detection, where the task methoxy ether C C C is to predict the complete set of functional C cat C cycle C groups present in a molecular graph. ExperC O C ⇔ C iments on the ChEMBL dataset show that C path C C dog C GraphDETR achieves strong performance O C O while maintaining a simple, unified, and fully end-to-end architecture. Second, we Figure 1: (A) A molecular graph with three color-coded consider subgraph matching with a fixed functional groups, each predicted as a class label and a query set, which provides a general bench- binary node mask. (B) The analogy between object demark for evaluating the model’s ability to tection and subgraph detection, where bounding boxes predict multiple substructures simultane- over pixels correspond to node masks over graphs. ously. Overall, our approach demonstrates that the set prediction paradigm provides a natural and effective formulation for graph reasoning problems involving multiple structured outputs. By combining GNNs with transformer-based set prediction, GraphDETR provides a new approach for learning to detect subgraphs directly from data.
2
Related Work
GraphDETR is related to three lines of machine learning research: set-prediction-based detection, graph representation learning, and subgraph matching. Set prediction. DETR [4] reformulated object detection as direct set prediction, where a transformer decoder with a fixed pool of learnable query vectors attends to image features and is trained endto-end via Hungarian bipartite matching [18], eliminating anchors and non-maximum suppression. Subsequent work refined query initialization [36] and extended the paradigm to instance segmentation [7]. SAM [17] and SAM 2 [26] introduced a two-way transformer decoder in which prompt tokens and image tokens mutually attend to each other, allowing the image representation to incorporate per-query context before mask logits are computed. GraphDETR applies this full pipeline to graphs, where image feature maps become per-node embeddings produced by a graph encoder, bounding boxes become binary node-membership masks, and class labels become subgraph types. The principal graph-specific addition is the cut penalty, which steers each predicted mask toward a spatially connected subgraph, a structural prior with no direct image analogue. Graph neural networks. The dominant paradigm for graph learning is message passing, with representative MPNNs including GCN [16], GIN [30], and GatedGCN [3]. Graph Transformers [33, 5] augment local message passing with global self-attention. GraphGPS [25] runs an MPNN branch and self-attention in parallel per layer, attaining strong results on several benchmarks. Random Walk Neural Networks [15, 28], in particular NeuralWalker [6], take an alternative route by encoding random-walk sequences with a sequence model, such as a state-space model, and aggregating back to nodes, capturing long-range structural context without the quadratic cost of full attention. All standard MPNNs and Graph Transformers suffer from the symmetry issue, i.e., they assign identical representations to nodes that are in the same orbit. This positional ambiguity is especially problematic 2
predictions
N nodes
GT classes+masks
input graph
GT subgraphs
graph encoder
···
transformer decoder
⇔
∅
COOH ring OMe
bipartite matching
learnable queries
Figure 2: GraphDETR architecture. An input graph is encoded into per-node embeddings by the graph encoder. A set of learnable query vectors and the node embeddings are jointly refined by a (two-way) transformer decoder via interleaved bidirectional cross-attention. A linear class head and a bilinear mask head produce one (class, node-mask) pair per query. At training time, bipartite matching assigns predictions to the ground-truth set of subgraphs. for instance-level tasks, where two nodes belonging to different occurrences of the same subgraph query may receive identical node embeddings, obstructing per-instance mask assignment. Subgraph matching. Classical algorithms, such as Ullmann’s backtracking [29] and VF2 [9], compute exact subgraph isomorphisms but run in worst-case exponential time, making them impractical on large graphs. Early neural approaches sidestep combinatorial search by learning graph-level similarity scores. For instance, Graph Matching Networks [19] employ cross-graph attention to compute pairwise graph similarity, and SimGNN [1] combines graph-level embeddings with nodeto-node interaction to approximate graph edit distance. These methods measure how similar two graphs are globally, but do not localize where in a larger graph a pattern occurs. Neural Subgraph Matching [34] learns order-preserving embeddings that determine whether a query is a subgraph of a target and can identify a matching neighborhood through post-processing. However, it only processes a single query–target pair and does not predict multiple simultaneous occurrences. A related line of work learns to count pattern occurrences [23], returning a scalar estimate of how many times a query appears, without spatial localization. GraphDETR is the first model to jointly produce a complete set of query-subgraph pairs for all instances in a single differentiable forward pass, with no combinatorial search or post-processing at inference time.
3
GraphDETR for End-to-End Subgraph Detection
The task of subgraph detection requires identifying each occurrence of each pattern separately. The same pattern may appear multiple times in one graph, and different occurrences may have overlapping node sets. For each occurrence, the model needs to predict which pattern class it belongs to and which nodes it occupies. A suitable model should therefore produce a variable-size set of (class, node-mask) pairs, one per instance. This prediction problem has a natural analogue in object detection, where a model must similarly produce a variable-size set of (class, localization) pairs, one per detected object. The established paradigm for this task, pioneered by DETR [4], is phrased as set prediction, where a fixed set of learnable queries each produce one candidate. GraphDETR adopts this formulation for graphs, replacing bounding boxes with binary node-membership masks and class labels with pattern types. The model works as follows. A graph neural network encoder produces per-node embeddings that retain the local structure of the input (Section 3.2). A fixed number Q of learnable query vectors then interact with these node embeddings through a two-way transformer decoder, with each query predicting a specific subgraph instance (Section 3.3). A class head and a bilinear mask head decode each query into a (class, node-mask) pair. Queries that do not correspond to any instance predict a designated background class. The model is trained end-to-end with Hungarian matching, which assigns each prediction to a ground-truth instance, and a composite loss that penalizes both misclassification and mask inaccuracy (Section 3.4). An overview of the architecture is visualized in Figure 2. 3.1
Problem Formulation
We formulate subgraph detection as a set prediction task over node-induced subgraph instances. Let G = (V, E, X) be a graph with N = |V | nodes and node feature matrix X ∈ RN ×dx . A 3
node-induced subgraph instance is a pair (c, m) consisting of a class label c ∈ {1, . . . , C} and a binary node mask m ∈ {0, 1}N . A mask defines a node subset Vm = {v ∈ V : mv = 1}, and the instance is the induced subgraph G[Vm ] = (Vm , Em ) with Em = {(u, v) ∈ E : u, v ∈ Vm }. A graph G may contain multiple instances of each pattern class, forming a set S ∗ = {(c∗k , m∗k )}K k=1 , where K varies across graphs and instances of the same or different classes may overlap in their node sets. We note that this formulation also supports edge attributes (see Section 4) and easily extends to edge-induced subgraphs by replacing node masks with edge-membership masks. The model is trained on a dataset of annotated graphs {(Gi , Si∗ )}ni=1 , where each Si∗ enumerates the instances present in Gi . At inference time, given an unseen graph G, the goal is to predict a set Ŝ that matches the complete set S ∗ of all instances. 3.2
Graph Encoder
The encoder maps each node to an embedding that captures its features and structural context, producing a matrix H ∈ RN ×D . Any graph neural network that produces per-node embeddings can serve as the backbone. A vital aspect of the encoder is its expressive power, which directly influences the decoder’s ability to recover subgraph instances. More precisely, if two nodes receive identical embeddings, the decoder cannot distinguish them and will produce identical mask scores for both across all queries, making it impossible to assign them to different instances. Note that for nodes in the same orbit of the graph’s automorphism group, no deterministic equivariant encoder can produce distinct embeddings. However, stochastic mechanisms such as random-walk sampling can break this symmetry, alleviating this issue. Complementary to discriminability, the encoder should produce representations that are structurally informative, encoding sufficient subgraph context for the decoder to determine pattern membership. As one source of expressivity and structural signal, encoders optionally incorporate a Random Walk Structural Encoding (RWSE) [10], which enriches each node with random-walk return probabilities at increasing hop distances. We study three encoder families that differ in their expressivity and how they capture structural context. Message-passing neural networks (MPNNs). We consider GCN [16], GIN [30], and GatedGCN [3] equipped with the training recipes of Luo et al. [21]. MPNNs iteratively aggregate neighborhood information. Their expressivity is bounded by the 1-WL test [30], meaning they assign identical representations to nodes that the 1-WL algorithm fails to distinguish. Graph transformers. We use GraphGPS [25], which combines local message passing with global self-attention, allowing each node to aggregate information beyond its immediate neighborhood. This allows each node to aggregate both local structural information and long-range context within each layer. Despite this richer inductive bias, graph transformers remain permutation-symmetric in the standard formulation. Random-walk neural networks. We employ NeuralWalker [6] which combines random walks with message passing. It samples random walks from each node, encodes node and edge features along each walk with identity and adjacency encodings, and processes the resulting sequences with a sequence model. These structural encodings allow the model to identify induced subgraphs along walks, producing node representations that are informed by rich subgraph structure. Moreover, because each walk traces a unique trajectory through the graph, nodes at different positions receive distinct embeddings even when their local neighborhoods are isomorphic, breaking the symmetry that limits both MPNNs and standard graph transformers. 3.3
Two-Way Transformer Decoder
The decoder transforms the per-node embeddings from the encoder into Q instance predictions, each consisting of a class label and a node-membership mask. It maintains Q learnable queries Q ∈ RQ×D and node embeddings H ∈ RN ×D , which are jointly updated by stacking two-way attention blocks, following the bidirectional decoder design of SAM [17, 26]. A fixed positional encoding E q is added to the queries at every layer. We write one block as the following coupled update: Qℓself = fself Qℓ + E q , Qℓ , Qℓ , Qℓcross = fcross Qℓself + E q , H ℓ , H ℓ , Qℓ+1 = fffn Qℓcross , H ℓ+1 = frev H ℓ , Qℓ + E q , Qℓ , 4
where fself , fcross , frev denote multi-head attention modules (query–query, query–node, and node–query, respectively), and fffn is a position-wise feedforward network. Standard LayerNorm and residual connections are applied to each sub-layer. The update is bidirectional. Queries first interact via self-attention, then gather evidence from nodes, while nodes are updated in parallel by attending back to the queries. The reverse attention induces query-conditioned node representations, allowing the mask head to assign different membership scores to the same node under different queries, which becomes necessary when instances overlap. After the final block, a standard cross-attention (Q → H) produces Qout and H ref , which are used by the class and mask heads, respectively. Class head. A linear projection maps each query to logits over C + 1 classes, comprising C foreground pattern classes and a background class ∅: cls
C+1 l̂j = Wcls q out , j ∈R
j = 1, . . . , Q,
(1)
where q out j is the j-th query output from the final decoder block. Mask head. The mask head predicts node-membership logits through a bilinear interaction between a projected query and the query-conditioned node embeddings: mask
l̂j
⊤ N = H ref (Wmask q out j ) ∈R .
(2)
Using H ref rather than the raw encoder output H is critical, because H ref already encodes which queries are attending to which nodes. Thus, the dot-product score measures how relevant each node is to query j’s current hypothesis rather than an unconditional node-query similarity. This gives the mask head access to information that flows in both directions of the decoder. 3.4
Training Objective
The decoder produces a fixed set of Q predictions, while the number of ground-truth instances K varies across graphs, with K < Q in general. Since there is no a priori assignment between predictions and ground-truth instances, training requires a matching step that pairs each ground-truth instance with exactly one prediction. We solve this via the Hungarian algorithm [18] and train with a composite loss on the matched pairs. Hungarian matching. For each graph, we determine an optimal matching σ ∗ : [K] → [Q] that assigns each ground-truth instance to a distinct query. This is achieved using the Hungarian algorithm applied to a cost matrix C ∈ RQ×K that combines a classification term and mask term: cls
mask
Cj,k = − softmax(l̂j )c∗k + λmask LBCE (l̂j , m∗k ) {z } | | {z }
(3)
mask cost
class cost
Since the matching is non-differentiable, gradients flow exclusively through the training loss evaluated on the matched pairs. Unmatched queries j ∈ / σ ∗ ([K]) are assigned the background class. Loss function. Given the matching σ ∗ , the total training loss is given by: L = LCE + λmask Lmask
(4)
where LCE is a cross-entropy loss over all Q query slots. Unmatched slots target class ∅ and are down-weighted by w∅ < 1 to counterbalance the imbalance between the few matched queries and the many background ones. Lmask is applied only to matched pairs: Lmask = LBCE + λcut Lcut .
(5)
The binary cross-entropy term LBCE provides per-node supervision. Graph cut penalty. The term Lcut encodes a structural prior that subgraph instances are connected subgraphs, penalizing edges that cross the predicted membership boundary. For a matched pair, the penalty is computed from the predicted membership probabilities pu = σ(lu ) as follows: 1 X Lcut = pu (1 − pv ) + pv (1 − pu ) . (6) |E| (u,v)∈E
5
Table 1: Functional group detection on ChEMBL12k. All GraphDETR models use Q=40 queries, 5 encoder layers, D=256, RWSE (K=20), and the full loss. NeuralWalker uses the Mamba sequence backend. Results are mean ± std over 5 seeds. Encoder
# Params
GCN GIN GatedGCN GraphGPS NeuralWalker (λmask =2) NeuralWalker (λmask =4)
3.9M 4.9M 5.3M 6.6M 7.4M 7.4M
AP100
mAP50:95
Rec100
mIoU
ExactMatch
0.8669±0.0122 0.8815±0.0104 0.8687±0.0078 0.9191±0.0112 0.9136±0.0165 0.9370±0.0147
0.8766±0.0106 0.8888±0.0100 0.8751±0.0072 0.9230±0.0099 0.9207±0.0164 0.9438±0.0135
0.8631±0.0082 0.8724±0.0043 0.8735±0.0032 0.8923±0.0017 0.9567±0.0102 0.9718±0.0037
0.9768±0.0025 0.9792±0.0037 0.9756±0.0028 0.9812±0.0012 0.9912±0.0036 0.9944±0.0009
0.7424±0.0273 0.7642±0.0153 0.5948±0.0259 0.7460±0.0286 0.8912±0.0264 0.8342±0.0320
Each summand is zero when both endpoints are confidently on the same side of the boundary (p ≈ 0 or p ≈ 1) and reaches 1/2 when they lie on opposite sides. The gradient drives uncertain boundary nodes toward the majority vote of their neighbors, pushing a node inward if most neighbors are predicted inside the subgraph, and outward otherwise (see Appendix D for a full derivation). This implements a differentiable relaxation of the subgraph connectivity constraint without requiring any auxiliary connected-component check during training.
4
Molecular Functional Group Detection
We apply GraphDETR to molecular functional group (FG) detection, an instance-level subgraph detection problem where both the class and the exact atom-membership mask of every FG instance need to be jointly recovered. We evaluate GraphDETR on ChEMBL1 , drawn from ChEMBL-36, containing 2,827,875 molecules across 95 functional group classes. For ablation studies we use ChEMBL12k, a subset of 12,000 molecules. Full dataset details can be found in Appendix E. Evaluation metrics. We adopt an object detection evaluation protocol adapted to graphs. Each predicted node-set mask is matched to a ground-truth instance by Hungarian assignment, using the Intersection over Union (IoU) of their node sets, i.e., |Vpred ∩ Vgt | / |Vpred ∪ Vgt |, as the similarity measure. We report five metrics: AP100 (average precision at IoU = 1.0, macro-averaged over classes), mAP (COCO-style, thresholds 0.50–0.95 in steps of 0.05), Rec100 (recall at IoU = 1.0), mIoU (mean mask IoU over matched true-positive pairs), and ExactMatch (fraction of molecules where every GT instance is matched with IoU ≥ 0.5 and no false positive is active). 4.1
Graph Encoder Comparison
We start by comparing the encoder backbones introduced in Section 3.2, keeping all other components of GraphDETR fixed. As shown in Table 1, GraphDETR achieves strong detection performance across all encoders, demonstrating that the set prediction formulation is effective for this combinatorially rich real-world task. Notably, local MPNN encoders (GCN, GIN, GatedGCN) are consistently outperformed by GraphGPS and NeuralWalker across all precision-oriented metrics, with NeuralWalker achieving the best overall performance. This likely stems from the stronger ability of GraphGPS and NeuralWalker to capture global structural context, in contrast to the purely local aggregation of MPNNs. Among local encoders, GatedGCN achieves competitive AP100 but its ExactMatch (i.e., the ability to find all instances exactly) is substantially lower than both GCN and GIN, suggesting that it struggles to cleanly separate co-occurring instances at the molecule level. Furthermore, it is notable that mIoU is uniformly high across all encoders, which shows that matched pairs are well localized regardless of backbone. Differences between encoders are therefore most pronounced in recall and ExactMatch rather than in the quality of masks for already-identified instances. Data scaling (Figure 3). We further evaluate how detection performance scales with training data size on the full ChEMBL dataset. Both GIN and NeuralWalker improve log-linearly as the number of training molecules grows, with NeuralWalker consistently ahead. The parallel slopes suggest that NeuralWalker’s advantage over GIN does not erode with scale, pointing to a structural rather than a data-driven benefit. 1 https://chembl.gitbook.io/
6
Table 2: Loss ablation (OFAT) on the ChEMBL12k dataset. Each row adds one loss component relative to the previous.
Figure 3: Data scaling on ChEMBL (AP100 , test set). Encoders improve log-linearly with scale, with NeuralWalker consistently ahead. 100
CE only + BCE + BG weight Full (+ cut)
AP100 0.4 85.4 92.4 94.3
ExactMatch 0.8 79.1 84.8 81.8
Rec100
AP100 (%)
Loss
0.5 95.0 97.1 97.2
GIN NeuralWalker
91.2
90 80
86.6
87.5 84.9
87.3
80.7
70 104
105 106 Training molecules
107
Table 3: Decoder ablation (OFAT) on the ChEMBL12k validation set. Baseline: NeuralWalker encoder with # layers=3, # queries=40, h=8 heads, attn downsample rate r=2. Each row varies exactly one axis. Varied axis
4.2
Value
AP100
mAP
Rec100
mIoU
ExactMatch
baseline
–
0.9429
0.9497
0.9720
0.9939
0.8180
# layers # layers
1 2
0.8983 0.9207
0.9050 0.9273
0.9493 0.9690
0.9885 0.9936
0.8100 0.8460
# queries # queries # queries
10 20 30
0.8674 0.9296 0.9166
0.8822 0.9371 0.9247
0.9107 0.9563 0.9635
0.9858 0.9924 0.9925
0.7080 0.8180 0.8420
# attn heads
4
0.8953
0.9064
0.9502
0.9893
0.7020
attn downsample rate attn downsample rate
1 4
0.9062 0.9312
0.9169 0.9411
0.9639 0.9739
0.9923 0.9949
0.8500 0.9000
Ablation and Hyperparameter Studies
In this section, we ablate key components of GraphDETR and study the sensitivity to central hyperparameters on the ChEMBL12k dataset. Specifically, we examine the contribution of each loss term, the impact of the decoder capacity, and the sensitivity of the NeuralWalker encoder to its hyperparameter choices. Qualitative predictions on held-out test molecules are provided in Appendix G. Loss components (Table 2). We ablate the training objective introduced in Section 3.4 by progressively adding each loss term. Without mask supervision, the model fails to localize instances entirely, confirming that cross-entropy supervision (CE) on class predictions alone is insufficient for instance-level detection. Adding the binary cross-entropy mask loss (BCE) recovers most of the performance, and down-weighting the background class (BCE+BG weight) further reduces false positive predictions substantially. Finally, the full objective, which additionally includes the graph cut penalty (Full+cut), further improves AP100 and Rec100 , though at a slight cost to ExactMatch. Decoder capacity (Table 3). We study the effect of the main architectural hyperparameters of the two-way transformer decoder (Section 3.3), i.e., the number of attention blocks, query slots, and attention heads. Furthermore, we analyze the effect of the downsample rate r, which compresses the attention key/value dimensions to D/r. Reducing the number of attention blocks degrades AP100 gradually, suggesting that decoder depth contributes meaningfully to detection performance. Concerning the number of query slots Q, it can be observed that Q=10 leads to a sharp performance drop, possibly because many molecules contain more than 10 functional group instances, leaving the decoder unable to cover them all simultaneously. The rather gradual degradation observed at higher values of Q may reflect the decreasing fraction of molecules affected as Q grows. Turning to the number of attention heads, we find that halving from 8 to 4 causes a larger performance drop than any reduction in depth, showing that multi-head diversity is particularly important for decoder performance. Finally, increasing the attention downsample rate r improves ExactMatch notably at a mild cost to AP100 , possibly suggesting that compressing the key/value space acts as a form of regularization that promotes more decisive mask predictions. NeuralWalker encoder sensitivity (Table 4). Given that NeuralWalker achieves the best overall performance in Section 4.1, we study the sensitivity of its key parameter choices, i.e., the number of NeuralWalker blocks, walk length, and the use of RWSE and edge features. The number of NeuralWalker blocks L has only a modest effect on performance across the tested values, with AP100 improving gradually with depth while ExactMatch peaks at an intermediate value and then 7
Table 4: NeuralWalker encoder ablation (OFAT) on the ChEMBL12k validation set. Value
Layers L
Walk ℓ
RWSE
AP100
baseline
–
5
20
✓(K=20)
0.9429
# layers # layers # layers
2 3 4
2 3 4
20 20 20
✓ ✓ ✓
0.9122 0.9130 0.9352
walk length walk length
10 40
5 5
10 40
✓ ✓
0.9292 0.8931
RWSE
✗
5
20
✗
edge attr
off
5
20
✓
Varied axis
mAP
Rec100
mIoU
ExactMatch
0.9497
0.9720
0.9939
0.8180
0.9230 0.9219 0.9428
0.9617 0.9688 0.9715
0.9910 0.9930 0.9931
0.8380 0.8530 0.8480
0.9344 0.9021
0.9581 0.9625
0.9918 0.9931
0.8500 0.8540
0.9225
0.9292
0.9635
0.9921
0.8480
0.9170
0.9246
0.9678
0.9921
0.8240
slightly declines. Turning to walk length, an optimum is observed at ℓ=20, with shorter walks providing insufficient structural context and, interestingly, longer walks actively hurting performance. Removing RWSE, which enriches node features with random-walk return probabilities, leads to a meaningful drop in AP100 , suggesting that it provides further structural information beyond what the walk sequences themselves capture. Finally, ablating edge features also leads to a meaningful drop in AP100 , confirming that edge attributes provide further useful structural signal for instance detection.
5
General Subgraph Detection Capabilities
To assess the generality of GraphDETR beyond molecular graphs, we evaluate it on a diverse set of subgraph detection benchmarks covering exact and approximate pattern matching across a wide range of graph sizes and pattern types. In addition, we provide inference runtimes and study the ability of trained models to generalize to larger graphs than those seen during training. We evaluate on five dataset families: Cactus graphs in which cycles of varying lengths are the query patterns, bipartite graphs with injected k-cliques as query patterns, ZINC12k [11] where frequent molecular subgraphs serve as query patterns, Mol-Reddit where molecular structures injected into social network host graphs are the targets of detection, and fuzzy variants of the Cactus and Clique datasets where instances only approximately match the query pattern. For the Cactus and Clique datasets, the graph generation procedure is designed to prevent accidental pattern occurrences, ensuring complete ground-truth annotations. For ZINC12k, completeness is guaranteed by the exhaustive frequent subgraph enumeration. Full details are provided in Appendix E. We report AP100 as the primary metric, following the same evaluation protocol as in Section 4. Model configuration follows Section 4, with hyperparameters listed in Appendix F.2. Exact detection (Table 5). We start by examining exact subgraph detection across the synthetic benchmarks. As in Section 4.1, NeuralWalker and GraphGPS consistently outperform local MPNN encoders across all datasets, confirming that global structural context is beneficial beyond the molecular setting. Performance on Cactus graphs degrades substantially with graph size, which is expected given that both the host graphs and the cycle patterns grow larger, making disambiguation increasingly difficult. In contrast, performance on Clique graphs remains strong even as the clique size grows, suggesting that the dense connectivity of cliques provides a distinctive structural signature that is easier to detect regardless of size. ZINC12k and Mol-Reddit present a different challenge as they involve attributed graphs with molecular (sub-)structures as patterns. Notably, NeuralWalker performs particularly strongly on Mol-Reddit, which is arguably the most challenging dataset due to its incomplete annotations and large, varied host graphs. Approximate detection (Table 5). We further evaluate GraphDETR on approximate pattern matching, where instances are defined by their proximity to a canonical query pattern under graph edit distance (GED). The task requires separating instances whose GED to the canonical pattern falls below a threshold from those that do not, which is challenging because GED computation is itself NP-hard. Despite this difficulty, GraphDETR achieves surprisingly strong performance on both fuzzy datasets, demonstrating that it can learn to implicitly discriminate between structurally similar subgraphs purely from data, without any explicit GED computation. This is particularly striking as the model must correctly reject subgraphs that differ from the query pattern by only a small number of edits, a fine-grained structural distinction that emerges purely from training. Runtime (Table 6). We compare the inference runtime of GraphDETR against VF2 [9], which is the de facto standard algorithm for subgraph isomorphism, a highly optimized combinatorial baseline. 8
Table 5: Synthetic subgraph detection in AP100 %. n/m denotes the average number of nodes/edges. Dataset
Patterns (#)
Attr.
GraphDETR encoder
Stats
GIN
GraphGPS
NeuralWalker
Cactus40 Cactus200 Cactus1000 Cliques100 Cliques200 Cliques400 ZINC12k Mol-Reddit
(3-8)-cycles (6) (11-16)-cycles (6) (27-32)-cycles (6) 5-clique (1) 10-clique (1) 20-clique (1) frequent subgraphs (9) injected molecules (10)
✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗
n = 40, m = 45 n = 200, m = 204 n = 1000, m = 1004 n = 140, m = 350 n = 290, m = 1450 n = 590, m = 5900 n = 23, m = 25 n = 441, m = 517
92.33±0.56 42.80±3.16 10.46±3.04 90.94±2.48 90.33±1.46 92.51±2.85 89.68±0.88 65.68±1.11
92.98±0.90 41.51±4.45 4.82±7.30 93.31±0.74 92.84±2.20 94.12±1.51 92.86±0.25 62.12±1.31
96.51±0.43 83.67±0.78 40.22±0.68 97.05±1.60 96.45±1.17 95.05±3.23 95.28±0.13 80.78±1.32
97.44±0.44 91.90±2.41 42.20±2.06 96.15±0.57 93.48±2.35 92.58±3.48 97.66±0.27 89.76±0.97
Cactus-fuzzy Cliques-fuzzy
fuzzy (7-10)-cycles (4) fuzzy 8-clique (1)
✓ ✗
n = 100, m = 105 n = 170, m = 470
67.78±1.17 95.05±1.02
76.19±2.03 95.26±0.89
84.86±0.51 96.66±0.86
90.91±2.88 93.94±2.10
Table 6: Inference runtime (s / graph). VF2 uses a 60 s per-graph budget; † marks datasets where VF2 timed out on >80% of test graphs. GraphDETR runtimes are means across seeds.
100
VF2 [9]
GCN
GIN
GPS
NW
0.068 2.799 60† 0.120 60† 60† 0.010 51† – –
5.4e-5 9.3e-5 0.0002 5.8e-5 8.5e-5 0.0002 5.5e-5 0.0002 5.6e-5 6.1e-5
5.2e-5 9.2e-5 0.0002 6.2e-5 9.0e-5 0.0002 5.3e-5 0.0002 5.6e-5 6.6e-5
9.8e-5 0.0002 0.0009 0.0001 0.0003 0.0007 9.9e-5 0.0021 0.0001 0.0002
0.0014 0.0174 0.0412 0.0041 0.0038 0.0079 0.0021 0.0125 0.0045 0.0043
80
AP100 (%)
Cactus40 Cactus200 Cactus1000 Cliques100 Cliques200 Cliques400 ZINC12k Mol-Reddit Cactus-fuzzy Cliques-fuzzy
Figure 4: Generalization to larger graphs. AP100 of a single model trained on small graphs, evaluated at increasing graph sizes. Left: trained on Cactus40. Right: trained on Cliques100.
GraphDETR
Dataset
GCN
60 40 20 0 40 50 60 70 80 90 100
140 160 180 200 220 240
Graph size
Graph size
GCN
GIN
GraphGPS
NeuralWalker
Nevertheless, VF2 fails to terminate within the provided time budget on a large amount of test graphs across several datasets, while GraphDETR processes all graphs in a single forward pass at runtimes several orders of magnitude lower. This gap widens with graph size, consistent with the exponential worst-case complexity of combinatorial subgraph isomorphism search, while GraphDETR maintains low runtimes even on the largest graphs. Generalization to larger graphs (Figure 4). We evaluate the ability of a single model trained on small graphs (Cactus40 and Cliques100) to generalize to increasingly larger graphs at test time. For cycles, all encoders significantly degrade as graph size grows, with NeuralWalker and GraphGPS degrading slightly slower than MPNNs. For cliques, the picture is more nuanced and somewhat surprising. GraphGPS proves to be the most robust encoder, maintaining strong performance well beyond the training distribution, while NeuralWalker degrades more significantly at larger graph sizes despite being the best encoder in-distribution.
6
Conclusion
This work introduced GraphDETR, an end-to-end framework for subgraph detection that casts the problem as set prediction. By combining graph encoders with a two-way transformer decoder and bipartite matching, the model predicts the complete set of subgraph instances in a single forward pass, eliminating the need for combinatorial search or post-processing. This formulation naturally supports both exact and approximate matching, extending beyond the rigid constraints of classical subgraph isomorphism. Empirical results across molecular and synthetic benchmarks demonstrate that GraphDETR achieves strong detection performance, scales to large graphs, and operates with orders-of-magnitude faster inference than traditional algorithms. The analysis further highlights the importance of expressive graph encoders and the role of global structural context in instance-level graph reasoning. More broadly, the proposed set prediction perspective provides a general and flexible framework for structured prediction on graphs and a useful framework for evaluating expressive graph encoders. Future work may explore richer query conditioning, improved scalability to even larger graphs, and extensions to other structured outputs such as edge-induced subgraphs or hierarchical patterns. 9
Acknowledgments and Disclosure of Funding The authors would like to thank Cheng-Wei Liao for his insightful discussions, which have inspired this work.
References [1] Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. SimGNN: A neural network approach to fast graph similarity computation. In ACM International Conference on Web Search and Data Mining (WSDM), pages 384–392, 2019. 3 [2] Guy W Bemis and Mark A Murcko. The properties of known drugs. 1. molecular frameworks. Journal of medicinal chemistry, 39(15):2887–2893, 1996. 15 [3] Xavier Bresson and Thomas Laurent. arXiv:1711.07553, 2017. 2, 4
Residual gated graph convnets.
arXiv preprint
[4] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In Proceedings of the European Conference on Computer Vision (ECCV), pages 213–229. Springer, 2020. 2, 3 [5] Dexiong Chen, Leslie O’Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning (ICML), pages 3469–3489. PMLR, 2022. 2 [6] Dexiong Chen, Till Hendrik Schulz, and Karsten Borgwardt. Learning long range dependencies on graphs via random walks. In International Conference on Learning Representations (ICLR), 2025. URL https://openreview.net/forum?id=kJ5H7oGT2M. 2, 4 [7] Bowen Cheng, Ishan Misra, Alexander G Schwing, Alexander Kirillov, and Rohit Girdhar. Masked-attention mask transformer for universal image segmentation. In Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR), pages 1290–1299, 2022. 2 [8] Gonzalo Colmenarejo. Efgs: a complete and accurate implementation of Ertl’s functional group detection algorithm in RDKit. Journal of Chemical Information and Modeling, 65(3): 1061–1066, 2025. 15 [9] Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub) graph isomorphism algorithm for matching large graphs. Transactions on Pattern Analysis and Machine Intelligence (PAMI), 26(10):1367–1372, 2004. 1, 3, 8, 9 [10] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations (ICLR), 2022. 4 [11] 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 (JMLR), 24(43):1–48, 2023. 8 [12] Peter Ertl. An algorithm to identify functional groups in organic molecules. Journal of Cheminformatics, 9(1):36, 2017. doi: 10.1186/s13321-017-0225-z. 15 [13] Dedre Gentner. Structure-mapping: A theoretical framework for analogy. Cognitive science, 7 (2):155–170, 1983. 1 [14] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020. 15, 16 [15] Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International Conference on Machine Learning (ICML), pages 2186–2195. PMLR, 2018. 2 10
[16] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017. URL https://openreview.net/forum?id=SJU4ayYgl. 2, 4 [17] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al. Segment anything. In Proceedings of the International Conference on Computer Vision (ICCV), pages 4015–4026, 2023. 2, 4 [18] Harold W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2):83–97, 1955. 2, 5 [19] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In International Conference on Machine Learning (ICML), pages 3835–3845. PMLR, 2019. 3 [20] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations (ICLR), 2019. URL https://openreview.net/ forum?id=Bkg6RiCqY7. 17 [21] Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Can classic gnns be strong baselines for graph-level tasks? simple architectures meet excellence. In International Conference on Machine Learning (ICML), pages 41290–41310. PMLR, 2025. 4 [22] Siegfried Nijssen and Joost N Kok. A quickstart in frequent structure mining can make a difference. In Proceedings of the international conference on Knowledge discovery and data mining (KDD), pages 647–652, 2004. 15, 16 [23] Paolo Pellizzoni, Till Hendrik Schulz, and Karsten Borgwardt. Graph neural networks can (often) count substructures. In International Conference on Learning Representations (ICLR), 2025. 3 [24] Eric Plotnick. Concept mapping: A graphical system for understanding the relationship between concepts. ERIC Clearinghouse on Information and Technology Syracuse, NY, 1997. 1 [25] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, 2022. 2, 4 [26] Nikhila Ravi, Valentin Gabeur, Yuan-Ting Hu, Ronghang Hu, Chaitanya Ryali, Tengyu Ma, Haitham Khedr, Roman Rädle, Chloe Rolland, Laura Gustafson, et al. SAM 2: Segment anything in images and videos. In International Conference on Learning Representations (ICLR), 2025. 2, 4 [27] John W Raymond, Eleanor J Gardiner, and Peter Willett. Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm. Journal of Chemical Information and Computer Sciences, 42(2):305–316, 2002. 1 [28] Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL https://openreview.net/forum?id=vgXnEyeWVY. 2 [29] Julian R Ullmann. An algorithm for subgraph isomorphism. Journal of the ACM (JACM), 23 (1):31–42, 1976. 1, 3 [30] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019. 2, 4 [31] Pinar Yanardag and Svn VN Vishwanathan. Deep graph kernels. In International conference on knowledge discovery and data mining (KDD), pages 1365–1374, 2015. 16 [32] Qingwu Yang and Sing-Hoi Sze. Path matching and graph matching in biological networks. Journal of Computational Biology, 14(1):56–67, 2007. 1 11
[33] 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? In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 28877–28888, 2021. 2 [34] Zhitao Ying, Andrew Wang, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, and Jure Leskovec. Neural subgraph matching, 2021. URL https://openreview.net/forum?id= LMslR3CTzE_. 1, 3 [35] Barbara Zdrazil, Eloy Felix, Fiona Hunter, Emma J Manners, James Blackshaw, Sybilla Corbett, Marleen De Veij, Harris Ioannidis, David Mendez Lopez, Juan F Mosquera, et al. The chembl database in 2023: a drug discovery platform spanning multiple bioactivity data types and time periods. Nucleic acids research, 52(D1):D1180–D1192, 2024. 15 [36] Hao Zhang, Feng Li, Shilong Liu, Lei Zhang, Hang Su, Jun Zhu, Lionel Ni, and Heung-Yeung Shum. DINO: DETR with improved denoising anchor boxes for end-to-end object detection. In International Conference on Learning Representations (ICLR), 2022. 2
12
Appendix The appendix provides supplementary technical and experimental materials. It is organized as follows: Section A discusses the limitations of the proposed approach. Section B provides a discussion on the broader impacts. Section C lists the use of large language models. Section D provides the derivation and analysis of the graph cut penalty used in the training objective. Section E provides details of the datasets used in this work. Section F provides full implementations for reproducibility purposes. Section G provides additional experimental results.
A
Limitations
While GraphDETR demonstrates strong empirical performance and scalability, several limitations remain. First, the approach relies on a fixed number of query slots, which imposes an upper bound on the number of detectable instances per graph. Although this can be mitigated by choosing a sufficiently large number of queries, doing so increases computational cost and may introduce optimization challenges due to a larger proportion of unmatched queries. Second, the model’s performance depends critically on the expressivity of the graph encoder. As discussed in Section 3.2, encoders with limited discriminative power (e.g., standard MPNNs) may fail to distinguish structurally symmetric nodes, which can hinder instance separation. While more expressive architectures, such as Graph Transformers or random-walk-based models, alleviate this issue, they may incur higher computational overhead, and no single model dominates on all datasets. Third, although GraphDETR scales well compared to combinatorial methods, its memory and runtime still grow with graph size due to attention operations in the decoder. This may limit applicability to extremely large graphs without further architectural modifications, such as sparse or hierarchical attention. Fourth, the current formulation is limited to a closed vocabulary of pattern classes observed during training. The model cannot directly generalize to detect entirely novel or unseen subgraph patterns at inference time, in contrast to open-vocabulary detection settings explored in other domains. Enabling open-vocabulary or query-conditioned subgraph detection, where patterns are specified at test time, remains an important direction for future work. Finally, the current formulation assumes access to fully annotated training data with instance-level supervision (i.e., node masks). In many real-world settings, such annotations are costly or unavailable. Extending the framework to weakly supervised or unsupervised settings remains an open challenge.
B
Broader Impacts
GraphDETR provides a general framework for detecting structured patterns in graphs, with potential applications across chemistry, biology, and network science. In molecular science, the ability to accurately detect functional groups and substructures may accelerate drug discovery, retrosynthesis planning, and materials design. By enabling scalable and flexible pattern detection, GraphDETR could support the identification of novel chemical motifs and improve predictive modeling pipelines. In network analysis, the method may facilitate the discovery of recurring structural motifs in social, biological, or technological networks, contributing to a deeper understanding of their organization and function. However, these capabilities also raise potential concerns. In chemistry and biology, improved substructure detection could be misused to design harmful compounds or bypass safety constraints in molecular screening pipelines. In social network analysis, identifying structural patterns at scale may raise privacy concerns if applied to sensitive relational data. 13
Mitigating these risks requires responsible deployment, including adherence to domain-specific regulations, careful dataset curation, and consideration of ethical implications. We emphasize that GraphDETR is a general-purpose modeling framework, and its societal impact depends on the context in which it is applied.
C
Usage of Large Language Models
This work used large language models in the following ways: Preparation of plots LLMs were partly used to generate the code for the plots presented in this work. The correctness of all code and data was checked manually. The data shown in the figures was generated by manually written code. Code development LLMs were used to assist in developing code for data generation, preparing procedural job launching scripts, documenting implemented functions or modules, and integrating existing GNN codebases into the working directory. All code modified by LLMs was manually checked. Polishing of manuscript LLMs were occasionally used to refine or rephrase individual sentences.
D
Graph Cut Penalty: Derivation and Gradient Analysis
Here we describe in more detail the graph cut penalty introduced in Section 3.4. D.1
Loss definition
For a matched pair with predicted membership probabilities pu = σ(lu ) (where σ is the sigmoid function and lu is the per-node logit), the graph cut penalty is 1 X Lcut = pu (1 − pv ) + pv (1 − pu ) . (7) |E| (u,v)∈E
Each summand is the product pu (1−pv ) (node u inside, node v outside) plus pv (1−pu ) (the reverse), and equals zero when both endpoints are on the same side of the boundary (p ≈ 0 or p ≈ 1) and reaches its maximum of 1/2 when they straddle it (pu = pv = 1/2). D.2
Gradient analysis
u Differentiating (7) with respect to logit lu , and using ∂p ∂lu = pu (1 − pu ): ∂Lcut pu (1 − pu ) X (1 − 2pv ). = ∂lu |E|
(8)
v : (u,v)∈E
Three structural properties of this gradient are noteworthy: • Saturated nodes are unaffected. The pre-factor pu (1 − pu ) is zero when pu ∈ {0, 1}, so nodes that are already certain do not receive any gradient from this term, avoiding perturbation of confident predictions. P • Majority-vote pressure. The sum v (1 − 2pv ) is negative when the majority of neighbors have pv > 1/2 (i.e. are predicted inside the subgraph), and positive otherwise. A negative sum decreases the gradient, increasing lu , hence pushing u further inside; a positive sum pushes u outward. The penalty therefore implements a differentiable neighbor-majority constraint. • Boundary sharpening. The gradient is largest for boundary nodes (pu ≈ 1/2) that have disagreeing neighbors, and vanishes at topological interiors or exteriors, focusing learning signal exactly where structural ambiguity is highest.
E
Dataset Descriptions
We provide details of the creation of all datasets used in this work. 14
E.1
Molecular datasets Table 7: Statistics of the ChEMBL and ChEMBL12k dataset.
Dataset
# Graphs
# Classes
Patterns/Graph
Nodes (µ±σ)
Edges (µ±σ)
Nodes [min,max]
Edges [min,max]
ChEMBL ChEMBL12k
2,827,875 12,000
95 95
5.8 ± 2.9 5.8 ± 2.9
29.8 ± 10.4 29.9 ± 10.6
32.4 ± 11.4 32.5 ± 11.5
[1.0,100.0] [5.0,100.0]
[0.0,132.0] [4.0,108.0]
ChEMBL. We construct the ChEMBL dataset from ChEMBL-36 [35] using a scalable preprocessing pipeline. Starting from 2,848,825 molecules, we retain those parseable by RDKit and remove duplicates, yielding 2,827,875 molecules. Functional group instances and their atom-level membership masks are generated by Ertl’s IFG algorithm [12, 8], which provides context-sensitive labeling (e.g., distinguishing amide nitrogen from a free amine). After filtering functional group classes with frequency below 0.1%, the vocabulary contains 95 classes. Molecules are featurized with OGB atom and bond features [14] (9-dimensional atom features, 3-dimensional bond features). The dataset is split 80/10/10 by Bemis–Murcko scaffold [2] to ensure no training scaffold appears at test time. ChEMBL12k. For ablation studies and rapid iteration, we define a 12,000-molecule subset drawn uniformly at random from ChEMBL: 10,000 molecules for training, 1,000 for validation, 1,000 for test. The subset shares the same atom/bond features and FG vocabulary as the full ChEMBL dataset; the split is fixed by a global seed for reproducibility. The statistics of both datasets are provided in Table 7. E.2
Synthetic datasets Table 8: Statistics of all synthetic datasets.
Dataset
# Graphs
# Classes
Patterns/Graph
Nodes (µ±σ)
Edges (µ±σ)
Nodes [min,max]
Edges [min,max]
Cactus40 Cactus200 Cactus1000 Cliques100 Cliques200 Cliques400 ZINC12k Mol-Reddit Cactus fuzzy Cliques fuzzy
12000 12000 12000 12000 12000 12000 12000 11929 12000 12000
6 6 6 1 1 1 9 10 4 1
6.3±1.2 4.8±0.9 4.9±0.9 10.0±0.0 10.0±0.0 10.0±0.0 5.5±3.3 2.1±1.2 4.4±1.3 5.0±1.6
40.0±0.0 200.0±0.0 1000.0±0.0 139.5±0.7 290.0±0.1 590.0±0.0 23.2±4.5 440.7±426.1 100.0±0.0 169.5±0.7
45.3±1.2 203.8±0.9 1003.9±0.9 350.3±15.0 1450.3±30.0 5900.2±60.2 24.9±5.3 516.5±517.0 104.7±0.9 470.3±16.2
[40,40] [200,200] [1000,1000] [135,140] [288,290] [590,590] [9,37] [27,3810] [100,100] [165,170]
[41,49] [201,207] [1001,1007] [298,412] [1346,1564] [5643,6186] [8,42] [30,5333] [101,108] [404,534]
All synthetic datasets are stored in Gaston format, with a target-graph file and a pattern file. Each sample is a host graph together with a set of injected subgraph instances annotated by class label and node mask. Statistics for each dataset are listed in Table 8. Query patterns for each dataset are described in Table 9. Cactus graphs. A cactus graph is generated by sampling a random labeled tree on n nodes and injecting c edge-disjoint cycles of lengths drawn uniformly from a specified range, by identifying tree paths of the required length and closing them into cycles. Each injected cycle forms a chordless induced subgraph by construction. The pattern vocabulary contains one class per distinct cycle length. Node and edge features are omitted (constant feature 1). Clique graphs. A host graph is a random bipartite graph G(nside , nside , p) with nside nodes on each side. Each clique injection replaces a randomly chosen, previously unexpanded node v with a k-clique, where v’s neighbours are rewired to uniformly random nodes in the new clique, and v is deleted. Disconnected graphs are resampled. The single pattern class is the k-clique Kk . ZINC12k. Frequent subgraph patterns are mined from the ZINC12k molecular benchmark using the GASTON algorithm [22] at minimum support 25% and a maximum of 5 occurrences per graph. Nine high-frequency subgraphs with 3–7 atoms are retained as query patterns; only atom type is preserved as a node attribute. Ground-truth instance masks are the GASTON-reported node sets for each occurrence within each molecule. Mined patterns are visualized in Figure 5. 15
Table 9: Synthetic dataset query patterns. Match: whether instances are identified by exact subgraph isomorphism (exact) or approximate structural similarity (fuzzy). Node attr. / Edge attr.: feature type present on nodes / edges; ✗ = unlabeled (constant 1 feature). Dataset
#Classes
Node attr.
Edge attr.
Match
Pattern description
Cactus40
6
✗
✗
exact
Cactus200
6
✗
✗
exact
Cactus1000
6
✗
✗
exact
Cycles of lengths 3–8 (one class per length), each embedded in a cactus host graph (n=40). Same as Cactus40 with cycle lengths 11–16 and larger cactus hosts (n=200). Same setup with cycle lengths 27–32 within larger hosts (n=1000).
Cliques100
1
✗
✗
exact
Cliques200
1
✗
✗
exact
Cliques400
1
✗
✗
exact
ZINC12k
9
atom type
✗
exact
Mol-Reddit
10
✗
✗
exact
Cactus-fuzzy
4
binary
✗
fuzzy
Cliques-fuzzy
1
✗
✗
fuzzy
Complete graph K5 (5 nodes, 10 edges). Injected into random bipartite hosts (n=50 per part) by replacing a randomly chosen node with a 5-clique and rewiring its incident edges to uniformly random clique members. Complete graph K10 ; same injection procedure, larger bipartite host (n=100 per part). Complete graph K20 (20 nodes, 190 edges); same injection procedure, much larger bipartite host (n=200 per part). Nine frequent molecular subgraphs (3–7 nodes each) mined from ZINC12k by the GASTON algorithm [22] at minimum support 25% and max occurrences of 5 per graph. Mined patterns are illustrated in Figure 5. Ground-truth instance masks are the GASTON-reported node sets for each occurrence within each molecule. Ten molecular structures (19–62 nodes) with all atom and bond features discarded (pure topology) are randomly sampled from the Molhiv dataset of OGB [14]. Each structure is injected as a node-disjoint subgraph into a host graph drawn from REDDITMULTI-12K [31], with the number of attachment edges sampled from a Poisson distribution of mean 2. The host may contain unlabeled background motifs isomorphic to the injected patterns, requiring the model to distinguish true instances from background. Patterns are shown in Figure 6. Target graphs are cactus graphs containing cycles of lengths k ∈ {7, . . . , 10} as patterns. Each node receives a uniformly random label from {1, 2}. The canonical pattern for length k is a k-cycle with alternating labels 1-2-1-2-· · · . An cycle is annotated as an instance if its graph edit distance to the canonical pattern is at most τGED = 3; otherwise it is treated as background noise. The injection procedure follows the exact-match Cliques setting, but each injected k-clique is subsequently perturbed by randomly removing internal edges. Each injection is independently classified as an instance (with probability 50%) or as noise. Instances have 4 edges removed, while noise cliques have 8 edges removed, yielding a more aggressive perturbation. Only instances are annotated with ground-truth masks; noise cliques are present in the target graphs but not annotated, requiring the model to distinguish between mild and heavy perturbations.
Mol-Reddit. Molecular structures (query patterns) are injected into social network host graphs drawn from REDDIT-MULTI-12K [31]. Ten molecular structures are randomly sampled from the Molhiv dataset of OGB [14] as pattern classes; their node features are discarded (constant 1), leaving only the topology for detection. Each injection adds a molecular subgraph as a node-disjoint component of the host graph, with ∼2 (following a Poisson distribution) random attachment edges connecting the molecule to the host. This dataset emulates the scenario of incomplete annotations: the original social network may contain graph motifs that are isomorphic to injected molecules, which are not labeled, so the model must distinguish true injected instances from background structure. The patterns are visualized in Figure 6.
Fuzzy Cactus. Each node is assigned a binary label drawn uniformly from {1, 2}. The pattern class for a cycle of length k is a canonical k-cycle with alternating labels 1-2-1-2-· · · . An injected cycle is considered a proper instance if its node-label sequence differs from the canonical pattern (over all rotations and reflections) by at most τGED substitutions; otherwise it is treated as background noise. Four cycle-length classes (7–10) are used, with the graph size set to n ≈ 100 nodes. 16
C
O
C
C
N
O
C
C
S
N C
N C
O C
N
C
N
C C
C
O
C C
C
C
C
C
O
C
C
C
C
C
C
N C
C
N C
C
C
C
C C
C
C
Figure 5: Query patterns for ZINC12k pattern 0 62 nodes · 64 edges
pattern 1 19 nodes · 20 edges
pattern 5 23 nodes · 27 edges
pattern 6 22 nodes · 24 edges
Mol-Reddit Dataset -- Query Patterns pattern 2 25 nodes · 27 edges
pattern 3 19 nodes · 20 edges
pattern 4 21 nodes · 23 edges
pattern 7 21 nodes · 22 edges
pattern 8 18 nodes · 19 edges
pattern 9 25 nodes · 28 edges
Figure 6: Query patterns for Mol-Reddit
Fuzzy Cliques. The injection procedure follows the exact-match Cliques setting, but each clique is subsequently perturbed by removing a random subset of its internal edges, yielding an approximate clique pattern. A fraction of injections are designated as noise (with probability pnoise = 0.5) and receive more aggressive edge removal; only proper injections are annotated in the pattern file. The single pattern class is a fuzzy 8-clique (k=8) injected into bipartite host graphs.
F
Implementation Details
F.1
Training setup
All models are trained with the AdamW optimiser [20] with weight decay 10−4 . The learning rate follows a linear warm-up over 100 steps to the peak learning rate, followed by cosine decay. Gradients are clipped to unit norm. All models are trained with PyTorch Lightning on a single GPU per run. For the molecular task (ChEMBL12k), models are trained for up to 200 epochs with batch size 128. For synthetic tasks, epochs and batch sizes are adjusted per dataset owing to the wide range of graph sizes. All results are reported as mean ± std over 5 random seeds. F.2
Hyperparameters
Table 10 lists the hyperparameters used for the main ChEMBL12k and ChEMBL experiments. Table 11 lists the search grid for the tuned hyperparameters; the other hyperparameters remain the same as for ChEMBL. 17
Table 10: Hyperparameters for the main GraphDETR configuration on ChEMBL12k and ChEMBL. Hyperparameter
Value
Description
Model D (hidden dim) Q (# queries) encoder blocks
256 40 5
RWSE dim K
20
Shared embedding dimension Number of learnable query slots Number of graph encoder blocks for GCN/GIN/GraphGPS/NeuralWalker Random-walk structural encoding steps in the graph encoder
Two-way transformer decoder Ldec (blocks) 3 h (attention heads) 8 dff (feedforward) 512 r (downsample rate) 2
Number of two-way transformer decoder blocks Multi-head attention heads MLP hidden dimension Attention key/value dimension = D/r
NeuralWalker encoder walk length ℓ walks per node (train) walks per node (test) sequence backend dconv dstate window size W bidirectional
20 1 5 Mamba 9 16 8 ✗
Walk sequence length Random walks sampled per node Walks at inference time SSM sequence model Conv1d kernel width Mamba SSM state size Structural encoding context Forward-only walk processing
Loss λmask λcut w∅
4.0 0.1 0.1
Mask loss total weight Graph cut penalty relative weight Background class CE weight
Optimisation optimiser learning rate weight decay warmup steps max epochs gradient clip norm batch size
AdamW 10−3 10−4 100 200 1.0 128
Peak learning rate AdamW weight decay Linear warm-up steps ChEMBL12k training budget Graphs per batch
Table 11: Hyperparameter search grids for GraphDETR on synthetic datasets. Hyperparameter Search grid or values Q (# queries) λcut batch size NeuralWalker walk length
F.3
{20, 40, 60} {0.0, 0.001, 0.01, 0.1} we adjust it based on the graph sizes in the dataset 20 for Cactus40, ZINC12k, Cactus fuzzy, 5 for Cliques100, Cliques200, Cliques400, Cliques fuzzy, 50 for Mol-Reddit, 200 for Cactus200, 1000 for Cactus1000.
Computing resources
All experiments are run on a GPU cluster with NVIDIA A100 or H100 GPUs. A single ChEMBL12k run (200 epochs) completes in under 8 hours on one GPU. A full ChEMBL run (5 encoder layers, batch size 128) takes approximately one day on a single GPU. Synthetic dataset runs vary from a few hours (Cactus40, Cliques100) to over one day (Cactus1000, Mol-Reddit) depending on graph size. 18
G
Additional Results
G.1
Full synthetic results
Table 12 reports all five evaluation metrics for every encoder–dataset combination. Table 12: Full synthetic results. All five metrics for every encoder–dataset combination (mean ± std over 5 seeds).
G.2
Dataset
Encoder
AP100
mAP
Rec100
mIoU
ExactMatch
Cactus40
GCN GIN GraphGPS NeuralWalker
92.33±0.56 92.98±0.90 96.51±0.43 97.44±0.44
95.55±0.19 95.98±0.42 97.84±0.21 98.27±0.24
95.37±0.26 95.76±0.42 97.82±0.23 98.66±0.29
99.14±0.05 99.21±0.11 99.57±0.04 99.77±0.04
81.83±2.30 83.77±1.32 89.63±0.83 84.02±1.79
Cactus200
GCN GIN GraphGPS NeuralWalker
42.80±3.16 41.51±4.45 83.67±0.78 91.90±2.41
57.86±5.04 52.94±3.82 92.17±0.64 95.78±1.60
55.65±3.87 53.47±3.04 90.44±0.55 94.08±1.55
93.70±0.94 93.84±2.06 98.96±0.06 99.34±0.17
18.12±10.59 9.20±4.25 84.12±1.16 71.98±13.66
Cactus1000
GCN GIN GraphGPS NeuralWalker
10.46±3.04 4.82±7.30 40.22±0.68 42.20±2.06
17.75±4.38 7.83±11.85 47.00±0.26 61.51±2.58
18.44±3.01 7.97±11.74 45.69±0.29 57.81±2.08
89.25±1.46 35.37±48.44 94.86±0.31 94.06±0.44
0.00±0.00 0.07±0.15 3.70±0.40 0.32±0.37
Cliques100
GCN GIN GraphGPS NeuralWalker
90.94±2.48 93.31±0.74 97.05±1.60 96.15±0.57
94.03±1.56 96.03±0.47 98.16±0.79 97.40±0.41
93.53±1.75 95.52±0.57 98.02±1.17 97.71±0.39
98.73±0.34 99.04±0.11 99.58±0.25 99.49±0.09
69.90±7.65 88.23±4.25 96.00±4.74 95.93±1.06
Cliques200
GCN GIN GraphGPS NeuralWalker
90.33±1.46 92.84±2.20 96.45±1.17 93.48±2.35
95.21±0.90 96.69±1.04 98.23±0.50 97.17±0.77
93.91±0.59 95.42±1.85 97.94±0.88 96.08±1.41
99.11±0.12 99.31±0.27 99.72±0.14 99.45±0.17
86.47±10.14 95.63±2.39 97.92±1.64 97.18±1.92
Cliques400
GCN GIN GraphGPS NeuralWalker
92.51±2.85 94.12±1.51 95.05±3.23 92.58±3.48
95.91±2.54 97.49±0.54 98.14±0.99 97.53±0.84
95.11±2.07 96.31±0.58 97.06±2.34 95.77±1.66
99.37±0.33 99.63±0.06 99.72±0.28 99.60±0.16
87.28±15.53 95.42±1.13 98.35±2.25 97.78±0.66
ZINC12k
GCN GIN GraphGPS NeuralWalker
89.68±0.88 92.86±0.25 95.28±0.13 97.66±0.27
93.78±0.47 95.60±0.10 97.15±0.07 98.60±0.16
93.47±0.52 95.33±0.15 97.08±0.24 98.79±0.18
98.71±0.14 99.11±0.04 99.38±0.08 99.75±0.04
84.70±2.34 88.73±1.33 92.58±2.64 94.73±1.33
Mol-Reddit
GCN GIN GraphGPS NeuralWalker
65.86±1.11 62.12±1.31 80.78±1.32 89.76±0.97
85.05±0.67 82.67±0.92 90.67±1.08 95.26±0.42
76.04±0.59 73.45±0.93 84.59±1.44 93.12±0.60
96.51±0.20 96.15±0.24 97.51±0.28 98.99±0.13
93.17±0.83 91.89±0.82 95.26±1.12 97.30±0.16
Cactus-fuzzy
GCN GIN GraphGPS NeuralWalker
67.78±1.17 76.19±2.03 84.86±0.51 90.91±2.88
78.07±1.08 84.19±2.42 91.34±0.29 93.19±2.92
85.55±0.92 89.56±0.78 93.57±0.39 97.78±0.35
98.15±0.07 98.70±0.10 99.15±0.16 99.77±0.04
35.83±2.91 45.15±5.97 79.95±1.18 43.38±15.89
Cliques-fuzzy
GCN GIN GraphGPS NeuralWalker
95.05±1.02 95.26±0.89 96.66±0.86 93.94±2.10
96.81±0.57 97.22±0.46 98.05±0.48 96.58±0.94
96.83±0.45 96.48±0.62 98.13±0.68 96.32±1.28
99.45±0.06 99.38±0.15 99.65±0.13 99.35±0.20
90.82±1.37 97.37±0.85 99.15±0.55 96.30±1.91
Qualitative results on ChEMBL
We provide in Figure 7 a few examples from the ChEMBL dataset whose functional groups are successfully predicted by GraphDETR.
19
Success 9: 10 FG(s) exact (IoU=1.0) O=[S](=O)([R])[R], O=[C]([R])[N]([R])[R], [R][NH][R], O=[C]([R])[N]([R])[R], [Nar], [Nar], [Nar], [Nar], [Sar], [Nar] CCn1c(C(=O)N(C2CC2)C2CC2)cc2c3c(ncn3C)c(Nc3nc(C)c(C(=O)N4CCS(=O)(=O)CC
Ground Truth
Predicted
FG: O=[S](=O)([R])[R]
FG: O=[C]([R])[N]([R])[R]
FG: [R][NH][R]
FG: [Nar]
FG: [Sar]
Success 12: 7 FG(s) exact (IoU=1.0) O=[S](=O)([R])[O][R], [F][R], [F][R], [F][R], [Cl][R], [Nar], [Sar] O=S(=O)(Oc1nccs1)c1ccc2c(-c3ccc(C(F)(F)F)cc3Cl)cccc2c1
Ground Truth
Predicted
FG: O=[S](=O)([R])[O][R]
FG: [F][R]
FG: [Cl][R]
FG: [Nar]
FG: [Sar]
Success 13: 7 FG(s) exact (IoU=1.0) [R][N]([R])[R], [R][O][R], O=[C]([R])[N]([R])[R], [R][O][R], O=[C]([R])[N]([R])[R], [Cl][R], [R][N]([R])[R] COc1cc2c(cc1OC(C)C)[C@H](c1ccc(Cl)cc1)N(c1ccc(N(C)C[C@H]3CC[C@H](N4CCC
Ground Truth
Predicted
FG: [R][N]([R])[R]
FG: [R][O][R]
FG: O=[C]([R])[N]([R])[R]
FG: [Cl][R]
Success 24: 9 FG(s) exact (IoU=1.0) O=S(=O)([N]([R])[R])[N]([R])[R], [F][R], [F][R], [F][R], [Nar], [Nar], [Sar], [Nar], [Nar] O=S(=O)(Nc1ncns1)N1CCc2c(cccc2-c2ccc(C(F)(F)F)cc2-n2ccnc2)C1
Ground Truth
Predicted
FG: O=S(=O)([N]([R])[R])[N]([R])[R]
FG: [F][R]
FG: [Nar]
FG: [Sar]
Success 27: 5 FG(s) exact (IoU=1.0) O=[S](=O)([R])[N]([R])[R], O=[C]([R])[N]([R])[R], O=[C]([R])[N]([R])[R], O=[C](O)[R], [Nar] Cc1ccc(S(=O)(=O)N[C@@H](Cc2ccc3ccccc3n2)C(=O)N[C@H](C(=O)N[C@H](/C=C(\
Ground Truth
FG: O=[S](=O)([R])[N]([R])[R]
Predicted
FG: O=[C]([R])[N]([R])[R]
FG: O=[C](O)[R]
FG: [Nar]
Figure 7: Visualization of ChEMBL examples whose functional groups are successfully predicted by GraphDETR.
20