PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Framework for Structured Graph Learning via Spectral Constraints

Sandeep Kumar, Jiaxi Ying, José Vinícius de M. Cardoso, Daniel Palomar

arXiv:1904.09792v1stat.MLcs.LGcs.SImath.OC

TL;DR

Structured graph learning is an NP-hard problem, and existing approaches can be limited to particular structures or computationally demanding. The paper formulates graph-structure requirements as spectral constraints and develops algorithms for learning structure and weights together. Its algorithms are reported to converge, and experiments on synthetic and real data demonstrate effectiveness.

  • Problem

    Structured graph learning is NP-hard, while existing methods can be limited to particular structures, require known connectivity, or involve computationally demanding stages.

    Source: §1 · p. 3

  • Method

    The framework converts combinatorial graph constraints into spectral constraints on graph matrices and uses algorithms to learn graph structure and weights simultaneously.

    Source: §1 · p. 3, • Structured graph learning via… · p. 4

  • Results

    SGL has a considerable advantage over the cited competing structured-graph algorithms, while its worst-case complexity O(p^3) matches GLasso; experiments on synthetic and real data demonstrate effectiveness.

    Source: §3.2.4 · p. 18, §7.2 · p. 42

  • Takeaways & Limitations

    The framework applies spectral constraints to learn structured graphs from a large class of graph families while jointly estimating their structure and weights.

    Source: §7.2 · p. 42

    For multi-component graph learning, SGL requires the number of components k as prior information; the paper suggests model-selection methods if k is unavailable.

    Source: §6.3.5 · p. 30

Abstract

from arXiv · show

Graph learning from data represents a canonical problem that has received substantial attention in the literature. However, insufficient work has been done in incorporating prior structural knowledge onto the learning of underlying graphical models from data. Learning a graph with a specific structure is essential for interpretability and identification of the relationships among data. Useful structured graphs include the multi-component graph, bipartite graph, connected graph, sparse graph, and regular graph. In general, structured graph learning is an NP-hard combinatorial problem, therefore, designing a general tractable optimization method is extremely challenging. In this paper, we introduce a unified graph learning framework lying at the integration of Gaussian graphical models and spectral graph theory. To impose a particular structure on a graph, we first show how to formulate the combinatorial constraints as an analytical property of the graph matrix. Then we develop an optimization framework that leverages graph learning with specific structures via spectral constraints on graph matrices. The proposed algorithms are provably convergent, computationally efficient, and practically amenable for numerous graph-based tasks. Extensive numerical experiments with both synthetic and real data sets illustrate the effectiveness of the proposed algorithms. The code for all the simulations is made available as an open source repository.

1. Introduction

The paper addresses the difficulty of jointly learning graph structures and weights when existing approaches are often structure-specific or computationally demanding. It introduces spectral formulations and convergent algorithms for learning multiple graph families.

1.1 Related work

  • Existing methods often separate structure inference from weight estimation, are limited to specific structures, or require computationally demanding multi-stage procedures.The paper notes that some existing methods also require known connectivity information.Source: §1 · pp. 2–3, §1.1 · p. 3

1. Introduction

  • The authors frame structured graph learning as NP-hard and propose converting combinatorial constraints into analytical spectral constraints on graph matrices.The framework learns graph structure and weights simultaneously.Source: §1 · p. 3, §1.2 · p. 4

1.2 Summary of contributions

  • The Laplacian-spectral formulation covers multi-component, regular, sparse connected, modular, and grid graphs, among other structures.It uses spectral properties of the Laplacian matrix.Source: • Structured graph learning via… · p. 4
  • The adjacency-spectral formulation addresses bipartite graphs, while joint Laplacian and adjacency constraints cover bipartite-regular and multi-component bipartite variants.The joint formulation includes multi-component bipartite-regular graphs.Source: • Structured graph learning via… · p. 4
  • Block MM, also called BSUM, algorithms solve the formulations with theoretical convergence and worst-case complexity O(p^3), matching GLasso.The paper reports experiments on synthetic and real data.Source: • Structured graph learning via… · p. 4

2. Problem Formulation

The problem formulation represents graph structure through matrix properties, with the Laplacian encoding edges and connectivity. It also relates the matrix to Gaussian Markov random fields.

2. Problem Formulation

  • A simple undirected graph with positive edge weights and no self-loops or multiple edges can be represented by a graph matrix whose nonzero entries correspond to edges.The matrix choice depends on modeling assumptions, desired graph properties, applications, and theoretical requirements.Source: §2 · p. 5
  • A graph Laplacian is positive semidefinite, diagonally dominant, and has zero row and column sums, so the all-ones vector is in its null space.Its off-diagonal entries encode edge weights as Θij = −wij; Θij = 0 indicates no edge.Source: §2 · pp. 5–6
  • The nonzero pattern of Θ determines graph G and conditional independence; a rank-p precision matrix defines a GMRF, while rank p−k defines an improper GMRF.For an improper GMRF, the density uses the generalized determinant, the product of Θ’s nonzero eigenvalues.Source: §2 · p. 6

2.1 A General Framework for Graph Learning under Spectral Constraints

The general framework learns a graph Laplacian from data statistics while imposing structural requirements through spectral constraints. It can be interpreted as penalized likelihood for Gaussian data or as a divergence-regularized problem under broader conditions.

2.1 A General Framework for Graph Learning under Spectral Constraints

  • The framework optimizes a graph matrix Θ from data statistics S, subject to Laplacian structure and spectral constraints on a transformation of Θ.The transformation can be Θ itself or the corresponding adjacency matrix ΘA.Source: §2.1 · p. 6
  • The spectral constraint set encodes prior structural information, turning combinatorial graph-structure requirements into analytical spectral constraints.The formulation becomes a matrix optimization problem under an appropriate choice of constraints.Source: §2.1 · pp. 6–7
  • For Gaussian data with sample covariance S, the formulation is penalized maximum-likelihood estimation for a structured precision matrix; with positive-definite S, it relates to log-determinant Bregman-divergence regularization.The paper also notes the Laplacian’s role in GMRF modeling and its flexibility for incorporating spectral properties.Source: §2.1 · p. 7

2.2 Structured Graph Learning Via Laplacian Spectral Constraints

The section formulates graph structures through constraints on Laplacian eigenvalues. It relates component count, connectedness, regularity, and cospectral properties to those constraints.

2.2 Structured Graph Learning Via Laplacian Spectral Constraints

  • The Laplacian formulation constrains a desired Laplacian matrix Θ through its eigendecomposition, with the allowed eigenvalues specified by prior structural information.The matrix is also constrained to belong to the set of Laplacian matrices.Source: §2.2 · p. 7

2.2.1 k-component graph

  • A graph’s number of connected components equals the multiplicity of zero among its Laplacian eigenvalues.The figure illustrates three zero eigenvalues for a three-component graph.Source: §2.2.1 · p. 8, Figure 1 · p. 8

2.2.2 Connected sparse graph

  • The section identifies a trade-off between sparsity and connectedness and uses a positive lower bound on nonzero Laplacian eigenvalues to impose both properties.The stated constraint bounds λ2 through λp between c1 and c2, with c1 > 0.Source: §2.2.2 · pp. 8–9

2.2.3 d−regular graph

  • For a d-regular graph, all nodes have the same weighted degree, and the formulation enforces regularity through constraints on Θ.The passage introduces the constraint set and diagonal condition for this structure.Source: §2.2.3 · p. 9

2.2.4 k−component d−regular graph

  • A k-component regular graph, also called a clustered regular graph, is described as useful for improved perceptual grouping in clustering.The section states that this structure is enforced by adding constraints to the formulation.Source: §2.2.4 · p. 9

2.2.5 Cospectral graphs

  • Cospectral graph learning targets graphs with specific eigenvalues; spectral sparsification is given as an example involving sparse approximation of a given graph.The target eigenvalues are related to those of the given graph through a specified function.Source: §2.2.5 · p. 9

2.3 Structured Graph Learning Via Adjacency Spectral Constraints

The framework imposes graph structure by constraining adjacency-matrix eigenvalues. For bipartite graphs, spectral symmetry characterizes the structure, with non-repeated extreme eigenvalues added for connectedness.

2.3 Structured Graph Learning Via Adjacency Spectral Constraints

  • Adjacency spectral constraints encode prior information about the desired graph structure while retaining the Laplacian constraint.The formulation decomposes the adjacency matrix and restricts its eigenvalues to a set containing the prior spectral information.Source: §2.3 · pp. 9–10

2.3.1 General bipartite graph

  • A graph is bipartite if and only if its adjacency spectrum is symmetric about zero.The method enforces this property by pairing eigenvalues with their negatives.Source: §2.3.1 · p. 10

2.3.2 Connected bipartite graph

  • A connected bipartite graph additionally requires non-repeated extreme adjacency eigenvalues.Its spectrum remains symmetric about zero; Figure 2 depicts the adjacency matrix and symmetric eigenvalues.Source: §2.3.2 · p. 10, Figure 2 · p. 11

2.4 Structured Graph Learning Via Joint Laplacian and Adjacency Spectral Constraints

The joint formulation constrains the Laplacian and adjacency spectra simultaneously. This permits combinations such as multi-component bipartite and regular bipartite structures.

2.4 Structured Graph Learning Via Joint Laplacian and Adjacency Spectral Constraints

  • The formulation enforces graph structure through simultaneous spectral constraints on the Laplacian and its corresponding adjacency matrix.Each matrix is represented by an eigendecomposition whose eigenvalues are restricted to a selected set.Source: §2.4 · p. 11

2.4.1 k−component bipartite graph

  • A k-component bipartite graph combines adjacency-spectrum symmetry with k zero Laplacian eigenvalues.These two structural requirements can be imposed together in the joint formulation.Source: §2.4.1 · pp. 11–12

2.4.2 k−component regular bipartite graph

  • A k-component regular bipartite graph combines bipartite symmetry, k-component Laplacian structure, and the regular-graph relation λ_i = d − ψ_i.The joint spectral properties of the adjacency and Laplacian matrices encode regularity.Source: §2.4.2 · p. 12

2.5 Block Successive Upper-bound Minimization algorithm

The BSUM framework optimizes a partitioned variable through sequential block updates. It uses majorizing surrogate functions to make updates easier than directly solving the original problem.

2.5 Block Successive Upper-bound Minimization algorithm

  • BSUM partitions the optimization variable into m blocks and updates them in cyclic order.At each iteration, it updates one block while holding the others fixed.Source: §2.5 · pp. 12–13
  • Each block update solves a subproblem using a majorization function for the objective.The function must satisfy the stated majorization conditions at the current iterate.Source: §2.5 · p. 12
  • With properly chosen surrogate functions, a BSUM subproblem can be easier to solve than the original problem.The framework is a sequential inexact block-coordinate approach.Source: §2.5 · p. 13

3. Structured Graph Learning Via Laplacian Spectral Constraints (SGL)

SGL learns structured Laplacians by representing them with nonnegative edge weights and enforcing spectral constraints. Its block updates yield a convergent algorithm, with an efficient eigenvalue-update procedure and worst-case complexity comparable to GLasso.

3. Structured Graph Learning Via Laplacian Spectral Constraints (SGL)

  • SGL imposes k-component Laplacian spectral constraints and uses ℓ1 regularization to promote sparsity.The method reformulates the regularization using the fixed signs of Laplacian entries.Source: §3 · p. 13

3.1 Graph Laplacian operator L

  • The linear operator L maps a nonnegative weight vector to a matrix satisfying Laplacian symmetry and zero-row-sum constraints.This converts the structured matrix variable into a simpler vector variable.Source: §3.1 · pp. 13–14

3.2 SGL algorithm

  • The SGL algorithm represents Θ as Lw and relaxes exact spectral reconstruction with a weighted squared mismatch penalty.The relaxation can be made tight by choosing β sufficiently large or increasing it iteratively.Source: §3.2 · pp. 14–15

3.2.1 Update of w

  • The w subproblem is strictly convex, but its nonnegativity constraint prevents a closed-form solution, so the algorithm uses majorization.The majorized update has an optimal solution given by a positive-part operation.Source: §3.2.1 · pp. 15–16

3.2.2 Update of U

  • The U update selects the p − k principal eigenvectors of Lw in increasing eigenvalue-magnitude order.The update optimizes over an orthogonal Stiefel manifold.Source: §3.2.2 · p. 16

3.2.3 Update for λ

  • Algorithm 1 solves the q-dimensional regularized isotonic regression globally in at most q + 1 iterations.Its iterative update procedure converges to a KKT point of the convex subproblem.Source: §3.2.3 · pp. 16–17

3.2.4 SGL algorithm summary

  • SGL can be adapted to other spectral constraints and connected graph families; its O(p^3) worst-case complexity matches GLasso, and its iterates converge to KKT points.The dominant step is the eigendecomposition for the U update.Source: §3.2.4 · p. 18

4. Structured Graph Learning Via Adjacency Spectral Constraints (SGA)

SGA formulates connected bipartite graph learning through adjacency spectral constraints and a BSUM-based optimization method. Its updates exploit the symmetry of the adjacency eigenvalues, and the algorithm is reported to converge to KKT points.

4.1 Graph adjacency operator A

  • A linear operator A maps edge weights to an adjacency matrix, and the algorithm relaxes its adjacency spectral constraint into the objective before applying BSUM updates.The formulation drops zero eigenvalues and imposes symmetric nonzero eigenvalues, with ψ_i = −ψ_b+1−i.Source: §4.1 · p. 19, §4.2 · p. 20

4.2.1 Update of w

  • The w subproblem is strictly convex but lacks a closed-form solution under non-negativity, so the method uses majorization for its update.The Lipschitz constant may be unbounded when nonzero edge weights approach zero; imposing w ≥ ǫ_w is one option to force a minimum weight.Source: §4.2.1 · pp. 20–21

4.2.4 SGA algorithm summary

  • The algorithm has worst-case complexity O(p^3), and its generated sequence converges to the set of KKT points of Problem (45).Eigenvalue decomposition and matrix inversion are the most demanding steps; sparse structure can improve them.Source: §4.2.4 · p. 23
  • SGA is a single-stage method for learning bipartite structure directly from the sample covariance matrix and has smaller worst-case complexity than the method of Pavez et al. (2018).The compared approach first estimates structure with Goemans–Williamson and then estimates Laplacian weights with GGL.Source: §4.2.4 · pp. 23–24

5. Structured Graph Learning Via Joint Laplacian and Adjacency Spectral Constraints (SGLA)

SGLA jointly imposes Laplacian and adjacency spectral constraints in a BSUM-type method. This joint treatment supports intricate structures such as k-component bipartite graphs, and the algorithm converges to KKT points.

5. Structured Graph Learning Via Joint Laplacian and Adjacency Spectral Constraints (SGLA)

  • SGLA moves both graph-matrix spectral constraints into the objective to form a tractable approximation, then applies a BSUM-type method.The formulation uses Laplacian and adjacency operators with their respective spectral variables.Source: §5 · p. 24
  • The updates for (U, λ) and (V, ψ) are decoupled and can therefore be performed in parallel.The λ subproblem uses Algorithm 1; ψ can use the specialized method for bipartite graph families or a standard convex solver for a more general convex set.Source: §5 · p. 25

5.1 SGLA algorithm summary

  • SGLA has worst-case complexity O(p^3) and requires two eigenvalue decompositions per iteration; reducing that cost is left to future work.Source: §5.1 · p. 25
  • Joint Laplacian and adjacency spectral constraints let SGLA impose k-component bipartite structure in one stage, combining the component and bipartite requirements.The paper describes this as a structure that previously lacked a one-stage method for direct learning from data.Source: §5.1 · pp. 25–26
  • The sequence generated by Algorithm 4 converges to the set of KKT points of Problem (60).Source: §5.1 · p. 26

6. Experiments

The experiments evaluate SGL across synthetic graph structures and real animal and cancer data, reporting improved graph recovery and clustering in several comparisons.

6.1–6.2 Experimental settings and benchmarks

  • Evaluation uses 20 Monte Carlo runs and RE/FS; comparisons use CGL on connected synthetic graphs, Naive/QP on multi-component graphs, and GLasso/GGL/CLR plus clustering baselines on real data.Source: §6.1 · pp. 26–27, §6.2 · p. 27

6.3.1 Grid graph

  • SGL lowers average RE and raises average FS across grid sample ratios; for RE 0.1 it needs n/p=5 versus Naive 80, QP 29, and CGL 30.Source: Figure 4 · p. 28, §6.3.1 · p. 28

6.3.2 Modular graph

6.3.3–6.3.4 Multi-component graphs

6.3.5 Multi-component graph: components number mismatch

  • With true k=7 but imposed k=2, SGL attained RE=0.18, FS=0.81; thresholding extra edges can recover components, and correct k yields best performance.Source: §6.3.5 · pp. 30–31, Figure 8 · p. 32

6.3.6–6.3.7 Popular structures and animal data

  • SGL perfectly classifies tested synthetic clusters; on animals, it jointly learns connectivity and clusters, with meaningful but differing CLR/SGL groupings.CLR groups all insects; SGL splits them, while SGL groups herbivore mammals that CLR divides.Source: §6.3.6 · p. 31, Figure 10 · p. 33, §6.3.7 · p. 34

6.3.8 Real data: Cancer Genome data set

  • On 801 cancer samples with 20,531 features, SGL uses no labels, outperforms CLR at clustering, and learns component-separated graphs consistent with cancer types.The learned BRCA graph also reveals an inner subgrouping for further biological investigation.Source: §6.3.8 · p. 34, Figure 13 · p. 37

6.3.9 Effect of the parameter β

6.4 Performance evaluation for SGA Algorithm

The evaluations compare SGA and SGLA on bipartite and multi-component bipartite graph learning, including noisy settings. They report average algorithm comparisons and example recovery scores.

6.4 Performance evaluation for SGA Algorithm

  • SGA significantly outperforms Naive, QP, and CGL in average performance, while SGLA significantly outperforms QP and Naive in F-score and has RE comparable to QP.The SGA evaluation uses a connected bipartite graph; the SGLA evaluation uses a three-component bipartite graph.Source: Figure 15 · p. 38, §6.5 · p. 39, Figure 17 · p. 40

6.4.1 Bipartite graph leaning: noisy setting

  • For noisy bipartite graph learning, the illustrated SGA instance reports RE = 0.219 and FS = 0.872.The example uses samples from a noisy precision matrix for a bipartite graph.Source: Figure 16 · p. 39, §6.4.1 · p. 39

6.5 Performance evaluation for SGLA Algorithm

  • SGLA learns multi-component bipartite graphs by combining Laplacian spectral constraints for multiple components with adjacency spectral constraints for bipartite structure.For the three-component evaluation, QP is comparable in RE, while SGLA significantly outperforms the baselines in FS.Source: §6.5 · p. 39, Figure 17 · p. 40

6.5.1 Multi-component bipartite graph: noisy setting

  • In a noisy three-component bipartite example, SGLA reports RE = 0.225 and FS = 0.947, described as perfect structure recovery despite heavily suppressed ground-truth weights.The example adds random noise to all possible edges.Source: Figure 18 · p. 40, §6.5.1 · p. 40

7. Discussion and Conclusion

The conclusion presents a unified GGM framework that imposes graph structure through spectral constraints. The discussion identifies possible extensions to other spectral priors, statistical models, and graph signal processing.

7. Discussion and Conclusion

  • The discussion characterizes the unified spectral-constraint optimization framework as general and as a basis for plausible future directions.The conclusion reports extensive experiments on both synthetic and real data.Source: §7 · p. 41, §7.2 · p. 42

7.1 Discussion

  • The paper also proposes future work on more specific eigenvalue constraints, graph transforms for graph signal processing, and other statistical models.These are presented as plausible extensions of the framework.Source: §7.1 · p. 41

7.1.1 Other spectral prior information

  • Other graph-structure-related spectral properties in the literature are potential sources of additional priors for the framework.The discussion points to further results concerning Laplacian eigenvalues and other graph properties.Source: §7.1.1 · p. 41

7.1.2 Structured statistical models

  • The spectral constraints and algorithms could be integrated with structured Ising, Gaussian covariance, latent-variable, least-squares, regression, and vector auto-regression models.The paper's current focus is their integration with the GGM framework.Source: §7.1.2 · p. 41

7.1.3 Structured graph signal processing

  • The framework could be paired with constraints on graph-matrix eigenvectors to jointly learn structured graphs for graph signal processing.The discussion identifies this joint learning direction as not yet investigated.Source: §7.1.3 · pp. 41–42

7.2 Conclusion

  • The framework converts combinatorial structure constraints into analytical constraints on graph-matrix eigenvalues and develops SGL, SGA, and SGLA for learning graph structures and weights simultaneously within Gaussian graphical modeling.The paper reports convergence properties, low computational complexity, and effectiveness in synthetic and real-data experiments.Source: §7 · p. 41, §7.2 · p. 42

8. Appendix

The appendix supplies proof details for lemmas and convergence theorems associated with the proposed algorithms.

8.1 Proof of Lemma 2

  • The Lemma 2 proof uses an index set of cardinality p − 1 to bound an operator norm, with equality in an intermediate inequality when all x_k are equal.The proof introduces the index set before applying the operator-norm definition.Source: §8.1 · pp. 42–43

8.2 Proof for Lemma 7

  • The iterative-update procedure, whose updates are derived from KKT optimality conditions for Problem (40), converges to its KKT point; the cited lemma also gives a KKT-system solution under the stated bounds.Specifically, c1 ≤ λ1 ≤ ··· ≤ cq ≤ c2.Source: §8.2 · pp. 43, 46

8.3 Proof for Theorem 5

  • Theorem 5 establishes convergence of Algorithm 2 to stationary points, and every limit point satisfies the KKT conditions.The proof notes that the orthogonal Stiefel constraint is nonconvex, while the cost is non-increasing and bounded below.Source: §8.3 · pp. 46–47

8.4 Proof for Lemma 15

  • Lemma 15 uses the symmetry of diagonal vectors to express the least-squares fit through their paired entries.The proof requires the values for ψ to be symmetric across zero.Source: §8.4 · p. 48

8.5 Proof for Theorem 7

  • For Theorem 7, the proof establishes subsequence convergence despite two variables potentially having non-unique updates, then shows each limit is stationary and satisfies the KKT conditions.The argument uses the independent updates of λ and U with ψ and V.Source: §8.5 · pp. 48, 51
Loading 1904.09792v1…