Frequent Subgraph Mining Over Dynamic Graphs

Abstract

Frequent subgraph mining (FSM) is an essential and challenging graph mining task used in several applications. Modern applications employ evolving graphs, so FSM is more challenging with evolving graphs due to the streaming nature of the input, and the exponential time complexity of the algorithms. Sampling schemes are used if approximate results serve the purpose. This thesis introduces three approximate frequent subgraph mining algorithms in evolving graphs. those algorithms use novel controlled reservoir sampling. A sample reservoir of the evolving graph and an auxiliary heap reservoir data structure are kept together in a fixed sized reservoir. When the whole reservoir is full, and space has required the edges of lower degree or higher nodes are deleted. This selection is done by utilizing the heap data structure as a heap reservoir, which keeps the node degrees. By keeping the edges of higher degree nodes in the sample reservoir, accuracy is maximized without sacrificing time and space, in contrast, keeping the edges of lower degree nodes in the sample reservoir, accuracy is minimized with higher time and space. The first algorithm is Controlled Reservoir Sampling with Unlimited heap size (UCRS), where the used heap reservoir size is unlimited. The second algorithm is Controlled Reservoir Sampling with Limited heap size (LCRS). It is a modified version of UCRS, but the heap reservoir size is limited, as a result; sample reservoir size in the whole reservoir increases since the total number of nodes dedicated for the whole reservoir includes the nodes of the heap reservoir also. The third algorithm is Maximum Controlled Reservoir Sampling (MCRS). It is a modified version of UCRS, but the candidate edge for deletion is an edge with maximum node degrees. Experimental evaluations to measure scalability and recall performances of the three algorithms in comparison to state of art algorithms are performed on dense and sparse evolving graphs. Findings show that UCRS and LCRS algorithms are scalable and achieve better recall than edge based reservoir algorithms. LCRS achieves the best recall in comparison to edge or subgraph based reservoir algorithms. MCRS has the worst speed-up and recall among the other proposed and competitor algorithms.

Sık alt çizgeler madenciliği bir çok veri madenciliği uygulaması için temel ve zorlu bir iştir. Modern uygulamalar devingen çizgelerle çalışmakta olup, girdilerindeki veri akışı, sık alt çizge madenciliği algoritmalarının karmaşıklığını arttırmaktadır. Yaklaşık sonuçların yeterli olduğu durumlarda örneklemeye dayalı yaklaşımlar kullanılmaktadır. Bu tez kapsamında üç adet yaklaşık sık alt çizge madenciliği algoritması önerilmektedir. Önerilen algoritmalarda yenilikçi olarak, kontrollü depolama ile örneklem oluşturma yaklaşımı kullanılmıştır. Devingen çizgeye ilişkin örneklem sabit boyutlu depoda tutulmakta ve yardımcı bir yığın veri yapısı kullanılmaktadır. Bu yığın veri yapısında depodaki çizge düğümlerinin bağlantı dereceleri tutulmaktadır. Sabit boyutlu depo dolduğunda ve yeni alan gereksinimi ortaya çıktığında bu depodan çizgenin en düşük dereceli düğümleri çıkarılmaktadır. Devingen çizge örneklemini tutan sabit depoda yüksek dereceli düğümlerin kalması sağlanarak sonuçlardaki doğruluk, yer ve zaman maliyetini artırmadan yükseltebilmektedir. İlk olarak limitsiz boyutlu kontrollü depo örneklemesine dayalı “Controlled Reservoir Sampling with Unlimited heap size (UCRS)” algoritması önerilmiştir; adından da anlaşılacağı üzere kullanılan yardımcı yığının boyutu kısıtlanmamıştır. İkinci algoritma “Controlled Reservoir Sampling with Limited heap size (LCRS)” da büyüyen depo ile büyüyen yığının boyutuna sınır getirilmektedir. Üçüncü algoritma “Maximum Controlled Reservoir Sampling (MCRS)” ilk algoritmaya benzemektedir; yığın boyutu sınırlandırılmamıştır ancak depodan düğüm silmek gerektiğinde en düşük dereceli düğüm yerine en yüksek dereceli düğüm çıkarılmaktadır. Her üç algoritmanın başarım değerlendirmeleri zaman, ölçeklenebilirlik ve doğruluk ölçütleri ile yapılmıştır. Başarım değerlendirmelerinde önerilen algoritmalar iki güncel rakip algoritma ile yoğun ve seyrek veri setleri üzerinde karşılaştırılmıştır. Bulgular UCRS ve LCRS algorithmalarının ölçeklenebilir olduğunu, rakip kenar tabanlı algoritmadan daha doğru sonuçlar verdiğini göstermiştir. LCRS tüm rakip algoritmalardan daha iyi başarım elde etmiştir. MCRS algoritmasının sonuçları tüm algoritmalar arasında en kötüdür.