Please register for the CV & Online Identity Workshop below.

Register for this talk here. You will receive the Zoom link the day before the talk.

Node classification is an important problem in graph data. It is commonly solved by various label propagation methods (such as belief propagation or linearized belief propagation) that work iteratively starting from a few labeled seed nodes. For graphs with arbitrary potentials (also called compatibilities or attractions) between classes (i.e. going beyond the assortative mixing assumption and explicitly allowing heterophily like in general Markov random fields), these methods crucially depend on knowing the compatibilities between neighboring labels. This information must be provided by either domain experts or heuristics before any label algorithm to work. Can we instead directly estimate the compatibilities from extremely sparsely labeled graphs in a way that scales to networks with millions of edges? We answer this question affirmatively and suggest a method called distant compatibility estimation that works even on extremely sparsely labeled graphs (e.g., 1 in 10,000 nodes is labeled) in a fraction of the time it later takes to label the remaining nodes. Our approach first creates multiple factorized graph representations (with size independent of the graph) and then performs estimation on these smaller graph summaries. We refer to algebraic amplification as the more general idea of leveraging algebraic properties of an algorithm’s update equations to amplify sparse signals. Our experiments show that our estimator is by orders of magnitude faster than alternative textbook approaches and that the end-to-end classification accuracy is comparable to using gold standard compatibilities. This makes it a cheap preprocessing step for any existing label propagation method and removes the current dependence on heuristics. It remains to be seen whether any of the more recent GNN approaches can be extended to work in a similar sparse regime.

[1] VLDB 2015: Linearized and Single-pass Belief Propagation. http://www.vldb.org/pvldb/vol8/p581-gatterbauer.pdf
[2] SIGMOD 2020: Factorized Graph Representations for Semi-Supervised Learning from Sparse Data. https://arxiv.org/pdf/2003.02829