  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.
