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 the graph. We consider the problem of learning over this Laplacian in a distributed streaming setting, where new edges of the graph are observed in real time by a network of workers. In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L. To address this challenge, we present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances. We show that our algorithm produces sparsifiers with strong spectral approximation guarantees, all while processing edges in a single pass and in a distributed fashion.
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…
Bridging 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 AnsweringRetrievalMind the Gap: Bridging Thought Leap for Improved Chain-of-Thought Tuning
Large language models (LLMs) have achieved remarkable progress on mathematical tasks through Chain-of-Thought (CoT) reasoning. However, existing mathematical CoT datasets often suffer from Thought Leaps due to experts om…
Logical ReasoningMathematical Reasoning