Many graph clustering quality functions suffer from a resolution limit, the inability to find small clusters in large graphs. So called resolution-limit-free quality functions do not have this limit. This property was previously introduced for hard clustering, that is, graph partitioning. We investigate the resolution-…
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,657 papers · 148 categories
Trend · papers per month
48 results for “Local Graph Limits”
Uncertainty principles such as Heisenberg's provide limits on the time-frequency concentration of a signal, and constitute an important theoretical tool for designing and evaluating linear signal transforms. Generalizations of such principles to the graph setting can inform dictionary design for graph signals, lead to …
The study proves sampling-based GNNs can approximate training on full graphs with small subgraphs.
problem Training Graph Neural Networks (GNNs) on large graphs is computationally expensive.
method Theoretical framework using graph local limits to prove approximation of GNN training on small samples.
result Parameters learned from sampling-based GNNs on small subgraphs are close to those on full graphs.
GNNs may be limited by graph topology, affecting their learning outcomes.
problem Understanding how graph topology influences GNN behavior and performance.
method Investigating the interaction between local topological features and GNN message-passing schemes.
result Locally similar neighborhoods can lead to consistent node representations, affecting GNN performance.
Graph-based weather prediction adapted for local models.
problem Applying neural weather prediction to limited area modeling.
method Adapting graph-based Neural Weather Prediction approach to local models.
result Validation of multi-scale hierarchical model extension for Nordic region.
Study reveals limits of detecting local geometry in random graphs.
problem Detecting local geometry in random graphs with hidden communities.
method Introduced model and used information-theoretic and computational limits to investigate detection.
result Detection threshold determined at for fixed .
We address two fundamental questions about graph neural networks (GNNs). First, we prove that several important graph properties cannot be computed by GNNs that rely entirely on local information. Such GNNs include the standard message passing models, and more powerful spatial variants that exploit local graph structur…
Graph neural networks can be adapted to new graphs with a limit object called graphon NNs.
problem Transferability of graph neural networks across different graphs.
method Introduced graphon NNs as limit objects of GNNs and proved a bound on the difference between GNN and graphon-NN outputs.
result The bound on the difference between GNN and graphon-NN outputs vanishes with growing number of nodes if the graph convolutional filters are bandlimited.
The end compactification |Γ| of the locally finite graph Γis the union of the graph and its ends, endowed with a suitable topology. We show that π_1(|Γ|) embeds into a nonstandard free group with hyperfinitely many generators, i.e. an ultraproduct of finitely generated free groups, and that the embedding we construct f…
We review recent probabilistic results on covariant Schrödinger operators on vector bundles over (possibly locally infinite) weighted graphs, and explain applications like semiclassical limits. We also clarify the relationship between these results and their formal analogues on smooth (possibly noncompact) Riemannian m…
Existing approaches to analyzing the asymptotics of graph Laplacians typically assume a well-behaved kernel function with smoothness assumptions. We remove the smoothness assumption and generalize the analysis of graph Laplacians to include previously unstudied graphs including kNN graphs. We also introduce a kernel-fr…
Proves continuum limits of Lipschitz learning using Γ-convergence.
problem Semi-supervised learning with graph-based methods and continuum limits of -Laplacian learning.
method Proves continuum limits of Lipschitz learning using Γ-convergence.
result Proves -convergence in the -topology to the supremum norm of the gradient.
Graphs can be smoothed or squashed too, study finds.
problem Graph Neural Networks struggle with over-smoothing and over-squashing issues.
method Unified framework using Ollivier-Ricci curvature to address both issues.
result Over-smoothing and over-squashing linked to positive and negative graph curvature respectively.
Large data limit of the MBO scheme for data clustering: -convergence of the thresholding energiesmath.AP
The MBO scheme for data clustering is analyzed in the large data limit, proving convergence to optimal partition problems.
problem Analyzing the MBO scheme for data clustering in the large data limit.
method Implicit gradient descent on the thresholding energy of a similarity graph.
result The MBO scheme outcomes converge to minimizers of a weighted optimal partition problem.
Although many successful ensemble clustering approaches have been developed in recent years, there are still two limitations to most of the existing approaches. First, they mostly overlook the issue of uncertain links, which may mislead the overall consensus process. Second, they generally lack the ability to incorpora…
Tests if vertices in graphs have the same latent positions.
problem Testing equality of latent positions in random graphs.
method Empirical Mahalanobis distances from spectral embeddings.
result Test statistics follow chi-square distributions under null and local alternatives.
Short text classi cation is a method for classifying short sentence with prede ned labels. However, short text is limited in shortness in text length that leads to a challenging problem of sparse features. Most of existing methods treat each short sentences as independently and identically distributed (IID), local cont…
Belief propagation (BP) can do exact inference in loop-free graphs, but its performance could be poor in graphs with loops, and the understanding of its solution is limited. This work gives an interpretable belief propagation rule that is actually minimization of a localized -divergence. We term this algorithm as $α…
We present our ongoing work on understanding the limitations of graph convolutional networks (GCNs) as well as our work on generalizations of graph convolutions for representing more complex node attribute dependencies. Based on an analysis of GCNs with the help of the corresponding computation graphs, we propose a gen…
MaGNet integrates local and global graph information for interpretable results.
problem Lack of interpretability and inability to learn varying-order representations in GNNs.
method Model-agnostic Graph Neural Network (MaGNet) framework integrating estimation and interpretation models.
result MaGNet effectively integrates information of various orders and provides meaningful, interpretable results.
Enhances graph neural networks with structural message-passing for better generalization.
problem Limited representation power and inability to learn basic graph topological properties.
method Proposes a framework that includes a one-hot encoding of nodes and parametrized message and update functions ensuring permutation equivariance.
result Achieves state-of-the-art results on molecular graph regression on the ZINC dataset.
Let be a complete Riemannian manifold which either is compact or has a pole, and let be a positive smooth function on . In the warped product , we study the flow by the mean curvature of a locally Lipschitz continuous graph on and prove that the flow exists for all time an…
Paper proposes a new method for joint feature selection and graph learning.
problem Previous methods suffer from neglecting joint formulation and lack of graph learning.
method Formulates multi-view feature selection with orthogonal decomposition, incorporates cross-space locality preservation, and uses a unified objective function for simultaneous learning.
result Demonstrates superior performance in multi-view feature selection and graph learning tasks.
Graph convolutional kernel networks generalize CNNs to graph data.
problem Representing graph-structured data for machine learning.
method Convolutional kernel networks applied to graph data.
result Competitive performance on graph classification benchmarks.
Driven by the outstanding performance of neural networks in the structured Euclidean domain, recent years have seen a surge of interest in developing neural networks for graphs and data supported on graphs. The graph is leveraged at each layer of the neural network as a parameterization to capture detail at the node le…
We focus our attention on the link prediction problem for knowledge graphs, which is treated herein as a binary classification task on neural embeddings of the entities. By comparing, combining and extending different methodologies for link prediction on graph-based data coming from different domains, we formalize a un…
This thesis explores GNNs, categorizing them into local and global approaches.
problem Understanding the convergence of global GNNs and connecting local and global approaches.
method Categorization of GNNs into local and global, study of Invariant Graph Networks, connecting local and global approaches, and using local MPNN for graph coarsening.
result Established a connection between local and global GNN approaches.
We consider learning on graphs, guided by kernels that encode similarity between vertices. Our focus is on random walk kernels, the analogues of squared exponential kernels in Euclidean spaces. We show that on large, locally treelike, graphs these have some counter-intuitive properties, specifically in the limit of lar…
Non-local GNNs improve performance on disassortative graphs.
problem Efficiency and performance issues in local aggregation for disassortative graphs.
method Proposes a non-local aggregation framework with attention-guided sorting.
result Significantly outperforms previous methods on disassortative graphs.
Several probabilistic models from high-dimensional statistics and machine learning reveal an intriguing --and yet poorly understood-- dichotomy. Either simple local algorithms succeed in estimating the object of interest, or even sophisticated semi-definite programming (SDP) relaxations fail. In order to explore this p…
Federated learning on graphs tackles heterogeneity with efficient parameter estimation.
problem Parameter estimation in federated learning with data distribution and communication heterogeneity.
method Joint estimation of parameters using -estimation framework with fused Lasso regularization, considering graph structure.
result Our estimator achieves optimal rate under certain graph fidelity conditions, similar to centralized aggregation.
A new hybrid GNN framework tackles oversmoothing in graph data.
problem Oversmoothing in graph convolutional networks limits their expressive power and generalization.
method Combines traditional GCN filters with band-pass filters defined via geometric scattering and introduces an attention framework.
result Improves expressive power and generalization of graph convolutional networks.
New method calculates Ricci curvature from distances between weighted volumes.
problem Calculating Ricci curvature for weighted Riemannian manifolds.
method Asymptotic retrieval of generalized Ricci tensor from scaled metric derivatives of Wasserstein 1-distances.
result Limiting coarse curvature of random graphs converges to generalized Ricci tensor.
A new method detects financial fraud using graph transformers.
problem Detecting fraudulent transactions in financial data.
method Spatial-Temporal-Aware Graph Transformer (STA-GT) integrating GNNs and transformers.
result STA-GT outperforms general GNN models on financial fraud detection.
Graph neural networks (GNNs) are a powerful tool to learn representations on graphs by iteratively aggregating features from node neighbourhoods. Many variant models have been proposed, but there is limited understanding on both how to compare different architectures and how to construct GNNs systematically. Here, we p…
Many interesting problems in machine learning are being revisited with new deep learning tools. For graph-based semisupervised learning, a recent important development is graph convolutional networks (GCNs), which nicely integrate local vertex features and graph topology in the convolutional layers. Although the GCN mo…
SPECTRE uses spectral conditioning to generate larger graphs without mode collapse.
problem Overcoming expressivity and mode collapse in one-shot graph generators.
method SPECTRE generates graph Laplacian spectrum and eigenvectors to model graph structure.
result SPECTRE outperforms state-of-the-art deep autoregressive generators in fidelity and speed.
The paper classifies dense conjugacy classes in mapping class groups of locally finite graphs.
problem Identifying which mapping class groups have dense conjugacy classes.
method Developed flux homomorphisms and combinatorial criteria for stability.
result A complete classification for self-similar locally finite graphs and a criterion for stability.
New -BP algorithm improves belief propagation for graphs with loops.
problem Uncertainty in belief propagation for graphs with loops.
method Derive -BP algorithm motivated by minimizing -divergence.
result Proves convergence conditions for -BP.
Graph convolution is the core of most Graph Neural Networks (GNNs) and usually approximated by message passing between direct (one-hop) neighbors. In this work, we remove the restriction of using only the direct neighbors by introducing a powerful, yet spatially localized graph convolution: Graph diffusion convolution …
Matrix completion models are among the most common formulations of recommender systems. Recent works have showed a boost of performance of these techniques when introducing the pairwise relationships between users/items in the form of graphs, and imposing smoothness priors on these graphs. However, such techniques do n…
node2coords learns interpretable graph node representations robust to graph perturbations.
problem Need representations that capture graph structure and are robust to perturbations.
method Proposes a graph representation learning algorithm using Wasserstein barycenters.
result Learned representations are interpretable and stable to graph perturbations.
Proposes LSGP for better graph signal representation.
problem Local variations in graph process characteristics.
method Locally stationary graph process (LSGP) model.
result LSGP provides accurate signal representations.
New algorithm improves graph-based active learning by identifying unexplored regions.
problem Improving graph-based active learning by identifying unexplored regions.
method Poisson Reweighted Laplacian Uncertainty Sampling (PWLL) with a diagonal perturbation.
result PWLL effectively identifies unexplored regions in graph-based data.
New graph convolution captures local features on non-Euclidean grids.
problem Capturing local features on irregular, coarse non-Euclidean grids.
method Low-rank learnable local filters in graph convolutions.
result Proves more expressive than previous spectral graph convolution methods.
Proposes methods for local clustering in attributed graphs.
problem Finding a single cluster concentrated on a specific region in a graph.
method Introduces Graph Unimodality (GU) and Attribute Unimodality (AU) measures, and LOCLU algorithm to optimize Compactness score.
result Local cluster detected by LOCLU concentrates on the region of interest and exhibits unimodal data distribution.
Graphs and local systems count multiwebs.
problem Counting multiwebs in graphs with local systems.
method Using Kasteleyn matrices and web-traces.
result Determinant of Kasteleyn matrix counts multiwebs.
An efficient search-and-score algorithm for ancestral graphs using multivariate information scorescs.LG
Efficiently searches ancestral graphs using multivariate information.
problem Discovering causal relationships in graphs with latent variables.
method Greedy search-and-score algorithm with two-step approach.
result Outperforms existing methods on benchmark datasets.