- Rating
- 2
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This work proposes GLEX, a text‑free graph foundation model for few‑shot cross‑graph transfer. Instead of transferring fixed representations, it leverages executable graph programs that adapt to heterogeneous graphs. GLEX induces graph‑specific program vocabularies, uses a frozen pre‑trained encoder, and conducts closed‑form target adaptation without fine‑tuning. Evaluations on seven datasets yield strong one‑shot node‑classification gains but limited graph‑classification improvements, with key limitations including hand‑crafted program primitives and lack of large‑graph validation.
Critical strengths
- Novel transfer paradigm of executable graph computations: Instead of transferring representations or structural instances, GLEX transfers computation logic. It generates graph‑adaptive outputs without explicit feature alignment. The pretrained encoder is frozen; closed‑form adaptation avoids fine‑tuning and scales with support‑set size for stable few‑shot performance.
- Strong few‑shot node‑level results and solid evaluations: GLEX outperforms the strong baseline BRIDGE by 6.43% on average for one‑shot node classification over seven heterogeneous datasets. It includes thorough ablations, diagnostics and theoretical analysis to back up empirical observations.
Critical weaknesses
- Strong inductive bias from hand‑designed program primitives: Candidate programs are restricted to a manually‑defined pool. Greedy selection only picks existing operators and cannot generate new computation primitives, risking failure for tasks requiring out‑of‑distribution graph operations.
- Unclear practical utility of greedy per‑graph induction & limited generality: Ablations show a fixed program bank works nearly as well on average, so greedy induction helps only for specific datasets. Gains are marginal for graph‑level classification, and real‑world large‑graph experiments are missing.
Questions for authors
- The greedy per‑graph vocabulary induction brings only minor average improvement compared with a fixed program bank. Could you identify what graph properties determine whether this greedy induction yields large empirical gains?
- Why does GLEX obtain substantial improvements for node classification but only marginal gains for graph‑level classification? Is this caused by the program vocabulary itself or by the pooling design for ego‑graphs?
- All program primitives are manually predefined. What failure modes can we expect when target tasks require graph computations outside this hand‑built candidate pool?
- Vocabulary induction involves heavy computation. How does it scale to real‑world large graphs, and can sampling fully mitigate the overhead?
3 comments
W2 & Q2:
Thank you for highlighting the difference between node- and graph-level gains. The smaller graph margin is specific to the comparison with the strong BRIDGE result, rather than a general limitation of GLEX on graph-level tasks. In the main results, GLEX improves over BRIDGE, SAMGPT, and GCOPE by 6.43, 7.60, and 11.90 points for node classification, and by 1.57, 4.65, and 10.64 points for graph classification, respectively, showing that the graph-level gains remain substantial against the other strong baselines.
To further evaluate transfer when each entire graph has its own ground-truth label, we add experiments on the whole-graph datasets PROTEINS, ENZYMES, and NCI1, using the original seven graphs as source domains. All methods use the same settings. GLEX exceeds the strongest baseline BRIDGE by 20.61, 35.32, and 13.66 points on the three datasets, respectively. These results show that the premise of consistently marginal gains on graph-level tasks does not hold: GLEX’s small advantage over BRIDGE is specific to the original ego-graph comparison, rather than a general limitation caused by the program vocabulary or pooling design. We have added this experiment to the revised paper.
| Method | PROTEINS | ENZYMES | NCI1 |
|---|---|---|---|
| GCN | 50.45 | 19.07 | 49.98 |
| GAT | 49.86 | 19.24 | 51.09 |
| BRIDGE | 52.73 | 22.29 | 50.98 |
| GLEX | 73.34 | 57.61 | 64.75 |
W2 & Q4:
Thank you for raising the question of computational scalability and the effect of sampling.
(1) Effectiveness on a large graph. To evaluate whether GLEX remains effective at a substantially larger scale, we further evaluate it on ogbn-arxiv, which contains 169,343 nodes, 1,166,243 directed edges, and 40 classes. We apply SVD to its official 128-dimensional node attributes and use the resulting 16-dimensional inputs for all methods. GLEX achieves 22.43% accuracy, compared with 19.03% for BRIDGE and 15.53% for GraphPrompt. These results confirm that GLEX remains effective on a large attributed graph.
(2) Effectiveness of sampling. Under the default grammar configuration, vocabulary induction first executes 150 candidate programs and then uses their execution values to select the final ten. Each candidate produces a node-by-feature matrix with 169,343 rows (one per node) and 16 columns (one per SVD feature), amounting to 169,343 × 16 = 2,709,488 scalar values per candidate. Without sampling, the selection stage uses all of these values from every candidate. With sampling, it instead retains 512 evenly spaced values per candidate, for a total of 76,800 values across the 150 candidates, and uses them to select the final ten programs. This reduces selection time from 408.76 s to 2.42 s and total induction time from 415.41 s to 9.13 s, while lowering peak process RAM from 9.13 to 3.68 GiB. Candidate generation still takes 6.70 s because every candidate must be executed on the full graph. Sampling therefore removes most of the selection overhead.
The measurements use one fresh CPU process per condition on a Xeon Platinum 8375C with two numerical-library threads. Generation and selection times exclude graph loading and SVD, while peak host RAM includes graph loading and runtime libraries. The two runs use the same rank-16 attribute inputs and differ only in the sampling cap. We have added these results and the corresponding analysis to the revised paper.
| Setting | Scalar values used per candidate | Generation (s) | Selection (s) | Total (s) | RAM (GiB) |
|---|---|---|---|---|---|
| Sampling | 512 | 6.70 | 2.42 | 9.13 | 3.68 |
| No sampling | 2,709,488 | 6.65 | 408.76 | 415.41 | 9.13 |
I appreciate the authors' additional experiments, which address several of my concerns, particularly regarding graph-level performance and scalability. However, the new comparisons with fixed program banks still leave the practical benefit of graph-specific vocabulary induction insufficiently established. Moreover, the reliance on hand-crafted program primitives remains a limitation. I therefore maintain my original score.
Thank you for recognizing the transfer interface and the node-level results. Your concerns are addressed below.
W1 & Q3:
Thank you for raising this important question about the scope and limitations of the predefined grammar. We agree that greedy selection can only choose and compose programs from the predefined grammar; it cannot invent a new primitive at transfer time. This is an intentional inductive bias that keeps every selected program explicit and executable on an unseen graph. The current grammar nevertheless covers a broad family of computations commonly used in graph representation learning, including multi-hop propagation, contrasts between propagation depths, nonlinear scalar transformations, and pointwise feature interactions. Their bounded compositions express multiscale smoothing, high-pass responses, and feature-dependent interactions. The consistent results across citation, co-purchase, social, and whole-graph benchmarks suggest that this scope covers diverse, though not arbitrary, target computations.
Across the diverse benchmarks evaluated in this work, the current grammar provides sufficiently informative programs, and we have not identified a concrete failure case for the complete GLEX pipeline. In principle, a limitation would arise only if two nodes or graphs produced identical outputs under every candidate program while the task required different predictions for them. Selecting among the existing programs could not separate such inputs. This describes a general theoretical boundary of any fixed candidate pool. The framework is also extensible: if a future task reveals a missing computation, the corresponding primitive can be added without changing the vocabulary-selection or adaptation procedure.
W2 & Q1:
Thank you for valuable comment. To examine the practical value of induction, we compare GLEX with four predefined ten-program banks using a fixed SVD rank of 32 and the same one-shot support/query splits. GLEX selects ten programs from unlabeled target-graph executions. Each predefined bank also contains ten programs and shares standardized signals at depths zero, one, and two, while emphasizing a different computation family: low-order multiscale transforms, higher-order transforms, contrasts between propagation depths, or transported nonlinear signals. The original paper reports a compact four-program reference bank; this additional control complements that ablation by comparing vocabulary choices under the same ten-program budget.
No predefined bank is uniformly best across targets. For example, the contrast bank outperforms the transport bank by 8.40 points on LastFM but trails it by 7.59 points on Photo. GLEX achieves 51.71% on average, within 0.11 points of the strongest fixed bank, without target-specific hand selection. Its practical value lies in providing a single label-free rule for choosing a competitive vocabulary on an unseen graph. Manually defining such a bank is difficult: selecting ten programs from the candidate pool creates a large combinatorial space, and the best combination cannot be known before seeing the target. The few labeled examples available in the one-shot setting also provide too little evidence for a reliable target-specific search. We do not observe a simple graph property that predicts the gain. Even within the citation domain, GLEX leads all four fixed banks on PubMed but not on Cora or CiteSeer, showing that graph family alone is insufficient. A reliable predictor would require a substantially larger collection of target graphs; GLEX instead makes the choice directly from unlabeled program executions. We have added the corresponding discussion to the revised appendix.