GKer

GKer is a class of kernel-based methods used to measure the similarity between structured objects, with a focus on graphs. In kernel methods, a kernel function K(x, y) implicitly defines a feature mapping that allows learning algorithms to operate in a high-dimensional space without explicit feature construction. GKer applications typically involve comparing graphs or graph-structured data, enabling tasks such as classification, clustering, and regression.

Common members of the GKer family include several graph kernels, each defining similarity through different substructure counts. The Weisfeiler-Lehman kernel compares graphs based on iterative relabeling and subtree patterns. The shortest-path kernel uses pairs of nodes connected by shortest paths as features. The graphlet kernel counts small connected induced subgraphs, while random-walk kernels compare graphs by enumerating and weighting random walks. These approaches address graph isomorphism concerns and vary in computational cost and sensitivity to graph size and labeling.

History and context: graph kernels emerged in the early 2000s as a way to apply kernelized learning to graph-structured data, including chemical structures and biological networks. GKer enables the use of standard algorithms such as support vector machines and Gaussian processes without explicit graph feature engineering. Researchers pursue variants that balance expressiveness and scalability, often by approximating counts or using sparse representations.

Computation and limitations: kernel computation can be expensive for large graphs or large datasets, motivating approximate methods and parallel implementations. Kernel choice and parameter tuning influence performance and interpretation, requiring domain knowledge and cross-validation.

Applications and influence: GKer methods are used in cheminformatics, materials science, bioinformatics, and network analysis to predict properties, classify graphs, or detect similarities across datasets. See also graph kernel and kernel methods.