Spectral graph sparsification preserves geometry of GNN embeddings.
problem Maintaining geometric properties of graph neural network embeddings during sparsification.
method Proving spectral sparsification preserves squared pairwise distances, class means, and covariance structure in embedding space.
result Spectral sparsification preserves the geometry of learned embeddings in GNNs.
FastGAT reduces GNN computation time by 10x using graph sparsification.
problem High computational burden in attention-based GNNs.
method Spectral sparsification to generate optimal graph pruning.
result Per-epoch time is almost linear in graph nodes, reducing computational time by up to 10x.
Empirical error estimates improve graph sparsification reliability.
problem Uncertainty in sparsification error limits downstream computations reliability.
method Data-driven approach to compute empirical error estimates.
result Empirical error estimates provide theoretical guarantees and are computationally feasible.
This paper improves GNN efficiency for large-scale graph applications.
problem High memory usage and computational costs in large-scale graph applications.
method Sparsification techniques from Network Science and Machine Learning.
result Adaptive rewiring enhances GNN performance and scalability.
Spectral sparsification improves Gaussian graphical models under MTP2 constraints.
problem Learning accurate, sparse graphs from data under MTP2 constraints.
method Spectral graph sparsification applied to Gaussian graphical models.
result Spectral-MTP2 preserves MTP2 and approximates the original model well.
Spectral sparsification improves Laplacian-constrained graph learning.
problem Improving accuracy of Laplacian-constrained graph learning.
method Spectral graph sparsification as a post-estimation operation.
result Improved accuracy of Laplacian-constrained graph learning.
While the harmonic function solution performs well in many semi-supervised learning (SSL) tasks, it is known to scale poorly with the number of samples. Recent successful and scalable methods, such as the eigenfunction method focus on efficiently approximating the whole spectrum of the graph Laplacian constructed from …
Proposes a GNN for multivariate time-series prediction with filtering.
problem Low signal-to-noise ratio in complex systems data.
method Integrates a spatial-temporal GNN with a matrix filtering module to generate filtered graphs.
result Proposed model outperforms baseline approaches in multivariate time-series prediction.
Graphs from features improve classification accuracy in tasks.
problem Traditional classification tasks can be improved by incorporating relational information.
method Construct geometric graphs from features and use them in Graph Convolutional Networks.
result Graphs derived from features increase classification accuracy and improve class separation.
Proposes a method to improve GNN predictions by finding the most predictive subgraph.
problem GNNs aggregate all nodes and edges, making predictions hard to interpret.
method Uses reinforcement learning to find a sparse subgraph that optimizes graph classification performance.
result Our method finds sparser subgraphs that improve interpretability while maintaining performance.
The paper develops a method to sparsify magnetic Laplacians using multi-type spanning forests.
problem Sparsifying magnetic Laplacians for large and dense graphs.
method Sampling multi-type spanning forests using a determinantal point process.
result The method provides statistical guarantees for estimating the connection Laplacian.
The eigendeomposition of nearest-neighbor (NN) graph Laplacian matrices is the main computational bottleneck in spectral clustering. In this work, we introduce a highly-scalable, spectrum-preserving graph sparsification algorithm that enables to build ultra-sparse NN (u-NN) graphs with guaranteed preservation of the or…
Proposes an offline active learning method for graphs.
problem Active learning on graphs where labeling is expensive.
method Two-stage biased sampling strategy considering informativeness and representativeness.
result Establishes a theoretical relationship between generalization error and number of nodes selected.
A new method efficiently approximates Gromov-Wasserstein distance.
problem High computational complexity of Gromov-Wasserstein distance.
method Importance sparsification method to construct a sparse coupling matrix.
result Efficient approximation of GW distance with reduced complexity.
Graphs can model interactions between vertices, but how well depends on graph structure.
problem Lack of formal characterization of GNNs' ability to model interactions between vertices.
method Formalized interaction strength using separation rank and quantified it for different partitions of vertices.
result GNNs' ability to model interactions is primarily determined by the partition's walk index.
S-VNNs improve VNNs by sparsifying covariance matrices.
problem Spurious correlations in covariance matrices degrade VNNs' performance and efficiency.
method Apply sparsification techniques on sample covariance matrix and integrate into VNN architecture.
result S-VNNs achieve improved performance, stability, and reduced computational time.
We study epidemic forecasting on real-world health data by a graph-structured recurrent neural network (GSRNN). We achieve state-of-the-art forecasting accuracy on the benchmark CDC dataset. To improve model efficiency, we sparsify the network weights via transformed-ℓ1 penalty and maintain prediction accuracy at…
We derive a new proof to show that the incremental resparsification algorithm proposed by Kelner and Levin (2013) produces a spectral sparsifier in high probability. We rigorously take into account the dependencies across subsequent resparsifications using martingale inequalities, fixing a flaw in the original analysis…
Unified framework sparsifies GNNs for faster inference on large graphs.
problem Space and computational bottlenecks in GNNs due to graph size and connectivity.
method Unified GNN sparsification (UGS) framework that prunes graph adjacency matrix and model weights.
result Graph lottery tickets (GLTs) can be trained in isolation to match full model performance.
Gradient sparsification enhances privacy-preserving machine learning models.
problem Improving performance of differentially-private machine learning models under privacy constraints.
method Gradient sparsification combined with compressed sensing and additive Laplace noise.
result Gradient sparsification can improve performance of differentially-private machine learning models for small privacy budgets.
Method estimates travel times on urban roads using Uber data.
problem Estimating travel times on urban roads where data is scarce.
method Graph representation, trip sampling, least-squares optimization.
result Estimates travel times on arterial roads using aggregated Uber data.
Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for graph sparsification. This choice is motivated by the observation…
Many machine learning frameworks, such as resource-allocating networks, kernel-based methods, Gaussian processes, and radial-basis-function networks, require a sparsification scheme in order to address the online learning paradigm. For this purpose, several online sparsification criteria have been proposed to restrict …
We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial Lα(G)=D−∑r=1dαrD(D−1A)r where A is the adjacency matrix of a weighted, undirected graph, D is the diagonal matrix of weighted degrees, and α=(α1...αd) are nonn…
New method sparsifies hybrid neural ODEs for better performance and stability.
problem Excessive latent states and interactions from mechanistic models lead to training inefficiency and over-fitting.
method Automatic state selection and structure optimization combining domain-informed graph modifications with data-driven regularization.
result Improved predictive performance and robustness with desired sparsity.
A new federated learning framework with sparsification and adaptive optimization for privacy and efficiency.
problem Lack of sufficient privacy protection in federated learning.
method Integrates random sparsification with gradient perturbation and acceleration techniques to enhance privacy and efficiency.
result Outperforms previous differentially-private federated learning approaches in privacy and efficiency.
We show implicit filter level sparsity manifests in convolutional neural networks (CNNs) which employ Batch Normalization and ReLU activation, and are trained with adaptive gradient descent techniques and L2 regularization or weight decay. Through an extensive empirical study (Mehta et al., 2019) we hypothesize the mec…
Distributed model training suffers from communication overheads due to frequent gradient updates transmitted between compute nodes. To mitigate these overheads, several studies propose the use of sparsified stochastic gradients. We argue that these are facets of a general sparsification method that can operate on any p…
Large scale machine learning is increasingly relying on distributed optimization, whereby several machines contribute to the training process of a statistical model. In this work we study the performance of asynchronous, distributed settings, when applying sparsification, a technique used to reduce communication overhe…
2D-PT improves sampling in constrained optimization problems.
problem Sampling Boltzmann distributions with soft constraints.
method Two-dimensional extension of parallel tempering.
result 2D-PT achieves near-ideal mixing in constrained problems.
Bayesian sparsification reduces deep neural network complexity.
problem Complexity of deep neural networks limits their performance.
method Combines Bayesian shrinkage priors with stochastic variational inference.
result Bayesian model reduction (BMR) is a more efficient alternative for pruning model weights.
This paper proposes a method to reveal task relationships in multi-task learning models using sparse graphs.
problem Understanding the underlying task relationships in multi-task learning models.
method Proposes a bilevel formulation of multi-task learning that induces sparse graphs.
result The method improves interpretability of multi-task learning models without sacrificing generalization performance.
Deep neural networks have significantly alleviated the burden of feature engineering, but comparable efforts are now required to determine effective architectures for these networks. Furthermore, as network sizes have become excessively large, a substantial amount of resources is invested in reducing their sizes. These…
Modern large scale machine learning applications require stochastic optimization algorithms to be implemented on distributed computational architectures. A key bottleneck is the communication overhead for exchanging information such as stochastic gradients among different workers. In this paper, to reduce the communica…
Learning meaningful graphs from data plays important roles in many data mining and machine learning tasks, such as data representation and analysis, dimension reduction, data clustering, and visualization, etc. In this work, for the first time, we present a highly-scalable spectral approach (GRASPEL) for learning large…
Recently, a lot of techniques were developed to sparsify the weights of neural networks and to remove networks' structure units, e.g. neurons. We adjust the existing sparsification approaches to the gated recurrent architectures. Specifically, in addition to the sparsification of weights and neurons, we propose sparsif…
Efficiently sparsifies simplicial complexes using local densities of states.
problem Prohibitive computational requirements for dense simplicial complexes.
method Probabilistic sparsification using local densities of states and kernel-ignoring decomposition.
result Approximates the spectrum of the original SC with a sparser surrogate SC.
New sparsification technique for SGD reduces communication costs.
problem High communication costs in distributed SGD for large-scale models.
method Statistical estimation model for sparsity and skewness of stochastic gradients.
result Concatenated top-k and random-k sparsification outperforms individual methods.
In graph neural networks (GNNs), pooling operators compute local summaries of input graphs to capture their global properties, and they are fundamental for building deep GNNs that learn hierarchical representations. In this work, we propose the Node Decimation Pooling (NDP), a pooling operator for GNNs that generates c…
New algorithm improves distributed SGD with random sparsification for better convergence and generalization.
problem Communication bottleneck in distributed deep learning.
method Proposes detached error feedback (DEF) algorithm to improve convergence and generalization of communication-efficient distributed SGD.
result Shows better convergence and generalization bounds than existing methods.
In this paper, we investigate effective sketching schemes via sparsification for high dimensional multilinear arrays or tensors. More specifically, we propose a novel tensor sparsification algorithm that retains a subset of the entries of a tensor in a judicious way, and prove that it can attain a given level of approx…
Distributed stochastic gradient descent (SGD) algorithms are widely deployed in training large-scale deep learning models, while the communication overhead among workers becomes the new system bottleneck. Recently proposed gradient sparsification techniques, especially Top-k sparsification with error compensation (To…
Bayesian sparsification improves complex-valued neural networks by 50-100x with minimal performance loss.
problem Efficiently compressing complex-valued neural networks for embedded systems.
method Extending Sparse Variational Dropout to complex-valued networks and conducting a numerical study.
result Achieved state-of-the-art performance on MusicNet with 50-100x compression.
Bayesian approach sparsifies neural networks efficiently.
problem Efficiently pruning neural networks to save resources.
method Sparsifiability via the Marginal likelihood (SpaM) framework.
result Prunes neural networks effectively without significant loss in performance.
New sparsification theorem for Gaussian processes reduces dimensionality.
problem Dimension-independent sparsification of Gaussian process suprema.
method Dimension-independent sparsification of Gaussian process suprema.
result Sparsifier size is independent of ∣T∣ and n. New architectures improve KANs, making them more interpretable and accurate.
problem Improving Kolmogorov-Arnold networks while maintaining interpretability.
method Overprovisioned architectures combined with sparsification, deep supervision, and depth selection, optimized with a minimum description length objective.
result Combining sparsification with depth selection achieves competitive or superior accuracy while discovering smaller models.
New regularization techniques improve stability of deep neural networks.
problem Improving stability of deep neural networks in high-dimensional data.
method Apply manifold regularization to develop new regularizers based on graph Laplacian sparsification.
result Empirically, networks achieve high stability in various perturbation models, including adversarial attacks.
Graph-based semi-supervised learning for aspect term extraction.
problem Aspect term detection and sentiment analysis in reviews.
method Label spreading algorithm on graph sparsified by kNN for efficient classification.
result The approach achieves good results with limited labeled data.