huge memory footprint while adding edges to graph

I have a struct node and a class graph they are looking like this:

struct node {
    node(const std::string &s) : id(std::hash<std::string>()(s)) { }
    node(node &&) = default;
    node(const node &) = default;

    friend bool operator<(node lhs, node rhs){
        return lhs.id < rhs.id;
    }
    mutable bool visited{false};
    const std::size_t id;
    mutable std::set<node> neighbors;
    mutable std::set<node> back_edges;
};

class graph {
    private:
        std::set<node> node_set;
    public:
        size_t add_edge(node from, node to){

            //auto start = std::chrono::system_clock::now();

            auto iter_from = node_set.insert(from).first;
            auto iter_to = node_set.insert(to).first;


            iter_from->neighbors.insert(*iter_to);
            iter_to->back_edges.insert(*iter_from);

            //auto duration = std::chrono::duration_cast<std::chrono::milliseconds>
            //      (std::chrono::system_clock::now() - start);

            //return duration.count();
            return -1;
        }

        std::size_t size(){
            return node_set.size();
        }

};

Now I want to test the add_edge method by generating a random graph. For this I have a function which generates random alphanum strings of the length SIZE:

constexpr size_t SIZE{2};

graph g1;
for (int i = 0; i < 100000; i++){
    g1.add_edge(random_string(SIZE), random_string(SIZE));

If I choose SIZE not too small like more than 5, everything works fine, but if I try to choose SIZE small like 2 or even 1 I get a HUGE memory footprint and the test takes forever. Since the graph should be smaller with a smaller SIZE (for SIZE = 1 -> 26^2) I don't really understand why this happens.

EDIT: for smaller SIZE the add_edge is getting slower and slower each iteration in the loop.

EDIT: here is the function which generates my random strings:

std::string random_string(size_t length) {
    static bool initialized{false};
    if (!initialized) {
        std::srand(std::time(0));
        initialized = true;
    }
    auto randchar = []() -> char {
        static const char charset[] =
                "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        const size_t max_index = (sizeof(charset) - 1);
        return charset[std::rand() % max_index];
    };
    std::string str(length, 0);
    std::generate_n(str.begin(), length, randchar);
    return str;
}