We propose Sparse Neural Network architectures that are based on random or structured bipartite graph topologies. Sparse architectures provide compression of the models learned and speed-ups of computations, they can also surpass their unstructured or fully connected counterparts. As we show, even more compact topologi…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “sparsely connected graphs”
This work introduces a method to compare sparse neural network topologies using graph theory.
problem Comparing and understanding sparse neural network topologies, especially during training.
method Introducing Neural Network Sparse Topology Distance (NNSTD) to measure distances between different sparse neural networks.
result Sparse neural networks can outperform over-parameterized models without further structure optimization.
We introduce Graph-Sparse Logistic Regression, a new algorithm for classification for the case in which the support should be sparse but connected on a graph. We val- idate this algorithm against synthetic data and benchmark it against L1-regularized Logistic Regression. We then explore our technique in the bioinformat…
Proposes RBGP framework for efficient block sparse neural networks.
problem Efficiently exploit structured sparsity patterns for sparse neural networks on GPU.
method Uses Ramanujan Bipartite Graph Product to generate structured multi-level block sparse neural networks.
result Achieves 5-9x and 2-5x runtime gains over unstructured and block sparsity patterns respectively, while maintaining accuracy.
Graphs are naturally sparse objects that are used to study many problems involving networks, for example, distributed learning and graph signal processing. In some cases, the graph is not given, but must be learned from the problem and available data. Often it is desirable to learn sparse graphs. However, making a grap…
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.
NGRs merge sparse graph recovery with PGMs for efficient probabilistic inference.
problem Efficiently recover sparse graphs and learn distributions over variables.
method Integrates sparse graph recovery methods with PGMs using Graph-constrained path norm.
result NGRs can handle multimodal data and perform sparse graph recovery and probabilistic inference.
We propose a framework to model the distribution of sequential data coming from a set of entities connected in a graph with a known topology. The method is based on a mixture of shared hidden Markov models (HMMs), which are jointly trained in order to exploit the knowledge of the graph structure and in such a way that …
New algorithms reduce communication in GNN training.
problem Higher communication costs in GNNs due to sparse connectivity.
method Parallel algorithms for sparse-dense matrix multiplication.
result Asymptotic reduction in communication compared to previous methods.
A new method reduces memory requirements for Graph Transformers by sparsely training a network.
problem Quadratic memory complexity in Graph Transformers limits their scalability to large graphs.
method Spexphormer: trains a narrow network on augmented graph, then uses only active connections in a wider network.
result Spexphormer achieves good performance with drastically reduced memory requirements.
Proposes a graph neural network for efficient multi-agent routing.
problem Routing multiple agents in complex, sparsely connected graphs with dynamic traffic.
method Value Iteration Network based on graph neural networks for online coordination.
result Significantly outperforms traditional methods in terms of cost and runtime.
Model financial default cascades on sparse graphs via hitting times.
problem Capturing systemic risk in large, sparsely-connected financial networks.
method Dynamic particle systems with hitting times and convergence theory.
result Characterization of default time distribution in tree-like networks.
Finding "densely connected clusters" in a graph is in general an important and well studied problem in the literature \cite{Schaeffer}. It has various applications in pattern recognition, social networking and data mining \cite{Duda,Mishra}. Recently, Ames and Vavasis have suggested a novel method for finding cliques i…
Analyzes geodesic lengths in sparse networks, deriving a distribution.
problem Understanding connectivity and robustness in networked systems.
method Analytic derivation of geodesic length distribution in sparse networks.
result Simple closed-form expression for geodesic length distribution.
Subspace clustering is the problem of clustering data points into a union of low-dimensional linear/affine subspaces. It is the mathematical abstraction of many important problems in computer vision, image processing and machine learning. A line of recent work (4, 19, 24, 20) provided strong theoretical guarantee for s…
Many computer vision tasks involve processing large amounts of data contaminated by outliers, which need to be detected and rejected. While outlier detection methods based on robust statistics have existed for decades, only recently have methods based on sparse and low-rank representation been developed along with guar…
Paper connects probability density cuts to graph theory eigenfunctions.
problem Developing sparse cuts for probability densities.
method Defines sparse cuts and principal eigenfunctions for probability densities, proving Cheeger and Buser inequalities.
result No such inequalities hold for prior definitions, proving new inequalities for probability densities.
Graph energy helps detect communities in networks better than traditional methods.
problem Detecting communities in sparse networks where traditional methods fail.
method Using graph energy based on the full spectrum of adjacency matrices.
result The difference in graph energy between a planted partition model and an Erdős--Rényi network has a distinct transition at the detectability threshold.
Graphical model for factorization and completion of relatively high rank tensors by sparse samplingstat.ML
Sparse sampling method for tensor factorization and completion of high rank tensors.
problem Completion of high rank tensors with missing data in recommendation systems.
method Sparse measurements and message-passing algorithms in a high-dimensional limit.
result Theoretical insights and performance analysis of tensor factorization in dense limit.
Research shows finiteness in triangulations with girth constraints.
problem Finiteness of cellular partial triangulations with girth constraints.
method Characterization of sparse graphs and contraction-minimal graphs.
result There are finitely many (3,6)-tight and (3,3)-tight graphs.
In practical machine learning systems, graph based data representation has been widely used in various learning paradigms, ranging from unsupervised clustering to supervised classification. Besides those applications with natural graph or network structure data, such as social network analysis and relational learning, …
We present an algorithm to identify sparse dependence structure in continuous and non-Gaussian probability distributions, given a corresponding set of data. The conditional independence structure of an arbitrary distribution can be represented as an undirected graph (or Markov random field), but most algorithms for lea…
Study spectral properties of sparse random graphs to recover latent vectors.
problem Recovering latent vectors in sparse random geometric graphs.
method Analyzes spectral concentration and uses orthogonal polynomial expansions, decoupling, and matrix concentration.
result Sharpens spectral norm bounds and proves exact recovery for Gaussian mixture models.
Unified spectral clustering for sparse networks with heterogeneous degrees.
problem Efficiently detecting communities in sparse networks with varying degrees.
method Developed a parametrized regularized Laplacian matrix for spectral clustering.
result Improved parametrization accounts for network heterogeneity and community hardness.
Optimal graph classification uses message-passing neural networks.
problem Node classification on sparse graphs with fixed feature dimensions.
method Asymptotic local Bayes optimality, message-passing graph neural networks.
result Optimal message-passing architecture interpolates between MLP and convolution.
We consider the problem of detecting a tight community in a sparse random network. This is formalized as testing for the existence of a dense random subgraph in a random graph. Under the null hypothesis, the graph is a realization of an Erdös-Rényi graph on vertices and with connection probability ; under the …
Many transformations in deep learning architectures are sparsely connected. When such transformations cannot be designed by hand, they can be learned, even through plain backpropagation, for instance in attention mechanisms. However, during learning, such sparse structures are often represented in a dense form, as we d…
There has been a recent interest in understanding the power of local algorithms for optimization and inference problems on sparse graphs. Gamarnik and Sudan (2014) showed that local algorithms are weaker than global algorithms for finding large independent sets in sparse random regular graphs. Montanari (2015) showed t…
Graphons of Line Graphsstat.ML
The paper explores graphons of line graphs from sparse finite graphs.
problem Estimating graph limits from sparse finite graphs.
method Mapping finite graphs to their line graphs and analyzing graphs with the square-degree property.
result Graphons of line graphs can distinguish between sparse graphs like star graphs and superlinear preferential attachment graphs.
Financial transactions can be considered edges in a heterogeneous graph between entities sending money and entities receiving money. For financial institutions, such a graph is likely large (with millions or billions of edges) while also sparsely connected. It becomes challenging to apply machine learning to such large…
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…
We consider the sparse inverse covariance regularization problem or graphical lasso with regularization parameter . Suppose the co- variance graph formed by thresholding the entries of the sample covariance matrix at is decomposed into connected components. We show that the vertex-partition induced by the thresh…
The goal in network state prediction (NSP) is to classify the global state (label) associated with features embedded in a graph. This graph structure encoding feature relationships is the key distinctive aspect of NSP compared to classical supervised learning. NSP arises in various applications: gene expression samples…
The -norm fails to produce sparse solutions in Laplacian constrained graphical models, leading to a complete graph.
problem Learning a sparse graph under Laplacian constrained Gaussian graphical models.
method Introduced a nonconvex sparsity penalty and proposed a new estimator using a sequence of weighted -norm penalized sub-problems. Developed a projected gradient descent algorithm with linear convergence rate.
result The proposed estimator can recover the edges correctly with high probability and is effective on both synthetic and real-world data sets.
A new model for sparse networks improves consistency of score estimators.
problem Statistical inference in large sparse networks.
method General pairwise comparison model with flexible parametrization.
result Maximum likelihood estimator is uniformly consistent under sparse conditions.
This paper uses the relationship between graph conductance and spectral clustering to study (i) the failures of spectral clustering and (ii) the benefits of regularization. The explanation is simple. Sparse and stochastic graphs create a lot of small trees that are connected to the core of the graph by only one edge. G…
Regularized spectral methods improve clustering in signed graphs, especially for sparse data.
problem Clustering signed graphs with positive and negative edges.
method Developed regularized versions of SPONGE and Signed Laplacian methods for clustering signed graphs, especially for sparse data.
result Theoretical guarantees and empirical performance improvements for clustering signed graphs, especially in sparse regimes.
We consider supervised learning problems where the features are embedded in a graph, such as gene expressions in a gene network. In this context, it is of much interest to automatically select a subgraph with few connected components; by exploiting prior knowledge, one can indeed improve the prediction performance or o…
Graphon Mixturesstat.ML
Generative model captures hubs and dense communities in social networks.
problem Capturing both hubs and dense communities in social networks.
method Graphon mixture model with a new condition on sparse graphs.
result Estimation of hub normalized degree and graphon for sparse components.
New algorithm tackles multi-agent bandits with heavy-tailed data.
problem Maximizing system performance in multi-agent settings with heavy-tailed data.
method Algorithm exploits hub-like structures and synchronization among clients.
result Regret bound of for homogeneous settings, for heterogeneous.
Sparse Inverse Covariance Estimation (SICE) is useful in many practical data analyses. Recovering the connectivity, non-connectivity graph of covariates is classified amongst the most important data mining and learning problems. In this paper, we introduce a novel SICE approach using adaptive thresholding. Our method i…
Learning the effect of latent variables in Gaussian Graphical models with unobserved variablesstat.ML
The edge structure of the graph defining an undirected graphical model describes precisely the structure of dependence between the variables in the graph. In many applications, the dependence structure is unknown and it is desirable to learn it from data, often because it is a preliminary step to be able to ascertain c…
Graph neural networks have become increasingly popular in recent years due to their ability to naturally encode relational input data and their ability to scale to large graphs by operating on a sparse representation of graph adjacency matrices. As we look to scale up these models using custom hardware, a natural assum…
This paper refines understanding of decentralized learning by considering graph topology.
problem Current theory fails to predict performance in decentralized learning settings.
method Quantifies how graph topology influences convergence in decentralized learning.
result Graph topology significantly impacts convergence in decentralized learning, contrary to spectral gap theory.
New method for disentangling latent factors with sparse dependencies.
problem Disentangling latent factors from observed variables and past factors.
method Mechanism sparsity regularization and sparse causal graphical model.
result Identifiability of latent factors up to a sparse causal graph.
Graph-Dictionary model for sparse multivariate signal representation.
problem Capturing complex relational information in multivariate signals.
method Graph dictionaries and bilinear primal-dual splitting algorithm.
result Graph-dictionary model outperforms baselines in signal reconstruction and classification.
Paper introduces a new method to identify brain hubs using both structural and functional connectivity.
problem Hub node identification in brain networks using only functional connectivity.
method Graph signal processing framework that models functional activity as graph signals on structural connectivity.
result The proposed GraFHub framework identifies hub nodes more accurately than conventional methods.
Study on signal recovery from low-rank matrix with sparse noise.
problem Inference of a rank-one signal in the presence of sparse noise.
method Replica method from statistical physics, recursive distributional equations, population dynamics algorithm.
result Critical signal strength for recovery via top eigenvector identified.