Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectors

• URL: http://arxiv.org/abs/2410.09737v1
• Date: Sun, 13 Oct 2024 06:02:25 GMT
• Title: Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectors
• Authors: Junru Zhou, Cai Zhou, Xiyuan Wang, Pan Li, Muhan Zhang,
• Abstract summary: We propose a novel method exploiting Laplacian eigenvectors to generate stable and globally expressive graph representations. Our method deals with numerically close eigenvalues in a smooth fashion, ensuring its better robustness against perturbations.
• Score: 29.055130767451036
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNNs) have achieved remarkable success in a variety of machine learning tasks over graph data. Existing GNNs usually rely on message passing, i.e., computing node representations by gathering information from the neighborhood, to build their underlying computational graphs. They are known fairly limited in expressive power, and often fail to capture global characteristics of graphs. To overcome the issue, a popular solution is to use Laplacian eigenvectors as additional node features, as they contain global positional information of nodes, and can serve as extra node identifiers aiding GNNs to separate structurally similar nodes. For such an approach, properly handling the orthogonal group symmetry among eigenvectors with equal eigenvalue is crucial for its stability and generalizability. However, using a naive orthogonal group invariant encoder for each separate eigenspace may not keep the full expressivity in the Laplacian eigenvectors. Moreover, computing such invariants inevitably entails a hard split of Laplacian eigenvalues according to their numerical identity, which suffers from great instability when the graph structure is perturbed. In this paper, we propose a novel method exploiting Laplacian eigenvectors to generate stable and globally expressive graph representations. The main difference from previous works is that (i) our method utilizes learnable orthogonal group invariant representations for each Laplacian eigenspace, based upon powerful orthogonal group equivariant neural network layers already well studied in the literature, and that (ii) our method deals with numerically close eigenvalues in a smooth fashion, ensuring its better robustness against perturbations. Experiments on various graph learning benchmarks witness the competitive performance of our method, especially its great potential to learn global properties of graphs.

Related papers

• Diss-l-ECT: Dissecting Graph Data with local Euler Characteristic Transforms [13.608942872770855]
  We introduce the Local Euler Characteristic Transform ($ell$-ECT) to enhance expressivity and interpretability in graph representation learning. Unlike traditional Graph Neural Networks (GNNs), which may lose critical local details through aggregation, the $ell$-ECT provides a lossless representation of local neighborhoods. Our method exhibits superior performance than standard GNNs on a variety of node classification tasks, particularly in graphs with high heterophily.
  arXiv  Detail & Related papers  (2024-10-03T16:02:02Z)
• Graph Generation via Spectral Diffusion [51.60814773299899]
  We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process. Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix. Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• GOAt: Explaining Graph Neural Networks via Graph Output Attribution [32.66251068600664]
  This paper introduces Graph Output Attribution (GOAt), a novel method to attribute graph outputs to input graph features. GOAt is faithful, discriminative, as well as stable across similar samples. We show that our method outperforms various state-ofthe-art GNN explainers in terms of the commonly used fidelity metric.
  arXiv  Detail & Related papers  (2024-01-26T00:32:58Z)
• On the Stability of Expressive Positional Encodings for Graphs [46.967035678550594]
  Using Laplacian eigenvectors as positional encodings faces two fundamental challenges. We introduce Stable and Expressive Positional generalizations (SPE) SPE is the first architecture that is (1) provably stable, and (2) universally expressive for basis invariant functions.
  arXiv  Detail & Related papers  (2023-10-04T04:48:55Z)
• 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)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Sign and Basis Invariant Networks for Spectral Graph Representation Learning [75.18802152811539]
  We introduce SignNet and BasisNet -- new neural architectures that are invariant to all requisite symmetries and hence process collections of eigenspaces in a principled manner. Our networks are theoretically strong for graph representation learning -- they can approximate any spectral graph convolution. Experiments show the strength of our networks for learning spectral graph filters and learning graph positional encodings.
  arXiv  Detail & Related papers  (2022-02-25T23:11:59Z)
• Building powerful and equivariant graph neural networks with structural message-passing [74.93169425144755]
  We propose a powerful and equivariant message-passing framework based on two ideas. First, we propagate a one-hot encoding of the nodes, in addition to the features, in order to learn a local context matrix around each node. Second, we propose methods for the parametrization of the message and update functions that ensure permutation equivariance.
  arXiv  Detail & Related papers  (2020-06-26T17:15:16Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.