Vi anser att problemet med bytespunktsdetektering är att, baserat på bullriga mätningar, avgöra om en okänd signal över en given graf är konstant eller istället bitvis konstant över två anslutna inducerade subgrafer av relativt låg skärstorlek. Vi analyserar motsvarande generaliserade sannolikhetskvot (GLR) statistik och relaterar den till problemet med att hitta en glesaste skär i en graf. Vi utvecklar en dragbar avslappning av GLR statistik baserad på kombinatorial Laplacian av grafen, som vi kallar spektral avsökning statistik, och analysera dess egenskaper. Vi visar hur dess prestanda som testförfarande är direkt beroende av grafens spektrum, och använder detta resultat för att explicit härleda dess asymptotiska egenskaper på få signifikanta graftopologier. Slutligen visar vi både teoretiskt och genom simuleringar att statistiken över spektralskanning kan överträffa naiva testförfaranden baserade på kanttröskel och χ 2-test.
Vi bygger vidare på våra tidigare resultat i REF där Spectral Scan Statistik föreslogs som en konvex spektral avslappning av GLRT och karakteriserar dess statistiska prestanda.
Changepoint Detection over Graphs with the Spectral Scan Statistic
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}