Clustering Node Attributed Networks with Graph Neural Networks and Self Learning

Technical Summary: Clustering Node Attributed Networks with Graph Neural Networks and Self Learning

Problem Formulation
The paper addresses the problem of clustering nodes in attributed networks, where each node possesses both topological connections (edges) and feature attributes. The goal is to partition the node set into disjoint subsets (communities) that reflect latent structures by jointly leveraging network topology and node attributes. Crucially, the work operates in a fully unsupervised setting, meaning no ground-truth cluster labels are available during training; the only inputs are the graph structure, node attributes, and the target number of clusters ($K$). The authors note that while joint clustering is intuitively superior to using only topology or only attributes, designing algorithms that effectively fuse these signals—especially when one source is noisy—is non-trivial.

Methodology: DCSL-GNN
The authors propose Dynamic Context Self-Learning Graph Neural Network (DCSL-GNN), a framework that operates in iterative rounds to refine node representations and cluster assignments. The framework consists of three interconnected modules:

1. Dynamic Context Generation:

   • Standard Graph Neural Networks (GNNs) often suffer from "under-reaching" (insufficient depth to capture distant cluster centers) or "over-smoothing" (loss of distinctiveness with too many layers). To mitigate this, DCSL-GNN constructs a Context Graph ($G_c$) for each round, which differs from the original graph.
   • Virtual Edges: The context graph introduces "virtual edges" connecting nodes to the nearest neighbors of their cluster's center of mass (in the representation space). This allows information from cluster centers to propagate directly, bypassing the need for deep GNN layers.
   • Random Walks: The context graph is generated via biased random walks. At each step, the walk either follows an original edge (weighted by the similarity of node representations from the previous round) or jumps via a virtual edge to a node near a cluster center.
   • Importance-Based Neighborhoods: The neighborhood of a node in $G_c$ is determined by the visit counts of random walks starting from that node, utilizing a threshold based on the $k$-th percentile of visit distribution. This ensures that the most influential nodes (even if distant in the original graph) become direct neighbors in the context graph.

2. Embedding (GNN Encoder):

   • A standard GCN encoder processes the context graph $G_c$ and node attributes to generate node embeddings.
   • Edge Weights: Edges in $G_c$ are weighted dynamically. If the attributes of connected nodes are highly similar (verified by a silhouette coefficient threshold $\beta$), the edge weight is inversely proportional to the Euclidean distance between their attributes. Otherwise, the weight remains neutral (1).
   • Training: The GNN parameters are trained using a triplet loss function. This loss minimizes the distance between an anchor node and positive samples (nodes in the same cluster) while maximizing the distance to negative samples (nodes in different clusters).
   • Parameter Persistence: Unlike standard training, the GNN weights learned in round $r$ are initialized with the values from round $r-1$, allowing the model to refine its understanding over time without retraining from scratch.

3. Clustering and Self-Learning Loop:

   • The generated embeddings are fed into a standard K-means algorithm to produce cluster assignments.
   • These new cluster assignments are then used to update the cluster centers and the random walk biases for the next round.
   • This creates a self-reinforcing mechanism: better representations lead to better clusters, which in turn generate better context graphs and representations for the subsequent round.

Key Contributions

• Novel Framework: The introduction of DCSL-GNN, a fully unsupervised framework that iteratively refines node representations through a self-learning loop.
• Dynamic Context Graph: A mechanism to construct a context graph that combines original topology with virtual edges to cluster centers, effectively addressing the depth limitations of GNNs without requiring excessive layers.
• Self-Learning Mechanism: An iterative process where clustering results from one round directly influence the graph structure (context) and edge weights of the next, allowing the model to progressively denoise and align topology with attributes.
• Robustness to Noise: The methodology is designed to leverage the more reliable information source (either topology or attributes) to correct the noisier source.

Experimental Results
The authors evaluated DCSL-GNN on synthetic data (Attributed Stochastic Block Models) and three real-world benchmark datasets (Cora, Citeseer, PubMed).

• Synthetic Data:

  • Self-Learning Efficacy: Multiple rounds of self-learning consistently outperformed a single long round of training (equivalent to classic GNN clustering).
  • Noise Handling: The framework successfully extracted information from the reliable source when the other was noisy. For instance, when network information was very noisy ($p_I=0.2$) but attributes were clean, performance improved over rounds. Conversely, when attributes were noisy but the network was clean, the model also converged well. However, when both sources were highly noisy, performance degraded to random guessing, as expected.
  • Comparison: DCSL-GNN outperformed algorithms relying solely on network structure (Louvain) or solely on attributes (K-means) in scenarios where neither source was perfectly informative.

• Real Datasets:

  • Citeseer: DCSL-GNN achieved the highest Normalized Mutual Information (NMI) among all compared state-of-the-art methods.
  • Cora and PubMed: The model performed competitively but did not surpass the state-of-the-art (MGCCN for Cora, SEComm for PubMed).
  • Limitation: The authors attribute the lower performance on Cora and PubMed partly to cluster imbalance. The model showed high accuracy for dominant clusters but negligible accuracy for smaller clusters, suggesting a bias toward larger groups in the objective function.

Significance and Claims
The paper claims that DCSL-GNN offers a flexible approach to attributed graph clustering that effectively fuses structural and attribute information without supervision. The authors emphasize that the multi-round self-learning is a critical component, as it allows the model to iteratively refine the "context" in which nodes are viewed, leading to superior clustering compared to single-round approaches.

The authors modestly conclude that while the method is highly effective in scenarios with balanced clusters or mixed noise levels (as demonstrated on Citeseer and synthetic data), it faces challenges with highly imbalanced real-world datasets. They assert that the framework demonstrates the potential of self-learning mechanisms to improve node representations and clustering quality in the absence of labeled data, though it does not claim to be a universal solution superior to all existing methods across all dataset characteristics.