2021/10/14 by Peihao Wang, Wang, Peihao, Yuehao Wang +5 · 2 citations
Computer Science · #Advanced Graph Neural Networks #Business #Computer science #FOS: Computer and information sciences #Graph #Graph Theory and Algorithms #Machine Learning (cs.LG) #Order (exchange) #Theoretical computer science #Topic Modeling #cs.LG
paper · pdf · doi:10.48550/arxiv.2110.07141
published in arXiv (Cornell University) (Cornell University) · 15 pages, 7 figures
arxiv created 2021/10/14 · openalex publication_date 2021/10/14 · arxiv updated 2021/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 × 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.