RIS, A Topology-Preserving Framework for Adaptive Transformer Sparsification

# Code Ocean Capsule: Reduced Interaction Sampling (RIS) Framework ## Overview This compute capsule provides the reference implementation, high-performance benchmarking suite, and reproducible figure-generation scripts for the **Reduced Interaction Sampling (RIS)** framework. RIS is a stochastic sparsification algorithm designed to break the $O(N^2)$ quadratic complexity bottleneck inherent in self-attention mechanisms and large-scale graph analytics. By exploiting the deep informational redundancy present in complex networks, the Heuristic Adaptive Function (HAF) within RIS identifies a "structural skeleton" of high-degree hubs and bridging edges. This allows algorithms to transition from $O(N^2)$ to $O(N \log N)$, or even to linear $O(N)$, operations while maintaining global topological fidelity. ## Key Reproducible Results This capsule automatically reproduces the core empirical findings of the manuscript: 1. **The Quadratic Wall Break**: Achieving near-total reduction of redundant pairwise operations for large networks, validating the theoretical shift to linear complexity. 2. **Topological Preservation**: Generating Pearson correlations between true vs. sampled degree centrality on synthetic scale-free networks, maintaining $\rho > 0.75$ through a stable Transition Phase. 3. **Extreme Sparsity Performance (Transformers)**: Simulating context-window patterns on the 4-million-node com-LiveJournal network at $\approx 0.06\%$ density (the scale of modern frontier LLMs), where RIS recovers 4.4% more global hubs than Longformer and BigBird across 20,000 statistical replicates. 4. **Universality Across Domains**: Validating RIS behavior across scientific collaboration arrays, financial trust graphs, and global air transport networks vs. regular power grid lattices. ## Execution The default `run` script automatically detects the environment and executes the Python 3 orchestration suite to process the synthetic and real-world network data. All final outputs—including the CSV metrics and high-resolution PDFs mirroring the manuscript's Figures 1 through 5—are generated natively and exported to the `/results` directory.