Perception of Small Subgraphs in Graph Theory
On the Perception of Small
Subgraphs
Jacob Miller,
Mohammad Ghoniem,
Hsiang-Yun Wu,
Helen Purchase
1
2
Which of these are more similar?
3
Which of these are more similar?
?
4
Which of these are more similar?
5
Same Structure, different shape
Different structure, same shape
Hypotheses
Judge to be
different
Judge to be the
same
6
Three levels of perceptual processing (Ware 2021)
●
‘Bottom-up’: low-level properties
●
‘Pattern recognition’: grouping into regions,
patterns
●
‘Top-down’: Cognitive evaluation
7
Three levels of perceptual processing (Ware 2021)
●
‘Bottom-up’: low-level properties
●
‘
P
a
t
t
e
r
n
r
e
c
o
g
n
i
t
i
o
n
’
:
g
r
o
u
p
i
n
g
i
n
t
o
r
e
g
i
o
n
s
,
p
a
t
t
e
r
n
s
●
‘Top-down’: Cognitive evaluation
8
Gestalt Principle of Similarity
●
Distinct objects may be
grouped together by
looking similar
●
During pattern
recognition, subgraphs
may be grouped together
by looking similar
Source: Creative Beacon
9
Graph motifs
●
Subgraph, together with a drawing
Motif of
10
Experimental design: Overview
Define “base” motifs
Plant variations of motifs into graphs
Experiment 1
●
Compare base motif to
modified motifs
●
Modify by
○
Structure
○
Shape
○
Both
Experiment 2
●
Compare base motif to
force-directed-modified
motif
11
Experimental Design: Motifs
●
5 interesting and identifiable motifs
Bi-clique
Clique
Cycle
Double-cycle
Star
12
Experimental Design: Motif Variations
●
2-dimension variations
○
Structure
○
Shape
GED = 1
GED = 2
GED = 3
GED: Graph Edit Distance
13
Experimental Design: Generating Layouts
1.
Generate random graph
Graph
|V|=50; |E|~100
14
Experimental Design: Generating Layouts
1.
Generate random graph
2.
Stitch motif into graph
Graph
|V|=55; |E|~100
15
Experimental Design: Generating Layouts
1.
Generate random graph
2.
Stitch motif into graph
3.
Layout graph by constrained MDS
16
Experimental Design: Generating Layouts
1.
Generate random graph
2.
Stitch motif into graph
3.
Layout by constrained MDS
4.
Edit graph/layout to satisfy
constraints
17
Experimental procedure
●
Crowd-sourced
●
Used Prolific+Qualtrics
●
5 sets of experiments, 1 for each motif
●
30 valid participants each, around 10 minutes per participant
18
Experimental Design: Procedure
●
We ask participants to evaluate two graphs with highlighted motifs
○
One base motif, one modified motif
●
“Do the two highlighted sections represent the same friendship
relationships?”
●
Participants had 4 seconds to respond
19
20
21
Experimental Design: Dependent Variable
●
Similarity accuracy
○
Measured by how ‘correct’ the response was
Responses
Graph Edit Distance
22
Results: Q1
●
Does rotation affect the perception of the same sub-graph represented using
the same visual form?
23
Results: Q1
●
Is there a significant difference in accuracy when comparing the base motif
with rotarted variations?
24
No
Results: Q2
●
If the motif is adapted to create a sub-graph of different structure, does
depicting it in a similar manner affect the ability to distinguish the difference?
25
Results: Q2
●
I
s
t
h
e
r
e
a
s
i
g
n
i
f
i
c
a
n
t
d
i
f
f
e
r
e
n
c
e
i
n
a
c
c
u
r
a
c
y
b
e
t
w
e
e
n
i
d
e
n
t
i
f
y
i
n
g
d
i
f
f
e
r
e
n
t
m
o
t
i
f
s
(
c
o
m
p
a
r
e
d
w
i
t
h
t
h
e
b
a
s
e
)
w
i
t
h
t
h
e
s
a
m
e
o
r
d
i
f
f
e
r
e
n
t
v
i
s
u
a
l
f
o
r
m
s
?
26
Yes
Except for double-cycle
Results: Q3
●
Does using a different layout affect perception of motifs of the same
structure?
27
Results: Q3
●
I
s
t
h
e
r
e
a
s
i
g
n
i
f
i
c
a
n
t
d
i
f
f
e
r
e
n
c
e
i
n
a
c
c
u
r
a
c
y
b
e
t
w
e
e
n
i
d
e
n
t
i
f
y
i
n
g
i
d
e
n
t
i
c
a
l
m
o
t
i
f
s
(
c
o
m
p
a
r
e
d
w
i
t
h
t
h
e
b
a
s
e
)
w
i
t
h
t
h
e
s
a
m
e
o
r
d
i
f
f
e
r
e
n
t
v
i
s
u
a
l
f
o
r
m
s
?
28
Yes
Results: Q4
●
If different sub-graphs are depicted in similar shape, are near-similar sub-
graphs incorrectly assessed as being similar?
29
Results: Q4
●
Is there a significant difference when comparing identical motifs (GD=0)
versus highly dissimilar motifs (GED=1,2,3).
30
Yes
Results: Q5
●
Is it easier to match identical small motifs if they have both been given a well-
formed, regular shape?
31
Results: Q5
●
There is a significant difference in accuracy when identifying well-formed
motif structures in comparison with force-directed form
32
Results: Q5
●
T
h
e
r
e
i
s
a
s
i
g
n
i
f
i
c
a
n
t
d
i
f
f
e
r
e
n
c
e
i
n
a
c
c
u
r
a
c
y
w
h
e
n
i
d
e
n
t
i
f
y
i
n
g
m
o
d
i
f
i
e
d
,
y
e
t
w
e
l
l
-
f
o
r
m
e
d
m
o
t
i
f
s
t
r
u
c
t
u
r
e
s
i
n
c
o
m
p
a
r
i
s
o
n
w
i
t
h
f
o
r
c
e
-
d
i
r
e
c
t
e
d
f
o
r
m
○
Except for cycle
33
Recommendations
●
Draw identical subgraphs similarly
34
Recommendations
●
Draw dissimilar subgraphs (very) differently
35
Recommendations
●
Draw dissimilar subgraphs (very) differently
36
Future Work
●
We study 5-8 node motifs; Does this hold for larger
structures?
37
38
Cluster A
Cluster D
Cluster
C
Cluster B
Future Work
●
We study 5-8 node motifs; Does this hold for larger
structures?
●
Layout algorithms that identify motifs, and depict
them similarly
39
Acknowledgements
This work arose from collaboration initiated at Dagstuhl Seminar 23051,
“Perception in Network Visualization”, February 2023.
40
Future Work
●
We study 5-8 node motifs; Does this hold for larger
structures?
●
Layout algorithms that identify motifs, and depict them
similarly
Open for questions
41
Comments and Questions
42
Explore the perception of small subgraphs through the study of graph motifs and experimental design, touching on Gestalt principles of similarity and levels of perceptual processing. The research delves into how distinct objects can be grouped together based on similarity, influencing pattern recognition and cognitive evaluation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
On the Perception of Small Subgraphs Jacob Miller, Mohammad Ghoniem, Hsiang-Yun Wu, Helen Purchase 1
Which of these are more similar? Same Structure, different shape Different structure, same shape 5
Hypotheses Judge to be different Judge to be the same 6
Three levels of perceptual processing (Ware 2021) Bottom-up : low-level properties Pattern recognition : grouping into regions, patterns Top-down : Cognitive evaluation 7
Three levels of perceptual processing (Ware 2021) Bottom-up : low-level properties Pattern recognition : grouping into regions, patterns Top-down : Cognitive evaluation 8
Source: Creative Beacon Gestalt Principle of Similarity Distinct objects may be grouped together by looking similar During pattern recognition, subgraphs may be grouped together by looking similar 9
Graph motifs Subgraph, together with a drawing Motif of 10
Experimental design: Overview Define base motifs Plant variations of motifs into graphs Experiment 2 Experiment 1 Compare base motif to force-directed-modified motif Compare base motif to modified motifs Modify by Structure Shape Both 11
Experimental Design: Motifs 5 interesting and identifiable motifs Bi-clique Clique Cycle Star Double-cycle 12
Experimental Design: Motif Variations 2-dimension variations Structure Shape GED: Graph Edit Distance GED = 1 GED = 2 GED = 3 13
Experimental Design: Generating Layouts 1. Generate random graph Graph |V|=50; |E|~100 14
Experimental Design: Generating Layouts 1. Generate random graph 2. Stitch motif into graph Graph |V|=55; |E|~100 15
Experimental Design: Generating Layouts 1. Generate random graph 2. Stitch motif into graph 3. Layout graph by constrained MDS 16
Experimental Design: Generating Layouts 1. Generate random graph 2. Stitch motif into graph 3. Layout by constrained MDS 4. Edit graph/layout to satisfy constraints 17
Experimental procedure Crowd-sourced Used Prolific+Qualtrics 5 sets of experiments, 1 for each motif 30 valid participants each, around 10 minutes per participant 18
Experimental Design: Procedure We ask participants to evaluate two graphs with highlighted motifs One base motif, one modified motif Do the two highlighted sections represent the same friendship relationships? Participants had 4 seconds to respond 19
Experimental Design: Dependent Variable Similarity accuracy Measured by how correct the response was Graph Edit Distance Responses 22
Results: Q1 Does rotation affect the perception of the same sub-graph represented using the same visual form? 23
Results: Q1 Is there a significant difference in accuracy when comparing the base motif with rotarted variations? No 24
Results: Q2 If the motif is adapted to create a sub-graph of different structure, does depicting it in a similar manner affect the ability to distinguish the difference? 25
Results: Q2 Is there a significant difference in accuracy between identifying different motifs (compared with the base) with the same or different visual forms? Yes Except for double-cycle 26
Results: Q3 Does using a different layout affect perception of motifs of the same structure? 27
Results: Q3 Is there a significant difference in accuracy between identifying identical motifs (compared with the base) with the same or different visual forms? Yes 28
Results: Q4 If different sub-graphs are depicted in similar shape, are near-similar sub- graphs incorrectly assessed as being similar? 29
Results: Q4 Is there a significant difference when comparing identical motifs (GD=0) versus highly dissimilar motifs (GED=1,2,3). Yes 30
Results: Q5 Is it easier to match identical small motifs if they have both been given a well- formed, regular shape? 31
Results: Q5 There is a significant difference in accuracy when identifying well-formed motif structures in comparison with force-directed form 32
Results: Q5 There is a significant difference in accuracy when identifying modified, yet well-formed motif structures in comparison with force-directed form Except for cycle 33
Recommendations Draw identical subgraphs similarly 34
Recommendations Draw dissimilar subgraphs (very) differently 35
Recommendations Draw dissimilar subgraphs (very) differently 36
Future Work We study 5-8 node motifs; Does this hold for larger structures? 37
Cluster A Cluster B Cluster D Cluster C 38
Future Work We study 5-8 node motifs; Does this hold for larger structures? Layout algorithms that identify motifs, and depict them similarly 39
Acknowledgements This work arose from collaboration initiated at Dagstuhl Seminar 23051, Perception in Network Visualization , February 2023. 40
Future Work We study 5-8 node motifs; Does this hold for larger structures? Layout algorithms that identify motifs, and depict them similarly Open for questions 41
