Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper considers the problem of sparsifying directed graphs, a timely task of importance in many applications. The main contribution is the proposal of a unified approach for spectral sparsification of such directed graphs.

The proposed eigenvalue perturbation pipeline is interesting in its own right, and similarly that of ranking edges in terms of spectral importance from Section 5.2.  One of the main advantages of the approach is that it does not require the underlying directed graphs to be strongly connected and aperiodic, unlike recent work from the literature. Their proposed approach is fairly straightforward, but yet appears to be very efficient. The authors do a good job of placing their work in the relevant context, highlighting drawbacks of existing symmetrization techniques. The authors rightfully point out that naive symmetrization schemes from the literature may damage the structural properties of the graph. The proposed a Laplacian symmetrization approach which enjoys theoretical guarantees while remaining computationally scalable. The authors also mention other properties of interest that one could preserve during the sparsification process. 

The authors also evaluate the embedding given by the proposed symmetrized Laplacian in the context of clustering directed graphs, where the majority of existing spectral methods tend to underperform. Clustering directed graphs is an important timely problem, less studied, and the present work makes also a nice contribution in that regard. The application to computing the (Personalized) PageRank is also nice (the sparsification appears to perform well in the PageRank computation), but perhaps less impactful since since this can be computed fast via a number of other methods. 

The authors could further provide more intuition linking Theorem 4.3 on the existence of the sparsifier, and Section 5, in particular the pipeline in Section 5.2  The authors could also consider testing on synthetic data sets, also to assess the behaviour of the proposed method on graphs with increasing density. What about comparison with other approaches? The authors claim strong performance in their numerical results, but it would be good to have some baselines to compare against.
review_title: Spectral Sparsification for Directed Graphs

final_score: rating: 4: Ok but not good enough - rejection
review_content: Authors propose a novel method to approximate a given directed graph with a´nother one (the sparsifier) which has fewer edges. The proposed method seems promising. however, the paper needs significant improvement in clarity and contextualizing the results. 

1. The main algorithmic result, Algorithm 1 should be placed in the main sectino of the paper and not an appendix. 
2. The main numerfic results, e.g., applying the sparsifier to linear solvers should be put in the main section of the paper and not hidden in the appendix. 
3. The comparision for the linear solver application should also inclucde the spcial case of undirected graphs. how does your sparsifier compare then with Spielmen et.al. mehtods. Also, for the general case of directed graphs which are not strongly connected, you should compare with existing sparsifiers for directed graphs but whose analysis requires them to be strongly connected. Maybe in practice those existing sparsifiers work fine. 
4. Pls also evaluate the sparsifier on machine learning applications, e.g., federated and mulit-task learning over networks:

A. Jung and N. Tran, "Localized Linear Regression in Networked Data," in IEEE Signal Processing Letters, vol. 26, no. 7, pp. 1090-1094, July 2019, doi: 10.1109/LSP.2019.2918933. 

minor issues: 
- "..in which any node can be reached from any other node along with direction."
- "...will have the all-one vector as its null space,..."  --> the null space consists of more than one single vector 

review_title: Spectral Sparisifiers for Directed Graphs

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper introduces new notions of producing small approximations of directed graphs. These notions are based on measuring importances of edges with respect to quadratic forms of symmetrizations of the Laplacian. The algorithm is implemented, and some experimental results for the effectiveness of the sparse approximation as preconditioners are shown.

I feel the contributions of the paper are more in the numerical analysis / linear systems solving setting. The new notion introduced appears fundamentally similar to the error-after-symmetrizatzion approaches taken in previous works. The experimental results don't involve end-to-end uses of directed Laplacians / directed random walks for learning tasks, but are more about approximations for solutions of linear systems / pagerank produced. Furthermore, I'm unfamiliar with uses of methods such as GMRES in learning tasks. So given such concerns, I'm unsure how relevant this paper is to ICLR.
review_title: Contributions Unclear

final_score: rating: 3: Clear rejection
review_content: Summary
========
The paper studies a certain notion of spectral sparsification of directed graphs. It claims the existence of nearly linear sized sparsifiers under this notion, and suggests empirical methods to produce such sparsifiers in nearly linear time.

Comments
=========

Section 4: I am not sure what is the downstream justification for the notion of spectral approximation studied here (relative condition number) in the context of directed graphs, and it would help if the authors could elaborate on this. For example, the notion defined in Cohen et al. (2017) enables fast approximate solution of linear equations, which is a primitive in various algorithmic tasks on directed graphs. The notion in this paper does not rigorously lead to such consequences (or at least none are presented), which leaves the question why one should be interested in an existence result like Theorem 4.3. (The appendix contains some experimental results for linear system solving, but no rigorous claims.)

About the proof Theorem 4.3: Could you please clarify how does the approximating matrix $L_{S_u} = B^T W_o^{1/2} T W_o^{1/2} B$ (defined in the end of section 8.2) give rise to a directed subgraph? How does one construct $S$ (or in other words, why can $L_{S_u}$ be written as $L_SL_S^T$ for $L_S$ of the form in eq (18))

Section 5: I am generally not able to follow the derivations in section 5.2, and it may be needed to be written more clearly. Specific comments/questions:
1. How come $\lambda_n>0$ if the matrix $L_{S_u}^+L_{G_u}$  has non-full rank?
2. You define v_i once as the eigenvectors of $L_{S_u}^+L_{G_u}$ in the first sentence sentence as then as scaled eigenvalues of $L_{S_u}$ between eq (5) and (6), which one is it? Or are they supposed to be denoted differently?
3. Could you elaborate on how you arrive at eq (5)?

Section 6: The experiments in the main text concentrate on measuring the relative condition number of the sparsifier w.r.t the original graph as per the sparsification notion studied in this paper, but as written above it is not clear what do we actually get out of the sparsifier. In general I have doubts about fit to the venue; while ICLR scope is broad and inclusive and spectral sparsification has certain potential connections to ML, this paper does not highlight any of them, and it is not entirely clear what it is attempting to achieve.

Conclusion:
=========
Pros: Spectral sparsification of directed graphs is a relatively new field, so far with initial results that invite further research and improvements. The paper implements an algorithm which seems to improve over baselines under certain metrics.
Cons: It is not clear what ML task the paper is trying to solve or improve upon, and what improvement is achieved. Viewed as a theoretical submission, the analysis is unclear to me in many parts, and at present I am unable to confirm its soundness. The algorithm implemented in the experimental section seems rather detached from the preceding theoretical definitions, whose purpose remains somewhat unclear. 

Post-discussion update: I thank the authors for their participation in the discussion. Unfortunately I find it mostly has not cleared the numerous question marks I have regarding the paper. I recommend putting more effort into clarifying the mathematical derivations and into positioning the paper correctly w.r.t. prior work on the topic.
review_title: Review

Meta-review: The paper proposes a fast, nearly-linear time, algorithm for finding a sparsifier for general directed and undirected graphs that approximately preserves the spectral properties of the original graph. The reviewers appreciated the main contribution of the paper, but they were concerned about the correctness and clarity of the paper, as well as the relevance of the contribution to machine learning. Following the discussion with the authors, the reviewers still felt that these concerns had not been fully addressed by the authors' responses and the subsequent revision of the paper. After taking these concerns into account as well as evaluating the paper relative to other ICLR submissions, I recommend reject.
Decision: Reject