A question on completeness in theorem3.2

[wjxts]

consider the graph list: {B-A-C, A-B, D-A-C}, the vocab can be {B-A, B-A-C, D-A, D-A-C}, for principal subgraph A-C, there is no subgraph in vocab that contains A-C and has the same frequency with A-C?

[kxz18]

Looks like A-B has the same frequency with A-C and has been included in the vocab? (graphs are undirected so A-B is equal to B-A)

[wjxts]

thanks for reply! We can change the graph list to: {B-A-C, A-B, A-B, D-A-C, D-A}, then the vocab must be {B-A, B-A-C, D-A, D-A-C}, there is no subgraph in vocab that contains A-C and has the same frequency with A-C?

[kxz18]

Looks like in this case A-C is not a principle subgraph because B-A intersects with A-C in the first graph but has higher frequency than A-C. There exists a subgraph that intersects with A-C yet neither is a subgraph of A-C nor has a frequency lower or equal to A-C.

[wjxts]

Oh yes, I made a mistake in the second case, thanks!

[wjxts]

For the first case, the problem will occur if A-B are extracted before A-C, I think this kind of cases may be rare.

an augmented case: {B-A-C, A-B, D-A-C, D-A}, either B-A or D-A is extracted before A-C, A-C will be ignored in vocab.

[wjxts]

Besides, for the significance in theorem3.2, if we have graph list: {B-A-C, B-A, B-A, B-A, A-C, A-C, }, then A-C will be in the vocab, but A-C is not a principal subgraph?

[kxz18]

Yes, this looks like a valid counter example. Good insight! So looks like when there have three or more principle subgraphs sharing the same frequency, the "completeness" might be broken in some corner cases. Maybe some prefixes like "under the condition that no more than two intersecting principle subgraphs have the same frequency" should be added to the theorem. Though it's true that violation of such condition is barely visible in real world datasets.