Joint Inference of Multiple Graphs from Matrix Polynomials
Authors: Madeline Navarro, Yuhao Wang, Antonio G. Marques, Caroline Uhler, Santiago Segarra
JMLR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Numerical experiments demonstrate the effectiveness of the proposed method with perfect covariance information as well as its robustness in the noisy regime. Through experiments on synthetic and real-world data, we illustrate the performance of the proposed joint graph inference method in Section 5. In this numerical experiment, we illustrate the theoretical guarantees in Theorem 1 by jointly inferring pairs of networks from perfect knowledge of the covariances of graph stationary processes. Figure 1: (a) Experimental validation of Theorem 1. (b) Experimental validation of Theorem 2. (c) Recovery error for three social networks with similar structure as a function of the number of signals in the computation of the sample covariance. (d) Recovery error for three networks with no common structure as a function of the number of signals in the computation of the sample covariance. |
| Researcher Affiliation | Academia | Madeline Navarro EMAIL Department of Electrical and Computer Engineering Rice University Houston, TX 77005-1827, USA Yuhao Wang EMAIL Institute for Interdisciplinary Information Sciences Tsinghua University and Shanghai Qi Zhi Institute Haidian District, Beijing, China Antonio G. Marques EMAIL Department of Signal Theory and Communications King Juan Carlos University Madrid, Spain Caroline Uhler EMAIL Department of Electrical Engineering & Computer Science Department of Institute for Data, Systems, and Society Massachusetts Institute of Technology Cambridge, MA 02139-4301, USA Santiago Segarra EMAIL Department of Electrical and Computer Engineering Rice University Houston, TX 77005-1827, USA |
| Pseudocode | No | The paper describes its methodology through mathematical optimization problems such as equations (2), (3), (6), (7), (8), (9), (11), (13), (14), and (15). It does not include any explicitly labeled 'Pseudocode' or 'Algorithm' sections, nor are there structured steps presented in a code-like format. |
| Open Source Code | No | License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v23/20-1375.html. The paper discusses its methodology and presents numerical experiments, but does not provide any explicit statement about making the source code available or a link to a code repository. |
| Open Datasets | Yes | Consider three graphs defined on a common set of nodes representing 32 students from the University of Ljubljana in Slovenia. The networks encode different types of interactions among the students... Access to the data and additional details are available at http://vladowiki.fmf.uni-lj.si/doku.php?id=pajek:data:pajek:students |
| Dataset Splits | No | Subsets are randomly selected from all available votes, and ten trials of randomized subsets are performed to observe their mean behavior; see Figure 3(a). The graph signals are synthetically generated following covariance matrices obtained from the GSOs as explained in the previous numerical experiment. The paper mentions randomized subsets for evaluation but does not specify fixed train/test/validation splits or their sizes. |
| Hardware Specification | No | The paper describes numerical experiments on synthetic and real-world data but does not provide any specific details about the hardware used to run these experiments. |
| Software Dependencies | No | The paper discusses methods and experiments but does not provide specific software dependencies with version numbers, such as programming languages, libraries, or specialized solvers. |
| Experiment Setup | Yes | The formulation of the problem in (3) presents a general case with freedom of different choices of αk and βk,k respectively for each graph and pair of graphs... we implement the same value αk = α for all graphs k and the same value for βk,k = β for all pairs of graphs (k, k ). In this case, note that there is only one degree of freedom determining the trade-off between sparsity and similarity given by the ratio β/α. We jointly estimate K = 3 networks while observing effects on recovery performance as a function of β/α. The first graph is generated from an Erdős-Rényi model with N = 25 and edge-formation probability p = 0.3, and the remaining two graphs are obtained by rewiring a number of edges in the first graph. We test the recovery performance of the robust formulation in (11) where the sample covariances are estimated from varying numbers of graph signals, and ϵn is chosen as small as possible while ensuring feasibility. Moreover, to recover graphs on which the observed signals are not only stationary but also smooth, we add a regularization term S Z to the optimization objective, where Z is the pairwise distance matrix Zij = xi xj 2 2, and xi contains the value of all signals at the i-th node; see Kalofolias (2016). |