| 1. |
- Kriege, Nils M., et al.
(författare)
-
A survey on graph kernels
- 2020
-
Ingår i: Applied Network Science. - : Springer Science and Business Media LLC. - 2364-8228. ; 5:1
-
Forskningsöversikt (refereegranskat)abstract
- Graph kernels have become an established and widely-used technique for solving classification tasks on graphs. This survey gives a comprehensive overview of techniques for kernel-based graph classification developed in the past 15 years. We describe and categorize graph kernels based on properties inherent to their design, such as the nature of their extracted graph features, their method of computation and their applicability to problems in practice. In an extensive experimental evaluation, we study the classification accuracy of a large suite of graph kernels on established benchmarks as well as new datasets. We compare the performance of popular kernels with several baseline methods and study the effect of applying a Gaussian RBF kernel to the metric induced by a graph kernel. In doing so, we find that simple baselines become competitive after this transformation on some datasets. Moreover, we study the extent to which existing graph kernels agree in their predictions (and prediction errors) and obtain a data-driven categorization of kernels as result. Finally, based on our experimental results, we derive a practitioner’s guide to kernel-based graph classification.
|
|
| 2. |
- Oettershagen, Lutz, et al.
(författare)
-
A Higher-Order Temporal H-Index for Evolving Networks
- 2023
-
Ingår i: KDD 2023. - : Association for Computing Machinery (ACM). ; , s. 1770-1782
-
Konferensbidrag (refereegranskat)abstract
- The H-index of a node in a static network is the maximum value h such that at least h of its neighbors have a degree of at least h. Recently, a generalized version, the n-th order H-index, was introduced, allowing to relate degree centrality, H-index, and the k-core of a node. We extend the n-th order H-index to temporal networks and define corresponding temporal centrality measures and temporal core decompositions. Our n-th order temporal H-index respects the reachability in temporal networks leading to node rankings, which reflect the importance of nodes in spreading processes. We derive natural decompositions of temporal networks into subgraphs with strong temporal coherence. We analyze a recursive computation scheme and develop a highly scalable streaming algorithm. Our experimental evaluation demonstrates the efficiency of our algorithms and the conceptional validity of our approach. Specifically, we show that the n-th order temporal H-index is a strong heuristic for identifying possible super-spreaders in evolving social networks and detects temporally well-connected components.
|
|
