Source-linked AI summary
How to learn a graph from smooth signals
Vassilis Kalofolias
TL;DR
The paper addresses learning an unknown graph underlying signals that are smooth across connected nodes. It recasts the smoothness objective as weighted sparsity, proposes a graph-learning model, and supplies scalable primal-dual algorithms. Experiments suggest the new model outperforms the state of the art when sparse graphs and connectivity are important.
Problem
The paper studies how to learn graph structure from signals when the underlying graph is unknown or noisy.
Method
The framework learns nonnegative edge weights by minimizing a smoothness term expressed as weighted ℓ-1 sparsity, with a new model and primal-dual algorithms.
Results
Experiments on artificial and real data suggest the new model is superior in many cases and achieves better connectivity when sparse graphs are sought.
Takeaways & Limitations
The framework unifies standard Gaussian weight construction and Dong et al.'s model while providing scalable solutions for both.
Takeaways & Limitations
The probabilistic generative model does not cover cases where the initial signal x0 is not white Gaussian.
Abstract
from arXiv · showhide
We propose a framework that learns the graph structure underlying a set of smooth signals. Given $X\in\mathbb{R}^{m\times n}$ whose rows reside on the vertices of an unknown graph, we learn the edge weights $w\in\mathbb{R}_+^{m(m-1)/2}$ under the smoothness assumption that $\text{tr}{X^\top LX}$ is small. We show that the problem is a weighted $\ell$-1 minimization that leads to naturally sparse solutions. We point out how known graph learning or construction techniques fall within our framework and propose a new model that performs better than the state of the art in many settings. We present efficient, scalable primal-dual based algorithms for both our model and the previous state of the art, and evaluate their performance on artificial and real data.
1 INTRODUCTION
The paper learns unknown graph structure from signals assumed to vary smoothly across connected nodes. It links smoothness to sparsity, proposes a graph-learning model, and develops scalable algorithms evaluated on artificial and real data.
- Problem: Each column of X is a graph signal, with rows assigned to the unknown graph's nodes.Smoothness means signals change gradually between connected nodes.
- Problem: The paper formulates graph learning through a smoothness objective over valid graph Laplacians.The goal is to learn a good graph when the graph is noisy or unavailable.
- Contributions: The smoothness term is equivalent to a weighted ℓ-1 objective, producing naturally sparse graphs.The weighting penalizes edges between distant rows of X.
- Contributions: The framework contains Gaussian kernel construction and the model of Dong et al. as special cases, while introducing a new graph-learning model.The new model has effectively one parameter controlling learned-graph sparsity.
- Algorithms: Fast, scalable, convergent primal-dual algorithms are provided for the proposed model and Dong et al.'s model.The paper presents these as scalable solutions for graph learning under the smoothness assumption.
- Evaluation: Experiments on artificial and real data report that the new model is superior in many cases and improves connectivity when sparse graphs are sought.The comparison includes the state-of-the-art model by Dong et al.
2 PROPERTIES OF THE LAPLACIAN
The paper represents valid Laplacians through weighted adjacency matrices and edge-weight vectors, simplifying graph-learning optimization. Rewriting the trace term reveals weighted sparsity based on pairwise signal distances.
- Representations: Valid Laplacians are represented equivalently through Laplacian matrices, adjacency matrices, and edge-weight vectors.The vector representation avoids imposing adjacency-matrix symmetry explicitly.
- Smoothness and sparsity: Rewriting the trace term shows that smoothness is a weighted ℓ-1 norm of the adjacency matrix.The weights are determined by pairwise distances between rows of X.
- Representations: Table 1 summarizes equivalent terms across the spaces L, Wm, and Wv, using vectorized distances and the summation operator S.The paper analyzes the matrix representation and solves the optimization in vector form.
- Smoothness and sparsity: The weighted sparsity objective penalizes edges connecting distant rows and favors edges associated with small distances.When distances arise from a smooth manifold, the resulting graph is expected to be sparse.
- Smoothness and sparsity: Adding an explicit ℓ-1 sparsity term is equivalent here to adding a constant to the squared distances.The trace term's information about X is contained in the pairwise distance matrix Z.
- Assumptions: Individual rows of X need not themselves be smooth signals because two nonsmooth signals can still have a small pairwise distance.The relevant smoothness relation is between signal pairs rather than necessarily within each signal.
3 WHAT IS A SMOOTH SIGNAL?
The paper unifies several notions of graph-smooth signals through graph filtering, where low frequencies correspond to smooth components. Tikhonov regularization, probabilistic models, and heat diffusion are represented as filtering operations with different filters.
- Graph filtering: Graph filtering unifies different definitions of smooth signals as transformations of an initial non-smooth signal.The paper uses this framework to compare signal models across contexts.
- Graph filtering: Low graph frequencies correspond to small Laplacian eigenvalues, while smooth filters are decaying functions of frequency.The graph Fourier representation expresses signals in eigenvector-eigenvalue pairs of the Laplacian.
- Tikhonov regularization: Tikhonov regularization produces the graph-smooth signal x = (αL + I)^-1x0, with larger α yielding smoother signals.This is equivalent to filtering x0 with a low-pass filter.
- Probabilistic models: The probabilistic generative model samples smooth signals by filtering white Gaussian noise and adding a mean, but excludes non-white-Gaussian initial signals.The model can use any filter h when x0 follows a white Gaussian distribution.
- Heat diffusion: Heat diffusion generates x = exp(-Lt)x0, and larger diffusion times t produce smoother signals.This formulation is used, for example, in image denoising on a pixel graph.
4 LEARNING A GRAPH FROM SMOOTH SIGNALS
The paper rewrites graph learning in terms of a positive weighted adjacency matrix and pairwise distances, yielding a general weighted sparsity framework. It instantiates this framework with Gaussian weights, a new connectivity-promoting model, and a simplified state-of-the-art model.
- General framework: Graph learning is reformulated using the weighted adjacency matrix W and pairwise distance matrix Z.The regularizer f(W) prevents the trivial W = 0 solution and incorporates prior structure.
- Existing models: The framework contains standard Gaussian weight construction and the state-of-the-art graph learning model as special cases.This establishes the framework's connection to existing graph construction and learning methods.
- Proposed model: The proposed model places a logarithmic barrier on node degrees, forcing positive degrees without preventing individual edges from becoming zero.This improves connectivity while preserving sparsity.
- Proposed model: With β = 0, the proposed model gives the sparsest solution assigning at least one edge to every node, resembling a 1-NN graph for distant nodes.Changing β controls edge density through a Frobenius penalty on edge weights.
- State-of-the-art model: The reformulated state-of-the-art model becomes simpler to optimize and spans edge shapes from a single smallest-distance edge at α = 0 to a dense constant-degree graph as α →∞.Its scale is controlled by s, while α controls density.
5 OPTIMIZATION
The paper develops primal-dual optimization methods for its graph-learning model and the state-of-the-art model. The resulting algorithms are scalable, parallelizable, and convergent under convexity assumptions.
- Primal-dual formulation: Primal-dual techniques are used to solve both the proposed model and the state-of-the-art model within the general framework.The framework also supports efficient solution of other models formed by alternative choices of f(W).
- Primal-dual formulation: The optimization is expressed in vector form as three functions suited to proximal splitting, with a differentiable term having Lipschitz-continuous gradient.The operator K maps edge weights to structural quantities such as node degrees.
- Model-specific operators: For the proposed model, K = S maps edge weights to node degrees, while for model (14), K maps weights to the total weight constrained by s.These choices avoid imposing symmetry as an explicit constraint.
- Algorithm: The proposed primal-dual algorithm updates primal and dual variables iteratively using proximal operations and stopping tolerances.The vectorized implementation uses z as the pairwise-distance vector and γ as the stepsize.
- Complexity and convergence: O(m^2) per iteration, both algorithms can be parallelized and are guaranteed to converge to the minimum.The guarantee follows because both objectives are proper, convex, and lower-semicontinuous.
6 EXPERIMENTS
The experiments compare the proposed model with Dong et al. and graph-construction baselines on artificial and real data. The proposed model generally performs better, especially when sparse graphs and connectivity are important.
- Artificial data: In most graph/signal combinations, the proposed model performs better across the reported metrics.Tikhonov and heat-diffusion signals produced slightly worse results than the generative model in the reported comparison.
- USPS digits: The USPS study learns graphs for 1001 imbalanced digit images and evaluates spectral clustering and label propagation against k-NN graphs.Clustering is repeated 100 times and label propagation uses different 10% labeled subsets.
- USPS digits: On USPS, the best clustering results are nearly identical, at 0.24 for one algorithm and 0.25 for the other, while the proposed model is more robust to graph density.Label propagation shows similar robustness, with better classification quality for the proposed model at sparser densities.
- USPS digits: At six edges per node, Dong et al.'s graph has 35 components, including 22 disconnected nodes.The proposed model has better connectivity at sparse densities, while Dong et al.'s method connects distant nodes only at fairly high density.
- Runtime: The proposed algorithms learn a 10-edge-per-node USPS graph in 5 seconds for Algorithm 1 and 1 minute for Algorithm 2 on a standard PC.The reported runs use 218 and 2043 iterations, respectively, at tolerance ϵ = 1e-4.
7 CONCLUSION
The paper reframes graph learning from smooth signals as weighted sparsity optimization and introduces a model with scalable primal-dual solvers. Experiments suggest advantages over the state of the art when sparse graphs must remain connected.
- Conclusion: Smoothness can be simplified into a weighted sparsity problem, providing a general framework for learning graphs.The framework links the smoothness term to a weighted ℓ-1 norm of the adjacency matrix.
- Conclusion: The proposed model has effectively one parameter controlling the sparsity of the learned graph.
- Conclusion: The framework includes standard Gaussian distance-based graph construction and analyzes Dong et al.'s model within the same formulation.
- Conclusion: Primal-dual algorithms are provided for both the proposed model and Dong et al.'s model, including a scalable algorithm previously missing for the latter.
- Conclusion: The experiments suggest that the proposed model is expected to outperform the state of the art when sparse graphs and connectivity are both important.
A.2 Proof of proposition 2
The proof uses a logarithmic scaling identity and specializes the scaling parameter to obtain a second equality.
- The proof uses log(γ ˜W1) = log(˜W1) + const.(W).
- The additive constant is identified as depending on W.
- The second equality follows from the first when γ = α.
A.3 Proof of proposition 3
The appendix presents the smooth-signal settings and the primal-dual algorithmic ingredients for the proposed and comparison models.
- Smooth signals: Table 3 summarizes the different types of smooth signals used in the paper.
- Algorithms: The appendix introduces the primal-dual algorithm for the proposed model and separately for Dong et al.'s model.
- Dong et al. algorithm: The Dong et al. algorithm uses ζ = 2α(m + 1) as the Lipschitz constant of the gradient of f3.
- Dong et al. algorithm: The listed iterations update primal variables, auxiliary variables, and dual quantities until relative changes satisfy tolerance ϵ.
C.1 Learning the graph of COIL 20 images
The COIL 20 experiments evaluate graph-learning models across graph-density levels using non-uniformly sampled images and compare them with k-NN graphs. Performance is assessed through clustering, label propagation, and graph connectivity, including components that lack labeled nodes.
- C.1 Learning the graph of COIL 20 images: The comparison includes k-NN graphs with different k values and evaluates models at different average numbers of non-zero edges per node.The horizontal axis represents the average number of non-zero edges per node.
- C.1 Learning the graph of COIL 20 images: Components without labeled nodes are separately tracked because their nodes cannot be classified by label propagation.These nodes are represented by dashed lines in the middle plot.
- C.1 Learning the graph of COIL 20 images: Clustering quality, label propagation quality, and connectivity are reported for the learned graphs.Connectivity includes the number of disconnected components and disconnected nodes; the figure notes that the proposed model and k-NN have no disconnected nodes.