Is star complexity a proxy for information based complexity of graphs?

Technische Samenvatting: Stercomplexiteit als Proxy voor Informatie-gebaseerde Complexiteit van Grafen

Probleemstelling
Het artikel onderzoekt of "stercomplexiteit", een structurele maatstaf voor grafen, dient als een praktische proxy voor "Informatie-gebaseerde Complexiteit" (IBC). IBC is een formele complexiteitsmaatstaf die wordt gedefinieerd door de proportie beschrijvingen in een specifieke taal die via een classifier naar een gegeven object leiden. Hoewel theoretische IBC (gebaseerd op universele Turingmachines) asymptotisch onafhankelijk is van de coderings-taal, veronderstelt het artikel dat praktische IBC-maten afgeleid van verschillende coderingsschema's ook asymptotisch equivalent zullen zijn. Specifiek vergelijkt de studie een standaard grafen-IBC-maat ($C$), die grafen codeert via edge-lijsten en ze classificeert op basis van automorfisme, met stercomplexiteit, wat complexiteit definieert op basis van het minimale aantal unie- en intersectie-operaties van elementaire "sterren" die nodig zijn om een graaf te construeren.

Methodologie
Het onderzoek hanteert een vergelijkende empirische benadering met behulp van twee verschillende complexiteitsmaten:

1. Grafencomplexiteit ($C$): Berekend met de formule $C(x) = \ell - \log_2 \omega(x)$, waarbij $\ell$ de lengte is van de edge-list codering en $\omega$ het aantal strings van die lengte is die naar dezelfde graaf leiden (bepaald via grafen-automorfisme algoritmen met de Nauty-bibliotheek).
2. Stercomplexiteit ($Star(G)$): Gedefinieerd als het minimale aantal verzamelingenoperaties (unie/intersectie) van elementaire sterren (een centrale hub-vertex verbonden met alle andere vertices) die nodig zijn om een graaf te genereren.
3. Ster-gebaseerde IBC ($C^*$): Een IBC-maatstaf die specifiek is afgeleid van stercomplexiteit. Deze codeert de graaf door het aantal vertices, het aantal sterren en een Reverse Polish Notation (RPN) "recept" van operaties op te slaan. $C^*$ past de bitlengte van dit recept aan door $\log_2 \omega$ af te trekken, waarbij $\omega$ het aantal equivalente recepten voor een gegeven graaf is.
4. Bovengrens Schatting ($\overline{Star}(G)$): Omdat het berekenen van de exacte $Star(G)$ een uitputtende zoektocht vereist naar alle mogbare opeenvolgingen van operaties (wat computationeel onhaalbaar is voor grote grafen), introduceren de auteurs een algoritmische bovengrens. Dit algoritme construeert een graaf door vertices met een maximale graad te dekken met sterren en de resterende edges te dekken via paarwise intersecties, en optimaliseert vervolgens de expressie middels verzameling-associativiteit.

Experimentele Uitvoering
De studie maakte gebruik van het EcoLab-pakket, geoptimaliseerd voor GPU-executie (Intel Xe graphics) om een 23x versnelling te bereiken ten opzichte van single-threaded CPU-verwerking. De experimenten omvatten:

• Kleinschalige Uitputtende Zoektocht: Het genereren van alle grafen met 10 en 22 vertices die een stercomplexiteit van 8 of minder hebben. Dit maakte de exacte berekening van $C$, $Star(G)$ en $C^*$ mogelijk, inclusief de enumeratie van equivalente recepten ($\omega$).
• Grootschalige Steekproef: Het genereren van 1.000 Erdős-Rényi willekeurige grafen met 1.000 vertices om de relatie tussen de gemakkelijk berekenbare bovengrens $\overline{Star}(G)$ en de standaard complexiteit $C$ te testen.

Belangrijkste Resultaten

• Kleine Grafen (10 en 22 vertices): De correlatie tussen de standaard complexiteit $C$ en de ruwe stercomplexiteit $Star(G)$ bleek verwaarloosbaar (correlatiecoëfficiënten $\rho \approx 0,08$ en $-0,04$, respectievelijk). Ook de correlatie tussen $C$ en de op sterren gebaseerde IBC $C^*$ was zwak ($\rho \approx 0,14$ en nabij nul).
• Correlatie van Maten: Echter, $Star(G)$ en $C^*$ vertoonden een matige positieve correlatie ($\rho \approx 0,6$), en de geschatte bovengrens $\overline{Star}(G)$ correleerde sterk met de exacte $Star(G)$($\rho \approx 0,85$).
• Grote Grafen (1.000 vertices): De meest significante bevinding kwam voort uit de grootschalige steekproef. Een sterke, zij het niet-lineaire, relatie werd waargenomen tussen de computationeel berekenbare bovengrens $\overline{Star}(G)$ en de informatie-gebaseerde complexiteit $C$.

Betekenis en Claims
Het artikel concludeert dat hoewel ruwe stercomplexiteit niet lineair correleert met informatie-gebaseerde complexiteit op kleine, uitputtende datasets, de twee maten voor grotere grafen waarschijnlijk dezelfde onderliggende eigenschap meten. De sterke empirische relatie tussen de gemakkelijk berekenbare bovengrens van de stercomplexiteit $\overline{Star}(G)$ en de standaard IBC-maat $C$ suggereert dat stercomplexiteit fungeert als een geldige proxy voor informatie-gebaseerde complexiteit in praktische scenario's. De auteurs stellen dat dit de bredere hypothese ondersteunt dat verschillende praktische IBC-coderingsschema's asymptotisch equivalent zijn. Bijgevolg kan stercomplexiteit, aangezien deze computationeel eenvoudiger te berekenen is dan volledige IBC-berekeningen voor grote grafen, dienen als een betrouwbare estimator voor grafencomplexiteit.