arXiv (Cornell University) · 2020 · 171 citations · 34 references
ComputingComputer ScienceArtificial IntelligenceFeature EngineeringMachine LearningGraph AlgorithmsGraph TheoryGraph-based LearningNeural NetworksRepresentation LearningSemi-supervised LearningGraph ClassificationGraph Neural NetworksGraph Representation LearningGraph Structure LearningGraph-based Semi-supervised LearningSemi-supervised ClassificationSemi-supervised Graph Neural NetworksSemi-supervised Learning On Graphs
We investigate the representation power of graph neural networks in the semi-supervised node classification task under heterophily or low homophily, i.e., in networks where connected nodes may have different class labels and dissimilar features. Many popular GNNs fail to generalize to this setting, and are even outperformed by models that ignore the graph structure (e.g., multilayer perceptrons). Motivated by this limitation, we identify a set of key designs -- ego- and neighbor-embedding separation, higher-order neighborhoods, and combination of intermediate representations -- that boost learning from the graph structure under heterophily. We combine them into a graph neural network, H2GCN, which we use as the base method to empirically evaluate the effectiveness of the identified designs. Going beyond the traditional benchmarks with strong homophily, our empirical analysis shows that the identified designs increase the accuracy of GNNs by up to 40% and 27% over models without them on synthetic and real networks with heterophily, respectively, and yield competitive performance under homophily.
34
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
Birds of a Feather: Homophily in Social Networks
Miller McPherson, Lynn Smith‐Lovin, James M. Cook · Annual Review of Sociology · 2001 · 18.6K citations
Deep Learning On Graphs (Graphsip Summer School)
Michaël Defferrard · Figshare · 2016 · 5.1K citations
Inductive Representation Learning on Large Graphs
William L. Hamilton, Rex Ying, Jure Leskovec · arXiv (Cornell University) · 2017 · 4.5K citations · Full text