Source-linked AI summary
On Valid Optimal Assignment Kernels and Applications to Graph Classification
Nils M. Kriege, Pierre-Louis Giscard, Richard C. Wilson
TL;DR
Optimal assignment similarities can better capture structural correspondence than convolution kernels, but they are generally not valid kernels. The paper characterizes strong base kernels that guarantee validity, computes the resulting assignments efficiently through hierarchies and histogram intersection, and applies them to graph classification, where WL-OA usually improves over WL.
Problem
Optimal assignments can provide more meaningful structural similarity than convolution kernels but generally yield indefinite functions, complicating their use in kernel methods.
Method
The paper characterizes strong base kernels, proves their equivalence to hierarchy-induced kernels, and computes valid optimal assignments through linear-time histogram intersection.
Results
WL-OA performs best on seven of nine data sets and generally improves over WL, with MUTAG as a distinct exception.
Takeaways & Limitations
Strong kernels provide a basis for efficient similarity kernels, including graph kernels that improve over convolution-based counterparts on classification benchmarks.
Takeaways & Limitations
The presentation assumes fixed set cardinality; differing sizes require filling the smaller set with zero-similarity objects.
Abstract
from arXiv · showhide
The success of kernel methods has initiated the design of novel positive semidefinite functions, in particular for structured data. A leading design paradigm for this is the convolution kernel, which decomposes structured objects into their parts and sums over all pairs of parts. Assignment kernels, in contrast, are obtained from an optimal bijection between parts, which can provide a more valid notion of similarity. In general however, optimal assignments yield indefinite functions, which complicates their use in kernel methods. We characterize a class of base kernels used to compare parts that guarantees positive semidefinite optimal assignment kernels. These base kernels give rise to hierarchies from which the optimal assignment kernels are computed in linear time by histogram intersection. We apply these results by developing the Weisfeiler-Lehman optimal assignment kernel for graphs. It provides high classification accuracy on widely-used benchmark data sets improving over the original Weisfeiler-Lehman kernel.
1 Introduction
The paper addresses the difficulty that optimal assignment similarities are not generally valid kernels by identifying base kernels that guarantee validity. It develops efficient hierarchical computation and applies the framework to graph classification.
- 1 Introduction: Optimal assignments maximize total similarity over bijections between parts, establishing structural correspondences unlike convolution kernels.Convolution kernels instead sum pairwise similarities across decomposed parts.
- 1 Introduction: The paper studies base kernels that produce valid, meaning symmetric and positive semidefinite, optimal assignment kernels.The optimal assignment kernel is defined over bijections between equal-sized subsets.
- 1 Introduction: Prior graph optimal-assignment similarities were not necessarily valid, while a soft-max alternative required an additional parameter and summation over all assignments.The paper instead seeks a single optimal assignment with validity guarantees.
- 1 Introduction: Strong base kernels are characterized as exactly those induced by hierarchies, yielding valid optimal assignment kernels computable in linear time by histogram intersection.The approach is not restricted to vectorial objects in Euclidean space.
- 1 Introduction: The framework produces graph kernels, including the Weisfeiler-Lehman optimal assignment kernel, which performs favorably against state-of-the-art graph kernels across many data sets.The authors report improvements over convolution-based counterparts.
2 Preliminaries
The preliminaries define valid kernels through Hilbert-space inner products and positive semidefinite Gram matrices, then establish notation for graphs and rooted trees.
- 2 Preliminaries: A valid kernel is represented as an inner product in a real Hilbert space through a feature map.The equivalent matrix criterion requires every finite kernel matrix to be positive semidefinite.
- 2 Preliminaries: The Dirac kernel assigns one to identical objects and zero to distinct objects.This provides a basic equality-based kernel example.
- 2 Preliminaries: Graphs are defined as simple undirected pairs of vertices and edges, with each edge represented symmetrically by either endpoint order.The preliminaries also distinguish trees and rooted trees using a designated root and parent relation.
3 Strong kernels and hierarchies
Strong kernels are characterized both by a similarity inequality and by weighted hierarchies, which also provide constructive representations and efficient feature maps.
- Strong kernels: A strong kernel satisfies k(x, y) ≥ min{k(x, z), k(z, y)} for all x, y, z ∈X.This condition defines the restricted kernel class studied in the section.
- Hierarchies: A hierarchy is a rooted tree on X whose leaves are objects and whose nondecreasing weights induce k(x, y) = w(LCA(x, y)).Each inner vertex represents the leaves of its subtree, and weights satisfy w(v) ≥ w(p(v)).
- Equivalence: Every hierarchy-induced kernel is strong, and every strong kernel has a hierarchy that induces it.Thus, the inequality-based and hierarchy-based characterizations define the same class.
- Constructive characterization: A hierarchy for a strong kernel can be constructed incrementally by inserting each new object as a leaf under a new parent determined by its maximum similarity.The construction identifies the leaves attaining kmax and grafts the new leaf onto their common subtree.
- Consequences: A strong kernel on n objects takes at most 2|X| −1 distinct values, and strong kernels are valid positive semidefinite kernels.The feature-map construction establishes validity, while the value bound follows from the hierarchy representation.
- Feature maps: Strong kernels admit additive feature maps whose coordinates are hierarchy vertices, with each object receiving the additive weights along its path to the root.The resulting dot product equals the kernel value for every pair of objects.
4 Valid kernels from optimal assignments
For strong base kernels, optimal assignment kernels are valid and can be computed through histogram intersection using an associated hierarchy. The resulting computation is linear in the set sizes rather than cubic with a general Hungarian assignment method.
- Histogram representation: A strong base kernel induces histograms whose entries are the kernel hierarchy weights multiplied by subtree multiplicities.For a hierarchy (T, w), each histogram entry is [Hk(X)]v = ω(v) · |Xv|.
- Optimal assignment identity: The optimal assignment value equals the histogram intersection value for strong base kernels.The equality follows by matching as many elements as possible within each hierarchy subtree, namely min{|Xv|, |Yv|} pairs.
- Illustration: In the illustrated assignment, both methods produce the value 15 after accounting for repeated labels and hierarchy weights.The optimal assignment and histogram intersection each evaluate to 15.
- Validity: Strong-base-kernel optimal assignment functions are valid kernels, meaning they are symmetric and positive semidefinite.This is stated by the theorem and its corollary for all X, Y ∈[X]n.
- Efficient computation: Given the hierarchy, bottom-up histogram construction and intersection compute the kernel in O(|X| + |Y |) time.This improves on the cubic-time general Hungarian method for solving the assignment problem.
5 Graph kernels from optimal assignments
The paper applies valid optimal assignment kernels to graphs by comparing labelled vertices and edges, then develops a Weisfeiler-Lehman optimal assignment kernel from colour-refinement hierarchies. The resulting base kernel is strong and therefore yields a valid kernel computable from Weisfeiler-Lehman feature vectors.
- Graph baselines: Graph optimal assignment kernels compare graph structures through bijections between labelled vertices or edges.The vertex and edge constructions use label-based base kernels; the vertex baseline uses the Dirac kernel on vertex labels.
- Weisfeiler-Lehman refinement: The Weisfeiler-Lehman subtree kernel iteratively refines vertex colours and counts shared colours through feature-vector dot products.Each refinement incorporates a vertex's current colour and the lexicographically sorted multiset of neighbour colours.
- Weisfeiler-Lehman optimal assignment: WL-OA uses a base kernel whose value counts matching colours across the refinement sequence, capturing neighbourhood similarity.The refinement colour classes form nested partitions and therefore define a hierarchy on the set of vertices.
- Validity and computation: Because the refinement hierarchy induces a strong base kernel, WL-OA is a valid kernel and can be computed from Weisfeiler-Lehman subtree feature vectors in linear time.The construction connects the optimal-assignment formulation to the hierarchy-based validity and computation results.
6 Experimental evaluation
The evaluation compares proposed optimal-assignment graph kernels with convolution and other kernels across graph-classification benchmarks. Optimal-assignment kernels generally improve related convolution kernels, with WL-OA performing best on most datasets while maintaining efficient computation.
- Experimental setup: Experiments used LIBSVM C-SVM with repeated 10-fold cross-validation and training-set parameter selection.Kernel normalization, regularization, and applicable kernel parameters were selected within each fold.
- Kernels: The study evaluated vertex, edge, Weisfeiler-Lehman, graphlet, shortest-path, and corresponding optimal-assignment kernels.Kernels without the OA suffix were convolution kernels; WL used h selected from {0, ..., 7}.
- Data sets: Benchmarks covered small-molecule, macromolecule, and social-network graphs, with two to six class labels.Social-network graphs were unlabelled and uniformly vertex-labelled, while edge labels were ignored when present.
- Results: Optimal-assignment kernels improved their convolution counterparts on most datasets, with MUTAG the distinct exception and especially notable gains on ENZYMES and REDDIT.The authors interpret this pattern as evidence that optimal assignments provide a more valid similarity notion for these classification tasks.
- Results: WL-OA performed best on seven of nine datasets, ranked second on D&D, and showed only a small difference from WL and baselines on MUTAG.The strongest results were therefore concentrated in WL-OA, although its advantage was limited on two datasets.
- Efficiency: Kernel-matrix computation took under one minute except for SP on D&D and REDDIT and GL on COLLAB, while OA computation matched related convolution-kernel runtimes.The reported exceptions required 29 minutes, 2 hours, and 28 minutes, respectively.
7 Conclusions and future work
The paper characterizes strong kernels as a route to valid optimal-assignment kernels and derives efficient graph kernels through histogram intersection. It identifies these results as a basis for designing new kernels and provides dataset resources for further work.
- Conclusions: Strong kernels lead to valid optimal-assignment kernels, and the paper derives novel effective kernels for graphs.The conclusion identifies this characterization and graph-kernel construction as the paper’s central outcomes.
- Future work: Reducing optimal-assignment computation to histogram intersection enables efficient computation and direct use of known intersection-kernel speed-up techniques.The authors suggest these results may support new kernels that efficiently measure similarity.
- Resources: The datasets, references, and statistics are available through the graph-kernel resource website.The availability information is given in a footnote accompanying the conclusion section.