Graf invaryantları ile güçlendirilmiş makine öğrenmesi algoritmaları
Machine learning algorithms enhanced with graph invariants
- Tez No: 1024803
- Danışmanlar: PROF. DR. AYŞEGÜL ALAYBEYOĞLU, ÖĞR. GÖR. ÜMİT SARP
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Grafik sinir ağları, Karmaşık ağlar, Makine öğrenmesi, Graph neural networks, Complex networks, Machine learning
- Yıl: 2026
- Dil: Türkçe
- Üniversite: İzmir Katip Çelebi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Yazılım Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Geleneksel makine öğrenmesi modellerinin doğrusal olmayan, Öklid dışı graf verilerini doğrudan işleme konusundaki yetersizliği ve derin öğrenme tabanlı Graf Sinir Ağlarının (GNN) yüksek donanım maliyetleri ile“kara kutu”doğasından kaynaklanan açıklanabilirlik sorunları, karmaşık ağ analizinin temel problem durumunu oluşturmaktadır. Bu tez çalışmasının temel amacı; graf teorisi tabanlı yerel, yarı-küresel ve küresel topolojik ve spektral indekslerin, geleneksel makine öğrenmesi modellerinde açıklanabilir ve düşük boyutlu öznitelik mühendisliği araçları olarak kullanılabilirliğini ve sınıflandırma performansına olan etkisini deneysel olarak ortaya koymaktır. Çalışmada, matematiksel graf invaryantlarının modellere sunduğu yapısal önbilgi (inductive bias) ampirik olarak değerlendirilmiştir. Çalışma kapsamında iki farklı veri yapısı ve problem düzeyi ele alınmıştır. İlk aşamada, tek büyük bir ağ yapısı sunan Cora atıf ağı veri seti üzerinde derece, aradalık, PageRank, harmonik ve özvektör merkezilikleri, yerel kümelenme katsayısı ve Katz merkeziliğinden oluşan yedi adet düğüm düzeyli öznitelik hesaplanarak“düğüm sınıflandırma”deneyleri yürütülmüştür. Bu deneylerde, graf tabanlı özniteliklerin geleneksel makine öğrenmesi modellerindeki katkısını değerlendirmek amacıyla Rastgele Orman (RF), XGBoost, Destek Vektör Makineleri (SVM) ve Çok Katmanlı Algılayıcı (MLP) modelleri kullanılmıştır. Ayrıca Cora veri setinin doğal graf yapısını doğrudan kullanan GCN tabanlı ek bir karşılaştırma deneyi gerçekleştirilmiştir. İkinci aşamada ise, her gözlemin bağımsız bir molekülü temsil ettiği MUTAG veri seti üzerinde Wiener, Zagreb-1, Zagreb-2, Randić, Sombor, Estrada ve Gutman indeksleri hesaplanarak“graf sınıflandırma”deneyleri gerçekleştirilmiştir. Deneysel bulgular, graf tabanlı yapısal özelliklerin özellikle geleneksel makine öğrenmesi modellerinde sınıflandırma başarısını artıran tamamlayıcı bir öznitelik mühendisliği aracı olarak işlev gördüğünü göstermiştir. Cora veri setinde, graf özniteliklerinin eklenmesiyle train-test deneylerinde en yüksek başarı artışı XGBoost modelinde elde edilmiş ve doğruluk oranı 0.7122'den 0.7509'a yükselmiştir; 5-katlı çapraz doğrulama aşamasında da RF, XGBoost ve SVM modellerinde kararlı bir performans artışı raporlanmıştır. Buna karşılık GCN tabanlı karşılaştırma deneyinde, yalnızca orijinal Cora öznitelikleriyle 0.8819 doğruluk, 0.8778 makro F1 ve 0.8815 weighted F1 değerleri elde edilirken, orijinal özniteliklere graf tabanlı düğüm özniteliklerinin eklenmesiyle 0.8635 doğruluk, 0.8597 makro F1 ve 0.8633 weighted F1 değerleri elde edilmiştir. Bu sonuç, GCN mimarisinin komşuluk matrisi üzerinden yapısal bilgiyi mesaj iletme süreciyle zaten içsel olarak kullandığını ve elle hesaplanan graf özniteliklerinin katkısının model mimarisine bağlı olarak değişebileceğini göstermektedir. Karar mekanizmalarında yapılan öznitelik önem analizlerinde, özvektör ve harmonik merkeziliklerin en belirleyici topolojik değişkenler olduğu saptanmıştır. MUTAG veri setinde ise en yüksek sınıflandırma doğruluğuna, yalnızca global graf indekslerini kullanan SVM modeli ile ulaşılmıştır (0.8829 ± 0.0433 doğruluk ve 0.8691 ± 0.0499 makro F1-skoru). Moleküler sınıflandırma süreçlerinde özellikle derece tabanlı (Zagreb ve Sombor) indekslerin en yüksek ayırt edici güce sahip olduğu doğrulanmıştır. Bu tez, karmaşık ağ problemlerinde geleneksel modellerin uygun topolojik indekslerle desteklendiğinde yüksek düzeyde başarılı, donanımsal açıdan daha az maliyetli ve açıklanabilir sonuçlar üretebileceğini göstermesi yönüyle literatüre önemli bir akademik katkı sunmaktadır. Çalışmanın temel sınırlılığı görece küçük ölçekli veri kümeleriyle çalışılmış olmasıdır; gelecek çalışmalarda bu yaklaşımın daha büyük biyolojik ve sosyal ağlarda test edilmesi, GCN dışındaki GraphSAGE, GAT ve GIN gibi farklı graf sinir ağı mimarileriyle karşılaştırılması ve Agentic AI gibi çok etmenli sistemlerin otonom iletişim topolojilerinin optimizasyonunda kullanılması önerilmektedir.
Özet (Çeviri)
The inability of traditional machine learning models to directly process non-linear, non-Euclidean graph data and the high computational costs along with the“black-box”nature of deep learning-based Graph Neural Networks (GNNs), which leads to explainability issues, constitute the core problem of complex network analysis. The main objective of this thesis is to empirically demonstrate the usability and impact on classification performance of local, quasi-global, and global topological and spectral graph theory indices as explainable and low-dimensional feature engineering tools in traditional machine learning models. In this study, the structural inductive bias provided by mathematical graph invariants to the models was evaluated empirically. Two different data structures and problem levels were addressed within the scope of this study. In the first stage, node classification experiments were conducted on the Cora citation network, which represents a single large network, by calculating seven node-level features consisting of degree, betweenness, PageRank, harmonic and eigenvector centralities, local clustering coefficient, and Katz centrality. In these experiments, Random Forest (RF), XGBoost, Support Vector Machines (SVM), and Multi-Layer Perceptron (MLP) models were used to evaluate the contribution of graph-based features to traditional machine learning models. In addition, a GCN-based comparison experiment was conducted by directly using the natural graph structure of the Cora dataset. In the second stage, graph classification experiments were performed on the MUTAG dataset, where each observation represents an independent molecule, by computing Wiener, Zagreb-1, Zagreb-2, Randić, Sombor, Estrada, and Gutman indices. Experimental results demonstrated that graph-based structural features function as complementary feature engineering tools that improve classification performance, particularly in traditional machine learning models. On the Cora dataset, the highest performance improvement in train-test experiments was achieved by the XGBoost model with the addition of graph features, increasing the accuracy from 0.7122 to 0.7509; moreover, a stable performance increase was reported in RF, XGBoost, and SVM models during the 5-fold cross-validation phase. In contrast, in the GCN-based comparison experiment, the model achieved 0.8819 accuracy, 0.8778 macro F1-score, and 0.8815 weighted F1-score using only the original Cora features, whereas the addition of graph-based node features to the original features resulted in 0.8635 accuracy, 0.8597 macro F1-score, and 0.8633 weighted F1-score. This result indicates that the GCN architecture already incorporates structural information internally through the message-passing process over the adjacency matrix, and that the contribution of manually computed graph features may vary depending on the model architecture. Feature importance analyses conducted on decision-making mechanisms revealed that eigenvector and harmonic centralities were the most decisive topological variables. On the MUTAG dataset, the highest classification performance was achieved by the SVM model utilizing only global graph indices (0.8829 ± 0.0433 accuracy and 0.8691 ± 0.0499 macro F1-score). It was confirmed that degree-based indices, particularly Zagreb and Sombor indices, possess the highest discriminative power in molecular classification processes. This thesis makes a significant academic contribution to the literature by demonstrating that traditional models, when supported by appropriate topological indices in complex network problems, can produce highly successful, computationally less expensive, and explainable results. The main limitation of the study is that it was conducted on relatively small-scale datasets; future work suggests testing this approach on larger biological and social networks, comparing it with graph neural network architectures other than GCN, such as GraphSAGE, GAT, and GIN, and using it for optimizing the autonomous communication topologies of multi-agent systems, such as Agentic AI.
Benzer Tezler
- Düğüm teorisinde klasik sayısal invaryantlar
Classical numerical invariants in knot theory
GÜLİN TABAKAN
