acceptodds
Under review as a conference paper at ICLR 2027

Compile Locally, Query Globally: Learning Reusable Graph Programs

Abstract

When familiar graph components are connected in new ways, reusing local structural knowledge can support new predictions and avoid repeated computation. However, standard message-passing representations depend on current connections, while boundary-only summaries omit information needed to query internal nodes. We address these challenges by learning how information propagates within each component and reusing this computation across different assemblies. We introduce the Compositional Graph Compiler (CoGraC), an end-to-end framework that turns local structure into reusable numerical programs. Its queryable programs preserve both boundary interactions and recoverable internal responses, allowing them to be connected and jointly executed for prediction. Prediction gradients through this computation train the compiler to retain local computations that remain useful after composition. Once compiled, unchanged components can support new connections and queries without rerunning the encoder. Experiments show that CoGraC improves compositional link prediction and transfers across domains with a frozen compiler. With task-specific training, the same interface supports competitive node classification and improved graph classification, while program reuse reduces computation as real graphs change.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph representation learning, compositionality, graph programs, link prediction

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_K96uOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduce CoGraC, an end-to-end framework that turns local structure into reusable numerical program, and with the compiled program, it support new connections and queries without rerunning the encoder. Experiments show that CoGraC improves compositional link prediction and transfers across domains with a frozen compiler.

Critical strengths

The idea is interesting. CoGraC can turns the local structure into reusable module, which make learning on a updated graph much easier, and also CoGraC improves compositional link prediction and transfers across domains with a frozen compiler.

Critical weaknesses
  1. Generalization. The paper only report the result with custom encoder in Appendix A.1, and with GINE attribute frontend. The generalization to other SoTA graph model(MPNN and graph transformers) remains unclear.
  2. Efficiency. Section 2.1&2.2 raise a concern about the computational compleixty of CoGraC, and the authors lack a discusssion about this. According to Table 3&Table 18, it seems that GPR shows the comparable performance while much more efficient(~13x faster).
Questions for authors
  1. Can author further discuss the generalization to other SoTA graph models rather than the custom encoder in Appendix A.1? If the method can not be applied to other SoTA models, it will strictly limit the contribution of this paper.
  2. What is the computational compleixty of CoGraC compared with other methods?
3 comments

Response to Reviewer K96u

Thank you for your thoughtful feedback and for recognizing the potential of reusable graph programs. We have followed up on your questions with additional encoder experiments and a direct comparison of computational cost.

Weakness 1 / Question 1: Encoder generalization

Thank you for pointing out the need to test CoGraC with other encoders. We wanted to check whether CoGraC's gains depend on the custom encoder, so we repeated the experiment with a GCN and a component-local Transformer. Both have two layers and width 32. They encode ports and internal nodes through the same interface. We kept the operator heads, program representation, and executor unchanged.

Both encoders retain the benefit of composition. On New-node, Full improves over Local by 1.70 AP points with GCN and 2.01 points with Transformer. We then held the execution interface fixed to check how much composition training contributes. We froze each compiler and fitted fresh readouts under the same global interface and training protocol. Full training still improves over Local training by 0.71 ± 0.50 points for GCN and 1.02 ± 0.30 for Transformer. The gains remain positive in all five seeds. Here, ± denotes the sample SD of paired differences. This shows that both encoder families can support reusable programs and benefit from training through composition.

Weakness 2 / Question 2: Computational complexity and efficiency

Thank you for highlighting the need for a clearer cost analysis. CoGraC first compiles each component and then executes the programs together. This distinction matters because it can reuse the first step when only the connections change.

Let rjr_j and bjb_j count the internal nodes and ports in component jj. Beyond encoding, dense local elimination costs ∑jO(rj3+rj2bj+rjbj2)\sum_j O(r_j^3+r_j^2b_j+r_jb_j^2). Dense global factorization and solves cost O(P3+P2h)O(P^3+P^2h) for PP global ports and hh right-hand sides. New wiring requires another global computation, but unchanged components keep their compiled programs. Our Cora implementation uses full-coordinate sparse LU, so fill-in affects its cost. GPR remains faster in that setting.

To see whether reuse can offset these costs, we ran both methods on the same 96 rewiring requests under the same CPU/thread settings. CoGraC completed the workload in 0.564 s, compared with 0.744 s for GPR64. We included program preparation and wiring updates in these totals and timed model loading separately. CoGraC therefore reduces cumulative cost by 24.3% and runs faster in all five seeds.

The savings also come with better predictions. On the same requests, CoGraC improves Original/New-node AP over GPR64 by 5.50/6.13 points. Both the accuracy and speed advantages hold across all five seeds. Together, these results show the practical value of reuse when connections between components change.

Follow-up regarding manuscript revision

Thank you once again for your constructive feedback and time. We have revised our manuscript to address your suggestions and uploaded the updated PDF.

Specifically, we added experiments with GCN and component-local Transformer encoders in Section 3.4 and Appendix B.7. Both encoders retain the benefits of composition training while using the same program representation and executor. We also added a computational complexity analysis in Appendix A.3 to explain the costs of local compilation and global execution, and which computations reuse avoids. Section 3.4 and Appendix E.1 now include a direct comparison with GPR64 on the same rewiring workload. CoGraC achieves higher AP and lower total runtime on these requests, including preparation costs.

We hope these revisions and our earlier responses address your concerns. If you have any remaining questions or further suggestions, we would be glad to discuss them.

I thank the authors for the response. While the experimental results are strong, the paper’s presentation, particularly the experimental section, leaves me leaning toward weak rejection. Moreover, the strong performance of the proposed method with GCNs and Transformers makes the choice of a custom encoder in the original submission even more confusing. Overall, I find the idea interesting, but I believe the paper requires substantial revisions to its writing and organization, as well as a more comprehensive evaluation of CoGraC with SoTA architectures.

Reviewer_z9XXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes the Compositional Graph Compiler (CoGraC), which reuses local graph computations when components are reconnected or queried repeatedly.

A shared encoder maps each component to a positive-definite operator. For each component, the method stores the boundary interactions and the factors that recover responses at internal nodes, and it quantizes these factors with learned coefficient dictionaries. At prediction time, the component programs are assembled into a global linear system, and the responses of that system serve as prediction features. Training differentiates through this computation to learn the local operators and dictionaries.

Experiments cover link prediction on constructed compositional graphs, transfer of a frozen compiler to three real graphs, node classification, and peptide classification. The paper also measures the savings from reusing compiled components and cached responses under structural and attribute updates.

Critical strengths
  1. The reusable representation has a coherent mathematical foundation and supports internal queries. The paper correctly distinguishes preserving a component’s boundary behavior from recovering responses at its internal nodes. Because the representation retains the lifting and conditional internal factors, it can answer queries anywhere in the graph and still reuse unchanged local computations.

The positive-definite construction and the conditional perturbation bound state what execution preserves and how coefficient approximation affects responses. The method is therefore more interpretable than an unexplained cache of learned embeddings.

  1. The experimental controls are well chosen and support several of the narrower claims. The paper includes fixed-operator controls, matched local/global execution, fresh readouts on frozen compilers, internal-factor ablations, and comparisons between finite and continuous coding. On Peptides-func, the Full and Local models are matched in architecture, capacity, and training budget, and the paper reports a 2.25-point AP improvement.

The reuse experiments also verify agreement with recomputation and include preparation costs. Together, these controls provide credible evidence that global execution can improve prediction and that cached execution can preserve the model’s outputs.

Critical weaknesses
  1. The evidence for learning reusable compositional programs is weaker than the headline comparisons suggest. The most informative experiment is Appendix B.5, which holds the execution interface and readout protocol fixed. In this comparison, Full training improves over Local training by 0.329 ± 0.399 AP points on Original and 0.331 ± 0.408 points on New-node, and the gain is positive in four of five seeds. Adding global execution to locally trained programs produces substantially larger improvements.

The results therefore support the usefulness of global response features more strongly than the claim that training through composition learns substantially better reusable local computations.

The fixed-operator comparisons reinforce this concern. On controlled link prediction, CoGraC improves over Fixed Operator by approximately 1.25 and 0.96 AP points. In real-graph transfer, the gains are 0.46, 0.92, and 0.34 points on PubMed, USA, and email-Eu-core, respectively, and resource allocation outperforms CoGraC on email-Eu-core. These improvements are useful but modest, given that the comparison representations require no learned compiler.

The controlled benchmark raises a related question. Its labels are generated from similarity between endpoint-to-port distances, while CoGraC receives specially designed endpoint-to-bridge alignment features, and Table 8 shows that removing alignment substantially reduces performance. This is not label leakage, and the paper appropriately includes alignment controls. A simple predictor using the visible port-distance statistics would still help establish how much the benchmark rewards learned composition beyond the structural rule used to generate it.

The method does learn something. My concern is that the demonstrated benefit of its distinctive learning mechanism remains small relative to the complexity of the framework.

  1. Reuse reduces CoGraC’s own cost, but the experiments do not establish an attractive overall accuracy–cost trade-off. The reported speedups are valid comparisons against full recompilation. Appendix E shows, however, that avoiding some work in CoGraC does not necessarily make it competitive with a simpler predictor.

For Cora structural updates, selective recompilation takes approximately 136–281 ms, while GPR takes approximately 10.7 ms. CoGraC therefore remains roughly 13–26 times slower, with less than one percentage point higher validation accuracy in these experiments.

For repeated attribute updates on Photo, both methods receive the same opportunity to cache response columns. CoGraC’s preparation-plus-64-request cost is 5.975 seconds, compared with 0.352 seconds for GPR. CoGraC has slightly lower steady-state latency after caching, but its cumulative cost is approximately 17 times higher over the measured workload, without an accuracy advantage. The reported Photo training cost is also approximately 26 times higher.

These results do not invalidate reusable execution, but they leave the practical justification unresolved: when does the additional predictive value justify compilation, numerical solves, and cache preparation? A comparison against an incremental propagation method would also be relevant, since methods such as InstantGNN already aim to avoid repeated computation under graph and attribute changes.

Because reduced repeated computation is a central motivation, the paper needs to identify an operating regime in which its benefits outweigh these costs.

Questions for authors
  1. Learning versus execution: Full training improves by approximately 0.33 AP points at a matched global interface. Which results show most strongly that training through composition is necessary? Does its benefit grow under particular composition changes or query types?
  2. Controlled-task reference: How does a readout using the visible endpoint-to-port distances and their compatibility statistics perform under the same constructed-task protocol? This would help separate learning gains from the advantage of features closely aligned with the label-generation rule.
  3. Practical crossover: Under the measured workloads, how many requests does CoGraC need to become competitive with GPR in cumulative cost, and at what accuracy? Please include preparation, cache maintenance, and the corresponding inference interfaces.
  4. Finite-program value: Continuous coding has nearly the same predictive performance. What storage or execution benefit does finite coding provide over caching continuous factors, once coefficient indices, support masks, addresses, dictionaries, and decoded execution state are counted?
4 comments

Response to Reviewer z9XX — Part 1/2 (Questions 1–2)

Thank you for your careful review and constructive comments on the mathematical foundation and experimental controls. Your questions prompted the additional comparisons below. AP differences are percentage points.

Weakness 1 / Question 1: Learning versus execution

Thank you for highlighting the distinction between learning and execution. The transfer experiments test reuse across domains with a frozen compiler. To examine learning directly, we added a Fixed-global control on Peptides-func. Both models use the same GINE frontend, global execution, and readout. We also matched the frontend/readout initialization and training budget. Full achieves 55.96 AP, compared with 54.41 for Fixed-global. The paired gain of 1.54 ± 1.04 points remains positive in all five seeds. Learning therefore improves prediction on real functional labels even when the fixed-operator reference also executes globally.

We then examined how the training gain changes with assembly size. We first analyzed the submitted predictions and then repeated the experiment with GCN and Transformer encoders. In each case, we froze the Full-trained and Local-trained compilers and fitted fresh readouts under the same global interface and training protocol. The table reports the gains from Full training over Local training:

EncoderAll New-node settings16-component New-node setting
Original0.33 ± 0.411.03 ± 0.49
GCN0.71 ± 0.501.85 ± 0.62
Local Transformer1.02 ± 0.301.77 ± 1.14

Values are means ± sample SDs of five paired seeds. All three encoders show larger gains in the 16-component setting. Every gain in that setting is positive in all five seeds. This identifies a concrete case where composition training contributes more: new components form larger assemblies. Composition training also increases the benefit of global execution for both new encoders.

Weakness 1 / Question 2: Direct distance reference

We appreciate your suggestion to include a direct distance-based reference. We implemented a predictor that receives the visible endpoint-to-port hop statistics. We also gave it the compatibility term exp⁡(−6∣log⁡(1+du)−log⁡(1+dv)∣)\exp(-6|\log(1+d_u)-\log(1+d_v)|) used to generate labels. This lets us test whether global responses help beyond the explicit distance information. We computed all features from visible structure. We froze the compilers and trained fresh readouts on the original source data. Every condition used the same 48-input architecture and training budget. Distance + Public used zeros in place of global responses. The table reports mean AP over five seeds:

Readout inputOriginal AP (%)New-node AP (%)
Distance + Public70.3269.64
Fixed global responses + Distance + Public72.4671.19
Local-trained global responses + Distance + Public72.3670.98
Full-trained global responses + Distance + Public72.6271.26

Adding Full's responses improves over Distance + Public by 2.30/1.62 points. Both gains are positive in all five seeds. Global responses thus contribute useful information beyond the distance reference. The fixed and learned controls also show how much learning adds. We used matched fresh readouts for this comparison and retained the submitted model's original readout for the cost measurements in Part 2.

Response to Reviewer z9XX — Part 2/2 (Questions 3–4)

Continuing our response, we address Questions 3 and 4 below.

Weakness 2 / Question 3: Practical crossover

Thank you for highlighting the importance of cumulative cost. We extended the Photo stream to locate the crossover directly. We also tested repeated rewiring to examine another setting where CoGraC can reuse its programs. GPR remains faster on Cora. The cumulative timings below measure deployment after training.

On the same 96 rewiring requests, CoGraC completed the workload in 0.564 s, compared with 0.744 s for GPR64. We included program preparation and wiring updates in these totals and timed model loading separately. Alongside this 24.3% cost reduction, CoGraC improves Original/New-node AP by 5.50/6.13 points on the same timed requests. Both the accuracy and speed advantages hold across all five seeds. Reuse therefore improves both prediction and cumulative inference cost on this workload.

For Photo, we ran the repeated-set stream for 16,384 requests. The three runs reached crossover at 14,049, 14,460, and 16,312 requests. By the end of the stream, the mean total cost reached 34.201 s for CoGraC and 34.848 s for GPR. Their mean accuracies were 94.768% and 94.917%, respectively. To give both methods the same opportunity to reuse computation, we applied the same cache admission rule. We allowed each method to cache responses for at most 2% of the nodes. We timed both through the core-plus-softmax interface and counted preparation and cache maintenance in the totals.

Neither the 16,384-request switching-set stream nor the 1,024-request uniform stream reached crossover. The benefit on Photo therefore depends on persistent access locality. We have not conducted an InstantGNN comparison.

Question 4: Finite-program value

Thank you for pointing out that the storage comparison should include the full program representation. We added a packed serializer to measure what finite coding saves when we store and reload programs. We compared it with continuous FP32 factors and measured the inventory size, decoding cost, and decoded execution state. For the FP32 reference, we stored only one triangle of each symmetric factor.

The FP32-to-packed file-size ratios are 1.27, 2.90, and 5.56 for inventories of 16, 64, and 1,024 components. We counted coefficient indices, support and shape metadata, addresses, scales, dictionaries, and file headers. At 1,024 components, the packed format therefore saves 82.0% of storage across five seeds.

The serializer preserves all integer codes and metadata exactly. Across the five seeds, replay after floating-point reconstruction changes Original or New-node AP by at most 0.0133 points. These savings come from the new packed format. The original int64 container is larger than FP32.

Decoding restores the same operator storage, so it does not reduce the decoded memory footprint. Both formats also give comparable execution times for the same six-component assembly. Decoding the 1,024-component inventory takes about 112 ms with the packed format and 2 ms with FP32. The benefit is therefore compact storage of reusable programs with essentially unchanged predictions.

Follow-up regarding manuscript revision

Thank you once again for your constructive feedback and time. We have revised our manuscript to incorporate the additional experiments discussed in our responses and uploaded the updated PDF.

Specifically, Sections 3.2 and 3.4 now include the Peptides fixed-global control and the analysis of composition training across encoders and assembly sizes. Appendices D.2 and B.7 provide the details. Section 3.3 adds the explicit-distance comparison, with the full protocol in Appendix B.5. Section 3.4 also presents the accuracy–cost comparison under rewiring and the cumulative-cost crossover on Photo, supported by Appendices E.1–E.2. Finally, Section 3.3 and Appendix E.3 quantify the storage savings from packed programs and report decoding costs and prediction agreement after reloading.

We hope these revisions and our earlier responses address your concerns. If you have any remaining questions or further suggestions, we would be glad to discuss them.

Thank you for the clarifications and the additional experiments. Your response helped me better understand the scope of the paper’s claims, and I will maintain my original rating.

Reviewer_YLcTOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

CoGraC learns positive-definite local graph operators and stores quantized boundary, lifting, and conditional internal factors. These local programs are assembled and solved to answer queries under changing graph connections, while retaining enough information to recover internal-node responses. The compiler is trained through assembled prediction losses. Experiments cover constructed compositional link prediction, frozen-compiler transfer, supervised node and graph classification, and reuse under structural or attribute changes.

Critical strengths
  1. The proposed representation addresses a concrete limitation of boundary-only summaries: they cannot recover responses at internal nodes. Retaining lifting and conditional factors provides a coherent solution, with clear positive-definiteness and query-recovery arguments.

  2. The paper includes useful controls for its architectural claims. Factor interventions, fresh readouts on frozen compilers, disjoint component pools, and multiple seeds help separate the effects of internal information, execution, and training.

  3. The framework shows benefits beyond the constructed link-prediction task. Joint execution improves Peptides-func AP by 2.25 points over matched Local execution, and program reuse reduces recomputation while preserving predictions. The appendix also reports preparation costs and numerical agreement.

Critical weaknesses
  1. The constructed task is closely aligned with the model's features. Synthetic labels depend on port-distance compatibility, while the readout receives related alignment features that carry substantial predictive signal (Table 8). Results on additional target rules would clarify how much of the advantage extends beyond this design.

  2. The benefit of learning through global composition is less clear than the benefit of joint execution. Under a common interface, Full training adds only about 0.33 AP points, with paired seed SDs around 0.40 (Table 9). Transfer gains over Fixed Operator are also modest, at 0.34–0.92 points.

  3. The efficiency gains mainly concern CoGraC's own recomputation cost. On Cora, selective recompilation still takes approximately 136–281 ms versus about 11 ms for GPR (Table 18). These comparisons should be more visible in the main discussion, together with the workloads that justify the method's additional cost.

Questions for authors

See weaknesses.

3 comments

Response to Reviewer YLcT

Thank you for your constructive review and for recognizing the value of internal-query recovery and our experimental controls. We address the three concerns you raised below, which also cover your questions.

Weakness 1: Target design

Thank you for pointing out the close connection between the target rule and the input features. Since the labels depend on distance compatibility, we tested whether global responses still help when the readout has direct access to that information. We replaced the original alignment features with visible endpoint-to-port log-hop statistics and the compatibility term used to generate labels. We froze the compilers and compared fresh 48-input readouts under the same training protocol.

Distance + Public achieves 70.32/69.64 AP on Original/New-node. Adding Full's global responses raises the scores to 72.62/71.26, a gain of 2.30/1.62 points. Both gains are positive in every seed. Fixed-operator responses also help and reach 72.46/71.19. Global responses therefore contribute useful information even when the readout receives the explicit distance reference. The next experiment examines learning on real functional labels that do not follow this constructed target rule.

Weakness 2: Contribution of learning

Thank you for highlighting the importance of separating learning from joint execution. The transfer experiments test reuse across domains with a frozen compiler. To examine the contribution of learning more directly, we added a Fixed-global control on Peptides-func so that both models could use global execution. It uses the same GINE frontend and readout as Full. We also matched the frontend/readout initialization and training budget.

Full achieves 55.96 AP, compared with 54.41 for Fixed-global. Its paired gain is 1.54 ± 1.04 points and remains positive in all five seeds. This comparison shows that learning improves prediction on real functional labels even when the fixed reference also executes globally.

Your question also prompted us to examine where composition training helps most. In the existing 16-component New-node evaluation, Full training gains 1.03 ± 0.49 AP points over Local training under the same global readout protocol. We repeated this comparison with GCN and local Transformer encoders and obtained gains of 1.85 ± 0.62 and 1.77 ± 1.14 points. All three comparisons are positive in every seed. The larger assemblies thus reveal a clearer training benefit across encoder architectures. Values after ± are sample SDs of paired differences.

Weakness 3: Accuracy and computational cost

We appreciate your point that reuse should offer a favorable overall accuracy–cost trade-off. This led us to compare both methods on the same 96 requests that reconnect reusable components. CoGraC completed the workload in 0.564 s, compared with 0.744 s for GPR64. We included program preparation and wiring updates in these totals and timed model loading separately.

Alongside this 24.3% cost reduction, CoGraC improves Original/New-node AP by 5.50/6.13 points on the same timed requests. Both the accuracy and speed advantages hold across all five seeds. GPR remains faster on Cora. The new comparison shows that reconnecting reusable components can favor CoGraC in both prediction and cumulative inference cost.

Follow-up regarding manuscript revision

Thank you once again for your constructive feedback and time. We have revised our manuscript to address your suggestions and uploaded the updated PDF.

Specifically, Section 3.3 and Appendix B.5 now include the explicit-distance reference to examine what global responses contribute beyond the target-related features. We also added the Peptides fixed-global control in Section 3.2 and Appendix D.2 to examine operator learning on real functional labels. Section 3.4 and Appendix B.7 show how composition training benefits different encoders and larger assemblies. To make the accuracy–cost trade-off more visible, Section 3.4 and Appendix E.1 now compare CoGraC and GPR64 on the same rewiring requests. CoGraC achieves higher AP and lower total runtime on this workload, including preparation costs.

We hope these revisions and our earlier responses address your concerns. If you have any remaining questions or further suggestions, we would be glad to discuss them.

Thank you for the detailed response and additional experiments. The fixed-global control on Peptides-func provides clearer evidence for the contribution of operator learning. The matched-interface comparisons across encoders and larger assemblies, together with the reuse-cost comparison including preparation, also substantially address my original concerns. While the efficiency benefits remain workload-dependent, the revised evidence strengthens the case for acceptance. I am raising my rating from 3 to 4.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.