FeatureNorm: L2 Feature Normalization for Dynamic Graph Embedding

• URL: http://arxiv.org/abs/2103.00164v1
• Date: Sat, 27 Feb 2021 09:13:47 GMT
• Title: FeatureNorm: L2 Feature Normalization for Dynamic Graph Embedding
• Authors: Menglin Yang, Ziqiao Meng, Irwin King
• Abstract summary: Graph convolutional network (GCN) has been widely explored and used in non-Euclidean application domains. In this paper, we analyze the shrinking properties in the node embedding space at first, and then design a simple yet versatile method. Experiments on four real-world dynamic graph datasets compared with competitive baseline models demonstrate the effectiveness of the proposed method.
• Score: 39.527059564775094
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Dynamic graphs arise in a plethora of practical scenarios such as social networks, communication networks, and financial transaction networks. Given a dynamic graph, it is fundamental and essential to learn a graph representation that is expected not only to preserve structural proximity but also jointly capture the time-evolving patterns. Recently, graph convolutional network (GCN) has been widely explored and used in non-Euclidean application domains. The main success of GCN, especially in handling dependencies and passing messages within nodes, lies in its approximation to Laplacian smoothing. As a matter of fact, this smoothing technique can not only encourage must-link node pairs to get closer but also push cannot-link pairs to shrink together, which potentially cause serious feature shrink or oversmoothing problem, especially when stacking graph convolution in multiple layers or steps. For learning time-evolving patterns, a natural solution is to preserve historical state and combine it with the current interactions to obtain the most recent representation. Then the serious feature shrink or oversmoothing problem could happen when stacking graph convolution explicitly or implicitly according to current prevalent methods, which would make nodes too similar to distinguish each other. To solve this problem in dynamic graph embedding, we analyze the shrinking properties in the node embedding space at first, and then design a simple yet versatile method, which exploits L2 feature normalization constraint to rescale all nodes to hypersphere of a unit ball so that nodes would not shrink together, and yet similar nodes can still get closer. Extensive experiments on four real-world dynamic graph datasets compared with competitive baseline models demonstrate the effectiveness of the proposed method.

Related papers

• Towards Dynamic Message Passing on Graphs [104.06474765596687]
  We propose a novel dynamic message-passing mechanism for graph neural networks (GNNs) It projects graph nodes and learnable pseudo nodes into a common space with measurable spatial relations between them. With nodes moving in the space, their evolving relations facilitate flexible pathway construction for a dynamic message-passing process.
  arXiv  Detail & Related papers  (2024-10-31T07:20:40Z)
• Input Snapshots Fusion for Scalable Discrete Dynamic Graph Nerual Networks [27.616083395612595]
  We introduce an Input bf Snapshots bf Fusion based bf Dynamic bf Graph Neural Network (SFDyG) By eliminating the partitioning of snapshots within the input window, we obtain a multi-graph (more than one edge between two nodes) We propose a scalable three-step mini-batch training method and demonstrate its equivalence to full-batch training counterpart.
  arXiv  Detail & Related papers  (2024-05-11T10:05:55Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• 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)
• Addressing Heterophily in Node Classification with Graph Echo State Networks [11.52174067809364]
  We address the challenges of heterophilic graphs with Graph Echo State Network (GESN) for node classification. GESN is a reservoir computing model for graphs, where node embeddings are computed by an untrained message-passing function. Our experiments show that reservoir models are able to achieve better or comparable accuracy with respect to most fully trained deep models.
  arXiv  Detail & Related papers  (2023-05-14T19:42:31Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Expander Graph Propagation [0.0]
  We propose an elegant approach based on propagating information over expander graphs. We show that EGP is able to address all of the above concerns, while requiring minimal effort to set up. We believe our analysis paves the way to a novel class of scalable methods to counter oversquashing in GNNs.
  arXiv  Detail & Related papers  (2022-10-06T15:36:37Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  Modelling long-range dependencies is critical for scene understanding tasks in computer vision. A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2022-09-20T14:41:37Z)
• CatGCN: Graph Convolutional Networks with Categorical Node Features [99.555850712725]
  CatGCN is tailored for graph learning when the node features are categorical. We train CatGCN in an end-to-end fashion and demonstrate it on semi-supervised node classification.
  arXiv  Detail & Related papers  (2020-09-11T09:25:17Z)
• Dynamic Spatiotemporal Graph Neural Network with Tensor Network [12.278768477060137]
  Dynamic spatial graph construction is a challenge in graph neural network (GNN) for time series data problems. We generate a spatial tensor graph (STG) to collect all the dynamic spatial relations, as well as a temporal tensor graph (TTG) to find the latent pattern along time at each node. We experimentally compare the accuracy and time costing with the state-of-the-art GNN based methods on the public traffic datasets.
  arXiv  Detail & Related papers  (2020-03-12T20:47:22Z)

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.