SoGCN: Second-Order Graph Convolutional Networks

• URL: http://arxiv.org/abs/2110.07141v1
• Date: Thu, 14 Oct 2021 03:56:34 GMT
• Title: SoGCN: Second-Order Graph Convolutional Networks
• Authors: Peihao Wang, Yuehao Wang, Hua Lin, Jianbo Shi
• Abstract summary: We show that multi-layer second-order graph convolution (SoGC) is sufficient to attain the ability of expressing spectral filters with arbitrary coefficients. We build our Second-Order Graph Convolutional Networks (SoGCN) with SoGC and design a synthetic dataset to verify its filter fitting capability.
• Score: 20.840026487716404
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Convolutional Networks (GCN) with multi-hop aggregation is more expressive than one-hop GCN but suffers from higher model complexity. Finding the shortest aggregation range that achieves comparable expressiveness and minimizes this side effect remains an open question. We answer this question by showing that multi-layer second-order graph convolution (SoGC) is sufficient to attain the ability of expressing polynomial spectral filters with arbitrary coefficients. Compared to models with one-hop aggregation, multi-hop propagation, and jump connections, SoGC possesses filter representational completeness while being lightweight, efficient, and easy to implement. Thereby, we suggest that SoGC is a simple design capable of forming the basic building block of GCNs, playing the same role as $3 \times 3$ kernels in CNNs. We build our Second-Order Graph Convolutional Networks (SoGCN) with SoGC and design a synthetic dataset to verify its filter fitting capability to validate these points. For real-world tasks, we present the state-of-the-art performance of SoGCN on the benchmark of node classification, graph classification, and graph regression datasets.

Related papers

• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Graph Transformers for Large Graphs [57.19338459218758]
  This work advances representation learning on single large-scale graphs with a focus on identifying model characteristics and critical design constraints. A key innovation of this work lies in the creation of a fast neighborhood sampling technique coupled with a local attention mechanism. We report a 3x speedup and 16.8% performance gain on ogbn-products and snap-patents, while we also scale LargeGT on ogbn-100M with a 5.9% performance improvement.
  arXiv  Detail & Related papers  (2023-12-18T11:19:23Z)
• Learnable Graph Convolutional Attention Networks [7.465923786151107]
  Graph Neural Networks (GNNs) compute the message exchange between nodes by either aggregating uniformly (convolving) the features of all the neighboring nodes, or by applying a non-uniform score (attending) to the features. Recent works have shown the strengths and weaknesses of the resulting GNN architectures, respectively, GCNs and GATs. We introduce the graph convolutional attention layer (CAT), which relies on convolutions to compute the attention scores. Our results demonstrate that L-CAT is able to efficiently combine different GNN layers along the network, outperforming competing methods in a wide
  arXiv  Detail & Related papers  (2022-11-21T21:08:58Z)
• Simplified Graph Convolution with Heterophily [25.7577503312319]
  We show that Simple Graph Convolution (SGC) is ineffective for heterophilous (i.e., non-homophilous) graphs. We propose Adaptive Simple Graph Convolution (ASGC), which we show can adapt to both homophilous and heterophilous graph structure.
  arXiv  Detail & Related papers  (2022-02-08T20:52:08Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
  VQ-GNN is a universal framework to scale up any convolution-based GNNs using Vector Quantization (VQ) without compromising the performance. Our framework avoids the "neighbor explosion" problem of GNNs using quantized representations combined with a low-rank version of the graph convolution matrix.
  arXiv  Detail & Related papers  (2021-10-27T11:48:50Z)
• Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
  We aim at improving the computational efficiency of graph convolutional networks (GCNs) for learning on point clouds. A series of experiments show that optimized networks have reduced computational complexity, decreased memory consumption, and accelerated inference speed.
  arXiv  Detail & Related papers  (2021-04-12T17:59:16Z)
• Representative Graph Neural Network [113.67254049938629]
  We present a Representative Graph layer to dynamically sample a few representative features. Instead of propagating the messages from all positions, our RepGraph layer computes the response of one node merely with a few representative nodes.
  arXiv  Detail & Related papers  (2020-08-12T09:46:52Z)
• RGCF: Refined Graph Convolution Collaborative Filtering with concise and expressive embedding [42.46797662323393]
  We develop a new GCN-based Collaborative Filtering model, named Refined Graph convolution Collaborative Filtering(RGCF) RGCF is more capable for capturing the implicit high-order connectivities inside the graph and the resultant vector representations are more expressive. We conduct extensive experiments on three public million-size datasets, demonstrating that our RGCF significantly outperforms state-of-the-art models.
  arXiv  Detail & Related papers  (2020-07-07T12:26:10Z)
• Connecting Graph Convolutional Networks and Graph-Regularized PCA [23.592657600394215]
  Graph convolution operator of the GCN model is originally motivated from a localized first-order approximation of spectral graph convolutions. We establish a textitmathematical connection between graph convolution and graph-regularized PCA (GPCA)
  arXiv  Detail & Related papers  (2020-06-22T14:27:02Z)

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.