Gradient scarcity with Bilevel Optimization for Graph Learning

• URL: http://arxiv.org/abs/2303.13964v1
• Date: Fri, 24 Mar 2023 12:37:43 GMT
• Title: Gradient scarcity with Bilevel Optimization for Graph Learning
• Authors: Hashem Ghanem (IMB), Samuel Vaiter (CNRS, JAD), Nicolas Keriven (CNRS, IRISA)
• Abstract summary: gradient scarcity occurs when learning graphs by minimizing a loss on a subset of nodes causes edges between unlabelled nodes that are far from labelled ones to receive zero gradients. We give a precise mathematical characterization of this phenomenon, and prove it also emerges in bilevel optimization. To alleviate this issue, we study several solutions: we propose to resort to latent graph learning using a Graph-to-Graph model (G2G), graph regularization to impose a prior structure on the graph, or optimizing on a larger graph than the original one with a reduced diameter.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A common issue in graph learning under the semi-supervised setting is referred to as gradient scarcity. That is, learning graphs by minimizing a loss on a subset of nodes causes edges between unlabelled nodes that are far from labelled ones to receive zero gradients. The phenomenon was first described when optimizing the graph and the weights of a Graph Neural Network (GCN) with a joint optimization algorithm. In this work, we give a precise mathematical characterization of this phenomenon, and prove that it also emerges in bilevel optimization, where additional dependency exists between the parameters of the problem. While for GCNs gradient scarcity occurs due to their finite receptive field, we show that it also occurs with the Laplacian regularization model, in the sense that gradients amplitude decreases exponentially with distance to labelled nodes. To alleviate this issue, we study several solutions: we propose to resort to latent graph learning using a Graph-to-Graph model (G2G), graph regularization to impose a prior structure on the graph, or optimizing on a larger graph than the original one with a reduced diameter. Our experiments on synthetic and real datasets validate our analysis and prove the efficiency of the proposed solutions.

Related papers

• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Addressing Heterophily in Node Classification with Graph Echo State Networks [11.52174067809364]
  We address the challenges of heterophilic graphs with Graph Echo State Network (GESN) for node classification. GESN is a reservoir computing model for graphs, where node embeddings are computed by an untrained message-passing function. Our experiments show that reservoir models are able to achieve better or comparable accuracy with respect to most fully trained deep models.
  arXiv  Detail & Related papers  (2023-05-14T19:42:31Z)
• Deep Manifold Learning with Graph Mining [80.84145791017968]
  We propose a novel graph deep model with a non-gradient decision layer for graph mining. The proposed model has achieved state-of-the-art performance compared to the current models.
  arXiv  Detail & Related papers  (2022-07-18T04:34:08Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  We propose a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN) GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive.
  arXiv  Detail & Related papers  (2022-05-19T14:08:15Z)
• 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 Sanitation with Application to Node Classification [41.311131936203715]
  We introduce the graph sanitation problem, to answer an question. By learning a better graph as part of the input of the mining model, it is expected to benefit graph mining in a variety of settings. In particular, it brings up to 25% performance improvement over the existing robust graph neural network methods.
  arXiv  Detail & Related papers  (2021-05-19T20:22:15Z)
• Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
  We consider the problem of inferring the graph structure from a given set of graph signals. Traditional graph learning models do not take this distributional uncertainty into account.
  arXiv  Detail & Related papers  (2021-05-12T06:47:34Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)

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.