MS-BioGraphs MSA200

NameMS-BioGraphs – MSA200
URLhttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-MSA200
Download Linkhttps://dx.doi.org/10.21227/gmd9-1534
Script for Downloading All Fileshttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-on-IEEE-DataPort/
Validating and Sample Codehttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-Validation/
Graph ExplanationVertices represent proteins and each edge represents the sequence similarity between its two endpoints
Edge WeightedYes
DirectedYes
Number of Vertices1,757,323,526
Number of Edges500,444,322,597
Maximum In-Degree658,879
Maximum Out-Degree709,176
Minimum Weight98
Maximum Weight634,925
Number of Zero In-Degree Vertices6,437,984
Number of Zero Out-Degree Vertices7,471,315
Average In-Degree285.8
Average Out-Degree286.0
Size of The Largest Weakly Connected Component496,880,685,957
Number of Weakly Connected Components221,467,156
Creation DetailsMS-BioGraphs: Sequency Similarity Graph Datasets
FormatWebGraph
LicenseCC BY-NC-SA
QUB IDF2223-052
DOI10.5281/zenodo.7820815
Citation
Mohsen Koohi Esfahani, Sebastiano Vigna, 
Paolo Boldi, Hans Vandierendonck, Peter Kilpatrick, March 13, 2024, 
"MS-BioGraphs: Trillion-Scale Sequence Similarity Graph Datasets", 
IEEE Dataport, doi: https://dx.doi.org/10.21227/gmd9-1534.
Bibtex
@data{gmd9-1534-24,
doi = {10.21227/gmd9-1534},
url = {https://dx.doi.org/10.21227/gmd9-1534},
author = {Koohi Esfahani, Mohsen and Vigna, Sebastiano and Boldi, 
Paolo and Vandierendonck, Hans and Kilpatrick, Peter},
publisher = {IEEE Dataport},
title = {MS-BioGraphs: Trillion-Scale Sequence Similarity Graph Datasets},
year = {2024} }


Files

Underlying Graph The underlying graph in WebGraph format:
  • File: MSA200-underlying.graph, Size: 1,558,147,532,780 Bytes
  • File: MSA200-underlying.offsets, Size: 4,319,801,854 Bytes
  • File: MSA200-underlying.properties, Size: 1,517 Bytes
Total Size: 1,562,467,336,151 Bytes
These files are validated using ‘Edge Blocks SHAs File’ as follows.
Weights (Labels) The weights of the graph in WebGraph format:
  • File: MSA200-weights.labels, Size: 1,105,784,580,128 Bytes
  • File: MSA200-weights.labeloffsets, Size: 4,123,546,304 Bytes
  • File: MSA200-weights.properties, Size: 187 Bytes
Total Size: 1,109,908,126,619 Bytes
These files are validated using ‘Edge Blocks SHAs File’ as follows.
Edge Blocks SHAs File (Text) This file contains the shasums of edge blocks where each block contains 64 Million continuous edges and has one shasum for its 64M endpoints and one for its 64M edge weights.
The file is used to validate the underlying graph and the weights. For further explanation about validation process, please visit the https://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-Validation.
  • Name: MSA200_edges_shas.txt
  • Size: 895,200 Bytes
  • SHASUM: de1ac0ddce536168881ca2e49e6d5f0cf5b82bb5
Offsets (Binary) The offsets array of the CSX (Compressed Sparse Rows/Columns) graph in binary format and little endian order. It consists of |V|+1 8-Bytes elements.
The first and last values are 0 and |E|, respectively.
This array helps converting the graph (or parts of it) from WebGraph format to binary format by one pass over (related) edges.
  • Name: MSA200_offsets.bin
  • Size: 14,058,588,216 Bytes
  • SHASUM: c241d2dc4bdf46f60c1cd889ac367504d3f58805
WCC (Binary) The Weakly-Connected Compontent (WCC) array in binary format and little endian order.
This array consists of |V| 4-Bytes elements The vertices in the same component have the same values in the WCC array.
  • Name: MSA200-wcc.bin
  • Size: 7,029,294,104 Bytes
  • SHASUM: 2cb256d5e49e5dd0989715cb909fd8f27bfbd04c
Transposed’s Offsets (Binary) The offsets array of the transposed graph in binary format and little endian order. It consists of |V|+1 8-Bytes elements. The first and last values are 0 and |E|, respectively.
It helps to transpose the graph by performing one pass over edges.
  • Name: MSA200_trans_offsets.bin
  • Size: 14,058,588,216 Bytes
  • SHASUM: 47787ac64fb4485da02e3bcdc1696a814adfdb86
Names (tar.gz) This compressed file contains 120 files in CSV format using ‘;’ as the separator. Each row has two columns: ID of vertex and name of the sequence.
Note: If the graph has a ‘N2O Reordering’ file, the n2o array should be used to convert the vertex ID to old vertex ID which is used for identifying name of the protein in the `names.tar.gz` file.
  • Name: names.tar.gz
  • Size: 27,130,045,933 Bytes
  • SHASUM: ba00b58bbb2795445554058a681b573c751ef315
OJSON The charactersitics of the graph and shasums of the files.
It is in the open json format and needs a closing brace (}) to be appended before being passed to a json parser.
  • Name: MSA200.ojson
  • Size: 897 Bytes
  • SHASUM: 18e371cbb4bd9dbe6515e4528956ff32fb2e30c4


Plots

For the explanation about the plots, please refer to the MS-BioGraphs paper.
To have a better resolution, please click on the images.

In-Degree Distribution
Out-Degree Distribution
Weight Distribution
Vertex-Relative Weight Distribution
Degree Decomposition
Push and Pull Locality
Cell-Binned Average Weight Degree Distribution
Weakly-Connected Components Size Distribution


MS-BioGraphs


Related Posts

MS-BioGraphs MS50

NameMS-BioGraphs – MS50
URLhttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-MS50
Download Linkhttps://dx.doi.org/10.21227/gmd9-1534
Script for Downloading All Fileshttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-on-IEEE-DataPort/
Validating and Sample Codehttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-Validation/
Graph ExplanationVertices represent proteins and each edge represents the sequence similarity between its two endpoints
Edge WeightedYes
DirectedNo
Number of Vertices585,603,088
Number of Edges124,783,559,600
Maximum Degree507,826
Minimum Weight900
Maximum Weight634,925
Number of Zero-Degree Vertices0
Average Degree213.1
Size of The Largest WCC102,256,631,195
Number of WCC155,295,301
Creation DetailsMS-BioGraphs: Sequency Similarity Graph Datasets
FormatWebGraph
LicenseCC BY-NC-SA
QUB IDF2223-052
DOI10.5281/zenodo.7820819
Citation
Mohsen Koohi Esfahani, Sebastiano Vigna, 
Paolo Boldi, Hans Vandierendonck, Peter Kilpatrick, March 13, 2024, 
"MS-BioGraphs: Trillion-Scale Sequence Similarity Graph Datasets", 
IEEE Dataport, doi: https://dx.doi.org/10.21227/gmd9-1534.
Bibtex
@data{gmd9-1534-24,
doi = {10.21227/gmd9-1534},
url = {https://dx.doi.org/10.21227/gmd9-1534},
author = {Koohi Esfahani, Mohsen and Vigna, Sebastiano and Boldi, 
Paolo and Vandierendonck, Hans and Kilpatrick, Peter},
publisher = {IEEE Dataport},
title = {MS-BioGraphs: Trillion-Scale Sequence Similarity Graph Datasets},
year = {2024} }


Files

Underlying Graph The underlying graph in WebGraph format:
  • File: MS50-underlying.graph, Size: 347,621,279,586 Bytes
  • File: MS50-underlying.offsets, Size: 1,235,232,971 Bytes
  • File: MS50-underlying.properties, Size: 1,459 Bytes
Total Size: 348,856,514,016 Bytes
These files are validated using ‘Edge Blocks SHAs File’ as follows.
Weights (Labels) The weights of the graph in WebGraph format:
  • File: MS50-weights.labels, Size: 324,269,690,037 Bytes
  • File: MS50-weights.labeloffsets, Size: 1,221,399,047 Bytes
  • File: MS50-weights.properties, Size: 185 Bytes
Total Size: 325,491,089,269 Bytes
These files are validated using ‘Edge Blocks SHAs File’ as follows.
Edge Blocks SHAs File (Text) This file contains the shasums of edge blocks where each block contains 64 Million continuous edges and has one shasum for its 64M endpoints and one for its 64M edge weights.
The file is used to validate the underlying graph and the weights. For further explanation about validation process, please visit the https://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-Validation.
  • Name: MS50_edges_shas.txt
  • Size: 223,440 Bytes
  • SHASUM: 5d1bc449124448e9a6ed3bd439942e31f55d9f97
Offsets (Binary) The offsets array of the CSX (Compressed Sparse Rows/Columns) graph in binary format and little endian order. It consists of |V|+1 8-Bytes elements.
The first and last values are 0 and |E|, respectively.
This array helps converting the graph (or parts of it) from WebGraph format to binary format by one pass over (related) edges.
  • Name: MS50_offsets.bin
  • Size: 4,684,824,712 Bytes
  • SHASUM: b298f974167a1c64a8ba8e211a970c5b5d427137
WCC (Binary) The Weakly-Connected Compontent (WCC) array in binary format and little endian order.
This array consists of |V| 4-Bytes elements The vertices in the same component have the same values in the WCC array.
  • Name: MS50-wcc.bin
  • Size: 2,342,412,352 Bytes
  • SHASUM: 4d640ce445477191a3bc3dd00f09f712b9429af2
Names (tar.gz) This compressed file contains 120 files in CSV format using ‘;’ as the separator. Each row has two columns: ID of vertex and name of the sequence.
Note: If the graph has a ‘N2O Reordering’ file, the n2o array should be used to convert the vertex ID to old vertex ID which is used for identifying name of the protein in the `names.tar.gz` file.
  • Name: names.tar.gz
  • Size: 27,130,045,933 Bytes
  • SHASUM: ba00b58bbb2795445554058a681b573c751ef315
N2O Reordering (Binary) The New to Old (N2O) reordering array of the graph in binary format and little endian order.
It consists of |V| 4-Bytes elements and identifies the old ID of each vertex which is used in searching the name of vertex (protein) in the names.tar.gz file .
  • Name: MS50-n2o.bin
  • Size: 2,342,412,352 Bytes
  • SHASUM: 91939605bdde3eb67a013f80d4c2a84d1684ca8f
OJSON The charactersitics of the graph and shasums of the files.
It is in the open json format and needs a closing brace (}) to be appended before being passed to a json parser.
  • Name: MS50.ojson
  • Size: 751 Bytes
  • SHASUM: eb94812bea81cd40a3f33d6aaa5fdd63946ffc92


Plots

For the explanation about the plots, please refer to the MS-BioGraphs paper.
To have a better resolution, please click on the images.

Degree Distribution
Weight Distribution
Vertex-Relative Weight Distribution
Degree Decomposition
Cell-Binned Average Weight Degree Distribution
Weakly-Connected Components Size Distribution


MS-BioGraphs


Related Posts

MS-BioGraphs MSA50

NameMS-BioGraphs – MSA50
URLhttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-MSA50
Download Linkhttps://dx.doi.org/10.21227/gmd9-1534
Script for Downloading All Fileshttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-on-IEEE-DataPort/
Validating and Sample Codehttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-Validation/
Graph ExplanationVertices represent proteins and each edge represents the sequence similarity between its two endpoints
Edge WeightedYes
DirectedYes
Number of Vertices1,757,323,526
Number of Edges125,312,536,732
Maximum In-Degree543,117
Maximum Out-Degree297,981
Minimum Weight98
Maximum Weight634,925
Number of Zero In-Degree Vertices6,437,984
Number of Zero Out-Degree Vertices8,542,018
Average In-Degree71.6
Average Out-Degree71.7
Size of The Largest Weakly Connected Component117,980,151,055
Number of Weakly Connected Components363,090,851
Creation DetailsMS-BioGraphs: Sequency Similarity Graph Datasets
FormatWebGraph
LicenseCC BY-NC-SA
QUB IDF2223-052
DOI10.5281/zenodo.7820821
Citation
Mohsen Koohi Esfahani, Sebastiano Vigna, 
Paolo Boldi, Hans Vandierendonck, Peter Kilpatrick, March 13, 2024, 
"MS-BioGraphs: Trillion-Scale Sequence Similarity Graph Datasets", 
IEEE Dataport, doi: https://dx.doi.org/10.21227/gmd9-1534.
Bibtex
@data{gmd9-1534-24,
doi = {10.21227/gmd9-1534},
url = {https://dx.doi.org/10.21227/gmd9-1534},
author = {Koohi Esfahani, Mohsen and Vigna, Sebastiano and Boldi, 
Paolo and Vandierendonck, Hans and Kilpatrick, Peter},
publisher = {IEEE Dataport},
title = {MS-BioGraphs: Trillion-Scale Sequence Similarity Graph Datasets},
year = {2024} }


Files

Underlying Graph The underlying graph in WebGraph format:
  • File: MSA50-underlying.graph, Size: 410,094,612,576 Bytes
  • File: MSA50-underlying.offsets, Size: 3,504,554,221 Bytes
  • File: MSA50-underlying.properties, Size: 1,493 Bytes
Total Size: 413,599,168,290 Bytes
These files are validated using ‘Edge Blocks SHAs File’ as follows.
Weights (Labels) The weights of the graph in WebGraph format:
  • File: MSA50-weights.labels, Size: 284,756,409,010 Bytes
  • File: MSA50-weights.labeloffsets, Size: 3,374,946,996 Bytes
  • File: MSA50-weights.properties, Size: 186 Bytes
Total Size: 288,131,356,192 Bytes
These files are validated using ‘Edge Blocks SHAs File’ as follows.
Edge Blocks SHAs File (Text) This file contains the shasums of edge blocks where each block contains 64 Million continuous edges and has one shasum for its 64M endpoints and one for its 64M edge weights.
The file is used to validate the underlying graph and the weights. For further explanation about validation process, please visit the https://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-Validation.
  • Name: MSA50_edges_shas.txt
  • Size: 224,400 Bytes
  • SHASUM: 6f56a6710ef6b6e7c01e90907f19c7a0099a272c
Offsets (Binary) The offsets array of the CSX (Compressed Sparse Rows/Columns) graph in binary format and little endian order. It consists of |V|+1 8-Bytes elements.
The first and last values are 0 and |E|, respectively.
This array helps converting the graph (or parts of it) from WebGraph format to binary format by one pass over (related) edges.
  • Name: MSA50_offsets.bin
  • Size: 14,058,588,216 Bytes
  • SHASUM: 3272fb9c681648598f18ab5a10bbafb5bf48dca5
WCC (Binary) The Weakly-Connected Compontent (WCC) array in binary format and little endian order.
This array consists of |V| 4-Bytes elements The vertices in the same component have the same values in the WCC array.
  • Name: MSA50-wcc.bin
  • Size: 7,029,294,104 Bytes
  • SHASUM: 82e3ba326bb56c69edbe7fbb90ce70b731e3a7f2
Transposed’s Offsets (Binary) The offsets array of the transposed graph in binary format and little endian order. It consists of |V|+1 8-Bytes elements. The first and last values are 0 and |E|, respectively.
It helps to transpose the graph by performing one pass over edges.
  • Name: MSA50_trans_offsets.bin
  • Size: 14,058,588,216 Bytes
  • SHASUM: 812d75359683dd235a1bd948566b306f43e7088d
Names (tar.gz) This compressed file contains 120 files in CSV format using ‘;’ as the separator. Each row has two columns: ID of vertex and name of the sequence.
Note: If the graph has a ‘N2O Reordering’ file, the n2o array should be used to convert the vertex ID to old vertex ID which is used for identifying name of the protein in the `names.tar.gz` file.
  • Name: names.tar.gz
  • Size: 27,130,045,933 Bytes
  • SHASUM: ba00b58bbb2795445554058a681b573c751ef315
OJSON The charactersitics of the graph and shasums of the files.
It is in the open json format and needs a closing brace (}) to be appended before being passed to a json parser.
  • Name: MSA50.ojson
  • Size: 892 Bytes
  • SHASUM: 5767cdd2e0cddba1ba255afe9accfdbe5d5aabd2


Plots

For the explanation about the plots, please refer to the MS-BioGraphs paper.
To have a better resolution, please click on the images.

In-Degree Distribution
Out-Degree Distribution
Weight Distribution
Vertex-Relative Weight Distribution
Degree Decomposition
Push and Pull Locality
Cell-Binned Average Weight Degree Distribution
Weakly-Connected Components Size Distribution


MS-BioGraphs


Related Posts

MS-BioGraphs MSA10

NameMS-BioGraphs – MSA10
URLhttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-MSA10
Download Linkhttps://dx.doi.org/10.21227/gmd9-1534
Script for Downloading All Fileshttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-on-IEEE-DataPort/
Validating and Sample Codehttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-Validation/
Graph ExplanationVertices represent proteins and each edge represents the sequence similarity between its two endpoints
Edge WeightedYes
DirectedYes
Number of Vertices1,757,323,526
Number of Edges25,236,632,682
Maximum In-Degree207,279
Maximum Out-Degree62,060
Minimum Weight98
Maximum Weight634,925
Number of Zero In-Degree Vertices6,437,984
Number of Zero Out-Degree Vertices9,926,249
Average In-Degree14.4
Average Out-Degree14.4
Size of The Largest Weakly Connected Component15,576,385,764
Number of Weakly Connected Components628,505,933
Creation DetailsMS-BioGraphs: Sequency Similarity Graph Datasets
FormatWebGraph
LicenseCC BY-NC-SA
QUB IDF2223-052
DOI10.5281/zenodo.7820823
Citation
Mohsen Koohi Esfahani, Sebastiano Vigna, 
Paolo Boldi, Hans Vandierendonck, Peter Kilpatrick, March 13, 2024, 
"MS-BioGraphs: Trillion-Scale Sequence Similarity Graph Datasets", 
IEEE Dataport, doi: https://dx.doi.org/10.21227/gmd9-1534.
Bibtex
@data{gmd9-1534-24,
doi = {10.21227/gmd9-1534},
url = {https://dx.doi.org/10.21227/gmd9-1534},
author = {Koohi Esfahani, Mohsen and Vigna, Sebastiano and Boldi, 
Paolo and Vandierendonck, Hans and Kilpatrick, Peter},
publisher = {IEEE Dataport},
title = {MS-BioGraphs: Trillion-Scale Sequence Similarity Graph Datasets},
year = {2024} }


Files

Underlying Graph The underlying graph in WebGraph format:
  • File: MSA10-underlying.graph, Size: 87,421,101,649 Bytes
  • File: MSA10-underlying.offsets, Size: 2,743,422,804 Bytes
  • File: MSA10-underlying.properties, Size: 1,439 Bytes
Total Size: 90,164,525,892 Bytes
These files are validated using ‘Edge Blocks SHAs File’ as follows.
Weights (Labels) The weights of the graph in WebGraph format:
  • File: MSA10-weights.labels, Size: 58,798,062,287 Bytes
  • File: MSA10-weights.labeloffsets, Size: 2,731,563,328 Bytes
  • File: MSA10-weights.properties, Size: 186 Bytes
Total Size: 61,529,625,801 Bytes
These files are validated using ‘Edge Blocks SHAs File’ as follows.
Edge Blocks SHAs File (Text) This file contains the shasums of edge blocks where each block contains 64 Million continuous edges and has one shasum for its 64M endpoints and one for its 64M edge weights.
The file is used to validate the underlying graph and the weights. For further explanation about validation process, please visit the https://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-Validation.
  • Name: MSA10_edges_shas.txt
  • Size: 45,480 Bytes
  • SHASUM: 9c42e8ba057c519ae318071e63ab3ffdf992cd50
Offsets (Binary) The offsets array of the CSX (Compressed Sparse Rows/Columns) graph in binary format and little endian order. It consists of |V|+1 8-Bytes elements.
The first and last values are 0 and |E|, respectively.
This array helps converting the graph (or parts of it) from WebGraph format to binary format by one pass over (related) edges.
  • Name: MSA10_offsets.bin
  • Size: 14,058,588,216 Bytes
  • SHASUM: b42a8f6aee7c0abdd715f523238ea59acb09c24b
WCC (Binary) The Weakly-Connected Compontent (WCC) array in binary format and little endian order.
This array consists of |V| 4-Bytes elements The vertices in the same component have the same values in the WCC array.
  • Name: MSA10-wcc.bin
  • Size: 7,029,294,104 Bytes
  • SHASUM: 37f30d638341fa50ae9c73893e7cab689ef14be8
Transposed’s Offsets (Binary) The offsets array of the transposed graph in binary format and little endian order. It consists of |V|+1 8-Bytes elements. The first and last values are 0 and |E|, respectively.
It helps to transpose the graph by performing one pass over edges.
  • Name: MSA10_trans_offsets.bin
  • Size: 14,058,588,216 Bytes
  • SHASUM: 2ae765f6f79b8f41221ba0d869648d01d19bcadd
Names (tar.gz) This compressed file contains 120 files in CSV format using ‘;’ as the separator. Each row has two columns: ID of vertex and name of the sequence.
Note: If the graph has a ‘N2O Reordering’ file, the n2o array should be used to convert the vertex ID to old vertex ID which is used for identifying name of the protein in the `names.tar.gz` file.
  • Name: names.tar.gz
  • Size: 27,130,045,933 Bytes
  • SHASUM: ba00b58bbb2795445554058a681b573c751ef315
OJSON The charactersitics of the graph and shasums of the files.
It is in the open json format and needs a closing brace (}) to be appended before being passed to a json parser.
  • Name: MSA10.ojson
  • Size: 885 Bytes
  • SHASUM: 0d8c48f9297d36a628aabcd8576cb0c083607534


Plots

For the explanation about the plots, please refer to the MS-BioGraphs paper.
To have a better resolution, please click on the images.

In-Degree Distribution
Out-Degree Distribution
Weight Distribution
Vertex-Relative Weight Distribution
Degree Decomposition
Push and Pull Locality
Cell-Binned Average Weight Degree Distribution
Weakly-Connected Components Size Distribution


MS-BioGraphs


Related Posts

MS-BioGraphs MS1

NameMS-BioGraphs – MS1
URLhttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-MS1
Download Linkhttps://dx.doi.org/10.21227/gmd9-1534
Script for Downloading All Fileshttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-on-IEEE-DataPort/
Validating and Sample Codehttps://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-Validation/
Graph ExplanationVertices represent proteins and each edge represents the sequence similarity between its two endpoints
Edge WeightedYes
DirectedNo
Number of Vertices43,144,218
Number of Edges2,660,495,200
Maximum Degree14,212
Minimum Weight3,680
Maximum Weight634,925
Number of Zero-Degree Vertices0
Average Degree61.7
Size of The Largest WCC124,003,393
Number of WCC15,746,208
Creation DetailsMS-BioGraphs: Sequency Similarity Graph Datasets
FormatWebGraph
LicenseCC BY-NC-SA
QUB IDF2223-052
DOI10.5281/zenodo.7820827
Citation
Mohsen Koohi Esfahani, Sebastiano Vigna, 
Paolo Boldi, Hans Vandierendonck, Peter Kilpatrick, March 13, 2024, 
"MS-BioGraphs: Trillion-Scale Sequence Similarity Graph Datasets", 
IEEE Dataport, doi: https://dx.doi.org/10.21227/gmd9-1534.
Bibtex
@data{gmd9-1534-24,
doi = {10.21227/gmd9-1534},
url = {https://dx.doi.org/10.21227/gmd9-1534},
author = {Koohi Esfahani, Mohsen and Vigna, Sebastiano and Boldi, 
Paolo and Vandierendonck, Hans and Kilpatrick, Peter},
publisher = {IEEE Dataport},
title = {MS-BioGraphs: Trillion-Scale Sequence Similarity Graph Datasets},
year = {2024} }


Files

Underlying Graph The underlying graph in WebGraph format:
  • File: MS1-underlying.graph, Size: 6,300,911,484 Bytes
  • File: MS1-underlying.offsets, Size: 77,574,569 Bytes
  • File: MS1-underlying.properties, Size: 1,288 Bytes
Total Size: 6,378,487,341 Bytes
These files are validated using ‘Edge Blocks SHAs File’ as follows.
Weights (Labels) The weights of the graph in WebGraph format:
  • File: MS1-weights.labels, Size: 8,201,441,365 Bytes
  • File: MS1-weights.labeloffsets, Size: 80,797,007 Bytes
  • File: MS1-weights.properties, Size: 184 Bytes
Total Size: 8,282,238,556 Bytes
These files are validated using ‘Edge Blocks SHAs File’ as follows.
Edge Blocks SHAs File (Text) This file contains the shasums of edge blocks where each block contains 64 Million continuous edges and has one shasum for its 64M endpoints and one for its 64M edge weights.
The file is used to validate the underlying graph and the weights. For further explanation about validation process, please visit the https://blogs.qub.ac.uk/DIPSA/MS-BioGraphs-Validation.
  • Name: MS1_edges_shas.txt
  • Size: 5,040 Bytes
  • SHASUM: 27974edb4bf8f3b17b00ff3a72a703da18f3807a
Offsets (Binary) The offsets array of the CSX (Compressed Sparse Rows/Columns) graph in binary format and little endian order. It consists of |V|+1 8-Bytes elements.
The first and last values are 0 and |E|, respectively.
This array helps converting the graph (or parts of it) from WebGraph format to binary format by one pass over (related) edges.
  • Name: MS1_offsets.bin
  • Size: 345,153,752 Bytes
  • SHASUM: 0abedde32e1ac7181897f82d10d40acfe14f2022
WCC (Binary) The Weakly-Connected Compontent (WCC) array in binary format and little endian order.
This array consists of |V| 4-Bytes elements The vertices in the same component have the same values in the WCC array.
  • Name: MS1-wcc.bin
  • Size: 172,576,872 Bytes
  • SHASUM: 4c491dd96e3582b70a203ae4a910001381278d75
Names (tar.gz) This compressed file contains 120 files in CSV format using ‘;’ as the separator. Each row has two columns: ID of vertex and name of the sequence.
Note: If the graph has a ‘N2O Reordering’ file, the n2o array should be used to convert the vertex ID to old vertex ID which is used for identifying name of the protein in the `names.tar.gz` file.
  • Name: names.tar.gz
  • Size: 27,130,045,933 Bytes
  • SHASUM: ba00b58bbb2795445554058a681b573c751ef315
N2O Reordering (Binary) The New to Old (N2O) reordering array of the graph in binary format and little endian order.
It consists of |V| 4-Bytes elements and identifies the old ID of each vertex which is used in searching the name of vertex (protein) in the names.tar.gz file .
  • Name: MS1-n2o.bin
  • Size: 172,576,872 Bytes
  • SHASUM: b163320b6349fed7a00fb17c4a4a22e7d124b716
OJSON The charactersitics of the graph and shasums of the files.
It is in the open json format and needs a closing brace (}) to be appended before being passed to a json parser.
  • Name: MS1.ojson
  • Size: 736 Bytes
  • SHASUM: c60afa0652955fd46f1bb8056380523504d69fa6


Plots

For the explanation about the plots, please refer to the MS-BioGraphs paper.
To have a better resolution, please click on the images.

Degree Distribution
Weight Distribution
Vertex-Relative Weight Distribution
Degree Decomposition
Cell-Binned Average Weight Degree Distribution
Weakly-Connected Components Size Distribution


MS-BioGraphs


Related Posts

MS-BioGraphs Validation

Repository

https://github.com/DIPSA-QUB/MS-BioGraphs-Validation

Explanation

We provide a Shell script, validation.sh, and a Java program, EdgeBlockSHA.java, to verify the the correctness of the graphs. Each graph has a .ojson file whose shasum is verified by the value retreived from our server. Files such as offsets.bin, wcc.bin, n2o.bin, trans_offsets.bin, and edges_shas.txt have shasum records in the ojson file which is used for validation of these files.

The graph in WebGraph format has been compressed in MS??-underlying.* and MS??-weights.* files. In order to validate the compressed graph, the EdgeBlockSHA.java is used. It is a parallel Java code that uses the WebGraph library to traverse the graph and calculate the shasum of blocks of edges (endpoints and weights). Then, the calculated results are matched with the edges_shas.txt file of the graph.

It is also possible to validate some particular blocks by matching the calculated shasum with the relevant row in the edges_shas.txt file. This file has a format such as the following. Each block contains 64 Million consecutive edges. The start of each block is identified by a vertex ID and its edge index. The Column endpoint_sha is the shasum of the 64 Million endpoints when stored as an array of 4-Bytes elements in the binary format and in the little endian order. Similarly, Column weights_sha shows the shasum of weights (labels). We have separated weights from endpoints as in some applications weights are not needed and therefore it is not necessary to read and validate them.

64MB blk#;     vertex; edge index;                             endpoint_sha;                              weights_sha;
         0;          0;          0; 509784b158cb9404241afb21d0ceaf590b88d2f2; 57da4ad7bb89c5922e436b0535d791fa8f40dffd;
         1;    2315113;        705; fafc118563c1d7b5fbff64af56edd6a56524f479; 13b7a9ca60bfb0715d563218d0a1cd787b00a07c;
         2;    4521625;        597; 4ed65aa07c8062a151166ef2e9bdb93e41d19357; 8158276bec426ee46eca9912759eb9bd57fcc957;
         3;    6347361;        112; d02e8913c807c3f4ecde9c638e0ded5ab80ba819; 26bc3296de65cba6ac539cd96b79ae6f7a4d37be;
         4;    8447869;         15; 61513c84db40124496cdf769516118b63598914f; 781b9f4372ac614e94d097017c756d015234deb6; 
 

Requirements

  • JDK with version > 15
  • jq
  • wget

WebGraph Framework

Please visit https://webgraph.di.unimi.it .

License

Licensed under the GNU v3 General Public License, as published by the Free Software Foundation. You must not use this Software except in compliance with the terms of the License. Unless required by applicable law or agreed upon in writing, this Software is distributed on an “as is” basis, without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose, neither express nor implied.

Copyright 2022-2023 The Queen’s University of Belfast, Northern Ireland, UK

MS-BioGraphs

Related Posts

Poster Presentation | Graphlet-based Filtering for High-Performance Subgraph Isomorphism Search

I presented a poster on “Graphlet-based Filtering for High-Performance Subgraph Isomorphism Search” at the 19th International Summer School on Advanced Computer Architecture and Compilation for High-performance Embedded Systems organised by HiPEAC at Fiuggi, Italy between July 9 – 15, 2023.


Summary

Introduction

Graphs are powerful tools for representing complex relationships in various domains such as social networks, bioinformatics, and computer networks. The Subgraph Isomorphism (SI) search problem is crucial in graph analytics, involving finding instances of a pattern graph within a larger data graph. This problem has applications in pattern discovery and graph database queries.

However, the SI problem is NP-complete, meaning that it becomes computationally intensive for larger graphs. To tackle this challenge, researchers have proposed heuristic algorithms that aim to speed up the SI search by pruning the search space through various techniques.

Three Stages of Heuristic Algorithms

These heuristic algorithms can be divided into three stages:

  1. Filtering: In this stage, a candidate set of data graph vertices is generated for each vertex of the pattern graph. The goal is to select a subset of data graph vertices that are potential matches for each pattern vertex. Two common filtering techniques are Label and Degree Filtering (LDF) and Neighbourhood Label Filtering (NLF). LDF ensures that only vertices with matching labels and sufficient degrees are considered, while NLF adds further constraints based on the labels of neighbours.
  2. Ordering: The vertices of the pattern graph are ordered for mapping with the candidate data vertices. The Highest Degree First (HDF) strategy is commonly used.
  3. Backtracking: A backtracking search is performed based on the ordered vertices to find subgraph isomorphisms.

Proposed Approach: Graphlet Filtering (GLF)

The proposed approach, Graphlet Filtering (GLF), introduces an additional stage to the heuristic algorithms. Graphlets are recurring small subgraphs, and orbits represent groups of vertices within these graphlets. By counting the occurrences of orbits in both pattern and data graphs, we propose that the count of an orbit in the pattern graph must be less than or equal to the count of the same orbit in the candidate data vertices’ graphs. This idea enhances the filtering stage by providing more stringent filtering criteria.

Preliminary Results

We conducted preliminary experiments on various datasets and found that GLF filtering provides additional filtering enhancements ranging from 4.2% to 15.38% depending on the dataset and pattern graph density. Across all datasets, the GLF technique improved filtering by 9.93% for sparse pattern graphs and 8.49% for dense pattern graphs.

Conclusion

The study suggests that incorporating graphlet-based filtering (GLF) into the existing heuristic algorithms for the Subgraph Isomorphism problem can lead to more effective filtering and pruning of the search space. We plan to explore the impact of GLF on the runtime of different heuristic algorithms. If successful, this technique could significantly reduce the execution time of algorithms used for tasks such as pattern discovery and graph database queries.


Download the poster and the abstract below.

ASCCED: Asynchronous Scientific Continuous Computations Exploiting Disaggregation

UKRI EPSRC Grant

The design of efficient and scalable scientific simulation software is reaching a critical point whereby continued advances are increasingly harder, more labour-intensive, and thus more expensive to achieve. This challenge emanates from the constantly evolving design of large-scale high-performance computing systems. World-leading (pre-)exascale systems, as well as their successors, are characterised by multi-million-scale parallel computing activities and a highly heterogeneous mix of processor types such as high-end many-core processors, Graphics Processing Units (GPU), machine learning accelerators, and various accelerators for compression, encryption and in-network processing. To make efficient use of these systems, scientific simulation software must be decomposed in various independent components and make simultaneous use of the variety of heterogeneous compute units.

Developing efficient, scalable scientific simulation software for these systems becomes increasingly harder as the limits of parallelism available in the simulation codes is approached. Moreover, the limit of parallelism cannot be reached in practice due to heterogeneity, system imbalances and synchronisation overheads. Scientific simulation software often persists over several decades. The software is optimised and re-optimised repeatedly as the design and scale of the target hardware evolves at a much faster pace, as impactful changes in the hardware may occur every few years. One may thus find that the guiding principles that underpin such software are outdated.

The ASCCED project will fundamentally change the status quo in the design of scientific simulation software by simplifying the design to reduce software development and maintenance effort, to facilitate performance optimisation, and to make software more robust to future evolution of computing hardware. The key distinguishing factor of our approach is to structure scientific simulation software as a collection of loosely coupled parallel activities. We will explore the opportunities and challenges of applying techniques previously developed for Parallel Discrete Event Simulation (PDES) to orchestrate these loosely coupled parallel activities. This radically novel approach will enable runtime system software to extract unprecedented scales of parallelism and to minimise performance inefficiencies due to synchronisation. Additionally, based on a speculative execution mechanism, it will uncover parallelism that has not been feasible to extract before.

The computational model proposed by ASCCED will, if successful, initiate a new direction of research within programming models for high-performance computing that may dramatically impact not only the performance of scientific simulation software, but can also reduce the engineering effort required to produce efficient scientific simulation software. It will have a profound impact on the sciences that are highly dependent on leadership computing capabilities, such as climate modeling and cancer research.

On Designing Structure-Aware High-Performance Graph Algorithms (PhD Thesis)

Mohsen Koohi Esfahani
Supervisors: Hans Vandierendonck and Peter Kilpatrick

Thesis in PDF format
Thesis on QUB Pure Portal

Graph algorithms find several usages in industry, science, humanities, and technology. The fast-growing size of graph datasets in the context of the processing model of the current hardware has resulted in different bottlenecks such as memory locality, work-efficiency, and load-balance that degrade the performance. To tackle these limitations, high-performance computing considers different aspects of the execution in order to design optimized algorithms through efficient usage of hardware resources.

The main idea in this thesis is to analyze the structure of graphs to exploit special features that are key to introduce new graph algorithms with optimized performance.

First, we study the structure of real-world graph datasets with skewed degree distribution and the applicability of graph relabeling algorithms as the main restructuring tools to improve performance and memory locality. To that end, we introduce novel locality metrics including Cache Miss Rate Degree Distribution, Effective Cache Size, Push Locality and Pull Locality, and Degree Range Decomposition.

Based on this structural analysis, we introduce the Uniform Memory Demands strategy that (i) recognizes diverse memory demands and behaviours as a source of performance inefficiency, (ii) separates contrasting memory demands into groups with uniform behaviours across each group, and (iii) designs bespoke data structures and algorithms for each group in order to satisfy memory demands with the lowest overhead.

We apply the Uniform Memory Demands strategy to design three graph algorithms with optimized performance: (i) the SAPCo Sort algorithm as a parallel counting sort algorithm that is faster than comparison-based sorting algorithms in degree-ordering of power-law graphs, (ii) the iHTL algorithm that optimizes locality in Sparse Matrix-Vector (SpMV) Multiplication graph algorithms by extracting dense subgraphs containing incoming edges to in-hubs and processing them in the push direction, and (iii) the LOTUS algorithm that optimizes locality in Triangle Counting by separating different caching demands and deploying specific data structure and algorithm for each of them.

Bibtex

@phdthesis{ODSAGA-ethos.874822,
  title  = {On Designing Structure-Aware High-Performance Graph Algorithms},
  author = {Mohsen Koohi Esfahani},
  year   = 2022,
  url    = {https://blogs.qub.ac.uk/DIPSA/On-Designing-Structure-Aware-High-Performance-Graph-Algorithms-PhD-Thesis/},
  school = {Queen's University Belfast},
  EThOSID = {uk.bl.ethos.874822}
}

Related Posts

LaganLighter

LaganLighter Source Code


Repository

https://github.com/DIPSA-QUB/LaganLighther

Algorithms in This Repo

Cloning

git clone https://github.com/DIPSA-QUB/LaganLighter.git --recursive

Graph Types

LaganLighter supports the following graph formats:

  • CSR/CSC graph in text format, for testing. This format has 4 lines: (i) number of vertices (|V|), (ii) number of edges (|E|), (iii) |V| space-separated numbers showing offsets of the vertices, and (iv) |E| space-separated numbers indicating edges.
  • CSR WebGraph format: supported by the Poplar Graph Loading Library
    external git repository

Measurements

In addition to execution time, we use the PAPI library to measure hardware counters such as L3 cache misses, hardware instructions, DTLB misses, and load and store memory instructions. ( papi_(init/start/reset/stop) and (print/reset)_hw_events functions defined in omp.c).

To measure load balance, we measure the total time of executing a loop and the time each thread spends in this loop (mt and ttimes in the following sample code). Using these values, PTIP macro (defined in omp.c) calculates the percentage of average idle time (as an indicator of load imbalance) and prints it with the total time (mt).

mt = - get_nano_time()
#pragma omp parallel  
{
   unsigned tid = omp_get_thread_num();
   ttimes[tid] = - get_nano_time();
	
   #pragma omp for nowait
   for(unsigned int v = 0; v < g->vertices_count; v++)
   {
      // .....
   }
   ttimes[tid] += get_nano_time();
}
mt += get_nano_time();
PTIP("Step ... ");

As an example, the following execution of Thrifty, shows that the “Zero Planting” step has been performed in 8.98 milliseconds and with a 8.22% load imbalance, while processors have been idle for 72.22% of the execution time, on average, in the “Initial Push” step.

NUMA-Aware and Locality-Preserving Partitioning and Scheduling

In order to assign consecutive partitions (vertices and/or their edges) to each parallel processor, we initially divide partitions and assign a number of consecutive partitions to each thread. Then, we specify the order of victim threads in the work-stealing process. During the initialization of LaganLighter parallel processing environment (in initialize_omp_par_env() function defined in file omp.c), for each thread, we create a list of threads as consequent victims of stealing.

A thread, first, steals jobs (i.e., partitions) from consequent threads in the same NUMA node and then from the threads in consequent NUMA nodes. As an example, the following image shows the stealing order of a 24-core machine with 2 NUMA nodes. This shows that thread 1 steals from threads 2, 3, …,11, and ,0 running on the same NUMA socket and then from threads 13, 14, …, 23, and 12 running on the next NUMA socket.

We use dynamic_partitioning_...() functions (in file partitioning.c) to process partitions by threads in the specified order. A sample code is in the following:

struct dynamic_partitioning* dp = dynamic_partitioning_initialize(pe, partitions_count);

#pragma omp parallel  
{
   unsigned int tid = omp_get_thread_num();
   unsigned int partition = -1U;		

   while(1)
   {
      partition = dynamic_partitioning_get_next_partition(dp, tid, partition);
      if(partition == -1U)
	 break; 

      for(v = start_vertex[partition]; v < start_vertex[partition + 1]; v++)
      {
	// ....
       }
   }
}

dynamic_partitioning_reset(dp);

Bugs & Support

As “we write bugs that in particular cases have been tested to work correctly”, we try to evaluate and validate the algorithms and their implementations. If you receive wrong results or you are suspicious about parts of the code, please contact us or submit an issue.

License

Licensed under the GNU v3 General Public License, as published by the Free Software Foundation. You must not use this Software except in compliance with the terms of the License. Unless required by applicable law or agreed upon in writing, this Software is distributed on an “as is” basis, without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose, neither express nor implied. For details see terms of the License.

Copyright 2022 The Queen’s University of Belfast, Northern Ireland, UK

LaganLighter

Related Posts