New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

question about computational complexity in global-attn #41

Closed

XingBin111 opened this issue Nov 17, 2023 · 1 comment

XingBin111 commented Nov 17, 2023

The paper claims that global-attention is linear complexity in the number of nodes, but the code(https://github.com/rampasek/GraphGPS/blob/main/graphgps/layer/gps_layer.py#L201) seems to be square complexity. Is it linear or square?

Collaborator

migalkin commented Nov 18, 2023

If you use global_model_type as a vanilla Transformer, then yes it's $O(N^2)$.

Just a few lines below you can select Performer for global attention, and Performer is linear

GraphGPS/graphgps/layer/gps_layer.py

Lines 205 to 206 in 2801570

    
           elif self.global_model_type == 'Performer': 
        
               h_attn = self.self_attn(h_dense, mask=mask)[mask]

luis-mueller closed this as completed

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment