Frequent subgraph mining over dynamic graphs

Abstract

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 artmadan yükseltilebilmektedir. İ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 en 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 seyrek veri setlerinde 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.

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. Sample of the evolving graph and an auxiliary heap data structure is kept in a fixed sized reservoir. When the reservoir is full, and space is required the edges of lower degree or higher nodes are deleted. This selection is done by utilizing the heap data structure in the reservoir, which keeps the node degrees. By keeping the edges of higher degree nodes in the reservoir, accuracy is maximized without sacrificing time and space, in contrast, keeping the edges of higher degree nodes in the reservoir, accuracy is minimized with higher time and space. First algorithm is Controlled Reservoir Sampling with Unlimited heap size (UCRS), where the used heap size is unlimited. Second algorithm is Controlled Reservoir Sampling with Limited heap size (LCRS). It is a modified version of UCRS, but the heap size is limited, as a result; sample size in the reservoir increases since the total number of nodes dedicated for the reservoir includes the nodes of the heap also. 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 on sparse datasets in comparison to edge or subgraph based reservoir algorithms. MCRS has the worst speed-up and recall among the other proposed and competitor algorithms.