Stochastic Sequential Decision Making over Expanding Networks with Graph Filtering
Authors: Zhan Gao, Bishwadeep Das, Elvin Isufi
Organizations: Department of Computer Science and Technology, University of Cambridge, Cambridge, UK. · Faculty of EEMCS, Delft University of Technology, The Netherlands.
Graph filters leverage topological information to process networked data with existing methods mainly studying fixed graphs, ignoring that graphs often expand as nodes continually attach with an unknown pattern. The latter requires developing filter-based decision-making paradigms that take evolution and uncertainty into account. Existing approaches rely on either pre-designed filters or online learning, limited to a myopic view considering only past or present information. To account for future impacts, we propose a stochastic sequential decision-making framework for filtering networked data with a policy that adapts filtering to expanding graphs. By representing filter shifts as agents, we model the filter as a multi-agent system and train the policy following multi-agent reinforcement learning. This accounts for long-term rewards and captures expansion dynamics through sequential decision-making. Moreover, we develop a context-aware graph neural network to parameterize the policy, which tunes filter parameters based on information of both the graph and agents. Experiments on synthetic and real datasets from cold-start recommendation to COVID prediction highlight the benefits of using a sequential decision-making perspective over batch and online filtering alternatives.
Fig. 2 : (a) Training convergence of G-MARL. (b) Performance comparison for synthetic data. (c) Generalization of G-MARL to unseen scenarios. (d) Performance comparison for recommender systems. (e) Performance comparison for COVID predication.
Graph Neural Networks (GNNs) are widely used in modern machine learning, yet most existing frameworks remain fundamentally static, limiting their applicability in Dynamic Data Driven Application Systems (DDDAS) where observations arrive sequentially under uncertainty. We introduce B-EAGLe (Bayesian Evidence Accumulation for Graph-Based Learning), a probabilistic framework inspired by CBGT-Net (cortico-basal ganglia-thalamic network) that reformulates graph classification as a sequential evidence accumulation process. B-EAGLe combines a GNN encoder with a Bayesian accumulator that incrementally updates posterior beliefs over class labels as new observations arrive, committing to a decision only when sufficient confidence is achieved. Experiments on CIFAR10 demonstrate competitive performance together with principled confidence estimation under sequential observations.
Moises Ponce, Sarah Harkins Dayton, Ioannis Schizas +1
University of Tennessee, Knoxville TN 37996, USA · US Army Combat Capabilities Development Command, Army Research Laboratory, Adelphi MD 20783, USA
We address the problem of inferring a directed network from nodal measurements generated by linear diffusion dynamics on the sought graph. Observations are modeled as the outputs of a graph convolutional filter, i.e., a polynomial (with unknown coefficients) of a local diffusion graph-shift operator encoding the latent graph topology, excited with an ensemble of independent graph signals with arbitrarily-correlated nodal components. Unlike prior efforts that considered undirected graphs and white signal excitations, here the graph-shift operator and the observations' covariance matrix are not simultaneously diagonalizable. In this challenging context, we first rely on measurements of the output signals along with prior statistical information on the inputs to identify the diffusion filter. Such system identification problem involves solving a system of quadratic matrix equations, which we show is identifiable under spectral-diversity assumptions on the input covariances. For algorithmic purposes we recast it as a smooth quadratic minimization subject to Stiefel manifold constraints. Subsequent identification of the network topology given the graph filter estimate boils down to finding a sparse and structurally admissible shift that commutes with the given filter, thus, forcing the latter to be a polynomial in the sought graph-shift operator. A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps in a mutually reinforcing fashion to offer improved sample complexity. Numerical tests corroborate the effectiveness of the proposed algorithms in recovering synthetic digraphs and real-data case studies, and illustrate their potential utility on urban mobility analyses as well as portfolio optimization.
Rasoul Shafipour, Andrei Buciulea, Santiago Segarra +2
NVIDIA · Dept. of Signal Theory and Comms., King Juan Carlos University · Dept. of Electrical and Computer Eng., Rice University +1
Graph signal processing tasks that leverage spectral information typically assume access to the complete graph topology, which is often unavailable in practice. We propose a systematic framework for subgraph filter learning (SFL), where subgraph-supported operators approximate ambient graph filters under partial observations. We formulate SFL as a statistical learning problem in which optimal subgraph operators are inherently data-dependent. To address the difficulty of directly estimating such operators, we develop a subgraph filter algebra based on distance-aware Laplacian constructions, defining a structured and controllable class of filters for effective approximation. We further establish performance risk bounds under the least squares loss, quantifying how well the learned operator approximates the restricted ambient mapping. Experiments real-world datasets show that, for SFL tasks, the proposed algebraic models consistently outperform polynomial filters, distribution-agnostic operators, and direct numerical filter learning baselines that attempt to recover the underlying structure from data.