{"id":"ca45209f-3442-42e2-ab61-2d1186e68ea0","arxiv_id":"2502.01809","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A walk-based reinforcement sampler learns to extract important graph substructures for classification, matching or beating existing subgraph methods on seven benchmark datasets.","lead":"This paper introduces RWE-SGNN, a graph-learning model that trains a reinforcement-learning agent to walk through a graph and extract the substructures that matter most for classification. The approach offers a cheaper, sequence-based alternative to subgraph-sampling methods common in drug discovery and molecular-property prediction.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 only covers unbounded walks; under Definition 3's finite L, the walk MDP cannot generate all connected subgraphs the subgraph MDP can, so the central equivalence claim fails.","rationale":"The most load-bearing issue is the mismatch between Theorem 1 and Definition 3. The reader's weakest assumption identifies the same point, and I agree with that diagnosis. However, the concern is stronger than a mere empirical assumption: the star counterexample shows the equivalence claim is false as a mathematical statement, independent of any dataset. The theorem is correct for arbitrary-length walks, but the MDP used in the method caps length at L, and the bounded version cannot generate every connected subgraph that the subgraph MDP can. This invalidates the abstract's central claim and the complexity argument that motivates the walk-based approach. The empirical results may still indicate a useful heuristic, and the paper does provide a correct though elementary theorem, but the current formulation of the theoretical contribution is unsound. Given that the central claim is false as stated, I recommend rejection unless the authors explicitly weaken the claim to an approximate or length-conditional statement and add the missing condition. This is a technical critique of the argument, not a comment on author integrity.","tokens_in":18653,"tokens_out":10552,"duration_ms":104525,"concrete_test":"Construct the star graph S with center c and 9 leaves (10 nodes). Set the maximum trajectory length to L=16, as in Section 4.1. Run the subgraph-generation MDP from an empty start: it can select c and then each leaf in 10 steps, producing the full 10-node star. Run the walk-exploration MDP under Definition 3: the shortest walk covering all 10 nodes has 17 steps (leaf1-c-leaf2-c-...-c-leaf9), so with L=16 it must stop after at most 16 nodes and will omit at least one leaf. Compare the two generated substructures; the walk MDP's output is missing a node that the subgraph MDP includes, demonstrating that Definition 3's bounded state space is not equivalent to the subgraph MDP's generation capability. This settles that Theorem 1's unbounded-walk construction cannot justify the equivalence claim in Section 3.2.","verdict_should_be":"REJECT","load_bearing_attack":"Section 3.2 defines the walk-exploration MDP with states restricted to walks of length at most L (Definition 3), yet Theorem 1 is stated for the complete random walk set of arbitrary length. The theorem therefore does not support the equivalence claim that follows it. The gap is not merely technical: for a star with a center and k leaves, any walk visiting all k+1 nodes has length at least 2k-1 (start and end at leaves). With L=16, the walk MDP can cover at most 8 leaves, while the subgraph-generation MDP with the same trajectory limit of 16 can generate a 10-node star (center plus 9 leaves) in 10 steps. Thus there are connected subgraphs generatable by the subgraph MDP but not by the walk MDP, contradicting the claimed equivalence. The experimental setting L in {8,16} therefore rests on an unproven and in general false premise; at best the method is a heuristic that may work when relevant substructures have low walk-cover number. This directly undermines the abstract's claim of equivalent generation capability and the complexity argument that motivates replacing subgraph generation with walk exploration.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript proposes RWE-SGNN, a self-supervised subgraph neural network in which a reinforcement learning agent generates substructures as bounded-length walk sequences rather than by iterative subgraph expansion. The sampling model combines a shallow MPNN graphlet encoder with a DQN-based walk-exploration MDP, and a two-stage training loop alternates between fitting the output model on the downstream loss and updating the agent using that loss as a reward. The authors claim that walk exploration has generation capability equivalent to subgraph generation, that it reduces candidate-action complexity from quadratic to linear, and that experiments on seven graph benchmarks show top-2 accuracy and explainable substructures.","tokens_in":18801,"tokens_out":10024,"duration_ms":104225,"significance":"The proposed framework is timely, and the same-framework comparison between subgraph-based and walk-based MDPs, together with the ablation over trajectory length and sample number, is a useful empirical contribution. If the equivalence and complexity claims could be made precise, the method would offer a practical trade-off between expressiveness and efficiency. The proof of Theorem 1 is correct, and the empirical study includes a meaningful internal baseline, but the theoretical equivalence is currently overstated and is the main load-bearing weakness; the experimental results alone do not justify the formal claims in the abstract.","major_comments":[{"comment":"The equivalence claim is not supported by Theorem 1 because the theorem concerns the complete random walk set of arbitrary length, while Definition 3 restricts states to walks of length at most L. For a star subgraph with center and k leaves, any walk visiting all k+1 nodes has length at least 2k-1; with the reported L=16, the walk MDP cannot represent a 10-node star (k=9) even though the subgraph-generation MDP can produce it in 10 node additions. Therefore the claimed equivalent generation capability is false under the finite-L definition actually used, and this directly affects the L in {8,16} settings of Section 4.1.","section":"Section 3.2, Definition 3 and Theorem 1"},{"comment":"Even for unbounded walks, the theorem only shows that some walk visits every vertex; it does not show that the walk MDP can generate every connected subgraph as a state, that the edge set of the subgraph is represented, or that optimal policies under the two reward definitions coincide. A walk visiting the three vertices of a triangle can miss one of the triangle's edges unless it is lengthened, so the object encoded by the sequence encoder E_w is not automatically the same object generated by the subgraph MDP. The sentence after Theorem 1 that walk exploration has equivalent subgraph generation capability therefore overstates what has been proved.","section":"Section 3.2, Theorem 1 and the following paragraph"},{"comment":"The claimed reduction from O(N^2 D) to O(L D) treats L as an independent constant, but to cover a connected substructure of N nodes the walk length L must scale with N (for a star with N=k+1 nodes the minimum visiting walk has length 2k-1). The experiments fix L in {8,16} without evidence that all informative substructures fit within that bound, and no wall-clock or memory measurements are reported, so the practical efficiency advantage is not fully demonstrated.","section":"Section 3.5, complexity comparison"}],"minor_comments":[{"comment":"The output-model parameter update minimizes lQ instead of lO; this appears to be a typographical error in the pseudo-code.","section":"Algorithm 1, line 29"},{"comment":"The inference procedure computes the Q-learning loss lQ although it is unused, and line 11 uses Z' without computing it in that algorithm; the pseudo-code should compute the output-model embeddings and remove the Q-loss computation.","section":"Algorithm 2"},{"comment":"The text says that Figure 6 shows the test accuracy curves of different hyperparameters, but the accuracy curves appear in Figure 4 while Figure 6 is the BA-2motifs visualization; the cross-reference should be corrected.","section":"Section 4.2, ablation paragraph"},{"comment":"There are several typographical and formatting errors, including Defintion, trajctory, architechture, enchance, and the inconsistent spacing R WE-SGNN; a careful proofread is needed.","section":"Throughout"},{"comment":"The caption states that top-2 results are marked in bold, but the bolding rule is applied unevenly (e.g., SUGAR NoMI has no reported standard deviation), and the criterion should be stated precisely.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The central equivalence claim is not salvageable in its current form, but the framework and empirical comparison may merit publication after a substantial revision. The authors should replace the equivalence claim with a precise statement about unbounded walks, explicitly treat finite L as a heuristic parameter, and add experiments or analysis showing that the chosen L covers informative substructures on each dataset. The SubgraphMDP baseline and the trajectory-length ablation are valuable strengths of the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a solid incremental paper with a real technical idea and one overclaimed result. The walk-exploration MDP is genuinely new: actions are neighbors of the current walk endpoint rather than the whole border of a growing subgraph, and that simplifies both the action space and the state encoding. You get a padded walk sequence instead of a subgraph, no isomorphism handling, and a smaller candidate set per step. The two-stage self-supervised loop, where the output model's downstream loss rewards the sampling model, is a sensible way to fuse SGNNs with explainer-style RL sampling. The reported accuracy is competitive on seven benchmarks, and the MUTAG and BA-2motifs visualizations look believable.\n\nThe main soft spot is Theorem 1. It is true but close to a tautology: a connected subgraph admits a walk visiting all its vertices, provided walks can be arbitrarily long. The MDP in Definition 3 is finite-horizon: states are walks of length at most L. With L=16, a star with a center and nine leaves can be generated by the subgraph MDP in ten steps, but no walk of length at most 16 visits all ten vertices. So the abstract's claim of equivalent generation capability is false for the actual algorithm. The theorem needs a bound on walk length in terms of the target subgraph and the number of backtracking steps required.\n\nThe complexity comparison is also under-supported. The O(LD) versus O(N^2D) argument treats L and N as comparable, but equivalence can require L much larger than N when substructures are star-like. The paper mentions this trade-off only informally, and no runtime or memory measurements are reported. Baseline numbers are taken from other papers, and the best-validation-accuracy protocol is known to be optimistic; without code or a unified re-run, the performance edge should be read cautiously.\n\nWho this is for: people building subgraph-based GNNs or RL explainers will get a useful MDP design and a reminder that walk-based coverage of subgraphs is more delicate than it looks. Once the equivalence claim is fixed or softened, this is a credible heuristic method. It deserves a serious referee: the core idea is worth engaging even though the central theorem needs rewriting. My recommendation is to send it to peer review and have reviewers push on the bounded-L question and ask for either code or runtime measurements.","headline":"A genuine technical idea—walk-endpoint action space for subgraph sampling—sits under an overclaimed equivalence theorem that only holds for unbounded walks, not the finite L used in practice.","tokens_in":19405,"tokens_out":3500,"would_cite":true,"duration_ms":36948,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A walk-based Markov decision process can generate the same connected substructures as subgraph expansion while cutting candidate cost from quadratic to linear.","keywords":["subgraph neural networks","graph neural networks","reinforcement learning","walk exploration","self-supervised learning","graph classification","explainability","deep Q-networks"],"falsifier":"Construct a graph whose classification label is determined by a star-shaped substructure with $n$ leaves, set the walk length $L$ to a value smaller than $n+1$, and check whether the extracted walk can visit all leaves. If the walk cannot cover the full star while the subgraph-based MDP can, the claimed equivalence between walk exploration and subgraph generation does not hold under the bounded-length setting actually used.","tokens_in":18368,"feed_emoji":"🧭","tokens_out":4877,"duration_ms":42267,"temperature":0.7,"pith_summary":"This paper proposes a self-supervised framework, RWE-SGNN, that trains a subgraph neural network by having a reinforcement-learning agent walk through the input graph rather than expand subgraphs step by step. The central claim is that a walk-based Markov decision process has equivalent generation capability to the traditional subgraph-generation process, so the agent can extract the same important substructures while evaluating far fewer candidates. If the claim holds, graph classifiers gain a data-driven sampling policy that is both cheaper than algorithm-based subgraph sampling and inherently interpretable: the learned walks mark the substructures that drive predictions. Experiments on seven graph classification benchmarks report top-2 accuracy everywhere and top-1 on four, with extracted walks localizing known chemical groups such as NO2 in MUTAG and circle and house motifs in BA-2motifs.","feed_headline":"A walk can cover any connected subgraph, so GNN sampling gets cheaper","feed_subtitle":"RL-guided walks match subgraph generation with linear cost and top-2 accuracy on seven benchmarks.","key_machinery":"The load-bearing object is the walk-exploration-based MDP (Definition 3), whose state space is random walks of length at most $L$ on the input graph, whose actions are neighbors of the current endpoint, and whose transition appends a node to the walk. It is paired with Theorem 1, which proves that every connected subgraph has a walk that visits all of its nodes, giving the walk process the same generation capability as the subgraph-based MDP (Definition 2) while reducing the feasible action space from $\\bigcup_{v \\in V_s} N(v) \\setminus V_s$ to $N(v_l^s)$. A deep Q-network trained with the downstream loss as reward implements the walk policy, and a shallow MPNN provides node-level graphlet-aware embeddings that guide the agent.","core_discovery":"RWE-SGNN replaces the breadth-first subgraph-generation MDP of earlier subgraph neural networks with a depth-first walk-exploration MDP. States are walk sequences of bounded length, actions are neighbors of the current endpoint, and the reward is the reduction in downstream loss obtained by extending the walk. Theorem 1 shows that for any connected subgraph there exists a walk visiting all its nodes, so walk exploration can, in principle, generate the same connected subgraphs as the traditional node-by-node expansion. The candidate count per step drops from the union of border neighborhoods to a single node neighborhood, changing the generation complexity from quadratic to linear in the structure size. The sampling model first uses a shallow MPNN to compute graphlet-aware embeddings, then a deep Q-network chooses walk steps, and a two-stage training loop alternates between optimizing the output model on downstream loss and using that loss as the reward signal for the agent. On the seven datasets, the walk-based MDP outperforms the subgraph-based MDP on six, and the extracted walks match known domain motifs in the visualization experiments.","pith_inferences":["The equivalence theorem says nothing about embedding fidelity: a walk that visits all nodes of a subgraph does not necessarily preserve the subgraph's edge structure in the sequence encoder, so tasks where edge topology matters may need a walk-to-subgraph reconstruction step.","The backtracking difficulty for star graphs suggests a natural extension: an adaptive or learned stopping criterion for walk length per graph, instead of a global $L$.","The reward difference $l(O(s)) - l(O(s'))$ rewards local improvements; a credit-assignment variant that rewards whole-trajectory outcomes could make the agent more stable on larger graphs.","The walk framework could transfer to link prediction or graph generation, where sequential construction of substructures is a core operation and the linear action space would be a direct benefit."],"forward_implications":["Walk-based sampling can replace subgraph generation in SGNNs, lowering the candidate evaluation cost from $O(N^2 D)$ to $O(L D)$ without losing access to the same connected substructures.","The same framework yields explanations: the learned walk sequences identify the substructures that determine predictions, as shown by the NO2 and motif visualizations.","The two-stage training loop lets the downstream loss act as the reward, so the sampling policy adapts to the task instead of relying on a fixed algorithm-based policy.","Because the method is self-supervised and task-driven, it can be ported to other downstream objectives by swapping the loss function in the reward definition.","Performance on seven benchmarks suggests the approach transfers across molecule and social-network domains, reaching top-2 accuracy on all and top-1 on four."],"supporting_citations":[{"why":"Supplies the deep Q-network algorithm that trains the walk agent.","marker":"[15]"},{"why":"Provides the reinforcement-learning explainer paradigm that the sampling model is trained in.","marker":"[19]"},{"why":"GIN is used as the shallow MPNN backbone for graphlet-aware embeddings and the output encoder.","marker":"[30]"},{"why":"Defines the important-subgraph explanation criterion that motivates the sampling-as-explainer design.","marker":"[32]"},{"why":"Contributes the subgraph-exploration sequential generation approach the walk MDP compares against.","marker":"[33]"},{"why":"SUGAR provides the reinforcement-pooling subgraph GNN baseline and the no-MI comparison row.","marker":"[21]"},{"why":"GraphSNN supplies a strong subgraph-based baseline and reports the per-dataset accuracies used in the comparison table.","marker":"[29]"},{"why":"MUTAG is the chemistry dataset used both for classification and for the NO2 substructure visualization.","marker":"[5]"}],"fun_headline_variants":["Walk-based GNN sampling beats subgraph generation on 7 datasets","Depth-first walks make subgraph GNNs faster and smarter","One walk can replace subgraph generation for GNN embeddings","RWE-SGNN uses walk exploration to cut GNN sampling cost","From subgraphs to walks: a cheaper GNN sampling strategy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method works only if a fixed maximum walk length $L$ (set to 8 or 16 in the experiments) is long enough for a walk to cover every important substructure, which fails for star-shaped substructures where backtracking requires more steps than the number of nodes.","fun_headline_variants_meta":{"raw":{"variants":["Walk-based GNN sampling beats subgraph generation on 7 datasets","Depth-first walks make subgraph GNNs faster and smarter","One walk can replace subgraph generation for GNN embeddings","RWE-SGNN uses walk exploration to cut GNN sampling cost","From subgraphs to walks: a cheaper GNN sampling strategy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000441,"raw_usage":{"total_tokens":2283,"prompt_tokens":1039,"completion_tokens":1244,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":655,"completion_tokens_details":{"reasoning_tokens":1156}},"tokens_in":655,"tokens_out":1244,"duration_ms":9296,"temperature":1.0,"reasoning_tokens":1156,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T14:22:09.524678+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a graph whose classification label is determined by a star-shaped substructure with $n$ leaves, set the walk length $L$ to a value smaller than $n+1$, and check whether the extracted walk can visit all leaves. If the walk cannot cover the full star while the subgraph-based MDP can, the claimed equivalence between walk exploration and subgraph generation does not hold under the bounded-length setting actually used.","supporting_citations":[{"cited_title":"Reinforcement learning enhanced explainer for graph neural networks","cited_arxiv_id":null,"evidence_quote":"Provides the reinforcement-learning explainer paradigm that the sampling model is trained in."},{"cited_title":"On explainability of graph neural networks via subgraph explorations","cited_arxiv_id":null,"evidence_quote":"Contributes the subgraph-exploration sequential generation approach the walk MDP compares against."},{"cited_title":"Sugar: Subgraph neural network with reinforcement pooling and self-supervised mutual information mechanism","cited_arxiv_id":null,"evidence_quote":"SUGAR provides the reinforcement-pooling subgraph GNN baseline and the no-MI comparison row."},{"cited_title":"A new perspective on” how graph neural networks go beyond weisfeiler-lehman?”","cited_arxiv_id":null,"evidence_quote":"GraphSNN supplies a strong subgraph-based baseline and reports the per-dataset accuracies used in the comparison table."},{"cited_title":"Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds","cited_arxiv_id":null,"evidence_quote":"MUTAG is the chemistry dataset used both for classification and for the NO2 substructure visualization."}],"review_version":1}