Source-linked AI summary
Graph-Revised Convolutional Network
Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, Yiming Yang
TL;DR
GCNs often treat observed graphs as ground truth despite real-world noise and missing edges, while existing revision approaches face scalability or edge-addition constraints. GRCN jointly learns graph revision and node classification, and experiments report strong benchmark results, especially for incomplete graphs or sparse labels.
Problem
Many GCNs assume the observed graph faithfully represents node relationships, although real-world graphs can be noisy and incomplete.
Source: §1 · p. 1Method
GRCN jointly learns graph revision and node classification using separate GCN modules, with revision that adds edges and reweights existing ones.
Source: §1 · p. 2Results
Across six benchmark datasets, GRCN achieves the best or highly competitive results, particularly when graphs are highly incomplete or training labels are sparse.
Source: §1 · p. 2Takeaways & Limitations
For node classification, GRCN's performance stands out especially with highly incomplete input graphs or sparse labeled training instances.
Source: §6 · p. 15Fast-GRCN relies on the intuition that each node's top-K important neighbors may remain unchanged while their edge weights are adjusted.
Source: §3.3 · p. 6
Abstract
from arXiv · showhide
Graph Convolutional Networks (GCNs) have received increasing attention in the machine learning community for effectively leveraging both the content features of nodes and the linkage patterns across graphs in various applications. As real-world graphs are often incomplete and noisy, treating them as ground-truth information, which is a common practice in most GCNs, unavoidably leads to sub-optimal solutions. Existing efforts for addressing this problem either involve an over-parameterized model which is difficult to scale, or simply re-weight observed edges without dealing with the missing-edge issue. This paper proposes a novel framework called Graph-Revised Convolutional Network (GRCN), which avoids both extremes. Specifically, a GCN-based graph revision module is introduced for predicting missing edges and revising edge weights w.r.t. downstream tasks via joint optimization. A theoretical analysis reveals the connection between GRCN and previous work on multigraph belief propagation. Experiments on six benchmark datasets show that GRCN consistently outperforms strong baseline methods by a large margin, especially when the original graphs are severely incomplete or the labeled instances for model training are highly sparse.
1 Introduction
Many GCNs treat the observed graph as ground truth, although real-world graphs can be noisy, incomplete, and unsuitable for downstream tasks. GRCN revises the graph while learning node classification, and experiments report strong results, especially with incomplete graphs or sparse labels.
1 Introduction
- Real-world graphs may be noisy, incomplete, or ill-suited to downstream tasks, challenging GCNs that assume the given graph is ground truth.Ignoring these issues is described as a fundamental weakness of many existing GCN methods.Source: §1 · p. 1
- Existing graph-revision approaches either reweight observed edges without adding missing ones or parameterize every node pair at a cost that grows quadratically with graph size.Edge reweighting can remain vulnerable to noise when edges are sparse; full graph parameterization can be difficult to scale.Source: §1 · p. 2
- GRCN uses a GCN-based revision module to add edges and reweight existing ones, jointly learning graph revision and node classification with separate GCN modules.The revision module predicts unseen edges by selecting high-confidence edges from an adjacency matrix calculated via GCN-based node embeddings.Source: §1 · p. 2
- Experiments on six benchmark datasets report best or highly competitive results, especially for highly incomplete graphs or sparse training labels.The paper also presents a theoretical connection between GRCN and multigraph propagation.Source: §1 · p. 2
2 Background
The background defines graph and node-feature representations, then reviews standard GCN propagation and graph-revision approaches. It contrasts edge reweighting with full graph parameterization, whose quadratic parameter count limits scalability.
2 Background
- A graph is represented by vertices and edges or an adjacency matrix, while node features are collected in a node feature matrix.The adjacency entry A_ij indicates whether an edge connects nodes i and j.Source: §2 · p. 2
- A standard GCN propagates node features layer by layer using the adjacency matrix directly, without modifying the underlying graph.Its layers update node representations by degree-normalized aggregation of neighboring nodes.Source: §2 · p. 3
- GLCN and GAT reweight observed edges, but neither method can add edges to the graph.GLCN uses node-feature similarity; GAT uses layer-wise attention across node-neighbor pairs.Source: §2 · p. 3
- GRCN's architecture uses a graph-revision GCN to construct a revised graph for the node-classification GCN.Source: Figure 1 · p. 4
- LDS can add edges by parameterizing every possible node pair, but its N^2 parameters make it hard to scale to large graphs.Its formulation jointly learns graph structure and GCN parameters.Source: §2 · pp. 3–4
3 Proposed Method
GRCN jointly revises graph structure and trains a classifier, adding or reweighting edges using GCN-derived node similarities. KNN sparsification and Fast-GRCN address the dense similarity graph, while the analysis connects GRCN propagation to multigraphs.
3.1 Graph-Revised Convolutional Network
- GRCN uses a graph-revision module to derive node embeddings from the original graph and features, form a similarity graph, and add or reweight edges before classification.The revised graph feeds a node-classification module, and the model is trained with cross-entropy without a separate graph-revision loss.Source: §3.1 · pp. 4–5
3.2 Sparsification
- KNN sparsification retains each node’s top-K similarity scores, then symmetrizes the sparse graph; this reduces similarity-matrix storage from O(N^2) to O(NK).Only top-K values receive gradients after sparsification.Source: §3.2 · pp. 5–6
3.3 Fast-GRCN
- Fast-GRCN computes the dense similarity matrix in the first epoch, saves the KNN indices, and thereafter updates only those values, reducing time complexity to O(NK).This relies on the intuition that each node’s top-K neighbors may remain unchanged while their edge weights are adjusted during training.Source: §3.3 · p. 6
3.4 Theoretical Analysis
- Under the representer-theorem analysis, the optimized output is a linear combination of kernels on node embeddings, with dot product used for simplicity.The analysis considers a simplified GCN without feature transformations or nonlinear activations.Source: §3.4 · pp. 6–7
- The theoretical analysis frames GRCN through multigraph propagation: its feature-induced graph can participate repeatedly, unlike the analyzed propagation that uses it only once.The authors present this added flexibility as especially useful when the original graph is unreliable or insufficient for downstream tasks.Source: §3.4 · p. 7
- GRCN’s additive edge combination resembles an OR of original and feature graphs, whereas GLCN’s entrywise product resembles an AND and only reweights existing edges.The paper also describes GRCN as a more general edge combination through varying m.Source: §3.4 · pp. 7–8
4 Experiments
The experiments evaluate semi-supervised node classification on six benchmark datasets and test GRCN under incomplete graphs, sparse labels, varying K, and simplified graph-revision designs. GRCN and Fast-GRCN perform strongly across datasets; reported gains are especially notable with few retained edges or training labels.
4.1 Datasets and Baselines
- The evaluation uses six semi-supervised node-classification benchmarks, comparing vanilla GCN and SGC with GAT, LDS, and GLCN graph-revision baselines.The datasets include Cora, CiteSeer, PubMed, CoraFull, Amazon-Computers, and Coauthor CS, with fixed and random-split settings described.Source: §4.1 · pp. 8–9
4.2 Implementation Details
- Training uses Adam for 300 epochs, selects the checkpoint with highest validation accuracy, and tunes weight decay and K on the validation set.The graph-refinement and label-prediction learning rates are 1 × 10^-3 and 5 × 10^-3, respectively.Source: §4.2 · pp. 9–10
4.3 Main Results
- Across six datasets, GRCN achieves the best or highly competitive accuracy, while Fast-GRCN performs nearly as well with much lower computational time complexity.The comparison reports mean accuracy and standard deviation over 10 runs.Source: Table 2 · p. 9, §4.3 · p. 10
- At 10% edge retention, GRCN beats the second-best baseline by 6.5%, 2.5%, 1.1%, 11.0%, 4.6%, and 2.3% across the six datasets.Edge-sparse tests randomly remove edges; GAT and GLCN reweighting alone performs poorly under high incompleteness, while LDS could not be tested on four larger datasets because it does not scale.Source: §4.3 · p. 10, Figure 2 · p. 11
4.4 Robustness on Training Labels
- With edge retention fixed at 20%, GRCN’s advantage over other models grows as the number of training labels per class falls from 15 to 5.This comparison covers Cora-Full, Amazon Computers, and Coauthor CS; the paper frames the finding as robustness to sparse training labels.Source: §4.4 · pp. 10–11, Table 3 · p. 12
4.5 Hyperparameter Analysis
- On Cora, accuracy initially improves as K increases, then declines after a peak, with the authors conjecturing that larger K adds noise to the revised graph.K-nearest-neighbor sparsification turns the dense similarity graph into a sparse graph, supporting efficiency as well as effectiveness.Source: §4.5 · pp. 11–12
4.6 Ablation Study
- On Cora, ablations indicate that residual original-graph links help, graph propagation improves feature-based construction, and feature learning matters most at low edge retention.The comparisons include SVD reconstruction, feature-only (FO), feature plus graph (FG), and random-walk feature plus graph (RWFG).Source: §4.6 · pp. 12–13
5 Related Work
Related work spans graph convolution methods that aggregate graph information or revise existing edges, and link-prediction methods that identify missing links. This paper instead revises graphs to improve downstream node classification.
5.1 Graph Convolutional Network
- Graph convolution includes spectral methods operating in the graph Laplacian’s Fourier domain and spatial methods aggregating nearby nodes; GraphSage samples adjacent nodes.GAT and GLCN reweight the original graph, while LDS reconstructs the entire graph through bilevel optimization; the paper positions its revision strategy as efficient and flexible.Source: §5.1 · pp. 13–14
5.2 Link prediction
- Unlike link-prediction work that treats missing-link identification as its objective, this paper revises edges to improve node classification through GCNs.Prior link-prediction approaches include neighborhood heuristics and neural methods that learn general structural features.Source: §5.2 · p. 14
6 Conclusion
The conclusion presents GRCN as graph revision integrated into graph convolution, with theoretical and experimental support for improved downstream prediction. Its node-classification performance stands out on highly incomplete graphs and with sparse training labels.
6 Conclusion
- GRCN incorporates graph revision into graph convolution networks, and the paper reports theoretical and experimental evidence of improved downstream prediction accuracy.The authors identify knowledge-base completion, epidemiological forecasting, and aircraft anomaly detection as future task areas.Source: §6 · pp. 14–15
- GRCN addresses prior approaches’ scaling issues or failure to consider missing edges, and stands out when graphs are highly incomplete or training labels are sparse.The conclusion limits this performance claim to the paper’s node-classification experiments.Source: §6 · p. 15