Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution

• URL: http://arxiv.org/abs/2302.03933v1
• Date: Wed, 8 Feb 2023 08:17:43 GMT
• Title: Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution
• Authors: Chao Chen, Haoyu Geng, Gang Zeng, Zhaobing Han, Hua Chai, Xiaokang Yang, Junchi Yan
• Abstract summary: We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
• Score: 112.3443939502313
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Inductive one-bit matrix completion is motivated by modern applications such as recommender systems, where new users would appear at test stage with the ratings consisting of only ones and no zeros. We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph, then learn structural graph properties to recover the function from its values on certain vertices -- the problem of graph signal sampling. We propose a class of regularization functionals that takes into account discrete random label noise in the graph vertex domain, then develop the GS-IMC approach which biases the reconstruction towards functions that vary little between adjacent vertices for noise reduction. Theoretical result shows that accurate reconstructions can be achieved under mild conditions. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain and builds upon a prediction-correction update algorithm to obtain the unbiased and minimum-variance reconstruction. Both GS-IMC and BGS-IMC have closed-form solutions and thus are highly scalable in large data. Experiments show that our methods achieve state-of-the-art performance on public benchmarks.

Related papers

• Graph Laplacian Learning with Exponential Family Noise [8.594140167290098]
  We propose a versatile graph inference framework for learning from graph signals corrupted by exponential family noise. Our framework generalizes previous methods from continuous smooth graph signals to various data types.
  arXiv  Detail & Related papers  (2023-06-14T02:09:52Z)
• Inhomogeneous graph trend filtering via a l2,0 cardinality penalty [10.62929792074829]
  We propose a $ell_2,0$-norm penalized Graph Trend Filtering (GTF) model to estimate piecewise smooth graph signals. We show that the proposed GTF model can be solved more efficiently than existing models for the dataset with a large edge set.
  arXiv  Detail & Related papers  (2023-04-11T13:46:59Z)
• From Spectral Graph Convolutions to Large Scale Graph Convolutional Networks [0.0]
  Graph Convolutional Networks (GCNs) have been shown to be a powerful concept that has been successfully applied to a large variety of tasks. We study the theory that paved the way to the definition of GCN, including related parts of classical graph theory.
  arXiv  Detail & Related papers  (2022-07-12T16:57:08Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Graph Denoising with Framelet Regularizer [25.542429117462547]
  This paper tailors regularizers for graph data in terms of both feature and structure noises. Our model achieves significantly better performance compared with popular graph convolutions even when the graph is heavily contaminated.
  arXiv  Detail & Related papers  (2021-11-05T05:17:23Z)
• Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
  Graph signal processing is a ubiquitous task in many applications such as sensor, social transportation brain networks, point cloud processing, and graph networks. We propose two restoration methods based on convexindependent deep ADMM (ADMM) parameters in the proposed restoration methods are trainable in an end-to-end manner.
  arXiv  Detail & Related papers  (2021-06-30T08:57:01Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• Robust Optimization as Data Augmentation for Large-scale Graphs [117.2376815614148]
  We propose FLAG (Free Large-scale Adversarial Augmentation on Graphs), which iteratively augments node features with gradient-based adversarial perturbations during training. FLAG is a general-purpose approach for graph data, which universally works in node classification, link prediction, and graph classification tasks.
  arXiv  Detail & Related papers  (2020-10-19T21:51:47Z)
• Heuristic Semi-Supervised Learning for Graph Generation Inspired by Electoral College [80.67842220664231]
  We propose a novel pre-processing technique, namely ELectoral COllege (ELCO), which automatically expands new nodes and edges to refine the label similarity within a dense subgraph. In all setups tested, our method boosts the average score of base models by a large margin of 4.7 points, as well as consistently outperforms the state-of-the-art.
  arXiv  Detail & Related papers  (2020-06-10T14:48:48Z)
• Sample Efficient Graph-Based Optimization with Noisy Observations [17.91308664586981]
  We show that a variant of best-arm identification can find a near-optimal solution after a small number of queries independent of the size of the graph. We show effectiveness of the greedy algorithm with restarts and the simulated annealing on problems of graph-based nearest neighbor classification.
  arXiv  Detail & Related papers  (2020-06-04T07:22:28Z)

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.