{"id":"30a2f56f-6cfb-4d1b-8c95-a3fbaafe1d00","arxiv_id":"2504.16360","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"GOMKCN uses a differentiable graph optimal matching kernel between node-centric subgraphs and trainable filters to produce disentangled representations, improving accuracy and interpretability on several graph classification benchmarks.","lead":"A new graph neural network, GOMKCN, compares local subgraphs against trainable filters with an optimal matching kernel to produce structured node representations. The paper claims this improves accuracy and interpretability on graph and node classification while making graph pattern matching differentiable.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Greedy subtree matching in Algorithm 1 is order-dependent and asymmetric, so the implemented GOMK is not established as a kernel; Section IV-C's assertion and Eq. 19's self-similarity constant both rest on this gap.","rationale":"The reader's weakest_assumption is the load-bearing one, and I agree with it. The paper's central claim is that GOMK is a kernel-based convolutional operator that reconciles differentiability and accuracy. That claim requires the implemented similarity to be a symmetric PSD function, since Eqs. 19-21 and the Hilbert-space framing depend on it. Algorithm 1 replaces the maximum in Eq. 16 with a greedy sequential matching, which is not invariant under swapping arguments or under source enumeration; Proposition 5 only covers a fixed matching and does not lift to a single global kernel. Thus the theoretical foundation of the claimed contribution is not secured. I do not recommend rejection: the synthetic experiments on isomorphic graph learning and frequent pattern mining are concrete, falsifiable demonstrations that the learned filters can recover planted structures, and the accuracy comparisons show selective improvements over baselines. Those results are compatible with GOMK acting as a differentiable similarity layer even if it is not a valid kernel. The reader's CONDITIONAL verdict is the right one; the condition should explicitly require either a proof of symmetry/PSD for the greedy variant or a switch to a symmetrized/exact matching, plus release of code to run the Gram-matrix check. Since my assessment matches the reader's, verdict_should_be is UNCHANGED.","tokens_in":20838,"tokens_out":12349,"duration_ms":135791,"concrete_test":"Implement Algorithm 1 exactly as specified, with t-SE embeddings (Eqs. 7-9) and the RBF solid function (Eq. 10), on small random graphs (e.g., 6 nodes, features in [0,1]). (1) For each ordered pair (G,H), compute kappa(G,H) and kappa(H,G) with source/target roles swapped under the same node-index order; report how often they differ. (2) Build the full Gram matrix over 20 random subgraphs and filters and check symmetry and the smallest eigenvalue; if any asymmetric entry or negative eigenvalue appears, the greedy function is not a kernel. (3) Compute kappa(G,G) under two different node orderings; if the value changes, Eq. 19 fails. This directly tests the unproven assertion in Section IV-C.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section IV-C defines GOMK by Eq. 16 as a maximum over all matchings, but Algorithm 1 (lines 20-25) computes a greedy matching: for each source subtree in the current enumeration, it picks the highest-similarity unmatched target subtree. The greedy result depends on the source enumeration and on which side is the source. Consequently, the implemented function is not guaranteed to be symmetric: kappa(X,Y) and kappa(Y,X) may differ, and the Gram matrix need not be symmetric. Proposition 5 proves only that a fixed matching scheme gives a PSD element kernel; it does not show that the greedy matching yields a single symmetric PSD kernel across all pairs of subgraphs and filters. Section IV-C's claim that greediness 'does not compromise the effectiveness of OMK to serve as a kernel function' is an assertion, not a proof. Section V-B's spherical-space argument uses Eq. 19, kappa(G,G)=n(t+1); under greedy matching with ties, a node can be matched to an equally similar non-self subtree, so even self-similarity is not guaranteed. The model may still work as a differentiable similarity layer, but the Hilbert-space interpretation and the kernel-based theoretical claims are unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GOMKCN, a graph convolutional network in which each node's representation is the vector of similarities between its k-hop subgraph and T learnable graph filters. The similarity is computed by decomposing subgraphs and filters into t-level subtree embeddings (t-SE) and then aligning those embeddings through a proposed Graph Optimal Matching Kernel (GOMK). The filters are trained end-to-end, and the resulting per-filter similarities are presented as disentangled structural factors. The authors claim a Hilbert-space interpretation of GOMK, a spherical feature-space property, an injectivity guarantee for t-SE, and improved interpretability and accuracy. Experiments cover isomorphic graph learning, frequent subgraph pattern mining, interpretability visualization, node classification on six datasets, and graph classification on six datasets.","tokens_in":2014,"tokens_out":2504,"duration_ms":195024,"significance":"If the theoretical claims held, the paper would make a useful contribution: an interpretable GNN with learnable structural filters and a differentiable graph-kernel-based convolution. The synthetic pattern-mining experiments are a concrete strength: the recovered filters in Figs. 8 and 9 provide visible evidence of interpretability, and the hyperparameter and runtime analyses are useful. The method also performs competitively, with the largest gains on ENZYMES, Chameleon, and Squirrel. However, the theoretical core is not established as written: the implemented greedy matching is not shown to define a kernel, and the proofs of element-kernel validity and t-SE injectivity have gaps. At this stage the paper is better described as an empirically motivated similarity-layer architecture than as a validated kernel-theoretic framework.","major_comments":[{"comment":"The kernel-valued claim is not established for the implemented function. Eq. (16) defines GOMK as an exact maximum over all matchings, but Algorithm 1 computes a greedy matching: each source subtree sequentially selects the most similar unmatched target subtree. This greedy outcome depends on the order in which source subtrees are enumerated and on which side is the source. For example, with X={x1,x2}, Y={y1,y2} and s(x1,y1)=1.0, s(x1,y2)=0.9, s(x2,y1)=0.9, s(x2,y2)=0.0 (self-similarities all 1.0), greedy from X in order x1,x2 gives total 1.0, while greedy from Y in order y2,y1 gives total 1.8. Hence the implemented kappa is not symmetric and a Gram matrix built from it need not be positive semidefinite. Proposition 5 proves validity only for a fixed matching scheme; the sentence in Section IV-C that greediness does not compromise the effectiveness of OMK to serve as a kernel function is an assertion, not a proof. The Hilbert-space interpretation (Eq. 2) and the spherical-feature-space interpretation (Eq. 21) are therefore unsupported for the model actually trained. The authors should either prove symmetry and PSD for the greedy implementation (or symmetrize it), or explicitly present GOMK as a non-kernel differentiable similarity layer and move the kernel-based theoretical claims to the exact-matching setting.","section":"Section IV-C, Eq. (16), Algorithm 1 (lines 20-25)"},{"comment":"The injectivity proof has a gap. The theorem requires the stacked embeddings hat F for G_u and G_v to be equal and full-rank, but the proof then needs each block c_i = A_G^i F to have full row rank in order to solve A_G c_i = A_H c_i uniquely for the adjacency matrix. Full rank of the stacked matrix does not imply full row rank of the individual blocks c_i; when d < n, no c_i can have rank n at all. In particular, Section VI-A reports successful recovery for featureless graphs with all node features initialized to 1.0, where F has rank 1 even though n=6. The proposition's condition is therefore not met in the experimental setting used to claim injectivity. The authors should either prove the statement under a weaker rank condition (e.g., full row rank of F), or substantially soften the expressiveness claim.","section":"Section V-A, Proposition 6"},{"comment":"Padding subgraphs with isolated zero-feature nodes is not a similarity-neutral operation. Each padded zero node contributes t+1 to the self-similarity in Eq. (19), and because RBF similarities of a zero vector to any nonzero embedding are positive (exp(-||f||^2/(d tau)) > 0), zero nodes also participate nontrivially in the greedy matching against non-isolated subtrees. The asserted bijection between the original and adjusted subgraph only preserves uniqueness of the subgraph representation; it does not preserve GOMK values. Consequently, the constant-radius sphere claim and Eq. (21)'s cosine interpretation do not follow for subgraphs of different original sizes unless the padding effect is included in the norm and the matching is made symmetric. This matters for the frequent-pattern-mining objective Eq. (23), which relies on the spherical/cosine interpretation.","section":"Section V-B, Eqs. (19)-(21)"},{"comment":"Even for the exact-matching version, the proof that OMK is a kernel is incomplete. In Proposition 5 the element kernel k_e is defined only for the union of a particular pair, and the feature map psi in Eq. (13) is built from the hierarchical tree T obtained from the matching between X and Y. Therefore the set embeddings Delta_X and Delta_Y in Eq. (14) are functions of the pair (X,Y), not representations of X and Y independently. Applying the histogram intersection kernel to these pair-dependent histograms does not define a fixed positive-definite kernel on the space of all finite subsets, because there is no single feature map on each set that yields Eq. (15). To substantiate the Hilbert-space claim, the authors need a global feature map over all possible elements and a pair-independent representation of sets, or they should cite and apply the known theory of valid optimal assignment kernels with a strong base kernel.","section":"Section IV-C, Propositions 5 and Eqs. (13)-(15)"}],"minor_comments":[{"comment":"There is a typo in the statement: it says G_kv and G_kv are isomorphic; the second occurrence should presumably be G_ku.","section":"Section V-A, Proposition 6 statement"},{"comment":"The results paragraph refers to Table II for the graph-classification results; it should refer to Table III.","section":"Section VI-E, Results"},{"comment":"The notation 'Vhat | = vhat' is not standard; it should be written as set union, for example 'Vhat <- Vhat union {vhat}'.","section":"Algorithm 1, line 24"},{"comment":"The hard argmax in Algorithm 1 is piecewise constant, so the claim of differentiability should be qualified as a subgradient statement or supported by a continuous relaxation; otherwise the phrase 'resolving the contradiction between differentiability and accuracy' overstates the property of the implemented GOMK.","section":"Section IV-C, differentiability claim"},{"comment":"The notation 1/(d tau) is unexplained: the reader cannot tell whether d is the node-feature dimension and whether the scaling is intentional; please clarify.","section":"Eq. (10)"},{"comment":"The phrase 'significantly higher' in Section VI-D is not backed by a statistical significance test; the standard deviations overlap for several datasets, so please either add significance tests or soften the wording.","section":"Table II and Table III"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The empirical pattern-mining demonstrations are the strongest part of the manuscript, but the advertised kernel-theoretic foundation is not yet supported. The gap between the exact optimal matching in Eq. (16) and the greedy implementation in Algorithm 1 is the central issue; it is fixable either by proving a symmetric PSD construction or by honestly repositioning GOMK as a similarity layer. I also recommend asking the authors to provide code and reproducibility details, since the current submission does not include them."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First read: this is a real variant, not a revolution. The authors combine RBF-based subtree embeddings with a greedy optimal matching scheme inside a learnable graph filter convolution, building directly on KerGNN and RWK+CN. The synthetic pattern-mining experiments are genuinely nice: the learned filters converge to the planted motifs, and the interpretability visualizations are convincing. On several real datasets, especially ENZYMES, the accuracy gains over the immediate baselines are substantial.\n\nThe soft spots are real but not disqualifying. The main one is the kernel claim. Proposition 5 proves that for a fixed matching, the element kernel is PSD, but Algorithm 1 replaces the exact maximum with a greedy, order-dependent, asymmetric procedure. Section IV-C asserts this 'does not compromise' kernel validity, and that is not proven; the implemented kappa may not be symmetric, so the Gram matrix need not be PSD. This matters because the Hilbert-space story, Eq. 19, and the cosine-similarity interpretation all rest on kernel validity. The model would likely still work as a differentiable similarity layer, but the theoretical contribution as stated is unsupported. Fixing this is not hard: either symmetrize the greedy (e.g., average both directions), use exact optimal assignment via the Hungarian algorithm for small filters, or drop the kernel language and present the operation as an alignment-based similarity. The authors should do one of those.\n\nSecond, the disentanglement claim is not actually compared against any disentanglement baselines (DisenGCN, IPGDN, FactorGCN, etc.). The comparison is against standard GNNs and the kernel-based KerGNN/RWK+CN. That is fine for predictive accuracy, but 'disentangled' is doing a lot of work without evidence of factor independence or structural separation beyond the synthetic motif experiments.\n\nThird, no code is released, and the Proposition 6 injectivity proof is sketchy: the rank argument does not obviously deliver the claimed uniqueness. This is a minor concern but worth tightening.\n\nOverall: the paper is a plausible, moderately novel method with good empirical illustrations and a fixable theoretical gap. It deserves serious peer review, not desk rejection. If I were the editor, I would send it out with a request for code and a revised treatment of the matching kernel.","headline":"A useful, moderately novel learnable graph kernel with a fixable theoretical gap: the greedy matching is not proven to yield a valid kernel, and the disentanglement claims outrun the experiments.","tokens_in":21657,"tokens_out":4027,"would_cite":false,"duration_ms":40683,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that aligning subtrees by optimal matching makes graph kernels differentiable enough to act as convolutional operators, so a GNN can learn interpretable structural patterns as trainable filters.","keywords":["graph optimal matching kernel","disentangled graph representation","graph kernels","graph pattern mining","interpretable graph neural networks","subtree encoding","optimal matching","graph convolutional networks"],"falsifier":"Run GOMK on many pairs of small random subgraphs, computing the similarity in both directions and assembling the full pairwise similarity matrix; if any pair gives different values depending on direction, or if the matrix has a negative eigenvalue, the kernel property stated in the paper fails. Repeating the test with exact Hungarian matching rather than the greedy algorithm would isolate whether the greedy step is the cause.","tokens_in":20591,"feed_emoji":"🕸️","tokens_out":6799,"duration_ms":62084,"temperature":0.7,"pith_summary":"This paper proposes GOMKCN, a graph neural network that uses a graph kernel, GOMK, as its convolutional operator. For each node, GOMK compares the node-centered subgraph with several trainable graph filters by decomposing both into rooted subtrees and aligning those subtrees through matching; the matched-pair similarities form the node's disentangled representation. The authors claim this design makes graph kernels differentiable enough for end-to-end training while retaining accurate structural matching, and that the learned filters converge to the structural patterns that drive predictions. Synthetic experiments show the filters recover planted motifs, and on node and graph classification benchmarks GOMKCN matches or exceeds standard GNN baselines. If the claims hold, GNNs gain a way to learn task-relevant structural motifs as explicit, inspectable filters rather than leaving structure implicit in aggregated features.","feed_headline":"Optimal matching turns graph kernels into trainable GNN filters","feed_subtitle":"Aligning subtrees before scoring removes spurious matches and lets filters reveal the motifs behind each prediction.","key_machinery":"The central objects are the t-level Subtree Encoding (t-SE) and the Optimal Matching Kernel (OMK), which together form GOMK. A subgraph or filter is decomposed into subtrees rooted at each node; t-SE encodes each subtree by stacking the embeddings obtained from t rounds of weighted neighbor aggregation, so the whole subgraph becomes a set of subtree embedding vectors. OMK then measures set similarity by greedily matching each subtree in the smaller set to its most similar unmatched counterpart in the larger set and summing only matched-pair similarities, with the per-pair similarity given by a sum of RBF comparisons across levels. The theory section constructs an element kernel whose feature map is explicit via a hierarchical tree and uses the histogram intersection kernel to justify set-level similarity, which is what licenses viewing the kernel as an inner product in Hilbert space. This machinery carries the argument because it makes the graph kernel differentiable in the filter parameters while keeping the match-based accuracy that R-convolution-style sum-over-all-pairs kernels lack.","core_discovery":"On its own terms, the paper claims that graph kernels can be turned into convolutional operators without sacrificing matching accuracy, resolving what it calls the contradiction between differentiability and accuracy in existing graph kernels. The key move is to represent each node-centered subgraph and each trainable filter as a set of points in Hilbert space, with each point encoding a t-level subtree by stacking the outcomes of t rounds of neighbor aggregation. Similarity between a subgraph and a filter is then computed not by summing over all pairs of subtrees, which the paper argues injects spurious similarities, but by first aligning subtrees through an optimal matching and summing only the matched pairs. Because the filter's adjacency and feature matrices are learnable, gradient descent drives filters toward the structural patterns that matter for the task at hand. The paper also shows all subgraphs and filters with the same node count lie on a common sphere in this Hilbert space, so the kernel response is a cosine similarity, and it reads the disentangled representation of a node as the projection of its subgraph onto each learned filter.","pith_inferences":["Editorial inference: because the greedy matching in Algorithm 1 is not symmetric, one should test whether the Gram matrix of GOMK is positive semidefinite on random subgraph sets; if it is not, the 'kernel' claim would need to be weakened to 'differentiable similarity layer' while most empirical uses would survive.","Editorial inference: the full-rank condition on t-SE embeddings suggests low-dimensional or constant node features could collapse distinct subgraphs; augmenting features or using higher-dimensional filters should make the injectivity claim hold more often in practice.","Editorial inference: the same formulation could be pointed at graph clustering or anomaly detection by replacing the classification loss with a kernel k-means objective, since filters already act as cluster centers in the spherical feature space.","Editorial inference: the filter convergence experiments leave open whether the learned patterns are stable across random initializations; a repeated-seed study on the synthetic motif datasets would show which discovered motifs are robust."],"forward_implications":["A GNN built on GOMK can discover task-relevant structural motifs end-to-end instead of relying on a fixed, pre-enumerated motif vocabulary.","Because GOMK aligns subtrees before scoring, it avoids the spurious similarities that the paper attributes to summing over all substructure pairs in R-convolution kernels.","Node representations produced by GOMKCN are interpretable in the literal sense that a high coordinate value points to a local subgraph resembling the corresponding learned filter.","The spherical geometry of GOMK's feature space means kernel responses can be read as cosine similarities, so the same model can double as a frequent-subgraph miner by treating filters as cluster centers.","On the evaluated node and graph classification benchmarks, GOMKCN is competitive with or better than standard GNNs and the closest kernel-convolution baselines."],"supporting_citations":[{"why":"Supplies the R-convolution decomposition template that GOMK modifies by aligning substructures instead of summing over all pairs.","marker":"[27]"},{"why":"Provides the closest differentiable kernel-convolution baseline and one of the main comparisons for GOMKCN.","marker":"[21]"},{"why":"Introduces the improved random walk kernel convolution that GOMK is directly compared against in isomorphism learning and classification.","marker":"[22]"},{"why":"Establishes the subtree decomposition and label refinement background that t-SE turns into a differentiable embedding.","marker":"[32]"},{"why":"Supplies the valid optimal assignment kernel construction and hierarchical-tree feature map that the element kernel proof is modeled on.","marker":"[33]"},{"why":"Provides the Moore-Aronszajn theorem used to prove that the proposed element kernel is a valid kernel.","marker":"[45]"},{"why":"Defines the histogram intersection kernel used to compute set similarity and to connect it to matched subtree similarities.","marker":"[46]"},{"why":"Characterizes GNN expressive power through subgraph counting and separation, framing the expressiveness analysis of t-SE.","marker":"[42]"}],"fun_headline_variants":["Optimal matching kernel as trainable graph convolution","Align subtrees, then learn: graph kernel convolution","Disentangled graphs from optimal matching kernel filters","Graph kernel gets CNN treatment with optimal matching","Subtree-aware kernel convolution for interpretable GNNs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes that the greedy sequential subtree matching still yields a valid kernel, even though the matching depends on which graph is the source and no symmetry or positive-semidefiniteness proof is given for the greedy version.","fun_headline_variants_meta":{"raw":{"variants":["Optimal matching kernel as trainable graph convolution","Align subtrees, then learn: graph kernel convolution","Disentangled graphs from optimal matching kernel filters","Graph kernel gets CNN treatment with optimal matching","Subtree-aware kernel convolution for interpretable GNNs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000294,"raw_usage":{"total_tokens":1744,"prompt_tokens":1010,"completion_tokens":734,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":661}},"tokens_in":626,"tokens_out":734,"duration_ms":7098,"temperature":1.0,"reasoning_tokens":661,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:06:30.583047+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run GOMK on many pairs of small random subgraphs, computing the similarity in both directions and assembling the full pairwise similarity matrix; if any pair gives different values depending on direction, or if the matrix has a negative eigenvalue, the kernel property stated in the paper fails. Repeating the test with exact Hungarian matching rather than the greedy algorithm would isolate whether the greedy step is the cause.","supporting_citations":[{"cited_title":"Convolution kernels on discrete structures,","cited_arxiv_id":null,"evidence_quote":"Supplies the R-convolution decomposition template that GOMK modifies by aligning substructures instead of summing over all pairs."},{"cited_title":"Kergnns: Interpretable graph neural networks with graph kernels,","cited_arxiv_id":null,"evidence_quote":"Provides the closest differentiable kernel-convolution baseline and one of the main comparisons for GOMKCN."},{"cited_title":"Descriptive kernel convolution network with improved random walk kernel,","cited_arxiv_id":null,"evidence_quote":"Introduces the improved random walk kernel convolution that GOMK is directly compared against in isomorphism learning and classification."},{"cited_title":"On valid optimal as- signment kernels and applications to graph classification,","cited_arxiv_id":null,"evidence_quote":"Supplies the valid optimal assignment kernel construction and hierarchical-tree feature map that the element kernel proof is modeled on."},{"cited_title":"Generalized histogram intersection kernel for image recognition,","cited_arxiv_id":null,"evidence_quote":"Defines the histogram intersection kernel used to compute set similarity and to connect it to matched subtree similarities."},{"cited_title":"The expressive power of graph neural networks: A survey,","cited_arxiv_id":null,"evidence_quote":"Characterizes GNN expressive power through subgraph counting and separation, framing the expressiveness analysis of t-SE."}],"review_version":1}