Graph Reduction in Multirelational Networks: A Spreading-Oriented Reduction Benchmark

Technische Samenvatting: Graafreductie in Multirelationele Netwerken (SORB)

Probleemstelling
Real-world netwerken zijn vaak incompleet, ruizig en dynamisch evoluerend, wat directe analyse computationeel veeleisend maakt. Hoewel Influence Maximization (IM)—de taak om zaadknooppunten te identificeren die de informatieverspreiding maximaliseren—breed wordt bestudeerd, blijft de impact van graafreductie (sparsificatie en coarsening) als een preprocessing-stap op de IM-nauwkeurigheid onderbelicht. Bestaande benchmarks richten zich doorgaans op single-relationship grafen of knoopclassificatie, en falen om hoe reductiestrategieën de verspreidingsprocessen in complexe, multirelationele systemen beïnvloeden. Bovendien is de interactie tussen graafreductie en de specifieke structurele eigenschappen van multilayer netwerken grotendeels ononderzocht.

Methodologie: De Spreading-Oriented Reduction Benchmark (SORB)
De auteurs introduceren SORB, een open-source, gestandaardiseerd framework dat is ontworpen om IM-modellen systematisch te evalueren over diverse taaksituaties, terwijl het graafreductie direct integreert in de evaluatiepijplijn.

• Pijplijn Architectuur: De workflow bestaat uit drie stadia:

  1. Reductiemodule: Genereert gereduceerde versies van invoernetwerken met behulp van een grid van reductieratio's ($r \in \{0.01, \dots, 0.9\}$) en methoden.
  2. Predictiemodule: Voert seed-selectiemodellen uit op zowel de originele als de gereduceerde grafen.
  3. Diffusie & Evaluatie: Voert Multilayer Independent Cascade Model (MICM) simulaties uit op de originele netwerken met behulp van de zaadsets die zijn voorspeld vanuit de gereduceerde grafen. Dit zorgt ervoor dat prestatiemetingen de ware verspreidingspotentie op de volledige data reflecteren, waardoor het effect van de reductie op de kwaliteit van de voorspelling wordt geïsoleerd.

• Datasets: De benchmark maakt gebruik van zeven real-world netwerken, inclus{\u00ad}e homogene grafen (WikiCS, Amazon-CS) en multilayer netwerken (Freebase, IMDB, FinDKG, arxiv, timik).

• Flattening Strategie: Omdat de meeste reductiealgoritmen opereren op homogene grafen, worden multilayer netwerken getransformeerd naar single-layer multigrafen via een "flattening"-proces. Dit aggregeert inter-layer relaties tot een enkele edge-set, waarbij de actor-niveau aggregatie behouden blijft maar potentiële edge-duplicatie wordt geïntroduceerd. De auteurs beschouwen dit als een pragmatische afweging om bestaande algoritmen te testen, waarbij zij erkennen dat dit een structurele operatie is met inherente kosten.

• Reductiemethoden: De studie evalueert vijf sparsificatietechnieken (Random, LocalDegree, Jaccard similarity, TSpanner, ForestFire) en twee coarsening technieken (VariationNeighborhoods, AffinityGs).

• IM Modellen: Zes seed-selectiemodellen worden getest, variërend van laag-complexe heuristieken (Degree Centrality, Degree Discount, Neighbourhood Size) tot hoog-complexe leer-gebaseerde modellen (ts-net) en multilayer extensies (v-rnk-m).

• Evaluatiemetingen:

  • Gain@k: Meet de kwaliteit van de geselecteerde zaadsets van grootte $k$ (enkele knoop of percentage van de actoren).
  • $AUC_{cutoff}$: Meet de overeenkomst tussen de grondwaarheid invloed-ranking en de voorspelde ranking binnen de top 80% van de actoren.

Belangrijkste Bijdragen en Bevindingen
De studie adresseert vier onderzoeksvragen met betrekking tot de impact van reductie op IM-prestaties, de rol van reductieratio's, consistentie over netwerken en het gebruik van computationele middelen.

1. Impact op de Kwaliteit van de Zaadset (Gain@k):

   • Sparsificatie: Op single-layer (homogene) netwerken behoudt sparsificatie de kwaliteit van de zaadset over alle onderzochte groottes. De gemiddelde prestatie blijft op baseline-niveaus en de variantie wordt vaak kleiner.
   • Coarsening: Op de subset van netwerken waar coarsening computationeel haalbaar was, resulteerde het in slechts een marginale daling in Gain@k, gepaard met een verbeterde stabiliteit van de resultaten (lagere variantie).
   • Multilayer Context: Geflatteneerde multilayer netwerken vertonen een systematische degradatie van de ranking, ongeacht de reductiestrategie, wat suggereert dat huidige reductiemethoden moeite hebben met de structurele complexiteit die door flattening wordt geïntroduceerd.

2. Rol van Reductieratio ($r$) vs. Strategie:

   • Er is geen statistisch significante monotone relatie tussen de nominale reductieratio $r$ en de downstream prestatiedegradatie ($AUC_{cutoff}$).
   • De degradatie wordt primair gedreven door de keuze van de reductiestrategie in plaats van het percentage verwijderde edges. Zo gedraagt ForestFire zich als een stapfunctie (behoudt structuur tot een drempelwaarde), terwijl TSpanner in sommige contexten een omgekeerde relatie met $r$ vertoont.
   • Structurele sensitiviteit is hoog; zelfs willekeurige edge-verwijdering induceert statistisch significante verschuivingen in de ranking.

3. Consistentie over Netwerken:

   • Homogene netwerken vertonen consistent en stabiel gedrag onder reductie.
   • Heterogene (multilayer) netwerken vormen een duidelijke uitdaging. De flattening-transformatie introduceert een overhead (edge-duplicatie) die de geheugenbesparing bij lage reductieratio's ($r \le 0.5$) kan tegenwerken, met name voor leer-gebaseerde modellen zoals ts-net.

4. Computationele Middelen:

   • Sparsificatie levert meetbare reducties op in de inferentie-tijd en het geheugengebruik, met name voor zwaardere modellen (v-rnk-m en ts-net).
   • Echter, voor heterogene grafen kan de flattening-stap de geheugenvereisten voor ts-net verhogen bij lage reductieratio's, omdat de resulterende single-layer graaf strikt meer edges bevat dan elke individuele layer.

Significantie en Claims
De auteurs beweren dat SORB de focus verschuift van het testen van IM-algoritmen in isolatie naar het kwantificeren van hoe graafreductie de voorspellende prestaties verandert onder realistische condities. De primaire significantie van het werk ligt in het aantonen dat:

• Graafreductie een levensvatbare preprocessing-stap is voor IM, met name voor sparsificatie op homogene netwerken, wat middelenbesparing biedt met minimaal prestatieverlies.
• De keuze van de reductiestrategie belangrijker is dan de reductieratio zelf.
• Huidige reductiemethoden niet goed geschikt zijn voor multilayer netwerken wanneer ze via een flatten-then-reduce pijplijn worden toegepast, wat een gat in de literatuur voor dedicated multilayer reductiealgoritmen benadrukt.

Het artikel concludeert dat hoewel sparsificatie potentieel biedt voor efficiënte analyse, het gebrek aan dedicated benaderingen voor heterogene grafen een uitdaging blijft. De auteurs positioneren SORB als een fundament voor toekomstig werk om graafcondensatie en methoden te integreren die specifiek zijn ontworpen voor heterogene netwerkstructuren.