Abstrakt. Vi betraktar problemet med länk förutsägelser, baserat på partiell observation av ett stort nätverk, och på sidoinformation i samband med dess hörn. Den generativa modellen är formulerad som en matris logistisk regression. Modellens prestanda analyseras i ett högdimensionellt system under ett strukturellt antagande. Minimax-räntan för Frobenius-normrisken fastställs och en kombinatorisk uppskattning baserad på den bestraffade metoden med maximal sannolikhet visas uppnå den. Dessutom har det visat sig att denna hastighet inte kan uppnås med någon (randomiserad) algoritm som kan beräknas i polynomtid under ett beräkningsgrundat antagande om komplexitet. Primär 62J02, 62C20, sekundär 68Q17. Nyckelord och fraser: Länkförutsägelse, Logistisk regression, Beräknings nedre gränser, Planterad klick. När det gäller nätverksanalys består uppgiften för länkförutsägelse i att förutsäga förekomsten eller frånvaron av kanter i en stor graf, baserat på observationer av vissa av dess kanter, och på sidoinformation. Nätverksanalys har blivit en växande inspiration för statistiska problem. En av de viktigaste egenskaperna hos dataset i det moderna vetenskapliga landskapet är inte bara deras växande storlek, utan också deras ökande komplexitet. De flesta fenomen som nu studeras inom naturvetenskap och samhällsvetenskap rör inte bara isolerade och oberoende variabler, utan också deras interaktioner och samband. Det grundläggande problemet med kopplingsförutsägelser är därför naturligt kopplat till statistisk uppskattning: målet är att förstå, genom en generativ modell, varför olika hörn är kopplade eller inte, och att generalisera dessa observationer till resten av grafen. De flesta statistiska problem som baseras på grafer är oövervakade: grafen i sig är den enda data, det finns ingen sidoinformation, och målet är att återställa en okänd struktur i den generativa modellen. Exempel är den planterade klique problem Kučera, 1995), den stokastiska blockmodellen (Holland et al., 1983)-see Abbe (2017) för en nyligen genomförd undersökning av en mycket aktiv linje arbete (Abbe och Sandon, 2015; Banks et al., 2016; Decelle et al., 2011 Massoulié, 2014; Mossel et al., 2013 Mossel et al.,, 2015, Ising blockmodel, slumpmässiga geometriska diagram -se Penrose (2003) för en introduktion och (Bubeck et al., 2014; Devroye et al., 2011) för senaste utvecklingen inom statistik, eller metrisk-baserat lärande (Bellet et al., 2014; Chen et al., 2009 ) och ordinal embedings (Jain et al., 2016). I övervakade regressionsproblem å andra sidan ligger fokus på att förstå en grundläggande mekanism, formaliserad som kopplingen mellan två variabler. Målet är att lära sig hur en förklarande variabel X gör det möjligt att förutsäga ett svar Y, dvs. för att hitta den okända funktionen f som bäst approximerar förhållandet Y  till f (X). Denna statistiska ram tillämpas ofta på observation av ett fenomen som mäts med Y (t.ex. av naturlig eller social natur), med angivande av känd information X: principen är att förstå detta fenomen, att förklara förhållandet mellan variablerna genom att uppskatta funktionen f (Hoff et al., 2002; Holland och Leinhardt, 1981). Vi följer denna strategi här: vårt mål är att lära sig hur kända egenskaper hos varje agent (representerad av en nod) i nätverket framkallar en större eller mindre chans till anslutning, att förstå mekanismen för bildande av grafen. Vi föreslår en modell för övervakad länk förutsägelse, med tillämpning av regressionsprincipen för slutsatser om grafer. För varje vertex, vi ges sidoinformation, en vektor av observationer X  på R d. Med tanke på observationer X i, X j om noder i och j av ett nätverk, syftar vi till att förstå hur dessa två förklarande variabler är relaterade till sannolikheten för anslutning mellan de två motsvarande hörn, sådan att P (Y (i,j) = 1) = f (X i, X j ), genom att uppskatta f inom en högdimensionell klass baserat på logistisk regression. Förutom denna högdimensionella parametriska modellering utnyttjades olika helt icke-parametriska statistiska ramar i litteraturen, se t.ex. Gao et al. Länk förutsägelse kan vara användbart i alla program där data kan samlas in om noderna i ett nätverk. En av de mest uppenbara motiven är i sociala nätverk, för att modellera sociala interaktioner. Med tillgång till sidoinformation om varje medlem i ett socialt nätverk är målet att förstå mekanismerna för anslutning mellan medlemmar: gemensamma intressen, skillnader i konstnärlig smak eller politisk åsikt (Wasserman och Faust, 1994). Detta kan också tillämpas på citeringsnätverk, eller inom naturvetenskapen på biologiska nätverk av interaktioner mellan molekyler eller proteiner (Madeira och Oliveira, 2004; Yu et al., 2008). Det viktigaste antagandet i denna modell är att nätverket är en följd av informationen, men inte nödvändigtvis baserad på likhet: det är möjligt att modellera mer komplexa interaktioner, t.ex. där motsatser drar till sig. Fokus på en högdimensionell miljö är en annan aspekt av detta arbete som också motiveras av moderna tillämpningar av statistik: data samlas ofta in utan urskiljning och den omgivande dimensionen d kan vara mycket större än provstorleken. Denna inställning är vanlig i regressionsproblem: den underliggande modellen är ofta mycket enkel, för att återspegla det faktum att endast ett litet antal uppmätta parametrar är relevanta för det aktuella problemet, och att den inneboende dimensionen är mycket mindre. Detta hanteras vanligen genom ett antagande om en parameters rang, sparsamhet eller regelbundenhet. Här måste detta anpassas till en modell med två kovariater (förklarande variabler) och ett strukturellt antagande görs OPTIMAL LINK PRIDICTION MED MATRIX LOGISTIC REGRESSION 3 för att återspegla denna typ av vårt problem. Vi beslutar därför att ta itu med länkförutsägelsen genom att modellera den som matris logistisk regression. Vi studerar en generativ modell för vilken P(Y (i,j) = 1) = σ(X  till i  på X j ), där σ är sigmoidfunktionen, och  på är den okända matrisen att uppskatta. Det är ett enkelt sätt att modellera hur variablerna interagerar, genom en kvadratisk affinitetsfunktion och en sigmoidfunktion. För att modellera realistiska situationer med partiella observationer, antar vi att Y (i,j) endast observeras för en delmängd av alla par (i, j), betecknad av  på. För att förmedla den allmänna idén om en enkel beroende av X i och X j, Vi gör strukturella antaganden om den rang och gleshet. Detta återspeglar att affiniteten X  och X j, för ett litet antal ortogonala vektorer, som har sig ett litet antal icke-noll koefficienter (parsitet antagande). För att införa att det inversa problemet är välplacerade, gör vi också en begränsad konditionering antagande om  på, inspirerad av den begränsade isometry egendom (RIP). Dessa villkor diskuteras i avsnitt 1. Vi talar om länk förutsägelse som detta är det äldre namnet, men vi fokuserar nästan helt på problemet med att uppskatta. De klassiska teknikerna för sannolikhetsmaximering kan leda till beräkningsmässigt intractable optimeringsproblem. Vi visar att både i detta och andra problem är detta en grundläggande svårighet, inte en svaghet i en viss uppskattningsteknik; statistiska och beräkningsmässiga komplexiteter är sammanflätade. Vårt bidrag: Detta arbete är organiserat på följande sätt: Vi ger en formell beskrivning av problemet i Avsnitt 1, samt en diskussion om våra antaganden och kopplingar till relaterat arbete. Avsnitt 2 samlar in våra viktigaste statistiska resultat. Vi föreslår en uppskattning som bygger på den bestraffade metoden med maximal sannolikhet och analyserar dess resultat i avsnitt 2.1 i termer av icke-asymptotisk uppskattningsfrekvens. Vi visar att det uppnår minimax hastighet av uppskattning över samtidigt block-sparse och låg-rank matriser  på, men är inte beräkningsbart dragbart. I avsnitt 2.2 ger vi en konvex avslappning av problemet som i huvudsak är Lasso estimator tillämpas på en vektoriserad version av problemet. Länkförutsägelseuppgiften behandlas i avsnitt 2.3. En motsvarande minimax lägre gräns för estimeringshastigheten anges i avsnitt 2.4. Dessutom visar vi i Avsnitt 3 att minimax-hastigheten inte kan uppnås med en (randomiserad) polynom-tidsalgoritm, och vi identifierar en motsvarande beräkningsmässig lägre gräns. Beviset på detta är baserat på ett minskningssystem från det så kallade täta problemet med att upptäcka subgrafer. Tekniska bevis skjuts upp till tillägget. Våra resultat beskrivs i figur 1. Anmärkning: För alla positiva heltal n, vi betecknar med [n] uppsättningen {1,.., n} och av [[n] uppsättningen par av [n], av kardinalitet n 2. Vi betecknar med R uppsättningen av reella tal och med S d uppsättningen av verkliga symmetriska matriser av storlek d. För en matris A  på S d, vi betecknar med A F dess Frobenius norm, definieras av Vi utökar denna definition för B  på S n och någon delmängd  och... [n] till dess semi-norm
I den besläktade inställningen av den induktiva länkförutsägelsen i graferna REF erhålls den optimala minimax-frekvensen i sparsamt och lågrankat system och avvägningarna mellan de statistiska talen och beräkningskomplexet avslöjas.
Optimal link prediction with matrix logistic regression
{'venue': None, 'journal': 'arXiv: Statistics Theory', 'mag_field_of_study': ['Mathematics']}