Thanks Tiago,
This is not an issue I’m seeing on my local machine (I’m on OSX) since I haven’t had to reinstall graph_tool. This is only failing within Docker which is relevant since gitlab uses it for CI. Aside from the change to the apt-url, the script I included worked fine before but is now failing.

I tried with the following Dockerfile to not have to depend on gitlab and so that it’s easier to reproduce (can use play-with-docker)

FROM python:3.7-slim

RUN apt-get update &&\
    apt-get install -y gnupg2 software-properties-common &&\
    apt-key adv --keyserver keys.openpgp.org --recv-key 612DEFB798507F25 &&\
    add-apt-repository "deb http://downloads.skewed.de/apt buster main" &&\
    apt-get update &&\
    apt-get install -y python3-graph-tool &&\
    pip3 install numpy &&\
    pip3 freeze &&\
    python3 -c 'from numpy import *'  &&\
    python3 -c 'from graph_tool.all import *'

This is the output of the last three lines:

Installing collected packages: numpy
Successfully installed numpy-1.18.2
numpy==1.18.2
Traceback (most recent call last):
  File "<string>", line 1, in <module>
ModuleNotFoundError: No module named 'graph_tool'

you can see that pip3 freeze is only showing numpy, which when imported is fine, but importing graph_tool fails. I ran the docker image to inspect, and this is the problem I think: it looks like that doing apt-get install -y python3-graph-tool is installing it for the /usr/bin/python3.7, but the python (and pip) versions visible in the PATH to docker is in /usr/local/bin. I am not sure why this would be behaving differently now…

docker build . -t test
docker run -it --rm test /bin/bash

root@afe35d645652:/# which python3
/usr/local/bin/python3
root@afe35d645652:/# python3
Python 3.7.7 (default, Mar 11 2020, 00:35:40) 
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import graph_tool
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ModuleNotFoundError: No module named 'graph_tool'
>>> 
root@afe35d645652:/# /usr/bin/python
python             python2.7          python3-config     python3.7-config   python3.7m-config  python3m-config
python2            python3            python3.7          python3.7m         python3m           
root@afe35d645652:/# /usr/bin/python
python             python2.7          python3-config     python3.7-config   python3.7m-config  python3m-config
python2            python3            python3.7          python3.7m         python3m           
root@afe35d645652:/# /usr/bin/python3.7
Python 3.7.3 (default, Dec 20 2019, 18:57:59) 
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import graph_tool
>>>