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…
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “Graph Spectral Regularization”
Regularization improves spectral embedding by focusing on the largest blocks.
problem Improving the quality of spectral embedding for graph data.
method Explained the impact of complete graph regularization on spectral embedding of a block model.
result Regularization forces spectral embedding to focus on the largest blocks, making it less sensitive to noise or outliers.
Developed a framework for designing filters in spectral GCNNs with improved performance.
problem Designing effective filters for spectral GCNNs with regularization properties.
method Exploring regularization properties of graph Laplacian and proposing a generalized framework for filter design.
result New filters derived from the framework outperform state-of-the-art techniques in semi-supervised node classification.
Dual regularized graph Laplacian improves spectral clustering for community detection.
problem Detecting clusters in networks with improved spectral clustering methods.
method Proposes dual regularized graph Laplacian for three spectral clustering approaches.
result Theoretical analysis shows DRSC and DRSLIM yield stable consistent community detection.
Graph Spectral Regularization makes neural network layers more interpretable.
problem Making neural network layers more interpretable without sacrificing performance.
method Using a graph Laplacian penalty to structure hidden layer activations.
result Encourages smooth activations within hidden layers, leading to better interpretability.
Fiedler regularization uses spectral graph theory to improve neural network performance.
problem Improving neural network performance by penalizing weights based on connectivity.
method Uses the Fiedler value of the neural network's graph as a regularization tool, providing theoretical and computational methods.
result Demonstrates Fiedler regularization's effectiveness in improving neural network performance.
Graph convolutional networks fail to use eigenvectors beyond the first, unlike spectral embedding.
problem Understanding when graph convolutional networks fail compared to spectral embedding.
method Presented a simple generative model to illustrate failure.
result Graph convolutional networks fail to use eigenvectors beyond the first in certain graphs.
New spectral clustering method using LASSO regularization for robust graph partitioning.
problem Lack of theoretical guarantees for spectral clustering on general graph models.
method 1-spectral clustering on a new random model with LASSO regularization.
result Effective and robust to small noise perturbations, validated by simulations and real data.
Paper optimizes Laplacian regularization for sparse network clustering.
problem Improving spectral clustering in sparse networks.
method Formally determines optimal Laplacian regularization.
result Proper regularization is closely tied to state-of-the-art techniques.
A new method improves graph-based learning for high-dimensional data.
problem Inconsistent high-dimensional learning efficiency of semi-supervised graph regularization.
method Introducing a novel regularization approach involving centering operation.
result Empirical results show improved performance over spectral clustering.
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.
GRAMPA spectral method solves graph matching problem with high probability.
problem Finding vertex correspondence between unlabeled graphs.
method GRAMPA constructs a similarity matrix from weighted eigenvector comparisons, rounding to produce a matching.
result GRAMPA exactly recovers correct vertex correspondence with high probability for Gaussian models.
Fiedler regularization uses graph sparsity to improve neural network training.
problem Improving neural network training by respecting graph structure.
method Using the Fiedler value of the neural network's graph as a regularization tool.
result Fiedler regularization outperforms traditional methods like dropout and weight decay.
The paper improves spectral convergence rates for graph Laplacians.
problem Improving spectral convergence rates for graph Laplacians.
method Utilizing regularity of continuum eigenfunctions and strong pointwise consistency results.
result Eigenvalues and eigenvectors of graph Laplacian converge to continuum at rate .
Unified framework for analyzing graph neural operators converging to graph limits.
problem Analyzing convergence of graph neural operators to graph limits.
method Develops a unified spectral framework for graph neural operators under various graphon assumptions.
result Unified framework enables direct comparison of convergence rates and tradeoffs.
Detects graph topology changes from noisy signals using prior spectral information.
problem Detecting changes in graph topology from graph signals.
method Leverages graph filtering and subspace detection to distill problem into a CUSUM-based algorithm.
result Demonstrates the effectiveness of incorporating prior spectral signatures for change-point detection.
This paper presents a bias-variance tradeoff of graph Laplacian regularizer, which is widely used in graph signal processing and semi-supervised learning tasks. The scaling law of the optimal regularization parameter is specified in terms of the spectral graph properties and a novel signal-to-noise ratio parameter, whi…
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.
Study shows consistency of shallow GCNNs on sampled point clouds under manifold assumption.
problem Consistency of shallow GCNNs on sampled point clouds under manifold assumption.
method Functional analysis perspective, weakly compact product of unit balls, Sobolev regularity, frequency cutoff.
result Proves -convergence of regularized empirical risk minimization functionals and convergence of their global minimizers.
Proposes a DR method for HSI classification with limited labeled data.
problem High dimensionality, singularity, limited training samples, lack of labeled data, heteroscedasticity, nonlinearity.
method Semi-supervised graph-based, HGF for smoothing, MLP for linear patches, RMLSC and NPMLSC for dissimilarity matrices, optimization for projection matrix.
result Improves HSI classification with limited labeled data.
Biological and social systems consist of myriad interacting units. The interactions can be represented in the form of a graph or network. Measurements of these graphs can reveal the underlying structure of these interactions, which provides insight into the systems that generated the graphs. Moreover, in applications s…
In this article, we study spectral methods for community detection based on -parametrized normalized modularity matrix hereafter called in heterogeneous graph models. We show, in a regime where community detection is not asymptotically trivial, that can be well approximated by a more tract…
A new DR method for HSI classification improves accuracy with limited samples.
problem Challenges in DR for HSI classification with limited training samples.
method Graph-based spatial and spectral regularized local scaling cut (SSRLSC).
result Improved classification accuracy compared to spectral-only methods.
Unified framework for structured graph learning from data.
problem Lack of structural knowledge incorporation in graph learning.
method Combining Gaussian graphical models and spectral graph theory, imposing constraints via optimization.
result Provable convergence, computational efficiency, and practical applicability for various graph tasks.
GRAMPA algorithm recovers latent vertex correspondence in correlated graphs with high probability.
problem Recovering latent vertex correspondence between unlabeled, edge-correlated weighted graphs.
method Spectral graph matching algorithm, GRAMPA, with exact recovery guarantees for Erdős-Rényi graphs.
result GRAMPA exactly recovers latent vertex correspondence with high probability for Erdős-Rényi graphs with edge correlation coefficient and average degree at least when .
In this work, we are interested in generalizing convolutional neural networks (CNNs) from low-dimensional regular grids, where image, video and speech are represented, to high-dimensional irregular domains, such as social networks, brain connectomes or words' embedding, represented by graphs. We present a formulation o…
This paper characterizes and explains the disagreement between two graph embedding methods.
problem Understanding why two popular graph embedding methods produce different results.
method End-to-end analysis of ASE-LSE latent subspaces, proving conditions for agreement and disagreement.
result No maximal-disagreement graph exists; disagreement is strictly below its theoretical ceiling.
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.
GCN and GPCA are mathematically connected, leading to improved node classification performance.
problem Improving node classification performance in semi-supervised settings.
method Established a mathematical connection between GCN and GPCA, demonstrating their equivalence and using this to design an effective initialization strategy.
result GPCA paired with a simple MLP achieves similar or better performance than GCN on semi-supervised node classification tasks.
New graph embedding method improves link prediction and node classification.
problem Improving graph embedding methods for better node representation.
method Spectral-biased random walks with neighborhood similarity bias.
result Significantly improves link prediction and node classification.
Due to the growing ubiquity of unlabeled data, learning with unlabeled data is attracting increasing attention in machine learning. In this paper, we propose a novel semi-supervised kernel learning method which can seamlessly combine manifold structure of unlabeled data and Regularized Least-Squares (RLS) to learn a ne…
New method computes dense partial correlations with applications in graph theory and uncertainty quantification.
problem Sparse inverse covariance matrices are popular but dense solutions are overlooked.
method Derives approach based on inverse problem theory.
result New insights and approaches for model selection and data preprocessing.
We study the Bakry-Émery curvature function of a vertex in a locally finite graph systematically. Here is defined as the optimal curvature lower bound in the Bakry-Émery curvature-dimension inequality $CD(\mathcal{K},\ma…
Analysis of spectral clustering algorithms for community detection: the general bipartite settingmath.ST
We consider spectral clustering algorithms for community detection under a general bipartite stochastic block model (SBM). A modern spectral clustering algorithm consists of three steps: (1) regularization of an appropriate adjacency or Laplacian matrix (2) a form of spectral truncation and (3) a k-means type algorithm…
Proposes GLNNs for robust semi-supervised classification using adaptive graphs.
problem Adaptive graph learning for robust semi-supervised classification.
method Optimizes graph structure from data and tasks using spectral graph theory and maximum a posteriori estimation.
result GLNNs outperform state-of-the-art approaches in semi-supervised classification.
Spectral Sectionsmath.SP
The paper generalizes spectral section concepts to non-compact spaces.
problem Generalizing spectral sections to non-compact base spaces.
method Generalization to arbitrary base spaces, applications to cobordism theorems, investigation of Riesz continuity.
result If a family of operators has a spectral section, it is Riesz continuous.
Consider a network of agents connected by communication links, where each agent holds a real value. The gossip problem consists in estimating the average of the values diffused in the network in a distributed manner. We develop a method solving the gossip problem that depends only on the spectral dimension of the netwo…
New spectral conditions ensure graph rigidity and global rigidity in the Euclidean plane.
problem Ensuring graph rigidity and global rigidity in the Euclidean plane.
method Improving algebraic connectivity bounds for graph rigidity and global rigidity.
result Every 6-connected graph is rigid and globally rigid if its algebraic connectivity exceeds specific thresholds.
New -Laplacian GNN model tackles heterophilic graphs by improving node classification.
problem Heterophilic graphs where node labels differ, leading to poor GNN performance.
method Proposes -Laplacian GNN model with a new message passing mechanism derived from discrete regularization.
result Significantly outperforms state-of-the-art GNNs on heterophilic benchmarks.
The performance of spectral clustering can be considerably improved via regularization, as demonstrated empirically in Amini et. al (2012). Here, we provide an attempt at quantifying this improvement through theoretical analysis. Under the stochastic block model (SBM), and its extensions, previous results on spectral c…
Autoencoding Random Forestsstat.ML
Proposes autoencoding with random forests using spectral graph theory.
problem Learning low-dimensional embeddings of random forest models.
method Combines nonparametric statistics and spectral graph theory for optimization.
result Establishes a universal consistent decoder for random forest models.
Improved spectral-based GCN for directed graphs.
problem Cannot directly work on directed graphs.
method Redefined Laplacians to improve propagation model.
result Outperforms state-of-the-art methods on directed graph datasets.
Graph reduction preserves spectral and cut properties without significant loss.
problem Can graphs be reduced in size without altering their fundamental properties?
method Restricted spectral approximation, focusing on coarsening.
result Improved quality coarse graphs found without sacrificing speed.
Observational data usually comes with a multimodal nature, which means that it can be naturally represented by a multi-layer graph whose layers share the same set of vertices (users) with different edges (pairwise relationships). In this paper, we address the problem of combining different layers of the multi-layer gra…
This paper tackles graph translation challenges by predicting both node and edge attributes simultaneously.
problem Challenges in predicting both node and edge attributes in graph translation, especially in interactive, iterative, and asynchronous processes.
method Developed a novel framework integrating both node and edge translations seamlessly, using spectral graph regularization to maintain consistency.
result Demonstrated the effectiveness of the proposed method on both synthetic and real-world application data.
Improved spectral clustering algorithm for better performance.
problem Improving the performance of spectral clustering algorithms.
method Developed a new performance guarantee under a weaker assumption and evaluated using a different spectral embedding map.
result Better performance guarantee under a weaker assumption and evaluation of a new spectral embedding map.
New wavelet frames constructed from reproducing kernels for continuous and discrete domains.
problem Generating wavelet frames on non-Euclidean structures.
method Spectral filtering of integral operators associated with reproducing kernels.
result Discrete frames as Monte Carlo estimates of continuous frames, with finite-sample rates derived.
Adversarial contamination of networks in the setting of vertex nomination: a new trimming methodstat.ML
New method trims network data to resist adversarial contamination.
problem Adversarial contamination in network data affects statistical and algorithmic performance.
method Proposes a new trimming method operating in model space to address both block and white noise contamination.
result Demonstrates superior performance in simulations compared to direct trimming.