Search papers, labs, and topics across Lattice.
This paper introduces a systematic framework for subgraph filter learning (SFL) that enables the approximation of ambient graph filters using only partial observations of the graph topology. By formulating SFL as a statistical learning problem and developing a distance-aware Laplacian-based algebra, the authors create a structured class of filters that effectively approximate the desired operators. Experimental results demonstrate that these algebraic models significantly outperform traditional polynomial filters and other baseline methods in real-world datasets, establishing robust performance risk bounds under least squares loss.
Subgraph filter learning can achieve superior performance over traditional methods, even with incomplete graph information.
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.
