On the Hölder Stability of Multiset and Graph Neural Networks

• URL: http://arxiv.org/abs/2406.06984v3
• Date: Tue, 08 Apr 2025 10:58:36 GMT
• Title: On the Hölder Stability of Multiset and Graph Neural Networks
• Abstract summary: We propose a novel pair-wise separation quality analysis framework based on an adaptation of Lipschitz and Holder stability to parametric functions.<n>We prove that common sum-based models are lower-Holder in expectation, with an exponent that decays rapidly with the network's depth.<n>We show these MPNNs can easily classify our adversarial examples, and compare favorably with standard MPNNs on standard graph learning tasks.
• Score: 3.396731589928944
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Extensive research efforts have been put into characterizing and constructing maximally separating multiset and graph neural networks. However, recent empirical evidence suggests the notion of separation itself doesn't capture several interesting phenomena. On the one hand, the quality of this separation may be very weak, to the extent that the embeddings of "separable" objects might even be considered identical when using fixed finite precision. On the other hand, architectures which aren't capable of separation in theory, somehow achieve separation when taking the network to be wide enough. In this work, we address both of these issues, by proposing a novel pair-wise separation quality analysis framework which is based on an adaptation of Lipschitz and \Holder{} stability to parametric functions. The proposed framework, which we name \emph{\Holder{} in expectation}, allows for separation quality analysis, without restricting the analysis to embeddings that can separate all the input space simultaneously. We prove that common sum-based models are lower-\Holder{} in expectation, with an exponent that decays rapidly with the network's depth . Our analysis leads to adversarial examples of graphs which can be separated by three 1-WL iterations, but cannot be separated in practice by standard maximally powerful Message Passing Neural Networks (MPNNs). To remedy this, we propose two novel MPNNs with improved separation quality, one of which is lower Lipschitz in expectation. We show these MPNNs can easily classify our adversarial examples, and compare favorably with standard MPNNs on standard graph learning tasks.

Related papers

• A Unified Framework for Quantized and Continuous Strong Lottery Tickets [3.772827533440353]
  We provide an analysis of the Random Subset Sum Problem (RSSP) in the discrete setting, and use it to derive tight SLTH guarantees in the quantized case.<n>Our analysis obtains tight bounds on the failure probability of finding a strong lottery ticket in the quantized regime, providing an exponential improvement over previous results.
  arXiv  Detail & Related papers  (2026-07-04T13:00:39Z)
• Do Deep Ensembles Actually Capture Uncertainty in Graph Neural Networks? [4.034187803388112]
  We investigate standard deep ensembles specifically for message-passing graph neural networks.<n>We find that ensembles provide surprisingly little improvement over a single model.<n>Our results suggest that deep ensemble success does not seamlessly transfer to graph machine learning.
  arXiv  Detail & Related papers  (2026-05-21T15:07:47Z)
• Input Specific Neural Networks [0.0]
  The black-box of neural networks limits the ability to encode or impose specific relationships between inputs and outputs. This paper presents two ISNNs, along with equations for first second derivatives of respect to the inputs. We show how ISNNs can be used to learn structural relationships between inputs outputs via a binary gating mechanism.
  arXiv  Detail & Related papers  (2025-03-01T00:57:16Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [92.05291395292537]
  Graph neural networks (GNNs) for link prediction can loosely be divided into two broad categories. First, emphnode-wise architectures pre-compute individual embeddings for each node that are later combined by a simple decoder to make predictions. Second, emphedge-wise methods rely on the formation of edge-specific subgraph embeddings to enrich the representation of pair-wise relationships.
  arXiv  Detail & Related papers  (2023-10-14T07:02:54Z)
• Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks [89.28881869440433]
  This paper provides the first theoretical characterization of joint edge-model sparse learning for graph neural networks (GNNs) It proves analytically that both sampling important nodes and pruning neurons with the lowest-magnitude can reduce the sample complexity and improve convergence without compromising the test accuracy.
  arXiv  Detail & Related papers  (2023-02-06T16:54:20Z)
• Comparative Analysis of Interval Reachability for Robust Implicit and Feedforward Neural Networks [64.23331120621118]
  We use interval reachability analysis to obtain robustness guarantees for implicit neural networks (INNs) INNs are a class of implicit learning models that use implicit equations as layers. We show that our approach performs at least as well as, and generally better than, applying state-of-the-art interval bound propagation methods to INNs.
  arXiv  Detail & Related papers  (2022-04-01T03:31:27Z)
• Implicit Equivariance in Convolutional Networks [1.911678487931003]
  Implicitly Equivariant Networks (IEN) induce equivariant in the different layers of a standard CNN model. We show IEN outperforms the state-of-the-art rotation equivariant tracking method while providing faster inference speed.
  arXiv  Detail & Related papers  (2021-11-28T14:44:17Z)
• Implicit vs Unfolded Graph Neural Networks [29.803948965931212]
  We show that implicit and unfolded GNNs can achieve strong node classification accuracy across disparate regimes.<n>While IGNN is substantially more memory-efficient, UGNN models support unique, integrated graph attention mechanisms and propagation rules.
  arXiv  Detail & Related papers  (2021-11-12T07:49:16Z)
• Learning from Small Samples: Transformation-Invariant SVMs with Composition and Locality at Multiple Scales [11.210266084524998]
  This paper shows how to incorporate into support-vector machines (SVMs) those properties that have made convolutional neural networks (CNNs) successful.
  arXiv  Detail & Related papers  (2021-09-27T04:02:43Z)
• Quantized convolutional neural networks through the lens of partial differential equations [6.88204255655161]
  Quantization of Convolutional Neural Networks (CNNs) is a common approach to ease the computational burden involved in the deployment of CNNs. In this work, we explore ways to improve quantized CNNs using PDE-based perspective and analysis.
  arXiv  Detail & Related papers  (2021-08-31T22:18:52Z)
• Mitigating Performance Saturation in Neural Marked Point Processes: Architectures and Loss Functions [50.674773358075015]
  We propose a simple graph-based network structure called GCHP, which utilizes only graph convolutional layers. We show that GCHP can significantly reduce training time and the likelihood ratio loss with interarrival time probability assumptions can greatly improve the model performance.
  arXiv  Detail & Related papers  (2021-07-07T16:59:14Z)
• Robust Implicit Networks via Non-Euclidean Contractions [63.91638306025768]
  Implicit neural networks show improved accuracy and significant reduction in memory consumption. They can suffer from ill-posedness and convergence instability. This paper provides a new framework to design well-posed and robust implicit neural networks.
  arXiv  Detail & Related papers  (2021-06-06T18:05:02Z)
• Encoding the latent posterior of Bayesian Neural Networks for uncertainty quantification [10.727102755903616]
  We aim for efficient deep BNNs amenable to complex computer vision architectures. We achieve this by leveraging variational autoencoders (VAEs) to learn the interaction and the latent distribution of the parameters at each network layer. Our approach, Latent-Posterior BNN (LP-BNN), is compatible with the recent BatchEnsemble method, leading to highly efficient (in terms of computation and memory during both training and testing) ensembles.
  arXiv  Detail & Related papers  (2020-12-04T19:50:09Z)
• Learning Deep Interleaved Networks with Asymmetric Co-Attention for Image Restoration [65.11022516031463]
  We present a deep interleaved network (DIN) that learns how information at different states should be combined for high-quality (HQ) images reconstruction. In this paper, we propose asymmetric co-attention (AsyCA) which is attached at each interleaved node to model the feature dependencies. Our presented DIN can be trained end-to-end and applied to various image restoration tasks.
  arXiv  Detail & Related papers  (2020-10-29T15:32:00Z)

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.