Reordering graphs for node embeddings
Düğüm gömme için çizgeleri yeniden sıralama
- Tez No: 894860
- Danışmanlar: DOÇ. DR. KAMER KAYA
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Bilimi ve Mühendisliği Bilim Dalı
- Sayfa Sayısı: 78
Özet
Günümüzün birbirine bağlı dünyasında, çizgeler sosyal ağlardan ulaşım sistemlerine, biyolojik ağlardan öneri sistemlerine kadar çeşitli alanlarda karmaşık ilişkileri ve yapıları modellemek için yaygın olarak kullanılmaktadır. Ancak, bu çizgelerin yüksek boyutluluğu ve karmaşık bağlantıları, analiz ve işleme konusunda önemli zorluklar yaratmaktadır. Düğüm gömme teknikleri, çizge düğümlerini düşük boyutlu vektörlere dönüştürerek orijinal çizgenin yapısal özelliklerini ve ilişkilerini korurken bu zorlukların üstesinden gelmek için güçlü araçlar olarak ortaya çıkmıştır. Etkili olmalarına rağmen, düğüm gömme işlemi, büyük ölçekli çizgeler için önemli hesaplama kaynakları ve zaman gerektirdiğinden pahalı bir süreç olabilir. Bu tez, çizgeleri temsil eden matrislerin yeniden düzenlenmesiyle GPU'ları kullanan düğüm gömme çerçevelerini iyileştirmeyi amaçlamaktadır. Çizgelerin yeniden düzenlendiği olasılıksal bir parça atlama stratejisi öneriyoruz; bu strateji, çizgenin parçalarının GPU belleğine taşınması ve geri alınması sırasında oluşan yükü ortadan kaldırarak süreci önemli ölçüde hızlandırmaktadır. Ortaya çıkan gömmeler, rastgele sıralanmış bir çizgede öğrenilen gömmeler kadar iyi performans göstermekte ve bazı durumlarda bağlantı tahmini görevlerinde önemli ölçüde daha iyi performans göstermektedir. Ayrıca, SuiteSparse ve The Network Repository'den elde edilen çeşitli çizgelerde yeniden düzenleme sonrası bağlantı tahmini sonuçlarını sunuyoruz. Sonuçlar, çizgeler içinde bulunan bağlantı yapısı ve topluluk bilgilerini vurgulayan yeniden düzenleme algoritmaları sınıfının, kullanılan çizge türünden bağımsız olarak bağlantı tahmini sonuçlarını iyileştirdiğini göstermektedir.
Özet (Çeviri)
In today's interconnected world, graphs are widely used to model complex relationships and structures across various domains, from social networks and transportation systems to biological networks and recommendation systems. However, the high dimensionality and intricate connectivity of these graphs pose significant challenges for analysis and processing. Node embedding techniques have emerged as powerful tools to address these challenges by transforming graph nodes into low-dimensional vectors while preserving the inherent structural properties and relationships of the original graph. Despite their effectiveness, node embedding can be an expensive process, particularly for large-scale graphs, due to the substantial computational resources and time required. This thesis aims to improve node embedding frameworks that utilize GPUs by reordering matrices that represent graphs. We propose a probabilistic part-skipping strategy on reordered graphs that eliminates the overhead created by moving parts of the graph into and out of the GPU memory and therefore speeding up the process significantly. The resulting embeddings perform as well as embeddings learned on a randomly ordered graph and in some cases perform significantly better on link prediction tasks. We also present link prediction results after reordering on various graphs obtained from SuiteSparse and The Network Repository. The results show that the class of reordering algorithms that emphasize the connectivity structure and community information found within the graphs improve the link prediction results regardless of the graph type used.
Benzer Tezler
- Optimization of SPARQL queries using artificial intelligence techniques
Yapay zeka teknikleri kullanılarak SPARQL sorgularının optimizasyonu
ELEM GÜZEL KALAYCI
Yüksek Lisans
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. DERYA BİRANT
- Parallel direct volume rendening of unsructed grids based on object-space decomposition
Düzensiz ızgaraların obje uzayı bölünmesine dayanan paralel hacim görüntülenmesi
FERİT FINDIK
Yüksek Lisans
İngilizce
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiDOÇ. DR. CEVDET AYKANAT
- Hypergraph models for sparse matrix partitioning and reordering
Seyrek matris bölümleme ve yeniden-düzenleme için hiperçizge modelleri
ÜMİT VEYSEL ÇATALYÜREK
Doktora
İngilizce
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Yazılımı Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Reordering methods for exploiting spatial and temporal localities in parallel sparse matrix-vector multiplication
Paralel seyrek matris vektör çarpımında uzaysal ve zamansal yerelliği kullanmak için sıralma yöntemleri
NABIL F. T. ABUBAKER
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Görsel olarak zenginleştirilmiş yenilikçi madde formatı geliştirilmesi ve uygulamalı olarak değerlendirilmesi
Development and evaluation of visually enhanced innovative item types
SEBAHAT GÖREN KAYA
Yüksek Lisans
Türkçe
2018
Eğitim ve ÖğretimGazi ÜniversitesiEğitim Bilimleri Ana Bilim Dalı
DOÇ. DR. NİLÜFER KAHRAMAN