Geri Dön

Unified anomaly detection in static graphs using randomized adversarial network

Statik çizgelerde rastgeleleştirilmiş saldırgan ağ kullanarak bütünleşik anomali tespiti

PDF İndir

  1. Tez No: 866233
  2. Yazar: AHMET TÜZEN
  3. Danışmanlar: DOÇ. DR. YUSUF YASLAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 131

Özet

Anomaliler ait oldukları kümenin geri kalanına göre büyük oranda farklılık gösteren, nadir görülen oluşumlardır. Bu tanımda üç önemli nokta vardır. Bunlardan ilki anomalilerin ender görülmesidir. İkinci nokta ise anomalilerin etkili olmasıdır. Bu nadir görülen oluşumlar, o kadar etkilidirler ki, anomalilerin yanlış bir şekilde etiketlenmesi geri dönüşü olmayan sonuçlar doğurabilmektedir. Son önemli nokta ise anomalilerin ait oldukları kümede anlamlı olmasıdır. Bir veri kümesinde anomali olarak değerlendirilebilecek oluşum, başka bir kümede sıradan bir olay olabilir. Bu üç anahtar noktadan yola çıkarak, anomalileri göz ardı ederek çalışan bir makine öğrenmesi modeli başarısız olacaktır. Bu yüzden anomalilerin tespiti ve gerekli olduğu durumlarda elenmesi son derece önemlidir. Bu problem, anomali tespiti olarak bilinmektedir. Anomali tespiti problemi birçok yönden zorlayıcıdır. Bu nadir olayların tespitini yapabilecek bir modeli eğitmek de zorludur. Birçok senaryoda anomalilerin, normal oluşumlara oranı binde veya on binde bir seviyelerindedir. Veri kümeleri de genellikle anomalilerin etiketleri bulunmaz veya bir parçası bulunur. Ayrıca, anomalilerin öngörülemez bir yapısı vardır ve bir modelden anomalileri yorumlayabilmesini beklemek gerçekçi olmayacaktır. Çizgeler veri gösterimi içi kullanılan güçlü veri yapılarıdır. Güçlü olmalarının nedeni, veri kümesindeki noktaları sadece bireysel olarak ele almayıp, noktaların birbirleriyle olan ilişkilerini de gösterebilmesidir. Çizgelerde veri noktaları düğüm ve kenarlar olarak gösterilmektedir. Bunlara ek olarak veri noktalarının özellikleri de bireysel olarak depolanabilir. Bu ileri seviye yapı, anomalilerin öngörülemezliğini konusunda yardımcı olabilecek bir yapı olma potansiyeli vardır. Anomaliler, çizge yapısında da ortaya çıkmaktadır. Literatürde bu anomaliler, çizge anomalisi olarak geçer. Çizge anomalilerin tespiti de çizge anomali tespiti olarak bilinmektedir. Bu tezde, statik çizgeler olarak bilinen, zamanla değişimi olmayan çizgelerde anomali tespiti üzerine odaklanılmıştır. Ancak çizgelerin anomali tespiti için kullanılması yeni problemler doğurmaktadır. Çizgelerdeki veriler muazzam boyuttaki verilerde tutulur. Bu büyüklükteki verilerle çalışmak da bilinen bir problemdir. Ayrıca çizgelerde anomaliler, anormal düğümler, anormal kenarlar ya da anormal düğümlerin ve kenarların bir araya getirdiği anormal alt gruplar olarak ortaya çıkar. Statik çizgelerdeki bu üç tip anomalilerinde tespitini aynı anda yapabilecek bir model önermek de zorlu bir süreçtir. Belirtilen anomalilerin tespitine başlamadan önce, çizgelerden verilerin nasıl alınacağı önemli bir adımdır. Bir düğümü tek başına değerlendirmek, çizge yapısını hiç kullanmadan direk ilerlemek olacaktır ve veriler boş yere uzun dizilerde tutulmuş olacaktır. Düğümün komşularını da büyük oranlarda kullanmak gereksiz bir karmaşıklık yaratabilecektir. Bu iki uç senaryo arasında takası dengelemek için çizge temsili öğrenme çalışılmıştır. Bu çalışmada, düğümün komşularını katmanlar olarak kullanarak yapay sinir ağı tasarlanmıştır ve böylece çizgeden daha iyi veri öğrenimi sağlanmıştır. Buna ek olarak, çizge sinir ağının kaç katmanda nasıl sonuç verdiği, bir düğümün komşularının nasıl kullanılacağına yönelik deneyler de yapılmıştır. Ayrıca, topluluk atlaması adı verilen yöntem geliştirilerek, bir düğümün rasgele komşularından ziyade kendisi ile topluluk oluşturan komşuları ile sinir ağı kurularak yapının başarımı arttırılmıştır. Bu özgün katkıya ek olarak, çalışma sonucunda tüm komşuların kullanılmasının karmaşıklığı arttırmasına rağmen performansı kötüleştirdiği tespit edilerek önemli bir sonuç elde edilmiştir. Böylece, hem öğrenilmesi gereken parametre sayısı azaltılmış, hem de çizge yapısından daha efektif bir şekilde veri çıkarımı yapılmıştır. Ek olarak, potansiyel komşular arasında rasgele seçim yapmak, uzun süren eğitimler konusunda bile modelin ezberlemesinin önüne geçmiştir. Bu yapı temel bir yapı olarak önerilmiştir ve farklı boyutlarda, farklı tiplerde çizgelere uygulanarak birçok senaryoda çalıştığı kanıtlanmıştır. Çizgeler üzerinde etkili bir öğrenim başarılınca, anomali tespiti problemi üzerinde, anormal düğüm tespiti ile çalışılmaya başlanmıştır. Çizge anomali tespitinin belirtilen zorluklarından ötürü daha ileri yapı olan, saldırgan öğrenme kullanılmıştır. Saldırgan otokodlayıcılar, ayrıştırıcı ve üretici olarak iki ana bileşenden oluşur. Her iki bileşenin de ortak parçası olan kodlayıcı hem çizge hem de sahte çizge girdilerini alarak bunları düşük boyutlu gösterimlere sıkıştırır. Daha sonra üretici bu iki gösterimi de alıp orijinal çizgeyi oluşturmaya çalışmaktadır. Üretecin amacı, sahte girdi olsa bile doğru bir şekilde çizgeyi tekrar oluşturabilmektir. Ayrıştırıcı ise, düşük boyutlu gösterimlerin hangisinin gerçek, hangisinin sahte olduğunu ayrıştırmaya çalışmaktadır. Her iki yapı da birleştirildiğinde, üretici o kadar gerçekçi sahte veriler üretmelidir ki, ayrıştırıcı kaynakları belirleyememeli; ayrıştırıcı da ne kadar gerçekçi veri gelse de hangisinin sahte hangisinin gerçek olduğunu söyleyebilmelidir. Bu saldırgan öğrenme yapıda, anomalilerin nadir olmasını iyileştirmesi amaçlanmaktadır. Öyle ki, sahte yapılar anomalilere benzetilerek, her gerçek yapının karşılaştırıldığı bir durum ortaya koymaktadır. Tezde saldırgan öğrenme ile kurulan sisteme ARNAD adı verilmiştir. ARNAD yukarıda belirtilen saldırgan öğrenme ile eğitilir ve sonrasında üreteç ve ayrıştırıcı ile her düğüm için anormallik puanı ataması yapar. Bu yapı, sadece çizgenin bağlamsal yapısına uyarlanabilse de girdi olarak özellik matrisini de alabilmektedir. Sonuç olarak her bir düğüme dört adet anormallik skoru atanır. Yapılan deneyler sonucu ARNAD, benzeri yapılara göre oldukça iyi sonuçlar göstermiştir. Ancak bu sistemin eksiklikleri vardır. ARNAD'ın ayrıştırıcı bileşeni, üreteci bileşenine göre büyük bir farkla iyi performans göstermektedir. Ayrıca özellik matrisi de komşuluk matrisine karşı üstün gelmiştir. Bunlara ek olarak, her bir düğüm için tüm kaynakları ayırmak çok mantıklı olmayan bir yaklaşımdır. Tezin ileri kısımlarında bu eksiklikler giderilmeye çalışılacaktır. İlk olarak sistemi besleyen rasgele oluşturulan sahte çizgeler değiştirilmiştir. Çizge bozum yöntemleri kullanılarak, bu rastgelelik yerine kontrollü rastgelelik elde etmek amaçlanmıştır. Bu yaklaşım, komşuluk matrisi ile kullanılan yapıları ciddi bir oranda iyileştirmiştir. Bir diğer zayıflık olan tüm kaynakların sadece anormal düğüm tespiti için ayrılmasında farklı bir yöntem izlenilmeye karar verilmiştir. Üretecinin çıktısı gerçeğe yakın çizge olacağı için, bu yapının çıktısı anormal kenar tespitinde kullanılabilir. Böylece ayrıştırıcı anormal düğüm tespiti, üretici de anormal kenar tespiti için ayrılmış bir şekilde her iki problemi de tek bir seferde çözebilecek bir model önerilmiştir. Yapılan deneyler sonucu üretici anormal kenar tespitinde çok iyi çıktılar vermiştir. Statik çizgelerdeki son anomali şekli anormal alt gruplardır. Bu anormalliklerin tespiti için şöyle bir yaklaşım uygulanmıştır: anormal alt gruplar birbirlerine oldukça benzerdir. Bu benzerlikler kodlayıcı çıktısı olan düşük boyutlu çıktılarda da benzer olacaktır. Normal veri noktaları ise kodlayıcı çıktısında düzenli veya rastgele dağılmaktadır. Böylece, düşük boyuttaki gösterimlere kümele algoritmaları uygulanarak anormal gruplar tespit edilmektedir. Şimdiye kadar ilerlenen yapıda, kodlayıcı çıktısı kod çözücüye ve ayrıştırıcı çıktısına iletilmek dışında bir yerde kullanılmamaktadır. Modelde, kodlayıcı çıktısı üzerinde OPTICS olarak bilinen kümeleme algoritması kullanılarak, model anormal alt grupları da tespit edecek bir duruma getirilmiştir. Bu yapı anormal grup tespitinde de oldukça iyi sonuçlar elde etmiştir. Özetle bu tezde önerilen yapı, DeGAN, statik çizge tespitlerinde tüm anomalileri tespit edebildiği için bütünleşik olan bir yaklaşımdır. Tek bir yapıda bütünleşik anomali tespiti yapabilmek büyük bir başarıdır. Böylelikle literatüre hem anomali tespitinde hem de çizge öğrenmesinde büyük ve özgün katkılar yapılmıştır.

Özet (Çeviri)

Anomalies are rare instances that shows significantly different behaviors than the rest of the sample. Even though anomalies appear infrequently, they are highly impactful, such that any machine learning model that does not consider the presence of the anomalies will likely fail. Therefore, it is extremely important to detect anomalies and, if necessary, eliminate them. This task is known as the anomaly detection problem. Graphs are a data representation tool that not only represent the individual information of data instances but also their relationships. The anomalies are also present in graph data structures, and they are referred to as graph anomalies. There are more possibilities for extracting information from graphs, which is useful because it enables the learning of the complex nature of the anomalies. Spotting the anomalies in graph data structure is known as graph anomaly detection. This thesis focuses on graph anomaly detection in a static graph. Graph anomaly detection is a challenging task due to the characteristics of the anomalies and their existence in different forms within graphs. To overcome these challenges, the first aspect that is studied is how to extract more data from the graph, and a novel contribution is made in this are with the introduction of a new neighbor selection criteria named community-hop. The outcome is a model that uses fewer parameters for learning and is resistant to overfitting. Additionally, this work has been proven to be effective in various types of graphs. After successfully achieving efficient data extraction from the graph, the next aspect investigated is the anomalous node detection in graphs. To develop a reliable anomalous node detector, an adversarial learning-based approach is adopted. The adversarial autoencoder is capable of learning the graphs in such a way that four outcomes can be assigned to a single node. This framework, named ARNAD, and has demonstrated excellent performance and competitiveness compared to similar state-of-the-art models. The discriminator component of the ARNAD outperformed the generator component in delegating anomaly scores. To improve the performance of the generator, adversarial learning is combined with graph decomposition. Instead of relying on randomness and noise for generating fake sources, utilizing graph decomposition significantly enhances the performance by a large margin. Another weakness of ARNAD is that it focuses solely on the task of anomalous node detection, neglecting the potential for anomalous edge detection. Since the generator in ARNAD already is already capable of reconstructing the connectivity pattern of the graph, it can readily be utilized for the task of anomalous edge detection as well. This approach has achieved high performance in the anomaly detection task, enabling the model to effectively detect both anomalous nodes and edges. The final aspect of static graph anomaly detection is the anomalous sub-graph detection. For this task, the approach of the embeddings of the suspicious sub-graphs would be similar in a latent space is adopted. In the previous model, the output of the encoder is primarily utilized for transferring embeddings to the decoder and discriminator components. However, for achieving anomalous sub-graph detection, the embedding of the graph is further processed using the OPTICS clustering method. This combination of methods and approach has demonstrated successful results. In summary, this thesis proposes a unified framework called DeGAN for detecting static graph anomalies. DeGAN is an advanced model capable of detecting all types of anomalies within a single framework. As a result, this thesis makes significant and novel contributions to the literature in multiple aspects related to graph representation learning and graph anomaly detection.

Benzer Tezler

  1. Tez No

    745431

    Crowd counting, localization and anomaly detection with convLSTM based CNN using synthetic images

    Evrişimli uzun-kısa süreli hafıza tabanlı evrişimsel sinir ağları ile sentetik görüntüler kullanarak kalabalık sayımı, lokalizasyonu ve anomali tespiti

    MUHAMMET FURKAN COŞKUN

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. GÖZDE AKAR

  2. Tez No

    392809

    DDoS saldırılarına karşı istatistiksel koruma yaklaşımı

    A statistical approach to SIP-based distributed denial of service attacks

    BAHAR UĞURDOĞAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBahçeşehir Üniversitesi

    Uygulamalı Matematik Ana Bilim Dalı

    YRD. DOÇ. DR. SELÇUK BAKTIR

  3. Tez No

    33902

    Büyük birleşme teorilerinde anomali hesapları

    Başlık çevirisi yok

    METİN BEDİR

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Fizik ve Fizik MühendisliğiÇukurova Üniversitesi

    Fizik Ana Bilim Dalı

    PROF. DR. MEHMET KOCA

  4. Tez No

    836734

    RbA: Segmenting unknown regions rejected by all using mask classifiers

    RbA: Maske sınıflandırıcıları kullanarak hepsi tarafından reddedilen bilinmeyen bölgeleri segmentlere ayırmak

    NAZIR NAYAL

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. FATMA GÜNEY

  5. Tez No

    495901

    Unified threat management (UTM): A comparative study

    Birleştirilmiş tehdit yönetimi (BTY): Karşılaştırmalı bir çalışma

    AHMAD AYID AHMAD AHMAD

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÇankaya Üniversitesi

    Matematik Ana Bilim Dalı

    YRD. DOÇ. DR. SİBEL TARIYAN ÖZYER

Geri Dön