TL;DR
This paper introduces Control-based Graph Contrastive Learning (CGCL), a novel framework that uses network controllability metrics to create graph embeddings and perform structure-preserving data augmentation. By treating graphs as dynamical systems and ensuring that "augmented" versions retain their fundamental control properties, the authors achieve state-of-the-art results in unsupervised graph classification.
What Problem Does This Paper Address?
Learning meaningful representations (embeddings) of graphs without labeled data is a major challenge in machine learning. Contrastive Learning (CL) has emerged as a powerful solution: it works by taking an input graph, creating a slightly modified "augmented" version of it, and training a model to recognize that these two belong together (a "positive pair") while distinguishing them from other graphs ("negative pairs").
However, standard augmentation techniques—like randomly dropping edges—are often too blunt. They can accidentally destroy the very structural features (like connectivity or community patterns) that define the graph's identity. This paper addresses the need for structure-preserving augmentation by looking at graphs through the lens of control theory.
Methods
The authors propose a two-part innovation:
-
CTRL Embeddings: They treat the graph as a linear dynamical system where a subset of nodes (leaders) can influence the rest (followers). They calculate the Controllability Gramian matrix ($W$), which describes how much energy is needed to move the system to a specific state. The graph is then represented as a vector of metrics derived from this matrix, such as its trace (overall controllability), rank (dimension of controllable space), and eigenvalues.
Fig. 1: Block diagram of the proposed CGCL approach Fig 1: The CGCL pipeline. An input graph is augmented, both are converted to CTRL embeddings, and a shared encoder learns to maximize their agreement. -
Smart Augmentation: Instead of random changes, they identify a "controllability backbone"—the set of essential edges required to maintain a lower bound on the network's controllability. They propose three specific methods:
- Edge Deletion: Removing only edges not in the backbone.
- Edge Addition: Adding edges that don't decrease the controllability bound.
- Edge Substitution: A combination that keeps the total number of edges constant.
Datasets
The framework was evaluated on seven standard graph classification benchmarks:
- Bioinformatics: MUTAG, PTC_MR, PROTEINS, and DD (representing small molecules and chemical compounds).
- Social Networks: IMDB-BINARY, IMDB-MULTI, and COLLAB (representing actor ego-networks and scientific collaborations).
Key Insights and Ideas
-
Control as a Structural Probe: Network controllability is highly sensitive to topology. By varying which nodes are "leaders," the model can "probe" the graph from different angles, capturing deep structural information that simple node-degree counts might miss.
Fig. 2: Controllability metrics vary with leader selection Fig 2: Changing the leader node (red) significantly alters metrics like the trace (tr), providing unique structural signatures for the same graph. -
The Controllability Backbone: The realization that some edges are "load-bearing" for a graph's dynamical properties allows for augmentations that are "logically consistent." This ensures the model learns the true underlying structure rather than noise introduced by random perturbations.
Key Results
The proposed CGCL method demonstrated significant performance gains over existing state-of-the-art (SOTA) methods:
- Vs. Unsupervised Methods: CGCL outperformed benchmarks like graph2vec and sub2vec on almost all datasets, with gains as high as 13.0% on COLLAB and 6.76% on MUTAG.
- Vs. Self-Supervised Methods: It surpassed current SOTA models like GraphCL and InfoGraph on MUTAG, PROTEINS, and COLLAB.
- Systematic vs. Random: A key experiment compared CGCL to "Random-CGCL" (using the same embeddings but random edge dropping). CGCL consistently won, proving that the controllability-driven augmentation strategy is essential for success.
Limitations and Future Work
While the results are strong, the authors note a few areas for growth:
- Feature Preservation: Current augmentation focuses primarily on preserving the rank of controllability. Future work aims to refine these techniques to preserve a broader range of control features.
- Performance Variation: While dominant on most datasets, the method was slightly outperformed on the IMDB-MULTI dataset, suggesting that different types of networks (e.g., social vs. biological) might respond differently to control-based features.
- Scalability: Calculating the Gramian matrix for extremely large graphs can be computationally intensive, which may require more efficient approximation methods in the future.
Summary updated