Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes an exact nonnegative matrix factorization method that provides interpretable node embeddings (interpretation as the cluster/community assignment). The authors prove that under the constraint of embedding dimensionality, the embeddings can reconstruct adjacency matrix exactly. A training algorithm is provided and shown to be effective in community detection and interpretable link prediction.
strength_and_weaknesses: Strengths:
- The proposed model is interpretable to provide node embeddings that can be interpreted as cluster assignments.
- The paper theoretically proves under certain embedding dimensionality, the node embeddings can be used to perfectly reconstruct the input adjacency matrix.
- The graph model can explicitly capture the homophily and heterophily of the graph.
- An illustrative example is provided in the introduction to help understand the motivations of this work.

Weaknesses:
- It's not clear whether the embedding dimension condition on arboricit is tighter than the existing degree-based theorem.
- The proposed algorithm has a high complexity given that it computes the reconstructed dense adjacency matrix in each iteration (BB^T-CC^T).
- Interpretable link prediction is not a new application, but in the experiments only few methods are compared. 
- The heterophily of the datasets is not clearly justified.
clarity,_quality,_novelty_and_reproducibility: The novelty is good since it studies the exactness of the embeddings on graphs with both homophily and heterophily.
The paper overall is clear and not hard to follow.
It's not clear whether the results presented in the paper is implemented based on the stochastic version or non-stochastic version.
summary_of_the_review: To further justify the weaknesses:
- It's not clear whether 4 * \alpha^2 is a smaller number than 2c (where c is the max degree). In appendix, the authors provide the value of degeneracy, but based on that number, 4 * \alpha^2 is definitely much larger than 2c. In this way, I don't think the bound based on arboricit has a wider applicability.  
- Regarding the heterophily of the datasets, though the authors illustrate the heterophily intuitively, it's not quantified. Thus, it's unable to justify whether the proposed method can model heterophily in practice.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose a representation model in the framework of describing an adjacency matrix through matrix factorization. They also prove a result regarding exact matrix representation, where the needed size of the embeddings can be described in terms of the arboricity of the graph. This improves previous results in terms of applicability to real graphs.
Finally, the authors propose an alternative learning method for the factorization based on gradient descent, which is then used for downstream tasks in the experimental section.
strength_and_weaknesses: The strength of the paper is the result regarding arboricity and the factorization of the adjacency matrix.

However, I find a significant weakness. There is a quite big community working in graph models via factorization, or "dot product graphs", which is not acknowledged in the paper. I'm sure this is not intentional, but the amount of work of these groups is quite large, and published in journals and conferences very related to this one (meaning that this is not a case of similar work but in a very different community) like NeurIPS or PAMI.
Namely, the RDPG model is widely studied and not mentioned in the paper. The model is almost exactly like the ones described in this work, and moreover, there is a version called Generalized RDPG which takes into account heterophily and homophily, and its formulation is very related to the one proposed in this paper (in equation 3).

I think the Generalized RDPG model is described in this paper:
P. Rubin-Delanchy, J. Cape, M. Tang, and C. E. Priebe, "A statistical interpretation of spectral embedding: The generalized random dot product graph," 2017

and some other papers on the subject are:
 - E. Scheinerman and K. Tucker, "Modeling graphs using dot product representations," Comput. Stat.
 - A. Athreya, D. E. Fishkind, M. Tang, C. E. Priebe, Y. Park, J. T.
Vogelstein, K. Levin, V. Lyzinski, and Y. Qin, "Statistical inference on random dot product graphs: A survey,"
 - I. Gallagher, A. Jones, and P. Rubin-Delanchy, "Spectral embedding
for dynamic networks with stability guarantees," Advances in Neural
Information Processing Systems 34, NeurIPS, 2021.
 - B. Marenco et. al, Online change-point detection for weighted and directed random dot product graphs. IEEE Transactions on Signal and Information Processing over Networks, 2022.

clarity,_quality,_novelty_and_reproducibility: The paper is well written in general, the results are clearly stated (and the proof is easy to follow). As far as I know, this result (regarding arboricity) is original and is an interesting extension of existing work. However, the formulation of the model is very related to existing work, which is not described in the paper (see previous section).

The code is included as supplementary material, so this is a good point too.

summary_of_the_review: The paper proposes interesting ideas, but the (unintentional) lack of references to very similar works makes it very hard to accept it in this first version.
I'm sure the authors will take into account these (and maybe other) related papers and will come up with a new version, which would be a very nice paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper addresses the issue with representing (esp. heterophilic, power law) graphs by factorising the adjacency matrix into a combination of homophilic and heterophilic factors that are interpretable. Lower bounds based on logisitic principal components analysis (LPCA) is improved removing assumptions on the max degree and replacing with the arboricity of the graph. A new graph model is proposed with symmetric and non-negative factorisations based on the decomposition mentioned and a simple gradient descent alogirthm is proposed to optimise the paramters. The method is compared to a baseline SVD decomposition and recent work using a similar method, BigClam. Results on synthetic and real-world data are reported with promising results.

strength_and_weaknesses: 
This paper addresses the issue of modelling graphs with both homophily and heterophily in a elegent decomposition that is both simple and effective. The new lower bound is novel and seems valid to the best of my knowledge but I could not follow all steps in detail due to time constraints and lack of deep knowledge in the area. The algorithm to optimise the model is simple and results looked promising. This is very relevant work, and a hot topic in graph related domains including GNNs for example.

I do wonder about the comparison with the other methods, as in the comparison with synthetic data, the BigClam method was limited to 12 factors, when I think using 20 factors would be interesting, and may lead to improved fitting of the BiClam method. Although the model is elegant, the selection of the hyper-parameters (how many homophilic and how many heterophilic factors) is left open but does not seem trivial is it is vital to the good fitting of the model. With the synthetic data, the exact number of homophilic factors was known (10 towns) and number of heterophilic were known (2 genders), leading to an over simplified problem, as this knoweldge is unknown for a real problem. Exporing this would strengthen the work, like showing the behaviour of the model if choosing 9 homophilic and 3 heterpholic features for example, or how to find those from the data maybe? Some more details about how many features and other parameter tuning of the comparison models in the results would also be important to understand if these seem optimal. 

clarity,_quality,_novelty_and_reproducibility: CL.

THe paper is very clearly written and presented. A few small questions I did have though to help clear up some details.

Fig. 1 - can you add some details on the sampling? Not critical though.

Could you elaborate on why kB + kC = 6k is required?

If I understand correctly, homophilic clusters, in B, are found as those with positive eigenvalues and heterophilic clusters, in C, those with negative eignevalues?

How to choose the kB and kC parameter values? Can these eigenvalues above somehow help with this, although for large data this probably not computationally feasible, can you comment?

QU.

"Many graph models fall under the framework of edge-independent graph generative models" - some references, including a review paper would be valueable here to support this claim.

In Figure 3 the learnt features are shown, and the proposed method has captured the ten cities and the additional 2 gender features. Big Clam only learns the ten cities; have you tried with 20 features and BigClam, as this has the potential to learn each combination of GENDER X CITY as an independent feature element?

NO.

There is a recent paper on overlapping community detection with embeddings that would fit into the cited work here, however, they do not address heterophily as far as I understand, nor do they show proof of exact representation but still it is close to this work:

Li, Y., Sha, C., Huang, X., & Zhang, Y. (2018). Community Detection in Attributed Graphs: An Embedding Approach. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11274

The contirbution of introdcuing the heterophilic factors (C) is a very nice contribution, and when this certainly gives the model the capability to fit a graph, with homophilic and heterophilic relations between nodes, with an interpretable representation. A weakness here though is the difficulty to choose the number of positive and negative factors for algorithm, an interesting topic. Additionally, if the other methods, like BigClam have more features, like 20 in the synthetic example, are they able to learn as well given the extra capacity? If so then this method is surely faster, and more interpretable but maybe the ability to reduce the frobenious norm error will be smaller?

RE.

Code is included in the supplementary material. Without the package versions, it may be very hard to get this running in the future. Adding file versions as text in the README or a requirements.txt can solve this problem, including the Python version.


summary_of_the_review: A very good model, with a new lower bound and a simple optimisation approach. The achilles heel seems to be selecting the number of homophilic factors and number of heterophilic factors. This is not explored in the experiments nor discussed in the paper. Clearing this up would make a strong paper.

[Post Review Updates]

My questions were clearly answered and I feel that this is a novel and sginificant contribution to a growing are of interest: working with heterophily in graphs.

I have raised my review to an accept as I see this work as ready for publication.

[Post Reviewer-Discussion]
During the reviewer discussion the similarity to the work on Generalized RDPG was brought up and this area of work is not compared in enough detail considering the similarity with the work on homopholic and heterophilic relations in [1]. There was also some questions about the bound, to be clarified. Therefore I have slightly lowered my review recommendation as I felt these were genuine concerns.

I want to emphasize that in my opinion this is an area of growing interest, namely modelling heterophilic and homophilic relations. I feel this paper is well written and shows promising results. I believe this will be a very strong paper with the additions of addressing more closely the GRDPG and related literature, clarifying questions on the bound and ensuring that the real-data experiments are strongly supporting the claims (datasets are those which have heterophilic and homophilic relations, and the comparable methods are state-of-the-art).

1. P. Rubin-Delanchy, J. Cape, M. Tang, and C. E. Priebe, "A statistical interpretation of spectral embedding: The generalized random dot product graph," 2017
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The work presents a way of decomposing a symmetric adjacency matrix using a Sigmoid and two lower rank matrices representing vectors for homophilous and heterophilous communities. Reviewers feel this is an important area with growing interest, although some earlier work Generalized RDPG also exists which the authors subsequently addressed. Reviewers also liked the model, and arboricity is a good concept to use for sparseness.  The theory shows such embeddings exist for matrices of bounded arboricity. Some experiments are done although the comparisons are limited to some earlier techniques. The paper is well written and motivated.

This is interesting work focussing on the theoretical contribution. The theory is motivated by various recent prior contributions, Peysakhovich & Bottou (2021) and Chanpuriya et al. (2020). Community detection and link prediction are demonstrated for five mid-sized data sets. Analysis of results w.r.t. heterophily on real-world data sets is not done, although as the authors say, a clear definition of heterophily is not currently accepted.  Note also, link prediction methods not based on matrix factorisation can be superior and have not been compared.

Support for acceptance at ICLR was not strong. Reviewers had suggested a number of improvements for discussion and experimental work.  My impression is that the focus of the presentation should be reworked since the core is solid: perhaps trying to better define heterophily and doing some studies on the real data sets to show that working.  Also studies of different model dimensions $K_B$ and $k_C$ could be demonstrated since they are never known in advance.  You have some informed comments here in the response.  Setting these using ground truth would not accepted by typical experimentalists.
justification_for_why_not_higher_score: The paper has a good solid core, a nice model and a good theory.  Many issues and questions remain, though in experimental work, elucidating what heterophily is and really highlighting how the algorithm helps the community.
Decision: Reject