Abstract
Graph Neural Networks (GNNs) typically rely on optimizing existing graph structures for semi-supervised learning (SSL). However, real-world graphs are often noisy or sparse, violating the core homophily assumption. This paper introduces ELCO (ELectoral COllege), a novel pre-processing framework that augments graphs by generating synthetic "elector" nodes to summarize dense subgraphs. By adding these high-quality nodes and edges, ELCO significantly improves feature separability, shortens long-range dependencies, and boosts the performance of standard models like GCN and GAT to state-of-the-art levels.
Introduction
In graph-based SSL, models like Graph Convolutional Networks (GCNs) predict labels for unlabeled nodes using a small set of labeled examples. These models assume that connected nodes share similar labels. In practice, however, graph topologies and node attributes often contain noise, meaning the observed graph may not perfectly reflect the underlying label distribution.
While previous research has focused on optimizing existing graph topology—such as through edge dropping or multi-hop connections—these methods are limited to the original node set. ELCO addresses this by expanding the graph with newly generated, high-quality nodes and edges to better guide the learning process. This approach acts as a graph augmentation step that enhances both structural and attribute quality before training.
Methodology
ELCO is a heuristic pre-processing pipeline inspired by the US voting system. It transforms an original graph into an augmented version through four primary stages:
- Constituency Division: The algorithm employs overlapping clustering (specifically the Ego-Splitting algorithm) to partition the original graph into dense subgraphs, or "constituencies."
- Elector Generation: For each cluster, a new "elector" node is created. Its features are derived by averaging the attributes of the original "voter" nodes within that cluster. This averaging acts as a noise-reduction mechanism.
- Label Assignment: Electors inherit labels from their constituent voter nodes via a "winner-takes-all" majority rule. For clusters without labeled voters, ELCO uses a self-learning scheme: a Gradient Boosting Decision Tree (GBDT) is trained on labeled electors to predict labels for unlabeled ones.
- Graph Augmentation: These elector nodes are integrated into the graph and connected to all voter nodes in their respective clusters. This augmented graph is then used for training standard GNNs.
Key Insights
Feature Separability through Averaging
By averaging the attributes of voter nodes to create an elector, the process effectively samples from the underlying distribution multiple times. This significantly reduces attribute noise. A linear SVM trained on elector node attributes achieved an error rate of just 4.41% on the Cora dataset, compared to 28.23% for original voter nodes, demonstrating a massive leap in feature quality.
Structural Optimization
Connecting an elector node to all voter nodes in its cluster turns the elector into a central hub. This structural change reduces the maximum distance between any two nodes in a dense subgraph to exactly two hops, facilitating more efficient message passing and mitigating the issues of long-range dependencies in deep GNNs.
Experimental Results
The framework was evaluated on three standard citation benchmarks: Cora, Citeseer, and Pubmed. ELCO-GAT achieved new state-of-the-art (SOTA) accuracies on all three, outperforming 19 strong baselines. Specifically, adding ELCO improved base GCN accuracy by 4.1% to 5.4% and base GAT accuracy by 4.2% to 4.7%.
Visual analysis via t-SNE (above) confirms that elector nodes form much tighter, more distinct clusters in the feature space compared to the original voter nodes. This clarity allows self-learning mechanisms (like pseudo-labeling) to thrive, as the synthetic data is far less noisy than the original input.
Furthermore, ELCO demonstrated significant robustness to edge sparsity. In experiments where edges were randomly deleted, ELCO maintained high performance levels much longer than standard GCN or GAT models, proving that the generated elector nodes successfully compensate for missing structural information.
Conclusion and Future Work
ELCO provides a powerful, model-agnostic pre-processing step for graph-based SSL. While highly effective, the authors note potential limitations: extremely sparse or saturated graphs may hinder high-quality elector generation, and overlapping clustering can introduce computational overhead. Future work will explore ELCO's application in inductive learning, link prediction, and data completion, as well as refining the augmentation strategies beyond the current heuristic framework.
Summary updated