Graph Topology Inference With Derivative-Reproducing Property in RKHS: Algorithm and Convergence Analysis

Mircea Moscu, Ricardo Augusto Borsoi, Cédric Richard, José Carlos M. BermudezIEEE Trans. Signal Inf. Process. Over Networks 2021 · DOI · OpenReview

Abstract

In many areas such as computational biology, finance or social sciences, knowledge of an underlying graph explaining the interactions between agents is of paramount importance but still challenging. Considering that these interactions may be based on nonlinear relationships adds further complexity to the topology inference problem. Among the latest methods that respond to this need is a topology inference one proposed by the authors, which estimates a possibly directed adjacency matrix in an online manner. Contrasting with previous approaches based on linear models, the considered model is able to explain nonlinear interactions between the agents in a network. The novelty in the considered method is the use of a derivative-reproducing property to enforce network sparsity, while reproducing kernels are used to model the nonlinear interactions. The aim of this paper is to present a thorough convergence analysis of this method. The analysis is proven to be sane both in the mean and mean square sense. In addition, stability conditions are devised to ensure the convergence of the analyzed method.

Introduction

In fields ranging from neuroscience to finance, researchers often observe signals from various "agents"—such as neurons or stock prices—without knowing the underlying network structure that connects them. This challenge, known as the graph topology inference problem, is central to understanding complex systems. While traditional tools effectively map linear relationships, real-world interactions are rarely so simple. Nonlinearity introduces significant complexity, and the inherent sparsity of most networks—where most nodes are not directly connected—requires algorithms that can distinguish meaningful signals from noise.

This paper provides a rigorous mathematical foundation for an online algorithm designed to map these hidden connections. By leveraging derivative-reproducing properties within Reproducing Kernel Hilbert Spaces (RKHS), the method identifies nonlinear relationships while enforcing network sparsity. The primary contribution of this work is a comprehensive convergence analysis, proving that the algorithm reliably settles on the correct topology in both mean and mean-square senses.

Methodology

Nonlinear Modeling via Kernels

Rather than assuming a linear relationship ($y = Ax$), the framework models the signal at any given node as a nonlinear function of its neighbors. By employing Reproducing Kernel Hilbert Spaces (RKHS), the algorithm can map data into high-dimensional feature spaces where complex interactions become mathematically tractable.

The Derivative-Reproducing Property

The core innovation lies in using partial derivatives as proxies for connectivity. To determine if an edge exists between node $m$ and node $n$, the algorithm evaluates the partial derivative of the signal at $n$ with respect to the signal at $m$. If this derivative is zero on average, no functional connection exists. The authors utilize a specific property of kernels that allows them to penalize these derivatives directly, effectively "pruning" the graph to ensure sparsity without sacrificing the ability to model nonlinearities.

Online Learning and Complexity Management

To ensure scalability, the system utilizes an online subgradient descent update rule. As new data arrives, the estimate of the adjacency matrix is updated iteratively, removing the need to re-process the entire data history. To prevent the computational costs associated with kernel methods from exploding, the algorithm maintains a "dictionary" of representative data points, capping the complexity of the model as the dataset grows.

Convergence Analysis

The heart of this research is the mathematical proof of the algorithm's stability. The authors perform a detailed analysis to ensure that the estimation error shrinks over time. Key components of this analysis include:

  • Mean Convergence: Proving that, on average, the estimated coefficients of the model converge to their optimal values.
  • Mean-Square Stability: Demonstrating that the variance of the estimation error remains bounded, preventing the algorithm from fluctuating wildly or diverging once it reaches a steady state.
  • Stability Conditions: The derivation of specific "step-size" limits. These mathematical bounds provide practitioners with the necessary constraints to ensure the algorithm remains stable during the update process.

Experimental Validation

The authors validated their theoretical models using synthetic datasets, allowing for a direct comparison between the algorithm's output and the known "ground truth."

  1. Linear Graph Model: A 5-node graph with Gaussian noise served as a baseline. The results confirmed that the theory aligns perfectly with the simplest linear cases.
  2. Highly Nonlinear Model: A 3-node graph featuring complex, non-polynomial functions (including exponential and power terms) tested the algorithm's limits. Even under these extreme conditions and high-noise environments, the algorithm successfully identified directed edges and correctly identified the absence of non-existent links.

Insights and Results

The study reveals a high degree of alignment between theoretical "learning curves" and experimental results. This suggests that the simplifying assumptions used in the proof—such as the Modified Independence Assumption—are robust enough for practical application. Furthermore, the derivative-based approach proved to be a physically meaningful metric for influence, outperforming simple correlation coefficients in nonlinear scenarios.

Limitations and Future Work

While the algorithm performed well on non-Gaussian data in experiments, the current mathematical proof relies heavily on Gaussian assumptions. Future research may focus on broadening the theoretical framework to include non-Gaussian distributions. Additionally, the current analysis assumes a stationary network; adapting the algorithm to handle dynamic topologies—where connections change over time—remains a significant area for future exploration. Finally, investigating "evolving" dictionaries that adaptively add or remove points could further enhance the algorithm's flexibility in real-time applications.

Summary updated

Abstract

In many areas such as computational biology, finance or social sciences, knowledge of an underlying graph explaining the interactions between agents is of paramount importance but still challenging. Considering that these interactions may be based on nonlinear relationships adds further complexity to the topology inference problem. Among the latest methods that respond to this need is a topology inference one proposed by the authors, which estimates a possibly directed adjacency matrix in an online manner. Contrasting with previous approaches based on linear models, the considered model is able to explain nonlinear interactions between the agents in a network. The novelty in the considered method is the use of a derivative-reproducing property to enforce network sparsity, while reproducing kernels are used to model the nonlinear interactions. The aim of this paper is to present a thorough convergence analysis of this method. The analysis is proven to be sane both in the mean and mean square sense. In addition, stability conditions are devised to ensure the convergence of the analyzed method.
BibTeX
@article{moscu2021graph,
  author = {Mircea Moscu and Ricardo Augusto Borsoi and Cédric Richard and José Carlos M. Bermudez},
  title = {{Graph Topology Inference With Derivative-Reproducing Property in RKHS: Algorithm and Convergence Analysis}},
  journal = {IEEE Trans. Signal Inf. Process. Over Networks},
  year = {2021},
  doi = {10.48550/arxiv.2104.13687},
}
Figure