Forming an Electoral College for a Graph: a Heuristic Semi-supervised Learning Framework.

Chen Li, Xutan Peng, Hao Peng, Jianxin Li, Lihong Wang, Philip S. Yu

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:

  1. Constituency Division: The algorithm employs overlapping clustering (specifically the Ego-Splitting algorithm) to partition the original graph into dense subgraphs, or "constituencies."
  2. 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.
  3. 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.
  4. 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.
The ELCO pipeline: from overlapping clustering to graph augmentation with elector nodes.

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%.

t-SNE visualizations comparing the feature separability of original voter nodes vs. synthetic elector nodes across three datasets.

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

Abstract

Recently, graph-based algorithms have drawn much attention because of their impressive success in semi-supervised scenarios. For better model performance, previous studies learn to transform the topology of the input graph. However, these works only focus on optimizing the original nodes and edges, leaving the direction of augmenting existing data unexplored. In this paper, by simulating the generation process of graph signals, we propose a novel heuristic pre-processing technique, namely ELectoral COllege (ELCO), which automatically expands new nodes and edges to refine the label similarity within a dense subgraph. Substantially enlarging the original training set with high-quality generated labeled data, our framework can effectively benefit downstream models. To justify the generality and practicality of ELCO, we couple it with the popular Graph Convolution Network and Graph Attention Network to extensively perform semi-supervised learning evaluations on three standard datasets. In all setups tested, our method boosts the average score of base models by a large margin of 4 points, as well as consistently outperforms the state-of-the-art. Please find our code at this https URL.
BibTeX
@misc{li2020forming,
  author = {Chen Li and Xutan Peng and Hao Peng and Jianxin Li and Lihong Wang and Philip S. Yu},
  title = {{Forming an Electoral College for a Graph: a Heuristic Semi-supervised Learning Framework.}},
  year = {2020},
  eprint = {2006.06469},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.06469},
}
Figure