A Fast Algorithm for the Finite Expression Method in Learning Dynamics on Complex Networks

Technical Summary: A Fast Algorithm for the Finite Expression Method in Learning Dynamics on Complex Networks

Problem Statement
The paper addresses the challenge of discovering governing physical laws and dynamic interactions within complex network systems from time-series data. While data-driven methods have advanced in uncovering equations for continuous systems (e.g., PDEs), extracting dynamics from network data remains difficult due to three primary factors:

1. Computational Complexity: In a network with $N$ nodes, modeling full pairwise interactions typically results in $O(N^2)$ complexity, which is prohibitive for large-scale real-world networks.
2. Data Quality: Real-world network data is often noisy, sparse, and may contain topological inaccuracies (missing or spurious links).
3. Interpretability and Prior Knowledge: Existing methods like SINDy (Sparse Identification of Nonlinear Dynamics) often require large libraries of candidate functions and direct access to time derivatives, which are frequently unavailable. Deep learning approaches (e.g., Graph Neural Networks) lack interpretability, functioning as "black boxes."

Methodology: The Finite Expression Method (FEX)
The authors propose the Finite Expression Method (FEX), a novel approach that represents network dynamics using binary trees composed of finite mathematical operators. The system dynamics are modeled as:
$$\frac{dx_i(t)}{dt} = F(x_i(t)) + \sum_{j=1}^N A_{ij}G(x_i(t), x_j(t))$$
where $F$ represents self-dynamics and $G$ represents interaction dynamics.

Key Components of FEX:

• Binary Tree Representation: Dynamics are encoded as binary trees where nodes are mathematical operators (unary: $\sin, \cos, \exp$; binary: $+, -, \times$). Leaf nodes operate on input variables with learnable weights and biases. This structure allows for the generation of complex functional compositions from a small dictionary of operators, reducing the need for large pre-defined libraries.
• Combinatorial Optimization via Reinforcement Learning (RL): Identifying the optimal tree structure is framed as a combinatorial optimization problem. A controller network (a fully connected neural network) is trained using a policy gradient approach to output probability mass functions for operator selection at each tree node. The goal is to sample operator sequences that maximize a reward score.
• Stochastic Algorithm for Scalability: To overcome the $O(N^2)$ bottleneck of calculating pairwise interactions, FEX integrates a stochastic algorithm inspired by Random Batch Methods. During the optimization of the loss function, nodes are grouped into random batches, and interactions are computed only within these batches. This reduces the computational complexity of the structure discovery phase from $O(N^2)$ to $O(N)$.
• Two-Phase Optimization:
  1. Coarse-tuning: The controller is trained to find high-scoring operator sequences using a mix of first-order (e.g., Adam) and second-order (e.g., BFGS) optimization on the continuous parameters, utilizing the stochastic batch approach for speed.
  2. Fine-tuning: Once top-performing candidate structures are identified, the coefficients are refined using the full interaction model to ensure high accuracy.

Key Contributions

1. Novel Representation: FEX utilizes a binary tree structure to represent dynamics, allowing for the discovery of complex equations with a minimal dictionary of operators, unlike SINDy which relies on extensive candidate libraries.
2. Derivative-Free Estimation: The method estimates time derivatives directly from noisy time-series data using numerical differentiation, removing the requirement for direct access to derivatives that plagues many existing methods.
3. Scalability: By employing a stochastic selection of particle batches during the combinatorial optimization phase, the algorithm achieves linear scaling ($O(N)$) in computational cost, making it feasible for large networks.
4. Robustness: The method is designed to handle low-resolution data, observational noise, and topological inaccuracies (missing or spurious links).

Experimental Results
The authors evaluated FEX on three classical dynamical systems (Hindmarsh-Rose, FitzHugh-Nagumo, and coupled Rössler oscillators) across various network topologies, including Erdős-Rényi and Scale-Free networks.

• Accuracy: FEX successfully identified the correct functional forms and coefficients (with relative errors often <1%) for all tested dynamics.
• Noise Robustness: In experiments with Signal-to-Noise Ratios (SNR) of 40 and 45, FEX outperformed baseline methods (Two-Phase SINDy and ARNI), which struggled to identify correct terms or produced redundant terms under noisy conditions.
• Topological Robustness: FEX maintained high accuracy even when 15% of network links were randomly added or removed.
• Data Scarcity: The method remained effective with only 5% to 10% of the original time-series data available.
• Efficiency: Log-log plots of computation time versus network size demonstrated that the stochastic-FEX algorithm scales linearly ($O(N)$), whereas the full interaction model scales quadratically ($O(N^2)$).

Significance and Claims
The paper claims that FEX provides a robust, interpretable, and computationally efficient framework for learning dynamics on complex networks. By combining reinforcement learning for structural search with stochastic optimization for scalability, FEX addresses the limitations of current methods regarding computational cost, data quality, and the need for extensive prior knowledge. The authors assert that this approach enables the discovery of physical laws in real-world complex systems where governing equations are previously unknown or underexplored, offering a pathway to analyze systems in domains ranging from biology to epidemiology. The work acknowledges limitations, such as the current focus on pairwise interactions and deterministic dynamics, noting that extensions to higher-order couplings and stochastic differential equations are potential future directions.