On dimensionality of feature vectors in MPNNs

• URL: http://arxiv.org/abs/2402.03966v2
• Date: Wed, 14 Feb 2024 09:13:30 GMT
• Title: On dimensionality of feature vectors in MPNNs
• Authors: C\'esar Bravo, Alexander Kozachinskiy, Crist\'obal Rojas
• Abstract summary: We revisit the classical result of Morris et al.(AAAI'19) that message-passing graphs neural networks (MPNNs) are equal in their distinguishing power to the Weisfeiler--Leman (WL) isomorphism test.
• Score: 49.32130498861987
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the classical result of Morris et al.~(AAAI'19) that message-passing graphs neural networks (MPNNs) are equal in their distinguishing power to the Weisfeiler--Leman (WL) isomorphism test. Morris et al.~show their simulation result with ReLU activation function and $O(n)$-dimensional feature vectors, where $n$ is the number of nodes of the graph. By introducing randomness into the architecture, Aamand et al.~(NeurIPS'22) were able to improve this bound to $O(\log n)$-dimensional feature vectors, again for ReLU activation, although at the expense of guaranteeing perfect simulation only with high probability. Recently, Amir et al.~(NeurIPS'23) have shown that for any non-polynomial analytic activation function, it is enough to use just 1-dimensional feature vectors. In this paper, we give a simple proof of the result of Amit et al.~and provide an independent experimental validation of it.

Related papers

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• GRIL: A $2$-parameter Persistence Based Vectorization for Machine Learning [0.49703640686206074]
  We introduce a novel vector representation called Generalized Rank Invariant Landscape (GRIL) for $2$- parameter persistence modules. We show that this vector representation is $1$-Lipschitz stable and differentiable with respect to underlying filtration functions. We also observe an increase in performance indicating that GRIL can capture additional features enriching Graph Neural Networks (GNNs)
  arXiv  Detail & Related papers  (2023-04-11T04:30:58Z)
• Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks [22.36443060418036]
  We show that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman graph test. We present an improved simulation of the WL test on GNNs with emphexponentially lower complexity.
  arXiv  Detail & Related papers  (2022-11-06T22:38:49Z)
• On the Identifiability and Estimation of Causal Location-Scale Noise Models [122.65417012597754]
  We study the class of location-scale or heteroscedastic noise models (LSNMs) We show the causal direction is identifiable up to some pathological cases. We propose two estimators for LSNMs: an estimator based on (non-linear) feature maps, and one based on neural networks.
  arXiv  Detail & Related papers  (2022-10-13T17:18:59Z)
• A Feedforward Unitary Equivariant Neural Network [3.6220250022337335]
  We devise a new type of feedforward neural network. It is equivariant with respect to the unitary group $U(n)$. The input and output can be vectors in $mathbbCn$ with arbitrary dimension $n$.
  arXiv  Detail & Related papers  (2022-08-25T15:05:02Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Largest Eigenvalues of the Conjugate Kernel of Single-Layered Neural Networks [0.0]
  We show that the largest eigenvalue has the same limit (in probability) as that of some well-known linear random matrix ensembles. This may be of interest for applications to machine learning.
  arXiv  Detail & Related papers  (2022-01-13T00:48:20Z)
• A Precise Performance Analysis of Support Vector Regression [105.94855998235232]
  We study the hard and soft support vector regression techniques applied to a set of $n$ linear measurements. Our results are then used to optimally tune the parameters intervening in the design of hard and soft support vector regression algorithms.
  arXiv  Detail & Related papers  (2021-05-21T14:26:28Z)
• On Mean Absolute Error for Deep Neural Network Based Vector-to-Vector Regression [79.86233860519621]
  We exploit the properties of mean absolute error (MAE) as a loss function for the deep neural network (DNN) based vector-to-vector regression. We show that MAE can be interpreted as an error modeled by Laplacian distribution.
  arXiv  Detail & Related papers  (2020-08-12T22:41:26Z)
• Statistical-Query Lower Bounds via Functional Gradients [19.5924910463796]
  We show that any statistical-query algorithm with tolerance $n- (1/epsilon)b$ must use at least $2nc epsilon$ queries for some constant $b. Our results rule out general (as opposed to correlational) SQ learning algorithms, which is unusual for real-valued learning problems.
  arXiv  Detail & Related papers  (2020-06-29T05:15:32Z)

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.