Online Filtering over Expanding Graphs
Data processing tasks over graphs couple the data residing over the nodes with the topology through graph signal processing tools. Graph filters are one such prominent tool, having been used in applications such as denoising, interpolation, and classification. However, they are mainly used on fixed graphs although many networks grow in practice, with nodes continually attaching to the topology. Re-training the filter every time a new node attaches is computationally demanding; hence an online learning solution that adapts to the evolving graph is needed. We propose an online update of the filter, based on the principles of online machine learning. To update the filter, we perform online gradient descent, which has a provable regret bound with respect to the filter computed offline. We show the performance of our method for signal interpolation at the incoming nodes. Numerical results on synthetic and graph-based recommender systems show that the proposed approach compares well to the offline baseline filter while outperforming competitive approaches. These findings lay the foundation for efficient filtering over expanding graphs.
Code (0)
등록된 구현이 없습니다.
Tasks
DenoisingRecommendation SystemsSimilar Papers 제목 키워드 기반
Stochastic Sequential Decision Making over Expanding Networks with Graph Filtering
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 latt…
Multi-agent Reinforcement LearningGraph Neural NetworkDecision MakingOnline Graph Filtering Over Expanding Graphs
Graph filters are a staple tool for processing signals over graphs in a multitude of downstream tasks. However, they are commonly designed for graphs with a fixed number of nodes, despite real-world networks typically gr…
Graph filtering over expanding graphs
Our capacity to learn representations from data is related to our ability to design filters that can leverage their coupling with the underlying domain. Graph filters are one such tool for network data and have been used…
DenoisingA Filtering-based General Approach to Learning Rational Constraints of Epistemic Graphs
Epistemic graphs are a generalization of the epistemic approach to probabilistic argumentation. Hunter proposed a 2-way generalization framework to learn epistemic constraints from crowd-sourcing data. However, the learn…
Computational EfficiencyOn Approximate Nonlinear Gaussian Message Passing On Factor Graphs
Factor graphs have recently gained increasing attention as a unified framework for representing and constructing algorithms for signal processing, estimation, and control. One capability that does not seem to be well exp…