Geri Dön

Boosting large-scale graph embedding with multi-level graph coarsening

Büyük ölçekli çizge gömme işlemlerini iyileştirmek için çok katmanlı çizge indirgeme

  1. Tez No: 642053
  2. Yazar: TAHA ATAHAN AKYILDIZ
  3. Danışmanlar: DR. ÖĞR. ÜYESİ KAMER KAYA
  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: 2020
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 66

Özet

Çizgeler protein etkileşim ağlarından sosyal ağlara hemen her yerde bulunmaktadır. Fakat çizgelerin düzensiz veri yapısı, çizgelerin üzerinde bağlantı tahmini, düğüm sınıflama ve aykırılık belirleme gibi makine öğrenmesi görevleri çalıştırmak adına bir engel teşkil etmektedir. Çizge gömme, çizgeleri çok boyutlu bir uzayda tanımlayarak, çizgeler üzerinde makine öğrenmesi görevlerinin kolayca çalıştırılabilmesini sağlamaktadır. Literatürde bir dizi çalışma bu metodun faydalarını göstermiş olsa da, çizge gömme yoğun işlem teşkil eden bir metottur. Güncel gömme uygulamaları, ya büyük ölçekli çizgeleri işleyememekte ya da işlemek için pahalı bir donanım gerektirmektedir. Bu çalışmada orijinal, paralel ve çok katmanlı bir çizge indirgeme metodu ileri sürmekteyiz. Bu metot çizge gömmenin performansını hem zaman hem de doğruluk açısından geliştirmektedir. Bu çalışmada, bahsedilen metot, GOSH adlı büyük ölçekli çizgeleri tek bir ekran kartı ile işleyebilen bir çizge gömme uygulamasına entegre edilmiştir. Çizge indirgeme metodu entegre edildiğinde, GOSH ortalama olarak 14 kat daha hızlı çalışmakta ve orta büyüklükteki çizgelerin çoğunda daha başarılı AUCROC değerleri elde etmektedir. Veri setindeki, 66 milyon düğüm ve 1.8 milyar bağlantı bulunan en büyük çizgeyi, GOSH, %93.4 AUCROC elde ederken işlemi bir saatin altında tamamlamıştır. Bunlara ek olarak bu çalışmada, çizge indirgeme kalitesinin çizge gömme kalitesine etkisini incelemekteyiz. Deneylerimiz indirgeme sürecinin dengeli olması gerektiğini ve ileri sürülen indirgeme metodunun çizge gömme açısından üstün bir performans sergilediğini göstermektedir.

Özet (Çeviri)

Graphs can be found anywhere from protein interaction networks to social networks. However, the irregular structure of graph data constitutes an obstacle for running machine learning tasks such as link prediction, node classification, and anomaly detection. Graph embedding is the process of representing graphs in a multi-dimensional space, which enables machine learning tasks to be run on graphs. Although, embedding is proven to be advantageous by a series of works, it is compute-intensive. Current embedding approaches either can not scale to large graphs or they require expensive hardware for such purposes. In this work we propose a novel, parallel multi-level coarsening method to boost the performance of graph embedding both in terms of speed, and accuracy. We integrate the proposed coarsening approach into a GPU-based graph embedding tool called GOSH, which is able to embed large-scale graphs with a single GPU at a fraction of the time compared to the state-of-the-art. When coarsening is introduced, the run-time of GOSH improves by 14 times while scoring greater AUCROC for the majority of medium-scale graphs. For the largest graph in our data-set with 66 million vertices, and 1.8 billion edges, embedding takes under an hour, and 93.4% AUCROC is achieved. Moreover, we investigate the relationship between quality of the coarsening on the quality of the embeddings. Our preliminary experiments show that the coarsening decisions must be balanced and the proposed coarsening strategy novel performs well for graph embedding.

Benzer Tezler

  1. Yapay sinir ağları ve makine öğrenmesi ile otomobil satış tahmininin yapılması ve zaman serileri analizi ile karşılaştırılması

    Forecasting automobile sales using artificial neural networks and machine learning and comparison with time series analysis

    BEYZA KURTGERİ

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

    Endüstri ve Endüstri MühendisliğiSakarya Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MERVE CENGİZ TOKLU

  2. A novel artificial intelligence based energy management system for microgrids

    Mikro şebekeler için yapay zeka temelli yeni bir enerji yönetim sistemi

    NECATİ AKSOY

    Doktora

    İngilizce

    İngilizce

    2023

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    PROF. DR. VEYSEL MURAT İSTEMİHAN GENÇ

  3. Web kazıma ve makine öğrenmesi yöntemleri kullanılarak fiyat tahminleme: İkinci el araç piyasasında bir örnek

    Price prediction using web scraping and machine learning methods: An example in the used car market

    SEDA KAHRAMAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Mühendislik BilimleriSakarya Üniversitesi

    Bilişim Sistemleri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. İHSAN HAKAN SELVİ

  4. Support vector boosting: A large scale parallel SVM approximation

    Support vector boostıng: Geniş veri setleri için paralel SVM yakınsaması

    ENDER AKPINAR

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. SÜREYYA AKYÜZ

  5. Türkiye'de bireysel emeklilik yatırım fonlarının TOPSIS yöntemi ile performans değerlendirmesi

    Evaluation performance of turkish individual pension funds with TOPSIS method in turkey

    KAMURAN ÜNAL

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    BankacılıkKarabük Üniversitesi

    İşletme Ana Bilim Dalı

    DOÇ. DR. MURAT YILDIRIM