search

cornell-zhang / GraphZoom

GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding
BSD 3-Clause "New" or "Revised" License
113 stars 15 forks source link

about projections of cora nodes #14

Closed dproxy8 closed 3 years ago

dproxy8 commented 3 years ago

Hi, thanks for your great work. I have a question about the projections stored in graphzoom/reduction_results/Projection_1.mtx It seems that the 2708 nodes are projected onto 1169 nodes. But there's no explanation about what the number 1169 indicates. Could you provide an explanation about it and how did you create this projections? Thank you in advance.

Chenhui1016 commented 3 years ago

Hi,

This projection is done by our coarsening algorithm. "1169" means the number of nodes in the coarsened graph, which is produced by our coarsening algorithm.

Although we compile our coarsening code to an executable file, you can check the source code in "mat_coarsen/LamgSetup.m". The line56 is where we save the projection matrix.

dproxy8 commented 3 years ago

So 1169 comes from the graph coarsened by Lamg algorithm. But why do you use the Lamg projections even though Simple is selected as the coarsening method? I thought node numbers of the projections should be 781 which is the number of the finally coarsened graph obtained by simple method.

Chenhui1016 commented 3 years ago

I assumed you were using LAMG. Sorry about the confusion. If you use Simple coarsening, the projection matrix is directly produced at line119 in "graphzoom.py" and we do not load the projection matrix from "reduction_results/". In other words, the "Projection_1.mtx" you mentioned was generated by LAMG that you previously ran. If you then run simple coarsening, the "Projection_1.mtx" still exists but it has nothing to do with simple coarsening. Feel free to ask me if you have any questions.

kkkkk001 commented 3 years ago

Hi, thanks for the great work and your reply. Sorry to interpret. I still have some questions about "Projection_1.mtx".

I'm trying to test with other dataset wiki and the code works well with "simple" coarsening methods. When I tried with "lamg" coarsening methods, the dimension of projection doesn't match with the dimension of embedding. when I traced back and checked, I found that the content of "Projection_1.mtx" hasn't been updated and stayed as the projection of the last dataset Cora.

I think except for preparing the json format dataset, there is something else I should do to generate a corresponding projection file. Could you please give me some hints? I have trouble understanding this part.

Chenhui1016 commented 3 years ago

Hi, once you have the correct json format of wiki, you can evaluate GraphZoom on it by simply adding the argument "--dataset wiki". As for your error message, have you successfully performed LAMG coarsening on your dataset? Could you share with me the LAMG coarsening information (e.g.,

nodes in each coarsening level, which should be printed into your console)?

On Sun, Dec 27, 2020 at 4:12 AM kkkkk001 notifications@github.com wrote:

Hi, thanks for the great work and your reply. Sorry to interpret. I still have some questions about "Projection_1.mtx".

I'm trying to test with other dataset wiki and the code works well with "simple" coarsening methods. When I tried with "lamg" coarsening methods, the dimension of projection doesn't match with the dimension of embedding. when I traced back and checked, I found that the content of "Projection_1.mtx" hasn't been updated and stayed as the projection of the last dataset Cora.

I think except for preparing the json format dataset, there is something else I should do to generate a corresponding projection file. Could you please give me some hints? I have trouble understanding this part.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/cornell-zhang/GraphZoom/issues/14#issuecomment-751443648, or unsubscribe https://github.com/notifications/unsubscribe-auth/AKDCMJCWSM7G3N7LAZCHAZ3SW33AFANCNFSM4URVEZQQ .

kkkkk001 commented 3 years ago

Thanks for your reply. I pasted the coarsening information below. I changed the reduced ratio to 4 as suggested. But I still got the error message "Error using LamgSetup (line 51) ERROR: Reduction ratio is too small, please try ReductionRatio > 2 !!!!!!\n"

Below is the related information.

------------------------------------------
Setting up environment variables
---
LD_LIBRARY_PATH is .:/usr/local/MATLAB/MATLAB_Runtime/v94/runtime/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/bin/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/sys/os/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/sys/opengl/lib/glnxa64
Loading Graph to be Reduced......

GraphPath =

    'dataset/wiki/wiki.mtx'

ReductionRatio =

    12

Fusion =

  logical

   1

SavePath =

    'reduction_results/'

###### Running LamgSetup ######
Multi-level setup
        #levels          = 1
        Design gamma     = 1.5
        Edge  complexity = 1.000
        Cycle complexity = 1.000
l  Type     Nodes    Edges    NodeR  EdgeR   DegL1   Nu  Gam  Work  TV 
=======================================================================
1  FINEST   4777     92295    1.000  1.000  38.64   1   0.0  1.00  0  
Error using LamgSetup (line 51)
ERROR: Reduction ratio is too small, plese try ReductionRatio > 2 !!!!!!\n

Successfully Writing Fused Graph.mtx file!!!!!!
%%%%%% Starting Graph Reduction %%%%%%
------------------------------------------
Setting up environment variables
---
LD_LIBRARY_PATH is .:/usr/local/MATLAB/MATLAB_Runtime/v94/runtime/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/bin/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/sys/os/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/sys/opengl/lib/glnxa64
Loading Graph to be Reduced......

GraphPath =

    'dataset/wiki/fused_wiki.mtx'

ReductionRatio =

     4

Fusion =

  logical

   0

SavePath =

    'reduction_results/'

###### Running LamgSetup ######
Multi-level setup
        #levels          = 1
        Design gamma     = 1.5
        Edge  complexity = 1.000
        Cycle complexity = 1.000
l  Type     Nodes    Edges    NodeR  EdgeR   DegL1   Nu  Gam  Work  TV 
=======================================================================
1  FINEST   4777     92295    1.000  1.000  38.64   1   0.0  1.00  0  
Error using LamgSetup (line 51)
ERROR: Reduction ratio is too small, plese try ReductionRatio > 2 !!!!!!\n
Chenhui1016 commented 3 years ago

I see. Your input graph is relatively dense (avg. degree = 92295/4777=19). In our current setting of LAMG, it may not find a high quality coarse graph for dense graphs and thus does not do any coarsening even if you set the reduced_ratio as 2. Here are two solutions:

  1. You can replace "graphzoom/coarsening" and "graphzoom/run_coarsening.sh" with "mat_coarsen/LamgSetup" and "mat_coarsen/run_LamgSetup.sh", respectively. The file" LamgSetup" is relatively insensitive to dense graphs. If it still cannot produce the coarsened graph, you can either refer to the second solution shown below, or send your input graph to me and I will help you to make it work.
  2. As suggested in our paper, you can use "GRASS" to sparsify the input graph first. Here is the executable code of "GRASS": https://sites.google.com/mtu.edu/zhuofeng-graphspar/home. You can simply run "./grass -m YOUR_MTX_FILE -c 100" to obtain the sparsified graph.

Feel free to ask me if you have any questions.

On Sun, Dec 27, 2020 at 8:05 AM kkkkk001 notifications@github.com wrote:

Thanks for your reply. I pasted the coarsening information below. I changed the reduced ratio to 2 as suggested. But I still got the error message "Error using LamgSetup (line 51) ERROR: Reduction ratio is too small, please try ReductionRatio > 2 !!!!!!\n"

Below is the related information.

Setting up environment variables

LD_LIBRARY_PATH is .:/usr/local/MATLAB/MATLAB_Runtime/v94/runtime/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/bin/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/sys/os/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/sys/opengl/lib/glnxa64 Loading Graph to be Reduced......

GraphPath =

'dataset/wiki/wiki.mtx'

ReductionRatio =

12

Fusion =

logical

1

SavePath =

'reduction_results/'
Running LamgSetup

Multi-level setup

levels = 1

    Design gamma     = 1.5
    Edge  complexity = 1.000
    Cycle complexity = 1.000

l Type Nodes Edges NodeR EdgeR DegL1 Nu Gam Work TV

1 FINEST 4777 92295 1.000 1.000 38.64 1 0.0 1.00 0 Error using LamgSetup (line 51) ERROR: Reduction ratio is too small, plese try ReductionRatio > 2 !!!!!!\n

Successfully Writing Fused Graph.mtx file!!!!!! %%%%%% Starting Graph Reduction %%%%%% args: /usr/local/MATLAB/MATLAB_Runtime/v94 dataset/wiki/fused_wiki.mtx 4 n reduction_results/

Setting up environment variables

LD_LIBRARY_PATH is .:/usr/local/MATLAB/MATLAB_Runtime/v94/runtime/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/bin/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/sys/os/glnxa64:/usr/local/MATLAB/MATLAB_Runtime/v94/sys/opengl/lib/glnxa64 Loading Graph to be Reduced......

GraphPath =

'dataset/wiki/fused_wiki.mtx'

ReductionRatio =

 4

Fusion =

logical

0

SavePath =

'reduction_results/'
Running LamgSetup

Multi-level setup

levels = 1

    Design gamma     = 1.5
    Edge  complexity = 1.000
    Cycle complexity = 1.000

l Type Nodes Edges NodeR EdgeR DegL1 Nu Gam Work TV

1 FINEST 4777 92295 1.000 1.000 38.64 1 0.0 1.00 0 Error using LamgSetup (line 51) ERROR: Reduction ratio is too small, plese try ReductionRatio > 2 !!!!!!\n

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/cornell-zhang/GraphZoom/issues/14#issuecomment-751465541, or unsubscribe https://github.com/notifications/unsubscribe-auth/AKDCMJGBT5MJTMBLKD5O6L3SW4WIHANCNFSM4URVEZQQ .