Graph-Revised Convolutional Network
This addresses the issue of sub-optimal solutions in GCNs due to treating incomplete graphs as ground-truth, which is a domain-specific problem for machine learning applications involving graph data.
The paper tackles the problem of incomplete and noisy real-world graphs in Graph Convolutional Networks (GCNs) by proposing the Graph-Revised Convolutional Network (GRCN), which predicts missing edges and revises edge weights via joint optimization, resulting in consistent outperformance of strong baselines by a large margin on six benchmark datasets.
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.