Flexible infinite-width graph convolutional networks and the importance of representation learning

Ben Anson, Edward Milsom, Laurence Aitchison

Introduction

In deep learning theory, "infinite-width" networks are often studied because they behave like Gaussian Processes (GPs), making them mathematically tractable. These models, known as Neural Network Gaussian Processes (NNGPs), have historically suffered from a significant limitation: their "kernels" (the functions defining similarity between data points) are fixed at initialization. Unlike finite-width Graph Convolutional Networks (GCNs), which learn task-specific features, NNGPs perform a form of template matching without the ability to adapt their representations to the data.

While prior research suggested that infinite-width graph NNGPs were surprisingly competitive, this paper challenges that narrative. The authors argue that NNGPs only perform well on specific types of datasets and introduce a framework that allows for a tunable amount of representation learning to understand when and why it matters for graph structures.

The Graph Convolutional Deep Kernel Machine (GC-DKM)

To bridge the gap between theory and practice, the authors developed the Graph Convolutional Deep Kernel Machine (GC-DKM). This framework introduces several key innovations:

  • The DKM Framework: Unlike standard NNGPs, a DKM treats Gram matrices (representing the kernel at each layer) as learnable parameters rather than fixed functions.
  • The "Flexibility Knob" ($\nu$): A regularization parameter, $\nu$, allows the model to transition between a fixed-kernel NNGP (when $\nu$ is large) and a flexible model that warps its representations to fit target labels (as $\nu$ decreases).
  • Graph Mixups: The model integrates the graph adjacency matrix into the kernel recursion, enabling information sharing between neighboring nodes in the infinite-width limit.
  • Scalability: To handle large-scale graphs, the authors propose "inducing point" schemes that reduce computational complexity from cubic to linear relative to the total number of nodes, allowing the model to scale to datasets like Arxiv (169,000+ nodes).

Key Insights: Representation Learning and Homophily

The paper's most significant insight is that the necessity of representation learning is dataset-dependent. The authors categorize graphs by their homophily ratio ($h$):

  • Homophilous Graphs (High $h$): Neighbors tend to share labels (e.g., Cora, Pubmed). Here, the fixed kernel of an NNGP is often "good enough."
  • Heterophilous Graphs (Low $h$): Neighbors tend to have different labels (e.g., Roman Empire, Squirrel). In these cases, the graph structure can be misleading, and active representation learning is essential for success.
Evolution of Gram matrices $G^1$ and $G^2$ from initialization to trained states, showing alignment with target labels $YY^T$.

As illustrated in the figure above, the GC-DKM "learns" by creating block-diagonal structures in its kernels that mirror the target labels ($YY^T$). This kernel alignment is a feat impossible for standard NNGPs, which remain static after initialization. By turning up the "flexibility knob," the infinite-width model performs almost identically to a standard GCN.

Results and Performance

The GC-DKM effectively closes the performance gap between infinite-width theory and practical GCNs:

  • Heterophily Boost: On the highly heterophilous Roman Empire dataset, the flexible GC-DKM achieved 79.2% accuracy, significantly outperforming the fixed-kernel NNGP's 73.6%.
  • Graph Classification: The model was uniformly superior to NNGPs on molecular tasks (e.g., MUTAG, NCI1), suggesting that representation learning is vital for predicting chemical properties.
  • Competitive Accuracy: Across most benchmarks, the GC-DKM matched or slightly outperformed standard GCNs when compared under fair conditions (removing dropout from the GCNs).

Conclusion

The GC-DKM framework provides a theoretical tool to "dial-in" representation learning, proving that while fixed kernels suffice for simple, homophilous graphs, flexibility is paramount for complex structures. Future work may involve extending this kernelization to more complex architectures like Graph Attention Networks (GATs) and further optimizing the inducing point schemes for even larger datasets.

Summary updated

BibTeX
@article{anson2025flexible,
  author = {Ben Anson and Edward Milsom and Laurence Aitchison},
  title = {{Flexible infinite-width graph convolutional networks and the importance of representation learning}},
  journal = {Trans. Mach. Learn. Res.},
  year = {2025},
}
Figure