Graph Neural Networks (GNNs) and Graph Signal Processing (GSP) have revolutionized how we model relational data. By injecting a relational inductive bias—the knowledge of who connects to whom—these frameworks allow models to smooth features, propagate messages, and exploit network structures.
However, these architectures suffer from a glaring vulnerability: they traditionally require an explicit, predefined graph structure. In many real-world applications, we possess rich observational data but lack a wiring diagram. For instance, in multivariate time series forecasting, we observe multiple sensors ticking over time, but the underlying dependencies between them are hidden.
Historically, practitioners bypassed this by constructing a graph using manual heuristics, such as calculating a k-nearest neighbors (k-NN) graph based on raw feature distances. But manual graphs are static, noisy, and often fail to capture the true underlying dynamics of the system. Latent topology inference solves this by treating the graph structure not as a fixed input, but as a learnable, latent variable that is co-optimized alongside the downstream task.
The Intuition: Task-Driven Co-Optimization
Why does learning a graph topology from scratch actually work? The core insight is that the downstream task acts as a regularizer for the graph structure.
If you try to learn a graph structure in isolation based purely on statistical correlation, you often end up with noisy, dense matrices that capture spurious associations. But when you optimize the graph topology jointly with a specific objective—like classification or forecasting—the model only retains edges that facilitate useful information flow.
[Raw Data] ───> [Latent Graph Inference Layer] ───> [Learned Topology]
│
▼
[Loss / Task Feedback] <─── [Downstream GNN Task] <─────────┘
Consider semi-supervised learning. Traditional methods rely on a fixed graph to smooth labels across neighbors. Bo Jiang et al. proposed the Graph Learning-Convolutional Network (GLCN) in Semi-Supervised Learning With Graph Learning-Convolutional Networks, which learns an optimal graph representation and performs convolutions simultaneously. By integrating feedback from both given and estimated labels, the network prunes away unhelpful connections, allowing relational learning to succeed even on independent image collections where no natural graph exists.
Similarly, in high-dimensional regression, Makoto Yamada et al. introduced the Localized Lasso in Localized Lasso for High-Dimensional Regression, demonstrating that integrating automated graph-learning techniques directly into the optimization process allows the model to infer sample similarities dynamically, rather than relying on a manually specified graph.
Overcoming the Differentiability Bottleneck
The primary technical challenge of latent topology inference is discrete optimization. A graph edge either exists ($1$) or it doesn't ($0$). Discrete graphs are non-differentiable, meaning we cannot use standard backpropagation to update the edge weights based on the task loss.
Researchers have engineered several clever workarounds to make graph discovery fully end-to-end trainable:
1. Continuous Relaxations and Agreement Functions
Instead of predicting a binary adjacency matrix, models can infer a fully connected graph with continuous edge weights that represent "agreement" or similarity. Otilia Stretcu et al. developed Graph Agreement Models (GAM) in Graph Agreement Models for Semi-Supervised Learning, where an auxiliary model learns to predict whether two data points should share the same label. This induces a latent relational structure across the entire dataset, creating a continuous topology that can be optimized directly.
2. Differentiable Sampling Tricks
In scenarios where a sparse, discrete graph is strictly necessary, researchers employ stochastic sampling tricks. In Discrete Graph Structure Learning for Forecasting Multiple Time Series, Chao Shang et al. utilized a differentiable sampling mechanism to parameterize the graph generation process. This allows the model to sample discrete graph structures during the forward pass while maintaining a smooth gradient flow during the backward pass, enabling the system to learn hidden dependencies between variables while simultaneously training the forecasting model.
3. Adaptive Message Passing
Another approach is to bypass explicit edge generation altogether and treat the message-passing steps themselves as an implicit optimization problem. Zepeng Zhang et al. introduced this in ASGNN: Graph Neural Networks with Adaptive Structure, where GNN layers dynamically denoise node features and the graph structure in tandem, allowing latent graph discovery to occur even when no initial connectivity information is provided.
Broad Applications: From Time Series to Bandits
The ability to discover latent structures has unlocked new capabilities across diverse machine learning paradigms:
- Multivariate Time Series: Zonghan Wu et al. developed MTGNN in Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks, which automatically extracts hidden dependencies between distinct time-series variables without an explicit graph, outperforming traditional forecasting models by injecting an optimized relational bias.
- Online Learning and Bandits: In reinforcement learning, graphical bandits assume that pulling one arm reveals information about neighboring arms. Fang Liu proved in Analysis of Thompson Sampling for Graphical Bandits Without the Graphs that Thompson Sampling remains optimal even when the underlying feedback graph is entirely latent, forcing the algorithm to navigate the exploration-exploitation trade-off while implicitly adapting to hidden network structures.
- System Dynamics and Physics: Beyond simple classification, latent topology inference allows models to discover the fundamental laws of physical systems. Jiao Hu demonstrated in Learning interpretable network dynamics via universal neural symbolic regression that it is possible to simultaneously infer both an underlying network structure and the governing mathematical differential equations directly from raw observational data.
By shifting the graph from a rigid prerequisite to a flexible, learnable component, latent topology inference bridges the gap between unstructured data and structured relational reasoning.