Improved large-scale graph learning through ridge spectral sparsification
The representation and learning benefits of methods based on graph Laplacians, such as Laplacian smoothing or harmonic function solution for semi-supervised learning (SSL), are empirically and theoretically well supported. Nonetheless, the exact versions of these methods scale poorly with the number of nodes $n$ of the graph. In this paper, we combine a spectral sparsification routine with Laplacian learning. Given a graph $G$ as input, our algorithm computes a sparsifier in a distributed way in $O(n\log^3(n))$ time, $O(m\log^3(n))$ work and $O(n\log(n))$ memory, using only $\log(n)$ rounds of communication. Furthermore, motivated by the regularization often employed in learning algorithms, we show that constructing sparsifiers that preserve the spectrum of the Laplacian only up to the regularization level may drastically reduce the size of the final graph. By constructing a spectrally-similar graph, we are able to bound the error induced by the sparsification for a variety of downstream tasks (e.g., SSL). We empirically validate the theoretical guarantees on Amazon co-purchase graph and compare to the state-of-the-art heuristics.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph LearningSimilar Papers 제목 키워드 기반
Learning Large-Scale MTP$_2$ Gaussian Graphical Models via Bridge-Block Decomposition
This paper studies the problem of learning the large-scale Gaussian graphical models that are multivariate totally positive of order two ($\text{MTP}_2$). By introducing the concept of bridge, which commonly exists in la…
Improved large-scale graph learning through ridge spectral sparsification
Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Laplacian L, which encodes the structure of …
Graph LearningBridging Code Graphs and Large Language Models for Better Code Understanding
Large Language Models (LLMs) have demonstrated remarkable performance in code intelligence tasks such as code generation, summarization, and translation. However, their reliance on linearized token sequences limits their…
Code TranslationCode GenerationEnhancing Bridge Deck Delamination Detection Based on Aerial Thermography Through Grayscale Morphologic Reconstruction: A Case Study
Environmental-induced temperature variations across the bridge deck were one of the major factors that degraded the performance of delamination detection through thermography. The non-uniformly distributed thermal backgr…
ClusteringQuantizationA STEP towards Interpretable Multi-Hop Reasoning:Bridge Phrase Identification and Query Expansion
We propose an unsupervised method for the identification of bridge phrases in multi-hop question answering (QA). Our method constructs a graph of noun phrases from the question and the available context, and applies the …
Multi-hop Question AnsweringQuestion AnsweringRetrieval