C# Cloning graph and updating circular references

Let me preface this by stating that I have seen similar posts to this, but none of the solutions have satisfied me and/or applied to C#.

I have a Graph class that consists of Node and Connection objects. The graph contains collections consisting of all of the child Node and Connection objects associated with it. In addition to this, each Node has a collection of Connection objects.

public class Graph : IDeepCloneable<Graph>
{
  // These are basically just Dictionary<int,object>s wrapped in an ICollection
  public NodeCollection Nodes;
  public ConnectionCollection Connections;

  public Graph Clone()
  {
    return new Graph
    {
      Nodes = this.Nodes.Clone(),
      Connections = this.Connections.Clone()
    };
  }
}

public class Node : IDeepCloneable<Node>
{
  public int Id;
  public NodeConnectionCollection Connections;
  // NodeConnectionCollection is more or less the same as NodeCollection
  // except that it stores Connection objects into '.Incoming' and '.Outgoing' properties

  public Node Clone()
  {
    return new Node
    {
      Id = this.Id,
      Connections = this.Connections.Clone()
    };
  }
}

public class Connection : IDeepCloneable<Connection>
{
  public int Id;
  public Node From;
  public Node To;

  public Connection Clone()
  {
    return new Connection
    {
      Id = this.Id,
      From = this.From.Clone(),
      To = this.To.Clone()
    };
  }
}

Each of these objects support deep cloning, with the main idea being that consuming classes can call Clone() on child classes and work down the stack that way.

However, this is not viable in production. A call to Graph.Clone() will clone the NodeCollection and ConnectionCollection fields, which will clone each Node and Connection instance stored within them, which will each clone other referencing child elements.

A common solution seems to be storing the Ids of each child object and then rebuilding the references when all cloning is complete. However, as far as I am aware, this would require a reference to parent objects and tightly couple the data structure.

I am very puzzled at how to properly approach this. I require a reasonable amount of performance, as my application (a genetic algorithm) performs cloning constantly, but in this case I am more interested in finding a robust design pattern or implementation that will allow me to perform deep cloning of this graph structure while stashing a lot of the gruntwork behind the scenes.

Is there any design pattern that will allow me to clone this data structure as-is while updating circular references and maintaining its integrity?