Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present a new optimization problem formulation for learning weighted bipartite graphs, and also extend the formulation to the presence of heavy tailed events (outliers) motivated by real-world problems. They propose a solution to both problem formulations based on PGD and MM, respectively. Experimental results on financial datasets demonstrate the superior performance of the approach compared to competing approaches, however the experiments themselves are limited. 
strengths_and_weaknesses: Originality: 
The paper proposes a novel graph learning framework and efficient solutions in the convex and non-convex case. 

Missing references from the graph learning literature:
* Dong, Xiaowen, et al. "Learning Laplacian matrix in smooth graph signal representations." IEEE Transactions on Signal Processing 64.23 (2016): 6160-6173.
* Kalofolias, Vassilis. "How to learn a graph from smooth signals." Artificial Intelligence and Statistics. PMLR, 2016
* Mateos, Gonzalo, et al. "Connecting the dots: Identifying network structure via graph signal processing." IEEE Signal Processing Magazine 36.3 (2019): 16-43.
* Hu, Chenhui, et al. "A spectral graph regression model for learning brain connectivity of Alzheimer’s disease." PloS one 10.5 (2015): e0128136.

Quality: 
The paper is technically sound and the solutions appropriate. The experimental section is somewhat lacking: Further comments in the questions regarding the experiments. 

Clarity: 
The paper is well-written and the methods clearly laid out in algorithmic form for reproducibility. 

Minor comments:
* Eq 3: V undefined
* Line 79: the statement that the method in [9] lacks statistical support seems somewhat harsh without toning down that it is motivated from a spectral graph theory perspective.
* Acronyms in section 4 are undefined (SOBG, SGA, SGLA)
* line 242: what does out of sample accuracy refer to? There was no reference to a train/test split with respect to this experiment so who are the out-of-samples? The new days? 
* Figure 3 missing colorbar


questions: 1) My major concern is that unfortunately the experimental results are focused on a single dataset and such have limited power to demonstrate the proposed approach. The experimental results section would benefit from a synthetic simulation in which the graphs are known and there are well defined outlier events Competing approaches (refs [9] and [11]) had much more detailed and varied experiments and the current paper would benefit from adding an additional synthetic experiment and real-world experiment. 

2) The statement that there is a decline in accuracy / modularity surrounding an adverse event such as COVID 19 or the crash in 2008 (appendix) and this is a good property of the proposed method is unclear. How does this demonstrate that the approach can handle adverse effects if it results in worse performance? How in practice would this framework be used to identify such an event or perform under these heavy-tail conditions? In comparison, the competing approaches are unaffected or perform better after 2020. 

3) What is the run-time complexity of this approach compared to competing methods (the supplement only details the proposed method)?

limitations: The authors did not describe limitations
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Paper proposes methods for graphical model selection from i.i.d. observations. The graph structure is constrainted to consist of compoeents being bipartite graphs with two node types (objects and classes). Two types of methods are proposed: one for Gaussian models and another one for student-t distributed data that is suited for data plagued by outliers. 

strengths_and_weaknesses: Strengths: 
* Learning network structure of data is an enabling task for many follow up applications such as federated learning. 
* Methods are evaluated on "real-world" data. 

Weaknesses: 

* The novelty is somewhat limited as the proposed methods are combinations of established approaches to graphical model selection via penalaized maximum likelihood methods. The penalty terms are well motivated by existing literature on learning bipartite graphs. 
The main technical result seems to be Theorem 2 which characterizes the convergence of Algorithm 3. What is the practical relevance of Theorem 2 ? How is it used/confirmed in the numerical experiments ?

* The underlying probabilistic model should be written out in more detail. In particular, are the samples assumed to be i.i.d.. or a stationary process which would be more suitable for the numerical experiments which use time series data. 

* The numerical experiments should be expanded by considered synthetic datasets that allow to measure the estimation error of Algorithm 1 - 3. Moreover, it would be interesting to compare with recent methods for graphical model section from samples forming (non-)stationary processes: 

A. Jung, G. Hannak and N. Goertz, "Graphical LASSO based Model Selection for Time Series," in IEEE Signal Processing Letters, vol. 22, no. 10, pp. 1781-1785, Oct. 2015, doi: 10.1109/LSP.2015.2425434.

A. Jung, "Learning the Conditional Independence Structure of Stationary Time Series: A Multitask Learning Approach," in IEEE Transactions on Signal Processing, vol. 63, no. 21, pp. 5677-5690, Nov.1, 2015, doi: 10.1109/TSP.2015.2460219.

N. Tran, O. Abramenko and A. Jung, "On the Sample Complexity of Graphical Model Selection From Non-Stationary Samples," in IEEE Transactions on Signal Processing, vol. 68, pp. 17-32, 2020, doi: 10.1109/TSP.2019.2956687.

* The paper would be much stronger if it would offer theoretical performance guarantees, e.g., required number of observations to ensure a prescribed estimation quality. 
questions: * What is "..a verifiably convergent iterative algorithm" ? 

* What is a "..unconstrained Gaussian Markov random fields (MRF)" ? 

* What do you mean by "..bipartite graphs under the MRF assumption." and " from data under probabilistic assumptions"? Do you mean that the underlying graph structure encodes pairwise local, global Markov properties ? (https://en.wikipedia.org/wiki/Markov_random_field)  It would also be useful to write down the prob. distribution of the observed data more explicitly. 

* What do you mean by "..We design an efficient optimisation algorithm" ? Does your algorithm achieve fundamenal limits regarding number of observations or computational complexity ? In which sense is your algorithm "efficient" ? 

* What is "a Laplacian-constrained precision matrix"?

* What is the relation between matrix A in (3) in the Laplacian matrix that you are after ? 

* Could you explain in more detail what you mean by "..our proposed methods and algorithms" 

* What is an "observed practical complexity" ? 

* What are "heavy-tailed events" and "heavy-tailed bipartite graphs"? 

* Can you pls provide more details for the arguing "...nonconvex due to the summation over concave terms and hence it is difficult to be dealt with directly."

* How does the rank constraint in (18) enter into (19)?

* What are the "node labels" that you refer to in the Experiments  ?

* What is the precise definition for the accuracy and modularity depicted in Figure 1 ? 

* Is Algorithm 3 returning a graph or a matrix ? 

* You might put your approach into context of another family of networked-structured probabilistic models: 

A. Jung, "Networked Exponential Families for Big Data Over Networks," in IEEE Access, vol. 8, pp. 202897-202909, 2020, doi: 10.1109/ACCESS.2020.3033817.

In contrast, to probabilistic graphical models (such as GMRF), networked exponential families model local datasets (at nodes) using separate probability spaces. In contrast, GMRF use a common probability space on which all node attributes/observations are defined. 
*
limitations: n/a
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper investigates the problem of learning undirected, bipartite graphs under different statistical models. The authors propose an optimization framework based on projected gradient descent for learning bipartite graphs under the Gaussian Markov random field model and the problem formulation is extended to learning bipartite graphs under multi-variate Student-t distribution and under multi-component assumption. The key feature of different algorithms proposed is leveraging the properties of bipartite graphs with statistical properties of the considered data models to efficiently infer graph structures. Experiments on a real world dataset demonstrate that the proposed algorithms significantly outperform the state of the art on a multi-component clustering task. 
strengths_and_weaknesses: Strengths:
1. Structure learning of bipartite graphs is a well-motivated problem. Learning bipartite graphs under Gaussian model is well-defined and uses standard technical arguments. The main contributions of interest are learning bipartite graphs under the Student-t distribution to accommodate data models with outliers or heavy-tailed distribution. For this purpose, the authors provide an iterative algorithm based on majorization-minimization framework and extend it to the learning of $k$-component, bipartite graphs. 
2. The mathematical arguments are sound and the rationale behind various choices in the implementations are (usually) well described. 
3. The paper is clearly written and easy to follow.

Weaknesses:
I find the experiments section to be too narrowly focused and possible inadequate to demonstrate learning of bipartite graphs.
Specifically, the experiments focus only on a clustering task and ignore learning of edge weights in these graphs (note that here I refer to the edge weights within the identified clusters as well). The two metrics that quantify accuracy of clustering and the modularity of identified clusters seem to be insufficient in this regard.  
questions: 1. Please provide a reference to the exact lemma for block matrices from [24]. 
2. The definition of operator $P_{\Delta}$ seems to be missing.
3. I did not follow how the problem in (10) amounts to a Euclidean projection on the probability simplex. I suggest adding more details to accompany the following statement after (10): Problem (10) is a Euclidean projection of the rows....
4. Please provide mathematical definitions for modularity and accuracy in Section 4.
5. I believe that the paper will benefit from a more elaborate empirical evaluation focused on learning of bipartite graphs (perhaps on a synthetic dataset) to conclusively demonstrate the utility of the proposed algorithms and any gains over state of the art approaches. 
limitations: Yes.
review_title: null

Meta-review: metareview: The reviewers agree that this work deals with an important problem and provided a sound solution.
confidence: Less certain
Decision: Accept