PaperlayerView exact revision on arXiv

Source-linked AI summary

Connecting the Dots: Identifying Network Structure via Graph Signal Processing

Gonzalo Mateos, Santiago Segarra, Antonio G. Marques, Alejandro Ribeiro

arXiv:1810.13066v1eess.SP

TL;DR

The paper addresses how to infer network topology when graph structure is unknown, informal, or difficult to acquire. It presents a tutorial survey of statistical and GSP-based graph-learning methods, emphasizing latent network-process models and emerging extensions. The supported conclusion is a framework for understanding challenges, opportunities, and algorithm choice across network-analytic applications.

  • Problem

    Graph signal processing often assumes known topology, although many networks lack directly observable or validated structure and updated topology can be difficult to acquire.

  • Method

    The tutorial surveys statistical graph learning and GSP-based inverse methods that use graph signals to infer latent topology under observation models involving correlation, smoothness, stationarity, or network diffusion.

  • Results

    The tutorial organizes mature statistical methods, recent GSP topology-inference frameworks, and emerging work on dynamic, nonlinear, multilayer, directed, and causal network models.

  • Takeaways & Limitations

    Choosing a graph-learning algorithm should be guided by the network-analytic application and its signal or network-process assumptions.

  • Takeaways & Limitations

    The surveyed GSP frameworks require assumptions linking observations to the unknown graph, including signal sparsity or smoothness and graph-process models.

Abstract

from arXiv · show

Network topology inference is a prominent problem in Network Science. Most graph signal processing (GSP) efforts to date assume that the underlying network is known, and then analyze how the graph's algebraic and spectral characteristics impact the properties of the graph signals of interest. Such an assumption is often untenable beyond applications dealing with e.g., directly observable social and infrastructure networks; and typically adopted graph construction schemes are largely informal, distinctly lacking an element of validation. This tutorial offers an overview of graph learning methods developed to bridge the aforementioned gap, by using information available from graph signals to infer the underlying graph topology. Fairly mature statistical approaches are surveyed first, where correlation analysis takes center stage along with its connections to covariance selection and high-dimensional regression for learning Gaussian graphical models. Recent GSP-based network inference frameworks are also described, which postulate that the network exists as a latent underlying structure, and that observations are generated as a result of a network process defined in such a graph. A number of arguably more nascent topics are also briefly outlined, including inference of dynamic networks, nonlinear models of pairwise interaction, as well as extensions to directed graphs and their relation to causal inference. All in all, this paper introduces readers to challenges and opportunities for signal processing research in emerging topic areas at the crossroads of modeling, prediction, and control of complex behavior arising in networked systems that evolve over time.

I. INTRODUCTION

The tutorial addresses topology inference when graph structure is unknown or difficult to acquire, using graph signals to learn network structure. It surveys statistical and GSP-based methods and outlines emerging extensions for dynamic, nonlinear, and directed network models.

  • Motivation: Graph signal processing traditionally assumes known network topology, but many conceptual and large infrastructure networks lack directly available or validated graph structure.This motivates learning topology from observations of graph signals.
  • Problem formulation: The central problem is to use graph-signal observations to infer the underlying network structure or a network model supporting efficient signal analysis.The sought model can facilitate representation, visualization, prediction, dimensionality reduction, and spectral clustering.
  • Problem formulation: Topology inference is formulated as an inverse problem requiring a data model that links observations to the unknown graph.Criteria may use probabilistic structure, signal smoothness, or graph stationarity, with regularization encouraging desirable network characteristics.
  • Methods surveyed: The survey first covers statistical approaches centered on correlation, covariance selection, and high-dimensional regression for Gaussian graphical models.It then reviews GSP frameworks based on graph variation, graph filters, diffusion, and stationarity, including latent-network generative assumptions.
  • Methods surveyed: Recent GSP-based frameworks treat the network as latent and observations as generated by a process defined on that graph.A major class assumes observed signals are smooth over the sought graph, while another uses graph-filter-based diffusion models.
  • Outlook: The tutorial compares surveyed methods to inform algorithm choice and briefly discusses dynamic and multilayer networks, nonlinear interactions, directed graphs, and causal inference.Applications connect the topic to modeling, prediction, and control of complex behavior in evolving networked systems.

III. STATISTICAL METHODS FOR NETWORK TOPOLOGY INFERENCE

Statistical network inference begins with similarity measures between nodal signals, but informal graph construction lacks principled validation. Formal approaches instead infer edges through correlation or partial-correlation structure while addressing identifiability, multiple testing, and scalability.

  • Correlation networks: Correlation networks assign edge weights from pairwise similarity measures such as Pearson correlation, Jaccard coefficients, Gaussian radial basis functions, or mutual information.Common constructions threshold user-defined scores or retain the k strongest relations per node, producing k-nearest neighbor graphs.
  • Statistical formulation: Informal thresholding and fixed-degree rules provide no general framework for assessing whether the resulting graph is accurate in an application-appropriate sense.A statistical formulation selects a representative graph from candidate networks and supports analysis of identifiability, consistency, robustness, measurement error, sampling, and complexity.
  • Correlation networks: Topology inference for correlation networks becomes inference of the subset of nonzero correlations among node-indexed random variables.Edges may be defined by nonzero correlations, with weights based on correlation magnitude, covariance magnitude, or binary edge presence.
  • Multiple testing: Individual correlation tests become problematic as graph size grows because the number of candidate edges and simultaneous tests scales as O(N^2).At constant per-edge false-alarm probability PFA, an empty graph can yield on average O(N^2PFA) spurious edges; FDR control is a common workaround but its guarantee assumes independent tests.
  • Multiple testing: The Benjamini–Hochberg procedure can guarantee FDR ≤ q under its independence assumption, but graph-learning tests are often dependent and require careful interpretation.The procedure orders p-values and declares edges using the threshold p_(i) ≤ (2i/N(N−1))q.
  • Partial correlations: Correlation networks capture linear and symmetric pairwise dependencies, which may reflect latent effects rather than direct influence between two vertices.Partial correlations condition on the remaining variables and provide an alternative for inferring direct pairwise relationships, though the resulting model-selection problem remains statistically challenging.

B. Gaussian graphical models, covariance selection, and graphical lasso

For Gaussian signals, topology inference is equivalent to identifying conditional independencies through sparse precision matrices, while graphical-model methods address both statistical structure and high-dimensional computation.

  • Covariance selection: In Gaussian graphical models, nonzero partial correlations correspond bijectively to nonzero entries in the precision matrix Θ, defining covariance selection.The graph edges encode conditional independence relationships among variables.
  • Graphical lasso: Classical maximum-likelihood precision estimation fails when the sample covariance is singular, including high-dimensional regimes where N exceeds P.Regularization is therefore needed for large or undersampled networks.
  • Graphical lasso: The graphical lasso adds sparsity-promoting regularization to the global Gaussian likelihood, producing more parsimonious and interpretable graphs.Variants can penalize only off-diagonal precision entries or use edge-specific penalties.
  • Laplacian constraints: Laplacian-constrained precision models impose nonpositive off-diagonal entries and require diagonal loading because graph Laplacians are singular.The loaded precision estimate can be converted back into a combinatorial Laplacian.
  • Scalability: Interior-point implementations can require O(N^6) complexity and O(N^2) Hessian storage per iteration, motivating scalable first-order algorithms.Specialized methods can handle sparse problems with thousands of nodes in under a few minutes.
  • Recovery guarantees: Support consistency is established with high probability when the sample size scales as P = Ω(dmax^2 log N), where dmax is the maximum nodal degree.This gives a recovery condition for the ground-truth precision matrix.

C. Graph selection via neighborhood-based sparse linear regression

Neighborhood-based inference recovers graph edges by fitting sparse regressions for each node, offering parallel computation and tractability beyond Gaussian models while trading off some statistical efficiency.

  • Neighborhood regression: Each node’s neighbors can be estimated by regressing xi on all other variables, because regression coefficients encode the incident dependencies.In the Gaussian case, the coefficients are expressible through the precision matrix.
  • Edge selection: Sparse neighborhood lasso estimates one regression per vertex, then combines the two directional estimates using an OR or AND rule to enforce edge symmetry.The OR rule selects an edge if either coefficient is nonzero; the AND rule requires both.
  • Recovery guarantees: Under suitable sparsity and sample-size conditions, either edge-selection rule consistently identifies the graph, even when P may be much smaller than N.The guarantee depends on the regularization choice and the ground-truth precision structure.
  • Comparison with graphical lasso: The neighborhood-based method is computationally faster than graphical lasso because its conditional-likelihood problems decompose across vertices and omit the global PSD constraint.All N lasso problems can be solved in parallel.
  • Comparison with graphical lasso: Graphical lasso tends to be more statistically efficient, whereas neighborhood likelihoods remain tractable for discrete or mixed graphical models.For binary variables, the corresponding approach uses ℓ1-penalized logistic regression.
  • GSP background: The GFT decomposes graph signals into spectral components whose eigenvalues quantify variation over the topology.For a Laplacian, the transform is ˜x = VT x and the inverse is x = V˜x.

B. Graph filters as models of network diffusion

Graph filters model network diffusion as polynomial transformations of a graph shift, connecting local information exchange, spectral responses, and familiar temporal convolution in special cases.

  • Network diffusion: Successive applications of S propagate a seed signal over increasing graph neighborhoods, so linear diffusion processes can represent heat diffusion, consensus, and DeGroot opinion dynamics.Product and sum forms are presented as equivalent models for linear network processes.
  • Filter model: A graph filter applies a polynomial in the shift operator, H = h0I + h1S + h2S^2 + . . . + hL−1S^(L−1), to diffuse an input signal.The filter length satisfies L ≤ N in the stated representation.
  • Distributed implementation: Because graph filters are polynomials in S, they commute with the shift and can be implemented distributively through successive exchanges among neighboring nodes.The required number of exchanges is tied to the filter order.
  • Spectral representation: In the graph-frequency domain, the filter response is ˜h = Ψh, and the output spectrum is obtained through an elementwise product with the input spectrum.This parallels the convolution theorem for temporal signals.
  • Temporal connection: For the directed cycle graph, graph filtering becomes circular convolution and both spectral matrices correspond to the DFT; this equivalence does not generally hold for non-circulant graphs.The time-domain identity U = Ψ is specific to the cycle setting described.
  • Stationary graph processes: Weak stationarity can be defined constructively through graph filtering of white input or spectrally through simultaneous diagonalization of the covariance and shift operators.The two definitions coincide under suitable normality and distinct-eigenvalue conditions.
  • Stationary graph processes: Stationarity reduces covariance description from N(N + 1)/2 parameters to N power-spectral-density components.The reduction follows from covariance diagonalization in the graph-shift eigenbasis.

V. LEARNING GRAPHS FROM OBSERVATIONS OF SMOOTH SIGNALS

Smooth-signal graph learning searches for a topology under which observed signals vary little, often jointly estimating a denoised signal representation and a valid sparse Laplacian.

  • Problem formulation: The smooth-signal paradigm learns a graph G(V, E, W) whose edge weights make the observed signals X smooth.Signals on heavily weighted edges are expected to have similar vertex values.
  • Smoothness criterion: Laplacian total variation provides a natural objective for selecting a topology that endows the observations with the desired smoothness.This connects graph learning to denoising, prediction, semi-supervised learning, and spectral clustering.
  • Factor analysis: Graph-dependent factor analysis uses Laplacian eigenvectors as factors and a pseudoinverse-eigenvalue prior that encourages low-pass, smooth signal representations.Large Laplacian eigenvalues receive low-power factor loadings, while small eigenvalues receive high-power loadings.
  • Factor analysis: The MAP estimator can be interpreted both as a Laplacian-based total-variation denoiser and as kernel ridge regression with kernel K = L†.The recovered signal is y = Vχ, an error-free representation of x.
  • Joint optimization: Joint graph learning alternates between estimating a denoised representation and a combinatorial Laplacian while balancing data fidelity, smoothness, and sparsity.The objective uses a quadratic data-fidelity loss, total-variation regularization, and a Frobenius penalty on edge weights.
  • Laplacian constraints: Valid combinatorial Laplacians satisfy trace(L) = N, L1 = 0, and symmetric nonpositive off-diagonal entries, preventing the trivial all-zero solution.The trace constraint fixes the scale, while the Frobenius penalty controls graph sparsity.
  • Optimization: The joint objective is bi-convex, so alternating minimization converges to a stationary point; fixed-L updates have the closed form Y = (I + αL)^−1X.The fixed-L solution is a low-pass graph-filter smoother.

B. Signal smoothness meets edge sparsity

The section presents two graph-learning views that connect signal smoothness with sparse topology: regularized weighted learning and explicit edge-subset selection. The latter directly controls edge count but introduces non-convexity and omits some structural freedoms.

  • Weighted graph learning: Smoothness-based graph learning links smaller signal-induced distances to preferentially selected, sparse edges.When distances arise from a smooth manifold, the resulting graph has a sparse edge set favoring smaller Z_ij.
  • Weighted graph learning: The smoothness formulation can be parameterized through entry-wise adjacency constraints rather than Laplacian constraints, enabling efficient primal-dual solvers.The associated convex optimization problem has complexity O(N2) per iteration and can be parallelized.
  • Weighted graph learning: A general-purpose regularized model combines degree and adjacency penalties to enforce positive degrees while controlling edge sparsity.The logarithmic barrier prevents isolated vertices, whereas Frobenius regularization penalizes larger edge weights; β = 0 yields the sparsest graph.
  • Edge-subset selection: Edge-subset selection represents topology with a Boolean vector ω whose support contains exactly K selected edges.The incidence matrix maps candidate edges to graph Laplacians, while ∥ω∥0 = K explicitly fixes the graph's edge count.
  • Edge-subset selection: Although cardinality-constrained edge selection is non-convex, the noise-free solution is obtained by sorting edge scores and choosing the K smallest at O(K log K) cost.With Gaussian noise, the unknown smooth signal can instead be estimated through alternating minimization or a semidefinite relaxation.

D. Comparative summary

The tutorial contrasts smoothness- and statistical-prior graph learning with diffusion-based inference, which treats the network as a latent structure explaining observed signal covariances. For stationary diffusion, shared eigenvectors enable a two-step recovery strategy, but finite samples and identifiability create constraints.

  • Diffusion-based inference: Diffusion-based inference models observed signals as outputs of a network process, requiring the graph to explain their covariance structure.This framework is broader than smoothness models: low-pass diffusion filters contain smooth signal models as special cases.
  • Stationary processes: The stationary diffusion problem is severely underdetermined and non-convex because inputs, filter coefficients, and the graph shift are all unknown and multiplicatively coupled.The method imposes statistical assumptions on inputs and graph regularity such as sparsity or least-energy weights.
  • Stationary processes: A two-step strategy first estimates the shift eigenvectors from signals, then estimates eigenvalues under graph priors and feasibility constraints.The shift is reconstructed as S = VΛV^T, with Figure 3 summarizing the stationary and non-stationary variants.
  • Stationary processes: Because S and Σ_x share eigenvectors, covariance eigendecomposition recovers the graph Fourier basis while diffusion primarily obscures the shift eigenvalues.The covariance contains indirect relationships, whereas S represents direct relationships; their distinction lies in the eigenvalues.
  • Robustness: Finite samples make perfect covariance recovery infeasible, so the estimated eigenbasis is noisy and robustness must be analyzed.The empirical covariance converges to Σ_x as P increases, and with non-repeated eigenvalues the estimated eigenvectors converge to those of the desired shift.

2) Step 2 – Inferring the eigenvalues:

Step 2 estimates graph-shift eigenvalues by selecting an operator that matches the recovered eigenbasis while satisfying graph constraints and an application-specific objective. The approach supports multiple structural criteria and provides robustness guarantees, but its cubic cost can limit scale.

  • Step 2 – Inferring the eigenvalues: Step 2 selects a shift S that is optimal under f(S), belongs to a prescribed convex operator set, and has the estimated eigenvectors as its eigenbasis.This resolves the eigenvalue ambiguity left after recovering the spectral basis.
  • Step 2 – Inferring the eigenvalues: Graph type is imposed through convex constraints defining Laplacian or adjacency shifts, including symmetry, nonnegative weights, no self-loops, and scale normalization.The adjacency constraints rule out the trivial S = 0 solution by fixing the weighted degree of the first node.
  • Robustness: With noisy eigenvectors, the recovered shift stays within a tolerance-dependent bound, and increasing the number of signals improves recovery under non-repeated eigenvalues.When the eigenbasis is exact and the stated conditions hold, zero tolerance guarantees perfect recovery of the sparsest shift.
  • Incomplete eigenbasis: Partial eigenbasis information enlarges the feasible solution set, while repeated covariance eigenvalues create rotation ambiguity that must be handled explicitly.The remaining shift component is constrained to the orthogonal complement of the known eigenvectors; repeated eigenvalues motivate rotation constraints.
  • Computational complexity: The two-step method requires O(N3) covariance eigendecomposition and O(N3) per iteration for shift recovery, potentially hindering high-dimensional applications.The tutorial identifies custom scalable algorithms as necessary to bridge this computational gap.

C. Diffused non-stationary graph signals

For non-stationary diffusion signals, the method first identifies the graph filter using multiple excitation processes and then feeds its estimated eigenvectors into shift identification. Positive-semidefinite filters yield strong identifiability, while generic input covariance breaks the stationary shortcut.

  • Generic input covariance: For generic non-identity input covariance, Σ_x is not simultaneously diagonalizable with S, so sample-covariance eigenvectors cannot serve as the shift eigenbasis.This invalidates the stationary Step 1 shortcut and motivates explicit filter identification.
  • Non-stationary diffusion: Non-stationary inference uses snapshot signals and statistical information about excitation inputs to estimate the filter eigenvectors before shift identification.The estimated eigenvectors enter the robust Step 2 optimization, forming the second branch of the two-step strategy.
  • Filter identification: With multiple input processes, filter identification fits output covariances to HΣ_w,mH^T through a system of matrix quadratic equations.The method can use independent realizations to estimate each output covariance and compare it with the model-implied covariance.
  • Robust filter identification: When empirical covariances are available, multiple diffusion processes improve system-identification performance relative to relying on a single process.Residuals can be downweighted when sample sizes, and therefore covariance accuracies, differ substantially across processes.
  • Positive semidefinite filters: Assuming H is positive semidefinite gives a strong identifiability result: with known input and output covariances, one diffusion process can suffice.The result applies even for M = 1 when the relevant covariance is known perfectly.

2) General symmetric graph filters:

General symmetric graph-filter inference uses covariance structure to recover graph operators, with identifiability depending on assumptions such as positive semidefiniteness. Heat-diffusion methods instead impose a specific signal-generation model with sparse inputs, trading model specificity for potentially improved estimation.

  • 2) General symmetric graph filters:: For PSD graph filters, the topology-inference solution is unique under the stated symmetric-filter conditions.Without the PSD assumption and with M = 1, the problem is non-identifiable; each quadratic equation admits 2^N solutions parameterized by a binary vector.
  • 2) General symmetric graph filters:: The general symmetric-filter formulation estimates binary sign vectors through a least-squares objective that minimizes residuals across M observed processes.The objective is convex in the binary vectors, but the binary constraints make the optimization non-convex and hard.
  • D. Learning heat diffusion graphs: A heat-diffusion approach models each observed signal as a sparse combination of diffusion processes generated by candidate rates and centered at possible nodes.Its objective combines dictionary fitting, sparsity on combination coefficients, and regularization of the unknown Laplacian under Laplacian and nonnegative-rate constraints.
  • D. Learning heat diffusion graphs: The heat-diffusion optimization is non-convex and involves matrix exponentials, creating local-minimum and computational challenges.A proximal alternating linearized minimization scheme alternates over the Laplacian, sparse coefficients, and diffusion rates; each linearized step is solvable in polynomial time, while the graph-learning cost is O(N^3) per iteration.
  • D. Learning heat diffusion graphs: When heat diffusion is a credible model, the model-specific approach is preferable; otherwise, data-driven methods may estimate better with a larger sample size.The comparison expresses a trade-off between model fidelity and sample requirements rather than a universally best algorithm.
  • Comparison of surveyed methods: The survey compares topology-inference methods by signal models, computational and sample complexities, and application relevance.It frames algorithm selection as dependent on the network-analytic task and the available signal information.

B. Computational and sample complexities

Computational and sample requirements vary substantially across graph-learning approaches. The survey contrasts faster regression-based methods with statistically more efficient graphical lasso, while noting unresolved recovery theory and data-scarcity issues for covariance-eigenvector methods.

  • B. Computational and sample complexities: Neighborhood-based regression algorithms for GMRF model selection are faster, whereas graphical lasso is statistically more efficient.Both approaches have efficient solvers that scale relatively well to large problems.
  • B. Computational and sample complexities: Methods requiring eigenvectors of the empirical covariance are likely to fail with few samples unless regularization is introduced.This contrasts with sparse GMRF estimation in the P ≪ N regime, where successful estimation can remain possible.
  • B. Computational and sample complexities: Sample-complexity analysis for GSP-based topology inference remains unresolved.For one covariance-based approach, recovery performance as a function of P = |X| lacks even an approximate analytical characterization because several estimation and optimization errors interact.
  • B. Computational and sample complexities: Non-convex criteria in several graph-learning approaches can compound these theoretical challenges because they lack global optimality guarantees.The cited discussion specifically identifies approaches relying on non-convex criteria as especially difficult to analyze.
  • B. Computational and sample complexities: Graph-learning choices are shaped by the application and data characteristics, including whether signals are linear, nonlinear, static, dynamic, or directional.The survey presents these extensions as emerging areas rather than treating one representation as universally suitable.
  • B. Computational and sample complexities: Graph-frequency methods learn transforms that support parsimonious signal representations, including a two-step procedure that jointly learns a GFT basis and sparse signals before inferring a Laplacian.Applications include brain functional-connectivity recovery, climate-graph learning, and fMRI classification, where GFT-based reduction outperformed state-of-the-art alternatives.

B. Dynamic networks and multi-layer graphs

Dynamic and multi-layer graph learning extends topology inference to networks that evolve over time or vary across subjects, modalities, and layers. These methods commonly exploit shared nodes, graph similarity, or additional related observations to improve estimation and enable tracking.

  • B. Dynamic networks and multi-layer graphs: Joint graph formulations can improve topology estimates by exploiting additional information across multiple networks.The graphs may share a vertex set while differing in edge sets and weights, as in multi-layer models.
  • B. Dynamic networks and multi-layer graphs: The paper extends earlier topology-inference formulations to dynamic settings, while noting that a thorough treatment of these emerging topics is beyond its scope.The discussion covers dynamic graphs, multi-layer graphs, directed graphs, and nonlinear pairwise interactions.
  • B. Dynamic networks and multi-layer graphs: A common multi-layer assumption is that consecutive graphs are similar, often encoded by a small distance between their shift operators.This is motivated by slowly time-varying graph sequences, though related layers may also represent subjects, demographics, or sensing modalities.
  • B. Dynamic networks and multi-layer graphs: Time-varying graphical lasso combines per-layer penalized likelihood with distance functions that represent smooth or abrupt topology transitions.An ADMM solver is used to tackle the resulting joint optimization efficiently.
  • B. Dynamic networks and multi-layer graphs: Other dynamic estimators learn slowly varying adjacency matrices from smooth graph signals using layer-specific objectives and primal-dual optimization.Alternative regularizers can promote common sparsity patterns or similar edge weights across layers.
  • B. Dynamic networks and multi-layer graphs: Dynamic SEM-based cascade models estimate time-varying directed networks from infection or information-spread traces while accounting for endogenous and external influences.Assuming slowly changing networks, adaptive estimation uses a sparsity-promoting exponentially weighted least-squares criterion; γ < 1 exponentially discards past data for tracking.

C. Nonlinear models of interaction

Linear network models can miss nonlinear dependencies, particularly in systems such as the brain. The survey outlines nonlinear association measures, kernel-based predictors, and hypothesis testing as routes toward nonlinear graph inference, while noting directionality limitations for some measures.

  • C. Nonlinear models of interaction: Mutual information and other nonlinear association measures can summarize dependencies beyond Pearson or partial correlation.The appropriate measure depends on the dependencies suspected in the data.
  • C. Nonlinear models of interaction: Nonlinear interactions among neural regions can make linear models inadequate for capturing dependencies.The paper identifies complex systems such as the brain as settings where this issue is especially relevant.
  • C. Nonlinear models of interaction: Nonlinear interactions between nodal time series can be constructed by replacing linear prediction with nonlinear predictors such as kernel-based methods.Subsequent hypothesis testing can determine whether graph edges are present.
  • C. Nonlinear models of interaction: Nonlinear graph inference requires care in selecting test statistics because tractable null distributions and multiple-testing control can be difficult.These challenges parallel issues discussed for partial-correlation networks.
  • C. Nonlinear models of interaction: Some nonlinear correlation approaches produce undirected graphs and cannot infer directionality.Kernelized structural VARM and SEM counterparts have been proposed to identify directed topologies while explicitly accounting for nonlinearities.

IX. APPLICATIONS

Applications demonstrate how graph learning and GSP-based inference use signals to construct, validate, or interpret network structure across economic, biological, and neuroscience settings.

  • A. Efficient representation of signals supported on a network of US economic sectors: Real economic sectors form a sparse graph, while synthetic sectors AV and FU are highly connected.
  • A. Efficient representation of signals supported on a network of US economic sectors: Keeping the first four GFT coefficients reconstructs the disaggregated GDP signal with relative error 3.5 × 10^-3.
  • A. Efficient representation of signals supported on a network of US economic sectors: The economic example validates that the heuristically constructed graph sparsely represents the disaggregated GDP signal.
  • C. Graph frequency analysis of brain signals during learning: Brain learning-task signals are dominated by low- and high-frequency components, with few regions exceeding the threshold in the medium-frequency component.
  • B. Identifying protein structure via network deconvolution: For protein contact networks, the general filter model produces a sparser graph that more accurately captures the desired structure.
  • B. Identifying protein structure via network deconvolution: For the top 200 edges, mutual information, network deconvolution, and the proposed method recover 36%, 43%, and 53% of desired edges, respectively.

D. Tracking the propagation of information cascades

Information-cascade tracking estimates time-varying networks from web data and reveals changing connectivity around major events involving Kim Jong-un.

  • D. Tracking the propagation of information cascades: The dynamic-SEM estimator is tested to uncover sparse time-varying topologies from real information-cascade data.
  • D. Tracking the propagation of information cascades: Abrupt increases in edge density coincide with Kim Jong-un’s appointment, Kim Jong-il’s death, and Kim Jong-un’s accession.
  • D. Tracking the propagation of information cascades: The dataset contains 360 websites and 466 cascades, retaining only significant cascades that propagated to at least 7 websites.
  • D. Tracking the propagation of information cascades: Inferred edge counts increase over the 45-week observation period as international news websites and blogs show growing interest in Kim Jong-un.
  • D. Tracking the propagation of information cascades: The 45-week observation horizon prevents investigating how quickly global news coverage eventually subsided.
  • X. CONCLUDING REMARKS AND RESEARCH OUTLOOK: The tutorial surveys statistical and GSP-based inference while identifying open directions including guarantees, scalability, discrete signals, nonlinear interactions, and adaptive learning.
Loading 1810.13066v1…