GraphTrials: Visual Proofs of Graph Properties

Area of Science:

• Computer Science
• Data Visualization
• Graph Theory

Background:

• Graph and network visualization is crucial for analyzing relational data across diverse domains.
• The rise of AI necessitates trustworthy and explainable methods for validating AI-generated insights from graph data.

Purpose of the Study:

• To introduce the concept of visual proofs for graph properties.
• To establish a framework for defining and creating visual proofs.
• To explore the role of visualization in verifying AI assertions about graphs.

Main Methods:

• Developed a framework defining visual proofs for graph properties.
• Introduced 'visual certificates'—specialized visualizations designed for perceptual verification.
• Analyzed the relationship between visual complexity, cognitive load, and complexity theory.
• Proposed a classification system for visual proof complexity.

Main Results:

• Defined visual proofs and visual certificates for graph properties.
• Demonstrated how visual certificates can leverage pre-attentive processing for efficient verification.
• Classified visual proofs based on their complexity.
• Provided examples of visual certificates for various graph problems.

Conclusions:

• Visual proofs offer a novel approach to validating graph properties, particularly for AI-generated claims.
• Visual certificates can enhance the trustworthiness and explainability of graph analysis.
• Further research is needed to explore limitations and expand the scope of visual proofs.