An Empirical Spectral-Domination Relationship Discovered Through Symbolic Regression

Technical Summary: An Empirical Spectral-Domination Relationship Discovered Through Symbolic Regression

Problem Statement
The paper addresses the challenge of discovering mathematical relationships between graph invariants, specifically focusing on the domination number $\gamma(G)$ (the size of the smallest dominating set) and the spectral radius $\lambda_1(G)$ (the largest eigenvalue of the adjacency matrix). While extensive research exists on bounds for $\gamma(G)$ involving degree structures (e.g., $\gamma(G) \ge n/(\Delta(G)+1)$) and spectral bounds involving the Laplacian spectrum, relatively few bounds relate $\gamma(G)$ directly to the adjacency spectral radius $\lambda_1(G)$. The authors aim to leverage machine learning to identify potential empirical formulas that could serve as starting points for theoretical investigation.

Methodology
The study employs a data-driven pipeline combining graph generation, invariant computation, and symbolic regression:

1. Dataset Generation: A dataset of 3,429 connected graphs was generated from four distinct families with expanded parameter ranges:

   • Erdős–Rényi ($G(n,p)$)
   • Barabási–Albert ($BA(n,m)$)
   • Watts–Strogatz ($WS(n,k,p)$)
   • Random Regular ($RR(n,d)$)
   • Parameters were constrained to $n \in [10, 60]$ with fixed random seeds for reproducibility.

2. Invariant Computation: For each graph, the authors computed basic invariants ($n, m, \Delta, \delta$), structural invariants (chromatic number $\chi$, clique number $\omega$, independence number $\alpha$, matching number $\nu$), and spectral invariants ($\lambda_1$). Exact algorithms were used where computationally feasible ($n \le 30$ or $n \le 40$), with greedy approximations for larger instances.

3. Symbolic Regression: Using the PySR library (based on genetic programming), the authors searched for mathematical expressions fitting the data. The search space included binary operators ($+, -, \times, \div$) and unary operators ($\sqrt{}, \exp, \log$) with a maximum complexity of 10. Regressions were run to predict various invariants, with a specific focus on $\gamma$ as a function of $n, m, \Delta, \lambda_1, \omega, \alpha, \nu$.

4. Filtering and Validation: Candidate formulas were screened against known literature bounds and tested on canonical graphs (e.g., $K_n, C_n, S_n$). Surviving candidates underwent rigorous "counterexample hunting," including:

   • Testing on fresh graph generations (different seeds).
   • Testing on extremal families (complete, bipartite, cycles, paths, stars, hypercubes, wheels).
   • Adversarial search (hill-climbing to maximize violation).

5. Model Refitting: The most promising candidate identified by symbolic regression was refitted using scipy.optimize.curve_fit to optimize coefficients.

Key Results
The symbolic regression process identified a specific empirical relationship:
$$\gamma(G) \approx \frac{1.53n}{\lambda_1(G) + 1.55}$$

• Overall Performance: On the full dataset of 3,429 graphs, the model achieved an $R^2$ of 0.9609, with a Mean Absolute Error (MAE) of 0.6633 and RMSE of 0.9186.
• Family-wise Performance: The relationship generalized well across the four training families, with $R^2$ values ranging from 0.89 (Barabási–Albert) to 0.96 (Random Regular).
• Failure Analysis: The model was explicitly tested on extremal graph families to characterize its domain of validity:
  • Complete Graphs ($K_n$): The formula systematically overestimates $\gamma$ by approximately 40–50% (predicting ~1.5 instead of 1).
  • Star Graphs ($S_n$): The model fails catastrophically, with relative errors exceeding 400% for $n=20$. The hub structure leads to trivial domination ($\gamma=1$) despite moderate spectral radii, causing severe overestimation.
  • Path and Cycle Graphs: Performance is moderate, with errors ranging from 10% to 30%, generally overestimating $\gamma$.
• Survival: Among several candidates generated (including relationships for $\omega$, $\alpha$, and $\chi$), the spectral-domination relationship was the only one to survive counterexample hunting with reasonable error bounds on non-extremal graphs.

Significance and Claims
The paper positions this work as a case study in "Data-Driven Mathematics" and "Scientific Machine Learning," rather than a definitive theoretical proof.

• Methodological Contribution: The authors demonstrate that ML-guided symbolic regression can successfully identify promising empirical relationships between complex graph invariants that might be non-obvious to human researchers.
• Empirical Contribution: The paper provides a specific, characterized formula: $\gamma(G) \approx 1.53n/(\lambda_1(G) + 1.55)$.
• Modest Claims: The authors explicitly state that this is an empirical model, not a theorem. They do not claim universal validity, theoretical proof, or exact characterization.
  • The constants (1.53 and 1.55) currently lack theoretical justification; attempts to derive them from classical bounds (e.g., combining $\gamma \ge n/(\Delta+1)$ and $\lambda_1 \le \Delta$) failed to reproduce the specific values.
  • The relationship is valid primarily for graphs with moderate density and no giant hubs.
• Future Directions: The paper suggests that the identified relationship serves as a starting point for theoretical investigation, specifically questioning whether the constants have structural interpretations and whether tighter bounds can be derived for restricted graph classes.

In summary, the paper successfully uses machine learning to generate a high-fidelity empirical conjecture regarding the inverse relationship between spectral radius and domination number, while rigorously defining the boundaries where this conjecture fails.