Abstract
Graph Convolutional Networks (GCNs) have become a standard for processing graph-structured data, yet most architectures rely on a restrictive first-order Chebyshev polynomial approximation. This paper introduces Taylor-based Graph Convolutional Networks (TGCN), a framework that employs Taylor expansions to approximate graph wavelet kernels. By transitioning from the spectral domain to a flexible vertex-domain propagation model, TGCN allows for trainable self-influence parameters and higher-order neighborhood aggregation. Experimental evaluations on citation networks and 3D point clouds show that TGCN outperforms traditional GCNs in accuracy and adaptability while remaining computationally efficient.
Introduction
The success of Graph Convolutional Networks (GCNs) is largely attributed to their ability to learn representations from complex relational data. However, the widely used "standard" GCN is built upon a first-order approximation of spectral filters, which necessitates specific assumptions about the graph's maximum eigenvalues and fixed coefficients. These constraints often lead to information loss and a lack of flexibility across diverse datasets.
To address these limitations, we propose a more generalized framework rooted in Taylor expansions. By approximating the graph wavelet kernel using Taylor series, we derive a propagation rule that operates directly in the vertex domain, bypassing the need for expensive spectral decompositions while offering greater control over the message-passing process.
Methodology
The core of TGCN is the approximation of the graph wavelet kernel through Taylor expansions. This allows for the design of a propagation matrix $P$ that is not strictly bound by the interval constraints of Chebyshev polynomials. We define four variants of TGCN:
- Type-1 (First-Order): Introduces a global trainable parameter $\alpha$ to balance a node's own features with its neighbors' information: $P = (1-\alpha)I + \alpha \tilde{A}$.
- Type-2 (Node-Specific): Extends Type-1 by assigning a unique self-influence parameter $\beta_i$ to each node, allowing for highly granular propagation rules.
- Type-3 & 4 (Higher-Order): Utilize $k$-th order Taylor polynomials to capture multi-hop neighborhood information within a single layer, effectively expanding the receptive field.
This approach makes the model "eigenvalue agnostic," meaning it can function effectively with various graph representations, such as the simple adjacency matrix or the transition matrix, without requiring normalized Laplacians.
Experiments and Results
We evaluated TGCN on three citation networks (Cora, Citeseer, and Pubmed) and the ShapeNet 3D point cloud dataset.
Impact of Self-Influence
A key finding is the significance of the diagonal elements in the propagation matrix. Figure 2 demonstrates how the accuracy of the model varies with the diagonal parameter $\alpha$.
The results indicate that the optimal $\alpha$ varies by dataset, highlighting the benefit of the trainable parameters in TGCN. For instance, Type-2 TGCN achieved 81.3% accuracy on Cora, compared to 78.7% for a standard GCN.
Depth and Computational Efficiency
We also investigated the relationship between model depth (number of layers) and performance. As shown in Figure 5, while increasing the number of layers initially improves accuracy, performance tends to saturate or decline beyond a certain depth, a phenomenon often attributed to over-smoothing.
Crucially, the computational overhead of TGCN remains manageable. Even with the additional parameters in Type-2 models, training time per epoch is only approximately 10% higher than that of a standard GCN.
Conclusion
TGCN provides a flexible and efficient alternative to standard GCNs by leveraging Taylor expansions for graph propagation. By enabling trainable self-influence and higher-order filters, the framework adapts more effectively to the unique characteristics of different graph datasets. Future work will explore the integration of Taylor approximations into attention-based architectures and automated selection of graph representations.
Summary updated