I praktiska maskininlärningssystem har grafbaserad datarepresentation i stor utsträckning använts i olika inlärningsparadigm, allt från oövervakad klusterbildning till övervakad klassificering. Förutom de tillämpningar med naturlig graf eller nätverksstruktur data, såsom sociala nätverksanalys och relationell inlärning, många andra applikationer ofta innebär ett kritiskt steg i att omvandla datavektorer till en adjacency graf. I synnerhet krävs ofta en gles subgraf som extraheras från den ursprungliga grafen på grund av både teoretiska och praktiska behov. Tidigare studie visar tydligt att prestandan hos olika inlärningsalgoritmer, t.ex. klusterering och klassificering, drar nytta av sådana glesa subgrafer med balanserad nodanslutning. De befintliga grafkonstruktionsmetoderna är dock antingen kostnadskrävande eller har otillfredsställande prestanda. I detta papper använder vi en skalbar metod som kallas auktionsalgoritm och dess parallella förlängning för att återställa en gles men ändå nästan balanserad subgraf med betydligt lägre beräkningskostnader. Empirisk studie och jämförelse med den senaste tekniken visar tydligt den föreslagna metodens överlägsenhet både vad gäller effektivitet och noggrannhet.
Dessutom, Wang et al. REF använde parallella auktionsalgoritmer för att återvinna en gles men ändå nästan balanserad subgraf för sociala nätverk, vilket avsevärt minskar beräkningskostnaderna.
Fast Graph Construction Using Auction Algorithm
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}