Optimization-Induced Graph Implicit Nonlinear Diffusion

• URL: http://arxiv.org/abs/2206.14418v1
• Date: Wed, 29 Jun 2022 06:26:42 GMT
• Title: Optimization-Induced Graph Implicit Nonlinear Diffusion
• Authors: Qi Chen, Yifei Wang, Yisen Wang, Jiansheng Yang, Zhouchen Lin
• Abstract summary: We propose a new kind of graph convolution variants, called Graph Implicit Diffusion (GIND) GIND implicitly has access to infinite hops of neighbors while adaptively aggregating features with nonlinear diffusion to prevent over-smoothing. We show that the learned representation can be formalized as the minimizer of an explicit convex optimization objective.
• Score: 64.39772634635273
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Due to the over-smoothing issue, most existing graph neural networks can only capture limited dependencies with their inherently finite aggregation layers. To overcome this limitation, we propose a new kind of graph convolution, called Graph Implicit Nonlinear Diffusion (GIND), which implicitly has access to infinite hops of neighbors while adaptively aggregating features with nonlinear diffusion to prevent over-smoothing. Notably, we show that the learned representation can be formalized as the minimizer of an explicit convex optimization objective. With this property, we can theoretically characterize the equilibrium of our GIND from an optimization perspective. More interestingly, we can induce new structural variants by modifying the corresponding optimization objective. To be specific, we can embed prior properties to the equilibrium, as well as introducing skip connections to promote training stability. Extensive experiments show that GIND is good at capturing long-range dependencies, and performs well on both homophilic and heterophilic graphs with nonlinear diffusion. Moreover, we show that the optimization-induced variants of our models can boost the performance and improve training stability and efficiency as well. As a result, our GIND obtains significant improvements on both node-level and graph-level tasks.

Related papers

• AUGUR, A flexible and efficient optimization algorithm for identification of optimal adsorption sites [0.4188114563181615]
  Our model combines graph neural networks and Gaussian processes to create a flexible, efficient, symmetry-aware, translation, and rotation-invariant predictor. It determines the optimal position of large and complicated clusters with far fewer iterations than current state-of-the-art approaches. It does not rely on hand-crafted features and can be seamlessly employed on any molecule without any alterations.
  arXiv  Detail & Related papers  (2024-09-24T16:03:01Z)
• Controlled Learning of Pointwise Nonlinearities in Neural-Network-Like Architectures [14.93489065234423]
  We present a general variational framework for the training of freeform nonlinearities in layered computational architectures. The slope constraints allow us to impose properties such as 1-Lipschitz stability, firm non-expansiveness, and monotonicity/invertibility. We show how to solve the numerically function-optimization problem by representing the nonlinearities in a suitable (nonuniform) B-spline basis.
  arXiv  Detail & Related papers  (2024-08-23T14:39:27Z)
• Through the Dual-Prism: A Spectral Perspective on Graph Data Augmentation for Graph Classification [71.36575018271405]
  We introduce the Dual-Prism (DP) augmentation method, comprising DP-Noise and DP-Mask. We find that keeping the low-frequency eigenvalues unchanged can preserve the critical properties at a large scale when generating augmented graphs.
  arXiv  Detail & Related papers  (2024-01-18T12:58:53Z)
• Achieving Constraints in Neural Networks: A Stochastic Augmented Lagrangian Approach [49.1574468325115]
  Regularizing Deep Neural Networks (DNNs) is essential for improving generalizability and preventing overfitting. We propose a novel approach to DNN regularization by framing the training process as a constrained optimization problem. We employ the Augmented Lagrangian (SAL) method to achieve a more flexible and efficient regularization mechanism.
  arXiv  Detail & Related papers  (2023-10-25T13:55:35Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation [80.227864832092]
  Graph neural networks (GNNs) have exhibited exceptional efficacy in a diverse array of applications. The sheer size of large-scale graphs presents a significant challenge to real-time inference with GNNs. We propose an online propagation framework and two novel node-adaptive propagation methods.
  arXiv  Detail & Related papers  (2023-10-17T05:03:00Z)
• Implicit Graph Neural Diffusion Networks: Convergence, Generalization, and Over-Smoothing [7.984586585987328]
  Implicit Graph Neural Networks (GNNs) have achieved significant success in addressing graph learning problems. We introduce a geometric framework for designing implicit graph diffusion layers based on a parameterized graph Laplacian operator. We show how implicit GNN layers can be viewed as the fixed-point equation of a Dirichlet energy minimization problem.
  arXiv  Detail & Related papers  (2023-08-07T05:22:33Z)
• Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks [25.59092732148598]
  Heterogeneous graph neural networks (GNNs) achieve strong performance on node classification tasks in a semi-supervised learning setting. We propose a novel heterogeneous GNN architecture in which layers are derived from optimization steps that descend a novel relation-aware energy function.
  arXiv  Detail & Related papers  (2022-06-22T13:48:08Z)
• Restructuring Graph for Higher Homophily via Adaptive Spectral Clustering [7.223313563198697]
  We show that a graph restructuring method can significantly boost the performance of six classical GNNs by an average of 25% on less-homophilic graphs. The boosted performance is comparable to state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-06-06T06:38:53Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)

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.