Filter Learning for Subgraphs: Algebras and Performance Risk Bounds

• URL: http://arxiv.org/abs/2607.21263v1
• Date: Thu, 23 Jul 2026 12:36:05 GMT
• Title: Filter Learning for Subgraphs: Algebras and Performance Risk Bounds
• Abstract summary: We propose a framework for subgraph filter learning, where subgraph-supported operators approximate ambient graph filters under partial observations.<n>We develop a subgraph filter algebra based on distance-aware Laplacian constructions, defining a structured and controllable class of filters for effective approximation.
• Score: 63.46320825598287
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Directed Graph Topology Inference via Graph Filter Identification [54.541275287889164]
  We address the problem of inferring a directed network from nodal measurements generated by a graph convolutional filter.<n>A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps to offer improved sample complexity.
  arXiv  Detail & Related papers  (2026-06-25T18:25:57Z)
• Enhancing Spectral Graph Neural Networks with LLM-Predicted Homophily [48.135717446964385]
  Spectral Graph Neural Networks (SGNNs) have achieved remarkable performance in tasks such as node classification.<n>We propose a novel framework that leverages Large Language Models (LLMs) to estimate the homophily level of a graph.<n>Our framework consistently improves performance over strong SGNN baselines.
  arXiv  Detail & Related papers  (2025-06-17T06:17:19Z)
• Graph-Based Operator Learning from Limited Data on Irregular Domains [17.225653683970393]
  Operator learning seeks to approximate mappings from input functions to output solutions, particularly in the context of partial differential equations (PDEs)<n>We propose a Graph-based Operator Learning with Attention (GOLA) framework that addresses this limitation by constructing graphs from irregularly sampled spatial points and leveraging attention-enhanced Graph Neural Netwoks (GNNs)<n>Our method consistently outperforms baselines, particularly in data-scarce regimes, demonstrating strong generalization and efficiency on irregular domains.
  arXiv  Detail & Related papers  (2025-05-25T01:06:32Z)
• Graph filtering over expanding graphs [14.84852576248587]
  We propose a filter learning scheme for data over expanding graphs. We show near-optimal performance compared with baselines relying on the exact topology. These findings lay the foundation for learning representations over expanding graphs by relying only on the connectivity model.
  arXiv  Detail & Related papers  (2022-03-15T16:50:54Z)
• Message Passing in Graph Convolution Networks via Adaptive Filter Banks [81.12823274576274]
  We present a novel graph convolution operator, termed BankGCN. It decomposes multi-channel signals on graphs into subspaces and handles particular information in each subspace with an adapted filter. It achieves excellent performance in graph classification on a collection of benchmark graph datasets.
  arXiv  Detail & Related papers  (2021-06-18T04:23:34Z)
• FiGLearn: Filter and Graph Learning using Optimal Transport [49.428169585114496]
  We introduce a novel graph signal processing framework for learning the graph and its generating filter from signal observations. We show how this framework can be used to infer missing values if only very little information is available.
  arXiv  Detail & Related papers  (2020-10-29T10:00:42Z)
• Graph Embedding with Data Uncertainty [113.39838145450007]
  spectral-based subspace learning is a common data preprocessing step in many machine learning pipelines. Most subspace learning methods do not take into consideration possible measurement inaccuracies or artifacts that can lead to data with high uncertainty.
  arXiv  Detail & Related papers  (2020-09-01T15:08:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.