Layouts auto API

[diane-lee-01]

Hi, just wanted to start a thread about the layouts/auto API and run some ideas by everyone!

Here's a version where a lot of the structure stays the same as the current auto.py, but we could have a new function layout_auto where the user can specify ase/lse/n2v (or use their own embedding) and umap/tsne, then use the show_graph function to plot the layout. auto_v1.txt

def layout_auto(
        graph: nx.Graph,
        embedding: Optional[np.ndarray] = None,
        embedding_algorithm: str = "n2v",
        reducing_algorithm="umap",
        n_components: int = 32,
        max_edges: int = 10000000,
        random_seed: Optional[int] = None,
        adjust_overlaps: bool = True,
        embed_kws={},
        reduce_kws={},
) -> Tuple[nx.Graph, List[NodePosition]]:
    """
    Automatic graph layout generation by creating an ase/lse/n2v embedding, then using
    UMAP/TSNE for dimensionality reduction to 2d space.

    Parameters Added
    ------
    embedding : np.ndarray
        The embedding to be reduced. Default is None and will run the specified embedding
        algorithm on the input graph.
    embedding_algorithm : str
        The embedding algorithm. Default is ''n2v'' but can also use ''ase'' or ''lse''.
    reducing_algorithm: str
        Reduces the embedding to 2d space. Default is ''umap'' but can also use ''tsne''.
    embed_kws:
        Additional parameters specific to the embedding algorithm.
    reduce_kws:
        Additional parameters specific to the reducing algorithm.
    """
    return lcc_graph, positions


def _embed_for_layout(
        graph: nx.Graph,
        algorithm="n2v",
        n_components: int = 32,
        max_edges: int = 10000000,
        random_seed: Optional[int] = None,
        embed_kws={},
) -> Tuple[nx.Graph, np.ndarray, np.ndarray]:
    """
    Generate a n2v/ase/lse embedding after pruning edges by weight and finding the lcc.

    Similar structure to current auto.py _node2vec_for_layout function, but user can
    specify algorithm and additional parameters.
    """
    return graph, tensors, labels


show_graph[lcc_graph, positions, colors]

The second version is more similar to the code Ben posted in the layouts meta issue (#736), where there's one function that does everything from start to finish, including the plotting part. I think one interesting thing we could look at is comparing the run times between networkx and other packages? But here's the outline for what I think the function could look like. auto_v2.txt

def plot_layout_auto(
        graph: nx.Graph,
        embedding: Optional[np.ndarray] = None,
        embedding_algorithm: str = "n2v",
        reducing_algorithm: str ="umap",
        n_components: int = 32,
        max_edges: int = 10000000,
        random_seed: Optional[int] = None,
        adjust_overlaps: bool = True,
        figsize: (float,float) = (15.0,15.0),
        vertex_shape: str = "o",
        vertex_line_width: float = 0.01,
        vertex_alpha: float = 0.55,
        edge_line_width: float = 0.5,
        edge_alpha: float = 0.02,
        light_background: bool = True,
        cmap=None,
        vmin=None,
        vmax=None,
        legend: bool = False,
        savefig: bool = False,
        verbose: bool = False,
        embed_kws={},
        reduce_kws={},
        plot_kws={}
):
    """
    Automatic graph layout generation by creating an ase/lse/n2v embedding, then using
    UMAP/TSNE for dimensionality reduction to 2d space.

    Renders and displays layout.
    """

We could also potentially think about exposing all of these functions for each step, where the user would call them individually as needed and follow a workflow, but just more food for thought. auto_v3.txt

def preprocessing_for_layout(
        graph: nx.Graph,
        max_edges: int = 10000000,
) -> nx.Graph:
    """
    Approximate pruning and find lcc of graph.
    """
    return lcc_graph

def embed_for_layout(
        graph: nx.Graph,
        algorithm="n2v",
        n_components: int = 32,
        max_edges: int = 10000000,
        random_seed: Optional[int] = None,
        embed_kws={},
) -> Tuple[nx.Graph, np.ndarray, np.ndarray]:
    """
    Generate a n2v/ase/lse embedding of input graph.

    Similar structure to current auto.py _node2vec_for_layout function, but user can
    specify algorithm and additional parameters.
    """
    return tensors, labels

def reduce_for_layout(
        embedding: np.ndarray,
        algorithm: str = "umap",
        metric="euclidean",
        random_seed: Optional[int] = None,
        reduce_kws={},
) -> np.ndarray:
    """
    Reduce embedding to 2d space using UMAP/TSNE.
    """
    return points_2d

def get_node_positions(
        graph: nx.Graph,
        labels: np.ndarray,
        down_projection_2d: np.ndarray,
        random_seed: Optional[int] = None,
        adjust_overlaps: bool = True,
) -> List[NodePosition]:
    """
    Get list of NodePositions for each node in the graph.
    """
    return positions

lcc_g = preprocessing_for_layout(g)
tensors, labels = embed_for_layout(g)
points_2d = reduce_for_layout(tensors)
positions = get_node_positions(lcc_g, labels, points_2d)
show_graph(lcc_g, positions, colors)

I think this covers most of what we talked about @bdpedigo, but please let me know if I missed anything! Thoughts?

[bdpedigo]

hey @dlee0156 - this looks like a great start for this conversation! Do you think you could just copy paste what you have in those text files into your comment (or new ones)? I think this will make it easier for folks to provide feedback.

cc: @dwaynepryce @bryantower

[diane-lee-01]

Yup just updated!

[daxpryce]

as an aside, @daxpryce - I was wondering why I didn't get a notif for this earlier!

[bdpedigo]

oops i must have done this before i saw that your handle changed, my bad!

[bryantower]

Thanks for putting some thought into this. All three of these approaches have some merit. The 2nd proposal seems like it is doing a lot. I like decomposing the problem a little bit more than that if we are not going completely on rails (with the defaults).

Both the first and the third solutions have two different methods that take in the max_edges parameter. I think we want to avoid that. We want there to be a clear flow. If we are going to force someone to provide the embedding, then the graph preprocessing should be done before the layout method.

In the third solution it looks like the intent is for the preprocessing_for_layoutmethod to be called before the embed_for_layout method. If that is the case we should not provide the max_edges parameter to the embed_for_layout.

I think one other thing that would help is to write a layout method that produces the complete layout in proposal 1 and 3. Obviously proposal 2 has everything in that one method. That will help in two ways, 1, you will be able to solidify the methods proposed are sufficient and 2, you should be able to see if there is friction with the proposed methods and completing the full layout.

[bryantower]

The colors is a separate step from the positions in the workflow. If you look at the workflow above you see that they are separate calls.

[bdpedigo]

what i meant is this line
positions, partitions = get_node_positions(lcc_g, labels, points_2d)
im dont believe the labels/partitions need to have anything to do with getting node positions here, is there something I'm missing?

[diane-lee-01]

I made the get_node_positions output both positions and partitions because the _node_positions_from in auto.py runs leiden (and gets the partitions) to get the node positions within the function already. But I think it makes sense that there should be two separate functions for positions vs. partitions. Maybe it could look something like this?

def get_partitions(graph: nx.Graph) -> Dict:
    if isinstance(graph, nx.DiGraph):
        temp_graph = symmetrize(graph)
        logger.warning("Directed graph converted to undirected graph for community detection")
        partitions = leiden(temp_graph, random_seed=random_seed)
    else:
        partitions = leiden(graph, random_seed=random_seed)
    return partitions

[bdpedigo]

I would be in favor of this in the spirit of decomposing this function into minimal units - for instance, sometimes we wont want to run leiden since we already have something we want to color by, or sometimes we will want to run leiden but not no overlap, or sometimes neither. So I think something like what you have above makes sense.

[bryantower]

I am in favor of breaking the partitions and positions into separate functions. I think there was some reason why they got merged but it was probably more about getting something done than getting it done right.

[daxpryce]

Only minor comments here, it's looking pretty good as it goes. One thing is in embed_for_layout, you're going to want to do preconditions checks to ensure that nobody calls it with the 100% fabricated "DaxStupidEmbedderOfDoom" argument that has no actual impl. Just make sure you do your precons to make sure nobody calls it with the wrong magic strings.

Next, I'd change "reduce_for_layout" to "reduce_dimensionality" - sure, it's for the layout, but "reduce for layout" isn't specific enough on what is being reduced, though it does tell us what it's for. reduce_dimensionality_for_layout is fine, if probably overly verbose.

preprocessing_for_layout should also be turned into a verb, but I'm not coming up with a super obvious name for "potentially shrink this to at most n edges and then make sure we're only looking at the LCC". so maybe the obvious solution is preprocess_for_layout, but if you can think of something more accurate for the operation we're doing, and maybe why we're doing it, that would make for a better name. again, as long as it's a verb.

One question about doing the embed part: for lse you specifically force us to use R-DAD - is there a reason we do that? If it is just more ideal, you should instead check to see if form is present in embed_kws, and if not set it to R-DAD, but if it is do nothing -- that way you aren't superceding the user's selections.

One thing we're not doing for all of these broken out functions is the sanity checks that we got by default by only being able to use them via the auto flow. For instance, we knew (before) that the graph would be a single connect component - because we specifically did that. However, as we expose each chunk, guarantees fall on the caller and the caller may not know how important it is to only use a single CC for this to give us something reasonable.

Maybe we add a boolean parameter that is set to False by default called like, uh... previously_validated or something. If it's set to True, we don't do the basic is an undirected graph and is an lcc checks in each of the componetitized functions, and if it's set to the default of False, we check every time. That way the user has to manually opt out of validation steps, but they can do it safely if they've done the LCC/undirectederizing steps?

[diane-lee-01]

Makes sense, thank you for the comments!

I'll change the function names so that they all start with verbs and add parts where we check for undirected + lcc. Adding a boolean also sounds like a great idea so that the user can choose to opt out of it, and yes, form shouldn't have been set to R-DAD. Thanks so much for taking the time to look at this!

[diane-lee-01]

I also have been thinking about a plot_layout function that takes in positions and edges and produces a graph. It could take in parameters that are similar to seaborn functions such as palette or hue, which may be more intuitive to use than the show_graph function we have right now in render.py. This is just an initial outline of what I think it could look like:

def plot_layout(
    positions: List[NodePosition],
    edges: np.ndarray,
    figsize: Tuple[float, float] = (10, 10),
    palette: str = "Set1",
    hue: Optional[str] = None,
    vertex_linewidth: float = 0.01,
    vertex_alpha: float = 0.5,
    edge_linewidth: float = 0.5,
    edge_alpha: float = 0.5,
    title=None,
    legend=None,
):

We could also maybe have a boolean parameter called autoscale that lets the user decide whether or not to automatically scale node sizes/alphas and edge line widths/alphas (and overrides the default values)? Thanks!