Can one trace a criminal with his Pubkey?
Knowledge about his addresses and transaction history will be sufficient to discover addresses with which he made deals. His Private key will not help. This is the consequence of public ledger.

The different case is with deterministic wallets. When you know master private key/ mnemonic seed you can check all derived addresses, even the ones you have no previous knowledge.