Graph filtering over expanding graphs

• URL: http://arxiv.org/abs/2203.08058v1
• Date: Tue, 15 Mar 2022 16:50:54 GMT
• Title: Graph filtering over expanding graphs
• Authors: Bishwadeep Das, Elvin Isufi
• Abstract summary: 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.
• Score: 14.84852576248587
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 in a myriad of applications. But graph filters work only with a fixed number of nodes despite the expanding nature of practical networks. Learning filters in this setting is challenging not only because of the increased dimensions but also because the connectivity is known only up to an attachment model. We propose a filter learning scheme for data over expanding graphs by relying only on such a model. By characterizing the filter stochastically, we develop an empirical risk minimization framework inspired by multi-kernel learning to balance the information inflow and outflow at the incoming nodes. We particularize the approach for denoising and semi-supervised learning (SSL) over expanding graphs and show near-optimal performance compared with baselines relying on the exact topology. For SSL, the proposed scheme uses the incoming node information to improve the task on the existing ones. These findings lay the foundation for learning representations over expanding graphs by relying only on the stochastic connectivity model.

Related papers

• SPGNN: Recognizing Salient Subgraph Patterns via Enhanced Graph Convolution and Pooling [25.555741218526464]
  Graph neural networks (GNNs) have revolutionized the field of machine learning on non-Euclidean data such as graphs and networks. We propose a concatenation-based graph convolution mechanism that injectively updates node representations. We also design a novel graph pooling module, called WL-SortPool, to learn important subgraph patterns in a deep-learning manner.
  arXiv  Detail & Related papers  (2024-04-21T13:11:59Z)
• Online Filtering over Expanding Graphs [14.84852576248587]
  We propose an online update of the filter, based on the principles of online machine learning. We show the performance of our method for signal at the incoming nodes. These findings lay the foundation for efficient filtering over expanding graphs.
  arXiv  Detail & Related papers  (2023-01-17T14:07:52Z)
• Graph Filters for Signal Processing and Machine Learning on Graphs [83.29608206147515]
  We provide a comprehensive overview of graph filters, including the different filtering categories, design strategies for each type, and trade-offs between different types of graph filters. We discuss how to extend graph filters into filter banks and graph neural networks to enhance the representational power. Our aim is that this article provides a unifying framework for both beginner and experienced researchers, as well as a common understanding.
  arXiv  Detail & Related papers  (2022-11-16T11:56:45Z)
• Learning Optimal Graph Filters for Clustering of Attributed Graphs [20.810096547938166]
  Many real-world systems can be represented as graphs where the different entities in the system are presented by nodes and their interactions by edges. An important task in studying large datasets with graphical structure is graph clustering. We introduce a graph signal processing based approach, where we learn the parameters of Finite Impulse Response (FIR) and Autoregressive Moving Average (ARMA) graph filters optimized for clustering.
  arXiv  Detail & Related papers  (2022-11-09T01:49:23Z)
• 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)
• GraphMI: Extracting Private Graph Data from Graph Neural Networks [59.05178231559796]
  We present textbfGraph textbfModel textbfInversion attack (GraphMI), which aims to extract private graph data of the training graph by inverting GNN. Specifically, we propose a projected gradient module to tackle the discreteness of graph edges while preserving the sparsity and smoothness of graph features. We design a graph auto-encoder module to efficiently exploit graph topology, node attributes, and target model parameters for edge inference.
  arXiv  Detail & Related papers  (2021-06-05T07:07:52Z)
• Graph Neural Networks with Adaptive Frequency Response Filter [55.626174910206046]
  We develop a graph neural network framework AdaGNN with a well-smooth adaptive frequency response filter. We empirically validate the effectiveness of the proposed framework on various benchmark datasets.
  arXiv  Detail & Related papers  (2021-04-26T19:31:21Z)
• 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)
• Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks [183.97265247061847]
  We leverage graph signal processing to characterize the representation space of graph neural networks (GNNs) We discuss the role of graph convolutional filters in GNNs and show that any architecture built with such filters has the fundamental properties of permutation equivariance and stability to changes in the topology. We also study the use of GNNs in recommender systems and learning decentralized controllers for robot swarms.
  arXiv  Detail & Related papers  (2020-03-08T13:02:15Z)

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.