Deep Weisfeiler-Lehman Assignment Kernels via Multiple Kernel Learning

Nils M. Kriege

REVIEW 4 major objections 5 minor 13 references

Deep Weisfeiler-Lehman Assignment Kernels via Multiple Kernel Learning

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict A clean MKL reduction for learning hierarchy weights in assignment kernels, with experiments too weak to support the 'effectiveness' claim. read the letter →

arxiv 1908.06661 v1 pith:AVMMS2JM submitted 2019-08-19 cs.LG stat.ML

Nils M. Kriege This is my paper · ORCID

classification cs.LGstat.ML

keywords graphkernelsassignmentWeisfeiler-Lehmanmultiplekernellearningstronghierarchyweightsclassification

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

The 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.

None 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.

Who 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.

Referee Report

4 major / 5 minor

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.

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 (4)

[§4, Table 1] 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.
[§3.2] 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.
[§3, §3.1] 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.
[§4] 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.

minor comments (5)

[§2.3, Eq. (4)] 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.
[§4, Table 1] The text refers to 'DWL-OA' after defining only DWL-OA1 and DWL-OA2; specify which variant is meant.
[§4] The statement that 'a significant proportion of the learned weights is zero' is never quantified; report the proportion and its variance across folds.
[Throughout] 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.
[§4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the learned hierarchy weights are an explicit MKL objective, and the paper's main theoretical claim is a construction, not a hidden reuse of its inputs.

full rationale

The derivation chain is self-contained. Equation (2) states that the optimal assignment kernel for a hierarchy is the weighted sum of histogram-intersection terms min{|X_v|,|Y_v|}. Section 3 then defines each such term as a separate kernel k_v and uses Eq. (4), EasyMKL, to solve for coefficients alpha_v, which are interpreted as the hierarchy weights omega(v). This is a direct, explicit construction: the learned weights are exactly the optimizing variables of a supervised multiple-kernel-learning problem, and the paper does not present the resulting kernel as an independent prediction of Eq. (2). The validity of the kernel construction relies on the theorem from [3] that every hierarchy induces a strong kernel and that Eq. (2) holds; although [3] is prior work by the same author, it is a parameter-free mathematical result with stated assumptions that do not include the present target, and it is externally published, so per the rules it counts as independent support rather than circular self-citation. The experimental section is similarly honest: the paper reports that 'there is no clear evidence that learning weights via MKL improves the classification accuracy significantly,' and it explicitly acknowledges the fixed-tree limitation that the set of optimal assignments is determined by T and cannot be repaired by learned weights. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported to forbid alternatives, and no ansatz is smuggled in via citation. The claim is therefore a legitimate construction with an honest empirical assessment, not a circular derivation.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central claim rests on two established building blocks: the hierarchy representation of strong kernels (Kriege et al., 2016) and EasyMKL's convex kernel combination. The only genuinely new object is the learned weight vector, which is a set of free parameters fit to the training set. No additional entities are introduced. The fixed number of clusters and WL iterations are hand-set, not derived.

free parameters (4)

Hierarchy weights alpha_v (per-cluster weights for DWL-OA2) = Not reported; learned per data set via EasyMKL
These are the central free parameters. They are selected to optimize the EasyMKL objective in Eq. (4), and no learned-weight values or analyses are given.
Number of clusters k = 10
Fixed by hand for DWL-OA2 in all experiments (Section 4); not tuned and no sensitivity analysis is provided.
Number of WL iterations h = 4
Fixed for all experiments (Section 4). The paper claims lower sensitivity to h but does not test this claim.
EasyMKL regularizer lambda and SVM C = lambda from {0.1,0.3,0.5,0.7,0.9}; C from {0.01,0.1,1,10,100} via inner cross-validation
Standard hyperparameters reported in Section 4, used to control regularization in EasyMKL and the SVM.

assumptions (5)

standard math A strong base kernel is equivalent to a hierarchy-induced kernel (Kriege et al., 2016).
Relied on in Section 2.1; the paper does not reprove this equivalence.
standard math The function k_v(X,Y)=min{|X_v|, |Y_v|} is a valid kernel for each node v.
Needed to apply MKL to Eq. (2); follows from histogram intersection and is stated implicitly in Section 3.
domain assumption Color refinement applied to a set of graphs under one injective mapping yields a hierarchy on the vertices.
Flagged as observed in [3] in Section 2.2; central to the WL hierarchy construction.
standard math EasyMKL returns nonnegative coefficients alpha_i whose convex combination is a valid kernel.
Used in Eq. (4) and Section 3; convex combinations of kernels are kernels, but the nonnegativity and normalization of the EasyMKL solution are assumed.
domain assumption K-means clustering of node count vectors with k=10 preserves enough granularity for useful weight learning.
Used in DWL-OA2 experiments; no validation of cluster quality or sensitivity to k is provided.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Deep Weisfeiler-Lehman Assignment Kernels via Multiple Kernel Learning." pith.science (2026). https://pith.science/paper/AVMMS2JM

@misc{pith2026190806661,
  author       = {Pith},
  title        = {Pith review of: Deep Weisfeiler-Lehman Assignment Kernels via Multiple Kernel Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AVMMS2JM}},
  note         = {Machine review of arXiv:1908.06661}
}

read the original abstract

Kernels for structured data are commonly obtained by decomposing objects into their parts and adding up the similarities between all pairs of parts measured by a base kernel. Assignment kernels are based on an optimal bijection between the parts and have proven to be an effective alternative to the established convolution kernels. We explore how the base kernel can be learned as part of the classification problem. We build on the theory of valid assignment kernels derived from hierarchies defined on the parts. We show that the weights of this hierarchy can be optimized via multiple kernel learning. We apply this result to learn vertex similarities for the Weisfeiler-Lehman optimal assignment kernel for graph classification. We present first experimental results which demonstrate the feasibility and effectiveness of the approach.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[4]

Gilmer, S

J. Gilmer, S. S. Schoenholz, P . F. Riley, O. Vinyals, and G . E. Dahl. Neural message passing for quantum chemistry. In 33rd International Conference on Machine Learning , 2017

work page 2017
[5]

R. Ying, J. Y ou, C. Morris, X. Ren, W. L. Hamilton, and J. Le skovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, 2018

work page 2018
[6]

Vishwanathan

Pinar Y anardag and S.V .N. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1365–1374. ACM, 2015

work page 2015
[1]

Nils M. Kriege. Deep Weisfeiler-Lehman assignment kern els via multiple kernel learn- ing. In 27th European Symposium on Artiﬁcial Neural Networks, ESAN N 2019, Bruges, Belgium, 24-26 April, 2019. 6

work page 2019
[2]

Borgwardt

Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeu wen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12:2539–2561, 2011

work page 2011
[3]

Kriege, Pierre-Louis Giscard, and Richard Wilso n

Nils M. Kriege, Pierre-Louis Giscard, and Richard Wilso n. On valid optimal assignment kernels and applications to graph classiﬁcation. In Advances in Neural Information Pro- cessing Systems, pages 1623–1631. Curran Associates, Inc., 2016

work page 2016
[7]

Deep-er kernels

John Shawe-Taylor. Deep-er kernels. In ICPRAM 2014 - Proceedings of the 3rd Interna- tional Conference on Pattern Recognition Applications and Methods, pages IS–9, 2014

work page 2014
[8]

Learning deep kernels i n the space of dot product poly- nomials

Michele Donini and Fabio Aiolli. Learning deep kernels i n the space of dot product poly- nomials. Machine Learning, pages 1–25, 2016

work page 2016

Show all 13 references

[9]

Aiolli, M

F. Aiolli, M. Donini, N. Navarin, and A. Sperduti. Multip le graph-kernel learning. In 2015 IEEE Symposium Series on Computational Intelligence , pages 1607–1614, Dec 2015

2015
[10]

Wegner, Florian Sieker, andAndreas Zell

Holger Fr¨ ohlich, J¨ org K. Wegner, Florian Sieker, andAndreas Zell. Optimal assignment kernels for attributed molecular graphs. In Proceedings of the 22nd International Confer- ence on Machine learning, pages 225–232, New Y ork, NY , USA, 2005. ACM

2005
[11]

The optimal assignment kernel is n ot positive deﬁnite

Jean-Philippe V ert. The optimal assignment kernel is n ot positive deﬁnite. CoRR, abs/0801.4061, 2008

2008 arXiv
[12]

EasyMKL: a scalable mu ltiple kernel learning algorithm

Fabio Aiolli and Michele Donini. EasyMKL: a scalable mu ltiple kernel learning algorithm. Neurocomputing, 169:215 – 224, 2015

2015
[13]

Kriege, Christopher Morris , Petra Mutzel, and Marion Neumann

Kristian Kersting, Nils M. Kriege, Christopher Morris , Petra Mutzel, and Marion Neumann. Benchmark data sets for graph kernels, 2 016. http://graphkernels.cs.tu-dortmund.de. 7

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [4]

Gilmer, S

J. Gilmer, S. S. Schoenholz, P . F. Riley, O. Vinyals, and G . E. Dahl. Neural message passing for quantum chemistry. In 33rd International Conference on Machine Learning , 2017

work page 2017

[2] [5]

R. Ying, J. Y ou, C. Morris, X. Ren, W. L. Hamilton, and J. Le skovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, 2018

work page 2018

[3] [6]

Vishwanathan

Pinar Y anardag and S.V .N. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1365–1374. ACM, 2015

work page 2015

[4] [1]

Nils M. Kriege. Deep Weisfeiler-Lehman assignment kern els via multiple kernel learn- ing. In 27th European Symposium on Artiﬁcial Neural Networks, ESAN N 2019, Bruges, Belgium, 24-26 April, 2019. 6

work page 2019

[5] [2]

Borgwardt

Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeu wen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12:2539–2561, 2011

work page 2011

[6] [3]

Kriege, Pierre-Louis Giscard, and Richard Wilso n

Nils M. Kriege, Pierre-Louis Giscard, and Richard Wilso n. On valid optimal assignment kernels and applications to graph classiﬁcation. In Advances in Neural Information Pro- cessing Systems, pages 1623–1631. Curran Associates, Inc., 2016

work page 2016

[7] [7]

Deep-er kernels

John Shawe-Taylor. Deep-er kernels. In ICPRAM 2014 - Proceedings of the 3rd Interna- tional Conference on Pattern Recognition Applications and Methods, pages IS–9, 2014

work page 2014

[8] [8]

Learning deep kernels i n the space of dot product poly- nomials

Michele Donini and Fabio Aiolli. Learning deep kernels i n the space of dot product poly- nomials. Machine Learning, pages 1–25, 2016

work page 2016