{"id":"17d72027-8746-4e6b-ba65-aee704b77566","arxiv_id":"1908.06661","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"Weights of the hierarchy that defines a Weisfeiler-Lehman optimal assignment kernel can be learned with multiple kernel learning, yielding a deep assignment kernel with sparse weights.","lead":"Learning the weights that define vertex similarities inside Weisfeiler-Lehman assignment kernels as part of training, using multiple kernel learning. The approach gives a principled way to build sparse, adaptive graph kernels, though experiments show only small, often not significant, accuracy changes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central MKL reduction is sound, but the practical claim of effectiveness rests on Table 1, which does not show that learned weights help.","rationale":"I read the paper as making two distinct claims: a theoretical reduction showing that hierarchy weights for a fixed WL color-refinement tree can be learned by MKL while preserving kernel validity, and an applied claim that this yields feasible and effective graph classification. The theoretical claim is sound. Eq. (2) expresses the assignment kernel as a nonnegative linear combination of node-wise histogram-intersection kernels, EasyMKL optimizes exactly such a combination, and the resulting base kernel is strong because it is still derived from the same hierarchy with nonnegative node weights. No hidden correctness assumption appears in this part. The applied claim is where the argument is insecure. The only experimental evidence is Table 1, which shows no significant accuracy gain, and the paper's own text concedes this. The reader's weakest assumption about fixed hierarchy expressiveness is real and acknowledged, but it is a limitation rather than a flaw; my sharper concern is that the empirical section does not even demonstrate that the learned weights matter, which is what would make the contribution practically load-bearing. The proposed random-weight comparison would settle exactly this. Because the reader already assigned CONDITIONAL on grounds that include weak empirical evidence, my stress-test does not move the verdict.","tokens_in":5779,"tokens_out":11732,"duration_ms":138313,"concrete_test":"Repeat the Table 1 protocol for DWL-OA2 on MUTAG, PTC-MR, NCI1, NCI109, PROTEINS, D&D, and REDDIT with the same cross-validation folds, but replace EasyMKL-learned weights with (a) uniform weights and (b) randomly permuted learned weights drawn from the same simplex, and report paired accuracy differences with a signed test such as Wilcoxon across the repeated folds. If uniform or random weights are statistically indistinguishable from learned weights, the learned-weight component of the effectiveness claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theoretical reduction in Section 3 is internally consistent: Eq. (2) makes the hierarchy weights appear linearly, EasyMKL returns nonnegative coefficients, and the resulting weighted hierarchy still induces a strong base kernel, so the combined kernel is valid. The load-bearing concern is the paper's applied claim that the approach is 'effective.' Table 1 shows DWL-OA2 within about one point of WL-OA on most sets and worse on REDDIT (86.9 vs. 88.5 for WL-OA); DWL-OA1 runs out of memory on every dataset above 1,000 objects; no significance tests, no comparison against uniform or randomly permuted weights, and no analysis of the learned weights are provided. The authors state this directly: 'there is no clear evidence that learning weights via MKL improves the classification accuracy significantly.' Since Section 3 also acknowledges that the fixed tree T determines the set of optimal assignments, learned weights cannot repair a hierarchy that is poorly matched to the task; the empirical question is therefore decisive for the central claim. The concern is about missing support, not an inconsistency in the derivation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies assignment kernels derived from hierarchies and proposes to learn the hierarchy weights via multiple kernel learning. The central observation is that the optimal assignment kernel of Eq. (2) is linear in the node weights, so each node v defines a histogram-intersection kernel k_v(X,Y)=min{|X_v|,|Y_v|}; combining these kernels with EasyMKL yields a coefficient vector that can be interpreted as hierarchy weights. The authors instantiate this for Weisfeiler-Lehman optimal assignment kernels, defining DWL-OA1 (per-node weights) and DWL-OA2 (weights shared by k-means clusters of hierarchy nodes). Experiments on seven graph benchmark data sets compare WL, WL-OA, DWL-OA1, and DWL-OA2. The paper reports comparable accuracies, sparsity of learned weights, but also out-of-memory failures for DWL-OA1 on large data sets and states that no significant accuracy improvement is observed.","tokens_in":5978,"tokens_out":7103,"duration_ms":75105,"significance":"The theoretical reduction is clean and correct: as long as the MKL coefficients are nonnegative, the weighted hierarchy induces a strong base kernel and the resulting assignment kernel is valid. This is a useful and nontrivial observation, and the sparsity of the learned weights is an appealing practical byproduct. If the practical effectiveness were established, the method would provide a data-adaptive yet theoretically sound alternative to hand-tuned WL-OA kernels. The paper also honestly states its main limitation: a fixed hierarchy determines the set of optimal assignments, and learned weights cannot change that set. However, the current experimental evidence does not establish effectiveness, and the feature-grouping step may leak test-set information; hence the practical contribution is not yet supported.","major_comments":[{"comment":"The empirical evidence does not support the 'effectiveness' claimed in the abstract. DWL-OA2 is within about one accuracy point of WL-OA on MUTAG, PTC-MR, NCI1, NCI109, and D&D, and it is worse on REDDIT (86.9 versus 88.5); the text itself says that 'there is no clear evidence that learning weights via MKL improves the classification accuracy significantly.' No significance tests are reported, and DWL-OA1 ran out of memory on five of the seven data sets. The authors should add paired significance tests over the repeated folds, include baselines with uniform weights and with randomly permuted weights to show that the learned weights matter, and report the memory footprint of the MKL step.","section":"§4, Table 1"},{"comment":"The feature-grouping procedure as written can leak information from the test set. The text says each hierarchy node is represented by a vector over 'the data set' of size n, and k-means is applied to these vectors; if this clustering is performed on all objects before the cross-validation split, the test objects influence which nodes share learned weights. This must be clarified and, if that is what was done, recomputed inside each training fold. The sensitivity to the number of clusters k=10 should also be reported.","section":"§3.2"},{"comment":"The paper's own limitation statement—'The tree T determines a set of optimal solutions...These solutions will remain optimal under all learned weight functions'—means the method cannot recover from a hierarchy whose optimal assignment set is poorly matched to the task. Since the experimental results do not show that learned weights improve over uniform weights, the paper should provide direct evidence on this point, for example, an analysis of which nodes or clusters receive nonzero weights, a comparison across different values of h, and a control with a deliberately less informative hierarchy.","section":"§3, §3.1"},{"comment":"The introduction motivates the work through deep graph classification methods (neural message passing [4], differentiable pooling [5], deep graph kernels [6]), but the experiments compare only with WL and WL-OA. Without comparisons to at least one of the cited deep learning methods, the paper cannot support its positioning as a deep approach with competitive effectiveness. The fixed value h=4 also leaves the claim that the method is 'less dependent' on h untested; an ablation over h is needed.","section":"§4"}],"minor_comments":[{"comment":"The summation in Eq. (4) is written as i=0 to R, although the text says there are R kernels k_1,...,k_R; the index should presumably start at 1.","section":"§2.3, Eq. (4)"},{"comment":"The text refers to 'DWL-OA' after defining only DWL-OA1 and DWL-OA2; specify which variant is meant.","section":"§4, Table 1"},{"comment":"The statement that 'a significant proportion of the learned weights is zero' is never quantified; report the proportion and its variance across folds.","section":"§4"},{"comment":"The paper contains several typos and formatting artifacts, for example 'decomp osing', 'na¨ ıve', and the table entries 'P ROTEINS' and 'R EDDIT'; a careful proofread is needed.","section":"Throughout"},{"comment":"No code or data link is provided, which makes the experiments hard to reproduce; please make the implementation available or give precise details for preprocessing and the k-means initialization.","section":"§4"}],"recommendation":"major_revision","confidential_remarks":"The theoretical part is sound and publishable, but the experimental section is currently insufficient for the claims made in the abstract. The potential test-set leakage in §3.2 is the most serious issue and must be resolved before acceptance. I recommend major revision rather than rejection because the theoretical reduction is correct and the experimental deficiencies are addressable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the reduction in Section 3 is correct and worth knowing. Eq. (2) makes the hierarchy weights appear linearly, so EasyMKL can learn them while keeping the optimal assignment kernel valid. That is a real, if modest, contribution, and I haven't seen it stated in the earlier assignment-kernel or MKL literature. The author also handles the key limitation honestly: the tree T fixes the set of optimal assignments, so learned weights can only reweight those solutions, not escape a bad hierarchy.\n\nThe paper does a few other things well. The derivation of k_v(X,Y)=min{|X_v|,|Y_v|} and the use of k-means to group hierarchy nodes for weight sharing is clean. The sparse-weight observation is plausible and could be practically useful. And the prose is refreshingly candid — Section 4 explicitly says there is no clear evidence that MKL improves accuracy significantly.\n\nThe soft spot is exactly that: the experiments don't show the method helps. Table 1 puts DWL-OA2 within noise of WL-OA on most sets, worse on REDDIT, and DWL-OA1 runs out of memory on five of seven data sets. There are no significance tests, no comparison against uniform or random weights, no learned-weight analysis, and no comparison with the deep learning methods cited in the introduction. The abstract says the approach is 'effective', which sits awkwardly next to the body's own admission. The state-of-the-art claim about WL-OA is also unsubstantiated in this paper.\n\nNone of this undermines the theoretical claim. The MKL reduction is a legitimate methodological step, and the limitation about fixed optimal assignments is stated in the paper itself. What is missing is support for the applied claim, not correctness of the math.\n\nWho is this for? Someone working on graph kernels or assignment kernels will get value from the reduction and may reuse it. It is not a demonstration that deep assignment kernels beat existing methods. As a desk decision, I'd send it to peer review: the theoretical contribution is real and the limitations are mostly empirical. A referee should press on the experimental design and on softening the abstract.","headline":"A clean MKL reduction for learning hierarchy weights in assignment kernels, with experiments too weak to support the 'effectiveness' claim.","tokens_in":6499,"tokens_out":2198,"would_cite":true,"duration_ms":22411,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The weights of a hierarchy defining a strong base kernel for an optimal assignment kernel can be learned via multiple kernel learning, yielding a data-adapted deep Weisfeiler-Lehman assignment kernel.","keywords":["graph kernels","assignment kernels","Weisfeiler-Lehman","multiple kernel learning","strong kernels","hierarchy weights","graph classification","kernel learning"],"falsifier":"On a synthetic two-class graph data set where class membership depends on a vertex attribute that color refinement merges into one color at every level, the deep Weisfeiler-Lehman assignment kernel cannot separate the classes under any learned weights, since every vertex in both classes has identical color sequences; the method's cross-validated accuracy would remain at chance.","tokens_in":5560,"feed_emoji":"⚖️","tokens_out":5958,"duration_ms":57200,"temperature":0.7,"pith_summary":"This paper proposes that the base kernel underlying an optimal assignment kernel should itself be learned as part of the classification task, rather than fixed in advance. For the restricted but expressive class of base kernels induced by a hierarchy on the parts, each node of the hierarchy contributes a separate kernel, and multiple kernel learning supplies the node weights. Applied to the Weisfeiler-Lehman color-refinement hierarchy, this produces a deep Weisfeiler-Lehman assignment kernel whose vertex similarities adapt to the data. The paper demonstrates feasibility on standard graph classification benchmarks and shows that many learned weights vanish, yielding compact sparse models. A sympathetic reader would care because it brings an interpretable, data-driven depth to kernel methods without abandoning kernel validity.","feed_headline":"Learned weights turn WL assignment kernels deep","feed_subtitle":"Color-refinement hierarchy weights adapt to each classification task instead of staying uniform.","key_machinery":"The key machinery is the hierarchy $(T,\\omega)$ on the set of parts, together with the identity that the optimal assignment kernel equals a weighted count over tree nodes, $K_B^k(X,Y)=\\sum_{v\\in V(T)} \\min\\{|X_v|,|Y_v|\\}\\,\\omega(v)$. This identity recasts assignment as histogram intersection, and each summand $k_v(X,Y)=\\min\\{|X_v|,|Y_v|\\}$ is itself a kernel, so multiple kernel learning can optimize the weights $\\omega(v)$. For the deep Weisfeiler-Lehman assignment kernel, the hierarchy is generated by color refinement, where inner nodes correspond to colors and the learned weights express how strongly each color-refinement level should contribute to vertex similarity.","core_discovery":"The central claim is that the weights of the hierarchy that defines a strong base kernel can be optimized via multiple kernel learning. For every node $v$ in the hierarchy tree $T$, the function $k_v(X,Y)=\\min\\{|X_v|,|Y_v|\\}$ is itself a valid kernel, and solving the MKL objective of Eq. (4) returns coefficients $\\alpha_v$ with $\\|\\alpha\\|=1$ that serve as the learned hierarchy weights $\\omega(v)=\\alpha_v$. Since the optimal assignment kernel for a strong base kernel decomposes as $\\sum_{v\\in V(T)} \\min\\{|X_v|,|Y_v|\\}\\,\\omega(v)$, this learned weighting directly yields a valid assignment kernel adapted to the learning task. The paper instantiates this for the Weisfeiler-Lehman color-refinement hierarchy, defining the deep Weisfeiler-Lehman assignment kernel, and reports experiments showing its feasibility, with feature grouping as a practical means to control the number of learned weights.","pith_inferences":["Because the learned weights only revalue assignments that the fixed hierarchy already allows, the method's discriminative power is capped by the hierarchy's set of optimal matchings; a task that requires a matching outside that set will defeat any weight choice.","The same MKL-for-hierarchy-weights recipe transfers to any structured object whose parts admit a hierarchy, such as strings or trees, not just graphs.","The nonzero learned weights could be inspected as interpretable indicators of which neighborhood depths matter for a given classification problem, a direction the author leaves for future work."],"forward_implications":["The Weisfeiler-Lehman assignment kernel becomes a deep kernel: different classification tasks can focus on different color-refinement levels through the learned weights.","Because the learned kernel remains a valid optimal assignment kernel, the theoretical guarantees of the strong-base-kernel framework continue to hold.","Zero learned weights allow nodes to be pruned from the hierarchy, producing sparser models and faster evaluation.","The sensitivity to the number of refinement iterations $h$ is reduced, since overly specific features are down-weighted automatically."],"supporting_citations":[{"why":"Establishes the theory that strong base kernels are exactly those induced by hierarchies and that the optimal assignment kernel decomposes as histogram intersection; this is the foundation the weight-learning construction builds on.","marker":"[3]"},{"why":"Introduces the Weisfeiler-Lehman color-refinement procedure and the WL subtree kernel whose hierarchy the deep assignment kernel reuses.","marker":"[2]"},{"why":"Supplies the EasyMKL multiple kernel learning algorithm used to optimize the hierarchy weights in Eq. (4).","marker":"[12]"},{"why":"Shows that unrestricted optimal assignment kernels are not positive definite, motivating the restriction to strong base kernels on which the learned-weight kernel relies.","marker":"[11]"}],"fun_headline_variants":["Learning hierarchy weights deepens WL assignment kernels","MKL tunes WL kernel weights for task-specific depth","Task-adaptive weights for Weisfeiler-Lehman kernels","Deep WL assignment kernels via learned weights","Optimal assignment kernels get deep with MKL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hierarchy generated by color refinement fixes which vertex matchings are optimal, and those matchings stay optimal under every learned weight function, so if the hierarchy's optimal assignment set does not contain the distinctions a task needs, learning weights cannot recover them.","fun_headline_variants_meta":{"raw":{"variants":["Learning hierarchy weights deepens WL assignment kernels","MKL tunes WL kernel weights for task-specific depth","Task-adaptive weights for Weisfeiler-Lehman kernels","Deep WL assignment kernels via learned weights","Optimal assignment kernels get deep with MKL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000242,"raw_usage":{"total_tokens":1479,"prompt_tokens":854,"completion_tokens":625,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":470,"completion_tokens_details":{"reasoning_tokens":553}},"tokens_in":470,"tokens_out":625,"duration_ms":6343,"temperature":1.0,"reasoning_tokens":553,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:37:32.503595+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a synthetic two-class graph data set where class membership depends on a vertex attribute that color refinement merges into one color at every level, the deep Weisfeiler-Lehman assignment kernel cannot separate the classes under any learned weights, since every vertex in both classes has identical color sequences; the method's cross-validated accuracy would remain at chance.","supporting_citations":[{"cited_title":"Kriege, Pierre-Louis Giscard, and Richard Wilso n","cited_arxiv_id":null,"evidence_quote":"Establishes the theory that strong base kernels are exactly those induced by hierarchies and that the optimal assignment kernel decomposes as histogram intersection; this is the foundation the weight-learning construction builds on."},{"cited_title":"Borgwardt","cited_arxiv_id":null,"evidence_quote":"Introduces the Weisfeiler-Lehman color-refinement procedure and the WL subtree kernel whose hierarchy the deep assignment kernel reuses."},{"cited_title":"EasyMKL: a scalable mu ltiple kernel learning algorithm","cited_arxiv_id":null,"evidence_quote":"Supplies the EasyMKL multiple kernel learning algorithm used to optimize the hierarchy weights in Eq. (4)."},{"cited_title":"The optimal assignment kernel is not positive definite","cited_arxiv_id":"0801.4061","evidence_quote":"Shows that unrestricted optimal assignment kernels are not positive definite, motivating the restriction to strong base kernels on which the learned-weight kernel relies."}],"review_version":1}