acceptodds
Under review as a conference paper at ICLR 2027

Training Probabilistic Graph Predictors without Graph Matching via Flow Matching

Abstract

Supervised graph prediction (SGP) maps any kind of input, such as images or molecular fingerprints, to graph outputs. The main challenge is that graphs do not have an intrinsic node ordering, making many different tensor representations valid and thus complicating coordinate-wise supervision. Existing SGP methods often handle this issue by matching predicted and target graphs. However, matching typically introduces a cubic-time alignment step and is hard to extend to settings with multiple valid, non-isomorphic outputs. We instead cast SGP as conditional generation over graph isomorphism classes and introduce pSGP (*probabilistic supervised graph predictor*), which instantiates this formulation using permutation-equivariant conditional flow matching. pSGP supports graph outputs with discrete and continuous graph features, and its training using standard coordinate-wise losses without graph matching scales quadratically. We prove that its empirical risk is invariant to the arbitrary indexing of each target graph. On six established SGP benchmarks, a single sample from pSGP outperforms the strongest baseline on graph-isomorphism accuracy, and modal decoding from multiple samples improves these results further. We also introduce a probabilistic graph prediction benchmark from genotype data with ambiguous targets, where pSGP achieves lower discrepancy from the target distribution over graph isomorphism classes. These results support conditional flow matching as a scalable, probabilistic approach to SGP.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
supervised graph prediction, structured prediction, flow matching, probabilistic prediction, graphs

Reviews

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

The paper proposes P SGP, which treats supervised graph prediction as conditional generation over attributed graph isomorphism classes. A permutation-equivariant flow model learns to reconstruct a clean graph from a corrupted graph while conditioning on an image, molecular fingerprint, or genotype sequence. Training uses coordinate-wise losses without aligning predicted and target graphs. At inference, the method generates one graph or selects the most frequent graph class among multiple samples using Weisfeiler–Lehman hashes.

Critical strengths
  1. The method combines permutation-equivariant conditional flow matching with coordinate-wise supervision, and Proposition 2 establishes that the expected training objective is invariant to arbitrary target reindexing. This provides a sound basis for predicting graphs with discrete or continuous attributes while avoiding the explicit alignment step required by matching-based approaches.
  2. A single generated candidate outperforms the strongest reported baseline on all six established benchmarks, with substantial gains on molecular reconstruction and USCities. Modal decoding improves performance further, and the appendix examines size prediction, clustering accuracy, and sampling budgets. These results support the practical usefulness of the approach across multiple input modalities and graph types.
Critical weaknesses
  1. The method closely builds on DiGress, DeFoG, and DIRECTO, but comparisons focus on matching-based predictors. Without a conditional diffusion baseline or a simpler DeFoG adaptation using comparable architectures and training budgets, it is difficult to determine which proposed design choices account for the gains. This limits the evidence for a distinct methodological advance despite the strong benchmark results.
  2. The genotype experiment compares only against a deterministic predictor, which necessarily incurs positive discrepancy when the reference distribution is multimodal. Furthermore, the constructed reference distributions are not the simulator’s full conditional posterior, and generic and designated non-identifiable examples can include the same family structures while receiving different reference distributions. These issues limit the interpretation of the reported MMD improvement as evidence of recovering conditional graph uncertainty; stronger probabilistic baselines and clarification of the statistical target are needed.
Questions for authors
  1. Do you have comparisons against a conditional graph diffusion model or a simpler DeFoG adaptation using comparable input encoders, graph backbones, and training budgets? These would help determine whether the gains depend on the proposed design choices.
  2. Appendix B.4 appears to allow the generic and non-identifiable branches to generate the same two-person, depth-four family structures, while assigning point-mass and uniform reference distributions, respectively. Is this interpretation correct? If so, how should the reference distribution be understood as a prediction target given only the observed genotype?
  3. How does P SGP compare with a probabilistic classifier over the benchmark’s finite family-template catalogue? Also, are the genotype MMD results stable when varying integration steps and replacing the terminal argmax with categorical sampling?
4 comments
AuthorsOpenReview ↗

Official Comment by Authors (1/2)

We thank the reviewer for the careful reading and recognizing the sound basis of Proposition 2, the gains on all six benchmarks from a single sample and further with modal decoding, and the usefulness across input modalities and graph types. We reply to the raised concerns next.

W1/Q1: Conditional diffusion and simpler DeFoG baselines. DiGress, DeFoG, and DIRECTO focus mainly on unconditional graph generation. Their conditional experiments use only graph-level labels or properties, such as a molecule's dipole moment in DiGress, the tertiary lymphoid structure content of a cell graph in DeFoG, or the execution time of a computational graph in DIRECTO. A simpler DeFoG adaptation therefore would condition only through the global graph features fed with a pooled embedding of the input. As new baselines, we trained this adaptation and a version of pSGP that replaces its flow with DiGress's diffusion process but keeps pSGP's full conditioning of the node and edge updates on the input tokens. Both use the same encoders, backbone size, frozen size predictors, training budgets, and argmax terminal step as pSGP. On validation inputs of Coloring 10 and of Genotypes:

GeneratorColoring 10 single GI-Acc (%)Coloring 10 modal@32 GI-Acc (%)Genotypes MMD², allGenotypes MMD², non-identifiable
pSGP95.298.60.2150.326
Simpler DeFoG adaptation (global only)60.170.80.2150.325
pSGP with DiGress diffusion88.897.90.2190.321

The table separates the two design choices, the conditioning and the generator. The conditioning matters most on Coloring 10, where the simpler DeFoG adaptation is far below pSGP, and on GDB13, where our conditioning ablations (see App. A.5 and our response to 4Qhd) show that conditioning only through the global features lowers single GI-Acc from 68.8% to 22.0%. These results also show that pSGP works well with diffusion too. With DiGress's diffusion process in place of DeFoG's flow matching, it reaches 88.8% single and 97.9% modal@32 GI-Acc on Coloring 10, far above the simpler DeFoG adaptation (60.1% and 70.8%) and within 0.7 points of flow matching in modal@32 GI-Acc. On Genotypes, all three models perform similarly. The gains therefore come mainly from conditioning the node and edge updates on the input tokens, with either generator. These results support the point we made in the conclusion (Sec. 4): our proposed probabilistic formulation of SGP is not limited to DeFoG and can be instantiated with other suitable generative processes, such as discrete diffusion. Our main contribution is the formulation of matching-free probabilistic SGP, rather than a new flow-matching algorithm. We still chose to use DeFoG as our main instantiation because it disentangles sampling from training, and its paper reports better results with fewer sampling steps than most diffusion models. We added these results to App. A.6.

While running these comparisons, we also found and fixed a bug in the code used for the probabilistic Genotypes evaluation of pSGP. Training, the trained model, and the evaluations of the other benchmarks are not affected. With the fix, pSGP's Genotypes test MMD² is 0.2146 overall (0.225 in the submission) and 0.3284 on the non-identifiable cases (0.388 in the submission), and the revised Table 2 reports these values. All Genotypes results in this response use the fixed evaluation.

W2/Q3: Catalogue classifier. We trained the requested classifier as a new baseline, which encodes the genotype tokens with the same encoder architecture as pSGP and maps the result through a linear layer to a probability for each of the 20 graph isomorphism classes found among the training targets (the benchmark's catalogue). It receives neither the true graph size nor whether the example is generic or non-identifiable. On the test examples, it performs similarly to pSGP:

PredictorMMD², allMMD², non-identifiable
Any2Graph0.38320.7742
pSGP0.21460.3284
Catalogue classifier0.21280.3311

The overall difference, classifier minus pSGP, is -0.0018, and its paired 95% CI (-0.0047 to 0.0008) includes zero. It is important to note that the classifier works well here because all test graphs come from a small finite catalogue, but it cannot predict structures outside it or continuously varying attributes, whereas pSGP generates nodes and edges directly. Any deterministic predictor, such as Any2Graph, places all probability on one structure and therefore scores at least 0.5 on each non-identifiable case, and at least 0.558 on average over the 1,524 non-identifiable test cases, compared with 0.3284 for pSGP. pSGP thus performs on par with a classifier that has the catalogue built in, and together with the diffusion version of pSGP and the simpler DeFoG adaptation above, this classifier provides the stronger probabilistic baselines that the reviewer asked for. We added this to App. A.7.

AuthorsOpenReview ↗

Official Comment by Authors (2/2)

W2/Q2: Generic and non-identifiable branches. Yes, this interpretation is correct, and for these structures both reference distributions favor the same prediction. In the test set, 51 of the 10,000 examples are generic examples with the same structure as a non-identifiable two-person example. In both branches, each example consists of genotypes and the one family graph used to simulate them, and the model is trained only on these pairs. Given only the genotypes, the prediction target is therefore the simulator's posterior, that is, the conditional distribution of the family graph given the genotypes, which the model can only learn from how often each family graph occurs with similar genotypes during training. As Sec. 3.3 states, this posterior is intractable to evaluate exactly, so neither reference distribution equals it. For a generic example, the benchmark compares the prediction with the family graph used to simulate its genotypes, the only graph that the example contains, so the reference distribution is a point mass on that graph. The generic branch is not restricted to structures that the genotypes can distinguish, which is why we call it generic rather than identifiable. A generic example can therefore leave the family graph uncertain, but without the posterior we do not know which other structures its genotypes leave possible or how likely each one is, and a single graph per example cannot show how a model spreads its probability. We introduced the non-identifiable branch to test this uncertainty in a controlled way. It chooses with equal probability among structures that the genotypes are known not to distinguish, so these structures are equally likely given the genotypes, and its reference distribution spreads probability equally over them.

A two-person family in which the two individuals descend from one shared ancestor through four edges in total has three such structures, in which the shared ancestor is 1, 2, or 3 generations above the first individual and 3, 2, or 1 generations above the second, so the uniform reference distribution gives each of them probability 1/3. When the generic branch produces one of these three structures, it also chooses each with equal probability, so the point mass of such a generic example falls on one of the three structures, chosen uniformly at random, and averaging this point mass over the random choice gives exactly the uniform reference distribution. Both reference distributions therefore favor the same prediction, probability 1/3 on each structure, which has the lowest MMD² against the uniform reference distribution and the lowest average MMD² against the point-mass one. The overlap thus does not change which prediction the reported MMD² rewards for these structures. The revised App. B.4 includes this explanation.

Q3: Integration steps and terminal sampling. Yes, the conclusions are stable. In new evaluations (App. A.7), we drew two independent sets of 16 samples from the paper's checkpoint per validation input and averaged their MMD², either taking the most probable category at the final step (argmax) or sampling it (categorical):

StepsMMD², all, argmaxMMD², all, categoricalMMD², non-identifiable, argmaxMMD², non-identifiable, categorical
1000.21990.22310.31780.3491
2500.21620.21340.33290.3100
5000.21690.21800.31180.3175
1,0000.21500.21700.31680.3025

At 250 steps, categorical minus argmax is -0.0027 overall (paired 95% CI -0.0105 to 0.0050) and -0.023 on the non-identifiable cases (-0.049 to 0.003), and both intervals include zero. On the non-identifiable cases every setting stays below 0.35, while any deterministic predictor scores at least 0.5 on each such case, so pSGP's advantage over deterministic prediction depends on neither the terminal step rule nor the number of steps.

Again, thank you for your valuable feedback. Given our response and clarifications to your questions and concerns, as well as the new results, we kindly ask you to consider increasing your score. We welcome further suggestions and are open to more questions.

I thank the authors for their efforts to address my concerns. My concerns were partially addressed. I would like to maintain my original scores.

Thank you for following up. Could you please clarify which of your concerns remain unresolved? We would like to address them if possible while the discussion period is still open.

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

This paper proposes propose PSGP (Probabilistic Supervised Graph Predictor), which reformulates supervised graph prediction as a conditional generative modeling problem over graph isomorphism classes and employs permutation-equivariant conditional flow matching. By combining a permutation-invariant source distribution with a permutation-equivariant graph Transformer, PSGP can be trained directly on arbitrarily indexed target graphs using standard coordinate-wise cross-entropy or squared-error losses, without requiring explicit graph matching. Theoretically, the authors prove that, under the assumptions that the conditional probability path and denoiser are permutation-equivariant and the endpoint loss is invariant to simultaneous reindexing, the expected training objective remains unchanged under arbitrary node reindexing of each target graph. For a dense graph implementation with fixed model width, depth, and number of conditioning tokens, the graph-side training complexity scales as O(n2)O(n^2).

Critical strengths
  1. The paper presents a conditional graph generation framework that avoids explicit node alignment during training. In contrast to matching-based SGP methods, PSGP directly optimizes coordinate-wise losses on arbitrarily indexed target graphs. This provides a simpler training formulation and avoids the additional computational cost associated with explicit matching.

  2. The paper provides a theoretical analysis showing that the expected training objective is invariant to arbitrary node reindexing under the stated permutation-equivariance assumptions. This result justifies the use of coordinate-wise losses without explicit graph matching. The analysis covers both categorical and continuous graph features.

  3. The proposed method is evaluated on six established SGP benchmarks and achieves higher graph-isomorphism accuracy than the previously reported baselines. The authors also investigate the effects of modal decoding, sampling budgets, and graph-size prediction in the appendix, providing additional information about the model's behavior.

Critical weaknesses
  1. PSGP largely builds upon existing permutation-equivariant graph generators, particularly DeFoG and DIRECTO. The invariance analysis also appears closely related to permutation-equivariance properties established in prior graph generative models. The authors should better clarify the specific methodological contributions beyond conditioning existing graph flow models on external inputs.
  2. The runtime comparison primarily isolates the loss computation rather than the complete training pipeline. Moreover, inference requires hundreds or thousands of flow steps, with additional computation for multiple candidates under modal decoding. End-to-end training time, inference latency, and memory comparisons would provide a more comprehensive assessment of the claimed computational advantages.
  3. The individual contributions of node-level cross-attention, global conditioning, and optional edge-level conditioning are not evaluated through dedicated ablation studies. Comparisons with simpler conditioning mechanisms would help clarify the effectiveness of the proposed architectural design.
  4. The Genotypes benchmark uses predefined reference distributions, which the authors acknowledge are not the full conditional posteriors induced by the genetic simulator. The relationship between these reference distributions and the underlying data-generating process could be further clarified. Moreover, comparing PSGP only against a deterministic predictor does not sufficiently establish its advantages over alternative probabilistic graph generation methods.
Questions for authors
  1. What are the key methodological differences between PSGP and a directly conditioned version of DeFoG? Would Proposition 2 also apply to such a baseline?
  2. Can the authors provide end-to-end computational comparisons with Any2Graph, including training time, inference latency, and memory usage, particularly considering the computational cost of multi-step flow sampling and modal decoding?
  3. What are the individual contributions of node-level cross-attention, global conditioning, and optional edge-level conditioning? Can the authors provide ablation results for these components?
  4. How do the predefined reference distributions in Genotypes relate to the structural ambiguity represented in the genetic simulation setting? Could the authors include a conditional probabilistic graph generation baseline, such as a conditioned variant of DeFoG, to provide a more direct comparison of distributional modeling performance?
3 comments

We thank the reviewer for supporting the paper and recognizing the training without explicit alignment, the invariance analysis, and the benchmark results. We reply to the concerns below.

W1/Q1: pSGP vs. a conditioned DeFoG. Yes, Proposition 2 applies to any conditional denoising model whose probability path and denoiser are permutation equivariant and whose loss is coordinate-wise, including an appropriately conditioned DeFoG. The proof uses the same equivariance argument as DeFoG's Lemma 3, but shows something new for SGP, namely that such a model needs no alignment with targets. Our contribution is therefore the supervised formulation (Sec. 2.1 and 2.3). When conditioned, DeFoG uses class labels with classifier-free guidance, whereas SGP maps each input to its own target graph, with no correspondence between input elements and output nodes given. Beyond Prop. 2, pSGP adds what this requires: a size predictor, conditioning of node and edge updates on input tokens, and a better point prediction by modal decoding (Prop. 1 and Sec. 2.4). Q3 shows that the conditioning matters. Unlike DeFoG, pSGP uses no structural encodings such as RRWP, which keeps each step quadratic in graph size (App. C.1).

W2/Q2: Computation. We now timed complete pipelines, not only the loss, training both pSGP and Any2Graph on Coloring 10 on the same GPU model up to their selected checkpoints. pSGP's time includes the size predictor training.

MethodTraining timeSingle GI-Acc (%)Modal@32 GI-Acc (%)
Any2Graph2.7 h82.2--
pSGP2.4 h95.298.6

pSGP trains faster and, on all 10,000 validation inputs, reaches higher GI-Acc, but uses more training memory (0.75 vs. 0.42 GB at batch 32). Still, all our pSGP training runs fit on one 24 GB A5500. For inference, we timed the complete pipeline, with multi-step sampling and modal decoding, on the 1,000 Coloring validation inputs of Fig. 5 (up to 50 nodes, one A100, batch 32), with pSGP using sampling hyperparameters suited to few steps (App. A.3):

MethodSSKKGI-Acc (%)ms per inputPeak memory (GB)
Any2Graph--127.90.200.06
pSGP8132.41.20.26
pSGP16149.92.40.26
pSGP643295.12590.40

Any2Graph is the fastest, but pSGP with 8 steps is already more accurate and becomes far more accurate with more computation.

W3/Q3: Conditioning ablations. In new ablations, each variant, including the full model, is trained from scratch with the paper's encoder, backbone size, frozen size predictor, and training budget, and evaluated on all 10,000 validation inputs per task. "Global only" conditions the graph only through a pooled input embedding fed to the global graph features, the route DeFoG and DIRECTO use for graph-level labels.

ConditioningColoring 10 single (%)Coloring 10 modal@32 (%)GDB13 single (%)GDB13 modal@32 (%)Genotypes MMD²
Full (pSGP)95.298.668.887.60.215
No edge-level94.898.467.887.80.214
No global94.798.368.487.50.214
No node cross-attention78.491.322.653.90.214
Global only60.170.822.055.00.215

Node cross-attention provides most of the gain on Coloring 10 and GDB13. Without it, edge-level conditioning still recovers much of the gap on Coloring 10, but not on GDB13. With it, removing edge-level or global conditioning keeps GI-Acc close to the full model, and the largest drop is from 68.8% to 67.8% in single GI-Acc on GDB13. On Genotypes all variants perform nearly the same (MMD² within 0.002). We added this to App. A.5.

W4/Q4: Genotypes. For generic families, the reference is a point mass on the simulated graph. For non-identifiable families, genotypes cannot distinguish certain structures, such as whether the shared ancestor of two individuals is 1, 2, or 3 generations above the first and 3, 2, or 1 above the second, and the reference gives them equal probability. Both references are benchmark targets rather than the intractable full posterior (Sec. 3.3). The closest model to the reviewer's conditioned DeFoG is Q3's "global only" variant, whose Genotypes MMD² matches pSGP's (0.215 vs. 0.215 overall, and 0.325 vs. 0.326 on the 1,488 non-identifiable validation cases), while any deterministic predictor scores at least 0.557 on those cases. On the non-identifiable cases, pSGP's advantage over Any2Graph therefore comes from predicting a distribution over graphs, which all five conditioning variants provide. Our reply to r6TF adds two more probabilistic baselines, a catalogue classifier and pSGP with DiGress diffusion, which score similarly to pSGP (App. A.6 and A.7).

Once again, we sincerely appreciate your valuable feedback and support for the paper. We would be very grateful if you would kindly consider increasing your score, and we welcome any further suggestions.

Thank you to the authors for their response. The clarifications have adequately addressed my concerns. I will therefore maintain my positive assessment of the paper.

Thank you for your reply. We are glad that our clarifications addressed your concerns and we appreciate your continued support of the paper.

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

The paper addresses supervised graph prediction from arbitrary input modalities, proposing a conditional graph flow-matching framework that avoids explicit graph matching during training and thus computational complexity reduces from cubic to quadratic.

I find the the reported improvements over existing supervised graph prediction methods substantial. However, my main concern is the limited methodological novelty relative to DeFoG (also mentioned in the introduction). As acknowledged in the manuscript, the model builds on DeFoG's permutation-equivariant graph transformer and conditional discrete flow-matching framework. The main methodological extension appears to be incorporating external input conditioning (however, also in this regard, the novelty is not clear for me compared to [1]). It remains unclear what fundamentally new contribution this provides beyond adapting an existing generative model to supervised graph prediction.

Regarding computational efficiency, the quadratic complexity analysis concerns training rather than the complete inference procedure. Since inference requires multiple flow steps and potentially multiple generated samples, an end-to-end computational comparison with existing methods would be valuable to substantiate the efficiency claims.

Overall, while the experimental results are promising, the paper would benefit from a stronger justification of its methodological novelty and more comprehensive computational comparisons.

[1] CVPR 2026, Can We Build Scene Graphs, Not Classify Them? FlowSG: Progressive Image-Conditioned Scene Graph Generation with Flow Matching. Xin Hu,Ke Qin,Wen Yin,Yuan-Fang Li,Ming Li,Tao He

Critical strengths

Formulating the problem in this way leads to substantial empirical improvements.

Critical weaknesses

Regarding novelty relative to prior work, FlowSG (CVPR 2026) already investigates image-conditioned graph generation using conditional flow matching. Although the task settings differ, the conceptual overlap appears substantial. I would appreciate a clearer discussion of the methodological differences and what the proposed approach contributes beyond this existing work. Furthermore, the time complexity comparison during inference is not clear. The wall time comparison of the methods end to end would be interesting.

Questions for authors
  1. Inference efficiency: Although Section 2.4 provides the theoretical inference complexity, an empirical end-to-end wall-clock runtime comparison with existing methods would be valuable. Figure 5 (Appendix A.3) shows that larger graphs remain challenging: for graphs with 41–50 nodes, even 1,000 sampling steps achieve only 54.1%. Could the authors report inference latency and compare the accuracy–runtime trade-off against existing methods?

  2. Methodological novelty: Could the authors clarify the key methodological differences and novel contributions relative to DeFoG and FlowSG (I mean excluding the down stream task differences)?

2 comments

We thank the reviewer and are glad they find the improvements substantial. We view the formulation that produces them as our main contribution, and clarify below how it differs methodologically from DeFoG and FlowSG.

W1/Q2: Novelty relative to DeFoG and FlowSG. Excluding the task itself, pSGP differs methodologically in four ways:

  1. it generates the whole graph of each input, with node cross-attention to condition tokens C(x)C(x) and a size predictor pψ(n∣x)p_\psi(n \mid x),
  2. it trains on arbitrarily indexed targets with coordinate-wise losses, without graph matching, a detector, or an assignment step,
  3. it returns one graph through the mode over graph isomorphism classes (Proposition 1), which the modal decoder approximates, and
  4. it uses none of the structural encodings of DeFoG and DIRECTO, such as RRWP or MagLap, which keeps each step quadratic in the number of nodes (App. C.1).

We do not claim graph flow matching, cross-attention, or permutation invariance as new components.

DeFoG generates graphs unconditionally or conditioned on graph-level labels (DeFoG, App. E). A label constrains properties of a plausible graph, whereas in SGP each input has its own target graph (or a distribution over a few target graphs) which is why prior general-purpose SGP methods align predictions with targets. Proposition 2 uses the same equivariance argument as DeFoG's Lemma 3, but its consequence for SGP is new. Because the expected loss is the same for every indexing of each target, this alignment is unnecessary in pSGP. As for the architecture, conditioning on the input as DeFoG conditions on labels, only through the global graph features, is not enough for good performance, since single GI-Acc on Coloring 10 drops from 95.2% to 60.1% in a new ablation (App. A.5).

We believe the overlap with FlowSG is smaller than it might appear, because the shared ingredients play different roles. FlowSG takes its nodes and their categories from a frozen Mask2Former detector (FlowSG, Eq. 7), itself trained with Hungarian matching (Cheng et al., CVPR 2022), instead of generating them. Its flow then generates relations, appearance codes, and boxes on these nodes (FlowSG, Eq. 12). Each FlowSG node is thus a detected image region, and its training target is defined per slot, which presupposes a correspondence between detections and ground-truth objects. Scene graph pipelines are commonly able to obtain such correspondence from box overlap (Zellers et al., CVPR 2018, Secs. 5.2 and 5.3), which requires spatially grounded nodes. Without that grounding, general-purpose SGP methods have needed graph matching. pSGP generates the node set itself and needs neither, because node ii of GtG_t is a noisy copy of node ii of the indexed target G1G_1, so it needs only an input encoder and applies to SGP tasks in general. The two also adopt flow matching for different reasons: FlowSG adopts it to replace one-shot classification with progressive refinement (FlowSG, Sec. 1), whereas pSGP adopts it to model a distribution over graph isomorphism classes, which needs no matching (Prop. 2) and gives a point prediction through the mode (Prop. 1). The revised related work in Sec. 1 adds this comparison.

W2/Q1: End-to-end inference time. The reviewer is right that the quadratic vs. cubic advantage concerns training. We also timed end-to-end training on Coloring 10, and pSGP trains faster than Any2Graph (2.4 h vs. 2.7 h). At inference, pSGP costs O(KSn2)\mathcal{O}(KSn^2) for KK parallel candidates of SS steps (Sec. 2.4). We measured wall-clock time end to end against Any2Graph, including size prediction, sampling, and modal selection. We use the 1,000 Coloring validation inputs of Fig. 5 (up to 50 nodes, one A100, batch 32), and pSGP uses sampling hyperparameters suited to few steps (App. A.3):

MethodSSKKGI-Acc (%)ms per input
Any2Graph--127.90.20
pSGP8132.41.2
pSGP16149.92.4
pSGP643295.1259

Any2Graph is the fastest, but pSGP with 8 steps is already more accurate, and the same trained model becomes far more accurate with more computation.

Q1: Graphs with 41–50 nodes. The 54.1% that the reviewer cites is the accuracy of one sample with S=1000S = 1000. With S=250S = 250 and 32 candidates, pSGP recovers 91.9% of these graphs (Fig. 5). In the timed setting above, pSGP with S=64S = 64 and K=32K = 32 recovers 79% of these 185 graphs and Any2Graph none.

Once again, we sincerely appreciate your valuable feedback. We hope that our responses, clarifications, and new results have addressed your questions and concerns. We respectfully ask you to consider increasing your score and welcome any further suggestions or questions.

We wanted to follow up and ask whether our response and additional experiments addressed your concerns about methodological novelty relative to DeFoG and FlowSG, as well as end-to-end inference time. If anything remains unresolved, we would be happy to clarify it while the discussion period is still open.

Comments on the paper

1 comment

We thank the reviewers for their constructive reviews. Reviewers found that "formulating the problem in this way leads to substantial empirical improvements" (NMXQ) and that "a single generated candidate outperforms the strongest reported baseline on all six established benchmarks" and "modal decoding improves performance further" (r6TF). They noted that Proposition 2 "provides a sound basis for predicting graphs with discrete or continuous attributes while avoiding the explicit alignment step required by matching-based approaches" (r6TF) and "justifies the use of coordinate-wise losses without explicit graph matching" (4Qhd), and that pSGP "provides a simpler training formulation and avoids the additional computational cost associated with explicit matching" (4Qhd).

Contribution and novelty. pSGP builds on graph flow matching and on the graph transformers of DeFoG and DIRECTO, which the paper credits (Sec. 1, Sec. 2.2, and App. C.1). As listed at the end of Sec. 1, our contributions are:

  1. the formulation of SGP as conditional generation over graph isomorphism classes,
  2. a proof that the expected training objective is invariant to reindexing each target, so that training needs no graph matching,
  3. a sample-based modal decoder for point prediction, and
  4. a probabilistic SGP benchmark with non-identifiable targets.

What differentiates pSGP from DeFoG, which all reviewers mention, is this supervised formulation and the input conditioning it requires. Like DiGress and DIRECTO, DeFoG focuses mostly on learning distributions over graphs unconditionally, and its conditional experiments use only graph-level labels or properties, while in SGP each input has its own target graph (or a distribution over a few target graphs), which is why prior SGP methods align predictions with targets. Proposition 2 shows that this alignment is unnecessary in pSGP, and new ablations on validation inputs show that conditioning only through the global graph features, the approach that DeFoG uses for labels, drops single GI-Acc from 95.2% to 60.1% on Coloring 10 and from 68.8% to 22.0% on GDB13. FlowSG, noted by NMXQ, generates relations on a node set fixed by a detector trained with Hungarian matching, depends on a correspondence between detections and ground-truth objects, and is motivated by replacing one-shot classification with progressive refinement, whereas pSGP generates the node set itself without any matching or correspondence and adopts flow matching to model a probability distribution over graph isomorphism classes. Neither DeFoG nor FlowSG proposes a modal decoder either, and previous general-purpose SGP methods did not tackle probabilistic SGP, in which an input can have several valid graphs.

New experiments. We ran the requested experiments and report each one in the corresponding reply. The experiments cover end-to-end training and inference time and memory measurements against Any2Graph (NMXQ, 4Qhd), conditioning ablations (4Qhd), a comparison with a simpler DeFoG adaptation and pSGP with DiGress diffusion as matched baselines (r6TF), a probabilistic classifier over the Genotypes family templates (r6TF), and Genotypes results across integration steps and terminal step sampling rules (r6TF). The revised paper adds these results to App. A, the comparison with FlowSG to Sec. 1, the differences from DeFoG, DiGress, and DIRECTO to Sec. 1 and 2.2, and a clarification of the Genotypes reference distribution to App. B.4. All changes are highlighted in blue.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.