Grafik Bazlı Anomali Tespiti: Kapsamlı Bir Özet

Bu yazı, Özellikle, veri madenciliği, güvenlik ve spam/fraud incelemeleri başta olmak üzere pek çok alanda yaygınlaşan Anomali tespiti probleminde, grafik (veya ağ) bazlı yöntemlerin önemini ve pratik uygulamalarını ortaya koymaktadır.

1. Arka Plan ve Giriş

Veri analizi ve makine öğrenmesi bağlamında Anomali tespiti, “veri kümesindeki çoğunluktan önemli ölçüde sapan veya beklenen davranışa uymayan örnekleri tanımlama” şeklinde ifade edilebilir. Bununla birlikte, gerçek hayatta bu “örnekler” sadece birer tekil nokta (örneğin çok boyutlu bir vektör) olarak değil, sıklıkla birbirleriyle ilişkili objeler olarak karşımıza çıkar. Bu ilişkileri yakalamanın en güçlü yollarından biri, veriyi bir grafik şeklinde temsil etmektir.

Grafik temsili, veri objelerinin (düğümlerin) arasındaki uzun menzilli korelasyonları (kenarlar/bağlantılar) kodlar. Böylece, düğümler arasında gözlemlenen anomaliler (beklenmedik bağlantılar, alt yapıların normalden sapması vb.) makine öğrenmesi, istatistik ve veri madenciliği yaklaşımlarıyla daha kolay veya daha isabetli şekilde bulunabilir. Dahası, bu tür grafik temelli Anomali tespiti yöntemleri, pek çok alanda (siber güvenlik, finans, sosyal medya vb.) işe yarar çözümler sunar. Çoğu zaman bir düğümün veya alt grafın anomaliliği, onun bağlamından (yani ilişkili olduğu komşulardan) bağımsız düşünülemez.

Makalenin temel motivasyonları şu şekildedir:

• Veri objeleri arasındaki bağımlılıklar (inter-dependencies): Birçok problemde, veri noktaları bağımsız değildir; birbirlerini etkileyen uzun menzilli korelasyonlar söz konusudur (örneğin bir sosyal ağda bir kişinin yakın arkadaşları arasında benzer davranış kalıpları). Grafikler, bu bağımlılıkları doğal biçimde gösterir.
• İfade gücü (expressiveness): Grafik yapıları, sadece düğüm özelliklerini değil, aynı zamanda kenarlara ait özellikleri (ilişki türleri, etiketler vb.) de kodlayarak çok zengin bir temsil sunar. Bu, Anomali tespiti için önemli ipuçları sağlayabilir.
• Güçlü ve saldırıya dirençli yapılar: Özellikle aldatma ve hile (fraud) durumlarında, saldırganların veri noktasının lokal özelliklerini değiştirmesi nispeten kolay olabilirken, tüm ağın küresel yapısına uygun biçimde “sahte” davranış sergilemesi zordur. Bu durum, grafik bazlı yöntemleri güvenlik açısından daha güçlü kılar.

Bir veri kümesinin grafik temsili yapılırken düğümler, genelde “varlık” (örneğin kullanıcılar, cihazlar, finansal hesaplar) olarak, kenarlar ise “ilişki” veya “etkileşim” (örneğin kullanıcılar arasındaki mesajlaşmalar, finansal hareketler, vb.) şeklinde tanımlanır. Makaledeki odak, bu temsil şekliyle Anomali tespiti süreçlerinin nasıl ele alındığıdır. Ayrıca, tespit edilmiş anomalilerin açıklanması (explanation veya sense-making) yani “anomalinin neden oluştuğu” veya “nasıl açıklanabileceği” soruları da yanıtlanmaya çalışılır.

2. Statik Grafiklerde Anomali Tespiti

Statik grafikler, zaman boyutu veya ek güncelleme olmaksızın tek seferde elde edilen “anlık” (snapshot) bir grafik yapısıdır. Bu tür grafiklerde Anomali tespiti genelde düğüm, kenar ve alt yapı (örneğin alt grafik) düzeyinde yapılabilir. Sınıflandırma amaçlı yöntemler (örneğin denetimli veya yarı-denetimli öğrenme) ya da tamamen denetimsiz (örneğin “en beklenmedik” veya “en seyrek” yapıları arayan) yöntemlerle geliştirilebilir.

Makalenin bu kısmında, iki ana yaklaşımdan söz edilmektedir:

1. Düğüm-kenar özelliklerini kullanan (feature-based) yöntemler: Grafikten çeşitli öznitelikler (in/ out derece, üçgen sayısı, yerel kümeleşme katsayısı, merkeziyet ölçüleri, vb.) çıkarılarak, elde edilen vektörler üzerinde geleneksel bir “nokta bazlı” anomali analizi yapılır Böylece, düğümün veya alt grafın “normal” dağılımdan ne kadar saptığı ölçülerek Anomali tespiti skoru verilebilir.
2. Topluluk (community) veya küme (cluster) temelli yöntemler: Grafikteki alt toplulukların tespiti sonrasında, topluluk sınırlarını aşan veya içinde aşırı farklı davranış gösteren düğüm/kenarlar anormal olarak işaretlenir. Örneğin SCAN ve benzeri algoritmalar, bir düğümü “köprü” veya “hub” rolünde bulduğunda anormal sınıfına ekleyebilir.

Bu yöntemler, düz (plain) grafiklerde geçerli olduğu gibi, ek düğüm veya kenar niteliklerinin (atribütlerin) bulunduğu durumlarda (attributed graphs) da çalışabilir. Attributed grafiklerde, “düğümün komşularıyla nitelik açısından benzerliği” veya “bir topluluktaki çoğunluğun nitelik değerlerine uymayan düğüm” gibi ek kriterler eklenir.

2.1 Yapı Temelli Yaklaşım (Structure-based)

Yapı temelli yaklaşımlar, sık rastlanan alt yapılar ile sıklıkla gözlemlenmeyen (seyrek veya modifikasyona uğramış) alt yapıları kıyaslayarak çalışır. Örneğin, eğer grafikte çokça gözlemlenen bir desen (substructure) varsa, bu desenin “ufak değişiklikle taklit edilmesi” potansiyel bir aldatma girişimini (fraud) temsil edebilir. Subdue (Noble ve Cook) bu bakış açısıyla “en iyi sık alt yapılar”ı bulur ve bunların varyantlarını (az rastlananları) anomali olarak tanımlar.

2.2 Topluluk Temelli Yaklaşım (Community-based)

Topluluk temelli yaklaşımlar, düğümlerin benzer yapısal özelliklerle bir araya geldiği kümeleri (community) bulur. Bir düğümün kendi topluluğu içinde aşırı uçta farklı niteliklere veya bağlanma örüntüsüne sahip olması durumunda anomali olabileceği kabul edilir. Örneğin CODA, hem toplulukları hem de topluluk içi “farklı” düğümleri aynı anda bulur. Böylece, hem normal yapıyı (topluluk dağılımını) hem de normalden sapan noktaları (topluluk anomalileri) yakalamayı hedefler.

3. Dinamik Grafiklerde Olay (Event) ve Anomali Tespiti

Birçok gerçek dünya sistemi (örneğin bilgisayar ağları, sosyal ağlar, telekom ağları) zaman içinde değişen grafikler şeklinde modellenir. Dinamik grafik (veya zaman serisi halinde akan ağ verisi) üzerinde Anomali tespiti, “hangi zaman diliminde veya hangi güncellemelerde önemli bir değişim olduğunu” saptamaya çalışır. Bu değişimler, beklenmeyen bir “olay” (event) olarak nitelendirilebilir.

1. Özellik (feature) bazlı: Her bir zaman anında, grafikten tek bir özet (örneğin düğüm-kenar sayısı, ortalama derece, spektral değerler vb.) çıkarılır. Ardından, bu özetler arasındaki benzerlik veya farklar izlenerek, ani bir değişim saptandığında anomali ilan edilir.
2. Ayrıştırma (decomposition) bazlı: Matris veya tensör ayrıştırması (SVD, PCA, CUR, vb.) yardımıyla her bir zaman anının “düşük boyutlu temsili” elde edilir. Ardından, yeniden kurulum (reconstruction) hatasındaki (veya benzer metriklerdeki) ani sıçramalar, anomali/olay işareti olarak değerlendirilir.
3. Topluluk/küme bazlı: Zaman içinde toplulukların nasıl değiştiğine bakarak, topluluklar arası etkileşimin aniden artması veya belirli toplulukların ayrışması gibi durumlar anomali olabilir.
4. Pencere (window) bazlı: Kimi yöntemler, zaman serisini sabit veya dinamik bir pencere ile inceler. Örneğin son w adım içindeki “normal model” oluşturulur ve güncel zaman adımı ile karşılaştırılır. Büyük bir sapma tespit edilirse olay/ anomali ilan edilir (örnek: scan statistics, NetSpot).

Bu dinamik senaryo, gerçek zamanlı (real-time) Anomali tespiti için de önemlidir: bir bilgisayar ağına saldırı anını hemen fark etmek veya finans piyasasında manipülasyon olduğunda gecikmeden tespit edebilmek gibi.

4. Anomalilerin Açıklanması ve Anlama (Sense-making)

Teknik olarak, bir Anomali tespiti algoritması “hangi düğüm/ kenar/ alt yapı anormal” sorusuna cevap verse de, pratikte bu sonucun nedenini veya nasıl bir ilişkiler bütününden kaynaklandığını anlamak da kritik önem taşır. Makalede, bu hedefe ulaşmak için iki ana yaklaşım öne çıkar:

1. Yorumlanabilirlik sağlama: Matrissel yaklaşımlarda (örneğin NrMF) “rezidüel matrisin” negatif olmayan ögeleri kullanılarak, hangi kenarların “ekstra” (fazladan) olduğu veya hangi düğümlerin “aşırı” bağlantılara sahip olduğu kolayca görülebilir. NMF tabanlı yöntemler, örneğin “kümeler”in gerçek sütun/ satırlardan oluşması sayesinde de daha açık bir yorum sağlar.
2. Etkileşimli grafik sorgulama (interactive graph querying): Bir küme anormal düğüm tespit edildikten sonra, bu düğümlerin nasıl bir ilişkide olduğunu, alt yapı düzeyinde hangi yollarla bağlandığını hızlı ve özet bir şekilde görebilmek için ek araçlara başvurmak gerekebilir (örneğin Center-Piece Subgraphs, Dot2Dot). Bu yaklaşım, anormalliklerin aynı kaynaktan mı, yoksa farklı alt kümelerde mi ortaya çıktığını anlamakta kullanışlıdır.

5. Uygulamalar: Farklı Alanlarda Grafik Bazlı Anomali Tespiti

Makalede, çeşitli gerçek dünya senaryosunda Anomali tespiti için grafik temelli tekniklerin başarıyla kullanıldığı gösterilmektedir. Burada, en çok vurgulanan bazı uygulamalar aşağıda listelenmiştir.

5.1 Telekomünikasyon Ağlarında Anomaliler

Abonelik sahtekarlığı (subscription fraud) gibi durumlar, telekom ağlarında büyük zararlara yol açar. Grafikte düğümler abonelik hesapları, kenarlar ise bu hesaplar arası çağrılar/iletişim olarak ele alınır.Her bir hesabın en çok etkileşimde olduğu alt çevresini takip eder. Eğer iki hesap COI bakımından oldukça örtüşüyorsa ve içlerinden biri dolandırıcı olarak etiketlenmişse, diğeri de yüksek olasılıkla dolandırıcıdır.

5.2 Açık Artırma Sitelerinde Sahtekarlık

Online müzayede (auction) platformlarında sıklıkla “non-delivery” sahtekarlıkları görülür. Düğümler “satıcı, alıcı, ara hesap” şeklinde ayrışırken, kenarlar işlem kayıtlarını gösterir. Relational Markov network (RMN) ve benzeri yapılarla “accomplice” ve “fraudster” rolleri keşfedilmiş; normal hesapların lokal özellikleri taklit edilse de genel ağ yapısında “anormal” kaldıkları anlaşılmıştır.

5.3 Muhasebe (Accounting) Ağlarında Anomaliler

Muhasebe kayıtlarında veya finansal tablolarda usulsüzlükler “yüksek riskli” hesaplar şeklinde sınıflandırılmak istenir. Relational yaklaşım, bir hesabın komşularının da risk durumunu dikkate alarak tahmin yapar. Böylece, tekil sinyallerin yetersiz kaldığı durumlarda, hesaplar arası ilişkiler yardımıyla daha yüksek tespit oranları elde edilir.

5.4 Menkul Kıymetler (Securities) Dolandırıcılığı

Menkul kıymet brokerlarının geçmiş bağlantılarını (sosyal, profesyonel, kurumsal) bir ağ halinde gösterip, kimlerin sahte işlere meyilli olduğunu tahminlemek için relational dependency networks kullanmıştır. “Word-of-mouth” ile kötü niyetin yayılması veya geçmişte aynı ortamı paylaşmış brokerların benzer şekilde suça bulaşması gibi gerçekçi durumlar grafik modelleriyle etkili biçimde yakalanabilmiştir.

5.5 Kullanıcı Yorumları ve İncelemelerde (Opinion Spam) Anomaliler

Amazon, Yelp, TripAdvisor gibi platformlarda ürün veya mekanlar hakkında sahte yorumlar (fake reviews) yazarak haksız puan artışı veya rakiplerine düşüş yaşatmak oldukça yaygındır. Kullanıcı-ürün inceleme grafiğindeki düğüm ve kenarları kullanarak, “hype” veya “defame” spamlerini tespit edebilmektedir. Bu tür grafiklerde “kullanıcı –> ürün” bağlantısı aynı zamanda bir “beğeni veya düşük puan” sinyali içerebilir; böylece relational bir model, şüpheli davranışları diğer kullanıcı ve ürün etkileşimleriyle kıyaslayarak yakalar.

5.6 Finansal (Borsa) İşlem Ağlarında Dolandırıcılık

Li vd. (2010), bir grup yatırımcının hisseyi yapay şekilde “pump” edip sonra satma (dump) stratejisini, “blackhole” (aşırı hisse toplama) ve “volcano” (aniden yüksek hacimde hisse satma) kalıpları üzerinden açıklamıştır. Bu kalıplar, grafik üzerinde “bir alt kümenin içindeki yoğun yönlü işlemler” ve sonrasında “topluluk dışına doğru yüksek hacimli işlem” olarak görülür. Bu şekilde manipülasyon dedektifliği (manipulation detection) daha net yapılabilir.

5.7 Web Ağı: Spam ve Malware

Arama motoru sıralamasını haksız yere yükseltmeye çalışan Web spam sayfaları, grafikte “bağlantı referansları”nı manipüle eder. TrustRank (Gygyi vd.) ve Anti-TrustRank gibi yaklaşımlar, az sayıda güvenilen veya bilinen spam sayfadan başlayarak güven/distrust yayma (propagation) işlevi kullanır. Bu sayede, spam toplulukları “çapraz bağlantılar” ile saptanabilir. Benzer biçimde Wu vd. (2006), “hangi sayfa hangisine güveniyor” mantığını link analizle otomatize eder.

5.8 Sosyal Ağlarda Kötü Amaçlı Yazılım (Socware)

Facebook veya Twitter gibi platformlarda, zararlı linkler veya oltalama (phishing) mesajları yayan saldırganlar, “arkadaş” bağlantılarından faydalanır. Gao vd. (2012) gibi çalışmalar, profil benzerlikleri, mesaj içerik benzerlikleri ve grafiğe özgü merkeziyet ölçülerini birleştiren denetimli öğrenme yaklaşımıyla bu saldırıları tespit etmeye çalışır. Alternatif olarak, “yayılma” modeli incelenerek kimlerin “normal paylaşımlardan farklı” biçimde link dağıttığı anlaşılabilir.

5.9 Bilgisayar Ağlarında Saldırı ve İzinsiz Giriş (Intrusion Detection)

Dağıtık hizmet engelleme saldırıları (DDoS), port taraması, kimlik hırsızlığı vb. durumlar sıklıkla büyük ölçekli ağ üzerinde zaman içinde büyüyen grafiklerle izlenir. Bir IP adresinin normal dışı davranışı, sadece kendi trafiğini değil, o IP’nin ilişkili olduğu diğer düğümlerin (IP veya cihaz) davranışlarıyla da kıyaslanarak anlaşılabilir. Bu kapsamda, Idé ve Kashima (2004), zaman boyutunda ana özvektörleri takip ederken, Sun vd. (2008) benzer şekilde CMD (Compact Matrix Decomposition) yaklaşımlarıyla ağın tipik davranışını modeller ve ani sıçramaları alarm olarak yorumlar.

6. Özet ve Geleceğe Yönelik Açık Konular

Grafik bazlı Anomali tespiti, veri madenciliğinin en canlı ve uygulanabilir alanlarından biridir. Yüksek etkileşimli veri kümeleri (sosyal medya, finans, siber güvenlik, telekom vb.) göz önüne alındığında, grafikler uzun menzilli ilişkileri temsil ederken saldırılara veya anormal davranışlara karşı ciddi avantajlar sunar. Bununla birlikte, alanda hala çözülmemiş veya kısmen çalışılmış bazı konu başlıkları mevcuttur.

6.1 Teorik Araştırma Zorlukları

• Dinamik + Attribütlü Grafikler: Hem zaman boyutu hem de düğüm/kenar nitelikleri aynı anda işin içine girdiğinde, anomali tanımlamak ve yakalamak zorlaşır. Uygulamada böyle vakalar olsa da, literatürde yeterince kapsanmamıştır.
• Tarihçe ve İz (Trace) Bilgisi: Dinamik güncellemelerle gelen grafikte, bir kenarın kalkması veya eklenmesi “geçmişte o kenar/ilişki var mıydı” sorusunu yanıtsız bırakmaz. Tarihçe, anomali tespitinde ek sinyaller verebilir.
• Zaman penceresi seçimi: Birçok algoritma, “son w zaman birimi” üzerinden bir normal model çıkarmayı tercih eder. Bu w değerini veya dinamik aralıkları otomatik öğrenmek, farklı tip anormalliklerin (kısa süreli saldırı vs. uzun vadeli sapma) yakalanmasında kritik olabilir.
• Adversary robustness: Saldırganların, grafik bazlı algoritmaların “büyük resmi” bilmediklerini varsaymak avantajdır; ancak saldırganların kısıtlı bile olsa sosyal mühendislikle veya sistem hatalarıyla bu küresel görünüme ulaşması ihtimali değerlendirilmeli, “kırılması daha zor” modeller geliştirilmeli.
• Gerçek zamanlılık ve ölçeklenebilirlik: Büyük hacimli veri akışlarında (örneğin yüksek trafiğe sahip ağlar) anında tepki vermek istenebilir. Bu da O(|V|+|E|) gibi lineer, hatta alt lineer karmaşıklıkta algoritmaları gerektirebilir.

6.2 Pratik Araştırma Zorlukları

• Gerçek etiket eksikliği ve değerlendirme güçlüğü: Fraud tespiti gibi konularda “true label” toplamak güç ve maliyetlidir. Elde edilen sonuçların ne kadar iyi olduğu, çoğu zaman ek veri (örn. domain uzmanları) veya sentetik/anomali enjeksiyon yöntemleri ile test edilir.
• Grafik Kurulumu (Graph Construction) ve Çoklu Veri Kaynakları (Multi-Graph): Bazı durumlarda elimizdeki ham veriler nokta bazlı iken, hangi düğümleri oluşturacağımız ve hangi ilişkileri kenar olarak seçeceğimiz önemli bir tasarım tercihi haline gelir. Ayrıca birden fazla grafik (farklı ilişkiler) aynı anda kullanılarak “daha net” anomali sinyalleri yakalanabilir. Bu alan henüz çok yeni.
• Özellik Seçimi, Parametre Ayarı: Özellikle yarı-denetimli veya denetimli yaklaşımlarda hangi özelliklere ve parametrelere hassas olduğu belirsizdir. Her problemde farklı bir set optimum olabilir. Dolayısıyla, kullanıcıya rehberlik edecek “otomatik parametre seçimi” veya “otomatik özellik seçimi” yöntemleri geliştirilebilir.
• Atıf (Attribution) ve Yenilik (Novelty) Arasındaki Denge: Mevcut kurallarla açıklanabilen anormaller mi daha önemli yoksa bilinmeyen yeni tip anomaliler mi? Bir yandan açıklanabilirlik (explainable AI) istenirken, öte yandan da hiç bilinmeyen saldırı türlerini yakalamak kritiktir.

Temel fikir, veri nesnelerinin (düğümlerin) bağımsız olmadığı, aksine çoğunlukla uzun menzilli etkileşimlerle (kenarlarla) birbirine bağlı olduğu gerçeğidir. Grafik bazlı modeller, özellikle hile, spam, siber saldırı gibi vakalarda saldırganın küresel ağ yapısını manipüle etmesini zorlaştırarak daha güçlü bir savunma katmanı sunar.

Ayrıca, anormalliklerin sadece “hangisi anomalidir” sorusuna yanıt vermesi, pratikte çoğu zaman yeterli değildir; “neden, hangi alt yapı ilişkilerine bağlı olarak anormal” sorusunun da yanıtlanması (explanation, sense-making) kritik önem taşır. Bu amaçla makalede, düşük boyutlu ayrıştırma (NrMF gibi), alt topluluk veya komşu sorgusu (Center-Piece Subgraph, Dot2Dot vb.) yaklaşımlarıyla anomalinin insan gözünde net biçimde açıklanabilir duruma gelmesi hedeflenmektedir.

Bütün bu yöntemler incelendiğinde, grafik bazlı Anomali tespiti için kapsamlı bir çerçevenin oluştuğu görülür. Yine de zaman boyutu + atribütler + çoklu ilişkiler (multi-relational) gibi daha karmaşık senaryolarda halen araştırma yapılması gerekir. Teorik ve pratik zorluklar, alanda yeni modellerin ve algoritmaların geliştirilmesine kapı aralamaktadır. Gerçek dünya uygulamalarının çeşitliliği (finans, telekom, sosyal medya, siber güvenlik vb.) ve bu alanlarda toplanan veri miktarının sürekli artışı, grafik temelli yöntemlerin gelecek yıllarda daha da yaygın şekilde kullanılacağının işaretidir.

Özetle, “Graph based anomaly detection and description: a survey” makalesi, Anomali tespiti literatüründe grafiklerin gücünü ve çeşitliliğini ortaya koyan, aynı zamanda yorumlanabilirlik ve pratik uygulamalar bağlamında yol gösteren kapsamlı bir kaynak olma niteliğindedir.