CiGNN: A Community-induced Graph Neural Network

Shi Yin Hong

Author: Shi Yin Hong | Major: Computer Engineering and Computer Science | Semester: Fall 2023

I am Shi Yin Hong (Computer Engineering & Computer Science — College of Engineering). This semester, I have been working on my Graph Neural Network (GNN) project under the guidance of Dr. Lu Zhang. The goal of the project is to improve the interpretability of subgraph GNN. Following, we propose a framework for subgraph GNNs, termed Community-induced Graph Neural Network (CiGNN), that endows an intuitive interpretability basis for subgraph GNNs by capturing the dynamics of inherent structural community topology in subgraph representation realization relative to individual nodes. Our modular framework supports multiple mainstream GNN base models, making CiGNN a general module easily adaptable to existing GNN or subgraph GNN models with intuitive interpretability.

CiGNN originally started as a hobby project and a self-challenge. Then, Dr. Zhang, who taught me the first class I had with our Department of Electrical Engineering and Computer Science in the Fall of 2020, kindly accepted to be my Honors thesis advisor for the project in Fall 2022. We affirmed the direction of the research together on subgraph GNN. Then, Dr. Zhang has been patiently guiding me ever since to transform CiGNN from intangible ideas into a concrete computational implementation that bridges gaps between our understanding of interpretability in subgraph GNN.

This project helps me to see the interconnects among graph representational learning, statistical physics, and network analysis. Specifically, we address the interpretability gap in subgraph GNN by approaching subgraph formulation with a theoretical basis from the Reichardt and Bornholdt’s Potts (RBP) model and Louvain-based community optimization methods. We present CiGNN, a lightweight subgraph GNN framework that captures community relationships among nodes. We propose four variants of CiGNN in establishing graph representations from community-induced local subgraphs. Experimental results on six benchmark graph classification datasets show that CiGNN achieves competitive performance against subgraph GNN baselines and recent state-of-the-art GNNs. The process of completing the manuscript also helps me to improve in scientific communication.

One challenge during the project was ensuring the explainability of our architectural design. By the end of Spring 2023, we achieved great preliminary results from our initial model – CiGNN v.0. However, we noted that the CiGNN v.0 did not maximize the utilization of intercommunity knowledge during its graph representation formulation, limiting its explainability of the model. In turn, Dr. Zhang and I worked closely throughout the summer to polish CiGNN’s architectural design. Specifically, Dr. Zhang advised that intercommunity knowledge should be exchanged among community-induced subgraphs during the message-passing phase in building subgraph representation. After iterations of implementing new architectures and running new experiments, we finalize CiGNN to make it account for intercommunity and intracommunity knowledge in subgraph representation formulation in deriving the final graph representation.

I look forward to completing this project under the mentorship of Dr. Zhang. Without his patience and support, the process could not have been rewarding. The next step for this closing project is to complete the Honors thesis defense after the Winter break. Overall, this research experience helps to understand the importance of grit and open-mindedness in research.