Affiliations: School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA, USA
Correspondence:
[*]
Corresponding author: Lawrence B. Holder, School of Electrical Engineering and Computer Science, Washington State University, Box 642752, Pullman, WA 99164, USA. E-mail:holder@wsu.edu
Abstract: With the emergence of networked data, graph classification has received considerable interest during the past years. Most approaches to graph classification focus on designing effective kernels to compute similarities for static graphs. However, they become computationally intractable in terms of time and space when a graph is presented in an incremental fashion with continuous updates, i.e., insertions of nodes and edges. In this paper, we examine the problem of classification in large-scale and incrementally changing graphs. We propose a framework combining an incremental support vector machine (SVM) with the Weisfeiler-Lehman (W-L) graph kernel. By retaining the support vectors from each learning step, the classification model is incrementally updated whenever new changes are made to the graph. We design an entropy-based subgraph extraction strategy, that selects informative neighbor nodes and discards those with less discriminative power, to facilitate the classification of nodes in a dynamic network. We validate the advantages of our learning techniques by conducting an empirical evaluation on several large-scale real-world graph datasets in comparison with other graph classification methods. The experimental results also validate the benefits of our subgraph extraction method when combined with the incremental learning techniques.
