  In graph learning, there have been two predominant inductive biases regarding
graph-inspired architectures: On the one hand, higher-order interactions and
message passing work well on homophilous graphs and are leveraged by GCNs and
GATs. Such architectures, however, cannot easily scale to large real-world
graphs. On the other hand, shallow (or node-level) models using ego features
and adjacency embeddings work well in heterophilous graphs. In this work, we
propose a novel scalable shallow method -- GLINKX -- that can work both on
homophilous and heterophilous graphs. GLINKX leverages (i) novel monophilous
label propagations, (ii) ego/node features, (iii) knowledge graph embeddings as
positional embeddings, (iv) node-level training, and (v) low-dimensional
message passing. Formally, we prove novel error bounds and justify the
components of GLINKX. Experimentally, we show its effectiveness on several
homophilous and heterophilous datasets.
