Beyond 1-WL with Local Ego-Network Encodings

• URL: http://arxiv.org/abs/2211.14906v1
• Date: Sun, 27 Nov 2022 18:14:03 GMT
• Title: Beyond 1-WL with Local Ego-Network Encodings
• Authors: Nurudin Alvarez-Gonzalez, Andreas Kaltenbrunner, Vicen\c{c} G\'omez
• Abstract summary: We show that ego-networks can produce a structural encoding scheme for arbitrary graphs with greater expressivity than the Weisfeiler-Lehman (1-WL) test. We introduce IGEL, a preprocessing step to produce features that augment node representations by encoding ego-networks into sparse vectors.
• Score: 0.42970700836450487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Identifying similar network structures is key to capture graph isomorphisms and learn representations that exploit structural information encoded in graph data. This work shows that ego-networks can produce a structural encoding scheme for arbitrary graphs with greater expressivity than the Weisfeiler-Lehman (1-WL) test. We introduce IGEL, a preprocessing step to produce features that augment node representations by encoding ego-networks into sparse vectors that enrich Message Passing (MP) Graph Neural Networks (GNNs) beyond 1-WL expressivity. We describe formally the relation between IGEL and 1-WL, and characterize its expressive power and limitations. Experiments show that IGEL matches the empirical expressivity of state-of-the-art methods on isomorphism detection while improving performance on seven GNN architectures.

Related papers

• A Pure Transformer Pretraining Framework on Text-attributed Graphs [50.833130854272774]
  We introduce a feature-centric pretraining perspective by treating graph structure as a prior. Our framework, Graph Sequence Pretraining with Transformer (GSPT), samples node contexts through random walks. GSPT can be easily adapted to both node classification and link prediction, demonstrating promising empirical success on various datasets.
  arXiv  Detail & Related papers  (2024-06-19T22:30:08Z)
• Efficient Topology-aware Data Augmentation for High-Degree Graph Neural Networks [2.7523980737007414]
  We propose TADA, an efficient and effective front-mounted data augmentation framework for graph neural networks (GNNs) on high-degree graphs (HDGs) Under the hood, TADA includes two key modules: (i) feature expansion with structure embeddings, and (ii) topology- and attribute-aware graph sparsification. TADA considerably improves the predictive performance of mainstream GNN models on 8 real homophilic/heterophilic HDGs in terms of node classification.
  arXiv  Detail & Related papers  (2024-06-08T14:14:19Z)
• DGNN: Decoupled Graph Neural Networks with Structural Consistency between Attribute and Graph Embedding Representations [62.04558318166396]
  Graph neural networks (GNNs) demonstrate a robust capability for representation learning on graphs with complex structures. A novel GNNs framework, dubbed Decoupled Graph Neural Networks (DGNN), is introduced to obtain a more comprehensive embedding representation of nodes. Experimental results conducted on several graph benchmark datasets verify DGNN's superiority in node classification task.
  arXiv  Detail & Related papers  (2024-01-28T06:43:13Z)
• Improving Expressivity of GNNs with Subgraph-specific Factor Embedded Normalization [30.86182962089487]
  Graph Neural Networks (GNNs) have emerged as a powerful category of learning architecture for handling graph-structured data. We propose a dedicated plug-and-play normalization scheme, termed as SUbgraph-sPEcific FactoR Embedded Normalization (SuperNorm)
  arXiv  Detail & Related papers  (2023-05-31T14:37:31Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• Graph Representation Learning with Individualization and Refinement [19.436520792345064]
  Graph Neural Networks (GNNs) have emerged as prominent models for representation learning on graph structured data. In this work, we follow the classical approach of Individualization and Refinement (IR) Our technique lets us learn richer node embeddings while keeping the computational complexity manageable.
  arXiv  Detail & Related papers  (2022-03-17T07:50:48Z)
• Breaking the Expressive Bottlenecks of Graph Neural Networks [26.000304641965947]
  Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to measure the expressiveness of graph neural networks (GNNs) In this paper, we improve the expressiveness by exploring powerful aggregators.
  arXiv  Detail & Related papers  (2020-12-14T02:36:46Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)
• Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks [183.97265247061847]
  We leverage graph signal processing to characterize the representation space of graph neural networks (GNNs) We discuss the role of graph convolutional filters in GNNs and show that any architecture built with such filters has the fundamental properties of permutation equivariance and stability to changes in the topology. We also study the use of GNNs in recommender systems and learning decentralized controllers for robot swarms.
  arXiv  Detail & Related papers  (2020-03-08T13:02:15Z)

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.