*WINNER* An Approach For Concept Drift Detection in a Graph Stream Using a Discriminative Subgraph

Abstract

Graph mining has attracted considerable research interest recently with the emergence of complex networks like social media, sensor networks, and the world wide web. In a streaming scenario, the concept to be learned might change over time. While there has been considerable research done for detecting concept drift in traditional data streams, little work has been done on addressing concept drift in data represented as a graph. We propose a novel unsupervised concept-drift detection method on graph streams. The methodology starts by discovering discriminative subgraphs for each graph in the stream. We then compute the entropy of the window based on the distribution of discriminative subgraphs with respect to the graphs and then use the direct density-ratio estimation approach for detecting concept drift in the series of entropy values obtained by moving one step forward in the sliding window. The usefulness of the proposed method is demonstrated through experiments using artificial and real-world datasets and its performance is evaluated by comparing against related baseline methods.