largest connected component confusion

[qubit0]

If I use:

from torch_geometric.datasets import Planetoid, WebKB
from torch_geometric.transforms import LargestConnectedComponents

and get_dataset with use_lcc=True:
https://github.com/gasteigerjo/gdc/blob/master/data.py
for citeseer, I get the same result. However, I get a different result for Wisconsin. PyG lcc gives back the full dataset as Wisconsin is not disconnected. However, the get_dataset gives me a graph with 184 nodes.

Citeseer is an undirected graph and Wisconsin is a directed graph. I do not know why I am getting different results. This is how they implement lcc:

def get_component(dataset: InMemoryDataset, start: int = 0) -> set:
    visited_nodes = set()
    queued_nodes = set([start])
    row, col = dataset.data.edge_index.numpy()
    while queued_nodes:
        current_node = queued_nodes.pop()
        visited_nodes.update([current_node])
        neighbors = col[np.where(row == current_node)[0]]
        neighbors = [n for n in neighbors if n not in visited_nodes and n not in queued_nodes]
        queued_nodes.update(neighbors)
    return visited_nodes


def get_largest_connected_component(dataset: InMemoryDataset) -> np.ndarray:
    remaining_nodes = set(range(dataset.data.x.shape[0]))
    comps = []
    while remaining_nodes:
        start = min(remaining_nodes)
        comp = get_component(dataset, start)
        comps.append(comp)
        remaining_nodes = remaining_nodes.difference(comp)
    return np.array(list(comps[np.argmax(list(map(len, comps)))]))

It looks like PyG is using sp.csgraph.connected_components(adj) to get the connected component.
I am using PyG 2.1.0, so I didn't use connection='strong' . If I use connection='strong' then I get a graph with 14 nodes.

[rusty1s]

Thanks for the discussion. Can you clarify what there is to do on our end? Do you think our implementation is wrong?

[qubit0]

The code I am referring to is from a highly cited paper and I have seen the same code used in another highly cited paper to get the largest connected component(lcc). They both get the data from PyG but use this different way to get lcc. Both of these papers do not define what they mean by lcc in a directed graph.

I think PyG's implementation is correct as I get the same result with Networkx's strongly connected component function.

I am just asking here (in the discussion section rather than the issue) to see if someone else has run into this confusion. It's really hard to reproduce results. I just wanted to see if someone understood the definition of lcc for a directed graph used in those papers as those papers fail to define it.

[rusty1s]

I will look into the differences when I find some time, and keep you posted. Thanks for bringing this to our attention.

[qubit0]

Thanks a lot!