Graph-baserade Semi-övervakade inlärningsalgoritmer (SSL) har framgångsrikt använts i ett stort antal tillämpningar. Dessa metoder klassificerar initialt omärkta noder genom att sprida märkningsinformation över strukturen på grafen med start från frönoder. Grafbaserade SSL-algoritmer skalas vanligtvis linjärt med antalet olika etiketter (m), och kräver O(m) utrymme på varje nod. Tyvärr finns det många tillämpningar av praktisk betydelse med mycket stora m över stora grafer, kräver bättre utrymme och tid komplexitet. I detta dokument föreslår vi MAD-Sketch, en ny grafbaserad SSL-algoritm som kompakt lagrar etikettdistribution på varje nod med Count-min Sketch, en randomiserad datastruktur. Vi presenterar teoretisk analys som visar att under milda förhållanden, MAD-Sketch kan minska utrymme komplexitet vid varje nod från O(m) till O(log m), och uppnå liknande besparingar i tid komplexitet också. Vi stöder vår analys genom experiment på flera riktiga datauppsättningar. Vi observerar att MAD-Sketch uppnår liknande prestanda som befintliga toppmoderna grafbaserade SSL-algoritmer, samtidigt som det kräver mindre minnesavtryck och samtidigt uppnår upp till 10x speedup. Vi finner att MAD-Sketch kan skala till datauppsättningar med en miljon etiketter, vilket ligger utanför räckvidden för befintliga grafbaserade SSL-algoritmer.
För att hantera ett stort antal olika etikettvärden kan märkningsuppdragen sammanfattas med hjälp av countminskisser REF.
Scaling Graph-based Semi Supervised Learning to Large Number of Labels Using Count-Min Sketch
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}