acceptodds
Withdrawn from ICLR 2027

Beyond Node Tokens: Motifs as Structural Context for Graph Tokenization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Graph tokenization enables graph-level learning with discrete symbols drawn from a shared vocabulary. A common approach represents each graph as an unordered multiset of quantized node tokens. We analyze the capacity of this representation and empirically unveil the inter-graph token collapse issue, i.e., structurally different graphs can receive highly similar token representations. To remedy this problem, we propose , a graph tokenization framework that uses recurring motifs as reusable structural context. constructs a shared motif vocabulary and learns motif embeddings through soft node matching supervised by motif–graph occurrence, with collision regularization to discourage many-to-one assignments. These embeddings guide node representation learning before quantization, encouraging node tokens to retain both attribute and motif-level information. A Transformer then jointly processes node and motif tokens through token-type-aware attention and motif-conditioned reconstruction of masked node-token embeddings, followed by fine-tuning for graph-level tasks. Empirically, achieves the best mean performance among evaluated methods on almost all classification and regression benchmarks, including a 17.1% reduction in mean absolute error over the strongest evaluated baseline.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph tokenization, subgraph mining, graph foundation models

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_w5hrOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies information loss when a graph is represented as an unordered multiset of quantized node codes, using a counting argument and a token-derived nearest-neighbor/GED diagnostic. It proposes GMT: mine a vocabulary of frequent subgraphs on training graphs; learn reusable motif embeddings with occurrence-supervised soft matching and a collision penalty; use those embeddings to supervise a node encoder before vector quantization; and pretrain a Transformer to reconstruct masked node-code embeddings with motif tokens visible. Tokenizers are then frozen during downstream fine-tuning. Tables 1-2 report the best mean among the evaluated configurations on 11 of 12 datasets, including ZINC MAE 0.150 versus 0.181 for the strongest evaluated baseline.

Critical strengths
  1. The frozen-tokenizer comparisons provide useful evidence for motif augmentation, improving downstream performance in 15 of 16 settings without retraining the node tokenizers.

  2. GMT is evaluated across diverse graph-level tasks and produces shorter inputs than the evaluated BPE-based serializations, with favorable downstream fine-tuning time and memory usage.

Critical weaknesses
  1. GMT combines several training stages and auxiliary objectives, but the current ablations do not fully establish whether this complexity is necessary. In particular, the random-motif-encoder comparison does not establish an advantage over directly learned motif-ID embeddings under the same motif inventory and downstream backbone. Separate ablations of collision regularization and graph–motif ranking would also help distinguish the benefits of the proposed mechanisms from those of simply providing motif information.
  2. Some aspects of the experimental setup make the reported gains difficult to assess. Appendix B.1 describes learned motif selection for unseen graphs, whereas Section 5.3 uses an exactly labeled motif inventory; it remains unclear which protocol supports the main results and how selection errors affect downstream performance. In addition, the reported GraphGPS ZINC MAE of 0.195 is substantially higher than its published result of 0.070. Configuration or training-budget differences may explain this discrepancy, but further detail is needed to assess the strength of the comparison.
Questions for authors
  1. Under a matched training budget, how does GMT compare with a simple learned motif-ID embedding baseline, and which auxiliary objectives provide consistent additional gains?
  2. Could you specify the test-time motif-selection procedure used in Tables 1–2 and the GraphGPS configuration and training budget used for ZINC?
  3. When motif tokens are omitted from the downstream input, does motif-supervised node tokenization still outperform an otherwise identical tokenizer trained without graph–motif ranking?
Reviewer_8tvNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies structural information loss when graphs are represented as unordered bags of quantized node tokens. GMT learns shared motif embeddings from occurrence supervision, uses them to guide node tokenization, and jointly processes node and motif tokens through masked pretraining for graph-level prediction.

Critical strengths

The motivation is clear, and the motif-removal and random-encoder ablations support the utility of motif information.

Critical weaknesses
  1. Motif–node grounding is unclear. The downstream Transformer receives node-code embeddings and selected motif embeddings, with an attention bias distinguishing token types. The paper does not describe an explicit signal linking each motif to its participating nodes. Thus, GMT may encode which motifs occur without representing how nodes compose them or their functional roles across attribute contexts.

  2. The contribution beyond existing hierarchical tokenization needs clearer isolation. HIGHT (Chen et al., ICML 2025) also combines node-, motif-, and graph-level tokens, although for molecule-language alignment. GMT's occurrence supervision is a meaningful difference, but a simple motif-ID/occurrence control under the same protocol would better isolate its value.

  3. The main ablation uses exact motif labels, while test-time selection is predicted. Please report whether the learned-mechanism conclusion holds under the deployable predicted-motif protocol.

Questions for authors
  1. How are motif–node relations represented downstream?
  2. How does the method distinguish the same motif in different attribute/functional contexts?
Reviewer_Jv6rOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper works on quantized node tokenization. One main limitation of previous methods is collapse. This work first did some empirical and theoretically analysis on the collapse, then propose the method GMT which explicitly encoder subgraph patterns to better distinguish graphs with similar node tokens. Specifically, this work use motifs to capture subgraph patterns. In addition, the authors designed several ssl training tasks to better train the model. The experiments on several graph-level tasks show good performance of the proposed GMT.

Critical strengths
  1. The paper is generally well-written and the full pipeline is clearly illustrated. The distinction between intra-graph and inter-graph token collapse provides a useful perspective for analyzing quantized node-token methods.

  2. The method is evaluated on twelve datasets with extensive component ablations. The experiments show that motif information can improve the graph-level representations of several existing quantized node tokenizers, and the results support motifs as useful complementary structural context.

Critical weaknesses
  1. My main concern is the motivation and real advantage. The motivation and advantage of discrete graph tokens are not sufficiently established. The paper largely follows the NLP paradigm of tokenization followed by Transformer pretraining,similar to several existing graph tokenization methods, but graphs already have natural node/edge representations and effective GNN/Graph Transformer architectures.

  2. The experiments do not isolate whether vector quantization is useful: there is no controlled baseline that feeds the continuous GIN node embeddings to the same Transformer while keeping the motif tokens, pretraining objective, and downstream architecture unchanged. Therefore, the current results mainly show that motif context is useful, rather than that motif-aware discrete tokenization is necessary or advantageous.

  3. The claimed shared vocabulary and pretraining do not provide the generalization normally motivating tokenization or foundation models. The motif vocabulary, motif encoder, node VQ codebook, tokenizer, and Transformer pretraining are all trained separately for each target dataset. There is no cross-dataset vocabulary, pretrain-once-and-transfer evaluation, unseen-motif evaluation, or multi-task transfer.

  4. Related work on transferable local-structure vocabularies and graph foundation models, such as RiemannGFM, is not discussed.

5.The method is evaluated only on graph-level tasks; it is unclear how it could support node- or edge-level prediction. All evaluated graphs are also very small, with fewer than 35 nodes on average.

  1. Some reproduced baselines, for example GraphGPS and Exphormer on ZINC, are substantially worse than commonly reported results. Although the authors already explained, but not well convince me
Questions for authors

please see weakness

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.